[PATCH]: Use ebitmaps in df.[ch], rewrite to use iterative dataflowfunctions
Daniel Berlin
dan@cgsoftware.com
Thu Aug 30 06:12:00 GMT 2001
Requires the ebitmap patch.
Once again, ignore the ssa-* dependencies added.
Using ebitmaps speeds up dataflow by a large amount, and reduces
memory also by a large amount (For instance, for reaching defs on
one random function, it used to take at least 2 minutes and 150 meg. It
now takes 10 seconds and 90 meg.).
The patch looks like it does more than it really does, because of how
many places bitmap/BITMAP appeared.
2001-08-30 Daniel Berlin <dan@cgsoftware.com>
* Makefile.in (df.o): Add ebitmap.h to list of dependencies.
* df.h: Add prototypes for transfer functions, iterative_dataflow
functions.
bitmap->ebitmap, BITMAP->EBITMAP.
(enum df_flow_dir): New enum.
(enum df_confluence_op): New enum.
(struct df): Add inverse_rts_map.
* df.c: bitmap->ebitmap, BITMAP->EBITMAP.
(df_rd_global_compute): Removed.
(df_ru_global_compute): Removed.
(df_lr_global_compute): Removed.
(df_rd_transfer_function): New function.
(df_ru_transfer_function): New function.
(df_lr_transfer_function): New function.
(df_analyse_1): Allocate/Compute/Free df->inverse_rts_map.
Use iterative_dataflow_ebitmap instead of df_*_global_compute.
(iterative_dataflow_sbitmap): New function.
(iterative_dataflow_ebitmap): New function.
Index: df.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/df.c,v
retrieving revision 1.11
diff -c -3 -p -w -B -b -r1.11 df.c
*** df.c 2001/08/28 23:43:20 1.11
--- df.c 2001/08/30 13:02:46
*************** Perhaps there should be a bitmap argumen
*** 165,174 ****
#include "obstack.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "bitmap.h"
#include "df.h"
-
#define FOR_ALL_BBS(BB, CODE) \
do { \
int node_; \
--- 165,175 ----
#include "obstack.h"
#include "hard-reg-set.h"
#include "basic-block.h"
+ #include "sbitmap.h"
#include "bitmap.h"
#include "df.h"
+ #include "fibheap.h"
#define FOR_ALL_BBS(BB, CODE) \
do { \
int node_; \
*************** do { \
*** 175,190 ****
for (node_ = 0; node_ < n_basic_blocks; node_++) \
{(BB) = BASIC_BLOCK (node_); CODE;};} while (0)
! #define FOR_EACH_BB_IN_BITMAP(BITMAP, MIN, BB, CODE) \
do { \
unsigned int node_; \
! EXECUTE_IF_SET_IN_BITMAP (BITMAP, MIN, node_, \
{(BB) = BASIC_BLOCK (node_); CODE;});} while (0)
! #define FOR_EACH_BB_IN_BITMAP_REV(BITMAP, MIN, BB, CODE) \
do { \
unsigned int node_; \
! EXECUTE_IF_SET_IN_BITMAP_REV (BITMAP, node_, \
{(BB) = BASIC_BLOCK (node_); CODE;});} while (0)
#define FOR_EACH_BB_IN_SBITMAP(BITMAP, MIN, BB, CODE) \
--- 176,191 ----
for (node_ = 0; node_ < n_basic_blocks; node_++) \
{(BB) = BASIC_BLOCK (node_); CODE;};} while (0)
! #define FOR_EACH_BB_IN_EBITMAP(BITMAP, MIN, BB, CODE) \
do { \
unsigned int node_; \
! EXECUTE_IF_SET_IN_EBITMAP (BITMAP, MIN, node_, \
{(BB) = BASIC_BLOCK (node_); CODE;});} while (0)
! #define FOR_EACH_BB_IN_EBITMAP_REV(BITMAP, MIN, BB, CODE) \
do { \
unsigned int node_; \
! EXECUTE_IF_SET_IN_EBITMAP_REV (BITMAP, node_, \
{(BB) = BASIC_BLOCK (node_); CODE;});} while (0)
#define FOR_EACH_BB_IN_SBITMAP(BITMAP, MIN, BB, CODE) \
*************** static void df_uses_record PARAMS((struc
*** 236,285 ****
enum df_ref_type, basic_block, rtx));
static void df_insn_refs_record PARAMS((struct df *, basic_block, rtx));
static void df_bb_refs_record PARAMS((struct df *, basic_block));
! static void df_refs_record PARAMS((struct df *, bitmap));
- static int df_visit_next_rc PARAMS ((struct df *, sbitmap));
- static int df_visit_next_rts PARAMS ((struct df *, sbitmap));
static void df_bb_reg_def_chain_create PARAMS((struct df *, basic_block));
! static void df_reg_def_chain_create PARAMS((struct df *, bitmap));
static void df_bb_reg_use_chain_create PARAMS((struct df *, basic_block));
! static void df_reg_use_chain_create PARAMS((struct df *, bitmap));
! static void df_bb_du_chain_create PARAMS((struct df *, basic_block, bitmap));
! static void df_du_chain_create PARAMS((struct df *, bitmap));
static void df_bb_ud_chain_create PARAMS((struct df *, basic_block));
! static void df_ud_chain_create PARAMS((struct df *, bitmap));
! static void df_rd_global_compute PARAMS((struct df *, bitmap));
! static void df_ru_global_compute PARAMS((struct df *, bitmap));
! static void df_lr_global_compute PARAMS((struct df *, bitmap));
static void df_bb_rd_local_compute PARAMS((struct df *, basic_block));
! static void df_rd_local_compute PARAMS((struct df *, bitmap));
static void df_bb_ru_local_compute PARAMS((struct df *, basic_block));
! static void df_ru_local_compute PARAMS((struct df *, bitmap));
static void df_bb_lr_local_compute PARAMS((struct df *, basic_block));
! static void df_lr_local_compute PARAMS((struct df *, bitmap));
! static void df_bb_reg_info_compute PARAMS((struct df *, basic_block, bitmap));
! static void df_reg_info_compute PARAMS((struct df *, bitmap));
static int df_bb_luids_set PARAMS((struct df *df, basic_block));
! static int df_luids_set PARAMS((struct df *df, bitmap));
! static int df_modified_p PARAMS ((struct df *, bitmap));
static int df_refs_queue PARAMS ((struct df *));
static int df_refs_process PARAMS ((struct df *));
static int df_bb_refs_update PARAMS ((struct df *, basic_block));
static int df_refs_update PARAMS ((struct df *));
! static void df_analyse_1 PARAMS((struct df *, bitmap, int, int));
static void df_insns_modify PARAMS((struct df *, basic_block,
rtx, rtx));
static int df_rtx_mem_replace PARAMS ((rtx *, void *));
static int df_rtx_reg_replace PARAMS ((rtx *, void *));
! void df_refs_reg_replace PARAMS ((struct df *, bitmap,
struct df_link *, rtx, rtx));
static int df_def_dominates_all_uses_p PARAMS((struct df *, struct ref *def));
static int df_def_dominates_uses_p PARAMS((struct df *,
! struct ref *def, bitmap));
static struct ref *df_bb_regno_last_use_find PARAMS((struct df *, basic_block,
unsigned int));
static struct ref *df_bb_regno_first_def_find PARAMS((struct df *, basic_block,
--- 237,281 ----
enum df_ref_type, basic_block, rtx));
static void df_insn_refs_record PARAMS((struct df *, basic_block, rtx));
static void df_bb_refs_record PARAMS((struct df *, basic_block));
! static void df_refs_record PARAMS((struct df *, ebitmap));
static void df_bb_reg_def_chain_create PARAMS((struct df *, basic_block));
! static void df_reg_def_chain_create PARAMS((struct df *, ebitmap));
static void df_bb_reg_use_chain_create PARAMS((struct df *, basic_block));
! static void df_reg_use_chain_create PARAMS((struct df *, ebitmap));
! static void df_bb_du_chain_create PARAMS((struct df *, basic_block, ebitmap));
! static void df_du_chain_create PARAMS((struct df *, ebitmap));
static void df_bb_ud_chain_create PARAMS((struct df *, basic_block));
! static void df_ud_chain_create PARAMS((struct df *, ebitmap));
static void df_bb_rd_local_compute PARAMS((struct df *, basic_block));
! static void df_rd_local_compute PARAMS((struct df *, ebitmap));
static void df_bb_ru_local_compute PARAMS((struct df *, basic_block));
! static void df_ru_local_compute PARAMS((struct df *, ebitmap));
static void df_bb_lr_local_compute PARAMS((struct df *, basic_block));
! static void df_lr_local_compute PARAMS((struct df *, ebitmap));
! static void df_bb_reg_info_compute PARAMS((struct df *, basic_block, ebitmap));
! static void df_reg_info_compute PARAMS((struct df *, ebitmap));
static int df_bb_luids_set PARAMS((struct df *df, basic_block));
! static int df_luids_set PARAMS((struct df *df, ebitmap));
! static int df_modified_p PARAMS ((struct df *, ebitmap));
static int df_refs_queue PARAMS ((struct df *));
static int df_refs_process PARAMS ((struct df *));
static int df_bb_refs_update PARAMS ((struct df *, basic_block));
static int df_refs_update PARAMS ((struct df *));
! static void df_analyse_1 PARAMS((struct df *, ebitmap, int, int));
static void df_insns_modify PARAMS((struct df *, basic_block,
rtx, rtx));
static int df_rtx_mem_replace PARAMS ((rtx *, void *));
static int df_rtx_reg_replace PARAMS ((rtx *, void *));
! void df_refs_reg_replace PARAMS ((struct df *, ebitmap,
struct df_link *, rtx, rtx));
static int df_def_dominates_all_uses_p PARAMS((struct df *, struct ref *def));
static int df_def_dominates_uses_p PARAMS((struct df *,
! struct ref *def, ebitmap));
static struct ref *df_bb_regno_last_use_find PARAMS((struct df *, basic_block,
unsigned int));
static struct ref *df_bb_regno_first_def_find PARAMS((struct df *, basic_block,
*************** static void df_chain_dump PARAMS((struct
*** 295,300 ****
--- 291,302 ----
static void df_chain_dump_regno PARAMS((struct df_link *, FILE *file));
static void df_regno_debug PARAMS ((struct df *, unsigned int, FILE *));
static void df_ref_debug PARAMS ((struct df *, struct ref *, FILE *));
+ static void df_rd_transfer_function PARAMS ((int, int *, ebitmap, ebitmap,
+ ebitmap, ebitmap, void *));
+ static void df_ru_transfer_function PARAMS ((int, int *, ebitmap, ebitmap,
+ ebitmap, ebitmap, void *));
+ static void df_lr_transfer_function PARAMS ((int, int *, ebitmap, ebitmap,
+ ebitmap, ebitmap, void *));
/* Local memory allocation/deallocation routines. */
*************** df_insn_table_realloc (df, size)
*** 322,329 ****
if (! df->insns_modified)
{
! df->insns_modified = BITMAP_XMALLOC ();
! bitmap_zero (df->insns_modified);
}
}
--- 324,331 ----
if (! df->insns_modified)
{
! df->insns_modified = EBITMAP_XMALLOC ();
! ebitmap_zero (df->insns_modified);
}
}
*************** df_bitmaps_alloc (df, flags)
*** 414,450 ****
if (flags & DF_RD && ! bb_info->rd_in)
{
/* Allocate bitmaps for reaching definitions. */
! bb_info->rd_kill = BITMAP_XMALLOC ();
! bitmap_zero (bb_info->rd_kill);
! bb_info->rd_gen = BITMAP_XMALLOC ();
! bitmap_zero (bb_info->rd_gen);
! bb_info->rd_in = BITMAP_XMALLOC ();
! bb_info->rd_out = BITMAP_XMALLOC ();
bb_info->rd_valid = 0;
}
if (flags & DF_RU && ! bb_info->ru_in)
{
/* Allocate bitmaps for upward exposed uses. */
! bb_info->ru_kill = BITMAP_XMALLOC ();
! bitmap_zero (bb_info->ru_kill);
/* Note the lack of symmetry. */
! bb_info->ru_gen = BITMAP_XMALLOC ();
! bitmap_zero (bb_info->ru_gen);
! bb_info->ru_in = BITMAP_XMALLOC ();
! bb_info->ru_out = BITMAP_XMALLOC ();
bb_info->ru_valid = 0;
}
if (flags & DF_LR && ! bb_info->lr_in)
{
/* Allocate bitmaps for live variables. */
! bb_info->lr_def = BITMAP_XMALLOC ();
! bitmap_zero (bb_info->lr_def);
! bb_info->lr_use = BITMAP_XMALLOC ();
! bitmap_zero (bb_info->lr_use);
! bb_info->lr_in = BITMAP_XMALLOC ();
! bb_info->lr_out = BITMAP_XMALLOC ();
bb_info->lr_valid = 0;
}
}
--- 416,452 ----
if (flags & DF_RD && ! bb_info->rd_in)
{
/* Allocate bitmaps for reaching definitions. */
! bb_info->rd_kill = EBITMAP_XMALLOC ();
! ebitmap_zero (bb_info->rd_kill);
! bb_info->rd_gen = EBITMAP_XMALLOC ();
! ebitmap_zero (bb_info->rd_gen);
! bb_info->rd_in = EBITMAP_XMALLOC ();
! bb_info->rd_out = EBITMAP_XMALLOC ();
bb_info->rd_valid = 0;
}
if (flags & DF_RU && ! bb_info->ru_in)
{
/* Allocate bitmaps for upward exposed uses. */
! bb_info->ru_kill = EBITMAP_XMALLOC ();
! ebitmap_zero (bb_info->ru_kill);
/* Note the lack of symmetry. */
! bb_info->ru_gen = EBITMAP_XMALLOC ();
! ebitmap_zero (bb_info->ru_gen);
! bb_info->ru_in = EBITMAP_XMALLOC ();
! bb_info->ru_out = EBITMAP_XMALLOC ();
bb_info->ru_valid = 0;
}
if (flags & DF_LR && ! bb_info->lr_in)
{
/* Allocate bitmaps for live variables. */
! bb_info->lr_def = EBITMAP_XMALLOC ();
! ebitmap_zero (bb_info->lr_def);
! bb_info->lr_use = EBITMAP_XMALLOC ();
! ebitmap_zero (bb_info->lr_use);
! bb_info->lr_in = EBITMAP_XMALLOC ();
! bb_info->lr_out = EBITMAP_XMALLOC ();
bb_info->lr_valid = 0;
}
}
*************** df_bitmaps_free (df, flags)
*** 470,508 ****
if ((flags & DF_RD) && bb_info->rd_in)
{
/* Free bitmaps for reaching definitions. */
! BITMAP_XFREE (bb_info->rd_kill);
bb_info->rd_kill = NULL;
! BITMAP_XFREE (bb_info->rd_gen);
bb_info->rd_gen = NULL;
! BITMAP_XFREE (bb_info->rd_in);
bb_info->rd_in = NULL;
! BITMAP_XFREE (bb_info->rd_out);
bb_info->rd_out = NULL;
}
if ((flags & DF_RU) && bb_info->ru_in)
{
/* Free bitmaps for upward exposed uses. */
! BITMAP_XFREE (bb_info->ru_kill);
bb_info->ru_kill = NULL;
! BITMAP_XFREE (bb_info->ru_gen);
bb_info->ru_gen = NULL;
! BITMAP_XFREE (bb_info->ru_in);
bb_info->ru_in = NULL;
! BITMAP_XFREE (bb_info->ru_out);
bb_info->ru_out = NULL;
}
if ((flags & DF_LR) && bb_info->lr_in)
{
/* Free bitmaps for live variables. */
! BITMAP_XFREE (bb_info->lr_def);
bb_info->lr_def = NULL;
! BITMAP_XFREE (bb_info->lr_use);
bb_info->lr_use = NULL;
! BITMAP_XFREE (bb_info->lr_in);
bb_info->lr_in = NULL;
! BITMAP_XFREE (bb_info->lr_out);
bb_info->lr_out = NULL;
}
}
--- 472,510 ----
if ((flags & DF_RD) && bb_info->rd_in)
{
/* Free bitmaps for reaching definitions. */
! EBITMAP_XFREE (bb_info->rd_kill);
bb_info->rd_kill = NULL;
! EBITMAP_XFREE (bb_info->rd_gen);
bb_info->rd_gen = NULL;
! EBITMAP_XFREE (bb_info->rd_in);
bb_info->rd_in = NULL;
! EBITMAP_XFREE (bb_info->rd_out);
bb_info->rd_out = NULL;
}
if ((flags & DF_RU) && bb_info->ru_in)
{
/* Free bitmaps for upward exposed uses. */
! EBITMAP_XFREE (bb_info->ru_kill);
bb_info->ru_kill = NULL;
! EBITMAP_XFREE (bb_info->ru_gen);
bb_info->ru_gen = NULL;
! EBITMAP_XFREE (bb_info->ru_in);
bb_info->ru_in = NULL;
! EBITMAP_XFREE (bb_info->ru_out);
bb_info->ru_out = NULL;
}
if ((flags & DF_LR) && bb_info->lr_in)
{
/* Free bitmaps for live variables. */
! EBITMAP_XFREE (bb_info->lr_def);
bb_info->lr_def = NULL;
! EBITMAP_XFREE (bb_info->lr_use);
bb_info->lr_use = NULL;
! EBITMAP_XFREE (bb_info->lr_in);
bb_info->lr_in = NULL;
! EBITMAP_XFREE (bb_info->lr_out);
bb_info->lr_out = NULL;
}
}
*************** df_alloc (df, n_regs)
*** 547,562 ****
df_reg_table_realloc (df, df->n_regs);
! df->bbs_modified = BITMAP_XMALLOC ();
! bitmap_zero (df->bbs_modified);
df->flags = 0;
df->bbs = xcalloc (df->n_bbs, sizeof (struct bb_info));
! df->all_blocks = BITMAP_XMALLOC ();
for (i = 0; i < n_basic_blocks; i++)
! bitmap_set_bit (df->all_blocks, i);
}
--- 549,564 ----
df_reg_table_realloc (df, df->n_regs);
! df->bbs_modified = EBITMAP_XMALLOC ();
! ebitmap_zero (df->bbs_modified);
df->flags = 0;
df->bbs = xcalloc (df->n_bbs, sizeof (struct bb_info));
! df->all_blocks = EBITMAP_XMALLOC ();
for (i = 0; i < n_basic_blocks; i++)
! ebitmap_set_bit (df->all_blocks, i);
}
*************** df_free (df)
*** 594,607 ****
df->reg_size = 0;
if (df->bbs_modified)
! BITMAP_XFREE (df->bbs_modified);
df->bbs_modified = 0;
if (df->insns_modified)
! BITMAP_XFREE (df->insns_modified);
df->insns_modified = 0;
! BITMAP_XFREE (df->all_blocks);
df->all_blocks = 0;
obstack_free (&df_ref_obstack, NULL);
--- 596,609 ----
df->reg_size = 0;
if (df->bbs_modified)
! EBITMAP_XFREE (df->bbs_modified);
df->bbs_modified = 0;
if (df->insns_modified)
! EBITMAP_XFREE (df->insns_modified);
df->insns_modified = 0;
! EBITMAP_XFREE (df->all_blocks);
df->all_blocks = 0;
obstack_free (&df_ref_obstack, NULL);
*************** df_bb_refs_record (df, bb)
*** 1316,1326 ****
static void
df_refs_record (df, blocks)
struct df *df;
! bitmap blocks;
{
basic_block bb;
! FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_refs_record (df, bb);
});
--- 1318,1328 ----
static void
df_refs_record (df, blocks)
struct df *df;
! ebitmap blocks;
{
basic_block bb;
! FOR_EACH_BB_IN_EBITMAP (blocks, 0, bb,
{
df_bb_refs_record (df, bb);
});
*************** df_bb_reg_def_chain_create (df, bb)
*** 1369,1379 ****
static void
df_reg_def_chain_create (df, blocks)
struct df *df;
! bitmap blocks;
{
basic_block bb;
! FOR_EACH_BB_IN_BITMAP/*_REV*/ (blocks, 0, bb,
{
df_bb_reg_def_chain_create (df, bb);
});
--- 1371,1381 ----
static void
df_reg_def_chain_create (df, blocks)
struct df *df;
! ebitmap blocks;
{
basic_block bb;
! FOR_EACH_BB_IN_EBITMAP/*_REV*/ (blocks, 0, bb,
{
df_bb_reg_def_chain_create (df, bb);
});
*************** df_bb_reg_use_chain_create (df, bb)
*** 1418,1428 ****
static void
df_reg_use_chain_create (df, blocks)
struct df *df;
! bitmap blocks;
{
basic_block bb;
! FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_reg_use_chain_create (df, bb);
});
--- 1420,1430 ----
static void
df_reg_use_chain_create (df, blocks)
struct df *df;
! ebitmap blocks;
{
basic_block bb;
! FOR_EACH_BB_IN_EBITMAP (blocks, 0, bb,
{
df_bb_reg_use_chain_create (df, bb);
});
*************** static void
*** 1434,1445 ****
df_bb_du_chain_create (df, bb, ru)
struct df *df;
basic_block bb;
! bitmap ru;
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
! bitmap_copy (ru, bb_info->ru_out);
/* For each def in BB create a linked list (chain) of uses
reached from the def. */
--- 1436,1447 ----
df_bb_du_chain_create (df, bb, ru)
struct df *df;
basic_block bb;
! ebitmap ru;
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
! ebitmap_copy (ru, bb_info->ru_out);
/* For each def in BB create a linked list (chain) of uses
reached from the def. */
*************** df_bb_du_chain_create (df, bb, ru)
*** 1469,1480 ****
{
struct ref *use = use_link->ref;
! if (bitmap_bit_p (ru, DF_REF_ID (use)))
{
DF_REF_CHAIN (def)
= df_link_create (use, DF_REF_CHAIN (def));
! bitmap_clear_bit (ru, DF_REF_ID (use));
}
}
}
--- 1471,1482 ----
{
struct ref *use = use_link->ref;
! if (ebitmap_bit_p (ru, DF_REF_ID (use)))
{
DF_REF_CHAIN (def)
= df_link_create (use, DF_REF_CHAIN (def));
! ebitmap_clear_bit (ru, DF_REF_ID (use));
}
}
}
*************** df_bb_du_chain_create (df, bb, ru)
*** 1483,1489 ****
for (use_link = df->insns[uid].uses; use_link; use_link = use_link->next)
{
struct ref *use = use_link->ref;
! bitmap_set_bit (ru, DF_REF_ID (use));
}
}
}
--- 1485,1491 ----
for (use_link = df->insns[uid].uses; use_link; use_link = use_link->next)
{
struct ref *use = use_link->ref;
! ebitmap_set_bit (ru, DF_REF_ID (use));
}
}
}
*************** df_bb_du_chain_create (df, bb, ru)
*** 1494,1512 ****
static void
df_du_chain_create (df, blocks)
struct df *df;
! bitmap blocks;
{
! bitmap ru;
basic_block bb;
! ru = BITMAP_XMALLOC ();
! FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_du_chain_create (df, bb, ru);
});
! BITMAP_XFREE (ru);
}
--- 1496,1514 ----
static void
df_du_chain_create (df, blocks)
struct df *df;
! ebitmap blocks;
{
! ebitmap ru;
basic_block bb;
! ru = EBITMAP_XMALLOC ();
! FOR_EACH_BB_IN_EBITMAP (blocks, 0, bb,
{
df_bb_du_chain_create (df, bb, ru);
});
! EBITMAP_XFREE (ru);
}
*************** df_bb_ud_chain_create (df, bb)
*** 1563,1569 ****
{
struct ref *def = def_link->ref;
! if (bitmap_bit_p (bb_info->rd_in, DF_REF_ID (def)))
{
DF_REF_CHAIN (use)
= df_link_create (def, DF_REF_CHAIN (use));
--- 1565,1571 ----
{
struct ref *def = def_link->ref;
! if (ebitmap_bit_p (bb_info->rd_in, DF_REF_ID (def)))
{
DF_REF_CHAIN (use)
= df_link_create (def, DF_REF_CHAIN (use));
*************** df_bb_ud_chain_create (df, bb)
*** 1590,1863 ****
static void
df_ud_chain_create (df, blocks)
struct df *df;
! bitmap blocks;
{
basic_block bb;
! FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_ud_chain_create (df, bb);
});
}
- /* Use reverse completion order, and the worklist, to figure out what block
- to look at next. */
-
- static int
- df_visit_next_rc (df, blocks)
- struct df *df ATTRIBUTE_UNUSED;
- sbitmap blocks;
- {
- int i=0;
- for (i = 0; i < n_basic_blocks; i++)
- if (TEST_BIT (blocks, df->rc_order[i]))
- return df->rc_order[i];
- return sbitmap_first_set_bit (blocks);
- }
-
- /* Use reverse topsort order, and the worklist, to figure out what block
- to look at next. */
- static int
- df_visit_next_rts (df, blocks)
- struct df *df ATTRIBUTE_UNUSED;
- sbitmap blocks;
- {
- int i=0;
- for (i = 0; i < n_basic_blocks; i++)
- if (TEST_BIT (blocks, df->rts_order[i]))
- return df->rts_order[i];
- return sbitmap_first_set_bit (blocks);
- }
-
-
- /* Calculate reaching defs for each basic block in BLOCKS, i.e., the
- defs that are live at the start of a basic block. */
static void
! df_rd_global_compute (df, blocks)
! struct df *df ATTRIBUTE_UNUSED;
! bitmap blocks;
! {
! int i;
! basic_block bb;
! sbitmap worklist;
!
! worklist = sbitmap_alloc (n_basic_blocks);
! sbitmap_zero (worklist);
!
! /* Copy the blocklist to the worklist */
! EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
! {
! SET_BIT (worklist, i);
! });
!
! /* We assume that only the basic blocks in WORKLIST have been
! modified. */
! FOR_EACH_BB_IN_SBITMAP (worklist, 0, bb,
! {
! struct bb_info *bb_info = DF_BB_INFO (df, bb);
!
! bitmap_copy (bb_info->rd_out, bb_info->rd_gen);
! });
!
! while ((i = df_visit_next_rc (df, worklist)) >= 0)
! {
! struct bb_info *bb_info;
! edge e;
! int changed;
!
! /* Remove this block from the worklist. */
! RESET_BIT (worklist, i);
!
!
! bb = BASIC_BLOCK (i);
! bb_info = DF_BB_INFO (df, bb);
!
! /* Calculate union of predecessor outs. */
! bitmap_zero (bb_info->rd_in);
! for (e = bb->pred; e != 0; e = e->pred_next)
{
! struct bb_info *pred_refs = DF_BB_INFO (df, e->src);
!
! if (e->src == ENTRY_BLOCK_PTR)
! continue;
!
! bitmap_a_or_b (bb_info->rd_in, bb_info->rd_in,
! pred_refs->rd_out);
}
-
- /* RD_OUT is the set of defs that are live at the end of the
- BB. These are the defs that are either generated by defs
- (RD_GEN) within the BB or are live at the start (RD_IN)
- and are not killed by other defs (RD_KILL). */
- changed = bitmap_union_of_diff (bb_info->rd_out, bb_info->rd_gen,
- bb_info->rd_in, bb_info->rd_kill);
-
- if (changed)
- {
- /* Add each of this block's successors to the worklist. */
- for (e = bb->succ; e != 0; e = e->succ_next)
- {
- if (e->dest == EXIT_BLOCK_PTR)
- continue;
-
- SET_BIT (worklist, e->dest->index);
- }
- }
- }
- sbitmap_free (worklist);
- }
-
-
- /* Calculate reaching uses for each basic block within BLOCKS, i.e.,
- the uses that are live at the start of a basic block. */
static void
! df_ru_global_compute (df, blocks)
! struct df *df ATTRIBUTE_UNUSED;
! bitmap blocks;
! {
! int i;
! basic_block bb;
! sbitmap worklist;
!
! worklist = sbitmap_alloc (n_basic_blocks);
! sbitmap_zero (worklist);
!
! EXECUTE_IF_SET_IN_BITMAP (blocks, 0, i,
{
! SET_BIT (worklist, i);
! });
!
! /* We assume that only the basic blocks in WORKLIST have been
! modified. */
! FOR_EACH_BB_IN_SBITMAP (worklist, 0, bb,
! {
! struct bb_info *bb_info = DF_BB_INFO (df, bb);
!
! bitmap_copy (bb_info->ru_in, bb_info->ru_gen);
! });
!
!
! while ((i = df_visit_next_rts (df, worklist)) >= 0)
! {
! struct bb_info *bb_info;
! edge e;
! int changed;
!
! /* Remove this block from the worklist. */
! RESET_BIT (worklist, i);
!
! bb = BASIC_BLOCK (i);
! bb_info = DF_BB_INFO (df, bb);
!
! /* Calculate union of successor ins. */
! bitmap_zero (bb_info->ru_out);
! for (e = bb->succ; e != 0; e = e->succ_next)
! {
! struct bb_info *succ_refs = DF_BB_INFO (df, e->dest);
!
! if (e->dest == EXIT_BLOCK_PTR)
! continue;
!
! bitmap_a_or_b (bb_info->ru_out, bb_info->ru_out,
! succ_refs->ru_in);
! }
!
! /* RU_IN is the set of uses that are live at the start of the
! BB. These are the uses that are either generated within the
! BB (RU_GEN) or are live at the end (RU_OUT) and are not uses
! killed by defs within the BB (RU_KILL). */
! changed = bitmap_union_of_diff (bb_info->ru_in, bb_info->ru_gen,
! bb_info->ru_out, bb_info->ru_kill);
!
! if (changed)
! {
! /* Add each of this block's predecessors to the worklist. */
! for (e = bb->pred; e != 0; e = e->pred_next)
! {
! if (e->src == ENTRY_BLOCK_PTR)
! continue;
!
! SET_BIT (worklist, e->src->index);
! }
}
- }
-
- sbitmap_free (worklist);
- }
-
- /* Calculate live registers for each basic block within BLOCKS. */
static void
! df_lr_global_compute (df, blocks)
! struct df *df ATTRIBUTE_UNUSED;
! bitmap blocks;
! {
! int i;
! basic_block bb;
! bitmap worklist;
!
! worklist = BITMAP_XMALLOC ();
! bitmap_copy (worklist, blocks);
!
! /* We assume that only the basic blocks in WORKLIST have been
! modified. */
! FOR_EACH_BB_IN_BITMAP (worklist, 0, bb,
{
! struct bb_info *bb_info = DF_BB_INFO (df, bb);
!
! bitmap_copy (bb_info->lr_in, bb_info->lr_use);
! });
!
! while ((i = bitmap_last_set_bit (worklist)) >= 0)
! {
! struct bb_info *bb_info = DF_BB_INFO (df, bb);
! edge e;
! int changed;
!
! /* Remove this block from the worklist. */
! bitmap_clear_bit (worklist, i);
!
! bb = BASIC_BLOCK (i);
! bb_info = DF_BB_INFO (df, bb);
!
! /* Calculate union of successor ins. */
! bitmap_zero (bb_info->lr_out);
! for (e = bb->succ; e != 0; e = e->succ_next)
! {
! struct bb_info *succ_refs = DF_BB_INFO (df, e->dest);
!
! if (e->dest == EXIT_BLOCK_PTR)
! continue;
!
! bitmap_a_or_b (bb_info->lr_out, bb_info->lr_out,
! succ_refs->lr_in);
}
- /* LR_IN is the set of uses that are live at the start of the
- BB. These are the uses that are either generated by uses
- (LR_USE) within the BB or are live at the end (LR_OUT)
- and are not killed by other uses (LR_DEF). */
- changed = bitmap_union_of_diff (bb_info->lr_in, bb_info->lr_use,
- bb_info->lr_out, bb_info->lr_def);
- if (changed)
- {
- /* Add each of this block's predecessors to the worklist. */
- for (e = bb->pred; e != 0; e = e->pred_next)
- {
- if (e->src == ENTRY_BLOCK_PTR)
- continue;
-
- bitmap_set_bit (worklist, e->src->index);
- }
- }
- }
- BITMAP_XFREE (worklist);
- }
-
-
/* Compute local reaching def info for basic block BB. */
static void
df_bb_rd_local_compute (df, bb)
--- 1592,1639 ----
static void
df_ud_chain_create (df, blocks)
struct df *df;
! ebitmap blocks;
{
basic_block bb;
! FOR_EACH_BB_IN_EBITMAP (blocks, 0, bb,
{
df_bb_ud_chain_create (df, bb);
});
}
static void
! df_rd_transfer_function (bb, changed, in, out, gen, kill, data)
! int bb ATTRIBUTE_UNUSED;
! int *changed;
! ebitmap in, out, gen, kill;
! void *data ATTRIBUTE_UNUSED;
{
! *changed = ebitmap_union_of_diff (out, gen, in, kill);
}
static void
! df_ru_transfer_function (bb, changed, in, out, gen, kill, data)
! int bb ATTRIBUTE_UNUSED;
! int *changed;
! ebitmap in, out, gen, kill;
! void *data ATTRIBUTE_UNUSED;
{
! *changed = ebitmap_union_of_diff (in, gen, out, kill);
}
static void
! df_lr_transfer_function (bb, changed, in, out, use, def, data)
! int bb ATTRIBUTE_UNUSED;
! int *changed;
! ebitmap in, out, use, def;
! void *data ATTRIBUTE_UNUSED;
{
! *changed = ebitmap_union_of_diff (in, use, out, def);
}
/* Compute local reaching def info for basic block BB. */
static void
df_bb_rd_local_compute (df, bb)
*************** df_bb_rd_local_compute (df, bb)
*** 1891,1906 ****
is greedy since many of these defs will not actually
be killed by this BB but it keeps things a lot
simpler. */
! bitmap_set_bit (bb_info->rd_kill, DF_REF_ID (def2));
/* Zap from the set of gens for this BB. */
! bitmap_clear_bit (bb_info->rd_gen, DF_REF_ID (def2));
}
! bitmap_set_bit (bb_info->rd_gen, DF_REF_ID (def));
}
}
!
bb_info->rd_valid = 1;
}
--- 1667,1682 ----
is greedy since many of these defs will not actually
be killed by this BB but it keeps things a lot
simpler. */
! ebitmap_set_bit (bb_info->rd_kill, DF_REF_ID (def2));
/* Zap from the set of gens for this BB. */
! ebitmap_clear_bit (bb_info->rd_gen, DF_REF_ID (def2));
}
! ebitmap_set_bit (bb_info->rd_gen, DF_REF_ID (def));
}
}
! ebitmap_compress (bb_info->rd_gen);
bb_info->rd_valid = 1;
}
*************** df_bb_rd_local_compute (df, bb)
*** 1909,1919 ****
static void
df_rd_local_compute (df, blocks)
struct df *df;
! bitmap blocks;
{
basic_block bb;
! FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_rd_local_compute (df, bb);
});
--- 1685,1695 ----
static void
df_rd_local_compute (df, blocks)
struct df *df;
! ebitmap blocks;
{
basic_block bb;
! FOR_EACH_BB_IN_EBITMAP (blocks, 0, bb,
{
df_bb_rd_local_compute (df, bb);
});
*************** df_bb_ru_local_compute (df, bb)
*** 1958,1967 ****
is greedy since many of these uses will not actually
be killed by this BB but it keeps things a lot
simpler. */
! bitmap_set_bit (bb_info->ru_kill, DF_REF_ID (use));
/* Zap from the set of gens for this BB. */
! bitmap_clear_bit (bb_info->ru_gen, DF_REF_ID (use));
}
}
--- 1734,1743 ----
is greedy since many of these uses will not actually
be killed by this BB but it keeps things a lot
simpler. */
! ebitmap_set_bit (bb_info->ru_kill, DF_REF_ID (use));
/* Zap from the set of gens for this BB. */
! ebitmap_clear_bit (bb_info->ru_gen, DF_REF_ID (use));
}
}
*************** df_bb_ru_local_compute (df, bb)
*** 1969,1977 ****
{
struct ref *use = use_link->ref;
/* Add use to set of gens in this BB. */
! bitmap_set_bit (bb_info->ru_gen, DF_REF_ID (use));
}
}
bb_info->ru_valid = 1;
}
--- 1745,1754 ----
{
struct ref *use = use_link->ref;
/* Add use to set of gens in this BB. */
! ebitmap_set_bit (bb_info->ru_gen, DF_REF_ID (use));
}
}
+ ebitmap_compress (bb_info->ru_gen);
bb_info->ru_valid = 1;
}
*************** df_bb_ru_local_compute (df, bb)
*** 1981,1991 ****
static void
df_ru_local_compute (df, blocks)
struct df *df;
! bitmap blocks;
{
basic_block bb;
! FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_ru_local_compute (df, bb);
});
--- 1758,1768 ----
static void
df_ru_local_compute (df, blocks)
struct df *df;
! ebitmap blocks;
{
basic_block bb;
! FOR_EACH_BB_IN_EBITMAP (blocks, 0, bb,
{
df_bb_ru_local_compute (df, bb);
});
*************** df_bb_lr_local_compute (df, bb)
*** 2016,2033 ****
unsigned int dregno = DF_REF_REGNO (def);
/* Add def to set of defs in this BB. */
! bitmap_set_bit (bb_info->lr_def, dregno);
! bitmap_clear_bit (bb_info->lr_use, dregno);
}
for (link = df->insns[uid].uses; link; link = link->next)
{
struct ref *use = link->ref;
/* Add use to set of uses in this BB. */
! bitmap_set_bit (bb_info->lr_use, DF_REF_REGNO (use));
}
}
bb_info->lr_valid = 1;
}
--- 1793,1811 ----
unsigned int dregno = DF_REF_REGNO (def);
/* Add def to set of defs in this BB. */
! ebitmap_set_bit (bb_info->lr_def, dregno);
! ebitmap_clear_bit (bb_info->lr_use, dregno);
}
for (link = df->insns[uid].uses; link; link = link->next)
{
struct ref *use = link->ref;
/* Add use to set of uses in this BB. */
! ebitmap_set_bit (bb_info->lr_use, DF_REF_REGNO (use));
}
}
+ ebitmap_compress (bb_info->lr_def);
bb_info->lr_valid = 1;
}
*************** df_bb_lr_local_compute (df, bb)
*** 2036,2046 ****
static void
df_lr_local_compute (df, blocks)
struct df *df;
! bitmap blocks;
{
basic_block bb;
! FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_lr_local_compute (df, bb);
});
--- 1814,1824 ----
static void
df_lr_local_compute (df, blocks)
struct df *df;
! ebitmap blocks;
{
basic_block bb;
! FOR_EACH_BB_IN_EBITMAP (blocks, 0, bb,
{
df_bb_lr_local_compute (df, bb);
});
*************** static void
*** 2053,2065 ****
df_bb_reg_info_compute (df, bb, live)
struct df *df;
basic_block bb;
! bitmap live;
{
struct reg_info *reg_info = df->regs;
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
! bitmap_copy (live, bb_info->lr_out);
for (insn = bb->end; insn && insn != PREV_INSN (bb->head);
insn = PREV_INSN (insn))
--- 1831,1843 ----
df_bb_reg_info_compute (df, bb, live)
struct df *df;
basic_block bb;
! ebitmap live;
{
struct reg_info *reg_info = df->regs;
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
! ebitmap_copy (live, bb_info->lr_out);
for (insn = bb->end; insn && insn != PREV_INSN (bb->head);
insn = PREV_INSN (insn))
*************** df_bb_reg_info_compute (df, bb, live)
*** 2077,2083 ****
unsigned int dregno = DF_REF_REGNO (def);
/* Kill this register. */
! bitmap_clear_bit (live, dregno);
reg_info[dregno].n_defs++;
}
--- 1855,1861 ----
unsigned int dregno = DF_REF_REGNO (def);
/* Kill this register. */
! ebitmap_clear_bit (live, dregno);
reg_info[dregno].n_defs++;
}
*************** df_bb_reg_info_compute (df, bb, live)
*** 2087,2098 ****
unsigned int uregno = DF_REF_REGNO (use);
/* This register is now live. */
! bitmap_set_bit (live, uregno);
reg_info[uregno].n_uses++;
}
/* Increment lifetimes of all live registers. */
! EXECUTE_IF_SET_IN_BITMAP (live, 0, regno,
{
reg_info[regno].lifetime++;
});
--- 1865,1876 ----
unsigned int uregno = DF_REF_REGNO (use);
/* This register is now live. */
! ebitmap_set_bit (live, uregno);
reg_info[uregno].n_uses++;
}
/* Increment lifetimes of all live registers. */
! EXECUTE_IF_SET_IN_EBITMAP (live, 0, regno,
{
reg_info[regno].lifetime++;
});
*************** df_bb_reg_info_compute (df, bb, live)
*** 2104,2122 ****
static void
df_reg_info_compute (df, blocks)
struct df *df;
! bitmap blocks;
{
basic_block bb;
! bitmap live;
! live = BITMAP_XMALLOC ();
! FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_reg_info_compute (df, bb, live);
});
! BITMAP_XFREE (live);
}
--- 1882,1900 ----
static void
df_reg_info_compute (df, blocks)
struct df *df;
! ebitmap blocks;
{
basic_block bb;
! ebitmap live;
! live = EBITMAP_XMALLOC ();
! FOR_EACH_BB_IN_EBITMAP (blocks, 0, bb,
{
df_bb_reg_info_compute (df, bb, live);
});
! EBITMAP_XFREE (live);
}
*************** df_bb_luids_set (df, bb)
*** 2148,2159 ****
static int
df_luids_set (df, blocks)
struct df *df;
! bitmap blocks;
{
basic_block bb;
int total = 0;
! FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
total += df_bb_luids_set (df, bb);
});
--- 1926,1937 ----
static int
df_luids_set (df, blocks)
struct df *df;
! ebitmap blocks;
{
basic_block bb;
int total = 0;
! FOR_EACH_BB_IN_EBITMAP (blocks, 0, bb,
{
total += df_bb_luids_set (df, bb);
});
*************** df_luids_set (df, blocks)
*** 2166,2178 ****
static void
df_analyse_1 (df, blocks, flags, update)
struct df *df;
! bitmap blocks;
int flags;
int update;
{
int aflags;
int dflags;
!
dflags = 0;
aflags = flags;
if (flags & DF_UD_CHAIN)
--- 1944,1956 ----
static void
df_analyse_1 (df, blocks, flags, update)
struct df *df;
! ebitmap blocks;
int flags;
int update;
{
int aflags;
int dflags;
! int i;
dflags = 0;
aflags = flags;
if (flags & DF_UD_CHAIN)
*************** df_analyse_1 (df, blocks, flags, update)
*** 2239,2255 ****
df->dfs_order = xmalloc (sizeof(int) * n_basic_blocks);
df->rc_order = xmalloc (sizeof(int) * n_basic_blocks);
df->rts_order = xmalloc (sizeof(int) * n_basic_blocks);
flow_depth_first_order_compute (df->dfs_order, df->rc_order);
flow_reverse_top_sort_order_compute (df->rts_order);
if (aflags & DF_RD)
{
/* Compute the sets of gens and kills for the defs of each bb. */
df_rd_local_compute (df, df->flags & DF_RD ? blocks : df->all_blocks);
!
! /* Compute the global reaching definitions. */
! df_rd_global_compute (df, df->all_blocks);
}
if (aflags & DF_UD_CHAIN)
{
--- 2017,2056 ----
df->dfs_order = xmalloc (sizeof(int) * n_basic_blocks);
df->rc_order = xmalloc (sizeof(int) * n_basic_blocks);
df->rts_order = xmalloc (sizeof(int) * n_basic_blocks);
+ df->inverse_dfs_map = xmalloc (sizeof(int) * n_basic_blocks);
+ df->inverse_rc_map = xmalloc (sizeof(int) * n_basic_blocks);
+ df->inverse_rts_map = xmalloc (sizeof(int) * n_basic_blocks);
flow_depth_first_order_compute (df->dfs_order, df->rc_order);
flow_reverse_top_sort_order_compute (df->rts_order);
+ for (i = 0; i < n_basic_blocks; i ++)
+ {
+ df->inverse_dfs_map[df->dfs_order[i]] = i;
+ df->inverse_rc_map[df->rc_order[i]] = i;
+ df->inverse_rts_map[df->rts_order[i]] = i;
+ }
if (aflags & DF_RD)
{
/* Compute the sets of gens and kills for the defs of each bb. */
df_rd_local_compute (df, df->flags & DF_RD ? blocks : df->all_blocks);
! {
! int i;
! ebitmap *in = alloca (sizeof (bitmap) * n_basic_blocks);
! ebitmap *out = alloca (sizeof (bitmap) * n_basic_blocks);
! ebitmap *gen = alloca (sizeof (bitmap) * n_basic_blocks);
! ebitmap *kill = alloca (sizeof (bitmap) * n_basic_blocks);
! for (i = 0; i < n_basic_blocks; i ++)
! {
! in[i] = DF_BB_INFO (df, BASIC_BLOCK (i))->rd_in;
! out[i] = DF_BB_INFO (df, BASIC_BLOCK (i))->rd_out;
! gen[i] = DF_BB_INFO (df, BASIC_BLOCK (i))->rd_gen;
! kill[i] = DF_BB_INFO (df, BASIC_BLOCK (i))->rd_kill;
! }
! iterative_dataflow_ebitmap (in, out, gen, kill, df->all_blocks,
! FORWARD, UNION, df_rd_transfer_function,
! df->inverse_rc_map, NULL);
}
+ }
if (aflags & DF_UD_CHAIN)
{
*************** df_analyse_1 (df, blocks, flags, update)
*** 2265,2273 ****
/* Compute the sets of gens and kills for the upwards exposed
uses in each bb. */
df_ru_local_compute (df, df->flags & DF_RU ? blocks : df->all_blocks);
!
! /* Compute the global reaching uses. */
! df_ru_global_compute (df, df->all_blocks);
}
if (aflags & DF_DU_CHAIN)
--- 2066,2088 ----
/* Compute the sets of gens and kills for the upwards exposed
uses in each bb. */
df_ru_local_compute (df, df->flags & DF_RU ? blocks : df->all_blocks);
! {
! int i;
! ebitmap *in = alloca (sizeof (bitmap) * n_basic_blocks);
! ebitmap *out = alloca (sizeof (bitmap) * n_basic_blocks);
! ebitmap *gen = alloca (sizeof (bitmap) * n_basic_blocks);
! ebitmap *kill = alloca (sizeof (bitmap) * n_basic_blocks);
! for (i = 0; i < n_basic_blocks; i ++)
! {
! in[i] = DF_BB_INFO (df, BASIC_BLOCK (i))->ru_in;
! out[i] = DF_BB_INFO (df, BASIC_BLOCK (i))->ru_out;
! gen[i] = DF_BB_INFO (df, BASIC_BLOCK (i))->ru_gen;
! kill[i] = DF_BB_INFO (df, BASIC_BLOCK (i))->ru_kill;
! }
! iterative_dataflow_ebitmap (in, out, gen, kill, df->all_blocks,
! BACKWARD, UNION, df_ru_transfer_function,
! df->inverse_rts_map, NULL);
! }
}
if (aflags & DF_DU_CHAIN)
*************** df_analyse_1 (df, blocks, flags, update)
*** 2287,2296 ****
{
/* Compute the sets of defs and uses of live variables. */
df_lr_local_compute (df, df->flags & DF_LR ? blocks : df->all_blocks);
!
! /* Compute the global live variables. */
! df_lr_global_compute (df, df->all_blocks);
}
if (aflags & DF_REG_INFO)
{
--- 2102,2125 ----
{
/* Compute the sets of defs and uses of live variables. */
df_lr_local_compute (df, df->flags & DF_LR ? blocks : df->all_blocks);
! {
! int i;
! ebitmap *in = alloca (sizeof (bitmap) * n_basic_blocks);
! ebitmap *out = alloca (sizeof (bitmap) * n_basic_blocks);
! ebitmap *use = alloca (sizeof (bitmap) * n_basic_blocks);
! ebitmap *def = alloca (sizeof (bitmap) * n_basic_blocks);
! for (i = 0; i < n_basic_blocks; i ++)
! {
! in[i] = DF_BB_INFO (df, BASIC_BLOCK (i))->lr_in;
! out[i] = DF_BB_INFO (df, BASIC_BLOCK (i))->lr_out;
! use[i] = DF_BB_INFO (df, BASIC_BLOCK (i))->lr_use;
! def[i] = DF_BB_INFO (df, BASIC_BLOCK (i))->lr_def;
! }
! iterative_dataflow_ebitmap (in, out, use, def, df->all_blocks,
! BACKWARD, UNION, df_lr_transfer_function,
! df->inverse_rts_map, NULL);
}
+ }
if (aflags & DF_REG_INFO)
{
*************** df_analyse_1 (df, blocks, flags, update)
*** 2299,2304 ****
--- 2128,2136 ----
free (df->dfs_order);
free (df->rc_order);
free (df->rts_order);
+ free (df->inverse_rc_map);
+ free (df->inverse_dfs_map);
+ free (df->inverse_rts_map);
}
*************** df_bb_refs_update (df, bb)
*** 2382,2388 ****
uid = INSN_UID (insn);
! if (bitmap_bit_p (df->insns_modified, uid))
{
/* Delete any allocated refs of this insn. MPH, FIXME. */
df_insn_refs_unlink (df, bb, insn);
--- 2214,2220 ----
uid = INSN_UID (insn);
! if (ebitmap_bit_p (df->insns_modified, uid))
{
/* Delete any allocated refs of this insn. MPH, FIXME. */
df_insn_refs_unlink (df, bb, insn);
*************** df_bb_refs_update (df, bb)
*** 2391,2397 ****
df_insn_refs_record (df, bb, insn);
! bitmap_clear_bit (df->insns_modified, uid);
count++;
}
if (insn == bb->end)
--- 2223,2229 ----
df_insn_refs_record (df, bb, insn);
! ebitmap_clear_bit (df->insns_modified, uid);
count++;
}
if (insn == bb->end)
*************** df_refs_update (df)
*** 2414,2420 ****
df_refs_queue (df);
! FOR_EACH_BB_IN_BITMAP (df->bbs_modified, 0, bb,
{
count += df_bb_refs_update (df, bb);
});
--- 2246,2252 ----
df_refs_queue (df);
! FOR_EACH_BB_IN_EBITMAP (df->bbs_modified, 0, bb,
{
count += df_bb_refs_update (df, bb);
});
*************** df_refs_update (df)
*** 2429,2442 ****
static int
df_modified_p (df, blocks)
struct df *df;
! bitmap blocks;
{
unsigned int j;
int update = 0;
for (j = 0; j < df->n_bbs; j++)
! if (bitmap_bit_p (df->bbs_modified, j)
! && (! blocks || (blocks == (bitmap) -1) || bitmap_bit_p (blocks, j)))
{
update = 1;
break;
--- 2261,2274 ----
static int
df_modified_p (df, blocks)
struct df *df;
! ebitmap blocks;
{
unsigned int j;
int update = 0;
for (j = 0; j < df->n_bbs; j++)
! if (ebitmap_bit_p (df->bbs_modified, j)
! && (! blocks || (blocks == (ebitmap) -1) || ebitmap_bit_p (blocks, j)))
{
update = 1;
break;
*************** df_modified_p (df, blocks)
*** 2452,2458 ****
int
df_analyse (df, blocks, flags)
struct df *df;
! bitmap blocks;
int flags;
{
int update;
--- 2284,2290 ----
int
df_analyse (df, blocks, flags)
struct df *df;
! ebitmap blocks;
int flags;
{
int update;
*************** df_analyse (df, blocks, flags)
*** 2479,2492 ****
}
else
{
! if (blocks == (bitmap) -1)
blocks = df->bbs_modified;
if (! df->n_bbs)
abort ();
df_analyse_1 (df, blocks, flags, 1);
! bitmap_zero (df->bbs_modified);
}
}
return update;
--- 2311,2324 ----
}
else
{
! if (blocks == (ebitmap) -1)
blocks = df->bbs_modified;
if (! df->n_bbs)
abort ();
df_analyse_1 (df, blocks, flags, 1);
! ebitmap_zero (df->bbs_modified);
}
}
return update;
*************** df_bb_refs_unlink (df, bb)
*** 2556,2568 ****
static void
df_refs_unlink (df, blocks)
struct df *df;
! bitmap blocks;
{
basic_block bb;
if (blocks)
{
! FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_refs_unlink (df, bb);
});
--- 2388,2400 ----
static void
df_refs_unlink (df, blocks)
struct df *df;
! ebitmap blocks;
{
basic_block bb;
if (blocks)
{
! FOR_EACH_BB_IN_EBITMAP (blocks, 0, bb,
{
df_bb_refs_unlink (df, bb);
});
*************** df_insn_modify (df, bb, insn)
*** 2624,2631 ****
if (uid >= df->insn_size)
df_insn_table_realloc (df, 0);
! bitmap_set_bit (df->bbs_modified, bb->index);
! bitmap_set_bit (df->insns_modified, uid);
#if 0
/* For incremental updating on the fly, perhaps we could make a copy
--- 2456,2463 ----
if (uid >= df->insn_size)
df_insn_table_realloc (df, 0);
! ebitmap_set_bit (df->bbs_modified, bb->index);
! ebitmap_set_bit (df->insns_modified, uid);
#if 0
/* For incremental updating on the fly, perhaps we could make a copy
*************** df_rtx_reg_replace (px, data)
*** 2749,2755 ****
void
df_refs_reg_replace (df, blocks, chain, oldreg, newreg)
struct df *df;
! bitmap blocks;
struct df_link *chain;
rtx oldreg;
rtx newreg;
--- 2581,2587 ----
void
df_refs_reg_replace (df, blocks, chain, oldreg, newreg)
struct df *df;
! ebitmap blocks;
struct df_link *chain;
rtx oldreg;
rtx newreg;
*************** df_refs_reg_replace (df, blocks, chain,
*** 2772,2778 ****
if (! INSN_P (insn))
continue;
! if (bitmap_bit_p (blocks, DF_REF_BBNO (ref)))
{
df_ref_reg_replace (df, ref, oldreg, newreg);
--- 2604,2610 ----
if (! INSN_P (insn))
continue;
! if (ebitmap_bit_p (blocks, DF_REF_BBNO (ref)))
{
df_ref_reg_replace (df, ref, oldreg, newreg);
*************** df_refs_reg_replace (df, blocks, chain,
*** 2796,2808 ****
/* Replace all occurrences of register OLDREG with register NEWREG in
! blocks defined by bitmap BLOCKS. This also replaces occurrences of
OLDREG in the REG_NOTES but only for insns containing OLDREG. This
routine expects the reg-use and reg-def chains to be valid. */
int
df_reg_replace (df, blocks, oldreg, newreg)
struct df *df;
! bitmap blocks;
rtx oldreg;
rtx newreg;
{
--- 2628,2640 ----
/* Replace all occurrences of register OLDREG with register NEWREG in
! blocks defined by ebitmap blocks. This also replaces occurrences of
OLDREG in the REG_NOTES but only for insns containing OLDREG. This
routine expects the reg-use and reg-def chains to be valid. */
int
df_reg_replace (df, blocks, oldreg, newreg)
struct df *df;
! ebitmap blocks;
rtx oldreg;
rtx newreg;
{
*************** static int
*** 3104,3110 ****
df_def_dominates_uses_p (df, def, blocks)
struct df *df ATTRIBUTE_UNUSED;
struct ref *def;
! bitmap blocks;
{
struct df_link *du_link;
--- 2936,2942 ----
df_def_dominates_uses_p (df, def, blocks)
struct df *df ATTRIBUTE_UNUSED;
struct ref *def;
! ebitmap blocks;
{
struct df_link *du_link;
*************** df_def_dominates_uses_p (df, def, blocks
*** 3117,3123 ****
/* Only worry about the uses within BLOCKS. For example,
consider a register defined within a loop that is live at the
loop exits. */
! if (bitmap_bit_p (blocks, DF_REF_BBNO (use)))
{
/* Follow use-def chain to check all the defs for this use. */
for (ud_link = DF_REF_CHAIN (use); ud_link; ud_link = ud_link->next)
--- 2949,2955 ----
/* Only worry about the uses within BLOCKS. For example,
consider a register defined within a loop that is live at the
loop exits. */
! if (ebitmap_bit_p (blocks, DF_REF_BBNO (use)))
{
/* Follow use-def chain to check all the defs for this use. */
for (ud_link = DF_REF_CHAIN (use); ud_link; ud_link = ud_link->next)
*************** df_insn_dominates_uses_p (df, bb, insn,
*** 3136,3142 ****
struct df *df;
basic_block bb ATTRIBUTE_UNUSED;
rtx insn;
! bitmap blocks;
{
unsigned int uid;
struct df_link *link;
--- 2968,2974 ----
struct df *df;
basic_block bb ATTRIBUTE_UNUSED;
rtx insn;
! ebitmap blocks;
{
unsigned int uid;
struct df_link *link;
*************** df_insn_dominates_uses_p (df, bb, insn,
*** 3148,3154 ****
struct ref *def = link->ref;
/* Only consider the defs within BLOCKS. */
! if (bitmap_bit_p (blocks, DF_REF_BBNO (def))
&& ! df_def_dominates_uses_p (df, def, blocks))
return 0;
}
--- 2980,2986 ----
struct ref *def = link->ref;
/* Only consider the defs within BLOCKS. */
! if (ebitmap_bit_p (blocks, DF_REF_BBNO (def))
&& ! df_def_dominates_uses_p (df, def, blocks))
return 0;
}
*************** df_bb_reg_live_start_p (df, bb, reg)
*** 3210,3216 ****
abort ();
#endif
! return bitmap_bit_p (bb_info->lr_in, REGNO (reg));
}
--- 3042,3048 ----
abort ();
#endif
! return ebitmap_bit_p (bb_info->lr_in, REGNO (reg));
}
*************** df_bb_reg_live_end_p (df, bb, reg)
*** 3228,3234 ****
abort ();
#endif
! return bitmap_bit_p (bb_info->lr_out, REGNO (reg));
}
--- 3060,3066 ----
abort ();
#endif
! return ebitmap_bit_p (bb_info->lr_out, REGNO (reg));
}
*************** df_dump (df, flags, file)
*** 3470,3482 ****
continue;
fprintf (file, "bb %d in \t", i);
! dump_bitmap (file, bb_info->rd_in);
fprintf (file, "bb %d gen \t", i);
! dump_bitmap (file, bb_info->rd_gen);
fprintf (file, "bb %d kill\t", i);
! dump_bitmap (file, bb_info->rd_kill);
fprintf (file, "bb %d out \t", i);
! dump_bitmap (file, bb_info->rd_out);
}
}
--- 3302,3314 ----
continue;
fprintf (file, "bb %d in \t", i);
! dump_ebitmap (file, bb_info->rd_in);
fprintf (file, "bb %d gen \t", i);
! dump_ebitmap (file, bb_info->rd_gen);
fprintf (file, "bb %d kill\t", i);
! dump_ebitmap (file, bb_info->rd_kill);
fprintf (file, "bb %d out \t", i);
! dump_ebitmap (file, bb_info->rd_out);
}
}
*************** df_dump (df, flags, file)
*** 3510,3522 ****
continue;
fprintf (file, "bb %d in \t", i);
! dump_bitmap (file, bb_info->ru_in);
fprintf (file, "bb %d gen \t", i);
! dump_bitmap (file, bb_info->ru_gen);
fprintf (file, "bb %d kill\t", i);
! dump_bitmap (file, bb_info->ru_kill);
fprintf (file, "bb %d out \t", i);
! dump_bitmap (file, bb_info->ru_out);
}
}
--- 3342,3354 ----
continue;
fprintf (file, "bb %d in \t", i);
! dump_ebitmap (file, bb_info->ru_in);
fprintf (file, "bb %d gen \t", i);
! dump_ebitmap (file, bb_info->ru_gen);
fprintf (file, "bb %d kill\t", i);
! dump_ebitmap (file, bb_info->ru_kill);
fprintf (file, "bb %d out \t", i);
! dump_ebitmap (file, bb_info->ru_out);
}
}
*************** df_dump (df, flags, file)
*** 3550,3562 ****
continue;
fprintf (file, "bb %d in \t", i);
! dump_bitmap (file, bb_info->lr_in);
fprintf (file, "bb %d use \t", i);
! dump_bitmap (file, bb_info->lr_use);
fprintf (file, "bb %d def \t", i);
! dump_bitmap (file, bb_info->lr_def);
fprintf (file, "bb %d out \t", i);
! dump_bitmap (file, bb_info->lr_out);
}
}
--- 3382,3394 ----
continue;
fprintf (file, "bb %d in \t", i);
! dump_ebitmap (file, bb_info->lr_in);
fprintf (file, "bb %d use \t", i);
! dump_ebitmap (file, bb_info->lr_use);
fprintf (file, "bb %d def \t", i);
! dump_ebitmap (file, bb_info->lr_def);
fprintf (file, "bb %d out \t", i);
! dump_ebitmap (file, bb_info->lr_out);
}
}
*************** debug_df_chain (link)
*** 3761,3764 ****
--- 3593,3864 ----
{
df_chain_dump (link, stderr);
fputc ('\n', stderr);
+ }
+
+ /* gen = GEN set.
+ kill = KILL set.
+ in, out = Filled in by function.
+ blocks = Blocks to analyze.
+ dir = Dataflow direction.
+ conf_op = Confluence operation.
+ transfun = Transfer function.
+ order = Order to iterate in. (Should map block numbers -> order)
+ data = Whatever you want. It's passed to the transfer function.
+
+ This function will perform iterative bitvector dataflow, producing
+ the in and out sets. Even if you only want to perform it for a
+ small number of blocks, the vectors for in and out must be large
+ enough for *all* blocks, because changing one block might affect
+ others. However, it'll only put what you say to analyze on the
+ initial worklist.
+
+ For forward problems, you probably want to pass in a mapping of
+ block number to rc_order (like df->inverse_rc_map).
+ */
+
+ void
+ iterative_dataflow_sbitmap (in, out, gen, kill, blocks,
+ dir, conf_op, transfun, order, data)
+ sbitmap *in, *out, *gen, *kill;
+ ebitmap blocks;
+ enum df_flow_dir dir;
+ enum df_confluence_op conf_op;
+ transfer_function_sbitmap transfun;
+ int *order;
+ void *data;
+ {
+ int changed;
+ int i;
+ fibheap_t worklist;
+ sbitmap onqueue;
+ basic_block bb;
+
+ onqueue = sbitmap_alloc (n_basic_blocks);
+ sbitmap_zero (onqueue);
+ worklist = fibheap_new ();
+ EXECUTE_IF_SET_IN_EBITMAP (blocks, 0, i,
+ {
+ fibheap_insert (worklist, order[i], (void *) i);
+ SET_BIT (onqueue, i);
+ if (dir == FORWARD)
+ {
+ sbitmap_copy (out[i], gen[i]);
+ }
+ else
+ {
+ sbitmap_copy (in[i], gen[i]);
+ }
+
+ });
+ while (!fibheap_empty (worklist))
+ {
+ edge e;
+ i = (int) fibheap_extract_min (worklist);
+ changed = 0;
+ bb = BASIC_BLOCK (i);
+ RESET_BIT (onqueue, i);
+
+ if (dir == FORWARD)
+ {
+ /* Calculate <conf_op> of predecessor_outs */
+ sbitmap_zero (in[i]);
+ for (e = bb->pred; e != 0; e = e->pred_next)
+ {
+ if (e->src == ENTRY_BLOCK_PTR)
+ continue;
+ switch (conf_op)
+ {
+ case UNION:
+ sbitmap_a_or_b (in[i], in[i], out[e->src->index]);
+ break;
+ case INTERSECTION:
+ sbitmap_a_and_b (in[i], in[i], out[e->src->index]);
+ break;
+ }
+ }
+ }
+ else
+ {
+ /* Calculate <conf_op> of successor ins */
+ sbitmap_zero(out[i]);
+ for (e = bb->succ; e != 0; e = e->succ_next)
+ {
+ if (e->dest == EXIT_BLOCK_PTR)
+ continue;
+ switch (conf_op)
+ {
+ case UNION:
+ sbitmap_a_or_b (out[i], out[i], in[e->dest->index]);
+ break;
+ case INTERSECTION:
+ sbitmap_a_and_b (out[i], out[i], in[e->dest->index]);
+ break;
+ }
+ }
+ }
+ /* Common part */
+ (*transfun)(i, &changed, in[i], out[i], gen[i], kill[i], data);
+
+ if (changed)
+ {
+ if (dir == FORWARD)
+ {
+ for (e = bb->succ; e != 0; e = e->succ_next)
+ {
+ if (e->dest == EXIT_BLOCK_PTR)
+ continue;
+ if (!TEST_BIT (onqueue, e->dest->index))
+ {
+ SET_BIT (onqueue, e->dest->index);
+ fibheap_insert (worklist,
+ order[e->dest->index],
+ (void *)e->dest->index);
+ }
+ }
+ }
+ else
+ {
+ for (e = bb->pred; e != 0; e = e->pred_next)
+ {
+ if (e->src == ENTRY_BLOCK_PTR)
+ continue;
+ if (!TEST_BIT (onqueue, e->src->index))
+ {
+ SET_BIT (onqueue, e->src->index);
+ fibheap_insert (worklist,
+ order[e->src->index],
+ (void *)e->src->index);
+ }
+
+ }
+ }
+ }
+ }
+ sbitmap_free (onqueue);
+ fibheap_delete (worklist);
+
+ }
+ /* Exactly the same as iterative_dataflow_sbitmap, except it works on
+ bitmaps instead */
+ void
+ iterative_dataflow_ebitmap (in, out, gen, kill, blocks,
+ dir, conf_op, transfun, order, data)
+ ebitmap *in, *out, *gen, *kill;
+ ebitmap blocks;
+ enum df_flow_dir dir;
+ enum df_confluence_op conf_op;
+ transfer_function_ebitmap transfun;
+ int *order;
+ void *data;
+ {
+ int changed;
+ int i;
+ fibheap_t worklist;
+ sbitmap onqueue;
+ basic_block bb;
+
+ onqueue = sbitmap_alloc (n_basic_blocks);
+ sbitmap_zero (onqueue);
+ worklist = fibheap_new ();
+ EXECUTE_IF_SET_IN_EBITMAP (blocks, 0, i,
+ {
+ fibheap_insert (worklist, order[i], (void *) i);
+ SET_BIT (onqueue, i);
+ if (dir == FORWARD)
+ {
+ ebitmap_copy (out[i], gen[i]);
+ }
+ else
+ {
+ ebitmap_copy (in[i], gen[i]);
+ }
+
+ });
+ while (!fibheap_empty (worklist))
+ {
+ edge e;
+ i = (int) fibheap_extract_min (worklist);
+ changed = 0;
+ bb = BASIC_BLOCK (i);
+ RESET_BIT (onqueue, i);
+
+ if (dir == FORWARD)
+ {
+ /* Calculate <conf_op> of predecessor_outs */
+ ebitmap_zero (in[i]);
+ for (e = bb->pred; e != 0; e = e->pred_next)
+ {
+ if (e->src == ENTRY_BLOCK_PTR)
+ continue;
+ switch (conf_op)
+ {
+ case UNION:
+ ebitmap_a_or_b (in[i], in[i], out[e->src->index]);
+ break;
+ case INTERSECTION:
+ ebitmap_a_and_b (in[i], in[i], out[e->src->index]);
+ break;
+ }
+ }
+ }
+ else
+ {
+ /* Calculate <conf_op> of successor ins */
+ ebitmap_zero(out[i]);
+ for (e = bb->succ; e != 0; e = e->succ_next)
+ {
+ if (e->dest == EXIT_BLOCK_PTR)
+ continue;
+ switch (conf_op)
+ {
+ case UNION:
+ ebitmap_a_or_b (out[i], out[i], in[e->dest->index]);
+ break;
+ case INTERSECTION:
+ ebitmap_a_and_b (out[i], out[i], in[e->dest->index]);
+ break;
+ }
+ }
+ }
+ /* Common part */
+ (*transfun)(i, &changed, in[i], out[i], gen[i], kill[i], data);
+
+ if (changed)
+ {
+ if (dir == FORWARD)
+ {
+ for (e = bb->succ; e != 0; e = e->succ_next)
+ {
+ if (e->dest == EXIT_BLOCK_PTR)
+ continue;
+ if (!TEST_BIT (onqueue, e->dest->index))
+ {
+ SET_BIT (onqueue, e->dest->index);
+ fibheap_insert (worklist,
+ order[e->dest->index],
+ (void *)e->dest->index);
+ }
+ }
+ }
+ else
+ {
+ for (e = bb->pred; e != 0; e = e->pred_next)
+ {
+ if (e->src == ENTRY_BLOCK_PTR)
+ continue;
+ if (!TEST_BIT (onqueue, e->src->index))
+ {
+ SET_BIT (onqueue, e->src->index);
+ fibheap_insert (worklist,
+ order[e->src->index],
+ (void *)e->src->index);
+ }
+
+ }
+ }
+ }
+ }
+ sbitmap_free (onqueue);
+ fibheap_delete (worklist);
+
}
Index: df.h
===================================================================
RCS file: /cvs/gcc/egcs/gcc/df.h,v
retrieving revision 1.4
diff -c -3 -p -w -B -b -r1.4 df.h
*** df.h 2001/08/28 23:43:20 1.4
--- df.h 2001/08/30 13:02:46
*************** along with GCC; see the file COPYING. I
*** 20,26 ****
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA. */
!
#define DF_RD 1 /* Reaching definitions. */
#define DF_RU 2 /* Reaching uses. */
#define DF_LR 4 /* Live registers. */
--- 20,26 ----
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA. */
! #include "ebitmap.h"
#define DF_RD 1 /* Reaching definitions. */
#define DF_RU 2 /* Reaching uses. */
#define DF_LR 4 /* Live registers. */
*************** struct reg_info
*** 91,110 ****
struct bb_info
{
/* Reaching def bitmaps have def_id elements. */
! bitmap rd_kill;
! bitmap rd_gen;
! bitmap rd_in;
! bitmap rd_out;
/* Reaching use bitmaps have use_id elements. */
! bitmap ru_kill;
! bitmap ru_gen;
! bitmap ru_in;
! bitmap ru_out;
/* Live variable bitmaps have n_regs elements. */
! bitmap lr_def;
! bitmap lr_use;
! bitmap lr_in;
! bitmap lr_out;
int rd_valid;
int ru_valid;
int lr_valid;
--- 91,110 ----
struct bb_info
{
/* Reaching def bitmaps have def_id elements. */
! ebitmap rd_kill;
! ebitmap rd_gen;
! ebitmap rd_in;
! ebitmap rd_out;
/* Reaching use bitmaps have use_id elements. */
! ebitmap ru_kill;
! ebitmap ru_gen;
! ebitmap ru_in;
! ebitmap ru_out;
/* Live variable bitmaps have n_regs elements. */
! ebitmap lr_def;
! ebitmap lr_use;
! ebitmap lr_in;
! ebitmap lr_out;
int rd_valid;
int ru_valid;
int lr_valid;
*************** struct df
*** 132,146 ****
unsigned int n_regs; /* Number of regs. */
unsigned int def_id_save; /* Saved next def ID. */
unsigned int use_id_save; /* Saved next use ID. */
! bitmap insns_modified; /* Insns that (may) have changed. */
! bitmap bbs_modified; /* Blocks that (may) have changed. */
! bitmap all_blocks; /* All blocks in CFG. */
! /* The bitmap vector of dominators or NULL if not computed.
Ideally, this should be a pointer to a CFG object. */
! bitmap *dom;
! int * dfs_order;
! int * rc_order;
! int * rts_order;
};
--- 132,149 ----
unsigned int n_regs; /* Number of regs. */
unsigned int def_id_save; /* Saved next def ID. */
unsigned int use_id_save; /* Saved next use ID. */
! ebitmap insns_modified; /* Insns that (may) have changed. */
! ebitmap bbs_modified; /* Blocks that (may) have changed. */
! ebitmap all_blocks; /* All blocks in CFG. */
! /* The sbitmap vector of dominators or NULL if not computed.
Ideally, this should be a pointer to a CFG object. */
! sbitmap *dom;
! int * dfs_order; /* DFS order -> block number */
! int * rc_order; /* reverse completion order -> block number */
! int * rts_order; /* reverse top sort order -> block number */
! int * inverse_rc_map; /* block number -> reverse completion order */
! int * inverse_dfs_map; /* block number -> DFS order */
! int * inverse_rts_map; /* block number -> reverse top-sort order */
};
*************** struct df_map
*** 211,217 ****
extern struct df *df_init PARAMS ((void));
! extern int df_analyse PARAMS ((struct df *, bitmap, int));
extern void df_finish PARAMS ((struct df *));
--- 214,220 ----
extern struct df *df_init PARAMS ((void));
! extern int df_analyse PARAMS ((struct df *, ebitmap, int));
extern void df_finish PARAMS ((struct df *));
*************** extern rtx df_pattern_emit_after PARAMS
*** 235,241 ****
extern rtx df_insn_move_before PARAMS ((struct df *, basic_block, rtx,
basic_block, rtx));
! extern int df_reg_replace PARAMS ((struct df *, bitmap, rtx, rtx));
extern int df_ref_reg_replace PARAMS ((struct df *, struct ref *, rtx, rtx));
--- 238,244 ----
extern rtx df_insn_move_before PARAMS ((struct df *, basic_block, rtx,
basic_block, rtx));
! extern int df_reg_replace PARAMS ((struct df *, ebitmap, rtx, rtx));
extern int df_ref_reg_replace PARAMS ((struct df *, struct ref *, rtx, rtx));
*************** extern int df_insn_dominates_all_uses_p
*** 266,272 ****
basic_block, rtx));
extern int df_insn_dominates_uses_p PARAMS ((struct df *, basic_block,
! rtx, bitmap));
extern int df_bb_reg_live_start_p PARAMS ((struct df *, basic_block, rtx));
--- 269,275 ----
basic_block, rtx));
extern int df_insn_dominates_uses_p PARAMS ((struct df *, basic_block,
! rtx, ebitmap));
extern int df_bb_reg_live_start_p PARAMS ((struct df *, basic_block, rtx));
*************** extern void debug_df_ref PARAMS ((struct
*** 296,298 ****
--- 299,331 ----
extern void debug_df_chain PARAMS ((struct df_link *));
extern void df_insn_debug PARAMS ((struct df *, rtx, FILE *));
extern void df_insn_debug_regno PARAMS ((struct df *, rtx, FILE *));
+ /* Meet over any path (UNION) or meet over all paths (INTERSECTION) */
+ enum df_confluence_op
+ {
+ UNION,
+ INTERSECTION
+ };
+ /* Dataflow direction */
+ enum df_flow_dir
+ {
+ FORWARD,
+ BACKWARD
+ };
+
+ typedef void (*transfer_function_sbitmap) (int, int *, sbitmap, sbitmap,
+ sbitmap, sbitmap, void *);
+ typedef void (*transfer_function_ebitmap) (int, int *, ebitmap, ebitmap,
+ ebitmap, ebitmap, void *);
+
+ extern void iterative_dataflow_sbitmap PARAMS ((sbitmap *, sbitmap *,
+ sbitmap *, sbitmap *,
+ ebitmap, enum df_flow_dir,
+ enum df_confluence_op,
+ transfer_function_sbitmap,
+ int *, void *));
+ extern void iterative_dataflow_ebitmap PARAMS ((ebitmap *, ebitmap *, ebitmap *,
+ ebitmap *, ebitmap,
+ enum df_flow_dir,
+ enum df_confluence_op,
+ transfer_function_ebitmap,
+ int *, void *));
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/egcs/gcc/Makefile.in,v
retrieving revision 1.730
diff -c -3 -p -w -B -b -r1.730 Makefile.in
*** Makefile.in 2001/08/27 18:13:36 1.730
--- Makefile.in 2001/08/30 13:02:46
*************** ssa.o : ssa.c $(CONFIG_H) $(SYSTEM_H) $(
*** 1478,1489 ****
hard-reg-set.h flags.h function.h real.h insn-config.h $(RECOG_H) \
$(BASIC_BLOCK_H) output.h ssa.h
ssa-dce.o : ssa-dce.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) hard-reg-set.h \
! $(BASIC_BLOCK_H) ssa.h insn-config.h $(RECOG_H) output.h
ssa-ccp.o : ssa-ccp.c $(CONFIG_H) system.h $(RTL_H) hard-reg-set.h \
$(BASIC_BLOCK_H) ssa.h insn-config.h $(RECOG_H) output.h \
! errors.h $(GGC_H) df.h function.h
df.o : df.c $(CONFIG_H) system.h $(RTL_H) insn-config.h $(RECOG_H) \
! function.h $(REGS_H) $(OBSTACK_H) hard-reg-set.h $(BASIC_BLOCK_H) df.h
conflict.o : conflict.c $(CONFIG_H) $(SYSTEM_H) $(OBSTACK_H) $(HASHTAB_H) \
$(RTL_H) hard-reg-set.h $(BASIC_BLOCK_H)
profile.o : profile.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TREE_H) flags.h \
--- 1478,1492 ----
hard-reg-set.h flags.h function.h real.h insn-config.h $(RECOG_H) \
$(BASIC_BLOCK_H) output.h ssa.h
ssa-dce.o : ssa-dce.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) hard-reg-set.h \
! $(BASIC_BLOCK_H) ssa.h insn-config.h $(RECOG_H) output.h ebitmap.h
ssa-ccp.o : ssa-ccp.c $(CONFIG_H) system.h $(RTL_H) hard-reg-set.h \
$(BASIC_BLOCK_H) ssa.h insn-config.h $(RECOG_H) output.h \
! errors.h $(GGC_H) df.h function.h ebitmap.h
df.o : df.c $(CONFIG_H) system.h $(RTL_H) insn-config.h $(RECOG_H) \
! function.h $(REGS_H) $(OBSTACK_H) hard-reg-set.h $(BASIC_BLOCK_H) df.h \
! ebitmap.h
! ebitmap.o : ebitmap.c ebitmap.h $(CONFIG_H) ebitmap.h $(SYSTEM_H) alloc-pool.h
! alloc-pool.o : alloc-pool.c alloc-pool.h $(CONFIG_H) $(SYSTEM_H)
conflict.o : conflict.c $(CONFIG_H) $(SYSTEM_H) $(OBSTACK_H) $(HASHTAB_H) \
$(RTL_H) hard-reg-set.h $(BASIC_BLOCK_H)
profile.o : profile.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TREE_H) flags.h \
--
"I put a new engine in my car, but forgot to take the old one
out. Now my car goes 500 miles per hour. The harmonica sounds
*amazing*.
"-Steven Wright
More information about the Gcc-patches
mailing list