[gcc r17-3330] tree-optimization/126887 - allow backward threading to loop exit

https://gcc.gnu.org/g:4fe2072d5d16ce26112d8035e627d47809aaa6c2

commit r17-3330-g4fe2072d5d16ce26112d8035e627d47809aaa6c2
Author: Richard Biener <[email protected]>
Date:   Mon Aug 17 09:58:27 2026 +0200

    tree-optimization/126887 - allow backward threading to loop exit
    
    The following allows the backward thread through a loop header
    to exit, allowing it to fully peel a not iterating loop on a
    threading path.  The backward thread copier cannot handle copying
    loops, but this special case is OK and is also handled by the
    forward threader.  We have to take care to not randomly peel
    loops though, not even after loop opts, so this patch adds
    appropriate measures and a testcase.
    
            PR tree-optimization/126887
            * tree-ssa-threadbackward.cc (back_threader::find_paths_to_names):
            Allow to search past a loop header in case we are threading a
            loop exit test.
            * tree-ssa-threadupdate.cc
            (back_jt_path_registry::duplicate_thread_path): Properly
            detect when a entered subloop is dissolved by threading,
            but avoid creating new entries into the original loop.
            (jt_path_registry::cancel_invalid_paths): Do not allow
            peeling loops.
    
            * gcc.dg/tree-ssa/ssa-thread-23.c: New testcase.
            * gcc.dg/tree-ssa/ssa-thread-24.c: Likewise.

Diff:
---
 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-23.c | 19 +++++++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-24.c | 19 +++++++++++++++++++
 gcc/tree-ssa-threadbackward.cc                | 14 ++++++--------
 gcc/tree-ssa-threadupdate.cc                  | 18 ++++++++++++++++--
 4 files changed, 60 insertions(+), 10 deletions(-)

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 000000000000..a7896e4e57c9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-23.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+volatile unsigned sink;
+
+void
+f (int flag, unsigned n)
+{
+  unsigned i = 0;
+  do
+    {
+      sink = i;
+      i += 1;
+    }
+  while (i != 128);
+}
+
+/* We should not peel this loop.  */
+/* { dg-final { scan-tree-dump-times "sink" 1 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-24.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-24.c
new file mode 100644
index 000000000000..dae43512a17c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-thread-24.c
@@ -0,0 +1,19 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 --param dom-jump-threading=0 -fdump-tree-thread2-stats" } */
+volatile unsigned sink;
+
+void
+f (int flag, unsigned n)
+{
+  unsigned i = flag ? 0 : n;
+  do
+    {
+      sink = i;
+      i += 4;
+    }
+  while (i != 4);
+}
+
+/* We should thread the path when i starts at 0 through loop exit.  */
+/* { dg-final { scan-tree-dump "Jumps threaded: 1" "thread2" } } */
+/* { dg-final { scan-tree-dump-times "sink" 2 "thread2" } } */
diff --git a/gcc/tree-ssa-threadbackward.cc b/gcc/tree-ssa-threadbackward.cc
index ca1af87bb401..20bb74c507fd 100644
--- a/gcc/tree-ssa-threadbackward.cc
+++ b/gcc/tree-ssa-threadbackward.cc
@@ -396,6 +396,7 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting,
   // edge might help here.  Alternatively copying divergent control flow
   // on the way to the backedge could be worthwhile.
   bool large_non_fsm;
+  edge e;
   if (m_path.length () > 1
       && (!profit.possibly_profitable_path_p (m_path, &large_non_fsm)
 	  || (!large_non_fsm
@@ -405,7 +406,10 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting,
   // The backwards thread copier cannot copy blocks that do not belong
   // to the same loop, so when the new source of the path entry no
   // longer belongs to it we don't need to search further.
-  else if (m_path[0]->loop_father != bb->loop_father)
+  else if (m_path[0]->loop_father != bb->loop_father
+	   && (!(e = loop_exits_from_bb_p (m_path[0]->loop_father,
+					   m_path[0]))
+	       || e->dest->loop_father != bb->loop_father))
     ;
 
   // Continue looking for ways to extend the path but limit the
@@ -481,13 +485,7 @@ back_threader::find_paths_to_names (basic_block bb, bitmap interesting,
 	  FOR_EACH_EDGE (e, iter, bb->preds)
 	    {
 	      if (e->flags & EDGE_ABNORMAL
-		  // This is like path_crosses_loops in profitable_path_p but
-		  // more restrictive to avoid peeling off loop iterations (see
-		  // tree-ssa/pr14341.c for an example).
-		  // ???  Note this restriction only applied when visiting an
-		  // interesting PHI with the former resolve_phi.
-		  || (!interesting_phis.is_empty ()
-		      && m_path[0]->loop_father != e->src->loop_father))
+		  || e->src->index == ENTRY_BLOCK)
 		continue;
 	      for (gphi *phi : interesting_phis)
 		{
diff --git a/gcc/tree-ssa-threadupdate.cc b/gcc/tree-ssa-threadupdate.cc
index db3520b42fc9..91c2c1788efb 100644
--- a/gcc/tree-ssa-threadupdate.cc
+++ b/gcc/tree-ssa-threadupdate.cc
@@ -2407,8 +2407,15 @@ back_jt_path_registry::duplicate_thread_path (edge entry,
   for (i = 0; i < n_region; i++)
     {
       /* We do not handle subloops, i.e. all the blocks must belong to the
-	 same loop.  */
-      if (region[i]->loop_father != loop)
+	 same loop.  Unless we thread to the subloop exit and thus the
+	 path will belong to loop after the threading.  */
+      if ((region[i]->loop_father != loop
+	   && !(loop_exit_edge_p (region[i]->loop_father, exit)
+		&& exit->dest->loop_father == loop))
+	  /* Avoid creating alternate entries into the original loop.  */
+	  || (loop->header == entry->dest
+	      && region[i] != exit->src
+	      && EDGE_COUNT (region[i]->succs) > 1))
 	return false;
     }
 
@@ -2812,6 +2819,13 @@ jt_path_registry::cancel_invalid_paths (vec<jump_thread_edge *> &path)
       && flow_loop_nested_p (exit->dest->loop_father, exit->src->loop_father))
     return false;
 
+  if (seen_latch && entry->dest == loop->header)
+    {
+      cancel_thread (&path, "Threading through latch from loop header "
+		     "peels loop");
+      return true;
+    }
+
   if (cfun->curr_properties & PROP_loop_opts_done)
     return false;