Re: [PATCH] Tame path_range_query::compute_imports

[Andrew MacLeod <amacleod@redhat.com>]

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)