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

Andrew MacLeod amacleod@redhat.com
Thu Nov 25 13:45:12 GMT 2021


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.




More information about the Gcc-patches mailing list