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
commit 7fdd113c8de94f96ddcbdd4561169fa16f8d4ea1
Author: Andrew MacLeod <amacl...@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;
