diff options
author | Paolo Bonzini <bonzini@gnu.org> | 2009-06-27 14:48:34 +0000 |
---|---|---|
committer | Paolo Bonzini <bonzini@gcc.gnu.org> | 2009-06-27 14:48:34 +0000 |
commit | c6741572cfd4b2ad9c262ec00e152cbf1ea8eb51 (patch) | |
tree | ccbd0084107a8508be366e60ac20d8c9a438201b | |
parent | 7ff23740a3d7fa1e41f7e58891c711b7ef25a90b (diff) | |
download | gcc-c6741572cfd4b2ad9c262ec00e152cbf1ea8eb51.zip gcc-c6741572cfd4b2ad9c262ec00e152cbf1ea8eb51.tar.gz gcc-c6741572cfd4b2ad9c262ec00e152cbf1ea8eb51.tar.bz2 |
re PR tree-optimization/26854 (Inordinate compile times on large routines)
2009-06-07 Paolo Bonzini <bonzini@gnu.org>
PR rtl-optimization/26854
* timevar.def: Remove TV_DF_RU, add TV_DF_MD.
* df-problems.c (df_rd_add_problem): Fix comment.
(df_md_set_bb_info, df_md_free_bb_info, df_md_alloc,
df_md_simulate_artificial_defs_at_top,
df_md_simulate_one_insn, df_md_bb_local_compute_process_def,
df_md_bb_local_compute, df_md_local_compute, df_md_reset,
df_md_transfer_function, df_md_init, df_md_confluence_0,
df_md_confluence_n, df_md_free, df_md_top_dump, df_md_bottom_dump,
problem_MD, df_md_add_problem): New.
* df.h (DF_MD, DF_MD_BB_INFO, struct df_md_bb_info, df_md,
df_md_get_bb_info): New.
DF_LAST_PROBLEM_PLUS1): Adjust.
* Makefile.in (fwprop.o): Include domwalk.h.
* fwprop.c: Include domwalk.h.
(reg_defs, reg_defs_stack): New.
(bitmap_only_bit_between): Remove.
(process_defs): New.
(process_uses): Use reg_defs and local_md instead of
bitmap_only_bit_between and local_rd.
(single_def_use_enter_block): New, from build_single_def_use_links.
(single_def_use_leave_block): New.
(build_single_def_use_links): Remove code moved to
single_def_use_enter_block, invoke domwalk.
(use_killed_between): Adjust comment.
From-SVN: r149010
-rw-r--r-- | gcc/ChangeLog | 29 | ||||
-rw-r--r-- | gcc/Makefile.in | 2 | ||||
-rw-r--r-- | gcc/df-problems.c | 450 | ||||
-rw-r--r-- | gcc/df.h | 33 | ||||
-rw-r--r-- | gcc/fwprop.c | 211 | ||||
-rw-r--r-- | gcc/timevar.def | 2 |
6 files changed, 658 insertions, 69 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index f7fdd4f..4134a2cf 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,32 @@ +2009-06-07 Paolo Bonzini <bonzini@gnu.org> + + PR rtl-optimization/26854 + * timevar.def: Remove TV_DF_RU, add TV_DF_MD. + * df-problems.c (df_rd_add_problem): Fix comment. + (df_md_set_bb_info, df_md_free_bb_info, df_md_alloc, + df_md_simulate_artificial_defs_at_top, + df_md_simulate_one_insn, df_md_bb_local_compute_process_def, + df_md_bb_local_compute, df_md_local_compute, df_md_reset, + df_md_transfer_function, df_md_init, df_md_confluence_0, + df_md_confluence_n, df_md_free, df_md_top_dump, df_md_bottom_dump, + problem_MD, df_md_add_problem): New. + * df.h (DF_MD, DF_MD_BB_INFO, struct df_md_bb_info, df_md, + df_md_get_bb_info): New. + DF_LAST_PROBLEM_PLUS1): Adjust. + + * Makefile.in (fwprop.o): Include domwalk.h. + * fwprop.c: Include domwalk.h. + (reg_defs, reg_defs_stack): New. + (bitmap_only_bit_between): Remove. + (process_defs): New. + (process_uses): Use reg_defs and local_md instead of + bitmap_only_bit_between and local_rd. + (single_def_use_enter_block): New, from build_single_def_use_links. + (single_def_use_leave_block): New. + (build_single_def_use_links): Remove code moved to + single_def_use_enter_block, invoke domwalk. + (use_killed_between): Adjust comment. + 2009-06-27 Paolo Bonzini <bonzini@gnu.org> * bitmap.h (bitmap_ior_and_into): New. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index d621d7f..d8bbc68 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -2761,7 +2761,7 @@ dse.o : dse.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \ fwprop.o : fwprop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \ $(TOPLEV_H) insn-config.h $(RECOG_H) $(FLAGS_H) $(OBSTACK_H) $(BASIC_BLOCK_H) \ output.h $(DF_H) alloc-pool.h $(TIMEVAR_H) $(TREE_PASS_H) $(TARGET_H) \ - $(TM_P_H) $(CFGLOOP_H) $(EMIT_RTL_H) + $(TM_P_H) $(CFGLOOP_H) $(EMIT_RTL_H) domwalk.h web.o : web.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \ hard-reg-set.h $(FLAGS_H) $(BASIC_BLOCK_H) $(FUNCTION_H) output.h $(TOPLEV_H) \ $(DF_H) $(OBSTACK_H) $(TIMEVAR_H) $(TREE_PASS_H) diff --git a/gcc/df-problems.c b/gcc/df-problems.c index 84dc42a..5e56025 100644 --- a/gcc/df-problems.c +++ b/gcc/df-problems.c @@ -726,9 +726,8 @@ static struct df_problem problem_RD = -/* Create a new DATAFLOW instance and add it to an existing instance - of DF. The returned structure is what is used to get at the - solution. */ +/* Create a new RD instance and add it to the existing instance + of DF. */ void df_rd_add_problem (void) @@ -3952,3 +3951,448 @@ df_simulate_finalize_forwards (basic_block bb, bitmap live) bitmap_clear_bit (live, DF_REF_REGNO (def)); } } + + + +/*---------------------------------------------------------------------------- + MULTIPLE DEFINITIONS + + Find the locations in the function reached by multiple definition sites + for a pseudo. In and out bitvectors are built for each basic + block. + + The gen and kill sets for the problem are obvious. Together they + include all defined registers in a basic block; the gen set includes + registers where a partial or conditional or may-clobber definition is + last in the BB, while the kill set includes registers with a complete + definition coming last. However, the computation of the dataflow + itself is interesting. + + The idea behind it comes from SSA form's iterated dominance frontier + criterion for inserting PHI functions. Just like in that case, we can use + the dominance frontier to find places where multiple definitions meet; + a register X defined in a basic block BB1 has multiple definitions in + basic blocks in BB1's dominance frontier. + + So, the in-set of a basic block BB2 is not just the union of the + out-sets of BB2's predecessors, but includes some more bits that come + from the basic blocks of whose dominance frontier BB2 is part (BB1 in + the previous paragraph). I called this set the init-set of BB2. + + (Note: I actually use the kill-set only to build the init-set. + gen bits are anyway propagated from BB1 to BB2 by dataflow). + + For example, if you have + + BB1 : r10 = 0 + r11 = 0 + if <...> goto BB2 else goto BB3; + + BB2 : r10 = 1 + r12 = 1 + goto BB3; + + BB3 : + + you have BB3 in BB2's dominance frontier but not in BB1's, so that the + init-set of BB3 includes r10 and r12, but not r11. Note that we do + not need to iterate the dominance frontier, because we do not insert + anything like PHI functions there! Instead, dataflow will take care of + propagating the information to BB3's successors. + ---------------------------------------------------------------------------*/ + +/* Set basic block info. */ + +static void +df_md_set_bb_info (unsigned int index, + struct df_md_bb_info *bb_info) +{ + gcc_assert (df_md); + gcc_assert (index < df_md->block_info_size); + df_md->block_info[index] = bb_info; +} + + +static void +df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED, + void *vbb_info) +{ + struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info; + if (bb_info) + { + BITMAP_FREE (bb_info->kill); + BITMAP_FREE (bb_info->gen); + BITMAP_FREE (bb_info->init); + BITMAP_FREE (bb_info->in); + BITMAP_FREE (bb_info->out); + pool_free (df_md->block_pool, bb_info); + } +} + + +/* Allocate or reset bitmaps for DF_MD. The solution bits are + not touched unless the block is new. */ + +static void +df_md_alloc (bitmap all_blocks) +{ + unsigned int bb_index; + bitmap_iterator bi; + + if (!df_md->block_pool) + df_md->block_pool = create_alloc_pool ("df_md_block pool", + sizeof (struct df_md_bb_info), 50); + + df_grow_bb_info (df_md); + + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) + { + struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index); + if (bb_info) + { + bitmap_clear (bb_info->init); + bitmap_clear (bb_info->gen); + bitmap_clear (bb_info->kill); + bitmap_clear (bb_info->in); + bitmap_clear (bb_info->out); + } + else + { + bb_info = (struct df_md_bb_info *) pool_alloc (df_md->block_pool); + df_md_set_bb_info (bb_index, bb_info); + bb_info->init = BITMAP_ALLOC (NULL); + bb_info->gen = BITMAP_ALLOC (NULL); + bb_info->kill = BITMAP_ALLOC (NULL); + bb_info->in = BITMAP_ALLOC (NULL); + bb_info->out = BITMAP_ALLOC (NULL); + } + } + + df_md->optional_p = true; +} + +/* Add the effect of the top artificial defs of BB to the multiple definitions + bitmap LOCAL_MD. */ + +void +df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md) +{ + int bb_index = bb->index; + df_ref *def_rec; + for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++) + { + df_ref def = *def_rec; + if (DF_REF_FLAGS (def) & DF_REF_AT_TOP) + { + unsigned int dregno = DF_REF_REGNO (def); + if (DF_REF_FLAGS (def) + & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)) + bitmap_set_bit (local_md, dregno); + else + bitmap_clear_bit (local_md, dregno); + } + } +} + + +/* Add the effect of the defs of INSN to the reaching definitions bitmap + LOCAL_MD. */ + +void +df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx insn, + bitmap local_md) +{ + unsigned uid = INSN_UID (insn); + df_ref *def_rec; + + for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) + { + df_ref def = *def_rec; + unsigned int dregno = DF_REF_REGNO (def); + if ((!(df->changeable_flags & DF_NO_HARD_REGS)) + || (dregno >= FIRST_PSEUDO_REGISTER)) + { + if (DF_REF_FLAGS (def) + & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)) + bitmap_set_bit (local_md, DF_REF_ID (def)); + else + bitmap_clear_bit (local_md, DF_REF_ID (def)); + } + } +} + +static void +df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info, + df_ref *def_rec, + int top_flag) +{ + df_ref def; + bitmap_clear (seen_in_insn); + + while ((def = *def_rec++) != NULL) + { + unsigned int dregno = DF_REF_REGNO (def); + if (((!(df->changeable_flags & DF_NO_HARD_REGS)) + || (dregno >= FIRST_PSEUDO_REGISTER)) + && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP)) + { + if (!bitmap_bit_p (seen_in_insn, dregno)) + { + if (DF_REF_FLAGS (def) + & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)) + { + bitmap_set_bit (bb_info->gen, dregno); + bitmap_clear_bit (bb_info->kill, dregno); + } + else + { + /* When we find a clobber and a regular def, + make sure the regular def wins. */ + bitmap_set_bit (seen_in_insn, dregno); + bitmap_set_bit (bb_info->kill, dregno); + bitmap_clear_bit (bb_info->gen, dregno); + } + } + } + } +} + + +/* Compute local multiple def info for basic block BB. */ + +static void +df_md_bb_local_compute (unsigned int bb_index) +{ + basic_block bb = BASIC_BLOCK (bb_index); + struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index); + rtx insn; + + /* Artificials are only hard regs. */ + if (!(df->changeable_flags & DF_NO_HARD_REGS)) + df_md_bb_local_compute_process_def (bb_info, + df_get_artificial_defs (bb_index), + DF_REF_AT_TOP); + + FOR_BB_INSNS (bb, insn) + { + unsigned int uid = INSN_UID (insn); + if (!INSN_P (insn)) + continue; + + df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0); + } + + if (!(df->changeable_flags & DF_NO_HARD_REGS)) + df_md_bb_local_compute_process_def (bb_info, + df_get_artificial_defs (bb_index), + 0); +} + +/* Compute local reaching def info for each basic block within BLOCKS. */ + +static void +df_md_local_compute (bitmap all_blocks) +{ + unsigned int bb_index, df_bb_index; + bitmap_iterator bi1, bi2; + basic_block bb; + bitmap *frontiers; + + df_set_seen (); + + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1) + { + df_md_bb_local_compute (bb_index); + } + + df_unset_seen (); + + frontiers = XNEWVEC (bitmap, last_basic_block); + FOR_ALL_BB (bb) + frontiers[bb->index] = BITMAP_ALLOC (NULL); + + compute_dominance_frontiers (frontiers); + + /* Add each basic block's kills to the nodes in the frontier of the BB. */ + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1) + { + bitmap kill = df_md_get_bb_info (bb_index)->kill; + EXECUTE_IF_SET_IN_BITMAP (frontiers[bb_index], 0, df_bb_index, bi2) + { + if (bitmap_bit_p (all_blocks, df_bb_index)) + bitmap_ior_into (df_md_get_bb_info (df_bb_index)->init, kill); + } + } + + FOR_ALL_BB (bb) + BITMAP_FREE (frontiers[bb->index]); + free (frontiers); +} + + +/* Reset the global solution for recalculation. */ + +static void +df_md_reset (bitmap all_blocks) +{ + unsigned int bb_index; + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) + { + struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index); + gcc_assert (bb_info); + bitmap_clear (bb_info->in); + bitmap_clear (bb_info->out); + } +} + +static bool +df_md_transfer_function (int bb_index) +{ + struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index); + bitmap in = bb_info->in; + bitmap out = bb_info->out; + bitmap gen = bb_info->gen; + bitmap kill = bb_info->kill; + + return bitmap_ior_and_compl (out, gen, in, kill); +} + +/* Initialize the solution bit vectors for problem. */ + +static void +df_md_init (bitmap all_blocks) +{ + unsigned int bb_index; + bitmap_iterator bi; + + EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi) + { + struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index); + + bitmap_copy (bb_info->in, bb_info->init); + df_md_transfer_function (bb_index); + } +} + +static void +df_md_confluence_0 (basic_block bb) +{ + struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index); + bitmap_copy (bb_info->in, bb_info->init); +} + +/* In of target gets or of out of source. */ + +static void +df_md_confluence_n (edge e) +{ + bitmap op1 = df_md_get_bb_info (e->dest->index)->in; + bitmap op2 = df_md_get_bb_info (e->src->index)->out; + + if (e->flags & EDGE_FAKE) + return; + + if (e->flags & EDGE_EH) + bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset); + else + bitmap_ior_into (op1, op2); +} + +/* Free all storage associated with the problem. */ + +static void +df_md_free (void) +{ + unsigned int i; + for (i = 0; i < df_md->block_info_size; i++) + { + struct df_md_bb_info *bb_info = df_md_get_bb_info (i); + if (bb_info) + { + BITMAP_FREE (bb_info->kill); + BITMAP_FREE (bb_info->gen); + BITMAP_FREE (bb_info->init); + BITMAP_FREE (bb_info->in); + BITMAP_FREE (bb_info->out); + } + } + + free_alloc_pool (df_md->block_pool); + + df_md->block_info_size = 0; + free (df_md->block_info); + free (df_md); +} + + +/* Debugging info at top of bb. */ + +static void +df_md_top_dump (basic_block bb, FILE *file) +{ + struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index); + if (!bb_info || !bb_info->in) + return; + + fprintf (file, ";; md in \t"); + df_print_regset (file, bb_info->in); + fprintf (file, ";; md init \t"); + df_print_regset (file, bb_info->init); + fprintf (file, ";; md gen \t"); + df_print_regset (file, bb_info->gen); + fprintf (file, ";; md kill \t"); + df_print_regset (file, bb_info->kill); +} + +/* Debugging info at bottom of bb. */ + +static void +df_md_bottom_dump (basic_block bb, FILE *file) +{ + struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index); + if (!bb_info || !bb_info->out) + return; + + fprintf (file, ";; md out \t"); + df_print_regset (file, bb_info->out); +} + +static struct df_problem problem_MD = +{ + DF_MD, /* Problem id. */ + DF_FORWARD, /* Direction. */ + df_md_alloc, /* Allocate the problem specific data. */ + df_md_reset, /* Reset global information. */ + df_md_free_bb_info, /* Free basic block info. */ + df_md_local_compute, /* Local compute function. */ + df_md_init, /* Init the solution specific data. */ + df_worklist_dataflow, /* Worklist solver. */ + df_md_confluence_0, /* Confluence operator 0. */ + df_md_confluence_n, /* Confluence operator n. */ + df_md_transfer_function, /* Transfer function. */ + NULL, /* Finalize function. */ + df_md_free, /* Free all of the problem information. */ + df_md_free, /* Remove this problem from the stack of dataflow problems. */ + NULL, /* Debugging. */ + df_md_top_dump, /* Debugging start block. */ + df_md_bottom_dump, /* Debugging end block. */ + NULL, /* Incremental solution verify start. */ + NULL, /* Incremental solution verify end. */ + NULL, /* Dependent problem. */ + TV_DF_MD, /* Timing variable. */ + false /* Reset blocks on dropping out of blocks_to_analyze. */ +}; + +/* Create a new MD instance and add it to the existing instance + of DF. */ + +void +df_md_add_problem (void) +{ + df_add_problem (&problem_MD); +} + + + @@ -52,8 +52,9 @@ union df_ref_d; #define DF_CHAIN 4 /* Def-Use and/or Use-Def Chains. */ #define DF_BYTE_LR 5 /* Subreg tracking lr. */ #define DF_NOTE 6 /* REG_DEF and REG_UNUSED notes. */ +#define DF_MD 7 /* Multiple Definitions. */ -#define DF_LAST_PROBLEM_PLUS1 (DF_NOTE + 1) +#define DF_LAST_PROBLEM_PLUS1 (DF_MD + 1) /* Dataflow direction. */ enum df_flow_dir @@ -619,6 +620,7 @@ struct df #define DF_LR_BB_INFO(BB) (df_lr_get_bb_info((BB)->index)) #define DF_LIVE_BB_INFO(BB) (df_live_get_bb_info((BB)->index)) #define DF_BYTE_LR_BB_INFO(BB) (df_byte_lr_get_bb_info((BB)->index)) +#define DF_MD_BB_INFO(BB) (df_md_get_bb_info((BB)->index)) /* Most transformations that wish to use live register analysis will use these macros. This info is the and of the lr and live sets. */ @@ -802,6 +804,22 @@ struct df_rd_bb_info }; +/* Multiple reaching definitions. All bitmaps are referenced by the + register number. */ + +struct df_md_bb_info +{ + /* Local sets to describe the basic blocks. */ + bitmap gen; /* Partial/conditional definitions live at BB out. */ + bitmap kill; /* Other definitions that are live at BB out. */ + bitmap init; /* Definitions coming from dominance frontier edges. */ + + /* The results of the dataflow problem. */ + bitmap in; /* Just before the block itself. */ + bitmap out; /* At the bottom of the block. */ +}; + + /* Live registers, a backwards dataflow problem. All bitmaps are referenced by the register number. */ @@ -862,6 +880,7 @@ extern struct df *df; #define df_chain (df->problems_by_index[DF_CHAIN]) #define df_byte_lr (df->problems_by_index[DF_BYTE_LR]) #define df_note (df->problems_by_index[DF_NOTE]) +#define df_md (df->problems_by_index[DF_MD]) /* This symbol turns on checking that each modification of the cfg has been identified to the appropriate df routines. It is not part of @@ -955,6 +974,9 @@ extern void df_byte_lr_simulate_uses (rtx, bitmap); extern void df_byte_lr_simulate_artificial_refs_at_top (basic_block, bitmap); extern void df_byte_lr_simulate_artificial_refs_at_end (basic_block, bitmap); extern void df_note_add_problem (void); +extern void df_md_add_problem (void); +extern void df_md_simulate_artificial_defs_at_top (basic_block, bitmap); +extern void df_md_simulate_one_insn (basic_block, rtx, bitmap); extern void df_simulate_find_defs (rtx, bitmap); extern void df_simulate_defs (rtx, bitmap); extern void df_simulate_uses (rtx, bitmap); @@ -1034,6 +1056,15 @@ df_lr_get_bb_info (unsigned int index) return NULL; } +static inline struct df_md_bb_info * +df_md_get_bb_info (unsigned int index) +{ + if (index < df_md->block_info_size) + return (struct df_md_bb_info *) df_md->block_info[index]; + else + return NULL; +} + static inline struct df_live_bb_info * df_live_get_bb_info (unsigned int index) { diff --git a/gcc/fwprop.c b/gcc/fwprop.c index 58cc9b0..df4edf9 100644 --- a/gcc/fwprop.c +++ b/gcc/fwprop.c @@ -38,6 +38,7 @@ along with GCC; see the file COPYING3. If not see #include "target.h" #include "cfgloop.h" #include "tree-pass.h" +#include "domwalk.h" /* This pass does simple forward propagation and simplification when an @@ -100,7 +101,17 @@ along with GCC; see the file COPYING3. If not see (set (reg:QI 121) (subreg:QI (reg:SI 119) 0)) (set (reg:SI 122) (plus:SI (reg:SI 118) (reg:SI 119))) - where the first two insns are now dead. */ + where the first two insns are now dead. + + We used to use reaching definitions to find which uses have a + single reaching definition (sounds obvious...), but this is too + complex a problem in nasty testcases like PR33928. Now we use the + multiple definitions problem in df-problems.c. The similarity + between that problem and SSA form creation is taken further, in + that fwprop does a dominator walk to create its chains; however, + instead of creating a PHI function where multiple definitions meet + I just punt and record only singleton use-def chains, which is + all that is needed by fwprop. */ static int num_changes; @@ -108,6 +119,8 @@ static int num_changes; DEF_VEC_P(df_ref); DEF_VEC_ALLOC_P(df_ref,heap); VEC(df_ref,heap) *use_def_ref; +VEC(df_ref,heap) *reg_defs; +VEC(df_ref,heap) *reg_defs_stack; /* Return the only def in USE's use-def chain, or NULL if there is @@ -120,96 +133,168 @@ get_def_for_use (df_ref use) } -/* Return the only bit between FIRST and LAST that is set in B, - or -1 if there are zero or more than one such bits. */ +/* Update the reg_defs vector with non-partial definitions in DEF_REC. + TOP_FLAG says which artificials uses should be used, when DEF_REC + is an artificial def vector. LOCAL_MD is modified as after a + df_md_simulate_* function; we do more or less the same processing + done there, so we do not use those functions. */ + +#define DF_MD_GEN_FLAGS \ + (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER) -static inline int -bitmap_only_bit_between (const_bitmap b, unsigned first, unsigned last) +static void +process_defs (bitmap local_md, df_ref *def_rec, int top_flag) { - bitmap_iterator bi; - unsigned bit, bit2; + df_ref def; + while ((def = *def_rec++) != NULL) + { + df_ref curr_def = VEC_index (df_ref, reg_defs, DF_REF_REGNO (def)); + unsigned int dregno; - if (last < first) - return -1; + if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) != top_flag) + continue; - bmp_iter_set_init (&bi, b, first, &bit); - if (bmp_iter_set (&bi, &bit) && bit <= last) - { - bit2 = bit; - bmp_iter_next (&bi, &bit2); - if (!bmp_iter_set (&bi, &bit2) || bit2 > last) - return bit; + dregno = DF_REF_REGNO (def); + if (curr_def) + VEC_safe_push (df_ref, heap, reg_defs_stack, curr_def); + else + { + /* Do not store anything if "transitioning" from NULL to NULL. But + otherwise, push a special entry on the stack to tell the + leave_block callback that the entry in reg_defs was NULL. */ + if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS) + ; + else + VEC_safe_push (df_ref, heap, reg_defs_stack, def); + } + + if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS) + { + bitmap_set_bit (local_md, dregno); + VEC_replace (df_ref, reg_defs, dregno, NULL); + } + else + { + bitmap_clear_bit (local_md, dregno); + VEC_replace (df_ref, reg_defs, dregno, def); + } } - return -1; } /* Fill the use_def_ref vector with values for the uses in USE_REC, - taking reaching definitions info from LOCAL_RD. TOP_FLAG says - which artificials uses should be used, when USE_REC is an - artificial use vector. */ + taking reaching definitions info from LOCAL_MD and REG_DEFS. + TOP_FLAG says which artificials uses should be used, when USE_REC + is an artificial use vector. */ static void -process_uses (bitmap local_rd, df_ref *use_rec, int top_flag) +process_uses (bitmap local_md, df_ref *use_rec, int top_flag) { df_ref use; while ((use = *use_rec++) != NULL) - if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP)) + if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == top_flag) { - unsigned int uregno = DF_REF_REGNO (use); - unsigned int first = DF_DEFS_BEGIN (uregno); - unsigned int last = first + DF_DEFS_COUNT (uregno) - 1; - int defno = bitmap_only_bit_between (local_rd, first, last); - df_ref def = (defno == -1) ? NULL : DF_DEFS_GET (defno); + unsigned int uregno = DF_REF_REGNO (use); + if (VEC_index (df_ref, reg_defs, uregno) + && !bitmap_bit_p (local_md, uregno)) + VEC_replace (df_ref, use_def_ref, DF_REF_ID (use), + VEC_index (df_ref, reg_defs, uregno)); + } +} + + +static void +single_def_use_enter_block (struct dom_walk_data *walk_data, basic_block bb) +{ + bitmap local_md = (bitmap) walk_data->global_data; + int bb_index = bb->index; + struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index); + rtx insn; + + bitmap_copy (local_md, bb_info->in); - VEC_replace (df_ref, use_def_ref, DF_REF_ID (use), def); + /* Push a marker for the leave_block callback. */ + VEC_safe_push (df_ref, heap, reg_defs_stack, NULL); + + process_uses (local_md, df_get_artificial_uses (bb_index), DF_REF_AT_TOP); + process_defs (local_md, df_get_artificial_defs (bb_index), DF_REF_AT_TOP); + + FOR_BB_INSNS (bb, insn) + if (INSN_P (insn)) + { + unsigned int uid = INSN_UID (insn); + process_uses (local_md, DF_INSN_UID_USES (uid), 0); + process_uses (local_md, DF_INSN_UID_EQ_USES (uid), 0); + process_defs (local_md, DF_INSN_UID_DEFS (uid), 0); } + + process_uses (local_md, df_get_artificial_uses (bb_index), 0); + process_defs (local_md, df_get_artificial_defs (bb_index), 0); +} + +/* Pop the definitions created in this basic block when leaving its + dominated parts. */ + +static void +single_def_use_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED, + basic_block bb ATTRIBUTE_UNUSED) +{ + df_ref saved_def; + while ((saved_def = VEC_pop (df_ref, reg_defs_stack)) != NULL) + { + unsigned int dregno = DF_REF_REGNO (saved_def); + + /* See also process_defs. */ + if (saved_def == VEC_index (df_ref, reg_defs, dregno)) + VEC_replace (df_ref, reg_defs, dregno, NULL); + else + VEC_replace (df_ref, reg_defs, dregno, saved_def); + } } -/* Do dataflow analysis and use reaching definitions to build - a vector holding the reaching definitions of uses that have a - single RD. */ +/* Build a vector holding the reaching definitions of uses reached by a + single dominating definition. */ static void build_single_def_use_links (void) { - basic_block bb; - bitmap local_rd = BITMAP_ALLOC (NULL); + struct dom_walk_data walk_data; + bitmap local_md; - /* We use reaching definitions to compute our restricted use-def chains. */ + /* We use the multiple definitions problem to compute our restricted + use-def chains. */ df_set_flags (DF_EQ_NOTES); - df_rd_add_problem (); + df_md_add_problem (); df_analyze (); df_maybe_reorganize_use_refs (DF_REF_ORDER_BY_INSN_WITH_NOTES); use_def_ref = VEC_alloc (df_ref, heap, DF_USES_TABLE_SIZE ()); - VEC_safe_grow (df_ref, heap, use_def_ref, DF_USES_TABLE_SIZE ()); + VEC_safe_grow_cleared (df_ref, heap, use_def_ref, DF_USES_TABLE_SIZE ()); - FOR_EACH_BB (bb) - { - int bb_index = bb->index; - struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index); - rtx insn; - - bitmap_copy (local_rd, bb_info->in); - process_uses (local_rd, df_get_artificial_uses (bb_index), DF_REF_AT_TOP); - - df_rd_simulate_artificial_defs_at_top (bb, local_rd); - FOR_BB_INSNS (bb, insn) - if (INSN_P (insn)) - { - unsigned int uid = INSN_UID (insn); - process_uses (local_rd, DF_INSN_UID_USES (uid), 0); - process_uses (local_rd, DF_INSN_UID_EQ_USES (uid), 0); - df_rd_simulate_one_insn (bb, insn, local_rd); - } + reg_defs = VEC_alloc (df_ref, heap, max_reg_num ()); + VEC_safe_grow_cleared (df_ref, heap, reg_defs, max_reg_num ()); - process_uses (local_rd, df_get_artificial_uses (bb_index), 0); - } + reg_defs_stack = VEC_alloc (df_ref, heap, n_basic_blocks * 10); + local_md = BITMAP_ALLOC (NULL); + + /* Walk the dominator tree looking for single reaching definitions + dominating the uses. This is similar to how SSA form is built. */ + walk_data.dom_direction = CDI_DOMINATORS; + walk_data.initialize_block_local_data = NULL; + walk_data.before_dom_children = single_def_use_enter_block; + walk_data.after_dom_children = single_def_use_leave_block; + walk_data.global_data = local_md; - BITMAP_FREE (local_rd); + init_walk_dominator_tree (&walk_data); + walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR); + fini_walk_dominator_tree (&walk_data); + + BITMAP_FREE (local_md); + VEC_free (df_ref, heap, reg_defs); + VEC_free (df_ref, heap, reg_defs_stack); } + /* Do not try to replace constant addresses or addresses of local and argument slots. These MEM expressions are made only once and inserted @@ -629,12 +714,12 @@ use_killed_between (df_ref use, rtx def_insn, rtx target_insn) int regno; df_ref def; - /* In some obscure situations we can have a def reaching a use - that is _before_ the def. In other words the def does not - dominate the use even though the use and def are in the same - basic block. This can happen when a register may be used - uninitialized in a loop. In such cases, we must assume that - DEF is not available. */ + /* We used to have a def reaching a use that is _before_ the def, + with the def not dominating the use even though the use and def + are in the same basic block, when a register may be used + uninitialized in a loop. This should not happen anymore since + we do not use reaching definitions, but still we test for such + cases and assume that DEF is not available. */ if (def_bb == target_bb ? DF_INSN_LUID (def_insn) >= DF_INSN_LUID (target_insn) : !dominated_by_p (CDI_DOMINATORS, target_bb, def_bb)) diff --git a/gcc/timevar.def b/gcc/timevar.def index 9d72763..938447f 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -58,7 +58,7 @@ DEFTIMEVAR (TV_LIFE_UPDATE , "life info update") /* Time spent in dataflow problems. */ DEFTIMEVAR (TV_DF_SCAN , "df scan insns") -DEFTIMEVAR (TV_DF_RU , "df reaching uses") +DEFTIMEVAR (TV_DF_MD , "df multiple defs") DEFTIMEVAR (TV_DF_RD , "df reaching defs") DEFTIMEVAR (TV_DF_LR , "df live regs") DEFTIMEVAR (TV_DF_LIVE , "df live&initialized regs") |