Attempt to resolve all incoming paths to a PHI.

The code that threads incoming paths to a PHI is duplicating what we
do generically in find_paths_to_names.  This shortcoming is actually
one of the reasons we aren't threading all possible paths into a PHI.
For example, we give up after finding one threadable path, but some
PHIs have multiple threadable paths:

      // x_5 = PHI <10(4), 20(5), ...>
      // if (x_5 > 5)

Addressing this not only fixes the oversight, but simplifies the
PHI handling code, since we can consider the PHI fully resolved upon
return.

Interestingly, for ssa-thread-12.c the main thread everything was
hinging on was unreachable.  With this patch, we call
maybe_register_path() earlier.  In doing so, the solver realizes
that any path starting with 4->8 is unreachable and can be avoided.
This caused the cascade of threadable paths that depended on this
to no longer happen.  Since threadable paths in thread[34] was the only
thing this test was testing, there's no longer anything to test.  Neat!

Tested on x86-64 Linux.

gcc/ChangeLog:

	* tree-ssa-threadbackward.c (back_threader::resolve_phi):
	Attempt to resolve all incoming paths to a PHI.
	(back_threader::resolve_def): Always return true for PHIs.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/pr21090.c: Adjust for threading.
	* gcc.dg/tree-ssa/ssa-thread-12.c: Removed.

1 files changed, 20 insertions, 50 deletions

diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index edb396b..a6b9893a 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -83,7 +83,7 @@ private:
   edge maybe_register_path ();
   bool find_paths_to_names (basic_block bb, bitmap imports);
   bool resolve_def (tree name, bitmap interesting, vec<tree> &worklist);
-  bool resolve_phi (gphi *phi, bitmap imports);
+  void resolve_phi (gphi *phi, bitmap imports);
   edge find_taken_edge (const vec<basic_block> &path);
   edge find_taken_edge_cond (const vec<basic_block> &path, gcond *);
   edge find_taken_edge_switch (const vec<basic_block> &path, gswitch *);
@@ -243,17 +243,14 @@ populate_worklist (vec<tree> &worklist, bitmap bits)
     }
 }
 
-// If taking any of the incoming edges to a PHI causes the final
-// conditional of the current path to be constant, register the
-// path(s), and return TRUE.
+// Find jump threading paths that go through a PHI.
 
-bool
+void
 back_threader::resolve_phi (gphi *phi, bitmap interesting)
 {
   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (phi)))
-    return true;
+    return;
 
-  bool done = false;
   for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
     {
       edge e = gimple_phi_arg_edge (phi, i);
@@ -275,53 +272,24 @@ back_threader::resolve_phi (gphi *phi, bitmap interesting)
 	  continue;
 	}
 
-      // FIXME: We currently stop looking if we find a threadable path
-      // through a PHI.  This is pessimistic, as there can be multiple
-      // paths that can resolve the path.  For example:
-      //
-      // x_5 = PHI <10(4), 20(5), ...>
-      // if (x_5 > 5)
-
       tree arg = gimple_phi_arg_def (phi, i);
-      if (TREE_CODE (arg) == SSA_NAME)
-	{
-	  unsigned v = SSA_NAME_VERSION (arg);
-
-	  // Avoid loops as in: x_5 = PHI <x_5(2), ...>.
-	  if (bitmap_bit_p (interesting, v))
-	    continue;
+      unsigned v = 0;
 
+      if (TREE_CODE (arg) == SSA_NAME
+	  && !bitmap_bit_p (interesting, SSA_NAME_VERSION (arg)))
+	{
+	  // Record that ARG is interesting when searching down this path.
+	  v = SSA_NAME_VERSION (arg);
+	  gcc_checking_assert (v != 0);
 	  bitmap_set_bit (interesting, v);
 	  bitmap_set_bit (m_imports, v);
+	}
 
-	  // When resolving unknowns, see if the incoming SSA can be
-	  // resolved on entry without having to keep looking back.
-	  bool keep_looking = true;
-	  if (m_resolve)
-	    {
-	      m_path.safe_push (e->src);
-	      if (maybe_register_path ())
-		{
-		  keep_looking = false;
-		  m_visited_bbs.add (e->src);
-		}
-	      m_path.pop ();
-	    }
-	  if (keep_looking)
-	    done |= find_paths_to_names (e->src, interesting);
+      find_paths_to_names (e->src, interesting);
 
-	  bitmap_clear_bit (interesting, v);
-	}
-      else if (TREE_CODE (arg) == INTEGER_CST)
-	{
-	  m_path.safe_push (e->src);
-	  edge taken_edge = maybe_register_path ();
-	  if (taken_edge && taken_edge != UNREACHABLE_EDGE)
-	    done = true;
-	  m_path.pop ();
-	}
+      if (v)
+	bitmap_clear_bit (interesting, v);
     }
-  return done;
 }
 
 // If the definition of NAME causes the final conditional of the
@@ -333,9 +301,11 @@ back_threader::resolve_def (tree name, bitmap interesting, vec<tree> &worklist)
   gimple *def_stmt = SSA_NAME_DEF_STMT (name);
 
   // Handle PHIs.
-  if (is_a<gphi *> (def_stmt)
-      && resolve_phi (as_a<gphi *> (def_stmt), interesting))
-    return true;
+  if (is_a<gphi *> (def_stmt))
+    {
+      resolve_phi (as_a<gphi *> (def_stmt), interesting);
+      return true;
+    }
 
   // Defer copies of SSAs by adding the source to the worklist.
   if (gimple_assign_single_p (def_stmt)