[LoopSimplify] Update LCSSA after separating nested loops.

Michael Zolotukhin · Michael Zolotukhin · commit ea5b72825b52 · 2016-07-18T19:44:19.000Z
Summary: Usually LCSSA survives this transformation, but in some cases (see attached test) it doesn't: values from the original loop after separating might be used from the outer loop. Before the transformation it was the same loop, so LCSSA phis were not required. This fixes PR28272. Reviewers: sanjoy, hfinkel, chandlerc Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D21665 llvm-svn: 275891
diff --git a/llvm/lib/Transforms/Utils/LoopSimplify.cpp b/llvm/lib/Transforms/Utils/LoopSimplify.cpp
@@ -327,19 +327,62 @@ static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
     else
       NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I));
 
+  SmallVector<BasicBlock *, 8> OuterLoopBlocks;
+  OuterLoopBlocks.push_back(NewBB);
   // Now that we know which blocks are in L and which need to be moved to
   // OuterLoop, move any blocks that need it.
   for (unsigned i = 0; i != L->getBlocks().size(); ++i) {
     BasicBlock *BB = L->getBlocks()[i];
     if (!BlocksInL.count(BB)) {
       // Move this block to the parent, updating the exit blocks sets
       L->removeBlockFromLoop(BB);
-      if ((*LI)[BB] == L)
+      if ((*LI)[BB] == L) {
         LI->changeLoopFor(BB, NewOuter);
+        OuterLoopBlocks.push_back(BB);
+      }
       --i;
     }
   }
 
+  // Split edges to exit blocks from the inner loop, if they emerged in the
+  // process of separating the outer one.
+  SmallVector<BasicBlock *, 8> ExitBlocks;
+  L->getExitBlocks(ExitBlocks);
+  SmallSetVector<BasicBlock *, 8> ExitBlockSet(ExitBlocks.begin(),
+                                               ExitBlocks.end());
+  for (BasicBlock *ExitBlock : ExitBlockSet) {
+    if (any_of(predecessors(ExitBlock),
+               [L](BasicBlock *BB) { return !L->contains(BB); })) {
+      rewriteLoopExitBlock(L, ExitBlock, DT, LI, PreserveLCSSA);
+    }
+  }
+
+  if (PreserveLCSSA) {
+    // Fix LCSSA form for L. Some values, which previously were only used inside
+    // L, can now be used in NewOuter loop. We need to insert phi-nodes for them
+    // in corresponding exit blocks.
+
+    // Go through all instructions in OuterLoopBlocks and check if they are
+    // using operands from the inner loop. In this case we'll need to fix LCSSA
+    // for these instructions.
+    SmallSetVector<Instruction *, 8> WorklistSet;
+    for (BasicBlock *OuterBB: OuterLoopBlocks) {
+      for (Instruction &I : *OuterBB) {
+        for (Value *Op : I.operands()) {
+          Instruction *OpI = dyn_cast<Instruction>(Op);
+          if (!OpI || !L->contains(OpI))
+            continue;
+          WorklistSet.insert(OpI);
+        }
+      }
+    }
+    SmallVector<Instruction *, 8> Worklist(WorklistSet.begin(),
+                                           WorklistSet.end());
+    formLCSSAForInstructions(Worklist, *DT, *LI);
+    assert(NewOuter->isRecursivelyLCSSAForm(*DT) &&
+           "LCSSA is broken after separating nested loops!");
+  }
+
   return NewOuter;
 }
 
@@ -541,17 +584,12 @@ static bool simplifyOneLoop(Loop *L, SmallVectorImpl<Loop *> &Worklist,
   SmallSetVector<BasicBlock *, 8> ExitBlockSet(ExitBlocks.begin(),
                                                ExitBlocks.end());
   for (BasicBlock *ExitBlock : ExitBlockSet) {
-    for (pred_iterator PI = pred_begin(ExitBlock), PE = pred_end(ExitBlock);
-         PI != PE; ++PI)
-      // Must be exactly this loop: no subloops, parent loops, or non-loop preds
-      // allowed.
-      if (!L->contains(*PI)) {
-        if (rewriteLoopExitBlock(L, ExitBlock, DT, LI, PreserveLCSSA)) {
-          ++NumInserted;
-          Changed = true;
-        }
-        break;
-      }
+    if (any_of(predecessors(ExitBlock),
+               [L](BasicBlock *BB) { return !L->contains(BB); })) {
+      rewriteLoopExitBlock(L, ExitBlock, DT, LI, PreserveLCSSA);
+      ++NumInserted;
+      Changed = true;
+    }
   }
 
   // If the header has more than two predecessors at this point (from the
diff --git a/llvm/test/Transforms/LoopSimplify/pr28272.ll b/llvm/test/Transforms/LoopSimplify/pr28272.ll
@@ -0,0 +1,76 @@
+; RUN: opt < %s -lcssa -loop-unroll -S | FileCheck %s
+target triple = "x86_64-unknown-linux-gnu"
+
+; PR28272
+; When LoopSimplify separates nested loops, it might break LCSSA form: values
+; from the original loop might be used in the outer loop. This test invokes
+; loop-unroll, which calls loop-simplify before itself. If LCSSA is broken
+; after loop-simplify, we crash on assertion.
+
+; CHECK-LABEL: @foo
+define void @foo() {
+entry:
+  br label %header
+
+header:
+  br label %loop1
+
+loop1:
+  br i1 true, label %loop1, label %bb43
+
+bb43:
+  %a = phi i32 [ undef, %loop1 ], [ 0, %bb45 ], [ %a, %bb54 ]
+  %b = phi i32 [ 0, %loop1 ], [ 1, %bb54 ], [ %c, %bb45 ]
+  br i1 true, label %bb114, label %header
+
+bb114:
+  %c = add i32 0, 1
+  %d = add i32 0, 1
+  br i1 true, label %bb45, label %bb54
+
+bb45:
+  %x = add i32 %d, 0
+  br label %bb43
+
+bb54:
+  br label %bb43
+}
+
+; CHECK-LABEL: @foo2
+define void @foo2() {
+entry:
+  br label %outer
+
+outer.loopexit:
+  br label %outer
+
+outer:
+  br label %loop1
+
+loop1:
+  br i1 true, label %loop1, label %loop2.preheader
+
+loop2.preheader:
+  %a.ph = phi i32 [ undef, %loop1 ]
+  %b.ph = phi i32 [ 0, %loop1 ]
+  br label %loop2
+
+loop2:
+  %a = phi i32 [ 0, %loop2.if.true ], [ %a, %loop2.if.false ], [ %a.ph, %loop2.preheader ], [0, %bb]
+  %b = phi i32 [ 1, %loop2.if.false ], [ %c, %loop2.if.true ], [ %b.ph, %loop2.preheader ], [%c, %bb]
+  br i1 true, label %loop2.if, label %outer.loopexit
+
+loop2.if:
+  %c = add i32 0, 1
+  switch i32 undef, label %loop2.if.false [i32 0, label %loop2.if.true
+                                       i32 1, label %bb]
+
+loop2.if.true:
+  br i1 undef, label %loop2, label %bb
+
+loop2.if.false:
+  br label %loop2
+
+bb:
+  br label %loop2
+}
