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 5507338618D9 for ; Mon, 26 Jul 2021 17:28:36 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 5507338618D9 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 EBB1E1FB; Mon, 26 Jul 2021 10:28:35 -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 76AE93F66F; Mon, 26 Jul 2021 10:28:35 -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 18:28:34 +0100 In-Reply-To: (Aldy Hernandez's message of "Mon, 26 Jul 2021 17:16:31 +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 17:28:39 -0000 Aldy Hernandez writes: > On Mon, Jul 26, 2021 at 4:18 PM Richard Sandiford > wrote: >> >> 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 was looking at the first statement of loop_info->block_list and one > of the dg.exp=loop-versioning* tests failed. Perhaps I should have > used the loop itself, as in the attached patch. With this patch all > of the loop-versioning tests pass. > >> >> > 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. > > If you're asking about the range_of_expr check, that's all cached, so > it should be pretty cheap. Besides, we're no longer calculating > ranges for each statement in the IL, as we were doing in lv_dom_walker > with evrp's record_ranges_from_stmt. Only statements of interest are > queried. Sounds good. If the results are already cached then another level of caching (via the second bitmap I mentioned above) would obviously be a waste of time. > How about this patch, pending tests? OK, thanks, as a strict improvement over the status quo. But it'd be even better without the dom walk :-) Richard > > Aldy > > From 8a350003d950869499d729921008abdb491d3a5e Mon Sep 17 00:00:00 2001 > From: Aldy Hernandez > Date: Sat, 24 Jul 2021 12:29:28 +0200 > Subject: [PATCH] Replace evrp use in loop versioning with ranger. > > This patch replaces the evrp_range_analyzer in the loop versioning code > with an on-demand ranger. > > Tested on x86-64 Linux. > > 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::prune_loop_conditions): Replace vr_values use > with range_query interface. > (pass_loop_versioning::execute): Use ranger. > --- > gcc/gimple-loop-versioning.cc | 44 ++++++++++++----------------------- > 1 file changed, 15 insertions(+), 29 deletions(-) > > diff --git a/gcc/gimple-loop-versioning.cc b/gcc/gimple-loop-versioning.cc > index 4b70c5a4aab..46c3a508c8d 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 *); > @@ -500,7 +494,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 +503,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. */ > > @@ -1483,18 +1463,21 @@ 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 = first_stmt (loop->header); > + > + 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 +1793,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