From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by sourceware.org (Postfix) with ESMTP id 583773857428 for ; Mon, 26 Jul 2021 14:18:07 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 583773857428 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 05454106F; Mon, 26 Jul 2021 07:18:07 -0700 (PDT) Received: from localhost (e121540-lin.manchester.arm.com [10.32.98.126]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 834D93F70D; Mon, 26 Jul 2021 07:18:06 -0700 (PDT) From: Richard Sandiford To: Aldy Hernandez Mail-Followup-To: Aldy Hernandez , GCC patches , richard.sandiford@arm.com Cc: GCC patches Subject: Re: [PATCH] Replace evrp use in loop versioning with ranger. References: <20210724141937.2325339-1-aldyh@redhat.com> Date: Mon, 26 Jul 2021 15:18:05 +0100 In-Reply-To: <20210724141937.2325339-1-aldyh@redhat.com> (Aldy Hernandez's message of "Sat, 24 Jul 2021 16:19:37 +0200") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain X-Spam-Status: No, score=-12.4 required=5.0 tests=BAYES_00, GIT_PATCH_0, KAM_DMARC_STATUS, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 26 Jul 2021 14:18:09 -0000 Aldy Hernandez writes: > This patch replaces the evrp_range_analyzer in the loop versioning code > with an on-demand ranger. > > Everything was pretty straightforward, except that range_of_expr requires > a gimple statement as context to provide context aware ranges. I didn't see > a convient place where the statement was saved, so I made a vector indexed > by SSA names. As an alternative, I tried to use the loop's first statement, > but that proved to be insufficient. The mapping is one-to-many though: there can be multiple statements for each SSA name. Maybe that doesn't matter in this context and any of the statements can act as a representative. I'm surprised that the loop's first statement didn't work though, since the SSA name is supposedly known to be loop-invariant. What went wrong when you tried that? > I am not familiar with loop versioning, but if the DOM walk was only > necessary for the calls to record_ranges_from_stmt, this too could be > removed as the ranger will work without it. Yeah, that was the only reason. If the information is available at version_for_unity (I guess it is) then we should just avoid recording the versioning there if so. How expensive is the check? If the result is worth caching, perhaps we should have two bitmaps: the existing one, and one that records whether we've checked a particular SSA name. If the check is relatively cheap then that won't be worth it though. Thanks, Richard > > Tested on x86-64 Linux. > > OK? > > gcc/ChangeLog: > > * gimple-loop-versioning.cc (lv_dom_walker::lv_dom_walker): Remove > use of m_range_analyzer. > (loop_versioning::lv_dom_walker::before_dom_children): Same. > (loop_versioning::lv_dom_walker::after_dom_children): Remove. > (loop_versioning::loop_versioning): Allocate space for > m_ssa_context. > (loop_versioning::version_for_unity): Set m_ssa_context. > (loop_versioning::prune_loop_conditions): Replace vr_values use > with range_query interface. > (pass_loop_versioning::execute): Use ranger. > --- > gcc/gimple-loop-versioning.cc | 49 ++++++++++++++--------------------- > 1 file changed, 20 insertions(+), 29 deletions(-) > > diff --git a/gcc/gimple-loop-versioning.cc b/gcc/gimple-loop-versioning.cc > index 4b70c5a4aab..987994d4995 100644 > --- a/gcc/gimple-loop-versioning.cc > +++ b/gcc/gimple-loop-versioning.cc > @@ -30,19 +30,17 @@ along with GCC; see the file COPYING3. If not see > #include "tree-ssa-loop.h" > #include "ssa.h" > #include "tree-scalar-evolution.h" > -#include "tree-chrec.h" > #include "tree-ssa-loop-ivopts.h" > #include "fold-const.h" > #include "tree-ssa-propagate.h" > #include "tree-inline.h" > #include "domwalk.h" > -#include "alloc-pool.h" > -#include "vr-values.h" > -#include "gimple-ssa-evrp-analyze.h" > #include "tree-vectorizer.h" > #include "omp-general.h" > #include "predict.h" > #include "tree-into-ssa.h" > +#include "gimple-range.h" > +#include "tree-cfg.h" > > namespace { > > @@ -261,14 +259,10 @@ private: > lv_dom_walker (loop_versioning &); > > edge before_dom_children (basic_block) FINAL OVERRIDE; > - void after_dom_children (basic_block) FINAL OVERRIDE; > > private: > /* The parent pass. */ > loop_versioning &m_lv; > - > - /* Used to build context-dependent range information. */ > - evrp_range_analyzer m_range_analyzer; > }; > > /* Used to simplify statements based on conditions that are established > @@ -308,7 +302,7 @@ private: > bool analyze_block (basic_block); > bool analyze_blocks (); > > - void prune_loop_conditions (class loop *, vr_values *); > + void prune_loop_conditions (class loop *); > bool prune_conditions (); > > void merge_loop_info (class loop *, class loop *); > @@ -355,6 +349,9 @@ private: > > /* A list of all addresses in M_ADDRESS_TABLE, in a predictable order. */ > auto_vec m_address_list; > + > + /* Gimple context for each SSA in loop_info::unity_names. */ > + auto_vec m_ssa_context; > }; > > /* If EXPR is an SSA name and not a default definition, return the > @@ -500,7 +497,7 @@ loop_info::worth_versioning_p () const > } > > loop_versioning::lv_dom_walker::lv_dom_walker (loop_versioning &lv) > - : dom_walker (CDI_DOMINATORS), m_lv (lv), m_range_analyzer (false) > + : dom_walker (CDI_DOMINATORS), m_lv (lv) > { > } > > @@ -509,26 +506,12 @@ loop_versioning::lv_dom_walker::lv_dom_walker (loop_versioning &lv) > edge > loop_versioning::lv_dom_walker::before_dom_children (basic_block bb) > { > - m_range_analyzer.enter (bb); > - > if (bb == bb->loop_father->header) > - m_lv.prune_loop_conditions (bb->loop_father, &m_range_analyzer); > - > - for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si); > - gsi_next (&si)) > - m_range_analyzer.record_ranges_from_stmt (gsi_stmt (si), false); > + m_lv.prune_loop_conditions (bb->loop_father); > > return NULL; > } > > -/* Process BB after processing the blocks it dominates. */ > - > -void > -loop_versioning::lv_dom_walker::after_dom_children (basic_block bb) > -{ > - m_range_analyzer.leave (bb); > -} > - > /* Decide whether to replace VAL with a new value in a versioned loop. > Return the new value if so, otherwise return null. */ > > @@ -549,6 +532,7 @@ loop_versioning::loop_versioning (function *fn) > m_num_conditions (0), > m_address_table (31) > { > + m_ssa_context.safe_grow (num_ssa_names); > bitmap_obstack_initialize (&m_bitmap_obstack); > gcc_obstack_init (&m_obstack); > > @@ -644,6 +628,8 @@ loop_versioning::version_for_unity (gimple *stmt, tree name) > if (loop_depth (li.outermost) < loop_depth (outermost)) > li.outermost = outermost; > > + m_ssa_context[SSA_NAME_VERSION(name)] = stmt; > + > if (dump_enabled_p ()) > { > dump_printf_loc (MSG_NOTE, stmt, "want to version containing loop" > @@ -1483,18 +1469,20 @@ loop_versioning::analyze_blocks () > LOOP. */ > > void > -loop_versioning::prune_loop_conditions (class loop *loop, vr_values *vrs) > +loop_versioning::prune_loop_conditions (class loop *loop) > { > loop_info &li = get_loop_info (loop); > > int to_remove = -1; > bitmap_iterator bi; > unsigned int i; > + int_range_max r; > EXECUTE_IF_SET_IN_BITMAP (&li.unity_names, 0, i, bi) > { > tree name = ssa_name (i); > - const value_range_equiv *vr = vrs->get_value_range (name); > - if (vr && !vr->may_contain_p (build_one_cst (TREE_TYPE (name)))) > + gimple *stmt = m_ssa_context[SSA_NAME_VERSION (name)]; > + if (get_range_query (cfun)->range_of_expr (r, name, stmt) > + && !r.contains_p (build_one_cst (TREE_TYPE (name)))) > { > if (dump_enabled_p ()) > dump_printf_loc (MSG_NOTE, find_loop_location (loop), > @@ -1810,7 +1798,10 @@ pass_loop_versioning::execute (function *fn) > if (number_of_loops (fn) <= 1) > return 0; > > - return loop_versioning (fn).run (); > + enable_ranger (fn); > + unsigned int ret = loop_versioning (fn).run (); > + disable_ranger (fn); > + return ret; > } > > } // anon namespace