Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -323,6 +323,19 @@ BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, bool PreserveLCSSA); +/// \brief Ensures LCSSA form for instruction Inst in the scope of loop L. +/// +/// For the given instruction in the loop which have uses outside of the loop, +/// an LCSSA PHI node is inserted and the uses outside the loop are rewritten to +/// use this node. +/// +/// LoopInfo and DominatorTree are required and preserved. +/// +/// Returns true if any modifications are made. +bool formLCSSAForInstruction(Loop &L, Instruction &Inst, DominatorTree &DT, + const SmallVectorImpl &ExitBlocks, + PredIteratorCache &PredCache, LoopInfo *LI); + /// \brief Simplify each loop in a loop nest recursively. /// /// This takes a potentially un-simplified loop L (and its children) and turns Index: lib/Transforms/Utils/LCSSA.cpp =================================================================== --- lib/Transforms/Utils/LCSSA.cpp +++ lib/Transforms/Utils/LCSSA.cpp @@ -60,7 +60,7 @@ /// Given an instruction in the loop, check to see if it has any uses that are /// outside the current loop. If so, insert LCSSA PHI nodes and rewrite the /// uses. -static bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT, +bool llvm::formLCSSAForInstruction(Loop &L, Instruction &Inst, DominatorTree &DT, const SmallVectorImpl &ExitBlocks, PredIteratorCache &PredCache, LoopInfo *LI) { SmallVector UsesToRewrite; @@ -190,7 +190,7 @@ // Recurse and re-process each PHI instruction. FIXME: we should really // convert this entire thing to a worklist approach where we process a // vector of instructions... - processInstruction(*OtherLoop, *I, DT, EBs, PredCache, LI); + formLCSSAForInstruction(*OtherLoop, *I, DT, EBs, PredCache, LI); } // Remove PHI nodes that did not have any uses rewritten. @@ -243,7 +243,7 @@ !isa(I.user_back()))) continue; - Changed |= processInstruction(L, I, DT, ExitBlocks, PredCache, LI); + Changed |= formLCSSAForInstruction(L, I, DT, ExitBlocks, PredCache, LI); } } Index: lib/Transforms/Utils/LoopSimplify.cpp =================================================================== --- lib/Transforms/Utils/LoopSimplify.cpp +++ lib/Transforms/Utils/LoopSimplify.cpp @@ -61,6 +61,7 @@ #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" +#include "llvm/IR/PredIteratorCache.h" #include "llvm/IR/Type.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -326,6 +327,8 @@ else NewOuter->addChildLoop(L->removeChildLoop(SubLoops.begin() + I)); + SmallSetVector OuterLoopBlocks; + OuterLoopBlocks.insert(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) { @@ -333,12 +336,59 @@ 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.insert(BB); + } --i; } } + // Split edges to exit blocks from the inner loop, if they emerged in the + // process of separating the outer one. + SmallVector ExitBlocks; + L->getExitBlocks(ExitBlocks); + SmallSetVector 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)) { + rewriteLoopExitBlock(L, ExitBlock, DT, LI, PreserveLCSSA); + break; + } + } + + 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. + // We've just rewritten the exit blocks, so we have to construct + // ExitBlocksSet again. + SmallVector ExitBlocks; + L->getExitBlocks(ExitBlocks); + + PredIteratorCache PredCache; + + // 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. + for (BasicBlock *OuterBB: OuterLoopBlocks) { + for (Instruction &I : *OuterBB) { + for (Value *Op : I.operands()) { + Instruction *OpI = dyn_cast(Op); + if (!OpI || !L->contains(OpI)) + continue; + formLCSSAForInstruction(*L, *OpI, *DT, ExitBlocks, PredCache, LI); + } + } + } + assert(NewOuter->isRecursivelyLCSSAForm(*DT) && + "LCSSA is broken after separating nested loops!"); + } + return NewOuter; } @@ -540,17 +590,12 @@ SmallSetVector 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 Index: test/Transforms/LoopSimplify/pr28272.ll =================================================================== --- /dev/null +++ test/Transforms/LoopSimplify/pr28272.ll @@ -0,0 +1,72 @@ +; RUN: opt < %s -lcssa -loop-unroll -S | FileCheck %s +target triple = "x86_64-unknown-linux-gnu" + +; Check that we don't crash on this test. +; LoopSimplify is invoked by LoopUnroll. +; 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 +}