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

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

[Aldy Hernandez]

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

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

[Aldy Hernandez]

Sorry, meant to append... "OK for trunk?" :)

On Mon, Jun 7, 2021 at 12:10 PM Aldy Hernandez <aldyh@redhat.com> 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.
>
> 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
>

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

[Richard Biener]

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.

Thanks,
Richard.

> 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
>

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

[Aldy Hernandez]

[-- Attachment #1: Type: text/plain, Size: 2306 bytes --]



On 6/7/21 3:30 PM, Richard Biener 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

Good point.  Renaming done.  I've adjusted the changelog and commit 
message as well.

Thanks.
Aldy

[-- Attachment #2: 0001-Implement-a-context-aware-pointer-equivalency-class-.patch --]
[-- Type: text/x-patch, Size: 14851 bytes --]

From 0b1f6d28a4cdaeb9e0a6285050a5b35eca86829d Mon Sep 17 00:00:00 2001
From: Aldy Hernandez <aldyh@redhat.com>
Date: Fri, 4 Jun 2021 20:25:20 +0200
Subject: [PATCH] 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 | 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);
 }
 
-- 
2.31.1

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

[Martin Sebor]

On 6/7/21 12:29 PM, Aldy Hernandez via Gcc-patches wrote:
> 
> 
> On 6/7/21 3:30 PM, Richard Biener 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
> 
> Good point.  Renaming done.  I've adjusted the changelog and commit 
> message as well.

Mostly just a question of the type choices in the implementation
of the ssa_equiv_stack class: m_stack is an auto_vec while
m_replacements is a plain array.  I'd expect both to be the same
(auto_vec).  Is there a reason for this choice?

If not, I'd suggest to use auto_vec.  That way the ssa_equiv_stack
class shouldn't need a dtor (auto_vec doesn't need to be explicitly
released before it's destroyed), though it should delete its copy
and assignment.

Martin

> 
> Thanks.
> Aldy

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

[Aldy Hernandez]

On 6/9/21 7:10 PM, Martin Sebor wrote:
> On 6/7/21 12:29 PM, Aldy Hernandez via Gcc-patches wrote:
>>

> Mostly just a question of the type choices in the implementation
> of the ssa_equiv_stack class: m_stack is an auto_vec while
> m_replacements is a plain array.  I'd expect both to be the same
> (auto_vec).  Is there a reason for this choice?
> 
> If not, I'd suggest to use auto_vec.  That way the ssa_equiv_stack
> class shouldn't need a dtor (auto_vec doesn't need to be explicitly
> released before it's destroyed), though it should delete its copy
> and assignment.

TBH, the ssa_equiv_stack was lifted from evrp_range_analyzer (there are 
also 2 more copies of the same mechanism in tree-ssa-scopedtables.h). 
The code there already used an auto_vec, so I left that.  However, for a 
mere array of trees, I thought it'd be simpler to use new/delete.  Which 
in retrospect was easy to get wrong, as can be seen by:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100984

Would something like the code below work?  It should also fix the PR.

Thanks.
Aldy

diff --git a/gcc/gimple-ssa-evrp.c b/gcc/gimple-ssa-evrp.c
index 7e1cf51239a..808d47506be 100644
--- a/gcc/gimple-ssa-evrp.c
+++ b/gcc/gimple-ssa-evrp.c
@@ -61,19 +61,18 @@ public:

  private:
    auto_vec<std::pair <tree, tree>> m_stack;
-  tree *m_replacements;
+  auto_vec<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] ();
+  m_replacements.safe_grow_cleared (num_ssa_names);
  }

  ssa_equiv_stack::~ssa_equiv_stack ()
  {
    m_stack.release ();
-  delete m_replacements;
  }

  // Pushes a marker at the given point.

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

[Martin Sebor]

On 6/9/21 12:50 PM, Aldy Hernandez wrote:
> 
> 
> On 6/9/21 7:10 PM, Martin Sebor wrote:
>> On 6/7/21 12:29 PM, Aldy Hernandez via Gcc-patches wrote:
>>>
> 
>> Mostly just a question of the type choices in the implementation
>> of the ssa_equiv_stack class: m_stack is an auto_vec while
>> m_replacements is a plain array.  I'd expect both to be the same
>> (auto_vec).  Is there a reason for this choice?
>>
>> If not, I'd suggest to use auto_vec.  That way the ssa_equiv_stack
>> class shouldn't need a dtor (auto_vec doesn't need to be explicitly
>> released before it's destroyed), though it should delete its copy
>> and assignment.
> 
> TBH, the ssa_equiv_stack was lifted from evrp_range_analyzer (there are 
> also 2 more copies of the same mechanism in tree-ssa-scopedtables.h). 
> The code there already used an auto_vec, so I left that.  However, for a 
> mere array of trees, I thought it'd be simpler to use new/delete.  Which 
> in retrospect was easy to get wrong, as can be seen by:
> 
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100984
> 
> Would something like the code below work?  It should also fix the PR.
> 
> Thanks.
> Aldy
> 
> diff --git a/gcc/gimple-ssa-evrp.c b/gcc/gimple-ssa-evrp.c
> index 7e1cf51239a..808d47506be 100644
> --- a/gcc/gimple-ssa-evrp.c
> +++ b/gcc/gimple-ssa-evrp.c
> @@ -61,19 +61,18 @@ public:
> 
>   private:
>     auto_vec<std::pair <tree, tree>> m_stack;
> -  tree *m_replacements;
> +  auto_vec<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] ();
> +  m_replacements.safe_grow_cleared (num_ssa_names);
>   }
> 
>   ssa_equiv_stack::~ssa_equiv_stack ()
>   {
>     m_stack.release ();
> -  delete m_replacements;
>   }

Yes, this is what I was suggesting, with the additional removal of
the dtor above (since release() is called from the auto_vec dtor).

(Once auto_vec is safe to copy and assign we'll also get copy and
assignment for nothing.)

Martin

PS Enhancing -Wmismatched-new-delete to detect the bug in PR 100984
is on my to do list.

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

[Andrew MacLeod]

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.

Andrew

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

[Aldy Hernandez]

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.

Aldy

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

[Andrew MacLeod]

On 6/8/21 2:26 AM, Aldy Hernandez wrote:
>
>
> 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.
>
> Aldy
>
patch is OK, btw..

Andrew

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

[Richard Biener]

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
>
>

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

[Andrew MacLeod]

On 6/8/21 3:26 AM, Richard Biener wrote:
> On Mon, Jun 7, 2021 at 9:20 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>>
>> 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

The initial code will be a bit basic, but it can be educated as we go 
along :-)

Its currently tied into ranger just because as ranger processes 
statements it registers any relations it sees.. the oracle organizes 
these and can answer questions on anything it has seen.

It is otherwise independent of ranger. It is dominance based, and there 
is no reason relations cant be queried and registered by any pass doing 
a DOM walk without ranger.  It benefits from ranger in that sometime 
relations are refined when we know ranges  (ie for unsigned math)

     a_2 = b_4 + 6

if we know the range of b_4 will not cause an overflow, then we could 
set a_2 > b_4.. otherwise we cant..  Wiring it with ranger also removes 
the dependency on a DOM walk as ranger sorts the ordering out as needed.

It is driven by data provided by range-ops and is more of a data 
propagation/lookup mechanism than anything. There are a number of cases 
we don't currently register relations simply because we have not flushed 
out the various tree code instructions.   We'll get to those eventually. 
I expect a number of the PRs will eventually be fixed primarily by 
adding code to range-ops .

It also only does first order relations so far...  I'll get to 
transitives and other things as well.


> 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).

I don't think the iteration is an issue,  ranger iterates to some degree 
as well, and some statement are registered multiple times. I believe it 
intersects with any known relation, so if an iteration causes a relation 
to become "better" it should be updated.

The API is for registering is pretty straightforward:

   void register_relation (gimple *stmt, relation_kind k, tree op1, tree 
op2);
   void register_relation (edge e, relation_kind k, tree op1, tree op2);

so all you'd have to do when a < b is encountered is to register  (a 
LT_EXPR b) on the true edge, and (a GE_EXPR b) on the false edge.  Then 
any queries downstream should be reflected.



> 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.
>
yeah, so a GT_EXPR B is registered on the true edge.  Then when 
processing c = a != b,  you can determine that a NE_EXPR b intersected 
with a GT_EXPR b result in  a GT_EXPR b... which folds to a 1.

This is all also available with the range-op API additions such that you 
can simply call :

rangerop->fold_range (stmt(c = a != b), range_of_a, range_of_b, GT_EXPR 
(relation of a to b)  and the range returned will be [1,1].

The actual ranges in this case are irrelevant, but arent for some other 
kinds of stmts.

Likewise, simply asking ranger for the range of c will likewise return 
[1,1], the relation processing is all integrated behind the scenes in 
ranger..

As we start using the code more, we may find we want/need a few more 
wrappers around some of this so that you can transparently ask what the 
RHS folds to without any ranger present, just with relations.  Those'll 
be fairly trivial to add...

The relation oracle is going to be directly accessible from the 
get_range_query(cfun) range_query class.  I'll do a big writeup when i 
submit it and we should be able to make it usable in any of those places.

Andrew

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

[Richard Biener]

On Tue, Jun 8, 2021 at 4:31 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>
> On 6/8/21 3:26 AM, Richard Biener wrote:
> > On Mon, Jun 7, 2021 at 9:20 PM Andrew MacLeod <amacleod@redhat.com> wrote:
> >>
> >> 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
>
> The initial code will be a bit basic, but it can be educated as we go
> along :-)
>
> Its currently tied into ranger just because as ranger processes
> statements it registers any relations it sees.. the oracle organizes
> these and can answer questions on anything it has seen.
>
> It is otherwise independent of ranger. It is dominance based, and there
> is no reason relations cant be queried and registered by any pass doing
> a DOM walk without ranger.  It benefits from ranger in that sometime
> relations are refined when we know ranges  (ie for unsigned math)
>
>      a_2 = b_4 + 6
>
> if we know the range of b_4 will not cause an overflow, then we could
> set a_2 > b_4.. otherwise we cant..  Wiring it with ranger also removes
> the dependency on a DOM walk as ranger sorts the ordering out as needed.
>
> It is driven by data provided by range-ops and is more of a data
> propagation/lookup mechanism than anything. There are a number of cases
> we don't currently register relations simply because we have not flushed
> out the various tree code instructions.   We'll get to those eventually.
> I expect a number of the PRs will eventually be fixed primarily by
> adding code to range-ops .
>
> It also only does first order relations so far...  I'll get to
> transitives and other things as well.
>
>
> > 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).
>
> I don't think the iteration is an issue,  ranger iterates to some degree
> as well, and some statement are registered multiple times. I believe it
> intersects with any known relation, so if an iteration causes a relation
> to become "better" it should be updated.

Note VN does optimistic iteration thus relations will become only "worse",
thus we somehow need to be able to remove relations we added during
the last iteration.  That is, in the first iteration a if (a > b) might be
registered as a > 1 when b has (optimistic) value b but in the second
we have to make it a > b when b dropped to varying for example.

The optimistic part of VN is that it treats all edges as not executable
initially and thus it ignores values on non-executable edges in PHI
nodes.

> The API is for registering is pretty straightforward:
>
>    void register_relation (gimple *stmt, relation_kind k, tree op1, tree
> op2);
>    void register_relation (edge e, relation_kind k, tree op1, tree op2);
>
> so all you'd have to do when a < b is encountered is to register  (a
> LT_EXPR b) on the true edge, and (a GE_EXPR b) on the false edge.  Then
> any queries downstream should be reflected.
>
>
>
> > 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.
> >
> yeah, so a GT_EXPR B is registered on the true edge.  Then when
> processing c = a != b,  you can determine that a NE_EXPR b intersected
> with a GT_EXPR b result in  a GT_EXPR b... which folds to a 1.
>
> This is all also available with the range-op API additions such that you
> can simply call :
>
> rangerop->fold_range (stmt(c = a != b), range_of_a, range_of_b, GT_EXPR
> (relation of a to b)  and the range returned will be [1,1].
>
> The actual ranges in this case are irrelevant, but arent for some other
> kinds of stmts.
>
> Likewise, simply asking ranger for the range of c will likewise return
> [1,1], the relation processing is all integrated behind the scenes in
> ranger..
>
> As we start using the code more, we may find we want/need a few more
> wrappers around some of this so that you can transparently ask what the
> RHS folds to without any ranger present, just with relations.  Those'll
> be fairly trivial to add...
>
> The relation oracle is going to be directly accessible from the
> get_range_query(cfun) range_query class.  I'll do a big writeup when i
> submit it and we should be able to make it usable in any of those places.

OK, so using this from DOM should be pretty straight-forward (you may
want to try to use it there as proof of API sanity).  When it's in I'll see if
it fits (iterative) VN.

Richard.

> Andrew
>
>
>

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

[Andrew MacLeod]

On 6/9/21 7:32 AM, Richard Biener wrote:
> On Tue, Jun 8, 2021 at 4:31 PM Andrew MacLeod <amacleod@redhat.com> wrote:
>>
>> an iteration causes a relation
>> to become "better" it should be updated.
>>> 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).
> Note VN does optimistic iteration thus relations will become only "worse",
> thus we somehow need to be able to remove relations we added during
> the last iteration.  That is, in the first iteration a if (a > b) might be
> registered as a > 1 when b has (optimistic) value b but in the second
> we have to make it a > b when b dropped to varying for example.
>
> The optimistic part of VN is that it treats all edges as not executable
> initially and thus it ignores values on non-executable edges in PHI
> nodes.
>
Yeah, haven't had to do that yet.  The add method currently does an 
intersection with any relation it finds already present, it shouldn't be 
too much work to add an alternate add routine that says "replace".  In 
fact, that may be also be adequate for my purposes, since typically the 
second time a relation is added, it *should* be either the same, or 
"better" for me.   The tricky part is I think it may already include any 
relation that dominates the currently location..  but that is addressable.

I'll keep an eye on this as I'm prepping the code and writing it up.

>> The API is for registering is pretty straightforward:
>>
>>     void register_relation (gimple *stmt, relation_kind k, tree op1, tree
>> op2);
>>     void register_relation (edge e, relation_kind k, tree op1, tree op2);
>>
>> so all you'd have to do when a < b is encountered is to register  (a
>> LT_EXPR b) on the true edge, and (a GE_EXPR b) on the false edge.  Then
>> any queries downstream should be reflected.
>>
>>
>>
>>> 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.
>>>
>>>
>>>
>>> As we start using the code more, we may find we want/need a few more
>>> wrappers around some of this so that you can transparently ask what the
>>> RHS folds to without any ranger present, just with relations.  Those'll
>>> be fairly trivial to add...
>>>
>>> The relation oracle is going to be directly accessible from the
>>> get_range_query(cfun) range_query class.  I'll do a big writeup when i
>>> submit it and we should be able to make it usable in any of those places.
> OK, so using this from DOM should be pretty straight-forward (you may
> want to try to use it there as proof of API sanity).  When it's in I'll see if
> it fits (iterative) VN.
>
Yeah, it should be quite straightforward as part of DOM.. and should be 
easy to set and query in parallel with whats there to verify its getting 
the same results.  Famous last words.  But yes, this would be further 
proof its evaluating what we expect on top of doing what EVRP did.

Slight delay while I'm sorting out some minor API issues to enable using 
this without ranger right off the bat, as well as interaction with some 
recent changes I made.

Andrew