[PATCH] tree-optimization/114792 - order loops to unloops in CH

[PATCH] tree-optimization/114792 - order loops to unloops in CH

[Richard Biener]

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.

Bootstrapped and tested on x86_64-unknown-linux-gnu, pushed.

 	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.
---
  gcc/testsuite/gcc.dg/torture/pr114792.c | 16 ++++++++++++++++
  gcc/tree-ssa-loop-ch.cc                 | 25 +++++++++++++++++++++++++
  2 files changed, 41 insertions(+)
  create mode 100644 gcc/testsuite/gcc.dg/torture/pr114792.c

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;
-- 
2.25.1