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.

3 files changed, 21 insertions, 124 deletions

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr21090.c b/gcc/testsuite/gcc.dg/tree-ssa/pr21090.c
index 3909adb..92a8768 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr21090.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr21090.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdisable-tree-evrp -fdump-tree-vrp1 -fdelete-null-pointer-checks" } */
+/* { dg-options "-O2 -fno-thread-jumps -fdisable-tree-evrp -fdump-tree-vrp1 -fdelete-null-pointer-checks" } */
 
 int g, h;
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-12.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-12.c
deleted file mode 100644
index 08c0b8d..0000000
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-12.c
+++ /dev/null
@@ -1,73 +0,0 @@
-/* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-thread3-details -fdump-tree-thread4-details -fno-finite-loops --param early-inlining-insns=14 -fno-inline-functions" } */
-/* { dg-final { scan-tree-dump "Registering jump thread" "thread3" } } */
-/* { dg-final { scan-tree-dump "Registering jump thread" "thread4" } } */
-
-typedef struct bitmap_head_def *bitmap;
-typedef const struct bitmap_head_def *const_bitmap;
-typedef struct VEC_int_base
-{
-}
-VEC_int_base;
-typedef struct VEC_int_heap
-{
-  VEC_int_base base;
-}
-VEC_int_heap;
-typedef unsigned long BITMAP_WORD;
-typedef struct bitmap_element_def
-{
-  struct bitmap_element_def *next;
-  unsigned int indx;
-}
-bitmap_element;
-typedef struct bitmap_head_def
-{
-}
-bitmap_head;
-typedef struct
-{
-  bitmap_element *elt1;
-  bitmap_element *elt2;
-  BITMAP_WORD bits;
-}
-bitmap_iterator;
-static __inline__ void
-bmp_iter_and_compl_init (bitmap_iterator * bi, const_bitmap map1,
-			 const_bitmap map2, unsigned start_bit,
-			 unsigned *bit_no)
-{
-}
-
-static __inline__ void
-bmp_iter_next (bitmap_iterator * bi, unsigned *bit_no)
-{
-}
-
-static __inline__ unsigned char
-bmp_iter_and_compl (bitmap_iterator * bi, unsigned *bit_no)
-{
-  if (bi->bits)
-    {
-      while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
-	bi->elt2 = bi->elt2->next;
-    }
-}
-
-extern int VEC_int_base_length (VEC_int_base *);
-bitmap
-compute_idf (bitmap def_blocks, bitmap_head * dfs)
-{
-  bitmap_iterator bi;
-  unsigned bb_index, i;
-  VEC_int_heap *work_stack;
-  bitmap phi_insertion_points;
-  while ((VEC_int_base_length (((work_stack) ? &(work_stack)->base : 0))) > 0)
-    {
-      for (bmp_iter_and_compl_init
-	   (&(bi), (&dfs[bb_index]), (phi_insertion_points), (0), &(i));
-	   bmp_iter_and_compl (&(bi), &(i)); bmp_iter_next (&(bi), &(i)))
-	{
-	}
-    }
-}
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)