Refine ranges using relations in GORI.

This allows GORI to recognize when a relation passed in applies to the 2 
operands of the current statement.  Check to see if further range 
refinement is possible before proceeding.

There are 2 primary ways this can happen.

1)  The relation record indicates there is a relation between the LHS 
and the operand being calculated.  If this is the case, then the 
relation is passed thru to the range-ops op1_range or op2_range routine 
for use in evaluating the operand.

2) if there is a relation between op1 and op2, then we take a special 
step (the new routine refine_using_relation) and look to see if there is 
also any dependence between op1 and op2.  If there is, we attempt to 
"refine" their ranges based on this dependence before proceeding 
further.   For example:

d_4 =a_1 * 2
a_1 = b_2 + 1
if (a_1 < b_2)

Looking at the true edge, we start with [1,1] = a_1 < b_2
There is a relation between a_1 and b_2, it checks if the value of a_1 
is dependent on b_2, and tries to calculate new values for a_1 and b_2 
based on this dependence.

if op1_range is properly implemented for operator_plus (next patch), 
then resolving the value of b_2 in
a_1 = b_2 + 1  with the relation op1 >= LHS would return the range of 
[+INF, +INF].  and using that value, a_1 would then have a range of [0, 0].

We calculate and substitute these values early, so that if we are 
looking for other exported values (such as d_4), the range of a_1 = 
[0,0] will trickle up to that calculation on the edge, and we'll get d_4 
= [0,0] on that edge too.

Bootstrapped on x86_64-pc-linux-gnu with no regressions.  Pushed.

Andrew

Hi Andrew!

On Thu, 29 Sep 2022 18:36:53 -0400
Andrew MacLeod via Gcc-patches <gcc-patches@gcc.gnu.org> wrote:

> diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
> index 57a7e820749..b37d03cddda 100644
> --- a/gcc/gimple-range-gori.cc
> +++ b/gcc/gimple-range-gori.cc
> @@ -934,6 +934,115 @@ gori_compute::compute_logical_operands (vrange &true_range, vrange &false_range,
>      src.get_operand (false_range, name);
>  }
>  
> +
> +// This routine will try to refine the ranges of OP1 and OP2 given a relation
> +// K between them.  In order to perform this refinement, one of the operands
> +// must be in the definition chain of the other.  The use is refined using
> +// op1/op2_range on the statement, and the defintion is then recalculated
> +// using the relation.

s/defintion/definition/g
And i'd add a 'kind' before K: given a relation_kind K

We've accumulated quite some "defintion" in the meantime. I think arm
expresses it quite well:
gcc/config/arm/unspecs.md:;; Unspec defintions.
nvptx OTOH only supports weak defintions.
Either way, maybe you can correct this typo in at
least gimple-range-gori.cc and value-query.cc ?

> +
> +bool
> +gori_compute::refine_using_relation (tree op1, vrange &op1_range,
> +			       tree op2, vrange &op2_range,
> +			       fur_source &src, relation_kind k)
> +{
> +  gcc_checking_assert (TREE_CODE (op1) == SSA_NAME);
> +  gcc_checking_assert (TREE_CODE (op2) == SSA_NAME);
> +  gcc_checking_assert (k != VREL_VARYING && k != VREL_UNDEFINED);
> +
> +  bool change = false;
> +  bool op1_def_p = in_chain_p (op2, op1);
> +  if (!op1_def_p)
> +    if (!in_chain_p (op1, op2))
> +      return false;
> +
> +  tree def_op = op1_def_p ? op1 : op2;
> +  tree use_op = op1_def_p ? op2 : op1;
> +
> +  if (!op1_def_p)
> +    k = relation_swap (k);
> +
> +  // op1_def is true if we want to look up op1, otherwise we want op2.
> +  // if neither is the case, we returned in the above check.

I think this comment should be moved up to before setting def_op and
s/op1_def/op1_def_p/
And i hope this ends up as a single if block even if written like above
:)

> +
> +  gimple *def_stmt = SSA_NAME_DEF_STMT (def_op);
> +  gimple_range_op_handler op_handler (def_stmt);
> +  if (!op_handler)
> +    return false;
> +  tree def_op1 = op_handler.operand1 ();
> +  tree def_op2 = op_handler.operand2 ();
> +  // if the def isn't binary, the relation will not be useful.
> +  if (!def_op2)
> +    return false;
> +
> +  // Determine if op2 is directly referenced as an operand.
> +  if (def_op1 == use_op)
> +    {
> +      // def_stmt has op1 in the 1st operand position.
> +      Value_Range other_op (TREE_TYPE (def_op2));
> +      src.get_operand (other_op, def_op2);
> +
> +      // Using op1_range as the LHS, and relation REL, evaluate op2.
> +      tree type = TREE_TYPE (def_op1);
> +      Value_Range new_result (type);
> +      if (!op_handler.op1_range (new_result, type,
> +				 op1_def_p ? op1_range : op2_range,
> +				 other_op, k))
> +	return false;
> +      if (op1_def_p)
> +	{
> +	  change |= op2_range.intersect (new_result);
> +	  // Recalculate op2.
> +	  if (op_handler.fold_range (new_result, type, op2_range, other_op))
> +	    {
> +	      change |= op1_range.intersect (new_result);
> +	    }
> +	}
> +      else
> +	{
> +	  change |= op1_range.intersect (new_result);
> +	  // Recalculate op1.
> +	  if (op_handler.fold_range (new_result, type, op1_range, other_op))
> +	    {
> +	      change |= op2_range.intersect (new_result);
> +	    }
> +	}
> +    }
> +  else if (def_op2 == use_op)
> +    {
> +      // def_stmt has op1 in the 1st operand position.

Maybe i'm confused by the swapping, but that's the 2nd operand
position, isn't it? Maybe you forgot to adjust the comments in one of
the blocks?
thanks,

> +      Value_Range other_op (TREE_TYPE (def_op1));
> +      src.get_operand (other_op, def_op1);
> +
> +      // Using op1_range as the LHS, and relation REL, evaluate op2.
> +      tree type = TREE_TYPE (def_op2);
> +      Value_Range new_result (type);
> +      if (!op_handler.op2_range (new_result, type,
> +				 op1_def_p ? op1_range : op2_range,
> +				 other_op, k))
> +	return false;
> +      if (op1_def_p)
> +	{
> +	  change |= op2_range.intersect (new_result);
> +	  // Recalculate op1.
> +	  if (op_handler.fold_range (new_result, type, other_op, op2_range))
> +	    {
> +	      change |= op1_range.intersect (new_result);
> +	    }
> +	}
> +      else
> +	{
> +	  change |= op1_range.intersect (new_result);
> +	  // Recalculate op2.
> +	  if (op_handler.fold_range (new_result, type, other_op, op1_range))
> +	    {
> +	      change |= op2_range.intersect (new_result);
> +	    }
> +	}
> +    }
> +  return change;
> +}
> +
>  // Calculate a range for NAME from the operand 1 position of STMT
>  // assuming the result of the statement is LHS.  Return the range in
>  // R, or false if no range could be calculated.
> @@ -947,6 +1056,7 @@ gori_compute::compute_operand1_range (vrange &r,
>    gimple *stmt = handler.stmt ();
>    tree op1 = handler.operand1 ();
>    tree op2 = handler.operand2 ();
> +  tree lhs_name = gimple_get_lhs (stmt);
>  
>    Value_Range op1_range (TREE_TYPE (op1));
>    Value_Range tmp (TREE_TYPE (op1));
> @@ -959,7 +1069,21 @@ gori_compute::compute_operand1_range (vrange &r,
>    if (op2)
>      {
>        src.get_operand (op2_range, op2);
> -      if (!handler.calc_op1 (tmp, lhs, op2_range))
> +      relation_kind k = VREL_VARYING;
> +      if (rel)
> +	{
> +	 if (lhs_name == rel->op1 () && op1 == rel->op2 ())
> +	   k = rel->kind ();
> +	 else if (lhs_name == rel->op2 () && op1 == rel->op1 ())
> +	   k = relation_swap (rel->kind ());
> +	 else if (op1 == rel->op1 () && op2 == rel->op2 ())
> +	   refine_using_relation (op1, op1_range, op2, op2_range, src,
> +				  rel->kind ());
> +	 else if (op1 == rel->op2 () && op2 == rel->op1 ())
> +	   refine_using_relation (op1, op1_range, op2, op2_range, src,
> +				  relation_swap (rel->kind ()));
> +       }
> +      if (!handler.calc_op1 (tmp, lhs, op2_range, k))
>  	return false;
>      }
>    else
> @@ -967,7 +1091,7 @@ gori_compute::compute_operand1_range (vrange &r,
>        // We pass op1_range to the unary operation.  Nomally it's a
>        // hidden range_for_type parameter, but sometimes having the
>        // actual range can result in better information.
> -      if (!handler.calc_op1 (tmp, lhs, op1_range))
> +      if (!handler.calc_op1 (tmp, lhs, op1_range, VREL_VARYING))
>  	return false;
>      }
>  
> @@ -1030,6 +1154,7 @@ gori_compute::compute_operand2_range (vrange &r,
>    gimple *stmt = handler.stmt ();
>    tree op1 = handler.operand1 ();
>    tree op2 = handler.operand2 ();
> +  tree lhs_name = gimple_get_lhs (stmt);
>  
>    Value_Range op1_range (TREE_TYPE (op1));
>    Value_Range op2_range (TREE_TYPE (op2));
> @@ -1037,9 +1162,24 @@ gori_compute::compute_operand2_range (vrange &r,
>  
>    src.get_operand (op1_range, op1);
>    src.get_operand (op2_range, op2);
> +  relation_kind k = VREL_VARYING;
> +  if (rel)
> +    {
> +      if (lhs_name == rel->op1 () && op2 == rel->op2 ())
> +       k = rel->kind ();
> +      else if (lhs_name == rel->op2 () && op2 == rel->op1 ())
> +       k = relation_swap (rel->kind ());
> +      else if (op1 == rel->op1 () && op2 == rel->op2 ())
> +       refine_using_relation (op1, op1_range, op2, op2_range, src,
> +			      rel->kind ());
> +      else if (op1 == rel->op2 () && op2 == rel->op1 ())
> +       refine_using_relation (op1, op1_range, op2, op2_range, src,
> +			      relation_swap (rel->kind ()));
> +    }
> +
>  
>    // Intersect with range for op2 based on lhs and op1.
> -  if (!handler.calc_op2 (tmp, lhs, op1_range))
> +  if (!handler.calc_op2 (tmp, lhs, op1_range, k))
>      return false;
>  
>    unsigned idx;
> diff --git a/gcc/gimple-range-gori.h b/gcc/gimple-range-gori.h
> index 1fff3e6255a..c7a32162a1b 100644
> --- a/gcc/gimple-range-gori.h
> +++ b/gcc/gimple-range-gori.h
> @@ -166,6 +166,9 @@ public:
>    bool has_edge_range_p (tree name, edge e);
>    void dump (FILE *f);
>  private:
> +  bool refine_using_relation (tree op1, vrange &op1_range,
> +			      tree op2, vrange &op2_range,
> +			      fur_source &src, relation_kind k);
>    bool may_recompute_p (tree name, edge e);
>    bool may_recompute_p (tree name, basic_block bb = NULL);
>    bool compute_operand_range (vrange &r, gimple *stmt, const vrange &lhs,