[gcc r12-1293] Implement a context aware pointer equivalency class for use in evrp.

[gcc r12-1293] Implement a context aware pointer equivalency class for use in evrp.

[Aldy Hernandez]

https://gcc.gnu.org/g:4ab8f20348676d209aa8da12baf5da07fa769788

commit r12-1293-g4ab8f20348676d209aa8da12baf5da07fa769788
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Fri Jun 4 20:25:20 2021 +0200

    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.

Diff:
---
 gcc/gimple-ssa-evrp.c | 354 +++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 352 insertions(+), 2 deletions(-)

diff --git a/gcc/gimple-ssa-evrp.c b/gcc/gimple-ssa-evrp.c
index 118d10365a0..7e1cf51239a 100644
--- a/gcc/gimple-ssa-evrp.c
+++ b/gcc/gimple-ssa-evrp.c
@@ -42,6 +42,307 @@ along with GCC; see the file COPYING3.  If not see
 #include "vr-values.h"
 #include "gimple-ssa-evrp-analyze.h"
 #include "gimple-range.h"
+#include "fold-const.h"
+
+// Unwindable SSA equivalence table for pointers.
+//
+// The main query point is get_replacement() which returns what a
+// given SSA can be replaced with in the current scope.
+
+class ssa_equiv_stack
+{
+public:
+  ssa_equiv_stack ();
+  ~ssa_equiv_stack ();
+  void enter (basic_block);
+  void leave (basic_block);
+  void push_replacement (tree name, tree replacement);
+  tree get_replacement (tree name) const;
+
+private:
+  auto_vec<std::pair <tree, tree>> m_stack;
+  tree *m_replacements;
+  const std::pair <tree, tree> m_marker = std::make_pair (NULL, NULL);
+};
+
+ssa_equiv_stack::ssa_equiv_stack ()
+{
+  m_replacements = new tree[num_ssa_names] ();
+}
+
+ssa_equiv_stack::~ssa_equiv_stack ()
+{
+  m_stack.release ();
+  delete m_replacements;
+}
+
+// Pushes a marker at the given point.
+
+void
+ssa_equiv_stack::enter (basic_block)
+{
+  m_stack.safe_push (m_marker);
+}
+
+// Pops the stack to the last marker, while performing replacements
+// along the way.
+
+void
+ssa_equiv_stack::leave (basic_block)
+{
+  gcc_checking_assert (!m_stack.is_empty ());
+  while (m_stack.last () != m_marker)
+    {
+      std::pair<tree, tree> e = m_stack.pop ();
+      m_replacements[SSA_NAME_VERSION (e.first)] = e.second;
+    }
+  m_stack.pop ();
+}
+
+// Set the equivalence of NAME to REPLACEMENT.
+
+void
+ssa_equiv_stack::push_replacement (tree name, tree replacement)
+{
+  tree old = m_replacements[SSA_NAME_VERSION (name)];
+  m_replacements[SSA_NAME_VERSION (name)] = replacement;
+  m_stack.safe_push (std::make_pair (name, old));
+}
+
+// Return the equivalence of NAME.
+
+tree
+ssa_equiv_stack::get_replacement (tree name) const
+{
+  return m_replacements[SSA_NAME_VERSION (name)];
+}
+
+// Return TRUE if EXPR is an SSA holding a pointer.
+
+static bool inline
+is_pointer_ssa (tree expr)
+{
+  return TREE_CODE (expr) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (expr));
+}
+
+// Simple context-aware pointer equivalency analyzer that returns what
+// a pointer SSA name is equivalent to at a given point during a walk
+// of the IL.
+//
+// Note that global equivalency take priority over conditional
+// equivalency.  That is, p = &q takes priority over a later p == &t.
+//
+// This class is meant to be called during a DOM walk.
+
+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;
+
+private:
+  void visit_edge (edge e);
+  tree get_equiv_expr (tree_code code, tree expr) const;
+  void set_global_equiv (tree ssa, tree pointee);
+  void set_cond_equiv (tree ssa, tree pointee);
+
+  gimple_ranger *m_ranger;
+  // Global pointer equivalency indexed by SSA_NAME_VERSION.
+  tree *m_global_points;
+  // Conditional pointer equivalency.
+  ssa_equiv_stack m_cond_points;
+};
+
+pointer_equiv_analyzer::pointer_equiv_analyzer (gimple_ranger *r)
+{
+  m_ranger = r;
+  m_global_points = new tree[num_ssa_names] ();
+}
+
+pointer_equiv_analyzer::~pointer_equiv_analyzer ()
+{
+  delete m_global_points;
+}
+
+// Set the global pointer equivalency for SSA to POINTEE.
+
+void
+pointer_equiv_analyzer::set_global_equiv (tree ssa, tree pointee)
+{
+  m_global_points[SSA_NAME_VERSION (ssa)] = pointee;
+}
+
+// Set the conditional pointer equivalency for SSA to POINTEE.
+
+void
+pointer_equiv_analyzer::set_cond_equiv (tree ssa, tree pointee)
+{
+  m_cond_points.push_replacement (ssa, pointee);
+}
+
+// Return the current pointer equivalency info for SSA, or NULL if
+// none is available.  Note that global info takes priority over
+// conditional info.
+
+tree
+pointer_equiv_analyzer::get_equiv (tree ssa) const
+{
+  tree ret = m_global_points[SSA_NAME_VERSION (ssa)];
+  if (ret)
+    return ret;
+  return m_cond_points.get_replacement (ssa);
+}
+
+// Method to be called on entry to a BB.
+
+void
+pointer_equiv_analyzer::enter (basic_block bb)
+{
+  m_cond_points.enter (bb);
+
+  for (gphi_iterator iter = gsi_start_phis (bb);
+       !gsi_end_p (iter);
+       gsi_next (&iter))
+    {
+      gphi *phi = iter.phi ();
+      tree lhs = gimple_phi_result (phi);
+      if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
+	continue;
+      tree arg0 = gimple_phi_arg_def (phi, 0);
+      if (TREE_CODE (arg0) == SSA_NAME && !is_gimple_min_invariant (arg0))
+	arg0 = get_equiv (arg0);
+      if (arg0 && is_gimple_min_invariant (arg0))
+	{
+	  // If all the PHI args point to the same place, set the
+	  // pointer equivalency info for the PHI result.  This can
+	  // happen for passes that create redundant PHIs like
+	  // PHI<&foo, &foo> or PHI<&foo>.
+	  for (size_t i = 1; i < gimple_phi_num_args (phi); ++i)
+	    {
+	      tree argi = gimple_phi_arg_def (phi, i);
+	      if (TREE_CODE (argi) == SSA_NAME
+		  && !is_gimple_min_invariant (argi))
+		argi = get_equiv (argi);
+	      if (!argi || !operand_equal_p (arg0, argi))
+		return;
+	    }
+	  set_global_equiv (lhs, arg0);
+	}
+    }
+
+  edge pred = single_pred_edge_ignoring_loop_edges (bb, false);
+  if (pred)
+    visit_edge (pred);
+}
+
+// Method to be called on exit from a BB.
+
+void
+pointer_equiv_analyzer::leave (basic_block bb)
+{
+  m_cond_points.leave (bb);
+}
+
+// Helper function to return the pointer equivalency information for
+// EXPR from a gimple statement with CODE.  This returns either the
+// cached pointer equivalency info for an SSA, or an invariant in case
+// EXPR is one (i.e. &foo).  Returns NULL if EXPR is neither an SSA
+// nor an invariant.
+
+tree
+pointer_equiv_analyzer::get_equiv_expr (tree_code code, tree expr) const
+{
+  if (code == SSA_NAME)
+    return get_equiv (expr);
+
+  if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
+      && is_gimple_min_invariant (expr))
+    return expr;
+
+  return NULL;
+}
+
+// Hack to provide context to the gimple fold callback.
+static struct
+{
+  gimple *m_stmt;
+  gimple_ranger *m_ranger;
+  pointer_equiv_analyzer *m_pta;
+} x_fold_context;
+
+// Gimple fold callback.
+static tree
+pta_valueize (tree name)
+{
+  tree ret
+    = x_fold_context.m_ranger->value_of_expr (name, x_fold_context.m_stmt);
+
+  if (!ret && is_pointer_ssa (name))
+    ret = x_fold_context.m_pta->get_equiv (name);
+
+  return ret ? ret : name;
+}
+
+// Method to be called on gimple statements during traversal of the IL.
+
+void
+pointer_equiv_analyzer::visit_stmt (gimple *stmt)
+{
+  if (gimple_code (stmt) != GIMPLE_ASSIGN)
+    return;
+
+  tree lhs = gimple_assign_lhs (stmt);
+  if (!is_pointer_ssa (lhs))
+    return;
+
+  tree rhs = gimple_assign_rhs1 (stmt);
+  rhs = get_equiv_expr (gimple_assign_rhs_code (stmt), rhs);
+  if (rhs)
+    {
+      set_global_equiv (lhs, rhs);
+      return;
+    }
+
+  // If we couldn't find anything, try fold.
+  x_fold_context = { stmt, m_ranger, this};
+  rhs = gimple_fold_stmt_to_constant_1 (stmt, pta_valueize, pta_valueize);
+  if (rhs)
+    {
+      rhs = get_equiv_expr (TREE_CODE (rhs), rhs);
+      if (rhs)
+	{
+	  set_global_equiv (lhs, rhs);
+	  return;
+	}
+    }
+}
+
+// If the edge in E is a conditional that sets a pointer equality, set the
+// conditional pointer equivalency information.
+
+void
+pointer_equiv_analyzer::visit_edge (edge e)
+{
+  gimple *stmt = last_stmt (e->src);
+  tree lhs;
+  // Recognize: x_13 [==,!=] &foo.
+  if (stmt
+      && gimple_code (stmt) == GIMPLE_COND
+      && (lhs = gimple_cond_lhs (stmt))
+      && TREE_CODE (lhs) == SSA_NAME
+      && POINTER_TYPE_P (TREE_TYPE (lhs))
+      && TREE_CODE (gimple_cond_rhs (stmt)) == ADDR_EXPR)
+    {
+      tree_code code = gimple_cond_code (stmt);
+      if ((code == EQ_EXPR && e->flags & EDGE_TRUE_VALUE)
+	  || ((code == NE_EXPR && e->flags & EDGE_FALSE_VALUE)))
+	set_cond_equiv (lhs, gimple_cond_rhs (stmt));
+    }
+}
 
 // This is the classic EVRP folder which uses a dominator walk and pushes
 // ranges into the next block if it is a single predecessor block.
@@ -120,6 +421,7 @@ public:
   {
     m_ranger = enable_ranger (cfun);
     m_simplifier.set_range_query (m_ranger);
+    m_pta = new pointer_equiv_analyzer (m_ranger);
   }
       
   ~rvrp_folder ()
@@ -129,16 +431,23 @@ public:
 
     m_ranger->export_global_ranges ();
     disable_ranger (cfun);
+    delete m_pta;
   }
 
   tree value_of_expr (tree name, gimple *s = NULL) OVERRIDE
   {
-    return m_ranger->value_of_expr (name, s);
+    tree ret = m_ranger->value_of_expr (name, s);
+    if (!ret && is_pointer_ssa (name))
+      ret = m_pta->get_equiv (name);
+    return ret;
   }
 
   tree value_on_edge (edge e, tree name) OVERRIDE
   {
-    return m_ranger->value_on_edge (e, name);
+    tree ret = m_ranger->value_on_edge (e, name);
+    if (!ret && is_pointer_ssa (name))
+      ret = m_pta->get_equiv (name);
+    return ret;
   }
 
   tree value_of_stmt (gimple *s, tree name = NULL) OVERRIDE
@@ -146,6 +455,21 @@ public:
     return m_ranger->value_of_stmt (s, name);
   }
 
+  void pre_fold_bb (basic_block bb) OVERRIDE
+  {
+    m_pta->enter (bb);
+  }
+
+  void post_fold_bb (basic_block bb) OVERRIDE
+  {
+    m_pta->leave (bb);
+  }
+
+  void pre_fold_stmt (gimple *stmt) OVERRIDE
+  {
+    m_pta->visit_stmt (stmt);
+  }
+
   bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE
   {
     return m_simplifier.simplify (gsi);
@@ -155,6 +479,7 @@ private:
   DISABLE_COPY_AND_ASSIGN (rvrp_folder);
   gimple_ranger *m_ranger;
   simplify_using_ranges m_simplifier;
+  pointer_equiv_analyzer *m_pta;
 };
 
 // In a hybrid folder, start with an EVRP folder, and add the required
@@ -186,6 +511,7 @@ public:
 	first = m_ranger;
 	second = &m_range_analyzer;
       }
+    m_pta = new pointer_equiv_analyzer (m_ranger);
   }
 
   ~hybrid_folder ()
@@ -195,6 +521,7 @@ public:
 
     m_ranger->export_global_ranges ();
     disable_ranger (cfun);
+    delete m_pta;
   }
 
   bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE
@@ -213,6 +540,24 @@ public:
       return false;
     }
 
+  void pre_fold_stmt (gimple *stmt) OVERRIDE
+  {
+    evrp_folder::pre_fold_stmt (stmt);
+    m_pta->visit_stmt (stmt);
+  }
+
+  void pre_fold_bb (basic_block bb) OVERRIDE
+  {
+    evrp_folder::pre_fold_bb (bb);
+    m_pta->enter (bb);
+  }
+
+  void post_fold_bb (basic_block bb) OVERRIDE
+  {
+    evrp_folder::post_fold_bb (bb);
+    m_pta->leave (bb);
+  }
+
   tree value_of_expr (tree name, gimple *) OVERRIDE;
   tree value_on_edge (edge, tree name) OVERRIDE;
   tree value_of_stmt (gimple *, tree name) OVERRIDE;
@@ -222,6 +567,7 @@ private:
   gimple_ranger *m_ranger;
   range_query *first;
   range_query *second;
+  pointer_equiv_analyzer *m_pta;
   tree choose_value (tree evrp_val, tree ranger_val);
 };
 
@@ -231,6 +577,8 @@ hybrid_folder::value_of_expr (tree op, gimple *stmt)
 {
   tree evrp_ret = evrp_folder::value_of_expr (op, stmt);
   tree ranger_ret = m_ranger->value_of_expr (op, stmt);
+  if (!ranger_ret && is_pointer_ssa (op))
+    ranger_ret = m_pta->get_equiv (op);
   return choose_value (evrp_ret, ranger_ret);
 }
 
@@ -241,6 +589,8 @@ hybrid_folder::value_on_edge (edge e, tree op)
   // via hybrid_folder::value_of_expr, but without an edge.
   tree evrp_ret = evrp_folder::value_of_expr (op, NULL);
   tree ranger_ret = m_ranger->value_on_edge (e, op);
+  if (!ranger_ret && is_pointer_ssa (op))
+    ranger_ret = m_pta->get_equiv (op);
   return choose_value (evrp_ret, ranger_ret);
 }