This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH]: Add iterative dataflow functions, convert df.c to use
- To: gcc-patches at gcc dot gnu dot org
- Subject: [PATCH]: Add iterative dataflow functions, convert df.c to use
- From: Daniel Berlin <dan at cgsoftware dot com>
- Date: Fri, 19 Oct 2001 11:58:53 -0400
Looks big, but it's removing more code than it adds.
2001-08-30 Daniel Berlin <dan@cgsoftware.com>
* Makefile.in (df.o): Add fibheap.h to dependencies.
* df.h: Add prototypes for transfer functions, iterative_dataflow
functions.
(enum df_flow_dir): New enum.
(enum df_confluence_op): New enum.
(struct df): Add inverse_rts_map.
* df.c: Add sbitmap.h to the list of includes.
(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_bb_rd_local_compute): Use a temporary sbitmap, then copy the results
back into the regsets. This is because we hit worst case bitmap
performance otherwise, since we continually are jumping around.
(df_bb_ru_local_compute): Ditto.
(df_analyse_1): allocate/compute/free df->inverse_rts_map.
Use iterative_dataflow_bitmap instead of df_*_global_compute.
(iterative_dataflow_sbitmap): New function.
(iterative_dataflow_bitmap): New function.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/egcs/gcc/Makefile.in,v
retrieving revision 1.752
diff -c -3 -p -w -B -b -r1.752 Makefile.in
*** Makefile.in 2001/10/17 09:31:34 1.752
--- Makefile.in 2001/10/19 15:50:40
*************** SYSTEM_HEADER_DIR = /usr/include
*** 236,241 ****
--- 236,242 ----
HASHTAB_H = $(srcdir)/../include/hashtab.h
OBSTACK_H = $(srcdir)/../include/obstack.h
SPLAY_TREE_H= $(srcdir)/../include/splay-tree.h
+ FIBHEAP_H = $(srcdir)/../include/fibheap.h
# Default cross SYSTEM_HEADER_DIR, to be overridden by targets.
CROSS_SYSTEM_HEADER_DIR = $(tooldir)/sys-include
*************** ssa-ccp.o : ssa-ccp.c $(CONFIG_H) system
*** 1483,1489 ****
$(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 \
--- 1486,1493 ----
$(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 \
! $(FIBHEAP_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 \
Index: df.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/df.c,v
retrieving revision 1.14
diff -c -3 -p -w -B -b -r1.14 df.c
*** df.c 2001/10/11 03:15:27 1.14
--- df.c 2001/10/19 15:50:41
*************** 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_; \
*************** static void df_insn_refs_record PARAMS((
*** 238,256 ****
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));
--- 239,252 ----
static void df_bb_refs_record PARAMS((struct df *, basic_block));
static void df_refs_record PARAMS((struct df *, bitmap));
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, sbitmap));
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_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_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 *, bitmap, bitmap,
+ bitmap, bitmap, void *));
+ static void df_ru_transfer_function PARAMS ((int, int *, bitmap, bitmap,
+ bitmap, bitmap, void *));
+ static void df_lr_transfer_function PARAMS ((int, int *, bitmap, bitmap,
+ bitmap, bitmap, void *));
/* Local memory allocation/deallocation routines. */
*************** 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. */
--- 1435,1450 ----
df_bb_du_chain_create (df, bb, ru)
struct df *df;
basic_block bb;
! sbitmap ru;
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
rtx insn;
! int i;
! sbitmap_zero (ru);
! EXECUTE_IF_SET_IN_BITMAP (bb_info->ru_out, 0, i,
! {
! SET_BIT (ru, i);
! });
/* 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));
}
}
}
--- 1474,1485 ----
{
struct ref *use = use_link->ref;
! if (TEST_BIT (ru, DF_REF_ID (use)))
{
DF_REF_CHAIN (def)
= df_link_create (use, DF_REF_CHAIN (def));
! RESET_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));
}
}
}
--- 1488,1494 ----
for (use_link = df->insns[uid].uses; use_link; use_link = use_link->next)
{
struct ref *use = use_link->ref;
! SET_BIT (ru, DF_REF_ID (use));
}
}
}
*************** df_du_chain_create (df, blocks)
*** 1496,1512 ****
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);
}
--- 1501,1517 ----
struct df *df;
bitmap blocks;
{
! sbitmap ru;
basic_block bb;
! ru = sbitmap_alloc (df->n_uses);
FOR_EACH_BB_IN_BITMAP (blocks, 0, bb,
{
df_bb_du_chain_create (df, bb, ru);
});
! sbitmap_free (ru);
}
*************** df_ud_chain_create (df, blocks)
*** 1601,1863 ****
}
- /* 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)
--- 1606,1642 ----
}
static void
! df_rd_transfer_function (bb, changed, in, out, gen, kill, data)
! int bb ATTRIBUTE_UNUSED;
! int *changed;
! bitmap in, out, gen, kill;
! void *data ATTRIBUTE_UNUSED;
{
! *changed = bitmap_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;
! bitmap in, out, gen, kill;
! void *data ATTRIBUTE_UNUSED;
{
! *changed = bitmap_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;
! bitmap in, out, use, def;
! void *data ATTRIBUTE_UNUSED;
{
! *changed = bitmap_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)
*** 1865,1871 ****
--- 1644,1656 ----
basic_block bb;
{
struct bb_info *bb_info = DF_BB_INFO (df, bb);
+ unsigned int i;
+ sbitmap gen, kill;
rtx insn;
+ gen = sbitmap_alloc (df->n_defs);
+ kill = sbitmap_alloc (df->n_defs);
+ sbitmap_zero (gen);
+ sbitmap_zero (kill);
for (insn = bb->head; insn && insn != NEXT_INSN (bb->end);
insn = NEXT_INSN (insn))
*************** 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;
}
--- 1676,1700 ----
is greedy since many of these defs will not actually
be killed by this BB but it keeps things a lot
simpler. */
! SET_BIT (kill, DF_REF_ID (def2));
/* Zap from the set of gens for this BB. */
! RESET_BIT (gen, DF_REF_ID (def2));
}
! SET_BIT (gen, DF_REF_ID (def));
}
}
! EXECUTE_IF_SET_IN_SBITMAP (gen, 0, i,
! {
! bitmap_set_bit (bb_info->rd_gen, i);
! });
! EXECUTE_IF_SET_IN_SBITMAP (kill, 0, i,
! {
! bitmap_set_bit (bb_info->rd_kill, i);
! });
! sbitmap_free (gen);
! sbitmap_free (kill);
bb_info->rd_valid = 1;
}
*************** df_bb_ru_local_compute (df, bb)
*** 1927,1938 ****
struct df *df;
basic_block bb;
{
/* This is much more tricky than computing reaching defs. With
reaching defs, defs get killed by other defs. With upwards
exposed uses, these get killed by defs with the same regno. */
- struct bb_info *bb_info = DF_BB_INFO (df, bb);
- rtx insn;
for (insn = bb->end; insn && insn != PREV_INSN (bb->head);
insn = PREV_INSN (insn))
--- 1721,1738 ----
struct df *df;
basic_block bb;
{
+ unsigned int i;
+ sbitmap gen, kill;
+ struct bb_info *bb_info = DF_BB_INFO (df, bb);
+ rtx insn;
+ gen = sbitmap_alloc (df->n_uses);
+ kill = sbitmap_alloc (df->n_uses);
+ sbitmap_zero (gen);
+ sbitmap_zero (kill);
/* This is much more tricky than computing reaching defs. With
reaching defs, defs get killed by other defs. With upwards
exposed uses, these get killed by defs with the same regno. */
for (insn = bb->end; insn && insn != PREV_INSN (bb->head);
insn = PREV_INSN (insn))
*************** 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));
}
}
--- 1758,1767 ----
is greedy since many of these uses will not actually
be killed by this BB but it keeps things a lot
simpler. */
! SET_BIT (kill, DF_REF_ID (use));
/* Zap from the set of gens for this BB. */
! RESET_BIT (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;
}
--- 1769,1787 ----
{
struct ref *use = use_link->ref;
/* Add use to set of gens in this BB. */
! SET_BIT (gen, DF_REF_ID (use));
}
}
+ EXECUTE_IF_SET_IN_SBITMAP (gen, 0, i,
+ {
+ bitmap_set_bit (bb_info->ru_gen, i);
+ });
+ EXECUTE_IF_SET_IN_SBITMAP (kill, 0, i,
+ {
+ bitmap_set_bit (bb_info->ru_kill, i);
+ });
+ sbitmap_free (gen);
+ sbitmap_free (kill);
bb_info->ru_valid = 1;
}
*************** df_analyse_1 (df, blocks, flags, update)
*** 2172,2178 ****
{
int aflags;
int dflags;
!
dflags = 0;
aflags = flags;
if (flags & DF_UD_CHAIN)
--- 1982,1988 ----
{
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)
{
--- 2049,2088 ----
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;
! bitmap *in = alloca (sizeof (bitmap) * n_basic_blocks);
! bitmap *out = alloca (sizeof (bitmap) * n_basic_blocks);
! bitmap *gen = alloca (sizeof (bitmap) * n_basic_blocks);
! bitmap *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_bitmap (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,2274 ****
/* 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)
{
--- 2098,2121 ----
/* 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;
! bitmap *in = alloca (sizeof (bitmap) * n_basic_blocks);
! bitmap *out = alloca (sizeof (bitmap) * n_basic_blocks);
! bitmap *gen = alloca (sizeof (bitmap) * n_basic_blocks);
! bitmap *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_bitmap (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,2295 ****
{
/* 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)
--- 2134,2156 ----
{
/* 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;
! bitmap *in = alloca (sizeof (bitmap) * n_basic_blocks);
! bitmap *out = alloca (sizeof (bitmap) * n_basic_blocks);
! bitmap *use = alloca (sizeof (bitmap) * n_basic_blocks);
! bitmap *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_bitmap (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 ****
--- 2160,2168 ----
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_insn_modify (df, bb, insn)
*** 2623,2636 ****
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
of all the refs of the original insn and turn them into
anti-refs. When df_refs_update finds these anti-refs, it annihilates
the original refs. If validate_change fails then these anti-refs
will just get ignored. */
- */
- #endif
}
--- 2487,2497 ----
*************** debug_df_chain (link)
*** 3752,3754 ****
--- 3613,3895 ----
df_chain_dump (link, stderr);
fputc ('\n', stderr);
}
+
+ /* gen = GEN set.
+ kill = KILL set.
+ in, out = Filled in by this 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 solve dataflow problems, using iteration,
+ 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).
+ For backwards problems, you probably want to pass in a mapping of
+ block number to rts_order (like df->inverse_rts_map).
+ */
+
+ void
+ iterative_dataflow_sbitmap (in, out, gen, kill, blocks,
+ dir, conf_op, transfun, order, data)
+ sbitmap *in, *out, *gen, *kill;
+ bitmap 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_BITMAP (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 */
+ for (e = bb->pred; e != 0; e = e->pred_next)
+ {
+ if (e->src == ENTRY_BLOCK_PTR)
+ {
+ sbitmap_zero (in[i]);
+ continue;
+ }
+ sbitmap_copy (in[i], out[e->src->index]);
+ break;
+ }
+ if (e == 0)
+ 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_bitmap (in, out, gen, kill, blocks,
+ dir, conf_op, transfun, order, data)
+ bitmap *in, *out, *gen, *kill;
+ bitmap blocks;
+ enum df_flow_dir dir;
+ enum df_confluence_op conf_op;
+ transfer_function_bitmap 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_BITMAP (blocks, 0, i,
+ {
+ fibheap_insert (worklist, order[i], (void *) i);
+ SET_BIT (onqueue, i);
+ if (dir == FORWARD)
+ {
+ bitmap_copy (out[i], gen[i]);
+ }
+ else
+ {
+ bitmap_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 */
+ bitmap_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:
+ bitmap_a_or_b (in[i], in[i], out[e->src->index]);
+ break;
+ case INTERSECTION:
+ bitmap_a_and_b (in[i], in[i], out[e->src->index]);
+ break;
+ }
+ }
+ }
+ else
+ {
+ /* Calculate <conf_op> of successor ins */
+ bitmap_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:
+ bitmap_a_or_b (out[i], out[i], in[e->dest->index]);
+ break;
+ case INTERSECTION:
+ bitmap_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/10/19 15:50:41
*************** 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 "bitmap.h"
#define DF_RD 1 /* Reaching definitions. */
#define DF_RU 2 /* Reaching uses. */
#define DF_LR 4 /* Live registers. */
*************** struct df
*** 135,146 ****
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;
};
--- 135,149 ----
bitmap insns_modified; /* Insns that (may) have changed. */
bitmap bbs_modified; /* Blocks that (may) have changed. */
bitmap 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 */
};
*************** 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_bitmap) (int, int *, bitmap, bitmap,
+ bitmap, bitmap, void *);
+
+ extern void iterative_dataflow_sbitmap PARAMS ((sbitmap *, sbitmap *,
+ sbitmap *, sbitmap *,
+ bitmap, enum df_flow_dir,
+ enum df_confluence_op,
+ transfer_function_sbitmap,
+ int *, void *));
+ extern void iterative_dataflow_bitmap PARAMS ((bitmap *, bitmap *, bitmap *,
+ bitmap *, bitmap,
+ enum df_flow_dir,
+ enum df_confluence_op,
+ transfer_function_bitmap,
+ int *, void *));
--
"(Later:) I bought one of those little glass ball things with
the snow in it... Just checking.
"-Steven Wright