path solver: Add relation support.

This patch adds relational support to the path solver.  It uses a
path_oracle that keeps track of relations within a path which are
augmented by relations on entry to the path.  With it, range_of_stmt,
range_of_expr, and friends can give relation aware answers.

gcc/ChangeLog:

	* gimple-range-fold.h (class fur_source): Make oracle protected.
	* gimple-range-path.cc (path_range_query::path_range_query): Add
	resolve argument.  Initialize oracle.
	(path_range_query::~path_range_query): Delete oracle.
	(path_range_query::range_of_stmt): Adapt to use relations.
	(path_range_query::precompute_ranges): Pre-compute relations.
	(class jt_fur_source): New
	(jt_fur_source::jt_fur_source): New.
	(jt_fur_source::register_relation): New.
	(jt_fur_source::query_relation): New.
	(path_range_query::precompute_relations): New.
	(path_range_query::precompute_phi_relations): New.
	* gimple-range-path.h (path_range_query): Add resolve argument.
	Add oracle, precompute_relations, precompute_phi_relations.
	* tree-ssa-threadbackward.c (back_threader::back_threader): Pass
	resolve argument to solver.

4 files changed, 200 insertions, 23 deletions

diff --git a/gcc/gimple-range-fold.h b/gcc/gimple-range-fold.h
index d62d29b..bc0874b 100644
--- a/gcc/gimple-range-fold.h
+++ b/gcc/gimple-range-fold.h
@@ -160,7 +160,7 @@ public:
 				  tree op2) OVERRIDE;
   virtual void register_relation (edge e, relation_kind k, tree op1,
 				  tree op2) OVERRIDE;
-private:
+protected:
   relation_oracle *m_oracle;
 };
 
diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 10b018b..b3040c9 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -30,11 +30,13 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-pretty-print.h"
 #include "gimple-range-path.h"
 #include "ssa.h"
+#include "tree-cfg.h"
+#include "gimple-iterator.h"
 
 // Internal construct to help facilitate debugging of solver.
 #define DEBUG_SOLVER (0 && dump_file)
 
-path_range_query::path_range_query (gimple_ranger &ranger)
+path_range_query::path_range_query (gimple_ranger &ranger, bool resolve)
   : m_ranger (ranger)
 {
   if (DEBUG_SOLVER)
@@ -43,12 +45,15 @@ path_range_query::path_range_query (gimple_ranger &ranger)
   m_cache = new ssa_global_cache;
   m_has_cache_entry = BITMAP_ALLOC (NULL);
   m_path = NULL;
+  m_resolve = resolve;
+  m_oracle = new path_oracle (ranger.oracle ());
 }
 
 path_range_query::~path_range_query ()
 {
   BITMAP_FREE (m_has_cache_entry);
   delete m_cache;
+  delete m_oracle;
 }
 
 // Mark cache entry for NAME as unused.
@@ -161,22 +166,6 @@ path_range_query::unreachable_path_p ()
   return m_undefined_path;
 }
 
-// Return the range of STMT at the end of the path being analyzed.
-
-bool
-path_range_query::range_of_stmt (irange &r, gimple *stmt, tree)
-{
-  tree type = gimple_range_type (stmt);
-
-  if (!irange::supports_type_p (type))
-    return false;
-
-  if (!fold_range (r, stmt, this))
-    r.set_varying (type);
-
-  return true;
-}
-
 // Initialize the current path to PATH.  The current block is set to
 // the entry block to the path.
 //
@@ -371,6 +360,12 @@ path_range_query::precompute_ranges (const vec<basic_block> &path,
   m_imports = imports;
   m_undefined_path = false;
 
+  if (m_resolve)
+    {
+      m_oracle->reset_path ();
+      precompute_relations (path);
+    }
+
   if (DEBUG_SOLVER)
     {
       fprintf (dump_file, "\npath_range_query: precompute_ranges for path: ");
@@ -400,3 +395,178 @@ path_range_query::precompute_ranges (const vec<basic_block> &path,
   if (DEBUG_SOLVER)
     dump (dump_file);
 }
+
+// A folding aid used to register and query relations along a path.
+// When queried, it returns relations as they would appear on exit to
+// the path.
+//
+// Relations are registered on entry so the path_oracle knows which
+// block to query the root oracle at when a relation lies outside the
+// path.  However, when queried we return the relation on exit to the
+// path, since the root_oracle ignores the registered.
+
+class jt_fur_source : public fur_depend
+{
+public:
+  jt_fur_source (gimple *s, path_range_query *, gori_compute *,
+		 const vec<basic_block> &);
+  relation_kind query_relation (tree op1, tree op2) override;
+  void register_relation (gimple *, relation_kind, tree op1, tree op2) override;
+  void register_relation (edge, relation_kind, tree op1, tree op2) override;
+private:
+  basic_block m_entry;
+};
+
+jt_fur_source::jt_fur_source (gimple *s,
+			      path_range_query *query,
+			      gori_compute *gori,
+			      const vec<basic_block> &path)
+  : fur_depend (s, gori, query)
+{
+  gcc_checking_assert (!path.is_empty ());
+
+  m_entry = path[path.length () - 1];
+
+  if (dom_info_available_p (CDI_DOMINATORS))
+    m_oracle = query->oracle ();
+  else
+    m_oracle = NULL;
+}
+
+// Ignore statement and register relation on entry to path.
+
+void
+jt_fur_source::register_relation (gimple *, relation_kind k, tree op1, tree op2)
+{
+  if (m_oracle)
+    m_oracle->register_relation (m_entry, k, op1, op2);
+}
+
+// Ignore edge and register relation on entry to path.
+
+void
+jt_fur_source::register_relation (edge, relation_kind k, tree op1, tree op2)
+{
+  if (m_oracle)
+    m_oracle->register_relation (m_entry, k, op1, op2);
+}
+
+relation_kind
+jt_fur_source::query_relation (tree op1, tree op2)
+{
+  if (!m_oracle)
+    return VREL_NONE;
+
+  if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
+    return VREL_NONE;
+
+  return m_oracle->query_relation (m_entry, op1, op2);
+}
+
+// Return the range of STMT at the end of the path being analyzed.
+
+bool
+path_range_query::range_of_stmt (irange &r, gimple *stmt, tree)
+{
+  tree type = gimple_range_type (stmt);
+
+  if (!irange::supports_type_p (type))
+    return false;
+
+  // If resolving unknowns, fold the statement as it would have
+  // appeared at the end of the path.
+  if (m_resolve)
+    {
+      fold_using_range f;
+      jt_fur_source src (stmt, this, &m_ranger.gori (), *m_path);
+      if (!f.fold_stmt (r, stmt, src))
+	r.set_varying (type);
+    }
+  // Otherwise, use the global ranger to fold it as it would appear in
+  // the original IL.  This is more conservative, but faster.
+  else if (!fold_range (r, stmt, this))
+    r.set_varying (type);
+
+  return true;
+}
+
+// Precompute relations on a path.  This involves two parts: relations
+// along the conditionals joining a path, and relations determined by
+// examining PHIs.
+
+void
+path_range_query::precompute_relations (const vec<basic_block> &path)
+{
+  if (!dom_info_available_p (CDI_DOMINATORS))
+    return;
+
+  jt_fur_source src (NULL, this, &m_ranger.gori (), path);
+  basic_block prev = NULL;
+  for (unsigned i = path.length (); i > 0; --i)
+    {
+      basic_block bb = path[i - 1];
+      gimple *stmt = last_stmt (bb);
+
+      precompute_phi_relations (bb, prev);
+
+      // Compute relations in outgoing edges along the path.  Skip the
+      // final conditional which we don't know yet.
+      if (i > 1
+	  && stmt
+	  && gimple_code (stmt) == GIMPLE_COND
+	  && irange::supports_type_p (TREE_TYPE (gimple_cond_lhs (stmt))))
+	{
+	  basic_block next = path[i - 2];
+	  int_range<2> r;
+	  gcond *cond = as_a<gcond *> (stmt);
+
+	  if (EDGE_SUCC (bb, 0)->dest == next)
+	    gcond_edge_range (r, EDGE_SUCC (bb, 0));
+	  else if (EDGE_SUCC (bb, 1)->dest == next)
+	    gcond_edge_range (r, EDGE_SUCC (bb, 1));
+	  else
+	    gcc_unreachable ();
+
+	  edge e0 = EDGE_SUCC (bb, 0);
+	  edge e1 = EDGE_SUCC (bb, 1);
+	  src.register_outgoing_edges (cond, r, e0, e1);
+	}
+      prev = bb;
+    }
+}
+
+// Precompute relations for each PHI in BB.  For example:
+//
+//   x_5 = PHI<y_9(5),...>
+//
+// If the path flows through BB5, we can register that x_5 == y_9.
+
+void
+path_range_query::precompute_phi_relations (basic_block bb, basic_block prev)
+{
+  if (prev == NULL)
+    return;
+
+  basic_block entry = entry_bb ();
+  edge e_in = find_edge (prev, bb);
+  gcc_checking_assert (e_in);
+
+  for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter);
+       gsi_next (&iter))
+    {
+      gphi *phi = iter.phi ();
+      tree result = gimple_phi_result (phi);
+      unsigned nargs = gimple_phi_num_args (phi);
+
+      for (size_t i = 0; i < nargs; ++i)
+	if (e_in == gimple_phi_arg_edge (phi, i))
+	  {
+	    tree arg = gimple_phi_arg_def (phi, i);
+
+	    if (gimple_range_ssa_p (arg))
+	      m_oracle->register_relation (entry, EQ_EXPR, arg, result);
+
+	    break;
+	  }
+    }
+}
diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
index c75721f..d12fd7743 100644
--- a/gcc/gimple-range-path.h
+++ b/gcc/gimple-range-path.h
@@ -35,13 +35,14 @@ along with GCC; see the file COPYING3.  If not see
 class path_range_query : public range_query
 {
 public:
-  path_range_query (class gimple_ranger &ranger);
+  path_range_query (class gimple_ranger &ranger, bool resolve);
   virtual ~path_range_query ();
   void precompute_ranges (const vec<basic_block> &path,
 			  const bitmap_head *imports);
   bool range_of_expr (irange &r, tree name, gimple * = NULL) override;
   bool range_of_stmt (irange &r, gimple *, tree name = NULL) override;
   bool unreachable_path_p ();
+  path_oracle *oracle () { return m_oracle; }
   void dump (FILE *) override;
   void debug ();
 
@@ -58,6 +59,8 @@ private:
   void precompute_ranges_in_block (basic_block bb);
   void adjust_for_non_null_uses (basic_block bb);
   void ssa_range_in_phi (irange &r, gphi *phi);
+  void precompute_relations (const vec<basic_block> &);
+  void precompute_phi_relations (basic_block bb, basic_block prev);
 
   // Path navigation.
   void set_path (const vec<basic_block> &);
@@ -79,12 +82,16 @@ private:
   // Path being analyzed.
   const vec<basic_block> *m_path;
 
-  // Current path position.
-  unsigned m_pos;
-
   const bitmap_head *m_imports;
   gimple_ranger &m_ranger;
   non_null_ref m_non_null;
+  path_oracle *m_oracle;
+
+  // Current path position.
+  unsigned m_pos;
+
+  // Use ranger to resolve anything not known on entry.
+  bool m_resolve;
 
   // Set if there were any undefined expressions while pre-calculating path.
   bool m_undefined_path;
diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index c6530d3..9554207 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -122,7 +122,7 @@ const edge back_threader::UNREACHABLE_EDGE = (edge) -1;
 back_threader::back_threader (bool speed_p)
   : m_registry (param_max_fsm_thread_paths),
     m_profit (speed_p),
-    m_solver (m_ranger)
+    m_solver (m_ranger, /*resolve=*/false)
 {
   m_last_stmt = NULL;
   m_imports = BITMAP_ALLOC (NULL);