[PATCH] Tame path_range_query::compute_imports

[PATCH] Tame path_range_query::compute_imports

[Richard Biener]

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.

OK?

Thanks,
Richard.

	* gimple-range-path.cc (path_range_query::compute_imports):
	Restrict walking SSA defs to blocks inside the path.  Track
	the same operands as range_def_chain::get_def_chain does.
---
 gcc/gimple-range-path.cc | 39 ++++++++++++++++++++++++++++-----------
 1 file changed, 28 insertions(+), 11 deletions(-)

diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 5ae374df3a2..5ff2c733b4e 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -575,18 +575,11 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
     {
       tree name = worklist.pop ();
       gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+      if (SSA_NAME_IS_DEFAULT_DEF (name)
+	  || !path.contains (gimple_bb (def_stmt)))
+	continue;
 
-      if (is_gimple_assign (def_stmt))
-	{
-	  add_to_imports (gimple_assign_rhs1 (def_stmt), imports);
-	  tree rhs = gimple_assign_rhs2 (def_stmt);
-	  if (rhs && add_to_imports (rhs, imports))
-	    worklist.safe_push (rhs);
-	  rhs = gimple_assign_rhs3 (def_stmt);
-	  if (rhs && add_to_imports (rhs, imports))
-	    worklist.safe_push (rhs);
-	}
-      else if (gphi *phi = dyn_cast <gphi *> (def_stmt))
+      if (gphi *phi = dyn_cast <gphi *> (def_stmt))
 	{
 	  for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
 	    {
@@ -599,6 +592,30 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
 		worklist.safe_push (arg);
 	    }
 	}
+      else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
+	{
+	  tree ssa[3];
+	  if (range_op_handler (ass))
+	    {
+	      ssa[0] = gimple_range_ssa_p (gimple_range_operand1 (ass));
+	      ssa[1] = gimple_range_ssa_p (gimple_range_operand2 (ass));
+	      ssa[2] = NULL_TREE;
+	    }
+	  else if (gimple_assign_rhs_code (ass) == COND_EXPR)
+	    {
+	      ssa[0] = gimple_range_ssa_p (gimple_assign_rhs1 (ass));
+	      ssa[1] = gimple_range_ssa_p (gimple_assign_rhs2 (ass));
+	      ssa[2] = gimple_range_ssa_p (gimple_assign_rhs3 (ass));
+	    }
+	  else
+	    continue;
+	  for (unsigned j = 0; j < 3; ++j)
+	    {
+	      tree rhs = ssa[j];
+	      if (rhs && add_to_imports (rhs, imports))
+		worklist.safe_push (rhs);
+	    }
+	}
     }
   // Exported booleans along the path, may help conditionals.
   if (m_resolve)
-- 
2.35.3

Re: [PATCH] Tame path_range_query::compute_imports

[Aldy Hernandez]

On Tue, Aug 16, 2022 at 3:48 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
>
> On 8/16/22 06:25, Aldy Hernandez wrote:
> > On Mon, Aug 15, 2022 at 11:53 AM Richard Biener <rguenther@suse.de> wrote:
> >> The remaining issue I have with the path_range_query is that
> >> we re-use the same instance in the back threader but the
> >> class doesn't provide any way to "restart", aka give m_path
> >> a lifetime.  The "start a new path" API seems to essentially
> >> be compute_ranges (), but there's no convenient way to end.
> >> It might be more appropriate to re-instantiate the path_range_query,
> >> though that comes at a cost.  Or abstract an actual query, like
> >> adding a
> > Yes, compute_ranges() is the way to start a new path.  It resets exit
> > dependencies, the path, relations, etc.  I think it would be clearer
> > to name it set_path (or reset_path if we want to share nomenclature
> > with the path_oracle).
> >
> > Instantiating a new path_range_query per path is fine, as long as you
> > allocate the ranger it uses yourself, instead of letting
> > path_range_query allocate it.  Instantiating a new ranger does have a
> > cost, and it's best to let path_range_query re-use a ranger from path
> > to path.  This is why path_range_query is (class) global in the
> > backwards threader.  Andrew mentioned last year making the ranger
> > start-up 0-cost, but it still leaves the internal caching the ranger
> > will do from path to path (well, the stuff outside the current path,
> > cause the stuff inside the path is irrelevant since it'll get
> > recalculated).
>
> Yes, you will want to have one instance of ranger regardless... just
> pass it to whatever/however many other instances you want to build paths
> from.
>
> Ranger itself is primarily to provide range-on-entry to the path.
> Trying to use it for values within the path would bring in values
> outside the path as it doesnt understand you have selected on certain
> edges along the way.
>
> The GORI engine within ranger can be utilized within the path because
> GORI never looks outside the basic block being asked about, other than
> thru the range-query that is provided to it. SO its perfectly safe to
> use within the path.
>
> As both GORI and ranger cache things and share the def chains, its far
> more efficient to have a global instance that is just utilized.   Even a
> zero-cost start up would incur costs as it recalculates the same things
> over and over

I forgot about the def chains.  That should be fine however, since we
use the gori from within the ranger that got passed down.

Aldy

Re: [PATCH] Tame path_range_query::compute_imports

[Andrew MacLeod]

On 8/16/22 06:25, Aldy Hernandez wrote:
> On Mon, Aug 15, 2022 at 11:53 AM Richard Biener <rguenther@suse.de> wrote:
>> The remaining issue I have with the path_range_query is that
>> we re-use the same instance in the back threader but the
>> class doesn't provide any way to "restart", aka give m_path
>> a lifetime.  The "start a new path" API seems to essentially
>> be compute_ranges (), but there's no convenient way to end.
>> It might be more appropriate to re-instantiate the path_range_query,
>> though that comes at a cost.  Or abstract an actual query, like
>> adding a
> Yes, compute_ranges() is the way to start a new path.  It resets exit
> dependencies, the path, relations, etc.  I think it would be clearer
> to name it set_path (or reset_path if we want to share nomenclature
> with the path_oracle).
>
> Instantiating a new path_range_query per path is fine, as long as you
> allocate the ranger it uses yourself, instead of letting
> path_range_query allocate it.  Instantiating a new ranger does have a
> cost, and it's best to let path_range_query re-use a ranger from path
> to path.  This is why path_range_query is (class) global in the
> backwards threader.  Andrew mentioned last year making the ranger
> start-up 0-cost, but it still leaves the internal caching the ranger
> will do from path to path (well, the stuff outside the current path,
> cause the stuff inside the path is irrelevant since it'll get
> recalculated).

Yes, you will want to have one instance of ranger regardless... just 
pass it to whatever/however many other instances you want to build paths 
from.

Ranger itself is primarily to provide range-on-entry to the path.  
Trying to use it for values within the path would bring in values 
outside the path as it doesnt understand you have selected on certain 
edges along the way.

The GORI engine within ranger can be utilized within the path because 
GORI never looks outside the basic block being asked about, other than 
thru the range-query that is provided to it. SO its perfectly safe to 
use within the path.

As both GORI and ranger cache things and share the def chains, its far 
more efficient to have a global instance that is just utilized.   Even a 
zero-cost start up would incur costs as it recalculates the same things 
over and over


Andrew

Re: [PATCH] Tame path_range_query::compute_imports

[Andrew MacLeod]

On 8/16/22 05:28, Richard Biener wrote:
> On Tue, 16 Aug 2022, Aldy Hernandez wrote:
>
>> On Tue, Aug 16, 2022 at 11:08 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>>> On Tue, Aug 16, 2022 at 10:32 AM Richard Biener <rguenther@suse.de> wrote:
>>>> On Tue, 16 Aug 2022, Aldy Hernandez wrote:
>>>>
>>>>> On Thu, Aug 11, 2022 at 1:42 PM Richard Biener <rguenther@suse.de> wrote:
>>>>>
>>>>>> @@ -599,6 +592,30 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
>>>>>>                  worklist.safe_push (arg);
>>>>>>              }
>>>>>>          }
>>>>>> +      else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
>>>>>> +       {
>>>>>> +         tree ssa[3];
>>>>>> +         if (range_op_handler (ass))
>>>>>> +           {
>>>>>> +             ssa[0] = gimple_range_ssa_p (gimple_range_operand1 (ass));
>>>>>> +             ssa[1] = gimple_range_ssa_p (gimple_range_operand2 (ass));
>>>>>> +             ssa[2] = NULL_TREE;
>>>>>> +           }
>>>>>> +         else if (gimple_assign_rhs_code (ass) == COND_EXPR)
>>>>>> +           {
>>>>>> +             ssa[0] = gimple_range_ssa_p (gimple_assign_rhs1 (ass));
>>>>>> +             ssa[1] = gimple_range_ssa_p (gimple_assign_rhs2 (ass));
>>>>>> +             ssa[2] = gimple_range_ssa_p (gimple_assign_rhs3 (ass));
>>>>>> +           }
>>>>>> +         else
>>>>>> +           continue;
>>>>>> +         for (unsigned j = 0; j < 3; ++j)
>>>>>> +           {
>>>>>> +             tree rhs = ssa[j];
>>>>>> +             if (rhs && add_to_imports (rhs, imports))
>>>>>> +               worklist.safe_push (rhs);
>>>>>> +           }
>>>>>> +       }
>>>>> We seem to have 3 copies of this copy now: this one, the
>>>>> threadbackward one, and the original one.
>>>>>
>>>>> Could we abstract this somehow?
>>>> I've thought about this but didn't find any good solution since the
>>>> use of the operands is always a bit different.  But I was wondering
>>>> why/if the COND_EXPR special-casing is necessary, that is, why
>>>> don't we have a range_op_handler for it and if we don't why
>>>> do we care about it?

Simply that range-ops is defined as always being one or 2 use operands. 
everything is streamlined for those common cases.  There is no support 
in the API for a 3rd field. All non-conforming stmts are "unique" and 
thus require some level of specialization.  I am not aware of any other 
3 operand stmt we would care about, so at the time it seemed easier to 
leave cond-expr as a specialization, in theory localized.

as for the abstraction, its easy enough to provide a routine which will 
take a vector and fill it with ssa_names we might care about on the 
stmt.. then each caller can do their own little specialized bit.  I 
never expected for that sequence to become common place :-)

>>> I think it's because we don't have a range-op handler for COND_EXPR,
>>> opting to handle the relational operators instead in range-ops.  We
>>> have similar code in the folder:
>>>
>>>    if (range_op_handler (s))
>>>      res = range_of_range_op (r, s, src);
>>>    else if (is_a<gphi *>(s))
>>>      res = range_of_phi (r, as_a<gphi *> (s), src);
>>>    else if (is_a<gcall *>(s))
>>>      res = range_of_call (r, as_a<gcall *> (s), src);
>>>    else if (is_a<gassign *> (s) && gimple_assign_rhs_code (s) == COND_EXPR)
>>>      res = range_of_cond_expr (r, as_a<gassign *> (s), src);
>>>
>>> Andrew, do you have any suggestions here?
>> Hmmm, so thinking about this, perhaps special casing it is the way to go ??
> It looks like so.  Though a range_op_handler could, for
> _1 = _2 ? _3 : _4; derive a range for _3 from _1 if _2 is
> known true?
>
the fold_using_range class does this for the forward direction, and my 
intention (just havent gotten to it yet), was to add similar 
specialization in GORI rather than expanding range-ops just for the one 
stmt... in much the same way that range_of_cond_expr works.

It should be localized to gori_compute::compute_operand_range () , where:

  range_op_handler handler(stmt);
   if (!handler)
     return false;

before returning, we check if its a COND_EXPR, and if so, call a 
specialized compute routine to look at the various operands and invoke 
any continued operand ranges as approriate.    It should be quite trivial..

   I'll take a look at adding COND_EXPR to GORI, and privoide that 
routine somewhere.. probably as a function as part of 
gimple-range-fold.h so it can potentially apply to any stmt.

Andrew

Re: [PATCH] Tame path_range_query::compute_imports

[Aldy Hernandez]

On Tue, Aug 16, 2022, 14:26 Richard Biener <rguenther@suse.de> wrote:

> On Tue, 16 Aug 2022, Aldy Hernandez wrote:
>
> > On Tue, Aug 16, 2022 at 1:38 PM Richard Biener <rguenther@suse.de>
> wrote:
> > >
> > > On Tue, 16 Aug 2022, Aldy Hernandez wrote:
> > >
> > > > On Mon, Aug 15, 2022 at 11:53 AM Richard Biener <rguenther@suse.de>
> wrote:
> > > > >
> > > > > The remaining issue I have with the path_range_query is that
> > > > > we re-use the same instance in the back threader but the
> > > > > class doesn't provide any way to "restart", aka give m_path
> > > > > a lifetime.  The "start a new path" API seems to essentially
> > > > > be compute_ranges (), but there's no convenient way to end.
> > > > > It might be more appropriate to re-instantiate the
> path_range_query,
> > > > > though that comes at a cost.  Or abstract an actual query, like
> > > > > adding a
> > > >
> > > > Yes, compute_ranges() is the way to start a new path.  It resets exit
> > > > dependencies, the path, relations, etc.  I think it would be clearer
> > > > to name it set_path (or reset_path if we want to share nomenclature
> > > > with the path_oracle).
> > > >
> > > > Instantiating a new path_range_query per path is fine, as long as you
> > > > allocate the ranger it uses yourself, instead of letting
> > > > path_range_query allocate it.  Instantiating a new ranger does have a
> > > > cost, and it's best to let path_range_query re-use a ranger from path
> > > > to path.  This is why path_range_query is (class) global in the
> > > > backwards threader.  Andrew mentioned last year making the ranger
> > > > start-up 0-cost, but it still leaves the internal caching the ranger
> > > > will do from path to path (well, the stuff outside the current path,
> > > > cause the stuff inside the path is irrelevant since it'll get
> > > > recalculated).
> > > >
> > > > However, why can't you use compute_ranges (or whatever we rename it
> to ;-))??
> > >
> > > I've added
> > >
> > >    auto_bb_flag m_on_path;
> > >
> > > to the path query and at set_path time set m_on_path on each BB so
> > > the m_path->contains () linear walks go away.  But I need to clear
> > > the flag for which I would need something like finish_path (),
> > > doing it just at the point we deallocate the path query object
> > > or when we set the next path via compute_ranges doesn't look right
> > > (and in fact it doesn't work out-of-the-box without adjusting the
> > > lifetime of the path query object).
> > >
> > > So a more incremental thing would be to add such finish_path ()
> > > or to make the whole path query object single-shot, thus remove
> > > compute_ranges and instead use the CTOR for this.
> > >
> > > Probably not too important (for short paths).
> >
> > On a high level, I wonder if this matters since we don't allow long
> > paths for other performance reasons you've already tackled.  But OTOH,
> > I've always been a little uncomfortable with contains_p linear search,
> > so if you think this makes a difference, go right ahead :).
> >
> > I'm fine with either the finish_path() or the single-shot thing you
> > speak of.  Although making path query inmutable makes things cleaner
> > in the long run.  I like it!  My guess is that the non-ranger
> > instantiation penalty would be minimal.  I'd even remove the default
> > (auto-allocated) ranger from path_range_query, to make it obvious that
> > you need to manage that yourself and avoid folks shooting themselves
> > in the foot.
>
> We currently have
>
> path_range_query::path_range_query (bool resolve, gimple_ranger *ranger)
>   : m_cache (new ssa_global_cache),
>     m_has_cache_entry (BITMAP_ALLOC (NULL)),
>     m_resolve (resolve),
>     m_alloced_ranger (!ranger)
> {
>   if (m_alloced_ranger)
>     m_ranger = new gimple_ranger;
>   else
>     m_ranger = ranger;
>
>   m_oracle = new path_oracle (m_ranger->oracle ());
>
>   if (m_resolve && flag_checking)
>     verify_marked_backedges (cfun);
> }
>
> so at least verify_marked_backedges will explode, I suppose we
> want to hoist that somehow ...
>

Good point.


> then we allocate the path_oracle - that one does have a
> reset_path () function at least.  It's allocation looks
> quite harmless, but we should only need it when m_resolve?
>

Yes.


> > Wanna have a go at it?  If you'd rather not, I can work on it.
>
> If you have cycles go ahead - I'm fiddling with other parts of
> the threader right now.
>

Sure, I'll take a stab at it. Thanks for the other stuff you're doing on
the threader.

Aldy


> Richard.
>
>

Re: [PATCH] Tame path_range_query::compute_imports

[Richard Biener]

On Tue, 16 Aug 2022, Aldy Hernandez wrote:

> On Tue, Aug 16, 2022 at 1:38 PM Richard Biener <rguenther@suse.de> wrote:
> >
> > On Tue, 16 Aug 2022, Aldy Hernandez wrote:
> >
> > > On Mon, Aug 15, 2022 at 11:53 AM Richard Biener <rguenther@suse.de> wrote:
> > > >
> > > > The remaining issue I have with the path_range_query is that
> > > > we re-use the same instance in the back threader but the
> > > > class doesn't provide any way to "restart", aka give m_path
> > > > a lifetime.  The "start a new path" API seems to essentially
> > > > be compute_ranges (), but there's no convenient way to end.
> > > > It might be more appropriate to re-instantiate the path_range_query,
> > > > though that comes at a cost.  Or abstract an actual query, like
> > > > adding a
> > >
> > > Yes, compute_ranges() is the way to start a new path.  It resets exit
> > > dependencies, the path, relations, etc.  I think it would be clearer
> > > to name it set_path (or reset_path if we want to share nomenclature
> > > with the path_oracle).
> > >
> > > Instantiating a new path_range_query per path is fine, as long as you
> > > allocate the ranger it uses yourself, instead of letting
> > > path_range_query allocate it.  Instantiating a new ranger does have a
> > > cost, and it's best to let path_range_query re-use a ranger from path
> > > to path.  This is why path_range_query is (class) global in the
> > > backwards threader.  Andrew mentioned last year making the ranger
> > > start-up 0-cost, but it still leaves the internal caching the ranger
> > > will do from path to path (well, the stuff outside the current path,
> > > cause the stuff inside the path is irrelevant since it'll get
> > > recalculated).
> > >
> > > However, why can't you use compute_ranges (or whatever we rename it to ;-))??
> >
> > I've added
> >
> >    auto_bb_flag m_on_path;
> >
> > to the path query and at set_path time set m_on_path on each BB so
> > the m_path->contains () linear walks go away.  But I need to clear
> > the flag for which I would need something like finish_path (),
> > doing it just at the point we deallocate the path query object
> > or when we set the next path via compute_ranges doesn't look right
> > (and in fact it doesn't work out-of-the-box without adjusting the
> > lifetime of the path query object).
> >
> > So a more incremental thing would be to add such finish_path ()
> > or to make the whole path query object single-shot, thus remove
> > compute_ranges and instead use the CTOR for this.
> >
> > Probably not too important (for short paths).
> 
> On a high level, I wonder if this matters since we don't allow long
> paths for other performance reasons you've already tackled.  But OTOH,
> I've always been a little uncomfortable with contains_p linear search,
> so if you think this makes a difference, go right ahead :).
> 
> I'm fine with either the finish_path() or the single-shot thing you
> speak of.  Although making path query inmutable makes things cleaner
> in the long run.  I like it!  My guess is that the non-ranger
> instantiation penalty would be minimal.  I'd even remove the default
> (auto-allocated) ranger from path_range_query, to make it obvious that
> you need to manage that yourself and avoid folks shooting themselves
> in the foot.

We currently have

path_range_query::path_range_query (bool resolve, gimple_ranger *ranger)
  : m_cache (new ssa_global_cache),
    m_has_cache_entry (BITMAP_ALLOC (NULL)),
    m_resolve (resolve),
    m_alloced_ranger (!ranger)
{
  if (m_alloced_ranger)
    m_ranger = new gimple_ranger;
  else
    m_ranger = ranger;

  m_oracle = new path_oracle (m_ranger->oracle ());

  if (m_resolve && flag_checking)
    verify_marked_backedges (cfun);
}

so at least verify_marked_backedges will explode, I suppose we
want to hoist that somehow ...

then we allocate the path_oracle - that one does have a
reset_path () function at least.  It's allocation looks
quite harmless, but we should only need it when m_resolve?

> Wanna have a go at it?  If you'd rather not, I can work on it.

If you have cycles go ahead - I'm fiddling with other parts of
the threader right now.

Richard.

Re: [PATCH] Tame path_range_query::compute_imports

[Aldy Hernandez]

On Tue, Aug 16, 2022 at 1:38 PM Richard Biener <rguenther@suse.de> wrote:
>
> On Tue, 16 Aug 2022, Aldy Hernandez wrote:
>
> > On Mon, Aug 15, 2022 at 11:53 AM Richard Biener <rguenther@suse.de> wrote:
> > >
> > > The remaining issue I have with the path_range_query is that
> > > we re-use the same instance in the back threader but the
> > > class doesn't provide any way to "restart", aka give m_path
> > > a lifetime.  The "start a new path" API seems to essentially
> > > be compute_ranges (), but there's no convenient way to end.
> > > It might be more appropriate to re-instantiate the path_range_query,
> > > though that comes at a cost.  Or abstract an actual query, like
> > > adding a
> >
> > Yes, compute_ranges() is the way to start a new path.  It resets exit
> > dependencies, the path, relations, etc.  I think it would be clearer
> > to name it set_path (or reset_path if we want to share nomenclature
> > with the path_oracle).
> >
> > Instantiating a new path_range_query per path is fine, as long as you
> > allocate the ranger it uses yourself, instead of letting
> > path_range_query allocate it.  Instantiating a new ranger does have a
> > cost, and it's best to let path_range_query re-use a ranger from path
> > to path.  This is why path_range_query is (class) global in the
> > backwards threader.  Andrew mentioned last year making the ranger
> > start-up 0-cost, but it still leaves the internal caching the ranger
> > will do from path to path (well, the stuff outside the current path,
> > cause the stuff inside the path is irrelevant since it'll get
> > recalculated).
> >
> > However, why can't you use compute_ranges (or whatever we rename it to ;-))??
>
> I've added
>
>    auto_bb_flag m_on_path;
>
> to the path query and at set_path time set m_on_path on each BB so
> the m_path->contains () linear walks go away.  But I need to clear
> the flag for which I would need something like finish_path (),
> doing it just at the point we deallocate the path query object
> or when we set the next path via compute_ranges doesn't look right
> (and in fact it doesn't work out-of-the-box without adjusting the
> lifetime of the path query object).
>
> So a more incremental thing would be to add such finish_path ()
> or to make the whole path query object single-shot, thus remove
> compute_ranges and instead use the CTOR for this.
>
> Probably not too important (for short paths).

On a high level, I wonder if this matters since we don't allow long
paths for other performance reasons you've already tackled.  But OTOH,
I've always been a little uncomfortable with contains_p linear search,
so if you think this makes a difference, go right ahead :).

I'm fine with either the finish_path() or the single-shot thing you
speak of.  Although making path query inmutable makes things cleaner
in the long run.  I like it!  My guess is that the non-ranger
instantiation penalty would be minimal.  I'd even remove the default
(auto-allocated) ranger from path_range_query, to make it obvious that
you need to manage that yourself and avoid folks shooting themselves
in the foot.

Wanna have a go at it?  If you'd rather not, I can work on it.

Aldy

Re: [PATCH] Tame path_range_query::compute_imports

[Richard Biener]

On Tue, 16 Aug 2022, Aldy Hernandez wrote:

> On Mon, Aug 15, 2022 at 11:53 AM Richard Biener <rguenther@suse.de> wrote:
> >
> > The remaining issue I have with the path_range_query is that
> > we re-use the same instance in the back threader but the
> > class doesn't provide any way to "restart", aka give m_path
> > a lifetime.  The "start a new path" API seems to essentially
> > be compute_ranges (), but there's no convenient way to end.
> > It might be more appropriate to re-instantiate the path_range_query,
> > though that comes at a cost.  Or abstract an actual query, like
> > adding a
> 
> Yes, compute_ranges() is the way to start a new path.  It resets exit
> dependencies, the path, relations, etc.  I think it would be clearer
> to name it set_path (or reset_path if we want to share nomenclature
> with the path_oracle).
> 
> Instantiating a new path_range_query per path is fine, as long as you
> allocate the ranger it uses yourself, instead of letting
> path_range_query allocate it.  Instantiating a new ranger does have a
> cost, and it's best to let path_range_query re-use a ranger from path
> to path.  This is why path_range_query is (class) global in the
> backwards threader.  Andrew mentioned last year making the ranger
> start-up 0-cost, but it still leaves the internal caching the ranger
> will do from path to path (well, the stuff outside the current path,
> cause the stuff inside the path is irrelevant since it'll get
> recalculated).
> 
> However, why can't you use compute_ranges (or whatever we rename it to ;-))??

I've added

   auto_bb_flag m_on_path;

to the path query and at set_path time set m_on_path on each BB so
the m_path->contains () linear walks go away.  But I need to clear
the flag for which I would need something like finish_path (),
doing it just at the point we deallocate the path query object
or when we set the next path via compute_ranges doesn't look right
(and in fact it doesn't work out-of-the-box without adjusting the
lifetime of the path query object).

So a more incremental thing would be to add such finish_path ()
or to make the whole path query object single-shot, thus remove
compute_ranges and instead use the CTOR for this.

Probably not too important (for short paths).

Richard.

> Aldy
> 
> >
> >   query start (const vec<basic_block> &);
> >
> > and make range_of_* and friends members of a new 'query' class
> > instantiated by path_range_query.  I ran into this when trying
> > to axe the linear array walks for the .contains() query on the
> > path where I need a convenient way to "clenanup" after a path
> > query is done.
> >
> > Richard.
> >

Re: [PATCH] Tame path_range_query::compute_imports

[Aldy Hernandez]

On Mon, Aug 15, 2022 at 11:53 AM Richard Biener <rguenther@suse.de> wrote:
>
> The remaining issue I have with the path_range_query is that
> we re-use the same instance in the back threader but the
> class doesn't provide any way to "restart", aka give m_path
> a lifetime.  The "start a new path" API seems to essentially
> be compute_ranges (), but there's no convenient way to end.
> It might be more appropriate to re-instantiate the path_range_query,
> though that comes at a cost.  Or abstract an actual query, like
> adding a

Yes, compute_ranges() is the way to start a new path.  It resets exit
dependencies, the path, relations, etc.  I think it would be clearer
to name it set_path (or reset_path if we want to share nomenclature
with the path_oracle).

Instantiating a new path_range_query per path is fine, as long as you
allocate the ranger it uses yourself, instead of letting
path_range_query allocate it.  Instantiating a new ranger does have a
cost, and it's best to let path_range_query re-use a ranger from path
to path.  This is why path_range_query is (class) global in the
backwards threader.  Andrew mentioned last year making the ranger
start-up 0-cost, but it still leaves the internal caching the ranger
will do from path to path (well, the stuff outside the current path,
cause the stuff inside the path is irrelevant since it'll get
recalculated).

However, why can't you use compute_ranges (or whatever we rename it to ;-))??

Aldy

>
>   query start (const vec<basic_block> &);
>
> and make range_of_* and friends members of a new 'query' class
> instantiated by path_range_query.  I ran into this when trying
> to axe the linear array walks for the .contains() query on the
> path where I need a convenient way to "clenanup" after a path
> query is done.
>
> Richard.
>

Re: [PATCH] Tame path_range_query::compute_imports

[Richard Biener]

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.

Re: [PATCH] Tame path_range_query::compute_imports

[Richard Biener]

On Tue, 16 Aug 2022, Aldy Hernandez wrote:

> On Tue, Aug 16, 2022 at 11:08 AM Aldy Hernandez <aldyh@redhat.com> wrote:
> >
> > On Tue, Aug 16, 2022 at 10:32 AM Richard Biener <rguenther@suse.de> wrote:
> > >
> > > On Tue, 16 Aug 2022, Aldy Hernandez wrote:
> > >
> > > > On Thu, Aug 11, 2022 at 1:42 PM Richard Biener <rguenther@suse.de> wrote:
> > > >
> > > > > @@ -599,6 +592,30 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
> > > > >                 worklist.safe_push (arg);
> > > > >             }
> > > > >         }
> > > > > +      else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
> > > > > +       {
> > > > > +         tree ssa[3];
> > > > > +         if (range_op_handler (ass))
> > > > > +           {
> > > > > +             ssa[0] = gimple_range_ssa_p (gimple_range_operand1 (ass));
> > > > > +             ssa[1] = gimple_range_ssa_p (gimple_range_operand2 (ass));
> > > > > +             ssa[2] = NULL_TREE;
> > > > > +           }
> > > > > +         else if (gimple_assign_rhs_code (ass) == COND_EXPR)
> > > > > +           {
> > > > > +             ssa[0] = gimple_range_ssa_p (gimple_assign_rhs1 (ass));
> > > > > +             ssa[1] = gimple_range_ssa_p (gimple_assign_rhs2 (ass));
> > > > > +             ssa[2] = gimple_range_ssa_p (gimple_assign_rhs3 (ass));
> > > > > +           }
> > > > > +         else
> > > > > +           continue;
> > > > > +         for (unsigned j = 0; j < 3; ++j)
> > > > > +           {
> > > > > +             tree rhs = ssa[j];
> > > > > +             if (rhs && add_to_imports (rhs, imports))
> > > > > +               worklist.safe_push (rhs);
> > > > > +           }
> > > > > +       }
> > > >
> > > > We seem to have 3 copies of this copy now: this one, the
> > > > threadbackward one, and the original one.
> > > >
> > > > Could we abstract this somehow?
> > >
> > > I've thought about this but didn't find any good solution since the
> > > use of the operands is always a bit different.  But I was wondering
> > > why/if the COND_EXPR special-casing is necessary, that is, why
> > > don't we have a range_op_handler for it and if we don't why
> > > do we care about it?
> >
> > I think it's because we don't have a range-op handler for COND_EXPR,
> > opting to handle the relational operators instead in range-ops.  We
> > have similar code in the folder:
> >
> >   if (range_op_handler (s))
> >     res = range_of_range_op (r, s, src);
> >   else if (is_a<gphi *>(s))
> >     res = range_of_phi (r, as_a<gphi *> (s), src);
> >   else if (is_a<gcall *>(s))
> >     res = range_of_call (r, as_a<gcall *> (s), src);
> >   else if (is_a<gassign *> (s) && gimple_assign_rhs_code (s) == COND_EXPR)
> >     res = range_of_cond_expr (r, as_a<gassign *> (s), src);
> >
> > Andrew, do you have any suggestions here?
> 
> Hmmm, so thinking about this, perhaps special casing it is the way to go ??

It looks like so.  Though a range_op_handler could, for
_1 = _2 ? _3 : _4; derive a range for _3 from _1 if _2 is
known true?

Re: [PATCH] Tame path_range_query::compute_imports

[Aldy Hernandez]

On Tue, Aug 16, 2022 at 11:08 AM Aldy Hernandez <aldyh@redhat.com> wrote:
>
> On Tue, Aug 16, 2022 at 10:32 AM Richard Biener <rguenther@suse.de> wrote:
> >
> > On Tue, 16 Aug 2022, Aldy Hernandez wrote:
> >
> > > On Thu, Aug 11, 2022 at 1:42 PM Richard Biener <rguenther@suse.de> wrote:
> > >
> > > > @@ -599,6 +592,30 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
> > > >                 worklist.safe_push (arg);
> > > >             }
> > > >         }
> > > > +      else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
> > > > +       {
> > > > +         tree ssa[3];
> > > > +         if (range_op_handler (ass))
> > > > +           {
> > > > +             ssa[0] = gimple_range_ssa_p (gimple_range_operand1 (ass));
> > > > +             ssa[1] = gimple_range_ssa_p (gimple_range_operand2 (ass));
> > > > +             ssa[2] = NULL_TREE;
> > > > +           }
> > > > +         else if (gimple_assign_rhs_code (ass) == COND_EXPR)
> > > > +           {
> > > > +             ssa[0] = gimple_range_ssa_p (gimple_assign_rhs1 (ass));
> > > > +             ssa[1] = gimple_range_ssa_p (gimple_assign_rhs2 (ass));
> > > > +             ssa[2] = gimple_range_ssa_p (gimple_assign_rhs3 (ass));
> > > > +           }
> > > > +         else
> > > > +           continue;
> > > > +         for (unsigned j = 0; j < 3; ++j)
> > > > +           {
> > > > +             tree rhs = ssa[j];
> > > > +             if (rhs && add_to_imports (rhs, imports))
> > > > +               worklist.safe_push (rhs);
> > > > +           }
> > > > +       }
> > >
> > > We seem to have 3 copies of this copy now: this one, the
> > > threadbackward one, and the original one.
> > >
> > > Could we abstract this somehow?
> >
> > I've thought about this but didn't find any good solution since the
> > use of the operands is always a bit different.  But I was wondering
> > why/if the COND_EXPR special-casing is necessary, that is, why
> > don't we have a range_op_handler for it and if we don't why
> > do we care about it?
>
> I think it's because we don't have a range-op handler for COND_EXPR,
> opting to handle the relational operators instead in range-ops.  We
> have similar code in the folder:
>
>   if (range_op_handler (s))
>     res = range_of_range_op (r, s, src);
>   else if (is_a<gphi *>(s))
>     res = range_of_phi (r, as_a<gphi *> (s), src);
>   else if (is_a<gcall *>(s))
>     res = range_of_call (r, as_a<gcall *> (s), src);
>   else if (is_a<gassign *> (s) && gimple_assign_rhs_code (s) == COND_EXPR)
>     res = range_of_cond_expr (r, as_a<gassign *> (s), src);
>
> Andrew, do you have any suggestions here?

Hmmm, so thinking about this, perhaps special casing it is the way to go ??

Re: [PATCH] Tame path_range_query::compute_imports

[Aldy Hernandez]

On Tue, Aug 16, 2022 at 10:32 AM Richard Biener <rguenther@suse.de> wrote:
>
> On Tue, 16 Aug 2022, Aldy Hernandez wrote:
>
> > On Thu, Aug 11, 2022 at 1:42 PM Richard Biener <rguenther@suse.de> wrote:
> >
> > > @@ -599,6 +592,30 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
> > >                 worklist.safe_push (arg);
> > >             }
> > >         }
> > > +      else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
> > > +       {
> > > +         tree ssa[3];
> > > +         if (range_op_handler (ass))
> > > +           {
> > > +             ssa[0] = gimple_range_ssa_p (gimple_range_operand1 (ass));
> > > +             ssa[1] = gimple_range_ssa_p (gimple_range_operand2 (ass));
> > > +             ssa[2] = NULL_TREE;
> > > +           }
> > > +         else if (gimple_assign_rhs_code (ass) == COND_EXPR)
> > > +           {
> > > +             ssa[0] = gimple_range_ssa_p (gimple_assign_rhs1 (ass));
> > > +             ssa[1] = gimple_range_ssa_p (gimple_assign_rhs2 (ass));
> > > +             ssa[2] = gimple_range_ssa_p (gimple_assign_rhs3 (ass));
> > > +           }
> > > +         else
> > > +           continue;
> > > +         for (unsigned j = 0; j < 3; ++j)
> > > +           {
> > > +             tree rhs = ssa[j];
> > > +             if (rhs && add_to_imports (rhs, imports))
> > > +               worklist.safe_push (rhs);
> > > +           }
> > > +       }
> >
> > We seem to have 3 copies of this copy now: this one, the
> > threadbackward one, and the original one.
> >
> > Could we abstract this somehow?
>
> I've thought about this but didn't find any good solution since the
> use of the operands is always a bit different.  But I was wondering
> why/if the COND_EXPR special-casing is necessary, that is, why
> don't we have a range_op_handler for it and if we don't why
> do we care about it?

I think it's because we don't have a range-op handler for COND_EXPR,
opting to handle the relational operators instead in range-ops.  We
have similar code in the folder:

  if (range_op_handler (s))
    res = range_of_range_op (r, s, src);
  else if (is_a<gphi *>(s))
    res = range_of_phi (r, as_a<gphi *> (s), src);
  else if (is_a<gcall *>(s))
    res = range_of_call (r, as_a<gcall *> (s), src);
  else if (is_a<gassign *> (s) && gimple_assign_rhs_code (s) == COND_EXPR)
    res = range_of_cond_expr (r, as_a<gassign *> (s), src);

Andrew, do you have any suggestions here?

Aldy

Re: [PATCH] Tame path_range_query::compute_imports

[Aldy Hernandez]

[-- Attachment #1: Type: text/plain, Size: 7855 bytes --]

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?

Aldy

[-- Attachment #2: 0001-Rename-imports-nomenclature-in-path_range_query-to-e.patch --]
[-- Type: text/x-patch, Size: 11247 bytes --]

From 48e97240a5255ffd72dca8d2c23937029aff882b Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <aldyh@redhat.com>
Date: Tue, 16 Aug 2022 10:52:37 +0200
Subject: [PATCH] Rename imports nomenclature in path_range_query to
 exit_dependencies.

The purpose of this change is to disambiguate the imports name with
its use in GORI.

gcc/ChangeLog:

	* gimple-range-path.cc (path_range_query::import_p): Rename to...
	(path_range_query::exit_dependency_p): ...this.
	(path_range_query::dump): Rename imports to exit dependencies.
	(path_range_query::compute_ranges_in_phis): Same.
	(path_range_query::compute_ranges_in_block): Same.
	(path_range_query::adjust_for_non_null_uses): Same.
	(path_range_query::compute_ranges): Same.
	(path_range_query::compute_phi_relations): Same.
	(path_range_query::add_to_imports): Rename to...
	(path_range_query::add_to_exit_dependencies): ...this.
	(path_range_query::compute_imports): Rename to...
	(path_range_query::compute_exit_dependencies): ...this.
	* gimple-range-path.h (class path_range_query): Rename imports to
	exit dependencies.
---
 gcc/gimple-range-path.cc | 79 +++++++++++++++++++---------------------
 gcc/gimple-range-path.h  | 19 +++++++---
 2 files changed, 51 insertions(+), 47 deletions(-)

diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 78146f5683e..c99d77dd340 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -62,13 +62,13 @@ path_range_query::~path_range_query ()
   delete m_cache;
 }
 
-// Return TRUE if NAME is in the import bitmap.
+// Return TRUE if NAME is an exit depenency for the path.
 
 bool
-path_range_query::import_p (tree name)
+path_range_query::exit_dependency_p (tree name)
 {
   return (TREE_CODE (name) == SSA_NAME
-	  && bitmap_bit_p (m_imports, SSA_NAME_VERSION (name)));
+	  && bitmap_bit_p (m_exit_dependencies, SSA_NAME_VERSION (name)));
 }
 
 // Mark cache entry for NAME as unused.
@@ -118,8 +118,8 @@ path_range_query::dump (FILE *dump_file)
 
   dump_ranger (dump_file, m_path);
 
-  fprintf (dump_file, "Imports:\n");
-  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+  fprintf (dump_file, "Exit dependencies:\n");
+  EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
     {
       tree name = ssa_name (i);
       print_generic_expr (dump_file, name, TDF_SLIM);
@@ -356,7 +356,7 @@ path_range_query::compute_ranges_in_phis (basic_block bb)
       gphi *phi = iter.phi ();
       tree name = gimple_phi_result (phi);
 
-      if (!import_p (name))
+      if (!exit_dependency_p (name))
 	continue;
 
       Value_Range r (TREE_TYPE (name));
@@ -400,17 +400,17 @@ path_range_query::compute_ranges_in_block (basic_block bb)
 
   // Force recalculation of any names in the cache that are defined in
   // this block.  This can happen on interdependent SSA/phis in loops.
-  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+  EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
     {
       tree name = ssa_name (i);
       if (ssa_defined_in_bb (name, bb))
 	clear_cache (name);
     }
 
-  // Solve imports defined in this block, starting with the PHIs...
+  // Solve dependencies defined in this block, starting with the PHIs...
   compute_ranges_in_phis (bb);
-  // ...and then the rest of the imports.
-  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+  // ...and then the rest of the dependencies.
+  EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
     {
       tree name = ssa_name (i);
       Value_Range r (TREE_TYPE (name));
@@ -423,7 +423,7 @@ path_range_query::compute_ranges_in_block (basic_block bb)
   if (at_exit ())
     return;
 
-  // Solve imports that are exported to the next block.
+  // Solve dependencies that are exported to the next block.
   basic_block next = next_bb ();
   edge e = find_edge (bb, next);
 
@@ -444,7 +444,7 @@ path_range_query::compute_ranges_in_block (basic_block bb)
 
   gori_compute &g = m_ranger->gori ();
   bitmap exports = g.exports (bb);
-  EXECUTE_IF_AND_IN_BITMAP (m_imports, exports, 0, i, bi)
+  EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi)
     {
       tree name = ssa_name (i);
       Value_Range r (TREE_TYPE (name));
@@ -472,7 +472,7 @@ path_range_query::compute_ranges_in_block (basic_block bb)
     compute_outgoing_relations (bb, next);
 }
 
-// Adjust all pointer imports in BB with non-null information.
+// Adjust all pointer exit dependencies in BB with non-null information.
 
 void
 path_range_query::adjust_for_non_null_uses (basic_block bb)
@@ -481,7 +481,7 @@ path_range_query::adjust_for_non_null_uses (basic_block bb)
   bitmap_iterator bi;
   unsigned i;
 
-  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+  EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
     {
       tree name = ssa_name (i);
 
@@ -501,39 +501,33 @@ path_range_query::adjust_for_non_null_uses (basic_block bb)
     }
 }
 
-// If NAME is a supported SSA_NAME, add it the bitmap in IMPORTS.
+// If NAME is a supported SSA_NAME, add it to the bitmap in dependencies.
 
 bool
-path_range_query::add_to_imports (tree name, bitmap imports)
+path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies)
 {
   if (TREE_CODE (name) == SSA_NAME
       && Value_Range::supports_type_p (TREE_TYPE (name)))
-    return bitmap_set_bit (imports, SSA_NAME_VERSION (name));
+    return bitmap_set_bit (dependencies, SSA_NAME_VERSION (name));
   return false;
 }
 
-// Compute the imports to PATH.  These are
-// essentially the SSA names used to calculate the final conditional
-// along the path.
-//
-// They are hints for the solver.  Adding more elements doesn't slow
-// us down, because we don't solve anything that doesn't appear in the
-// path.  On the other hand, not having enough imports will limit what
-// we can solve.
+// Compute the exit dependencies to PATH.  These are essentially the
+// SSA names used to calculate the final conditional along the path.
 
 void
-path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
+path_range_query::compute_exit_dependencies (bitmap dependencies,
+					     const vec<basic_block> &path)
 {
   // Start with the imports from the exit block...
   basic_block exit = path[0];
   gori_compute &gori = m_ranger->gori ();
-  bitmap r_imports = gori.imports (exit);
-  bitmap_copy (imports, r_imports);
+  bitmap_copy (dependencies, gori.imports (exit));
 
-  auto_vec<tree> worklist (bitmap_count_bits (imports));
+  auto_vec<tree> worklist (bitmap_count_bits (dependencies));
   bitmap_iterator bi;
   unsigned i;
-  EXECUTE_IF_SET_IN_BITMAP (imports, 0, i, bi)
+  EXECUTE_IF_SET_IN_BITMAP (dependencies, 0, i, bi)
     {
       tree name = ssa_name (i);
       worklist.quick_push (name);
@@ -557,7 +551,7 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
 
 	      if (TREE_CODE (arg) == SSA_NAME
 		  && path.contains (e->src)
-		  && bitmap_set_bit (imports, SSA_NAME_VERSION (arg)))
+		  && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg)))
 		worklist.safe_push (arg);
 	    }
 	}
@@ -581,7 +575,7 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
 	  for (unsigned j = 0; j < 3; ++j)
 	    {
 	      tree rhs = ssa[j];
-	      if (rhs && add_to_imports (rhs, imports))
+	      if (rhs && add_to_exit_dependencies (rhs, dependencies))
 		worklist.safe_push (rhs);
 	    }
 	}
@@ -594,19 +588,20 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
 	tree name;
 	FOR_EACH_GORI_EXPORT_NAME (gori, bb, name)
 	  if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE)
-	    bitmap_set_bit (imports, SSA_NAME_VERSION (name));
+	    bitmap_set_bit (dependencies, SSA_NAME_VERSION (name));
       }
 }
 
-// Compute the ranges for IMPORTS along PATH.
+// Compute the ranges for DEPENDENCIES along PATH.
 //
-// IMPORTS are the set of SSA names, any of which could potentially
-// change the value of the final conditional in PATH.  Default to the
-// imports of the last block in the path if none is given.
+// DEPENDENCIES are path exit dependencies.  They are the set of SSA
+// names, any of which could potentially change the value of the final
+// conditional in PATH.  If none is given, the exit dependencies are
+// calculated from the final conditional in the path.
 
 void
 path_range_query::compute_ranges (const vec<basic_block> &path,
-				  const bitmap_head *imports)
+				  const bitmap_head *dependencies)
 {
   if (DEBUG_SOLVER)
     fprintf (dump_file, "\n==============================================\n");
@@ -614,10 +609,10 @@ path_range_query::compute_ranges (const vec<basic_block> &path,
   set_path (path);
   m_undefined_path = false;
 
-  if (imports)
-    bitmap_copy (m_imports, imports);
+  if (dependencies)
+    bitmap_copy (m_exit_dependencies, dependencies);
   else
-    compute_imports (m_imports, m_path);
+    compute_exit_dependencies (m_exit_dependencies, m_path);
 
   if (m_resolve)
     get_path_oracle ()->reset_path ();
@@ -809,7 +804,7 @@ path_range_query::compute_phi_relations (basic_block bb, basic_block prev)
       tree result = gimple_phi_result (phi);
       unsigned nargs = gimple_phi_num_args (phi);
 
-      if (!import_p (result))
+      if (!exit_dependency_p (result))
 	continue;
 
       for (size_t i = 0; i < nargs; ++i)
diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
index e783e00b2f5..3cb794e34a9 100644
--- a/gcc/gimple-range-path.h
+++ b/gcc/gimple-range-path.h
@@ -35,9 +35,10 @@ public:
   path_range_query (bool resolve = true, class gimple_ranger *ranger = NULL);
   virtual ~path_range_query ();
   void compute_ranges (const vec<basic_block> &,
-		       const bitmap_head *imports = NULL);
+		       const bitmap_head *dependencies = NULL);
   void compute_ranges (edge e);
-  void compute_imports (bitmap imports, const vec<basic_block> &);
+  void compute_exit_dependencies (bitmap dependencies,
+				  const vec<basic_block> &);
   bool range_of_expr (vrange &r, tree name, gimple * = NULL) override;
   bool range_of_stmt (vrange &r, gimple *, tree name = NULL) override;
   bool unreachable_path_p ();
@@ -64,8 +65,8 @@ private:
   void compute_outgoing_relations (basic_block bb, basic_block next);
   void compute_phi_relations (basic_block bb, basic_block prev);
   void maybe_register_phi_relation (gphi *, edge e);
-  bool add_to_imports (tree name, bitmap imports);
-  bool import_p (tree name);
+  bool add_to_exit_dependencies (tree name, bitmap dependencies);
+  bool exit_dependency_p (tree name);
   bool ssa_defined_in_bb (tree name, basic_block bb);
   bool relations_may_be_invalidated (edge);
 
@@ -89,7 +90,15 @@ private:
   // Path being analyzed.
   auto_vec<basic_block> m_path;
 
-  auto_bitmap m_imports;
+  // This is a list of SSA names that may have relevant context
+  // information for solving the final conditional along the path.
+  // Ranges for these SSA names are pre-calculated and cached during a
+  // top-down traversal of the path, and are then used to answer
+  // questions at the path exit.
+  auto_bitmap m_exit_dependencies;
+
+  // A ranger used to resolve ranges for SSA names whose values come
+  // from outside the path.
   gimple_ranger *m_ranger;
 
   // Current path position.
-- 
2.37.1

Re: [PATCH] Tame path_range_query::compute_imports

[Richard Biener]

On Tue, 16 Aug 2022, Aldy Hernandez wrote:

> On Thu, Aug 11, 2022 at 1:42 PM Richard Biener <rguenther@suse.de> wrote:
> 
> > @@ -599,6 +592,30 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
> >                 worklist.safe_push (arg);
> >             }
> >         }
> > +      else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
> > +       {
> > +         tree ssa[3];
> > +         if (range_op_handler (ass))
> > +           {
> > +             ssa[0] = gimple_range_ssa_p (gimple_range_operand1 (ass));
> > +             ssa[1] = gimple_range_ssa_p (gimple_range_operand2 (ass));
> > +             ssa[2] = NULL_TREE;
> > +           }
> > +         else if (gimple_assign_rhs_code (ass) == COND_EXPR)
> > +           {
> > +             ssa[0] = gimple_range_ssa_p (gimple_assign_rhs1 (ass));
> > +             ssa[1] = gimple_range_ssa_p (gimple_assign_rhs2 (ass));
> > +             ssa[2] = gimple_range_ssa_p (gimple_assign_rhs3 (ass));
> > +           }
> > +         else
> > +           continue;
> > +         for (unsigned j = 0; j < 3; ++j)
> > +           {
> > +             tree rhs = ssa[j];
> > +             if (rhs && add_to_imports (rhs, imports))
> > +               worklist.safe_push (rhs);
> > +           }
> > +       }
> 
> We seem to have 3 copies of this copy now: this one, the
> threadbackward one, and the original one.
> 
> Could we abstract this somehow?

I've thought about this but didn't find any good solution since the
use of the operands is always a bit different.  But I was wondering
why/if the COND_EXPR special-casing is necessary, that is, why
don't we have a range_op_handler for it and if we don't why
do we care about it?

Richard.

Re: [PATCH] Tame path_range_query::compute_imports

[Aldy Hernandez]

On Thu, Aug 11, 2022 at 1:42 PM Richard Biener <rguenther@suse.de> wrote:

> @@ -599,6 +592,30 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
>                 worklist.safe_push (arg);
>             }
>         }
> +      else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
> +       {
> +         tree ssa[3];
> +         if (range_op_handler (ass))
> +           {
> +             ssa[0] = gimple_range_ssa_p (gimple_range_operand1 (ass));
> +             ssa[1] = gimple_range_ssa_p (gimple_range_operand2 (ass));
> +             ssa[2] = NULL_TREE;
> +           }
> +         else if (gimple_assign_rhs_code (ass) == COND_EXPR)
> +           {
> +             ssa[0] = gimple_range_ssa_p (gimple_assign_rhs1 (ass));
> +             ssa[1] = gimple_range_ssa_p (gimple_assign_rhs2 (ass));
> +             ssa[2] = gimple_range_ssa_p (gimple_assign_rhs3 (ass));
> +           }
> +         else
> +           continue;
> +         for (unsigned j = 0; j < 3; ++j)
> +           {
> +             tree rhs = ssa[j];
> +             if (rhs && add_to_imports (rhs, imports))
> +               worklist.safe_push (rhs);
> +           }
> +       }

We seem to have 3 copies of this copy now: this one, the
threadbackward one, and the original one.

Could we abstract this somehow?

Aldy

Re: [PATCH] Tame path_range_query::compute_imports

[Richard Biener]

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).

The remaining issue I have with the path_range_query is that
we re-use the same instance in the back threader but the
class doesn't provide any way to "restart", aka give m_path
a lifetime.  The "start a new path" API seems to essentially
be compute_ranges (), but there's no convenient way to end.
It might be more appropriate to re-instantiate the path_range_query,
though that comes at a cost.  Or abstract an actual query, like
adding a

  query start (const vec<basic_block> &);

and make range_of_* and friends members of a new 'query' class
instantiated by path_range_query.  I ran into this when trying
to axe the linear array walks for the .contains() query on the
path where I need a convenient way to "clenanup" after a path
query is done.

Richard.

Re: [PATCH] Tame path_range_query::compute_imports

[Aldy Hernandez]

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.

>
> 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?

Aldy

Re: [PATCH] Tame path_range_query::compute_imports

[Andrew MacLeod]

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.

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.

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.

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.

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

> K?
>
> Thanks,
> Richard.
>
> 	* gimple-range-path.cc (path_range_query::compute_imports):
> 	Restrict walking SSA defs to blocks inside the path.  Track
> 	the same operands as range_def_chain::get_def_chain does.
> ---
>   gcc/gimple-range-path.cc | 39 ++++++++++++++++++++++++++++-----------
>   1 file changed, 28 insertions(+), 11 deletions(-)
>
> diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
> index 5ae374df3a2..5ff2c733b4e 100644
> --- a/gcc/gimple-range-path.cc
> +++ b/gcc/gimple-range-path.cc
> @@ -575,18 +575,11 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
>       {
>         tree name = worklist.pop ();
>         gimple *def_stmt = SSA_NAME_DEF_STMT (name);
> +      if (SSA_NAME_IS_DEFAULT_DEF (name)
> +	  || !path.contains (gimple_bb (def_stmt)))
> +	continue;
>   
> -      if (is_gimple_assign (def_stmt))
> -	{
> -	  add_to_imports (gimple_assign_rhs1 (def_stmt), imports);
> -	  tree rhs = gimple_assign_rhs2 (def_stmt);
> -	  if (rhs && add_to_imports (rhs, imports))
> -	    worklist.safe_push (rhs);
> -	  rhs = gimple_assign_rhs3 (def_stmt);
> -	  if (rhs && add_to_imports (rhs, imports))
> -	    worklist.safe_push (rhs);
> -	}
> -      else if (gphi *phi = dyn_cast <gphi *> (def_stmt))
> +      if (gphi *phi = dyn_cast <gphi *> (def_stmt))
>   	{
>   	  for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
>   	    {
> @@ -599,6 +592,30 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
>   		worklist.safe_push (arg);
>   	    }
>   	}
> +      else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
> +	{
> +	  tree ssa[3];
> +	  if (range_op_handler (ass))
> +	    {
> +	      ssa[0] = gimple_range_ssa_p (gimple_range_operand1 (ass));
> +	      ssa[1] = gimple_range_ssa_p (gimple_range_operand2 (ass));
> +	      ssa[2] = NULL_TREE;
> +	    }
> +	  else if (gimple_assign_rhs_code (ass) == COND_EXPR)
> +	    {
> +	      ssa[0] = gimple_range_ssa_p (gimple_assign_rhs1 (ass));
> +	      ssa[1] = gimple_range_ssa_p (gimple_assign_rhs2 (ass));
> +	      ssa[2] = gimple_range_ssa_p (gimple_assign_rhs3 (ass));
> +	    }
> +	  else
> +	    continue;
> +	  for (unsigned j = 0; j < 3; ++j)
> +	    {
> +	      tree rhs = ssa[j];
> +	      if (rhs && add_to_imports (rhs, imports))
> +		worklist.safe_push (rhs);
> +	    }
> +	}
>       }
>     // Exported booleans along the path, may help conditionals.
>     if (m_resolve)

Re: [PATCH] Tame path_range_query::compute_imports

[Aldy Hernandez]

OK

On Thu, Aug 11, 2022, 13:42 Richard Biener <rguenther@suse.de> 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.
>
> OK?
>
> Thanks,
> Richard.
>
>         * gimple-range-path.cc (path_range_query::compute_imports):
>         Restrict walking SSA defs to blocks inside the path.  Track
>         the same operands as range_def_chain::get_def_chain does.
> ---
>  gcc/gimple-range-path.cc | 39 ++++++++++++++++++++++++++++-----------
>  1 file changed, 28 insertions(+), 11 deletions(-)
>
> diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
> index 5ae374df3a2..5ff2c733b4e 100644
> --- a/gcc/gimple-range-path.cc
> +++ b/gcc/gimple-range-path.cc
> @@ -575,18 +575,11 @@ path_range_query::compute_imports (bitmap imports,
> const vec<basic_block> &path)
>      {
>        tree name = worklist.pop ();
>        gimple *def_stmt = SSA_NAME_DEF_STMT (name);
> +      if (SSA_NAME_IS_DEFAULT_DEF (name)
> +         || !path.contains (gimple_bb (def_stmt)))
> +       continue;
>
> -      if (is_gimple_assign (def_stmt))
> -       {
> -         add_to_imports (gimple_assign_rhs1 (def_stmt), imports);
> -         tree rhs = gimple_assign_rhs2 (def_stmt);
> -         if (rhs && add_to_imports (rhs, imports))
> -           worklist.safe_push (rhs);
> -         rhs = gimple_assign_rhs3 (def_stmt);
> -         if (rhs && add_to_imports (rhs, imports))
> -           worklist.safe_push (rhs);
> -       }
> -      else if (gphi *phi = dyn_cast <gphi *> (def_stmt))
> +      if (gphi *phi = dyn_cast <gphi *> (def_stmt))
>         {
>           for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
>             {
> @@ -599,6 +592,30 @@ path_range_query::compute_imports (bitmap imports,
> const vec<basic_block> &path)
>                 worklist.safe_push (arg);
>             }
>         }
> +      else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
> +       {
> +         tree ssa[3];
> +         if (range_op_handler (ass))
> +           {
> +             ssa[0] = gimple_range_ssa_p (gimple_range_operand1 (ass));
> +             ssa[1] = gimple_range_ssa_p (gimple_range_operand2 (ass));
> +             ssa[2] = NULL_TREE;
> +           }
> +         else if (gimple_assign_rhs_code (ass) == COND_EXPR)
> +           {
> +             ssa[0] = gimple_range_ssa_p (gimple_assign_rhs1 (ass));
> +             ssa[1] = gimple_range_ssa_p (gimple_assign_rhs2 (ass));
> +             ssa[2] = gimple_range_ssa_p (gimple_assign_rhs3 (ass));
> +           }
> +         else
> +           continue;
> +         for (unsigned j = 0; j < 3; ++j)
> +           {
> +             tree rhs = ssa[j];
> +             if (rhs && add_to_imports (rhs, imports))
> +               worklist.safe_push (rhs);
> +           }
> +       }
>      }
>    // Exported booleans along the path, may help conditionals.
>    if (m_resolve)
> --
> 2.35.3
>
>

[PATCH] Tame path_range_query::compute_imports

[Richard Biener]

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.

OK?

Thanks,
Richard.

	* gimple-range-path.cc (path_range_query::compute_imports):
	Restrict walking SSA defs to blocks inside the path.  Track
	the same operands as range_def_chain::get_def_chain does.
---
 gcc/gimple-range-path.cc | 39 ++++++++++++++++++++++++++++-----------
 1 file changed, 28 insertions(+), 11 deletions(-)

diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 5ae374df3a2..5ff2c733b4e 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -575,18 +575,11 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
     {
       tree name = worklist.pop ();
       gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+      if (SSA_NAME_IS_DEFAULT_DEF (name)
+	  || !path.contains (gimple_bb (def_stmt)))
+	continue;
 
-      if (is_gimple_assign (def_stmt))
-	{
-	  add_to_imports (gimple_assign_rhs1 (def_stmt), imports);
-	  tree rhs = gimple_assign_rhs2 (def_stmt);
-	  if (rhs && add_to_imports (rhs, imports))
-	    worklist.safe_push (rhs);
-	  rhs = gimple_assign_rhs3 (def_stmt);
-	  if (rhs && add_to_imports (rhs, imports))
-	    worklist.safe_push (rhs);
-	}
-      else if (gphi *phi = dyn_cast <gphi *> (def_stmt))
+      if (gphi *phi = dyn_cast <gphi *> (def_stmt))
 	{
 	  for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
 	    {
@@ -599,6 +592,30 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
 		worklist.safe_push (arg);
 	    }
 	}
+      else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
+	{
+	  tree ssa[3];
+	  if (range_op_handler (ass))
+	    {
+	      ssa[0] = gimple_range_ssa_p (gimple_range_operand1 (ass));
+	      ssa[1] = gimple_range_ssa_p (gimple_range_operand2 (ass));
+	      ssa[2] = NULL_TREE;
+	    }
+	  else if (gimple_assign_rhs_code (ass) == COND_EXPR)
+	    {
+	      ssa[0] = gimple_range_ssa_p (gimple_assign_rhs1 (ass));
+	      ssa[1] = gimple_range_ssa_p (gimple_assign_rhs2 (ass));
+	      ssa[2] = gimple_range_ssa_p (gimple_assign_rhs3 (ass));
+	    }
+	  else
+	    continue;
+	  for (unsigned j = 0; j < 3; ++j)
+	    {
+	      tree rhs = ssa[j];
+	      if (rhs && add_to_imports (rhs, imports))
+		worklist.safe_push (rhs);
+	    }
+	}
     }
   // Exported booleans along the path, may help conditionals.
   if (m_resolve)
-- 
2.35.3

[PATCH] Tame path_range_query::compute_imports

[Richard Biener]

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.

OK?

Thanks,
Richard.

	* gimple-range-path.cc (path_range_query::compute_imports):
	Restrict walking SSA defs to blocks inside the path.  Track
	the same operands as range_def_chain::get_def_chain does.
---
 gcc/gimple-range-path.cc | 39 ++++++++++++++++++++++++++++-----------
 1 file changed, 28 insertions(+), 11 deletions(-)

diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 5ae374df3a2..5ff2c733b4e 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -575,18 +575,11 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
     {
       tree name = worklist.pop ();
       gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+      if (SSA_NAME_IS_DEFAULT_DEF (name)
+	  || !path.contains (gimple_bb (def_stmt)))
+	continue;
 
-      if (is_gimple_assign (def_stmt))
-	{
-	  add_to_imports (gimple_assign_rhs1 (def_stmt), imports);
-	  tree rhs = gimple_assign_rhs2 (def_stmt);
-	  if (rhs && add_to_imports (rhs, imports))
-	    worklist.safe_push (rhs);
-	  rhs = gimple_assign_rhs3 (def_stmt);
-	  if (rhs && add_to_imports (rhs, imports))
-	    worklist.safe_push (rhs);
-	}
-      else if (gphi *phi = dyn_cast <gphi *> (def_stmt))
+      if (gphi *phi = dyn_cast <gphi *> (def_stmt))
 	{
 	  for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
 	    {
@@ -599,6 +592,30 @@ path_range_query::compute_imports (bitmap imports, const vec<basic_block> &path)
 		worklist.safe_push (arg);
 	    }
 	}
+      else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
+	{
+	  tree ssa[3];
+	  if (range_op_handler (ass))
+	    {
+	      ssa[0] = gimple_range_ssa_p (gimple_range_operand1 (ass));
+	      ssa[1] = gimple_range_ssa_p (gimple_range_operand2 (ass));
+	      ssa[2] = NULL_TREE;
+	    }
+	  else if (gimple_assign_rhs_code (ass) == COND_EXPR)
+	    {
+	      ssa[0] = gimple_range_ssa_p (gimple_assign_rhs1 (ass));
+	      ssa[1] = gimple_range_ssa_p (gimple_assign_rhs2 (ass));
+	      ssa[2] = gimple_range_ssa_p (gimple_assign_rhs3 (ass));
+	    }
+	  else
+	    continue;
+	  for (unsigned j = 0; j < 3; ++j)
+	    {
+	      tree rhs = ssa[j];
+	      if (rhs && add_to_imports (rhs, imports))
+		worklist.safe_push (rhs);
+	    }
+	}
     }
   // Exported booleans along the path, may help conditionals.
   if (m_resolve)
-- 
2.35.3