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

Aldy Hernandez aldyh@redhat.com
Mon Jun 7 10:10:03 GMT 2021


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.

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 points_to_analyzer): New.
	(points_to_analyzer::points_to_analyzer): New.
	(points_to_analyzer::~points_to_analyzer): New.
	(points_to_analyzer::set_global_points_to): New.
	(points_to_analyzer::set_cond_points_to): New.
	(points_to_analyzer::get_points_to): New.
	(points_to_analyzer::enter): New.
	(points_to_analyzer::leave): New.
	(points_to_analyzer::get_points_to_expr): New.
	(pta_valueize): New.
	(points_to_analyzer::visit_stmt): New.
	(points_to_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 | 352 +++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 350 insertions(+), 2 deletions(-)

diff --git a/gcc/gimple-ssa-evrp.c b/gcc/gimple-ssa-evrp.c
index 118d10365a0..6ce32d7b620 100644
--- a/gcc/gimple-ssa-evrp.c
+++ b/gcc/gimple-ssa-evrp.c
@@ -42,6 +42,305 @@ 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 points-to analyzer that returns what an SSA name
+// points-to at a given point during a walk of the IL.
+//
+// Note that global points-to take priority over conditional points-to.  That
+// is, p = q takes priority over a later p == t.
+//
+// This class is meant to be called during a DOM walk.
+
+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 ssa) const;
+
+private:
+  void visit_edge (edge e);
+  tree get_points_to_expr (tree_code code, tree expr) const;
+  void set_global_points_to (tree ssa, tree pointee);
+  void set_cond_points_to (tree ssa, tree pointee);
+
+  gimple_ranger *m_ranger;
+  // Global points-to replacements indexed by SSA_NAME_VERSION.
+  tree *m_global_points;
+  // Conditional points-to replacements.
+  ssa_equiv_stack m_cond_points;
+};
+
+points_to_analyzer::points_to_analyzer (gimple_ranger *r)
+{
+  m_ranger = r;
+  m_global_points = new tree[num_ssa_names] ();
+}
+
+points_to_analyzer::~points_to_analyzer ()
+{
+  delete m_global_points;
+}
+
+// Set the global points-to for SSA to POINTEE.
+
+void
+points_to_analyzer::set_global_points_to (tree ssa, tree pointee)
+{
+  m_global_points[SSA_NAME_VERSION (ssa)] = pointee;
+}
+
+// Set the conditional points-to for SSA to POINTEE.
+
+void
+points_to_analyzer::set_cond_points_to (tree ssa, tree pointee)
+{
+  m_cond_points.push_replacement (ssa, pointee);
+}
+
+// Return the current points-to information for SSA, or NULL if none is
+// available.  Note that global info takes priority over conditional info.
+
+tree
+points_to_analyzer::get_points_to (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
+points_to_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_points_to (arg0);
+      if (arg0 && is_gimple_min_invariant (arg0))
+	{
+	  // If all the PHI args point to the same place, set the
+	  // points-to 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_points_to (argi);
+	      if (!argi || !operand_equal_p (arg0, argi))
+		return;
+	    }
+	  set_global_points_to (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
+points_to_analyzer::leave (basic_block bb)
+{
+  m_cond_points.leave (bb);
+}
+
+// Helper function to return the points-to information for EXPR from a gimple
+// statement with CODE.  This returns either the cached points-to 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
+points_to_analyzer::get_points_to_expr (tree_code code, tree expr) const
+{
+  if (code == SSA_NAME)
+    return get_points_to (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;
+  points_to_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_points_to (name);
+
+  return ret ? ret : name;
+}
+
+// Method to be called on gimple statements during traversal of the IL.
+
+void
+points_to_analyzer::visit_stmt (gimple *stmt)
+{
+  if (gimple_code (stmt) != GIMPLE_ASSIGN)
+    return;
+
+  tree lhs = gimple_assign_lhs (stmt);
+  if (!is_pointer_ssa (lhs))
+    return;
+
+  // Try to get the points-to info from the cache.
+  tree rhs = gimple_assign_rhs1 (stmt);
+  rhs = get_points_to_expr (gimple_assign_rhs_code (stmt), rhs);
+  if (rhs)
+    {
+      set_global_points_to (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_points_to_expr (TREE_CODE (rhs), rhs);
+      if (rhs)
+	{
+	  set_global_points_to (lhs, rhs);
+	  return;
+	}
+    }
+}
+
+// If the edge in E is a conditional that sets a pointer equality, set the
+// conditional points-to information.
+
+void
+points_to_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_points_to (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 +419,7 @@ public:
   {
     m_ranger = enable_ranger (cfun);
     m_simplifier.set_range_query (m_ranger);
+    m_pta = new points_to_analyzer (m_ranger);
   }
       
   ~rvrp_folder ()
@@ -129,16 +429,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_points_to (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_points_to (name);
+    return ret;
   }
 
   tree value_of_stmt (gimple *s, tree name = NULL) OVERRIDE
@@ -146,6 +453,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 +477,7 @@ private:
   DISABLE_COPY_AND_ASSIGN (rvrp_folder);
   gimple_ranger *m_ranger;
   simplify_using_ranges m_simplifier;
+  points_to_analyzer *m_pta;
 };
 
 // In a hybrid folder, start with an EVRP folder, and add the required
@@ -186,6 +509,7 @@ public:
 	first = m_ranger;
 	second = &m_range_analyzer;
       }
+    m_pta = new points_to_analyzer (m_ranger);
   }
 
   ~hybrid_folder ()
@@ -195,6 +519,7 @@ public:
 
     m_ranger->export_global_ranges ();
     disable_ranger (cfun);
+    delete m_pta;
   }
 
   bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE
@@ -213,6 +538,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 +565,7 @@ private:
   gimple_ranger *m_ranger;
   range_query *first;
   range_query *second;
+  points_to_analyzer *m_pta;
   tree choose_value (tree evrp_val, tree ranger_val);
 };
 
@@ -231,6 +575,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_points_to (op);
   return choose_value (evrp_ret, ranger_ret);
 }
 
@@ -241,6 +587,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_points_to (op);
   return choose_value (evrp_ret, ranger_ret);
 }
 
-- 
2.31.1



More information about the Gcc-patches mailing list