[LoopSimplify] Update LCSSA after separating nested loops.

[mzolotukhin]

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.

We might move this logic, along with the logic for updating LoopInfo, to
BasicBlockUtils (routine SplitBlockPredecessors), but I now see this
pretty independent on the fix in question.

This fixes PR28272.

[chandlerc]

lib/Transforms/Utils/LoopSimplify.cpp

343–345 ↗

(On Diff #61735)

Is it possible to track these when putting the instructions into this set? Maybe its just not worth it because its just the PHI nodes...

346 ↗

(On Diff #61735)

8? That seems like lots? Maybe not though

360–365 ↗

(On Diff #61735)

It's a bit odd to use this linear search for a unique dominating exit block... I wonder, is there some implicit guarantee that makes it make more sense? Do we instead want to perhaps build up a map from incoming BB of the outer PHI to dominating exit BB?

[sanjoy]

lib/Transforms/Utils/LoopSimplify.cpp

353 ↗

(On Diff #61735)

s/V/I/

370 ↗

(On Diff #61735)

What if you have

loop:
  %iv = phi [ 0, %entry ] [ %iv, (%loop, %left, %right)],  [ %iv.inc, %outer ]
  %iv.inc = %iv + 1
  switch(condition), %left, %right, %loop

left:
  br condition, %outer, %loop

right:
  br condition, %outer, %loop

outer:
  br %loop

then the separated loop structure will be

outer_header:
  %iv = [ 0, %entry ] , [ %iv.inc, %outer ]
  br loop

loop:
  %iv.inc = %iv + 1
  switch(condition), %left, %right, %loop

left:
  br condition, %outer, %loop

right:
  br condition, %outer, %loop

outer:
  br %loop

Now %iv.inc is live out of the inner loop and none of the inner loop
exits (%left, %right) dominate %outer.

[sanjoy]

lib/Transforms/Utils/LoopSimplify.cpp

370 ↗

(On Diff #61735)

Nit: the latter code snippet should be

outer_header:
  %iv = [ 0, %entry ] , [ %iv.inc, %outer ]
  br loop

loop:
  %iv.inc = %iv + 1
  switch(condition), %left, %right, %loop

left:
  br condition, %outer, %loop

right:
  br condition, %outer, %loop

outer:
  br %outer_header

[mzolotukhin]

Hi Sanjoy, Chandler,

Thanks for taking a look!
And thanks for the example, Sanjoy, I need to think over it. Probably, we'll need to insert phis if IncomingBB is reachable from the exit block (and then somehow find a merging point to insert another phi), or something like this.

Michael

[mzolotukhin]

• Use SSAUpdate to properly rewrite values.
• Break edges to exit-blocks after separating loop nest if the exit block has a pred from outside the loop.
• Add Sanjoy's test.

[mzolotukhin]

Ping.

[sanjoy]

lib/Transforms/Utils/LoopSimplify.cpp

350 ↗

(On Diff #62891)

Why not use predecessors ?

Actually, why not:

if (any_of(predecessors(ExitBlock), [](BasicBlock *BB) {
  return !L->contains(BB);
    }) {
rewriteLoopExitBlock(L, ExitBlock, DT, LI, PreserveLCSSA);
}

368 ↗

(On Diff #62891)

Why do you need to separately create a SmallSetVector here?

374 ↗

(On Diff #62891)

NewBB is the header of the new loop, right? (if so, a naming change
would be nice). Then I'm not sure if scanning NewBB for LCSSA
violations is sufficient -- what if we have:

loop:
  %iv = phi [ 0, %entry ] [ %iv, (%loop, %left, %right)],  [ %z, %outer ]
  switch(condition), %left, %right, %loop

left:
  %x = def()
  br condition, %outer_l, %loop

outer_l:
  br outer

right:
  %y = def()
  br condition, %outer_r, %loop

outer_r:
  br outer

outer:
  %z = phi(%x, %y)
  br %loop

then the separated structure would be

outer_l:
  %iv = phi [ 0, %entry ], [ %z, outer ]
  br loop

loop:
  switch(condition), %left, %right, %loop

left:
  %x = def()
  br condition, %outer_l, %loop

outer_l:
  br outer

right:
  %y = def()
  br condition, %outer, %loop

outer_r:
  br outer

outer:
  %z = phi(%x, %y)  ;; this PHI needs to be edited as well
  br %loop

388 ↗

(On Diff #62891)

When is this true?

393 ↗

(On Diff #62891)

s/the exit block/an exit block/
s/the phi-node/an LCSSA phi node/

[mzolotukhin]

• Modify test to catch more corner cases including a case mentioned by Sanjoy. Also, add an assert.
• Make processInstruction from LCSSA.cpp externally available.
• Use formLCSSAForInstruction routine instead of doing it manually.
• Use any_of when rewriting loop exit blocks.

[mzolotukhin]

• We don't need to include SSAUpdated any more.

[mzolotukhin]

Hi Sanjoy,

Thanks for review! You're right that we need to look not only at NewBB but in other blocks that happen to be outside the inner loop as well. I updated the test to check this case as well.

Also, I decided to make processInstruction from LCSSA externally available, since it greatly simplifies the patch. I'll submit the corresponding patch for a separate review (we'll need to iron out the API we want to have there), but I'll keep it here as well just to show you the complete picture.

Thanks,
Michael

[sanjoy]

lgtm with nits

lib/Transforms/Utils/LoopSimplify.cpp

331 ↗

(On Diff #63901)

Can't this just be a SmallVector ?

384 ↗

(On Diff #63901)

How about avoiding repeated calls to formLCSSAForInstruction on the same instruction using a set?

Given that you'll now send in a worklist of instructions anyway, maybe just unique that worklist before sending it in?

594 ↗

(On Diff #63901)

I was asking to use any_of instead of the loop you added. :)

If you want to clean this up also, that's fine too of course. :)

[mzolotukhin]

Thanks for reviewing, Sanjoy!

I committed this in r275891 with your remarks addressed.

Michael

lib/Transforms/Utils/LoopSimplify.cpp

331 ↗

(On Diff #63901)

Indeed it can. Fixed!

384 ↗

(On Diff #63901)

Fixed.

594 ↗

(On Diff #63901)

Oops, wrong spot:)

llvm/trunk/lib/Transforms/Utils/LoopSimplify.cpp

static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
   // not part of the inner loop.
   const std::vector<Loop*> &SubLoops = L->getSubLoops();
   for (size_t I = 0; I != SubLoops.size(); )
     if (BlocksInL.count(SubLoops[I]->getHeader()))
       ++I;   // Loop remains in L
     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;
 }
 
 /// \brief This method is called when the specified loop has more than one
 /// backedge in it.
 ///
 /// If this occurs, revector all of these backedges to target a new basic block
 /// and have that block branch to the loop header.  This ensures that loops
ReprocessLoop:
   // loop preheader/header will dominate the exit blocks.  If the exit block has
   // predecessors from outside of the loop, split the edge now.
   SmallVector<BasicBlock*, 8> ExitBlocks;
   L->getExitBlocks(ExitBlocks);
 
   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);
   }
 
   // If the header has more than two predecessors at this point (from the
   // preheader and from multiple backedges), we must adjust the loop.
   BasicBlock *LoopLatch = L->getLoopLatch();
   if (!LoopLatch) {
     // If this is really a nested loop, rip it out into a child loop.  Don't do
     // this for loops with a giant number of backedges, just factor them into a

llvm/trunk/test/Transforms/LoopSimplify/pr28272.ll

+; 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
+}