[PR tree-optimization/71335] Fix thread path management in backwards threader

[Jeff Law <law at redhat dot com>]

As previously noted, there's a buglet in the handling of the 
stack-of-blocks representation of the thread path in the backwards threader.

In particular there's a case where we can get the same block pushed onto 
that stack twice.  My workaround for that lameness could result in 
incorrect code if the last block in the path actually branches back to 
itself as seen in the 71335 testcase.

This patch removes the hacks and avoids putting the duplicate on the 
stack-of-blocks path earlier.

Bootstrapped and regression tested on x86_64 linux.  Additionally, I did 
bootstraps and regression testing with additional verification that the 
state of the stack was unchanged across the call to 
fsm_find_control_statement_thread_paths (that verification is not in 
this patch, but could be easily added as a follow-up).

Installed on the trunk,

Jeff

commit c2ffa8b6472e2d87763eeece99762fe3e5ab057a
Author: law <law@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Fri Jun 10 16:23:06 2016 +0000

    	PR tree-optimization/71335
    	* tree-ssa-threadbackward.c (profitable_jump_thread_path): Filter out
    	zero length paths here.
    	(convert_and_register_jump_thread_path): Remove hacks related to
    	duplicated blocks in the jump thread path.
    	(fsm_find_control_statement_thread_paths): Avoid putting the same
    	block on the thread path twice, but ensure the thread path is
    	unchanged from the caller's point of view.
    
    	PR tree-optimization/71335
    	* gcc.c-torture/execute/pr71335.c: New test.
    
    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@237312 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index af96025..bd9476e 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,14 @@
+2016-06-10  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/71335
+	* tree-ssa-threadbackward.c (profitable_jump_thread_path): Filter out
+	zero length paths here.
+	(convert_and_register_jump_thread_path): Remove hacks related to
+	duplicated blocks in the jump thread path.
+	(fsm_find_control_statement_thread_paths): Avoid putting the same
+	block on the thread path twice, but ensure the thread path is
+	unchanged from the caller's point of view.
+	
 2016-06-10  Jan Hubicka  <hubicka@ucw.cz>
 
 	* predict.c (predict_loops): Remove PRED_LOOP_BRANCH.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 71a2db1..b76e477 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2016-06-10  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/71335
+	* gcc.c-torture/execute/pr71335.c: New test.
+
 2016-06-10  David Malcolm  <dmalcolm@redhat.com>
 
 	* gcc.dg/plugin/must-tail-call-2.c: Remove all details from
diff --git a/gcc/testsuite/gcc.c-torture/execute/pr71335.c b/gcc/testsuite/gcc.c-torture/execute/pr71335.c
new file mode 100644
index 0000000..cbfd990
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr71335.c
@@ -0,0 +1,13 @@
+int a;
+int
+main ()
+{
+  int b = 0;
+  while (a < 0 || b)
+    {
+      b = 0;
+      for (; b < 9; b++)
+	;
+    }
+  exit (0);
+}
diff --git a/gcc/tree-ssa-threadbackward.c b/gcc/tree-ssa-threadbackward.c
index 57f1f5c..139d376 100644
--- a/gcc/tree-ssa-threadbackward.c
+++ b/gcc/tree-ssa-threadbackward.c
@@ -109,6 +109,19 @@ profitable_jump_thread_path (vec<basic_block, va_gc> *&path,
   /* Note BBI is not in the path yet, hence the +1 in the test below
      to make sure BBI is accounted for in the path length test.  */
   int path_length = path->length ();
+
+  /* We can get a length of 0 here when the statement that
+     makes a conditional generate a compile-time constant
+     result is in the same block as the conditional.
+
+     That's not really a jump threading opportunity, but instead is
+     simple cprop & simplification.  We could handle it here if we
+     wanted by wiring up all the incoming edges.  If we run this
+     early in IPA, that might be worth doing.   For now we just
+     reject that case.  */
+  if (path_length == 0)
+      return NULL;
+
   if (path_length + 1 > PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH))
     {
       if (dump_file && (dump_flags & TDF_DETAILS))
@@ -376,34 +389,12 @@ convert_and_register_jump_thread_path (vec<basic_block, va_gc> *&path,
       basic_block bb1 = (*path)[path->length () - j - 1];
       basic_block bb2 = (*path)[path->length () - j - 2];
 
-      /* This can happen when we have an SSA_NAME as a PHI argument and
-	 its initialization block is the head of the PHI argument's
-	 edge.  */
-      if (bb1 == bb2)
-	continue;
-
       edge e = find_edge (bb1, bb2);
       gcc_assert (e);
       jump_thread_edge *x = new jump_thread_edge (e, EDGE_FSM_THREAD);
       jump_thread_path->safe_push (x);
     }
 
-  /* As a consequence of the test for duplicate blocks in the path
-     above, we can get a path with no blocks.  This happens if a
-     conditional can be fully evaluated at compile time using just
-     defining statements in the same block as the test.
-
-     When we no longer push the block associated with a PHI argument
-     onto the stack, then this as well as the test in the loop above
-     can be removed.  */
-  if (jump_thread_path->length () == 0)
-    {
-      jump_thread_path->release ();
-      delete jump_thread_path;
-      path->pop ();
-      return;
-    }
-
   /* Add the edge taken when the control variable has value ARG.  */
   jump_thread_edge *x
     = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
@@ -579,10 +570,19 @@ fsm_find_control_statement_thread_paths (tree name,
 
       else
 	{
+	  /* profitable_jump_thread_path is going to push the current
+	     block onto the path.  But the path will always have the current
+	     block at this point.  So we can just pop it.  */
+	  path->pop ();
+
 	  edge taken_edge = profitable_jump_thread_path (path, var_bb,
 						     name, arg);
 	  if (taken_edge)
 	    convert_and_register_jump_thread_path (path, taken_edge);
+
+	  /* And put the current block back onto the path so that the
+	     state of the stack is unchanged when we leave.  */
+	  vec_safe_push (path, var_bb);
 	}
     }