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

Andrew MacLeod amacleod@redhat.com
Wed Nov 24 19:50:05 GMT 2021


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




-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Check-for-equivalences-between-PHI-argument-and-def.patch
Type: text/x-patch
Size: 2862 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20211124/a03f7aa5/attachment-0001.bin>


More information about the Gcc-patches mailing list