tree-optimization/120003 - missed jump threading

The following allows the entry and exit block of a jump thread path
to be equal, which can easily happen when there isn't a forwarder
on the interesting edge for an FSM thread conditional.  We just
don't want to enlarge the path from such a block.

	PR tree-optimization/120003
	* tree-ssa-threadbackward.cc (back_threader::find_paths_to_names):
	Allow block re-use but do not enlarge the path beyond such a
	re-use.

	* gcc.dg/tree-ssa/ssa-thread-23.c: New testcase.
	* gcc.dg/tree-ssa/ssa-dom-thread-7.c: Adjust.

(cherry picked from commit 1a13684dfc7286139064f7d7341462c9995cbd1c)

3 files changed, 24 insertions, 7 deletions

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c
index d84acee..8be9878 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dom-thread-7.c
@@ -11,8 +11,8 @@
    to change decisions in switch expansion which in turn can expose new
    jump threading opportunities.  Skip the later tests on aarch64.  */
 /* { dg-final { scan-tree-dump-not "Jumps threaded"  "dom3" { target { ! aarch64*-*-* } } } } */
-/* { dg-final { scan-tree-dump "Jumps threaded: 9"  "thread2" { target { ! aarch64*-*-* } } } } */
-/* { dg-final { scan-tree-dump "Jumps threaded: 17"  "thread2" { target { aarch64*-*-* } } } } */
+/* { dg-final { scan-tree-dump "Jumps threaded: 10"  "thread2" { target { ! aarch64*-*-* } } } } */
+/* { dg-final { scan-tree-dump "Jumps threaded: 14"  "thread2" { target { aarch64*-*-* } } } } */
 
 enum STATE {
   S0=0,
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-23.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-23.c
new file mode 100644
index 0000000..930360a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-23.c
@@ -0,0 +1,19 @@
+/* PR120003 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-cddce3-details" } */
+
+extern _Bool g(int);
+
+_Bool f()
+{
+  _Bool retval = 0;
+  for(int i=0; i<1000000; ++i)
+    retval = retval || g(i);
+  return retval;
+}
+
+/* Jump threading after loop optimization should get the counting loop
+   separated from the loop until retval is true and CD-DCE elide it.
+   It's difficult to check for the fact that a true retval terminates
+   the loop so check CD-DCE eliminates one loop instead.  */
+/* { dg-final { scan-tree-dump "fix_loop_structure: removing loop" "cddce3" } } */
diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc
index d0b74b2..3adb83e 100644
--- a/gcc/tree-ssa-threadbackward.cc
+++ b/gcc/tree-ssa-threadbackward.cc
@@ -349,9 +349,6 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting,
 				    unsigned overall_paths,
 				    back_threader_profitability &profit)
 {
-  if (m_visited_bbs.add (bb))
-    return;
-
   m_path.safe_push (bb);
 
   // Try to resolve the path without looking back.  Avoid resolving paths
@@ -377,7 +374,8 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting,
   // Continue looking for ways to extend the path but limit the
   // search space along a branch
   else if ((overall_paths = overall_paths * EDGE_COUNT (bb->preds))
-	   <= (unsigned)param_max_jump_thread_paths)
+	   <= (unsigned)param_max_jump_thread_paths
+	   && !m_visited_bbs.add (bb))
     {
       // For further greedy searching we want to remove interesting
       // names defined in BB but add ones on the PHI edges for the
@@ -489,6 +487,7 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting,
 	 backtracking we have to restore it.  */
       for (int j : new_imports)
 	bitmap_clear_bit (m_imports, j);
+      m_visited_bbs.remove (bb);
     }
   else if (dump_file && (dump_flags & TDF_DETAILS))
     fprintf (dump_file, "  FAIL: Search space limit %d reached.\n",
@@ -496,7 +495,6 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting,
 
   // Reset things to their original state.
   m_path.pop ();
-  m_visited_bbs.remove (bb);
 }
 
 // Search backwards from BB looking for paths where the final