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

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

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).

Richard.

> Andrew
>
>