Re: [PATCH] Implement a context aware points-to analyzer for use in evrp.

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

On Tue, Jun 8, 2021 at 4:31 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> On 6/8/21 3:26 AM, Richard Biener wrote:
> > On Mon, Jun 7, 2021 at 9:20 PM Andrew MacLeod <amacleod@redhat.com> wrote:
> >>
> >> I don't think this is actually doing the propagation though... It tracks
> >> that a_2 currently points to &foo.. and returns that to either
> >> simplifier or folder thru value_of_expr().  Presumably it is up to them
> >> to determine whether the tree expression passed back is safe to
> >> propagate.   Is there any attempt in EVRP to NOT set the range of
> >> something to [&foo, &foo] under some conditions?   This is what the
> >> change amounts to.  Ranger would just return a range of [1, +INF], and
> >> value_of_expr  would therefore return NULL.  This allows value_of to
> >> return &foo in these conditions.   Aldy, did you see any other checks in
> >> the vr-values code?
> >>
> >> Things like   if (var1_2 == var2_3) deal with just ssa-names and will be
> >> handled by an ssa_name relation oracle. It just treats equivalencies
> >> like a a slightly special kind of relation. Im just about to bring that
> >> forward this week.
> > Ah, great - I'm looking forward to this.  Currently both DOM and VN
>
> The initial code will be a bit basic, but it can be educated as we go
> along :-)
>
> Its currently tied into ranger just because as ranger processes
> statements it registers any relations it sees.. the oracle organizes
> these and can answer questions on anything it has seen.
>
> It is otherwise independent of ranger. It is dominance based, and there
> is no reason relations cant be queried and registered by any pass doing
> a DOM walk without ranger.  It benefits from ranger in that sometime
> relations are refined when we know ranges  (ie for unsigned math)
>
>      a_2 = b_4 + 6
>
> if we know the range of b_4 will not cause an overflow, then we could
> set a_2 > b_4.. otherwise we cant..  Wiring it with ranger also removes
> the dependency on a DOM walk as ranger sorts the ordering out as needed.
>
> It is driven by data provided by range-ops and is more of a data
> propagation/lookup mechanism than anything. There are a number of cases
> we don't currently register relations simply because we have not flushed
> out the various tree code instructions.   We'll get to those eventually.
> I expect a number of the PRs will eventually be fixed primarily by
> adding code to range-ops .
>
> It also only does first order relations so far...  I'll get to
> transitives and other things as well.
>
>
> > do a very simplistic thing when trying to simplify downstream conditions
> > based on earlier ones, abusing their known-expressions hash tables
> > by, for example, registering (a < b) == 1, (a > b) == 0, (a == b) == 0,
> > (a != b) == 1 for an earlier a < b condition on the true edge.  So I wonder
> > if this relation code can be somehow used there.  In VN there's the
> > extra complication that it iterates, but DOM is just a DOM-walk and
> > the VN code also has a non-iterating mode (but not a DOM walk).
>
> I don't think the iteration is an issue,  ranger iterates to some degree
> as well, and some statement are registered multiple times. I believe it
> intersects with any known relation, so if an iteration causes a relation
> to become "better" it should be updated.

Note VN does optimistic iteration thus relations will become only "worse",
thus we somehow need to be able to remove relations we added during
the last iteration.  That is, in the first iteration a if (a > b) might be
registered as a > 1 when b has (optimistic) value b but in the second
we have to make it a > b when b dropped to varying for example.

The optimistic part of VN is that it treats all edges as not executable
initially and thus it ignores values on non-executable edges in PHI
nodes.

> The API is for registering is pretty straightforward:
>
>    void register_relation (gimple *stmt, relation_kind k, tree op1, tree
> op2);
>    void register_relation (edge e, relation_kind k, tree op1, tree op2);
>
> so all you'd have to do when a < b is encountered is to register  (a
> LT_EXPR b) on the true edge, and (a GE_EXPR b) on the false edge.  Then
> any queries downstream should be reflected.
>
>
>
> > Of course the code is also used to simplify
> >
> >   if (a > b)
> >      c = a != b;
> >
> > but the relation oracle should be able to handle that as well I guess.
> >
> yeah, so a GT_EXPR B is registered on the true edge.  Then when
> processing c = a != b,  you can determine that a NE_EXPR b intersected
> with a GT_EXPR b result in  a GT_EXPR b... which folds to a 1.
>
> This is all also available with the range-op API additions such that you
> can simply call :
>
> rangerop->fold_range (stmt(c = a != b), range_of_a, range_of_b, GT_EXPR
> (relation of a to b)  and the range returned will be [1,1].
>
> The actual ranges in this case are irrelevant, but arent for some other
> kinds of stmts.
>
> Likewise, simply asking ranger for the range of c will likewise return
> [1,1], the relation processing is all integrated behind the scenes in
> ranger..
>
> As we start using the code more, we may find we want/need a few more
> wrappers around some of this so that you can transparently ask what the
> RHS folds to without any ranger present, just with relations.  Those'll
> be fairly trivial to add...
>
> The relation oracle is going to be directly accessible from the
> get_range_query(cfun) range_query class.  I'll do a big writeup when i
> submit it and we should be able to make it usable in any of those places.

OK, so using this from DOM should be pretty straight-forward (you may
want to try to use it there as proof of API sanity).  When it's in I'll see if
it fits (iterative) VN.

Richard.

> Andrew
>
>
>