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

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

On Mon, Jun 7, 2021 at 9:20 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> On 6/7/21 9:30 AM, Richard Biener via Gcc-patches wrote:
> > On Mon, Jun 7, 2021 at 12:10 PM Aldy Hernandez via Gcc-patches
> > <gcc-patches@gcc.gnu.org> wrote:
> >> The substitute_and_fold_engine which evrp uses is expecting symbolics
> >> from value_of_expr / value_on_edge / etc, which ranger does not provide.
> >> In some cases, these provide important folding cues, as in the case of
> >> aliases for pointers.  For example, legacy evrp may return [&foo, &foo]
> >> for the value of "bar" where bar is on an edge where bar == &foo, or
> >> when bar has been globally set to &foo.  This information is then used
> >> by the subst & fold engine to propagate the known value of bar.
> >>
> >> Currently this is a major source of discrepancies between evrp and
> >> ranger.  Of the 284 cases legacy evrp is getting over ranger, 237 are
> >> for pointer equality as discussed above.
> >>
> >> This patch implements a context aware points-to class which
> >> ranger-evrp can use to query what a pointer is currently pointing to.
> >> With it, we reduce the 284 cases legacy evrp is getting to 47.
> >>
> >> The API for the points-to analyzer is the following:
> >>
> >> class points_to_analyzer
> >> {
> >> public:
> >>    points_to_analyzer (gimple_ranger *r);
> >>    ~points_to_analyzer ();
> >>    void enter (basic_block);
> >>    void leave (basic_block);
> >>    void visit_stmt (gimple *stmt);
> >>    tree get_points_to (tree name) const;
> >> ...
> >> };
> >>
> >> The enter(), leave(), and visit_stmt() methods are meant to be called
> >> from a DOM walk.   At any point throughout the walk, one can call
> >> get_points_to() to get whatever an SSA is pointing to.
> >>
> >> If this class is useful to others, we could place it in a more generic
> >> location.
> >>
> >> Tested on x86-64 Linux with a regular bootstrap/tests and by comparing
> >> EVRP folds over ranger before and after this patch.
> > Hmm, but why call it "points-to" - when I look at the implementation
> > it's really about equivalences.  Thus,
> >
> >   if (var1_2 == var2_3)
> >
> > could be handled the same way.  Also "points-to" implies (to me)
> > that &p[1] and &p[2] point to the same object but your points-to
> > is clearly tracking equivalences only.
> >
> > So maybe at least rename it to pointer_equiv_analyzer?  ISTR
> > propagating random (symbolic) equivalences has issues.
>
> Yeah, pointer_equiv is probably more accurate. This is purely for cases
> where we know a pointer points to something that isn't an ssa_name.
> Eventually this is likely to be subsumed into a pointer_range object,
> but unlikely in this release.
>
> 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
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).

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.

Richard.

>
> Andrew
>
>