Move import population from threader to path solver.

Imports are our nomenclature for external SSA names to a block that
are used to calculate the outgoing edges for said block.  For example,
in the following snippet:

    <bb 2> :
    _1 = b_10 == block_11;
    _2 = b_10 != -1;
    _3 = _1 & _2;
    if (_3 != 0)
      goto <bb 3>; [INV]
    else
      goto <bb 5>; [INV]

...the imports to the block are b_10 and block_11 since they are both
needed to calculate _3.

The path solver takes a bitmap of imports in addition to the path
itself.  This sets up the number of SSA names to be on the lookout
for, while resolving the final conditional.

Calculating these imports was initially done in the threader, since it
was the only user of the path solver.  With new clients, it has become
obvious that populating the imports should be a task for the path
solver, so it can be shared among the clients.

This patch moves the import code to the solver, making both the solver
and the threader simpler in the process.  This is because intent is
clearer and some duplicate code was removed.

This reshuffling had the net effect of giving us a handful of new
threads through my suite of .ii files (125).  This was unexpected, but
welcome nevertheless.  There is no performance difference in callgrind
over the same suite.

Regstrapped on x86-64 Linux.

gcc/ChangeLog:

	* gimple-range-path.cc (path_range_query::add_copies_to_imports):
	Rename to...
	(path_range_query::compute_imports): ...this.  Adapt it so it can
	be passed the imports bitmap instead of working on m_imports.
	(path_range_query::compute_ranges): Call compute_imports in all
	cases unless an imports bitmap is passed.
	* gimple-range-path.h (path_range_query::compute_imports): New.
	(path_range_query::add_copies_to_imports): Remove.
	* tree-ssa-threadbackward.c (back_threader::resolve_def): Remove.
	(back_threader::find_paths_to_names): Inline resolve_def.
	(back_threader::find_paths): Call compute_imports.
	(back_threader::resolve_phi): Adjust comment.

1 files changed, 21 insertions, 24 deletions

diff --git a/gcc/gimple-range-path.cc b/gcc/gimple-range-path.cc
index 6da01c7..4843c13 100644
--- a/gcc/gimple-range-path.cc
+++ b/gcc/gimple-range-path.cc
@@ -439,26 +439,32 @@ path_range_query::add_to_imports (tree name, bitmap imports)
   return false;
 }
 
-// Add the copies of any SSA names in IMPORTS to IMPORTS.
+// Compute the imports to the path ending in EXIT.  These are
+// essentially the SSA names used to calculate the final conditional
+// along the path.
 //
-// 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.
+// They are hints for the solver.  Adding more elements 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 ()
+path_range_query::compute_imports (bitmap imports, basic_block exit)
 {
-  auto_vec<tree> worklist (bitmap_count_bits (m_imports));
+  // Start with the imports from the exit block...
+  bitmap r_imports = m_ranger.gori ().imports (exit);
+  bitmap_copy (imports, r_imports);
+
+  auto_vec<tree> worklist (bitmap_count_bits (imports));
   bitmap_iterator bi;
   unsigned i;
-
-  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
+  EXECUTE_IF_SET_IN_BITMAP (imports, 0, i, bi)
     {
       tree name = ssa_name (i);
       worklist.quick_push (name);
     }
 
+  // ...and add any operands used to define these imports.
   while (!worklist.is_empty ())
     {
       tree name = worklist.pop ();
@@ -466,15 +472,12 @@ path_range_query::add_copies_to_imports ()
 
       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);
+	  add_to_imports (gimple_assign_rhs1 (def_stmt), imports);
 	  tree rhs = gimple_assign_rhs2 (def_stmt);
-	  if (rhs && add_to_imports (rhs, m_imports))
+	  if (rhs && add_to_imports (rhs, imports))
 	    worklist.safe_push (rhs);
 	  rhs = gimple_assign_rhs3 (def_stmt);
-	  if (rhs && add_to_imports (rhs, m_imports))
+	  if (rhs && add_to_imports (rhs, imports))
 	    worklist.safe_push (rhs);
 	}
       else if (gphi *phi = dyn_cast <gphi *> (def_stmt))
@@ -486,7 +489,7 @@ path_range_query::add_copies_to_imports ()
 
 	      if (TREE_CODE (arg) == SSA_NAME
 		  && m_path.contains (e->src)
-		  && bitmap_set_bit (m_imports, SSA_NAME_VERSION (arg)))
+		  && bitmap_set_bit (imports, SSA_NAME_VERSION (arg)))
 		worklist.safe_push (arg);
 	    }
 	}
@@ -512,16 +515,10 @@ path_range_query::compute_ranges (const vec<basic_block> &path,
   if (imports)
     bitmap_copy (m_imports, imports);
   else
-    {
-      bitmap imports = m_ranger.gori ().imports (exit_bb ());
-      bitmap_copy (m_imports, imports);
-    }
+    compute_imports (m_imports, exit_bb ());
 
   if (m_resolve)
-    {
-      add_copies_to_imports ();
-      get_path_oracle ()->reset_path ();
-    }
+    get_path_oracle ()->reset_path ();
 
   if (DEBUG_SOLVER)
     {