[PATCH] PR tree-optimization/109192 - Terminate GORI calculations if a relation is not relevant.

[PATCH] PR tree-optimization/109192 - Terminate GORI calculations if a relation is not relevant.

[Andrew MacLeod]

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

As mentioned in the PR, the originally GORI terminated calculation if 
the LHS was varying as it could not provide any additional useful 
information on an outgoing edge beyond what folding would give.

The original patch  introduced relations, and aloowed GORI to keep going 
with the hope that the relation might provide new info.  This PR trips 
over a case where there are a lot of relations, and GORI is unbounded in 
the path query with is already quadratic.

This patch first checks if the relation can have an effect on the 
outgoing calculation, and if not, terminates the calculation like we use 
to.  This prevents a lot of excessive checking.  there are 2 cases where 
the relation is considered relevant:

  1- both argument to the relation are in the defchain of the operand 
currently being calculated:

b_2 = x_3 < y_5
c_3 = b_2 != 0
if (c_3 &&  x_3 < y_5)

on te true side, we will ge the relation x_3 < y_5,  both of which are 
in the defchain for c_3.  THis will enable use to evaluate that on the 
true side, c_3 must be [1,1], and therefore b_2 must be[1, 1], and the 
relation can be applied to the calculation [1,1] = x_3 < y_5    to 
establish that c_3 will indeed be [1,1] always if x_3<y_5
Without this, c_3 will evaluate to VARYING and the calcultion will 
terminate and we wont know b_2.


2 - AS in the original PR, the relation can be applied to the current 
statement as a def/operand relation:

     _1 = (sizetype) off_3(D);
   q_5 = p_4(D) + _1;
   if (p_4(D) == q_5)

applying p_4 == q_5 to   q_5 = p_4(D) + _1; allows us to evaluate _1 as 
[0,0] on the true side and ~[0,0] on the false side through the 
op2_range calculation for pointer_plus.

Without this, q_5 has a value of varying, and the calculation will 
terminate without getting better value sfor _1 or off_3.

3 -  If  zero or one element of the relation is in the def chain, the 
relation should not have any impact on the calculation, and we can 
simply stop calculating.

The performance impact is negligible (its actually slightly faster) 
across 230 GCC source files.  When there is a relation, the extra work 
to determine relevance is offset by the pointless calculations avoided.

A slight tweak was needed to the value_relation class as I was tripping 
over a fortran testcase failure resulting from an old assumption we 
could not have a value_relation record for  op1 VREL_EQ op1, which GORI 
is counting on.. It was sneaking through before because we we're 
assuming that the relation record has to be set properly.

Bootstraps on x86_64-pc-linux-gnu with no regressions.  OK for trunk?

Andrew

[-- Attachment #2: 192.patch --]
[-- Type: text/x-patch, Size: 2909 bytes --]

commit 7fdd113c8de94f96ddcbdd4561169fa16f8d4ea1
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Mon Mar 20 16:11:12 2023 -0400

    Terminate GORI calculations if a relation is not relevant.
    
    We currently allow VARYING lhs GORI calculations to continue if there is
    a relation present in the hope it will eventually better refine a result.
    This adds a check that the relation is relevant to the outgoing range
    calculation first.  If it is not relevant, stop calculating.
    
            PR tree-optimization/109192
            * gimple-range-gori.cc (gori_compute::compute_operand_range):
            Terminate gori calculations if a relation is not relevant.
            * value-relation.h (value_relation::set_relation): Allow
            equality between op1 and op2 if they are the same.

diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index 7f5a21a876b..469e6dc33f2 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -653,12 +653,38 @@ gori_compute::compute_operand_range (vrange &r, gimple *stmt,
   if (!op1_in_chain && !op2_in_chain)
     return false;
 
-  // If the lhs doesn't tell us anything and there are no relations, there
-  // is nothing to be learned.
-  if (lhs.varying_p () && !vrel_ptr)
-    return false;
+  bool res = false;
+  // If the lhs doesn't tell us anything only a relation can possibly enhance
+  // the result.
+  if (lhs.varying_p ())
+    {
+      if (!vrel_ptr)
+	return false;
+      // If there is a relation (ie: x != y) , it can only be relevant if
+      // a) both elements are in the defchain
+      //    c = x > y   // (x and y are in c's defchain)
+      if (op1_in_chain)
+	res = in_chain_p (vrel_ptr->op1 (), op1)
+	      && in_chain_p (vrel_ptr->op2 (), op1);
+      if (!res && op2_in_chain)
+	res = in_chain_p (vrel_ptr->op1 (), op2)
+	      || in_chain_p (vrel_ptr->op2 (), op2);
+      if (!res)
+	{
+	  // or b) one relation element is in the defchain of the other and the
+	  //       other is the LHS of this stmt.
+	  //  x = y + 2
+	  if (vrel_ptr->op1 () == handler.lhs ()
+	      && (vrel_ptr->op2 () == op1 || vrel_ptr->op2 () == op2))
+	    res = true;
+	  else if (vrel_ptr->op2 () == handler.lhs ()
+		   && (vrel_ptr->op1 () == op1 || vrel_ptr->op1 () == op2))
+	    res = true;
+	}
+      if (!res)
+	return false;
+    }
 
-  bool res;
   // Process logicals as they have special handling.
   if (is_gimple_logical_p (stmt))
     {
diff --git a/gcc/value-relation.h b/gcc/value-relation.h
index 023ac52e274..106650eaff9 100644
--- a/gcc/value-relation.h
+++ b/gcc/value-relation.h
@@ -446,7 +446,7 @@ value_relation::set_relation (relation_kind r, tree n1, tree n2)
 {
   gcc_checking_assert (TREE_CODE (n1) == SSA_NAME
 		       && TREE_CODE (n2) == SSA_NAME);
-  if (n1 == n2)
+  if (n1 == n2 && r != VREL_EQ)
     {
       related = VREL_VARYING;
       name1 = NULL_TREE;

Re: [PATCH] PR tree-optimization/109192 - Terminate GORI calculations if a relation is not relevant.

[Richard Biener]

On Tue, Mar 21, 2023 at 2:44 PM Andrew MacLeod via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> As mentioned in the PR, the originally GORI terminated calculation if
> the LHS was varying as it could not provide any additional useful
> information on an outgoing edge beyond what folding would give.
>
> The original patch  introduced relations, and aloowed GORI to keep going
> with the hope that the relation might provide new info.  This PR trips
> over a case where there are a lot of relations, and GORI is unbounded in
> the path query with is already quadratic.
>
> This patch first checks if the relation can have an effect on the
> outgoing calculation, and if not, terminates the calculation like we use
> to.  This prevents a lot of excessive checking.  there are 2 cases where
> the relation is considered relevant:
>
>   1- both argument to the relation are in the defchain of the operand
> currently being calculated:
>
> b_2 = x_3 < y_5
> c_3 = b_2 != 0
> if (c_3 &&  x_3 < y_5)
>
> on te true side, we will ge the relation x_3 < y_5,  both of which are
> in the defchain for c_3.  THis will enable use to evaluate that on the
> true side, c_3 must be [1,1], and therefore b_2 must be[1, 1], and the
> relation can be applied to the calculation [1,1] = x_3 < y_5    to
> establish that c_3 will indeed be [1,1] always if x_3<y_5
> Without this, c_3 will evaluate to VARYING and the calcultion will
> terminate and we wont know b_2.
>
>
> 2 - AS in the original PR, the relation can be applied to the current
> statement as a def/operand relation:
>
>      _1 = (sizetype) off_3(D);
>    q_5 = p_4(D) + _1;
>    if (p_4(D) == q_5)
>
> applying p_4 == q_5 to   q_5 = p_4(D) + _1; allows us to evaluate _1 as
> [0,0] on the true side and ~[0,0] on the false side through the
> op2_range calculation for pointer_plus.
>
> Without this, q_5 has a value of varying, and the calculation will
> terminate without getting better value sfor _1 or off_3.
>
> 3 -  If  zero or one element of the relation is in the def chain, the
> relation should not have any impact on the calculation, and we can
> simply stop calculating.
>
> The performance impact is negligible (its actually slightly faster)
> across 230 GCC source files.  When there is a relation, the extra work
> to determine relevance is offset by the pointless calculations avoided.
>
> A slight tweak was needed to the value_relation class as I was tripping
> over a fortran testcase failure resulting from an old assumption we
> could not have a value_relation record for  op1 VREL_EQ op1, which GORI
> is counting on.. It was sneaking through before because we we're
> assuming that the relation record has to be set properly.
>
> Bootstraps on x86_64-pc-linux-gnu with no regressions.  OK for trunk?

OK.

Richard.

> Andrew