From patchwork Mon Oct 18 21:27:43 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Bonzini X-Patchwork-Id: 68239 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 7C520B70E4 for ; Tue, 19 Oct 2010 08:28:03 +1100 (EST) Received: (qmail 22735 invoked by alias); 18 Oct 2010 21:28:02 -0000 Received: (qmail 22717 invoked by uid 22791); 18 Oct 2010 21:27:59 -0000 X-SWARE-Spam-Status: No, hits=-0.5 required=5.0 tests=AWL, BAYES_50, DKIM_SIGNED, DKIM_VALID, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, TW_CF, TW_FW X-Spam-Check-By: sourceware.org Received: from mail-yx0-f175.google.com (HELO mail-yx0-f175.google.com) (209.85.213.175) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 18 Oct 2010 21:27:49 +0000 Received: by yxt3 with SMTP id 3so893915yxt.20 for ; Mon, 18 Oct 2010 14:27:47 -0700 (PDT) Received: by 10.103.192.20 with SMTP id u20mr3287101mup.46.1287437267186; Mon, 18 Oct 2010 14:27:47 -0700 (PDT) Received: from yakj.usersys.redhat.com (s209p8.home.99maxprogres.cz [85.93.118.17]) by mx.google.com with ESMTPS id 2sm4521094faz.38.2010.10.18.14.27.45 (version=TLSv1/SSLv3 cipher=RC4-MD5); Mon, 18 Oct 2010 14:27:45 -0700 (PDT) Message-ID: <4CBCBBCF.2020108@gnu.org> Date: Mon, 18 Oct 2010 23:27:43 +0200 From: Paolo Bonzini User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.9) Gecko/20100907 Fedora/3.1.3-1.fc13 Lightning/1.0b3pre Mnenhy/0.8.3 Thunderbird/3.1.3 MIME-Version: 1.0 To: GCC Patches Subject: [PATCH] PR/44970, fix broken fwprop incremental dataflow Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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 * 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; }