Re: [PATCH] tree-optimization/101186 - extend FRE with "equivalence map" for condition prediction

[Aldy Hernandez <aldyh@redhat.com>]

On 6/25/21 9:38 AM, Richard Biener wrote:
> On Thu, Jun 24, 2021 at 5:01 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>>
>> On 6/24/21 9:25 AM, Andrew MacLeod wrote:
>>> On 6/24/21 8:29 AM, Richard Biener wrote:
>>>
>>>
>>> THe original function in EVRP currently looks like:
>>>
>>>   =========== BB 2 ============
>>>      <bb 2> :
>>>      if (a_5(D) == b_6(D))
>>>        goto <bb 8>; [INV]
>>>      else
>>>        goto <bb 7>; [INV]
>>>
>>> =========== BB 8 ============
>>> Equivalence set : [a_5(D), b_6(D)]                 edge 2->8 provides
>>> a_5 and b_6 as equivalences
>>>      <bb 8> :
>>>      goto <bb 6>; [100.00%]
>>>
>>> =========== BB 6 ============
>>>      <bb 6> :
>>>      # i_1 = PHI <0(8), i_10(5)>
>>>      if (i_1 < a_5(D))
>>>        goto <bb 3>; [INV]
>>>      else
>>>        goto <bb 7>; [INV]
>>>
>>> =========== BB 3 ============
>>> Relational : (i_1 < a_5(D))                         edge 6->3 provides
>>> this relation
>>>      <bb 3> :
>>>      if (i_1 == b_6(D))
>>>        goto <bb 4>; [INV]
>>>      else
>>>        goto <bb 5>; [INV]
>>>
>>>
>>> So It knows that a_5 and b_6 are equivalence, and it knows that i_1 <
>>> a_5 in BB3 as well..
>>>
>>> so we should be able to indicate that  i_1 == b_6 as [0,0]..  we
>>> currently aren't.   I think I had turned on equivalence mapping during
>>> relational processing, so should be able to tag that without
>>> transitive relations...  I'll have a look at why.
>>>
>>> And once we get a bit further along, you will be able to access this
>>> without ranger.. if one wants to simply register the relations directly.
>>>
>>> Anyway, I'll get back to you why its currently being missed.
>>>
>>> Andrew
>>>
>>>
>>>
>> As promised.  There was a typo in the equivalency comparisons... so it
>> was getting missed.  With the fix, the oracle identifies the relation
>> and evrp will now fold that expression away and the IL becomes:
>>
>>     <bb 2> :
>>     if (a_5(D) == b_6(D))
>>       goto <bb 4>; [INV]
>>     else
>>       goto <bb 5>; [INV]
>>
>>     <bb 3> :
>>     i_10 = i_1 + 1;
>>
>>     <bb 4> :
>>     # i_1 = PHI <0(2), i_10(3)>
>>     if (i_1 < a_5(D))
>>       goto <bb 3>; [INV]
>>     else
>>       goto <bb 5>; [INV]
>>
>>     <bb 5> :
>>     return;
>>
>> for the other cases you quote, there are no predictions such that if a
>> != 0 then this equivalency exists...
>>
>> +  if (a != 0)
>> +    {
>> +      c = b;
>> +    }
>>
>> but the oracle would register that in the TRUE block,  c and b are
>> equivalent... so some other pass that was interested in tracking
>> conditions that make a block relevant would be able to compare relations...
> 
> I guess to fully leverage optimizations for cases like
> 
>    if (a != 0)
>      c = b;
>    ...
>    if (a != 0)
>      {
>          if (c == b)
> ...
>      }
> 
> one would need to consider the "optimally jump threaded path" to the
> program point where the to be optimized stmt resides, making all
> originally conditional but on the jump threaded path unconditional
> relations and equivalences available.
> 
> For VN that could be done by unwinding to the CFG merge after
> the first if (a != 0), treating only one of the predecessor edges
> as executable and registering the appropriate a != 0 result and
> continue VN up to the desired point, committing to the result
> until before the CFG merge after the second if (a != 0).  And then
> unwinding again for the "else" path.  Sounds like a possible
> explosion in complexity as well if second-order opportunities
> arise.
> 
> That is, we'd do simplifications exposed by jump threading but
> without actually doing the jump threading (which will of course
> not allow all possible simplifications w/o inserting extra PHIs
> for computations we might want to re-use).

FWIW, as I mention in the PR, if the upcoming threader work could be 
taught to use the relation oracle, it could easily solve the conditional 
flowing through the a!=0 path.  However, we wouldn't be able to thread 
it because in this particular case, the path crosses loop boundaries.

I leave it to Jeff/others to pontificate on whether the jump-threader 
path duplicator could be taught to through loops. ??

Aldy