[LoopUnroll] First form LCSSA, then loop-simplify

[mkuper]

Summary

Running non-LCSSA-preserving loop-simplify followed by LoopSimplify on (roughly) the same loop is incorrect, since LoopSimplify may break LCSSA arbitrarily higher in the loop nest.
Instead, run LCSSA first, and then run LCSSA-perserving LoopSimplify on the result.

This fixes PR31718.

[chandlerc]

LGTM!

Thanks, I would never have imagined this was hiding behind the 'true' I changed in my patch.

lib/Transforms/Utils/LoopUnroll.cpp

bool llvm::UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, bool Force,
   // to ensure subsequent analyses can rely on this form. We want to simplify
   // at least one layer outside of the loop that was unrolled so that any
   // changes to the parent loop exposed by the unrolling are considered.
   if (DT) {
     if (OuterL) {
       // OuterL includes all loops for which we can break loop-simplify, so
       // it's sufficient to simplify only it (it'll recursively simplify inner
       // loops too).
-      // TODO: That potentially might be compile-time expensive. We should try
-      // to fix the loop-simplified form incrementally.
-      // Note that we only preserve LCSSA at this stage if we need to and if we
-      // won't end up fixing it. If we end up fixing it anyways, we don't need
-      // to preserve it here and in fact we can't because it isn't correct.
-      simplifyLoop(OuterL, DT, LI, SE, AC, PreserveLCSSA && !NeedToFixLCSSA);
-
+      if (NeedToFixLCSSA) {
         // LCSSA must be performed on the outermost affected loop. The unrolled
-      // loop's last loop latch is guaranteed to be in the outermost loop after
-      // LoopInfo's been updated by markAsRemoved.
+        // loop's last loop latch is guaranteed to be in the outermost loop
+        // after LoopInfo's been updated by markAsRemoved.
         Loop *LatchLoop = LI->getLoopFor(Latches.back());
-      if (!OuterL->contains(LatchLoop))
-        while (OuterL->getParentLoop() != LatchLoop)
-          OuterL = OuterL->getParentLoop();
-
-      if (NeedToFixLCSSA)
-        formLCSSARecursively(*OuterL, *DT, LI, SE);
-      else if (PreserveLCSSA)
+        Loop *FixLCSSALoop = OuterL;
+        if (!FixLCSSALoop->contains(LatchLoop))
+          while (FixLCSSALoop->getParentLoop() != LatchLoop)
+            FixLCSSALoop = FixLCSSALoop->getParentLoop();
+
+        formLCSSARecursively(*FixLCSSALoop, *DT, LI, SE);
+      } else if (PreserveLCSSA) {
         assert(OuterL->isLCSSAForm(*DT) &&
                "Loops should be in LCSSA form after loop-unroll.");
+      }
+
+      // TODO: That potentially might be compile-time expensive. We should try
+      // to fix the loop-simplified form incrementally.
+      simplifyLoop(OuterL, DT, LI, SE, AC, PreserveLCSSA);
     } else {
       // Simplify loops for which we might've broken loop-simplify form.
       for (Loop *SubLoop : LoopsToSimplify)
         simplifyLoop(SubLoop, DT, LI, SE, AC, PreserveLCSSA);
     }
   }
 
   return true;

test/Transforms/LoopUnroll/pr31718.ll

+; RUN: opt -loop-unroll -verify-loop-lcssa -S < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@b = external local_unnamed_addr global i32, align 4
+
+; CHECK-LABEL: @main
+; CHECK: exit.loopexit:
+; CHECK: {{.*}} = phi i32 [ %d.0, %h3 ]
+; CHECK: br label %exit
+; CHECK: exit.loopexit1:
+; CHECK: {{.*}} = phi i32 [ %d.0, %h3.1 ]
+; CHECK: br label %exit
+
+define void @main() local_unnamed_addr #0 {
+ph1:
+  br label %h1
+
+h1:
+  %d.0 = phi i32 [ %1, %latch1 ], [ undef, %ph1 ]
+  br label %ph2
+
+ph2:
+  br label %h2
+
+h2:
+  %0 = phi i32 [ 0, %ph2 ], [ %inc, %latch2 ]
+  br label %h3
+
+h3:
+  br i1 undef, label %latch3, label %exit
+
+latch3:
+  br i1 false, label %exit3, label %h3
+
+exit3:
+  br label %latch2
+
+latch2:
+  %inc = add nuw nsw i32 %0, 1
+  %cmp = icmp slt i32 %inc, 2
+  br i1 %cmp, label %h2, label %exit2
+
+exit2:
+  br i1 undef, label %latch1, label %ph2
+
+latch1:                 ; preds = %exit2
+  %1 = load i32, i32* @b, align 4
+  br label %h1
+
+exit:
+  %d.0.lcssa = phi i32 [ %d.0, %h3 ]
+  ret void
+}