From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id 90A5B3858421 for ; Tue, 16 Aug 2022 09:28:55 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 90A5B3858421 Received: from relay2.suse.de (relay2.suse.de [149.44.160.134]) by smtp-out2.suse.de (Postfix) with ESMTP id 563591F86B; Tue, 16 Aug 2022 09:28:54 +0000 (UTC) Received: from wotan.suse.de (wotan.suse.de [10.160.0.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by relay2.suse.de (Postfix) with ESMTPS id 4F9982C143; Tue, 16 Aug 2022 09:28:54 +0000 (UTC) Date: Tue, 16 Aug 2022 09:28:54 +0000 (UTC) From: Richard Biener To: Aldy Hernandez cc: Andrew MacLeod , gcc-patches Subject: Re: [PATCH] Tame path_range_query::compute_imports In-Reply-To: Message-ID: References: <73820.122081107421800679@us-mta-533.us.mimecast.lan> User-Agent: Alpine 2.22 (LSU 394 2020-01-19) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-Spam-Status: No, score=-5.0 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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: Tue, 16 Aug 2022 09:28:58 -0000 On Tue, 16 Aug 2022, Aldy Hernandez wrote: > On Mon, Aug 15, 2022 at 11:53 AM Richard Biener wrote: > > > > On Thu, 11 Aug 2022, Aldy Hernandez wrote: > > > > > On Thu, Aug 11, 2022 at 3:59 PM Andrew MacLeod wrote: > > > > > > > > > > > > On 8/11/22 07:42, Richard Biener wrote: > > > > > This avoids going BBs outside of the path when adding def chains > > > > > to the set of imports. It also syncs the code with > > > > > range_def_chain::get_def_chain to not miss out on some imports > > > > > this function would identify. > > > > > > > > > > Bootstrap / regtest pending on x86_64-unknown-linux-gnu. > > > > > > > > > > The question still stands on what the path_range_query::compute_ranges > > > > > actually needs in its m_imports - at least I don't easily see how > > > > > the range-folds will use the path range cache or be path sensitive > > > > > at all. > > > > > > > > All the range folding code is in gimple_range_fold.{h,cc}, and its > > > > driven by the mystical FUR_source classes. fur_source stands for > > > > Fold_Using_Range source, and its basically just an API class which all > > > > the folding routines use to make queries. it is used by all the fold > > > > routines to ask any questions about valueizing relations, ssa name, > > > > etc.. but abstracts the actual source of the information. Its the > > > > distillation from previous incarnations where I use to pass an edge, a > > > > stmt and other stuff to each routine that it might need, and decided to > > > > abstract since it was very unwieldy. The base class requires only a > > > > range_query which is then used for all queries. > > > > > > Note that not only is ranger and path_query a range_query, so is > > > vr_values from legacy land. It all shares the same API. And the > > > simplify_using_ranges class takes a range_query, so it can work with > > > legacy or ranger, or even (untested) the path_query class. > > > > > > > > > > > Then I derive fur_stmt which is instantiated additionally with the stmt > > > > you wish to fold at, and it will perform queries using that stmt as the > > > > context source.. Any requests for ranges/relations/etc will occur as > > > > if that stmt location is the source. If folding a particular stmt, you > > > > use that stmt as the fur_stmt source. This is also how I do > > > > recalculations.. when we see > > > > bb4: > > > > a_32 = f_16 + 10 > > > > <...> > > > > bb88: > > > > if (f_16 < 20) > > > > b_8 = a_32 + 8 > > > > and there is sufficient reason to think that a_32 would have a different > > > > value , we can invoke a re-fold of a_32's defintion stmt at the use > > > > point in b_8.. using that stmt as the fur_source. Ranger will take into > > > > account the range of f_16 being [0,19] at that spot, and recalculate > > > > a_32 as [10,29]. Its expensive to do this at every use point, so we > > > > only do it if we think there is a good reason at this point. > > > > > > > > The point is that the fur_source mechanism is how we provide a context, > > > > and that class talkes care of the details of what the source actually is. > > > > > > > > There are other fur_sources.. fur_edge allows all the same questions to > > > > be answered, but using an edge as the source. Meaning we can calculate > > > > an arbitrary stmt/expressions as if it occurs on an edge. > > > > > > > > There are also a couple of specialized fur_sources.. there is an > > > > internal one in ranger which communicates some other information called > > > > fur_depend which acts like range_of_stmt, but with additional > > > > functionality to register dependencies in GORI as they are seen. > > > > > > This is a really good explanation. I think you should save it and > > > included it in the documentation when you/we get around to writing it > > > ;-). > > > > > > > > > > > Aldy overloads the fur_depend class (called jt_fur_source-- Im not sure > > > > the origination of the name) to work with the values in the path_query > > > > class. You will note that the path_range_query class inherits from a > > > > range_query, so it supports all the range_of_expr, range_of_stmt, and > > > > range_on_edge aspect of rangers API. > > > > > > The name comes from "jump thread" fur_source. I should probably > > > rename that to path_fur_source. Note that even though the full > > > range_query API is available in path_range_query, only range_of_expr > > > and range_of_stmt are supported (or tested). As I mention in the > > > comment for the class: > > > > > > // This class is a basic block path solver. Given a set of BBs > > > // indicating a path through the CFG, range_of_expr and range_of_stmt > > > // will calculate the range of an SSA or STMT as if the BBs in the > > > // path would have been executed in order. > > > > > > So using range_on_edge would probably give unexpected results, using > > > stuff in the cache as it would appear at the end of the path, or some > > > such. We could definitely harden this class and make it work solidly > > > across the entire API, but we've had no uses so far for anything but > > > range_of_expr and range_of_stmt-- and even those are only supported > > > for a range as it would appear at the end of the path. So if you call > > > range_of_expr with a statement anywhere but the end of the path, > > > you're asking for trouble. > > > > > > > > > > > I believe all attempts are first made to pick up the value from the path > > > > cache, and failing that, a query is made from ranger at the start of the > > > > path. So as the walk thru the path happens, and edges are taken/chosen, > > > > all the context information local to the path should be placed into the > > > > path cache, and used in any future queries using the path_range_query. > > > > Ranger will only be invoked if there is no entry in the path query, and > > > > it would provide the range as it would appear at entry to the path. > > > > > > > > Thats my high level understanding of how the path_query class provides > > > > context. > > > > > > That's actually a really good explanation of how it all works (or at > > > least how it's supposed to work ;-)). Thanks. > > > > Yes, thanks - that was helpful (and the general back threader stuff > > confirms what I reverse engineered). > > > > > > > > > > So I think to answer the other question, the m_imports list Is probably > > > > the list of ssa-names that may have relevant context information which > > > > the path_query would provide ranges during the walk instead of ranger? > > > > I think Aldy pre-calculates all those during the walk, and then uses > > > > this pre-filled cache to answer questions at the thread exit? Thats my > > > > guess > > > > > > Yeah, though I should probably sit down and do some testing, making > > > sure we're not adding more imports than we need to. Richi has found a > > > whole bunch of imports that ended up in the list that were ultimately > > > not needed. My original comment that adding more imports to the > > > bitmap had no penalty should be nuked-- it obviously has a performance > > > effect, especially for pathological cases. > > > > > > Regarding the name "imports". I think it's confusing all of us, > > > because GORI has a very clear definition of what imports are. OTOH, > > > the path solver starts with the imports from GORI land, but ends up > > > adding more SSA names that would be useful to solve, to provide > > > context as Andrew says. Maybe, we should call the "imports" in the > > > path solver something else to avoid confusion. Interesting names? > > > Must-be-solved? Context-SSA? Suggestions? > > > > I understand them to be path exit dependences, the 'interesting names' > > thing is already used. So maybe > > s/compute_imports/compute_exit_dependences/, this name clash did > > confuse me a bit. Though we do stop at the path entry and have > > the "path imports" in the list of dependences as well (but not > > the dependences of those imports). > > Yeah, I much prefer the exit dependencies name as it avoids confusion > and makes things clearer. > > This is what I have in mind. Do you agree? Is it clearer now? LGTM.