On 11/15/21 12:24, Di Zhao OS via Gcc-patches wrote:
Attached is the updated patch. Fixed some errors in testcases.
-----Original Message-----
From: Richard Biener <richard.guent...@gmail.com>
Sent: Wednesday, November 10, 2021 5:44 PM
To: Di Zhao OS <diz...@os.amperecomputing.com>
Cc: gcc-patches@gcc.gnu.org; Andrew MacLeod <amacl...@redhat.com>
Subject: Re: [PATCH v2] tree-optimization/101186 - extend FRE with
"equivalence map" for condition prediction
On Sun, Oct 24, 2021 at 9:03 PM Di Zhao OS
<diz...@os.amperecomputing.com> wrote:
Hi,
Attached is a new version of the patch, mainly for improving performance
and simplifying the code.
The patch doesn't apply anymore, can you update it please?
I see the new ssa-fre-101.c test already passing without the patch.
It was a mistake in test ssa-fre-101.c::g to define the variables with
the unsigned integers, in this way "a >= 0" is always true. After modified
the case, now fre1 in the patch can remove unreachable call "foo ()", and
evrp on trunk does not.
Likewise ssa-fre-100.c and ssa-fre-102.c would PASS if you scan
the pass dump after fre1 which is evrp so it seems that evrp already
handles the equivalences (likely with the relation oracle) now?
I'm sure there are second order effects when eliminating conditions
in FRE but did you re-evaluate what made you improve VN to see
if the cases are handled as expected now without this change?
In case ssa-fre-102.c, the unreachable call "foo ()" can be removed by
evrp, but fre in the patch can additionally replace "g = x + b" with
"g = 99". (Again I'm sorry the regex to check this was wrong..)
Test cases to simulate the original problem I found are moved into
gcc.dg/tree-ssa/ssa-pre-34.c. The unreachable calls to "foo ()" are
still removed by pre with the patch. (If compiled with -O3, the
"foo ()"s in test file can now be removed by thread2/threadfull2 and
dom3 on trunk. This relies on jump threading across the loops, so
even with -O3, similar cases may not get optimized say if there're
too many statements to copy.)
Thanks,
Di Zhao
I will still look at and consider the change btw, but given the EVRP
improvements I'm also considering to remove the predication
support from VN alltogether. At least in the non-iterating mode
it should be trivially easy to use rangers relation oracle to simplify
predicates. For the iterating mode it might not be 100% effective
since I'm not sure we can make it use the current SSA values and
how it would behave with those eventually changing to worse.
Andrew, how would one ask the relation oracle to simplify a
condition? Do I have to do any bookkeeping to register
predicates on edges for it?
Sorry, missed this.
Presuming you have an active ranger, the range_query class has a
query_relation method which works on either a stmt or an edge. That
method has an optional flag (get_range) which defaults to true, and if
true, it triggers a range query before asking if there is a
relationship.. Which means even if you have done nothing else, it will
go pre-populate whatever is necessary in order determine those ranges at
that point which means filling in the relation oracle.
What that boils down to is on any edge or stmt, you can ask:
get_range_query (cfun)->query_relation (edge e, a_5, b_8)
And it will go and figure out the ranges of a_5 and b_8 at the point,
and any relations between them. so bookkeeping should already be done,
you just have to ask.
if you want to simplify a condition, say you are looking at
c_3 = b_4 < x_7
you dont need to do anything more than ask for the range_of_stmt (). if
its [1,1] or [0,0] you already have your answer. similarly if that was
an if (b_4 < x_7).. There doesn't need to be a LHS.
If you want to manually do it for whatever reason, ie you are tracking a
table or something, then
query_relation(stmt, b_4, x_7) will return a tree code for the
relation, whatever it knows.. ie, maybe LT_EXPR or VREL_NONE if nothing.
value-relation.h has a set of transformation routines:
// General relation kind transformations.
relation_kind relation_union (relation_kind r1, relation_kind r2);
relation_kind relation_intersect (relation_kind r1, relation_kind r2);
relation_kind relation_negate (relation_kind r);
relation_kind relation_swap (relation_kind r);
so you can intersect or union 2 relations to get a result. This is
effectively what asking for the range of c_3 in the above example does
under the covers.
It gets the known relation, intersects it with the condition on the
stmt, and if the result is VREL_EMPTY (empty intersect), the condition
is not true, and you get [0,0]
Similarly, if the known relation union with the condition on the stmt is
the same as the stmt's condition, then we know it is a subset and
therefore true, and return [1,1]. everything else produces [0,1]/VARYING.
I'm sorry I haven't had a chance to document all this stuff yet... I
have most of December scheduled for documentation :-)
Andrew
PS. if you have expressions as trees you are tracking instead of in the
IL, the range_of_expr() query supports arbitrary expressions trees I
believe (which I think we can leverage eventually into predicate
anaylsis) . so if you have stashed the tree (a_3 < b_6 && a_3 > d_2)
somewhere, and wonder what that evaluates at some stmt, you simply query:
if (range_of_expr (r, expr_tree, stmt)) and you should get a [0,0]
[1,1] or [0,1] based on what the values are at that point.
Also note that by using ranger this way instead of just looking at
relations, it will also pick up the ranges which can cause one or more
expressions to be true
Ie, if at that point in the IL a_3 = [100, 200] and d_2 = [0, 14] the
a_3 > d_2 will be true, regardless of whether there is a relation
between them.
This should all work, but hasn't been super extensively stressed yet.
