PR tree-optimization/103359 - Check for equivalences between PHI argument and def.
Commit Message
PHI nodes frequently feed each other, and this is particularly true of
the one/two incoming edge PHIs inserted by some of the loop analysis
code which is introduced at the start of the VRP passes.
Ranger has a hybrid of optimistic vs pessimistic evaluation, and when it
switches to pessimistic, it has to assume VARYING for a range. PHIs are
calculated as the union of all incoming edges, so once we throw a
VARYING into the mix, there's not much chance going back. (mostly
true... we can sometimes update the range when inputs change, but we
prefer to avoid iterating when possible)
We already have code to recognize that if an argument to a PHI is the
same as the def, it cannot provide any additional information and is
skipped. ie,
# h_10 = PHI <4(2), h_10(3), h_10(4), 1(7)>
We can skip the h_10 arguments, and produce [1,1][4,4] as the range with
any additional information/processing.
This patch extends that slightly to recognize that if the argument is a
known equivalence of the def, it also does not provide any additional
information. This allows us to "ignore" some of the pessimistic VARYING
values that come in on back edges when the relation oracle indicates
that there is a known equivalence.
Take for instance the sequence from the PR testcase:
<bb 5> :
# h_7 = PHI <4(2), 1(4)>
<bb 6> :
# h_18 = PHI <h_7(5), h_22(3)>
<bb 3> :
# h_22 = PHI <h_18(6)>
<bb 4> :
# h_20 = PHI <h_22(3)>
We only fully calculate one range at a time, so when calculating h_18,
we need to first resolve the range h_22 on the back edge 3->6. That
feeds back to h_18, which isn't fully calculated yet and is
pessimistically assumed to be VARYING until we do get a value. With h_22
being varying when resolving h_18 now, we end up makig h_18 varying, and
lose the info from h_7.
This patch extends the equivalence observation slightly to recognize
that if the argument is a known equivalence of the def in predecessor
block, it also does not provide any additional information. This allows
us to ignore some of the pessimistic VARYING values that are set when
the relation oracle indicates that there is a known equivalence.
In the above case, h_22 is known to be equivalent to h_18 in BB3, and so
we can ignore the range h_22 provides on any edge coming from bb3. There
is a caveat that if *all* the arguments to a PHI are in the equivalence
set, then you have to use the range of the equivalence.. otherwise you
get UNDEFINED.
This will help us to see through some of the artifacts of cycling PHIs
in these simple cases, and in the above case, we end up with h_7, h_18,
h_22 and h_20 all in the equivalence set with a range of [1, 1][4, 4],
and we can remove the code we need to like we did in GCC11.
This wont help with more complex PHI cycles, but that seems like
something we could be looking at elsewhere, phi-opt maybe, utilizing
ranger to set the global range when its complex.
Bootstrapped on x86_64-pc-linux-gnu with no regressions. OK?
Andrew
Comments
On Wed, Nov 24, 2021 at 9:49 PM Andrew MacLeod via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> PHI nodes frequently feed each other, and this is particularly true of
> the one/two incoming edge PHIs inserted by some of the loop analysis
> code which is introduced at the start of the VRP passes.
>
> Ranger has a hybrid of optimistic vs pessimistic evaluation, and when it
> switches to pessimistic, it has to assume VARYING for a range. PHIs are
> calculated as the union of all incoming edges, so once we throw a
> VARYING into the mix, there's not much chance going back. (mostly
> true... we can sometimes update the range when inputs change, but we
> prefer to avoid iterating when possible)
>
> We already have code to recognize that if an argument to a PHI is the
> same as the def, it cannot provide any additional information and is
> skipped. ie,
>
> # h_10 = PHI <4(2), h_10(3), h_10(4), 1(7)>
>
> We can skip the h_10 arguments, and produce [1,1][4,4] as the range with
> any additional information/processing.
>
> This patch extends that slightly to recognize that if the argument is a
> known equivalence of the def, it also does not provide any additional
> information. This allows us to "ignore" some of the pessimistic VARYING
> values that come in on back edges when the relation oracle indicates
> that there is a known equivalence.
>
> Take for instance the sequence from the PR testcase:
>
> <bb 5> :
> # h_7 = PHI <4(2), 1(4)>
>
> <bb 6> :
> # h_18 = PHI <h_7(5), h_22(3)>
>
> <bb 3> :
> # h_22 = PHI <h_18(6)>
>
> <bb 4> :
> # h_20 = PHI <h_22(3)>
>
> We only fully calculate one range at a time, so when calculating h_18,
> we need to first resolve the range h_22 on the back edge 3->6. That
> feeds back to h_18, which isn't fully calculated yet and is
> pessimistically assumed to be VARYING until we do get a value. With h_22
> being varying when resolving h_18 now, we end up makig h_18 varying, and
> lose the info from h_7.
>
> This patch extends the equivalence observation slightly to recognize
> that if the argument is a known equivalence of the def in predecessor
> block, it also does not provide any additional information. This allows
> us to ignore some of the pessimistic VARYING values that are set when
> the relation oracle indicates that there is a known equivalence.
>
> In the above case, h_22 is known to be equivalent to h_18 in BB3, and so
> we can ignore the range h_22 provides on any edge coming from bb3. There
> is a caveat that if *all* the arguments to a PHI are in the equivalence
> set, then you have to use the range of the equivalence.. otherwise you
> get UNDEFINED.
>
> This will help us to see through some of the artifacts of cycling PHIs
> in these simple cases, and in the above case, we end up with h_7, h_18,
> h_22 and h_20 all in the equivalence set with a range of [1, 1][4, 4],
> and we can remove the code we need to like we did in GCC11.
>
> This wont help with more complex PHI cycles, but that seems like
> something we could be looking at elsewhere, phi-opt maybe, utilizing
> ranger to set the global range when its complex.
>
> Bootstrapped on x86_64-pc-linux-gnu with no regressions. OK?
OK.
Thanks,
Richard.
> Andrew
>
>
>
>
On 11/25/21 07:40, Richard Biener wrote:
> On Wed, Nov 24, 2021 at 9:49 PM Andrew MacLeod via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>> PHI nodes frequently feed each other, and this is particularly true of
>> the one/two incoming edge PHIs inserted by some of the loop analysis
>> code which is introduced at the start of the VRP passes.
>>
>> Ranger has a hybrid of optimistic vs pessimistic evaluation, and when it
>> switches to pessimistic, it has to assume VARYING for a range. PHIs are
>> calculated as the union of all incoming edges, so once we throw a
>> VARYING into the mix, there's not much chance going back. (mostly
>> true... we can sometimes update the range when inputs change, but we
>> prefer to avoid iterating when possible)
>>
>> We already have code to recognize that if an argument to a PHI is the
>> same as the def, it cannot provide any additional information and is
>> skipped. ie,
>>
>> # h_10 = PHI <4(2), h_10(3), h_10(4), 1(7)>
>>
>> We can skip the h_10 arguments, and produce [1,1][4,4] as the range with
>> any additional information/processing.
>>
>> This patch extends that slightly to recognize that if the argument is a
>> known equivalence of the def, it also does not provide any additional
>> information. This allows us to "ignore" some of the pessimistic VARYING
>> values that come in on back edges when the relation oracle indicates
>> that there is a known equivalence.
>>
>> Take for instance the sequence from the PR testcase:
>>
>> <bb 5> :
>> # h_7 = PHI <4(2), 1(4)>
>>
>> <bb 6> :
>> # h_18 = PHI <h_7(5), h_22(3)>
>>
>> <bb 3> :
>> # h_22 = PHI <h_18(6)>
>>
>> <bb 4> :
>> # h_20 = PHI <h_22(3)>
>>
>> We only fully calculate one range at a time, so when calculating h_18,
>> we need to first resolve the range h_22 on the back edge 3->6. That
>> feeds back to h_18, which isn't fully calculated yet and is
>> pessimistically assumed to be VARYING until we do get a value. With h_22
>> being varying when resolving h_18 now, we end up makig h_18 varying, and
>> lose the info from h_7.
>>
>> This patch extends the equivalence observation slightly to recognize
>> that if the argument is a known equivalence of the def in predecessor
>> block, it also does not provide any additional information. This allows
>> us to ignore some of the pessimistic VARYING values that are set when
>> the relation oracle indicates that there is a known equivalence.
>>
>> In the above case, h_22 is known to be equivalent to h_18 in BB3, and so
>> we can ignore the range h_22 provides on any edge coming from bb3. There
>> is a caveat that if *all* the arguments to a PHI are in the equivalence
>> set, then you have to use the range of the equivalence.. otherwise you
>> get UNDEFINED.
>>
>> This will help us to see through some of the artifacts of cycling PHIs
>> in these simple cases, and in the above case, we end up with h_7, h_18,
>> h_22 and h_20 all in the equivalence set with a range of [1, 1][4, 4],
>> and we can remove the code we need to like we did in GCC11.
>>
>> This wont help with more complex PHI cycles, but that seems like
>> something we could be looking at elsewhere, phi-opt maybe, utilizing
>> ranger to set the global range when its complex.
>>
>> Bootstrapped on x86_64-pc-linux-gnu with no regressions. OK?
> OK.
>
> Thanks,
> Richard.
>
Committed.
From 9cb5bd6c436165a37717d58388950c5c5ecaf35e Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Tue, 23 Nov 2021 14:12:29 -0500
Subject: [PATCH] Check for equivalences between PHI argument and def.
If a PHI argument on an edge is equivalent with the DEF, then it doesn't
provide any new information, defer processing it unless they are all
equivalences.
PR tree-optimization/103359
gcc/
* gimple-range-fold.cc (fold_using_range::range_of_phi): If arg is
equivalent to def, don't initially include it's range.
gcc/testsuite/
* gcc.dg/pr103359.c: New.
---
gcc/gimple-range-fold.cc | 16 ++++++++++++++++
gcc/testsuite/gcc.dg/pr103359.c | 21 +++++++++++++++++++++
2 files changed, 37 insertions(+)
create mode 100644 gcc/testsuite/gcc.dg/pr103359.c
@@ -771,6 +771,7 @@ fold_using_range::range_of_phi (irange &r, gphi *phi, fur_source &src)
tree phi_def = gimple_phi_result (phi);
tree type = gimple_range_type (phi);
int_range_max arg_range;
+ int_range_max equiv_range;
unsigned x;
if (!type)
@@ -794,6 +795,16 @@ fold_using_range::range_of_phi (irange &r, gphi *phi, fur_source &src)
// Get the range of the argument on its edge.
src.get_phi_operand (arg_range, arg, e);
+ // Likewise, if the incoming PHI argument is equivalent to this
+ // PHI definition, it provides no new info. Accumulate these ranges
+ // in case all arguments are equivalences.
+ if (src.query ()->query_relation (e, arg, phi_def, false) == EQ_EXPR)
+ {
+ single_arg = arg;
+ equiv_range.union_(arg_range);
+ continue;
+ }
+
if (!arg_range.undefined_p ())
{
// Register potential dependencies for stale value tracking.
@@ -816,6 +827,11 @@ fold_using_range::range_of_phi (irange &r, gphi *phi, fur_source &src)
break;
}
+ // If all arguments were equivalences, use the equivalence ranges as no
+ // arguments were processed.
+ if (!seen_arg)
+ r = equiv_range;
+
// If the PHI boils down to a single effective argument, look at it.
if (single_arg)
{
new file mode 100644
@@ -0,0 +1,21 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-evrp" } */
+
+void foo();
+static char a, c;
+static int d, e;
+static short b(short f, short g) { return f * g; }
+int main() {
+ short h = 4;
+ for (; d;)
+ if (h)
+ if(e) {
+ if (!b(a & 1 | h, 3))
+ c = 0;
+ h = 1;
+ }
+ if (c)
+ foo();
+}
+
+/* { dg-final { scan-tree-dump-not "c = 0" "evrp" } } */
--
2.17.2