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

[Andrew MacLeod <amacleod@redhat.com>]

On 6/24/21 8:29 AM, Richard Biener wrote:
> On Thu, Jun 24, 2021 at 11:55 AM Di Zhao via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>
> You quote opportunities that are catched with this like
>
> +  if (a != 0)
> +    {
> +      c = b;
> +    }
> +  for (unsigned i = 0; i < c; i++)
> +    {
> +      if (a != 0)
> +       {
> +         if (i >= b)
> +           /* Should be eliminated.
> +            */
> +           foo ();
>
> but say other "obvious" cases like
>
> +  if (a != 0)
> +    {
> +      c = b;
> +    }
> +  for (unsigned i = 0; i < c; i++)
> +    {
> +      if (a != 0)
> +       {
> +           /* Should be zero.  */
>               return b - c;
>
> are not handled.  That's in line with the current "value predication"
> which mainly aims at catching simple jump threading opportunities;
> you only simplify conditions with the recorded equivalences.  But
> then the complexity of handling equivalences does probably not
> outweight the opportunities catched - can you share some numbers
> on how many branches are newly known taken during VN with
> this patch during say bootstrap or build of SPEC CPU?
>
> I've hoped to ditch the current "value predication" code by eventually
> using the relation oracle from ranger but did not yet have the chance
> to look into that.  Now, the predicated equivalences are likely not
> something that infrastructure can handle?
>
> In the end I think we should research into maintaining an alternate
> expression table for conditions (those we like to simplify with
> equivalences) and use a data structure that more easily allows to
> introduce (temporary) equivalences.  Like by maintaining
> back-references of values we've recorded a condition for and a way
> to quickly re-canonicalize conditions.  Well - it requires some research,
> as said.
>
The idea would be to handle all this eventually if it doesnt now.  It'll 
certainly be capable of it. we havent looked into any missed cases yet. 
early days :-)

The oracle  handles predicated things just fine.  We're missing 
transitive relations, and any time an edge has multiple predecessors we 
sort of bail on predicated things for now.  I also haven't gotten to 
producing a nice relation/equivlance map of what we actually know... 
That might be worthwhile sooner than later.

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