Patchwork PR/44970, fix broken fwprop incremental dataflow

login
register
mail settings
Submitter Paolo Bonzini
Date Oct. 18, 2010, 9:27 p.m.
Message ID <4CBCBBCF.2020108@gnu.org>
Download mbox | patch
Permalink /patch/68239/
State New
Headers show

Comments

Paolo Bonzini - Oct. 18, 2010, 9:27 p.m.
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?

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.
Jack Howarth - Oct. 19, 2010, 1:28 p.m.
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;
>  }
Paolo Bonzini - Nov. 8, 2010, 12:58 p.m.
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
Eric Botcazou - Nov. 8, 2010, 6:43 p.m.
> > Ok for mainline?
>
> PING?

This is dataflow stuff IMO.  Could a dataflow reviewer take a look?

Patch

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;
 }