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

[Andrew MacLeod <amacleod@redhat.com>]

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.guenther@gmail.com>
>> Sent: Wednesday, November 10, 2021 5:44 PM
>> To: Di Zhao OS <dizhao@os.amperecomputing.com>
>> Cc: gcc-patches@gcc.gnu.org; Andrew MacLeod <amacleod@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
>> <dizhao@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.