| Message ID | 4CBCBBCF.2020108@gnu.org |
|---|---|
| State | New |
| Headers | show |
On Mon, Oct 18, 2010 at 11:27:43PM +0200, Paolo Bonzini wrote: > It turns out fwprop has been incredibly broken since it's inception. :( > > Its incremental dataflow update looks at the uses in the instruction > before propagation, and creates new uses based on their presence after > propagation. But when fwprop copy propagates a pseudo into another > instruction, it misses the uses of the propagated pseudo. I find it > incredible that this never triggered in so many years. > > To fix the problem, the patch does not look at the old uses, and instead > reconstructs them using df-scan. To do this it cannot use > df_insn_rescan, because this would remove the old defs and make the > use->def links dangling. So I just created a new function > df_uses_create that scans an instruction and creates new refs like > df_ref_create would have done. > > With this in place, there is the question of how to create use->def > links for the new uses. The old way to do the updates could easily > create the links because, by knowing a correspondence from old to new > uses, it could reuse each old use's def link. > > The new scheme, instead, is based on the following observation: the new > uses can only refer to very few pseudos, those in the propagated-from > insn and those in the propagated-to insn. fwprop walks the uses in the > two insns and prepares in advance a map from pseudos to their defs. When > checking is enabled, I added assertions that the values of the array > indeed were set for the right insns. > > Bootstrapped/regtested x86_64-pc-linux-gnu, bootstrapped on > hppa64-hp-hpux11.11 by Steve Ellcey. > > Ok for mainline? On x86_64-apple-darwin10, this causes the regression of... FAIL: gcc.c-torture/execute/arith-rand-ll.c compilation, -Os (internal compiler error) UNRESOLVED: gcc.c-torture/execute/arith-rand-ll.c execution, -Os at -m32. This backtraces as... gdb /sw/src/fink.build/gcc46-4.6.0-1000/darwin_objdir/gcc/cc1 GNU gdb 6.3.50-20050815 (Apple version gdb-1472) (Wed Jul 21 10:53:12 UTC 2010) Copyright 2004 Free Software Foundation, Inc. GDB is free software, covered by the GNU General Public License, and you are welcome to change it and/or distribute copies of it under certain conditions. Type "show copying" to see the conditions. There is absolutely no warranty for GDB. Type "show warranty" for details. This GDB was configured as "x86_64-apple-darwin"...Reading symbols for shared libraries ............. done (gdb) r -quiet -v -imultilib i386 -iprefix /sw/src/fink.build/gcc46-4.6.0-1000/darwin_objdir/gcc/../lib/gcc/x86_64-apple-darwin10.5.0/4.6.0/ -isystem /sw/src/fink.build/gcc46-4.6.0-1000/darwin_objdir/gcc/include -isystem /sw/src/fink.build/gcc46-4.6.0-1000/darwin_objdir/gcc/include-fixed -D__DYNAMIC__ /sw/src/fink.build/gcc46-4.6.0-1000/gcc-4.6-20101018/gcc/testsuite/gcc.c-torture/execute/arith-rand-ll.c -fPIC -quiet -dumpbase arith-rand-ll.c -mmacosx-version-min=10.6.5 -m32 -mtune=generic -auxbase arith-rand-ll -Os -w -version -o /var/tmp//cc5lnolJ.s Starting program: /sw/src/fink.build/gcc46-4.6.0-1000/darwin_objdir/gcc/cc1 -quiet -v -imultilib i386 -iprefix /sw/src/fink.build/gcc46-4.6.0-1000/darwin_objdir/gcc/../lib/gcc/x86_64-apple-darwin10.5.0/4.6.0/ -isystem /sw/src/fink.build/gcc46-4.6.0-1000/darwin_objdir/gcc/include -isystem /sw/src/fink.build/gcc46-4.6.0-1000/darwin_objdir/gcc/include-fixed -D__DYNAMIC__ /sw/src/fink.build/gcc46-4.6.0-1000/gcc-4.6-20101018/gcc/testsuite/gcc.c-torture/execute/arith-rand-ll.c -fPIC -quiet -dumpbase arith-rand-ll.c -mmacosx-version-min=10.6.5 -m32 -mtune=generic -auxbase arith-rand-ll -Os -w -version -o /var/tmp//cc5lnolJ.s ... Program received signal EXC_BAD_ACCESS, Could not access memory. Reason: KERN_INVALID_ADDRESS at address: 0x0000000000000018 df_ref_record (cl=DF_REF_REGULAR, collection_rec=0x0, reg=0x1435c16c0, loc=0x1435c25b0, bb=0x143411750, insn_info=0x144078bd0, ref_type=DF_REF_REG_USE, ref_flags=4096) at ../../gcc-4.6-20101018/gcc/df-scan.c:58 58 DEF_VEC_ALLOC_P_STACK(df_mw_hardreg_ptr); (gdb) bt #0 df_ref_record (cl=DF_REF_REGULAR, collection_rec=0x0, reg=0x1435c16c0, loc=0x1435c25b0, bb=0x143411750, insn_info=0x144078bd0, ref_type=DF_REF_REG_USE, ref_flags=4096) at ../../gcc-4.6-20101018/gcc/df-scan.c:58 #1 0x0000000100360b32 in df_uses_record (collection_rec=0x0, loc=<value temporarily unavailable, due to optimizations>, ref_type=DF_REF_REG_USE, bb=0x143411750, insn_info=0x144078bd0, flags=0) at ../../gcc-4.6-20101018/gcc/df-scan.c:3092 Previous frame inner to this frame (gdb could not unwind past this frame) > > Paolo > 2010-09-04 Paolo Bonzini <bonzini@gnu.org> > > * Makefile.in (fwprop.o) Add sparseset.h. > * fwprop.c: Include sparseset.h > (struct find_occurrence_data, find_occurrence_callback, > find_occurrence): Remove. > (active_defs, active_defs_check, register_active_defs): New. > (update_df): Rewrite. Use active_defs to fill in use_def_ref. > (try_fwprop_subst): Add calls to register_active_defs. Call > df_uses_create before update_df. > (fwprop_init): Allocate active_defs and active_defs_check. > (fwprop_done): Free them. > (fwprop, fwprop_addr): Adjust comments. > * df.h (df_uses_create): Declare. > * df-scan.c (df_install_ref_incremental): Break out of df_ref_create. > (df_ref_create): Return result of df_ref_create_structure directly. > (df_ref_create_structure): Call df_install_ref_incremental when > no collection_rec is passed. > (df_uses_create): New. > > Index: Makefile.in > =================================================================== > --- Makefile.in (revision 163855) > +++ Makefile.in (working copy) > @@ -3096,7 +3093,7 @@ dse.o : dse.c $(CONFIG_H) $(SYSTEM_H) co > fwprop.o : fwprop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \ > $(TOPLEV_H) $(DIAGNOSTIC_CORE_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) domwalk.h > + $(TM_P_H) $(CFGLOOP_H) $(EMIT_RTL_H) domwalk.h sparseset.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) $(DIAGNOSTIC_CORE_H) \ > insn-config.h $(RECOG_H) $(DF_H) $(OBSTACK_H) $(TIMEVAR_H) $(TREE_PASS_H) > Index: fwprop.c > =================================================================== > --- fwprop.c (revision 163855) > +++ fwprop.c (working copy) > @@ -26,6 +26,7 @@ along with GCC; see the file COPYING3. > #include "diagnostic-core.h" > #include "toplev.h" > > +#include "sparseset.h" > #include "timevar.h" > #include "rtl.h" > #include "tm_p.h" > @@ -849,87 +850,57 @@ all_uses_available_at (rtx def_insn, rtx > } > > > -struct find_occurrence_data > -{ > - rtx find; > - rtx *retval; > -}; > +static df_ref *active_defs; > +#ifdef ENABLE_CHECKING > +static sparseset active_defs_check; > +#endif > > -/* Callback for for_each_rtx, used in find_occurrence. > - See if PX is the rtx we have to find. Return 1 to stop for_each_rtx > - if successful, or 0 to continue traversing otherwise. */ > - > -static int > -find_occurrence_callback (rtx *px, void *data) > -{ > - struct find_occurrence_data *fod = (struct find_occurrence_data *) data; > - rtx x = *px; > - rtx find = fod->find; > - > - if (x == find) > - { > - fod->retval = px; > - return 1; > - } > - > - return 0; > -} > - > -/* Return a pointer to one of the occurrences of register FIND in *PX. */ > - > -static rtx * > -find_occurrence (rtx *px, rtx find) > -{ > - struct find_occurrence_data data; > - > - gcc_assert (REG_P (find) > - || (GET_CODE (find) == SUBREG > - && REG_P (SUBREG_REG (find)))); > - > - data.find = find; > - data.retval = NULL; > - for_each_rtx (px, find_occurrence_callback, &data); > - return data.retval; > -} > - > - > -/* Inside INSN, the expression rooted at *LOC has been changed, moving some > - uses from USE_VEC. Find those that are present, and create new items > - in the data flow object of the pass. Mark any new uses as having the > - given TYPE. */ > -static void > -update_df (rtx insn, rtx *loc, df_ref *use_rec, enum df_ref_type type, > - int new_flags) > -{ > - bool changed = false; > - > - /* Add a use for the registers that were propagated. */ > - while (*use_rec) > - { > - df_ref use = *use_rec; > - df_ref orig_use = use, new_use; > - rtx *new_loc = find_occurrence (loc, DF_REF_REG (orig_use)); > - use_rec++; > - > - if (!new_loc) > - continue; > - > - /* Add a new insn use. Use the original type, because it says if the > - use was within a MEM. */ > - new_use = df_ref_create (DF_REF_REG (orig_use), new_loc, > - insn, BLOCK_FOR_INSN (insn), > - type, DF_REF_FLAGS (orig_use) | new_flags); > - > - /* Set up the use-def chain. */ > - gcc_assert (DF_REF_ID (new_use) == (int) VEC_length (df_ref, use_def_ref)); > - VEC_safe_push (df_ref, heap, use_def_ref, get_def_for_use (orig_use)); > - changed = true; > - } > - if (changed) > - df_insn_rescan (insn); > +/* Update the USE_DEF_REF array for the uses in the NULL-terminated array > + USE_REC, using the active definitions in the ACTIVE_DEFS array to > + match pseudos to their def. */ > + > +static void > +update_df (df_ref *use_rec) > +{ > + /* Find defs for the new uses that were created. */ > + while (*use_rec) > + { > + df_ref use = *use_rec++; > + int regno = DF_REF_REGNO (use); > + > + /* Set up the use-def chain. */ > + if (DF_REF_ID (use) >= (int) VEC_length (df_ref, use_def_ref)) > + VEC_safe_grow_cleared (df_ref, heap, use_def_ref, > + DF_REF_ID (use) + 1); > + > +#ifdef ENABLE_CHECKING > + gcc_assert (sparseset_bit_p (active_defs_check, regno)); > +#endif > + VEC_replace (df_ref, use_def_ref, DF_REF_ID (use), active_defs[regno]); > + } > +} > + > + > +/* Fill the ACTIVE_DEFS array with the use->def link for the registers > + mentioned in USE_REC. Register the valid entries in ACTIVE_DEFS_CHECK > + too, for checking purposes. */ > + > +static void > +register_active_defs (df_ref *use_rec) > +{ > + while (*use_rec) > + { > + df_ref use = *use_rec++; > + df_ref def = get_def_for_use (use); > + int regno = DF_REF_REGNO (use); > + > +#ifdef ENABLE_CHECKING > + sparseset_set_bit (active_defs_check, regno); > +#endif > + active_defs[regno] = def; > + } > } > > - > /* Try substituting NEW into LOC, which originated from forward propagation > of USE's value from DEF_INSN. SET_REG_EQUAL says whether we are > substituting the whole SET_SRC, so we can set a REG_EQUAL note if the > @@ -940,13 +911,24 @@ static bool > try_fwprop_subst (df_ref use, rtx *loc, rtx new_rtx, rtx def_insn, bool set_reg_equal) > { > rtx insn = DF_REF_INSN (use); > - enum df_ref_type type = DF_REF_TYPE (use); > - int flags = DF_REF_FLAGS (use); > rtx set = single_set (insn); > + rtx note; > bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn)); > int old_cost = 0; > bool ok; > > + /* Build the use->def links that we use to update the dataflow info > + for new uses. Note that building the links is very cheap and if > + it were done earlier, they could be used to rule out invalid > + propagations (in addition to what is done in all_uses_available_at). > + I'm not doing this yet, though. */ > +#ifdef ENABLE_CHECKING > + sparseset_clear (active_defs_check); > +#endif > + register_active_defs (DF_INSN_USES (def_insn)); > + register_active_defs (DF_INSN_USES (insn)); > + register_active_defs (DF_INSN_EQ_USES (insn)); > + > /* forward_propagate_subreg may be operating on an instruction with > multiple sets. If so, assume the cost of the new instruction is > not greater than the old one. */ > @@ -992,12 +974,13 @@ try_fwprop_subst (df_ref use, rtx *loc, > confirm_change_group (); > num_changes++; > > - df_ref_remove (use); > if (!CONSTANT_P (new_rtx)) > { > - struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn); > - update_df (insn, loc, DF_INSN_INFO_USES (insn_info), type, flags); > - update_df (insn, loc, DF_INSN_INFO_EQ_USES (insn_info), type, flags); > + struct df_insn_info *insn_info; > + df_uses_create (&PATTERN (insn), insn, 0); > + insn_info = DF_INSN_INFO_GET (insn); > + update_df (DF_INSN_INFO_USES (insn_info)); > + update_df (DF_INSN_INFO_EQ_USES (insn_info)); > } > } > else > @@ -1011,17 +994,13 @@ try_fwprop_subst (df_ref use, rtx *loc, > if (dump_file) > fprintf (dump_file, " Setting REG_EQUAL note\n"); > > - set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx)); > - > - /* ??? Is this still necessary if we add the note through > - set_unique_reg_note? */ > - if (!CONSTANT_P (new_rtx)) > + note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx)); > + if (note && !CONSTANT_P (new_rtx)) > { > - struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn); > - update_df (insn, loc, DF_INSN_INFO_USES (insn_info), > - type, DF_REF_IN_NOTE); > - update_df (insn, loc, DF_INSN_INFO_EQ_USES (insn_info), > - type, DF_REF_IN_NOTE); > + struct df_insn_info *insn_info; > + df_uses_create (&XEXP (note, 0), insn, DF_REF_IN_NOTE); > + insn_info = DF_INSN_INFO_GET (insn); > + update_df (DF_INSN_INFO_EQ_USES (insn_info)); > } > } > } > @@ -1381,6 +1360,11 @@ fwprop_init (void) > > build_single_def_use_links (); > df_set_flags (DF_DEFER_INSN_RESCAN); > + > + active_defs = XNEWVEC (df_ref, max_reg_num ()); > +#ifdef ENABLE_CHECKING > + active_defs_check = sparseset_alloc (max_reg_num ()); > +#endif > } > > static void > @@ -1389,6 +1373,11 @@ fwprop_done (void) > loop_optimizer_finalize (); > > VEC_free (df_ref, heap, use_def_ref); > + free (active_defs); > +#ifdef ENABLE_CHECKING > + sparseset_free (active_defs_check); > +#endif > + > free_dominance_info (CDI_DOMINATORS); > cleanup_cfg (0); > delete_trivially_dead_insns (get_insns (), max_reg_num ()); > @@ -1415,7 +1404,7 @@ fwprop (void) > > fwprop_init (); > > - /* Go through all the uses. update_df will create new ones at the > + /* Go through all the uses. df_uses_create will create new ones at the > end, and we'll go through them as well. > > Do not forward propagate addresses into loops until after unrolling. > @@ -1462,7 +1451,7 @@ fwprop_addr (void) > unsigned i; > fwprop_init (); > > - /* Go through all the uses. update_df will create new ones at the > + /* Go through all the uses. df_uses_create will create new ones at the > end, and we'll go through them as well. */ > for (i = 0; i < DF_USES_TABLE_SIZE (); i++) > { > Index: df.h > =================================================================== > --- df.h (revision 163855) > +++ df.h (working copy) > @@ -981,6 +981,7 @@ extern void df_grow_insn_info (void); > extern void df_scan_blocks (void); > extern df_ref df_ref_create (rtx, rtx *, rtx,basic_block, > enum df_ref_type, int ref_flags); > +extern void df_uses_create (rtx *, rtx, int); > extern void df_ref_remove (df_ref); > extern struct df_insn_info * df_insn_create_insn_record (rtx); > extern void df_insn_delete (basic_block, unsigned int); > Index: df-scan.c > =================================================================== > --- df-scan.c (revision 163855) > +++ df-scan.c (working copy) > @@ -122,6 +122,7 @@ static void df_uses_record (struct df_co > basic_block, struct df_insn_info *, > int ref_flags); > > +static void df_install_ref_incremental (df_ref); > static df_ref df_ref_create_structure (enum df_ref_class, > struct df_collection_rec *, rtx, rtx *, > basic_block, struct df_insn_info *, > @@ -678,6 +679,19 @@ df_scan_blocks (void) > } > } > > +/* Create new refs under address LOC within INSN. This function is > + only used externally. REF_FLAGS must be either 0 or DF_REF_IN_NOTE, > + depending on whether LOC is inside PATTERN (INSN) or a note. */ > + > +void > +df_uses_create (rtx *loc, rtx insn, int ref_flags) > +{ > + gcc_assert (!(ref_flags & ~DF_REF_IN_NOTE)); > + df_uses_record (NULL, loc, DF_REF_REG_USE, > + BLOCK_FOR_INSN (insn), > + DF_INSN_INFO_GET (insn), > + ref_flags); > +} > > /* Create a new ref of type DF_REF_TYPE for register REG at address > LOC within INSN of BB. This function is only used externally. */ > @@ -688,13 +702,6 @@ df_ref_create (rtx reg, rtx *loc, rtx in > enum df_ref_type ref_type, > int ref_flags) > { > - df_ref ref; > - struct df_reg_info **reg_info; > - struct df_ref_info *ref_info; > - df_ref *ref_rec; > - df_ref **ref_rec_ptr; > - unsigned int count = 0; > - bool add_to_table; > enum df_ref_class cl; > > df_grow_reg_info (); > @@ -706,8 +713,24 @@ df_ref_create (rtx reg, rtx *loc, rtx in > cl = DF_REF_REGULAR; > else > cl = DF_REF_BASE; > - ref = df_ref_create_structure (cl, NULL, reg, loc, bb, DF_INSN_INFO_GET (insn), > - ref_type, ref_flags); > + > + return df_ref_create_structure (cl, NULL, reg, loc, bb, > + DF_INSN_INFO_GET (insn), > + ref_type, ref_flags); > +} > + > +static void > +df_install_ref_incremental (df_ref ref) > +{ > + struct df_reg_info **reg_info; > + struct df_ref_info *ref_info; > + df_ref *ref_rec; > + df_ref **ref_rec_ptr; > + unsigned int count = 0; > + bool add_to_table; > + > + rtx insn = DF_REF_INSN (ref); > + basic_block bb = BLOCK_FOR_INSN (insn); > > if (DF_REF_REG_DEF_P (ref)) > { > @@ -796,8 +819,6 @@ df_ref_create (rtx reg, rtx *loc, rtx in > to mark the block dirty ourselves. */ > if (!DEBUG_INSN_P (DF_REF_INSN (ref))) > df_set_bb_dirty (bb); > - > - return ref; > } > > > @@ -2798,6 +2819,8 @@ df_ref_create_structure (enum df_ref_cla > else > VEC_safe_push (df_ref, stack, collection_rec->use_vec, this_ref); > } > + else > + df_install_ref_incremental (this_ref); > > return this_ref; > }
On 10/18/2010 11:27 PM, Paolo Bonzini wrote: > It turns out fwprop has been incredibly broken since it's inception. :( > > Its incremental dataflow update looks at the uses in the instruction > before propagation, and creates new uses based on their presence after > propagation. But when fwprop copy propagates a pseudo into another > instruction, it misses the uses of the propagated pseudo. I find it > incredible that this never triggered in so many years. > > To fix the problem, the patch does not look at the old uses, and instead > reconstructs them using df-scan. To do this it cannot use > df_insn_rescan, because this would remove the old defs and make the > use->def links dangling. So I just created a new function df_uses_create > that scans an instruction and creates new refs like df_ref_create would > have done. > > With this in place, there is the question of how to create use->def > links for the new uses. The old way to do the updates could easily > create the links because, by knowing a correspondence from old to new > uses, it could reuse each old use's def link. > > The new scheme, instead, is based on the following observation: the new > uses can only refer to very few pseudos, those in the propagated-from > insn and those in the propagated-to insn. fwprop walks the uses in the > two insns and prepares in advance a map from pseudos to their defs. When > checking is enabled, I added assertions that the values of the array > indeed were set for the right insns. > > Bootstrapped/regtested x86_64-pc-linux-gnu, bootstrapped on > hppa64-hp-hpux11.11 by Steve Ellcey. > > Ok for mainline? PING? Paolo
> > Ok for mainline? > > PING? This is dataflow stuff IMO. Could a dataflow reviewer take a look?
Index: Makefile.in =================================================================== --- Makefile.in (revision 163855) +++ Makefile.in (working copy) @@ -3096,7 +3093,7 @@ dse.o : dse.c $(CONFIG_H) $(SYSTEM_H) co fwprop.o : fwprop.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \ $(TOPLEV_H) $(DIAGNOSTIC_CORE_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) domwalk.h + $(TM_P_H) $(CFGLOOP_H) $(EMIT_RTL_H) domwalk.h sparseset.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) $(DIAGNOSTIC_CORE_H) \ insn-config.h $(RECOG_H) $(DF_H) $(OBSTACK_H) $(TIMEVAR_H) $(TREE_PASS_H) Index: fwprop.c =================================================================== --- fwprop.c (revision 163855) +++ fwprop.c (working copy) @@ -26,6 +26,7 @@ along with GCC; see the file COPYING3. #include "diagnostic-core.h" #include "toplev.h" +#include "sparseset.h" #include "timevar.h" #include "rtl.h" #include "tm_p.h" @@ -849,87 +850,57 @@ all_uses_available_at (rtx def_insn, rtx } -struct find_occurrence_data -{ - rtx find; - rtx *retval; -}; +static df_ref *active_defs; +#ifdef ENABLE_CHECKING +static sparseset active_defs_check; +#endif -/* Callback for for_each_rtx, used in find_occurrence. - See if PX is the rtx we have to find. Return 1 to stop for_each_rtx - if successful, or 0 to continue traversing otherwise. */ - -static int -find_occurrence_callback (rtx *px, void *data) -{ - struct find_occurrence_data *fod = (struct find_occurrence_data *) data; - rtx x = *px; - rtx find = fod->find; - - if (x == find) - { - fod->retval = px; - return 1; - } - - return 0; -} - -/* Return a pointer to one of the occurrences of register FIND in *PX. */ - -static rtx * -find_occurrence (rtx *px, rtx find) -{ - struct find_occurrence_data data; - - gcc_assert (REG_P (find) - || (GET_CODE (find) == SUBREG - && REG_P (SUBREG_REG (find)))); - - data.find = find; - data.retval = NULL; - for_each_rtx (px, find_occurrence_callback, &data); - return data.retval; -} - - -/* Inside INSN, the expression rooted at *LOC has been changed, moving some - uses from USE_VEC. Find those that are present, and create new items - in the data flow object of the pass. Mark any new uses as having the - given TYPE. */ -static void -update_df (rtx insn, rtx *loc, df_ref *use_rec, enum df_ref_type type, - int new_flags) -{ - bool changed = false; - - /* Add a use for the registers that were propagated. */ - while (*use_rec) - { - df_ref use = *use_rec; - df_ref orig_use = use, new_use; - rtx *new_loc = find_occurrence (loc, DF_REF_REG (orig_use)); - use_rec++; - - if (!new_loc) - continue; - - /* Add a new insn use. Use the original type, because it says if the - use was within a MEM. */ - new_use = df_ref_create (DF_REF_REG (orig_use), new_loc, - insn, BLOCK_FOR_INSN (insn), - type, DF_REF_FLAGS (orig_use) | new_flags); - - /* Set up the use-def chain. */ - gcc_assert (DF_REF_ID (new_use) == (int) VEC_length (df_ref, use_def_ref)); - VEC_safe_push (df_ref, heap, use_def_ref, get_def_for_use (orig_use)); - changed = true; - } - if (changed) - df_insn_rescan (insn); +/* Update the USE_DEF_REF array for the uses in the NULL-terminated array + USE_REC, using the active definitions in the ACTIVE_DEFS array to + match pseudos to their def. */ + +static void +update_df (df_ref *use_rec) +{ + /* Find defs for the new uses that were created. */ + while (*use_rec) + { + df_ref use = *use_rec++; + int regno = DF_REF_REGNO (use); + + /* Set up the use-def chain. */ + if (DF_REF_ID (use) >= (int) VEC_length (df_ref, use_def_ref)) + VEC_safe_grow_cleared (df_ref, heap, use_def_ref, + DF_REF_ID (use) + 1); + +#ifdef ENABLE_CHECKING + gcc_assert (sparseset_bit_p (active_defs_check, regno)); +#endif + VEC_replace (df_ref, use_def_ref, DF_REF_ID (use), active_defs[regno]); + } +} + + +/* Fill the ACTIVE_DEFS array with the use->def link for the registers + mentioned in USE_REC. Register the valid entries in ACTIVE_DEFS_CHECK + too, for checking purposes. */ + +static void +register_active_defs (df_ref *use_rec) +{ + while (*use_rec) + { + df_ref use = *use_rec++; + df_ref def = get_def_for_use (use); + int regno = DF_REF_REGNO (use); + +#ifdef ENABLE_CHECKING + sparseset_set_bit (active_defs_check, regno); +#endif + active_defs[regno] = def; + } } - /* Try substituting NEW into LOC, which originated from forward propagation of USE's value from DEF_INSN. SET_REG_EQUAL says whether we are substituting the whole SET_SRC, so we can set a REG_EQUAL note if the @@ -940,13 +911,24 @@ static bool try_fwprop_subst (df_ref use, rtx *loc, rtx new_rtx, rtx def_insn, bool set_reg_equal) { rtx insn = DF_REF_INSN (use); - enum df_ref_type type = DF_REF_TYPE (use); - int flags = DF_REF_FLAGS (use); rtx set = single_set (insn); + rtx note; bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn)); int old_cost = 0; bool ok; + /* Build the use->def links that we use to update the dataflow info + for new uses. Note that building the links is very cheap and if + it were done earlier, they could be used to rule out invalid + propagations (in addition to what is done in all_uses_available_at). + I'm not doing this yet, though. */ +#ifdef ENABLE_CHECKING + sparseset_clear (active_defs_check); +#endif + register_active_defs (DF_INSN_USES (def_insn)); + register_active_defs (DF_INSN_USES (insn)); + register_active_defs (DF_INSN_EQ_USES (insn)); + /* forward_propagate_subreg may be operating on an instruction with multiple sets. If so, assume the cost of the new instruction is not greater than the old one. */ @@ -992,12 +974,13 @@ try_fwprop_subst (df_ref use, rtx *loc, confirm_change_group (); num_changes++; - df_ref_remove (use); if (!CONSTANT_P (new_rtx)) { - struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn); - update_df (insn, loc, DF_INSN_INFO_USES (insn_info), type, flags); - update_df (insn, loc, DF_INSN_INFO_EQ_USES (insn_info), type, flags); + struct df_insn_info *insn_info; + df_uses_create (&PATTERN (insn), insn, 0); + insn_info = DF_INSN_INFO_GET (insn); + update_df (DF_INSN_INFO_USES (insn_info)); + update_df (DF_INSN_INFO_EQ_USES (insn_info)); } } else @@ -1011,17 +994,13 @@ try_fwprop_subst (df_ref use, rtx *loc, if (dump_file) fprintf (dump_file, " Setting REG_EQUAL note\n"); - set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx)); - - /* ??? Is this still necessary if we add the note through - set_unique_reg_note? */ - if (!CONSTANT_P (new_rtx)) + note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx)); + if (note && !CONSTANT_P (new_rtx)) { - struct df_insn_info *insn_info = DF_INSN_INFO_GET (def_insn); - update_df (insn, loc, DF_INSN_INFO_USES (insn_info), - type, DF_REF_IN_NOTE); - update_df (insn, loc, DF_INSN_INFO_EQ_USES (insn_info), - type, DF_REF_IN_NOTE); + struct df_insn_info *insn_info; + df_uses_create (&XEXP (note, 0), insn, DF_REF_IN_NOTE); + insn_info = DF_INSN_INFO_GET (insn); + update_df (DF_INSN_INFO_EQ_USES (insn_info)); } } } @@ -1381,6 +1360,11 @@ fwprop_init (void) build_single_def_use_links (); df_set_flags (DF_DEFER_INSN_RESCAN); + + active_defs = XNEWVEC (df_ref, max_reg_num ()); +#ifdef ENABLE_CHECKING + active_defs_check = sparseset_alloc (max_reg_num ()); +#endif } static void @@ -1389,6 +1373,11 @@ fwprop_done (void) loop_optimizer_finalize (); VEC_free (df_ref, heap, use_def_ref); + free (active_defs); +#ifdef ENABLE_CHECKING + sparseset_free (active_defs_check); +#endif + free_dominance_info (CDI_DOMINATORS); cleanup_cfg (0); delete_trivially_dead_insns (get_insns (), max_reg_num ()); @@ -1415,7 +1404,7 @@ fwprop (void) fwprop_init (); - /* Go through all the uses. update_df will create new ones at the + /* Go through all the uses. df_uses_create will create new ones at the end, and we'll go through them as well. Do not forward propagate addresses into loops until after unrolling. @@ -1462,7 +1451,7 @@ fwprop_addr (void) unsigned i; fwprop_init (); - /* Go through all the uses. update_df will create new ones at the + /* Go through all the uses. df_uses_create will create new ones at the end, and we'll go through them as well. */ for (i = 0; i < DF_USES_TABLE_SIZE (); i++) { Index: df.h =================================================================== --- df.h (revision 163855) +++ df.h (working copy) @@ -981,6 +981,7 @@ extern void df_grow_insn_info (void); extern void df_scan_blocks (void); extern df_ref df_ref_create (rtx, rtx *, rtx,basic_block, enum df_ref_type, int ref_flags); +extern void df_uses_create (rtx *, rtx, int); extern void df_ref_remove (df_ref); extern struct df_insn_info * df_insn_create_insn_record (rtx); extern void df_insn_delete (basic_block, unsigned int); Index: df-scan.c =================================================================== --- df-scan.c (revision 163855) +++ df-scan.c (working copy) @@ -122,6 +122,7 @@ static void df_uses_record (struct df_co basic_block, struct df_insn_info *, int ref_flags); +static void df_install_ref_incremental (df_ref); static df_ref df_ref_create_structure (enum df_ref_class, struct df_collection_rec *, rtx, rtx *, basic_block, struct df_insn_info *, @@ -678,6 +679,19 @@ df_scan_blocks (void) } } +/* Create new refs under address LOC within INSN. This function is + only used externally. REF_FLAGS must be either 0 or DF_REF_IN_NOTE, + depending on whether LOC is inside PATTERN (INSN) or a note. */ + +void +df_uses_create (rtx *loc, rtx insn, int ref_flags) +{ + gcc_assert (!(ref_flags & ~DF_REF_IN_NOTE)); + df_uses_record (NULL, loc, DF_REF_REG_USE, + BLOCK_FOR_INSN (insn), + DF_INSN_INFO_GET (insn), + ref_flags); +} /* Create a new ref of type DF_REF_TYPE for register REG at address LOC within INSN of BB. This function is only used externally. */ @@ -688,13 +702,6 @@ df_ref_create (rtx reg, rtx *loc, rtx in enum df_ref_type ref_type, int ref_flags) { - df_ref ref; - struct df_reg_info **reg_info; - struct df_ref_info *ref_info; - df_ref *ref_rec; - df_ref **ref_rec_ptr; - unsigned int count = 0; - bool add_to_table; enum df_ref_class cl; df_grow_reg_info (); @@ -706,8 +713,24 @@ df_ref_create (rtx reg, rtx *loc, rtx in cl = DF_REF_REGULAR; else cl = DF_REF_BASE; - ref = df_ref_create_structure (cl, NULL, reg, loc, bb, DF_INSN_INFO_GET (insn), - ref_type, ref_flags); + + return df_ref_create_structure (cl, NULL, reg, loc, bb, + DF_INSN_INFO_GET (insn), + ref_type, ref_flags); +} + +static void +df_install_ref_incremental (df_ref ref) +{ + struct df_reg_info **reg_info; + struct df_ref_info *ref_info; + df_ref *ref_rec; + df_ref **ref_rec_ptr; + unsigned int count = 0; + bool add_to_table; + + rtx insn = DF_REF_INSN (ref); + basic_block bb = BLOCK_FOR_INSN (insn); if (DF_REF_REG_DEF_P (ref)) { @@ -796,8 +819,6 @@ df_ref_create (rtx reg, rtx *loc, rtx in to mark the block dirty ourselves. */ if (!DEBUG_INSN_P (DF_REF_INSN (ref))) df_set_bb_dirty (bb); - - return ref; } @@ -2798,6 +2819,8 @@ df_ref_create_structure (enum df_ref_cla else VEC_safe_push (df_ref, stack, collection_rec->use_vec, this_ref); } + else + df_install_ref_incremental (this_ref); return this_ref; }