path solver: Add related SSAs to solvable set.

The path solver takes an initial set of SSA names which are deemed
interesting.  These are then solved along the path.  Adding any copies
of said SSA names to the list of interesting names yields significantly
better results.  This patch adds said copies to the already provided
list.

Currently this code is guarded by "m_resolve", which is the more
expensive mode, but it would be reasonable to make it available always,
especially since adding more imports usually has minimal impact on the
processing time.  I will investigate and make it universally available
if this is indeed the case.

gcc/ChangeLog:

	* gimple-range-path.cc (path_range_query::add_to_imports): New.
	(path_range_query::add_copies_to_imports): New.
	(path_range_query::precompute_ranges): Call
	add_copies_to_imports.
	* gimple-range-path.h (class path_range_query): Add prototypes
	for add_copies_to_imports and add_to_imports.

2 files changed, 82 insertions, 2 deletions

diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index b86a76f..a8ead3d 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -343,6 +343,71 @@ path_range_query::adjust_for_non_null_uses (basic_block bb)
     }
 }
 
+// If NAME is a supported SSA_NAME, add it the bitmap in IMPORTS.
+
+bool
+path_range_query::add_to_imports (tree name, bitmap imports)
+{
+  if (TREE_CODE (name) == SSA_NAME
+      && irange::supports_type_p (TREE_TYPE (name)))
+    return bitmap_set_bit (imports, SSA_NAME_VERSION (name));
+  return false;
+}
+
+// Add the copies of any SSA names in IMPORTS to IMPORTS.
+//
+// These are hints for the solver.  Adding more elements (within
+// reason) doesn't slow us down, because we don't solve anything that
+// doesn't appear in the path.  On the other hand, not having enough
+// imports will limit what we can solve.
+
+void
+path_range_query::add_copies_to_imports ()
+{
+  auto_vec<tree> worklist (bitmap_count_bits (m_imports));
+  bitmap_iterator bi;
+  unsigned i;
+
+  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+    {
+      tree name = ssa_name (i);
+      worklist.quick_push (name);
+    }
+
+  while (!worklist.is_empty ())
+    {
+      tree name = worklist.pop ();
+      gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+
+      if (is_gimple_assign (def_stmt))
+	{
+	  // ?? Adding assignment copies doesn't get us much.  At the
+	  // time of writing, we got 63 more threaded paths across the
+	  // .ii files from a bootstrap.
+	  add_to_imports (gimple_assign_rhs1 (def_stmt), m_imports);
+	  tree rhs = gimple_assign_rhs2 (def_stmt);
+	  if (rhs && add_to_imports (rhs, m_imports))
+	    worklist.safe_push (rhs);
+	  rhs = gimple_assign_rhs3 (def_stmt);
+	  if (rhs && add_to_imports (rhs, m_imports))
+	    worklist.safe_push (rhs);
+	}
+      else if (gphi *phi = dyn_cast <gphi *> (def_stmt))
+	{
+	  for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
+	    {
+	      edge e = gimple_phi_arg_edge (phi, i);
+	      tree arg = gimple_phi_arg (phi, i)->def;
+
+	      if (TREE_CODE (arg) == SSA_NAME
+		  && m_path->contains (e->src)
+		  && bitmap_set_bit (m_imports, SSA_NAME_VERSION (arg)))
+		worklist.safe_push (arg);
+	    }
+	}
+    }
+}
+
 // Precompute the ranges for IMPORTS along PATH.
 //
 // IMPORTS are the set of SSA names, any of which could potentially
@@ -353,11 +418,12 @@ path_range_query::precompute_ranges (const vec<basic_block> &path,
 				     const bitmap_head *imports)
 {
   set_path (path);
-  m_imports = imports;
+  bitmap_copy (m_imports, imports);
   m_undefined_path = false;
 
   if (m_resolve)
     {
+      add_copies_to_imports ();
       m_oracle->reset_path ();
       precompute_relations (path);
     }
@@ -379,6 +445,18 @@ path_range_query::precompute_ranges (const vec<basic_block> &path,
     {
       basic_block bb = curr_bb ();
 
+      if (m_resolve)
+	{
+	  gori_compute &gori = m_ranger.gori ();
+	  tree name;
+
+	  // Exported booleans along the path, may help conditionals.
+	  // Add them as interesting imports.
+	  FOR_EACH_GORI_EXPORT_NAME (gori, bb, name)
+	    if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE)
+	      bitmap_set_bit (m_imports, SSA_NAME_VERSION (name));
+	}
+
       precompute_ranges_in_block (bb);
       adjust_for_non_null_uses (bb);
 
diff --git a/gcc/gimple-range-path.h b/gcc/gimple-range-path.h
index d12fd7743..f23cce1 100644
--- a/gcc/gimple-range-path.h
+++ b/gcc/gimple-range-path.h
@@ -61,6 +61,8 @@ private:
   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);
+  void add_copies_to_imports ();
+  bool add_to_imports (tree name, bitmap imports);
 
   // Path navigation.
   void set_path (const vec<basic_block> &);
@@ -82,7 +84,7 @@ private:
   // Path being analyzed.
   const vec<basic_block> *m_path;
 
-  const bitmap_head *m_imports;
+  auto_bitmap m_imports;
   gimple_ranger &m_ranger;
   non_null_ref m_non_null;
   path_oracle *m_oracle;