Patchwork [v2] PR44970, rewrite fwprop dataflow update

login
register
mail settings
Submitter Paolo Bonzini
Date Nov. 17, 2010, 6:24 p.m.
Message ID <1290018299-31256-1-git-send-email-bonzini@gnu.org>
Download mbox | patch
Permalink /patch/71610/
State New
Headers show

Comments

Paolo Bonzini - Nov. 17, 2010, 6:24 p.m.
It turns out fwprop has been incredibly broken since it's inception.  :(
And fwprop_into_asm too.

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.

I'm very glad I did this because it caught a problem in v1 of the patch.
Stale DF_INSN_USES were found becuse forward_propagate_asm was not
updating the data flow at all.  Luckily, the new framework makes this
additional fix trivial.

Bootstrapped/regtested x86_64-pc-linux-gnu.  v1 bootstrapped also on
hppa64-hp-hpux11.11 and hppa64-linux but failed compilation of the
Linux kernel.

Ok for mainline?

Paolo


2010-11-17  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,
        update_df_init, update_uses): New.
	(update_df): Rewrite.
	(try_fwprop_subst, forward_propagate_asm): Add calls to
	update_df_init and 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_ref_record): Do not create multiword hard reg info when no
        collection_rec is passed.
	(df_uses_create): New.
Paolo Bonzini - Nov. 22, 2010, 1:03 p.m.
On 11/17/2010 07:24 PM, Paolo Bonzini wrote:
> It turns out fwprop has been incredibly broken since it's inception.  :(
> And fwprop_into_asm too.
>
> 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.
>
> I'm very glad I did this because it caught a problem in v1 of the patch.
> Stale DF_INSN_USES were found becuse forward_propagate_asm was not
> updating the data flow at all.  Luckily, the new framework makes this
> additional fix trivial.
>
> Bootstrapped/regtested x86_64-pc-linux-gnu.  v1 bootstrapped also on
> hppa64-hp-hpux11.11 and hppa64-linux but failed compilation of the
> Linux kernel.
>
> Ok for mainline?

ping -- kenny, this fixes hppa bootstrap.

> 2010-11-17  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,
>          update_df_init, update_uses): New.
> 	(update_df): Rewrite.
> 	(try_fwprop_subst, forward_propagate_asm): Add calls to
> 	update_df_init and 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_ref_record): Do not create multiword hard reg info 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,84 +850,91 @@ 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.  */
> +/* 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 int
> -find_occurrence_callback (rtx *px, void *data)
> +static void
> +register_active_defs (df_ref *use_rec)
>   {
> -  struct find_occurrence_data *fod = (struct find_occurrence_data *) data;
> -  rtx x = *px;
> -  rtx find = fod->find;
> -
> -  if (x == find)
> +  while (*use_rec)
>       {
> -      fod->retval = px;
> -      return 1;
> -    }
> +      df_ref use = *use_rec++;
> +      df_ref def = get_def_for_use (use);
> +      int regno = DF_REF_REGNO (use);
>
> -  return 0;
> +#ifdef ENABLE_CHECKING
> +      sparseset_set_bit (active_defs_check, regno);
> +#endif
> +      active_defs[regno] = def;
> +    }
>   }
>
> -/* Return a pointer to one of the occurrences of register FIND in *PX.  */
>
> -static rtx *
> -find_occurrence (rtx *px, rtx find)
> +/* 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.  */
> +
> +static void
> +update_df_init (rtx def_insn, rtx insn)
>   {
> -  struct find_occurrence_data data;
> +#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));
> +}
>
> -  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;
> -}
> +/* Update the USE_DEF_REF array for the given use, using the active definitions
> +   in the ACTIVE_DEFS array to match pseudos to their def. */
>
> -
> -/* 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)
> +static inline void
> +update_uses (df_ref *use_rec)
>   {
> -  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++;
> +      df_ref use = *use_rec++;
> +      int regno = DF_REF_REGNO (use);
>
> -      if (!new_loc)
> -	continue;
> +      /* 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);
>
> -      /* 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);
> +#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]);
> +    }
> +}
>
> -      /* 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;
> +
> +/* Update the USE_DEF_REF array for the uses in INSN.  Only update note
> +   uses if NOTES_ONLY is true.  */
> +
> +static void
> +update_df (rtx insn, rtx note)
> +{
> +  struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
> +
> +  if (note)
> +    df_uses_create (&XEXP (note, 0), insn, DF_REF_IN_NOTE);
> +  else
> +    {
> +      df_uses_create (&PATTERN (insn), insn, 0);
> +      update_uses (DF_INSN_INFO_USES (insn_info));
>       }
> -  if (changed)
> -    df_insn_rescan (insn);
> +
> +  update_uses (DF_INSN_INFO_EQ_USES (insn_info));
>   }
>
>
> @@ -940,13 +948,14 @@ 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 = NULL_RTX;
>     bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
>     int old_cost = 0;
>     bool ok;
>
> +  update_df_init (def_insn, 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.  */
> @@ -991,14 +1000,6 @@ 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);
> -	}
>       }
>     else
>       {
> @@ -1011,21 +1012,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))
> -	    {
> -	      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);
> -	    }
> +	  note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx));
>   	}
>       }
>
> +  if ((ok || note)&&  !CONSTANT_P (new_rtx))
> +    update_df (insn, note);
> +
>     return ok;
>   }
>
> @@ -1153,6 +1146,7 @@ forward_propagate_asm (df_ref use, rtx d
>     if (use_vec[0]&&  use_vec[1])
>       return false;
>
> +  update_df_init (def_insn, use_insn);
>     speed_p = optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn));
>     asm_operands = NULL_RTX;
>     switch (GET_CODE (use_pat))
> @@ -1203,6 +1197,7 @@ forward_propagate_asm (df_ref use, rtx d
>     if (num_changes_pending () == 0 || !apply_change_group ())
>       return false;
>
> +  update_df (use_insn, NULL);
>     num_changes++;
>     return true;
>   }
> @@ -1382,6 +1377,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
> @@ -1390,6 +1390,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 ());
> @@ -1416,7 +1421,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.
> @@ -1463,7 +1468,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;
>   }
>
>
> @@ -2794,6 +2815,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;
>   }
> @@ -2837,7 +2860,8 @@ df_ref_record (enum df_ref_class cl,
>         /*  If this is a multiword hardreg, we create some extra
>   	  datastructures that will enable us to easily build REG_DEAD
>   	  and REG_UNUSED notes.  */
> -      if ((endregno != regno + 1)&&  insn_info)
> +      if (collection_rec
> +	&&  (endregno != regno + 1)&&  insn_info)
>   	{
>   	  /* Sets to a subreg of a multiword register are partial.
>   	     Sets to a non-subreg of a multiword register are not.  */
>
Kenneth Zadeck - Nov. 22, 2010, 1:39 p.m.
this is fine.

kenny

On 11/22/2010 08:03 AM, Paolo Bonzini wrote:
> On 11/17/2010 07:24 PM, Paolo Bonzini wrote:
>> It turns out fwprop has been incredibly broken since it's inception.  :(
>> And fwprop_into_asm too.
>>
>> 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.
>>
>> I'm very glad I did this because it caught a problem in v1 of the patch.
>> Stale DF_INSN_USES were found becuse forward_propagate_asm was not
>> updating the data flow at all.  Luckily, the new framework makes this
>> additional fix trivial.
>>
>> Bootstrapped/regtested x86_64-pc-linux-gnu.  v1 bootstrapped also on
>> hppa64-hp-hpux11.11 and hppa64-linux but failed compilation of the
>> Linux kernel.
>>
>> Ok for mainline?
>
> ping -- kenny, this fixes hppa bootstrap.
>
>> 2010-11-17  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,
>>          update_df_init, update_uses): New.
>>     (update_df): Rewrite.
>>     (try_fwprop_subst, forward_propagate_asm): Add calls to
>>     update_df_init and 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_ref_record): Do not create multiword hard reg info 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,84 +850,91 @@ 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.  */
>> +/* 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 int
>> -find_occurrence_callback (rtx *px, void *data)
>> +static void
>> +register_active_defs (df_ref *use_rec)
>>   {
>> -  struct find_occurrence_data *fod = (struct find_occurrence_data *) 
>> data;
>> -  rtx x = *px;
>> -  rtx find = fod->find;
>> -
>> -  if (x == find)
>> +  while (*use_rec)
>>       {
>> -      fod->retval = px;
>> -      return 1;
>> -    }
>> +      df_ref use = *use_rec++;
>> +      df_ref def = get_def_for_use (use);
>> +      int regno = DF_REF_REGNO (use);
>>
>> -  return 0;
>> +#ifdef ENABLE_CHECKING
>> +      sparseset_set_bit (active_defs_check, regno);
>> +#endif
>> +      active_defs[regno] = def;
>> +    }
>>   }
>>
>> -/* Return a pointer to one of the occurrences of register FIND in 
>> *PX.  */
>>
>> -static rtx *
>> -find_occurrence (rtx *px, rtx find)
>> +/* 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.  */
>> +
>> +static void
>> +update_df_init (rtx def_insn, rtx insn)
>>   {
>> -  struct find_occurrence_data data;
>> +#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));
>> +}
>>
>> -  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;
>> -}
>> +/* Update the USE_DEF_REF array for the given use, using the active 
>> definitions
>> +   in the ACTIVE_DEFS array to match pseudos to their def. */
>>
>> -
>> -/* 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)
>> +static inline void
>> +update_uses (df_ref *use_rec)
>>   {
>> -  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++;
>> +      df_ref use = *use_rec++;
>> +      int regno = DF_REF_REGNO (use);
>>
>> -      if (!new_loc)
>> -    continue;
>> +      /* 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);
>>
>> -      /* 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);
>> +#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]);
>> +    }
>> +}
>>
>> -      /* 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;
>> +
>> +/* Update the USE_DEF_REF array for the uses in INSN.  Only update note
>> +   uses if NOTES_ONLY is true.  */
>> +
>> +static void
>> +update_df (rtx insn, rtx note)
>> +{
>> +  struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
>> +
>> +  if (note)
>> +    df_uses_create (&XEXP (note, 0), insn, DF_REF_IN_NOTE);
>> +  else
>> +    {
>> +      df_uses_create (&PATTERN (insn), insn, 0);
>> +      update_uses (DF_INSN_INFO_USES (insn_info));
>>       }
>> -  if (changed)
>> -    df_insn_rescan (insn);
>> +
>> +  update_uses (DF_INSN_INFO_EQ_USES (insn_info));
>>   }
>>
>>
>> @@ -940,13 +948,14 @@ 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 = NULL_RTX;
>>     bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
>>     int old_cost = 0;
>>     bool ok;
>>
>> +  update_df_init (def_insn, 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.  */
>> @@ -991,14 +1000,6 @@ 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);
>> -    }
>>       }
>>     else
>>       {
>> @@ -1011,21 +1012,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))
>> -        {
>> -          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);
>> -        }
>> +      note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx));
>>       }
>>       }
>>
>> +  if ((ok || note)&&  !CONSTANT_P (new_rtx))
>> +    update_df (insn, note);
>> +
>>     return ok;
>>   }
>>
>> @@ -1153,6 +1146,7 @@ forward_propagate_asm (df_ref use, rtx d
>>     if (use_vec[0]&&  use_vec[1])
>>       return false;
>>
>> +  update_df_init (def_insn, use_insn);
>>     speed_p = optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn));
>>     asm_operands = NULL_RTX;
>>     switch (GET_CODE (use_pat))
>> @@ -1203,6 +1197,7 @@ forward_propagate_asm (df_ref use, rtx d
>>     if (num_changes_pending () == 0 || !apply_change_group ())
>>       return false;
>>
>> +  update_df (use_insn, NULL);
>>     num_changes++;
>>     return true;
>>   }
>> @@ -1382,6 +1377,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
>> @@ -1390,6 +1390,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 ());
>> @@ -1416,7 +1421,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.
>> @@ -1463,7 +1468,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;
>>   }
>>
>>
>> @@ -2794,6 +2815,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;
>>   }
>> @@ -2837,7 +2860,8 @@ df_ref_record (enum df_ref_class cl,
>>         /*  If this is a multiword hardreg, we create some extra
>>         datastructures that will enable us to easily build REG_DEAD
>>         and REG_UNUSED notes.  */
>> -      if ((endregno != regno + 1)&&  insn_info)
>> +      if (collection_rec
>> + &&  (endregno != regno + 1)&&  insn_info)
>>       {
>>         /* Sets to a subreg of a multiword register are partial.
>>            Sets to a non-subreg of a multiword register are not.  */
>>
>

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,84 +850,91 @@  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.  */
+/* 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 int
-find_occurrence_callback (rtx *px, void *data)
+static void
+register_active_defs (df_ref *use_rec)
 {
-  struct find_occurrence_data *fod = (struct find_occurrence_data *) data;
-  rtx x = *px;
-  rtx find = fod->find;
-
-  if (x == find)
+  while (*use_rec)
     {
-      fod->retval = px;
-      return 1;
-    }
+      df_ref use = *use_rec++;
+      df_ref def = get_def_for_use (use);
+      int regno = DF_REF_REGNO (use);
 
-  return 0;
+#ifdef ENABLE_CHECKING
+      sparseset_set_bit (active_defs_check, regno);
+#endif
+      active_defs[regno] = def;
+    }
 }
 
-/* Return a pointer to one of the occurrences of register FIND in *PX.  */
 
-static rtx *
-find_occurrence (rtx *px, rtx find)
+/* 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.  */
+
+static void
+update_df_init (rtx def_insn, rtx insn)
 {
-  struct find_occurrence_data data;
+#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));
+}
 
-  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;
-}
+/* Update the USE_DEF_REF array for the given use, using the active definitions
+   in the ACTIVE_DEFS array to match pseudos to their def. */
 
-
-/* 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)
+static inline void
+update_uses (df_ref *use_rec)
 {
-  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++;
+      df_ref use = *use_rec++;
+      int regno = DF_REF_REGNO (use);
 
-      if (!new_loc)
-	continue;
+      /* 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);
 
-      /* 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);
+#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]);
+    }
+}
 
-      /* 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;
+
+/* Update the USE_DEF_REF array for the uses in INSN.  Only update note
+   uses if NOTES_ONLY is true.  */
+
+static void
+update_df (rtx insn, rtx note)
+{
+  struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
+
+  if (note)
+    df_uses_create (&XEXP (note, 0), insn, DF_REF_IN_NOTE);
+  else
+    {
+      df_uses_create (&PATTERN (insn), insn, 0);
+      update_uses (DF_INSN_INFO_USES (insn_info));
     }
-  if (changed)
-    df_insn_rescan (insn);
+
+  update_uses (DF_INSN_INFO_EQ_USES (insn_info));
 }
 
 
@@ -940,13 +948,14 @@  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 = NULL_RTX;
   bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
   int old_cost = 0;
   bool ok;
 
+  update_df_init (def_insn, 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.  */
@@ -991,14 +1000,6 @@  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);
-	}
     }
   else
     {
@@ -1011,21 +1012,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))
-	    {
-	      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);
-	    }
+	  note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (new_rtx));
 	}
     }
 
+  if ((ok || note) && !CONSTANT_P (new_rtx))
+    update_df (insn, note);
+
   return ok;
 }
 
@@ -1153,6 +1146,7 @@  forward_propagate_asm (df_ref use, rtx d
   if (use_vec[0] && use_vec[1])
     return false;
 
+  update_df_init (def_insn, use_insn);
   speed_p = optimize_bb_for_speed_p (BLOCK_FOR_INSN (use_insn));
   asm_operands = NULL_RTX;
   switch (GET_CODE (use_pat))
@@ -1203,6 +1197,7 @@  forward_propagate_asm (df_ref use, rtx d
   if (num_changes_pending () == 0 || !apply_change_group ())
     return false;
 
+  update_df (use_insn, NULL);
   num_changes++;
   return true;
 }
@@ -1382,6 +1377,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
@@ -1390,6 +1390,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 ());
@@ -1416,7 +1421,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.
@@ -1463,7 +1468,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;
 }
 
 
@@ -2794,6 +2815,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;
 }
@@ -2837,7 +2860,8 @@  df_ref_record (enum df_ref_class cl,
       /*  If this is a multiword hardreg, we create some extra
 	  datastructures that will enable us to easily build REG_DEAD
 	  and REG_UNUSED notes.  */
-      if ((endregno != regno + 1) && insn_info)
+      if (collection_rec
+	  && (endregno != regno + 1) && insn_info)
 	{
 	  /* Sets to a subreg of a multiword register are partial.
 	     Sets to a non-subreg of a multiword register are not.  */