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
