[PATCH] PR tree-optimization/103359 - Check for equivalences between PHI argument and def.
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
# 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
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?
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 2862 bytes
Desc: not available
More information about the Gcc-patches