Implement a context aware pointer equivalency class for use in evrp.
authorAldy Hernandez <aldyh@redhat.com>
Fri, 4 Jun 2021 18:25:20 +0000 (20:25 +0200)
committerAldy Hernandez <aldyh@redhat.com>
Tue, 8 Jun 2021 12:40:15 +0000 (14:40 +0200)
commit4ab8f20348676d209aa8da12baf5da07fa769788
treec8d5f0e683bcb80134990c3b0812a965e34e1d5f
parent30656822b3792712c7a69fe1a0a79739f8f29abc
Implement a context aware pointer equivalency class for use in evrp.

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 pointer equivalency class which
ranger-evrp can use to query what an SSA pointer is currently
equivalent to.  With it, we reduce the 284 cases legacy evrp is getting
to 47.

The API for the pointer equivalency analyzer is the following:

class pointer_equiv_analyzer
{
public:
  pointer_equiv_analyzer (gimple_ranger *r);
  ~pointer_equiv_analyzer ();
  void enter (basic_block);
  void leave (basic_block);
  void visit_stmt (gimple *stmt);
  tree get_equiv (tree ssa) 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_equiv() to get whatever an SSA is equivalent to.

Tested on x86-64 Linux with a regular bootstrap/tests and by comparing
EVRP folds over ranger before and after this patch.

gcc/ChangeLog:

* gimple-ssa-evrp.c (class ssa_equiv_stack): New.
(ssa_equiv_stack::ssa_equiv_stack): New.
(ssa_equiv_stack::~ssa_equiv_stack): New.
(ssa_equiv_stack::enter): New.
(ssa_equiv_stack::leave): New.
(ssa_equiv_stack::push_replacement): New.
(ssa_equiv_stack::get_replacement): New.
(is_pointer_ssa): New.
(class pointer_equiv_analyzer): New.
(pointer_equiv_analyzer::pointer_equiv_analyzer): New.
(pointer_equiv_analyzer::~pointer_equiv_analyzer): New.
(pointer_equiv_analyzer::set_global_equiv): New.
(pointer_equiv_analyzer::set_cond_equiv): New.
(pointer_equiv_analyzer::get_equiv): New.
(pointer_equiv_analyzer::enter): New.
(pointer_equiv_analyzer::leave): New.
(pointer_equiv_analyzer::get_equiv_expr): New.
(pta_valueize): New.
(pointer_equiv_analyzer::visit_stmt): New.
(pointer_equiv_analyzer::visit_edge): New.
(hybrid_folder::value_of_expr): Call PTA.
(hybrid_folder::value_on_edge): Same.
(hybrid_folder::pre_fold_bb): New.
(hybrid_folder::post_fold_bb): New.
(hybrid_folder::pre_fold_stmt): New.
(rvrp_folder::pre_fold_bb): New.
(rvrp_folder::post_fold_bb): New.
(rvrp_folder::pre_fold_stmt): New.
(rvrp_folder::value_of_expr): Call PTA.
(rvrp_folder::value_on_edge): Same.
gcc/gimple-ssa-evrp.c