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

[Richard Biener <richard.guenther@gmail.com>]

On Mon, Jun 28, 2021 at 3:15 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> On 6/27/21 11:46 AM, Aldy Hernandez wrote:
> >
> >
> > 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)
> >> ...
> >>      }
> >>
> >> 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
> >
> This is still bouncing around in my head. I think we have the tools to
> do this better than via threading,  Ranger is now trivially capable of
> calculating when a predicate expression is true or false at another
> location in the IL. Combine this with flagging relations that are true
> when the predicate is, and that relation could be simply added into the
> oracle.
>
> ie:
>
>      <bb 2> :
>      if (a_5(D) != 0)
>        goto <bb 3>; [INV]
>      else
>        goto <bb 4>; [INV]
>
>      <bb 3> :
>      <bb 4> :
>      # c_1 = PHI <c_6(D)(2), b_7(D)(3)>
>
> the predicate and relations are:
>      (a_5 != 0)  ->  c_1 == b_7
>      (a_5 == 0) -> c_1 == c_6
>
> then :
>
> <bb 9> :
>      # i_2 = PHI <0(4), i_12(8)>
>      if (c_1 > i_2)
>        goto <bb 5>; [INV]
>      else
>        goto <bb 10>; [INV]
>
>      <bb 5> :                                9->5 registers c_1 > 1_2
> with the oracle
>      if (a_5(D) != 0)
>        goto <bb 6>; [INV]
>      else
>        goto <bb 8>; [INV]
>
>      <bb 6> :
(*) >      if (i_2 == b_7(D))
>        goto <bb 7>; [INV]
>      else
>        goto <bb 8>; [INV]
> ..
> If we know to check the predicate list in bb_6, ranger can answer the
> question: on the branch in bb6, a_5 != 0.
> This in turn means the predicated relation c_1 == b_7 can be applied to
> bb6 and register with the oracle.
> Once that is done,  we already know c_1 > i_2 so we'll fold i_2 == b_7
> as [0, 0] as the equivalency between b_7 and c_1 is now applied.
>
> So the capability is built in.. it boils down to finding the predicated
> relations we care about and knowing to apply them.
> This one is pretty straightforward because the condition is exactly the
> same.   When we see a_5 != 0, a_5 is in the export list and we just
> check to see if there are any predicated flagged on a_5.  The actual
> expression could be more complicated, and it would still be able to
> answer it.  This is very similar to how the new threader finds
> threads..  It matches imports and exports.. here we mostly care just
> about the exports and figuring out what the predicates we care about are,
>
> Anyway, theres a fit in there somewhere.  It might be something as
> straightforward as a an enhancement to the relation oracle.   I plan to
> get to some experiments eventually.

The important part is to not waste too many cycles here.  For example
for the exact equalities i_2 == b_7(D) at (*) you could lookup whether
there are any "predicated" relations registered that match this and then
see whether the current active predicate matches the recorded one.
For sth more complicated like i_2 < b_7(D) you'd then need to
improve this lookup to say "any relation between i_2 and b_7(D)?".

Doing it this way is I guess cheaper than looking for all relations
recorded predicated on a predicate that's currently active.

But note that such "relation between i_2 and b_7(D)"  map will be
interesting to maintain since following equivalences may need to
alter existing relations ... but things quickly become quadratic
or worse if you want to cover all cases and I've not yet come up
with a scheme to improve that.  But there must be existing
research papers about the topic ...

Richard.

> Andrew
>
>