diff mbox series

PR tree-optimization/103359 - Check for equivalences between PHI argument and def.

Message ID cc1c7b0e-1398-dec5-0517-fbedbc9a97ea@redhat.com
State New
Headers show
Series PR tree-optimization/103359 - Check for equivalences between PHI argument and def. | expand

Commit Message

Andrew MacLeod Nov. 24, 2021, 7:50 p.m. UTC 
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

Richard Biener Nov. 25, 2021, 12:40 p.m. UTC | #1 
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
>
>
>
>
Andrew MacLeod Nov. 25, 2021, 1:45 p.m. UTC | #2 
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.
diff mbox series

Patch

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

diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index ec9690b05e4..d66ada5bb7c 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -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)
       {
diff --git a/gcc/testsuite/gcc.dg/pr103359.c b/gcc/testsuite/gcc.dg/pr103359.c
new file mode 100644
index 00000000000..13406f90d7d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr103359.c
@@ -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