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

Aldy Hernandez aldyh@redhat.com
Tue Jun 8 06:26:11 GMT 2021

On 6/7/21 9:20 PM, Andrew MacLeod 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?

The propagation is done in the subst & fold engine when either 
value_of_expr or value_on_edge return a value that can be propagated. 
Propagations are not done blindly, as all uses of the result of value_o* 
are guarded with may_propagate_copy().

The simplifier (vr-values) is not involved, as it uses range_of_expr 
which only returns constant ranges.


More information about the Gcc-patches mailing list