[gcc r14-10120] tree-optimization/114792 - order loops to unloops in CH

[gcc r14-10120] tree-optimization/114792 - order loops to unloops in CH

[Richard Biener]

https://gcc.gnu.org/g:59ff81835fee22a9d4c9a481a4d1814583aae945

commit r14-10120-g59ff81835fee22a9d4c9a481a4d1814583aae945
Author: Richard Biener <rguenther@suse.de>
Date:   Thu Apr 25 08:08:24 2024 +0200

    tree-optimization/114792 - order loops to unloops in CH
    
    When we use unloop_loops we have to make sure to have loops ordered
    inner to outer as otherwise we can wreck inner loop structure where
    unlooping relies on that being intact.  The following re-sorts the
    vector of to unloop loops after copy-header as that adds to the
    vector in two places and the wrong order.
    
            PR tree-optimization/114792
            * tree-ssa-loop-ch.cc (ch_order_loops): New function.
            (ch_base::copy_headers): Sort loops to unloop inner-to-outer.
    
            * gcc.dg/torture/pr114792.c: New testcase.

Diff:
---
 gcc/testsuite/gcc.dg/torture/pr114792.c | 16 ++++++++++++++++
 gcc/tree-ssa-loop-ch.cc                 | 25 +++++++++++++++++++++++++
 2 files changed, 41 insertions(+)

diff --git a/gcc/testsuite/gcc.dg/torture/pr114792.c b/gcc/testsuite/gcc.dg/torture/pr114792.c
new file mode 100644
index 00000000000..4990e76eb2a
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr114792.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-additional-options "-fno-tree-ccp -fno-tree-copy-prop" } */
+
+int a;
+int main() {
+  int b = -1, c;
+  for (; b >= 0; b++) {
+    for (c = 0; c; c++) {
+    L:
+      while (a)
+        if (a)
+          goto L;
+    }
+  }
+  return 0;
+}
diff --git a/gcc/tree-ssa-loop-ch.cc b/gcc/tree-ssa-loop-ch.cc
index b7ef485c4cc..d7dd3e5459d 100644
--- a/gcc/tree-ssa-loop-ch.cc
+++ b/gcc/tree-ssa-loop-ch.cc
@@ -759,6 +759,21 @@ protected:
   bool process_loop_p (class loop *loop) final override;
 }; // class pass_ch_vect
 
+/* Sort comparator to order loops after the specified order.  */
+
+static int
+ch_order_loops (const void *a_, const void *b_, void *order_)
+{
+  int *order = (int *)order_;
+  const class loop *a = *(const class loop * const *)a_;
+  const class loop *b = *(const class loop * const *)b_;
+  if (a->num == b->num)
+    return 0;
+  if (order[a->num] < order[b->num])
+    return -1;
+  return 1;
+}
+
 /* For all loops, copy the condition at the end of the loop body in front
    of the loop.  This is beneficial since it increases efficiency of
    code motion optimizations.  It also saves one jump on entry to the loop.  */
@@ -1152,6 +1167,16 @@ ch_base::copy_headers (function *fun)
     }
   if (!loops_to_unloop.is_empty ())
     {
+      /* Make sure loops are ordered inner to outer for unlooping.  */
+      if (loops_to_unloop.length () != 1)
+	{
+	  auto_vec<int, 8> order;
+	  order.safe_grow (number_of_loops (cfun), true);
+	  int i = 0;
+	  for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
+	    order[loop->num] = i++;
+	  loops_to_unloop.sort (ch_order_loops, order.address ());
+	}
       bool irred_invalidated;
       auto_bitmap lc_invalidated;
       auto_vec<edge> edges_to_remove;