From: Richard Biener <rguenther@suse.de>
To: Aldy Hernandez <aldyh@redhat.com>
Cc: Andrew MacLeod <amacleod@redhat.com>,
gcc-patches <gcc-patches@gcc.gnu.org>
Subject: Re: [PATCH] Tame path_range_query::compute_imports
Date: Tue, 16 Aug 2022 09:28:54 +0000 (UTC) [thread overview]
Message-ID: <nycvar.YFH.7.77.849.2208160928470.13569@jbgna.fhfr.qr> (raw)
In-Reply-To: <CAGm3qMUWZq=HZOK53XqEmF2BywrpjTjvibpWKnimpzC9Bxgt_g@mail.gmail.com>
On Tue, 16 Aug 2022, Aldy Hernandez wrote:
> On Mon, Aug 15, 2022 at 11:53 AM Richard Biener <rguenther@suse.de> wrote:
> >
> > On Thu, 11 Aug 2022, Aldy Hernandez wrote:
> >
> > > On Thu, Aug 11, 2022 at 3:59 PM Andrew MacLeod <amacleod@redhat.com> 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.
next prev parent reply other threads:[~2022-08-16 9:28 UTC|newest]
Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <73820.122081107421800679@us-mta-533.us.mimecast.lan>
2022-08-11 13:11 ` Aldy Hernandez
2022-08-11 13:59 ` Andrew MacLeod
2022-08-11 15:11 ` Aldy Hernandez
2022-08-15 9:53 ` Richard Biener
2022-08-16 8:56 ` Aldy Hernandez
2022-08-16 9:28 ` Richard Biener [this message]
2022-08-16 10:25 ` Aldy Hernandez
2022-08-16 11:38 ` Richard Biener
2022-08-16 12:17 ` Aldy Hernandez
2022-08-16 12:26 ` Richard Biener
2022-08-16 12:32 ` Aldy Hernandez
2022-08-16 13:47 ` Andrew MacLeod
2022-08-16 13:55 ` Aldy Hernandez
2022-08-16 8:21 ` Aldy Hernandez
2022-08-16 8:32 ` Richard Biener
2022-08-16 9:08 ` Aldy Hernandez
2022-08-16 9:15 ` Aldy Hernandez
2022-08-16 9:28 ` Richard Biener
2022-08-16 13:42 ` Andrew MacLeod
2022-08-17 1:16 ` [COMMITTED] Abstract interesting ssa-names from GORI Andrew MacLeod
2022-08-17 1:18 ` Andrew MacLeod
2022-08-18 7:26 ` Aldy Hernandez
2022-08-11 11:42 [PATCH] Tame path_range_query::compute_imports Richard Biener
-- strict thread matches above, loose matches on Subject: below --
2022-08-11 11:42 Richard Biener
2022-08-11 11:42 Richard Biener
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=nycvar.YFH.7.77.849.2208160928470.13569@jbgna.fhfr.qr \
--to=rguenther@suse.de \
--cc=aldyh@redhat.com \
--cc=amacleod@redhat.com \
--cc=gcc-patches@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).