[PATCH v2] PR44970, rewrite fwprop dataflow update
Paolo Bonzini
bonzini@gnu.org
Mon Nov 22 15:11:00 GMT 2010
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. */
>
More information about the Gcc-patches
mailing list