Index: llvm/include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- llvm/include/llvm/Transforms/Utils/LoopUtils.h +++ llvm/include/llvm/Transforms/Utils/LoopUtils.h @@ -338,7 +338,7 @@ /// /// All loop passes should call this as part of implementing their \c /// getAnalysisUsage. -void getLoopAnalysisUsage(AnalysisUsage &AU); +void getLoopAnalysisUsage(AnalysisUsage &AU, bool Preserve = true); /// Returns true if is legal to hoist or sink this instruction disregarding the /// possible introduction of faults. Reasoning about potential faulting Index: llvm/lib/Transforms/Scalar/LoopDeletion.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LoopDeletion.cpp +++ llvm/lib/Transforms/Scalar/LoopDeletion.cpp @@ -32,6 +32,9 @@ #define DEBUG_TYPE "loop-delete" STATISTIC(NumDeleted, "Number of loops deleted"); +STATISTIC(NumEarlyExits, "Number of early exits inserted"); +STATISTIC(NumLoopsElim, "Number of loops eliminated (no remaining blocks)"); +STATISTIC(NumSCEV0Skipped, "Number of skipped loops (SCEV 0)"); enum class LoopDeletionResult { Unmodified, @@ -39,6 +42,7 @@ Deleted, }; + static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B) { if (A == LoopDeletionResult::Deleted || B == LoopDeletionResult::Deleted) return LoopDeletionResult::Deleted; @@ -47,6 +51,14 @@ return LoopDeletionResult::Unmodified; } +static bool BBHasSideEffects(const BasicBlock *BB) { + if (any_of(*BB, [](const Instruction &I) { + return I.mayHaveSideEffects() && !I.isDroppable(); + })) + return true; + return false; +} + /// Determines if a loop is dead. /// /// This assumes that we've already checked for unique exit and exiting blocks, @@ -96,9 +108,7 @@ // This includes instructions that could write to memory, and loads that are // marked volatile. for (auto &I : L->blocks()) - if (any_of(*I, [](Instruction &I) { - return I.mayHaveSideEffects() && !I.isDroppable(); - })) + if (BBHasSideEffects(I)) return false; return true; } @@ -135,6 +145,10 @@ return true; } +static bool loopMustProgress(Loop *L) { + return L->getHeader()->getParent()->mustProgress() || hasMustProgress(L); +} + /// If we can prove the backedge is untaken, remove it. This destroys the /// loop, but leaves the (now trivially loop invariant) control flow and /// side effects (if any) in place. @@ -233,8 +247,7 @@ // Don't remove loops for which we can't solve the trip count unless the loop // was required to make progress but has been determined to be dead. const SCEV *S = SE.getConstantMaxBackedgeTakenCount(L); - if (isa(S) && - !L->getHeader()->getParent()->mustProgress() && !hasMustProgress(L)) { + if (isa(S) && !loopMustProgress(L)) { LLVM_DEBUG(dbgs() << "Could not compute SCEV MaxBackedgeTakenCount and was " "not required to make progress.\n"); return Changed ? LoopDeletionResult::Modified @@ -253,6 +266,220 @@ return LoopDeletionResult::Deleted; } +static bool usesLoopPHI(const Instruction *I, const Loop *L) { + if (!L->contains(I->getParent())) + return false; + if (isa(I)) + return true; + for (auto &Op : I->operands()) + if (const Instruction *OpI = dyn_cast(&Op)) + if (usesLoopPHI(OpI, L)) + return true; + return false; +} + +static bool BBHasLIVCondOnDeadPath(const BasicBlock *BB, Loop *L) { + // Check if the condition might change after an iteration across a dead + // path. TODO: worth checking if incoming value from preheader/latch are + // the same and allow that case? + const Instruction *TI = BB->getTerminator(); + const Instruction *Cond = nullptr; + if (const BranchInst *BI = dyn_cast(TI)) { + if (BI->isConditional()) + Cond = dyn_cast(BI->getCondition()); + } else if (const SwitchInst *SI = dyn_cast(TI)) { + Cond = dyn_cast(SI->getCondition()); + } else + return false; + return (Cond == nullptr || !usesLoopPHI(Cond, L)); +} + +static bool hasPredecessorInLoop(const BasicBlock *BB, Loop *L) { + for (auto *Pred: predecessors(BB)) + if (L->contains(Pred)) + return true; + return false; +} + +static bool hasSuccessorInLoop(const BasicBlock *BB, Loop *L) { + for (auto *Succ: successors(BB)) + if (L->contains(Succ)) + return true; + return false; +} + +static void findNoSEBlocks(SmallPtrSet &NoSEBBs, + Loop *L, bool Forward) { + auto takeBlock = [&L, &Forward](BasicBlock *BB) -> bool { + return !BBHasSideEffects(BB) && (!Forward || BBHasLIVCondOnDeadPath(BB, L)); + }; + + BasicBlock *Header = L->getHeader(); + BasicBlock *Latch = L->getLoopLatch(); + BasicBlock *Start = Forward ? Header : Latch; + if (!takeBlock(Start)) + return; + NoSEBBs.insert(Start); + + bool Change = true; + while (Change) { + Change = false; + for (auto BB : L->getBlocks()) { + if (NoSEBBs.count(BB) || !takeBlock(BB)) + continue; + + bool All = true; + if (Forward) { + for (auto *Pred: predecessors(BB)) + if (!NoSEBBs.count(Pred)) { + All = false; + break; + } + } else { + for (auto *Succ: successors(BB)) + if (L->contains(Succ) && !NoSEBBs.count(Succ)) { + All = false; + break; + } + } + if (All) { + NoSEBBs.insert(BB); + Change = true; + } + } + } +} + +// Return the exit block on the path from BB to the backedge. If there is +// none, return the unique exit block if it exists. If there are more than +// one, return null. Make sure there are no live-out values. +static BasicBlock *findExitBlock(const BasicBlock *BB, Loop *L) { + BasicBlock *ExitBB = L->getUniqueExitBlock(); + + if (!ExitBB) { + SmallVector WorkList; + WorkList.push_back(BB); + SmallPtrSet Visited; + while (!WorkList.empty()) { + const BasicBlock *CurrBB = WorkList.pop_back_val(); + if (!Visited.insert(CurrBB).second) + continue; + + const Instruction *TI = CurrBB->getTerminator(); + for (unsigned i = 0, e = TI->getNumOperands(); i != e; ++i) + if (BasicBlock *SuccBB = dyn_cast(TI->getOperand(i))) { + if (!L->contains(SuccBB)) { + if (ExitBB != nullptr && ExitBB != SuccBB) + return nullptr; + ExitBB = SuccBB; + } else if (SuccBB != L->getHeader()){ + WorkList.push_back(SuccBB); + } + } + } + } + + return (ExitBB && !isa(ExitBB->begin())) ? ExitBB : nullptr; +} + +#ifndef NDEBUG +static void dumpBBSet(std::string Msg, SmallPtrSet &S) { + dbgs() << Msg << ": "; + for (const BasicBlock *BB : S) + dbgs() << BB->getName() << ", "; + dbgs() << "\n"; +} +#endif + +static LoopDeletionResult tryInsertEarlyExit(Loop *L, DominatorTree &DT, + ScalarEvolution &SE, LoopInfo &LI, + MemorySSA *MSSA, + OptimizationRemarkEmitter &ORE) { + assert(L->isLCSSAForm(DT) && "Expected LCSSA!"); + BasicBlock *LatchBB = L->getLoopLatch(); + if (!LatchBB || L->getNumBlocks() == 1) + return LoopDeletionResult::Unmodified; + + // Check for a known trip count or a forward progress gurantee. + const SCEV *S = SE.getConstantMaxBackedgeTakenCount(L); + if (isa(S) && !loopMustProgress(L)) + return LoopDeletionResult::Unmodified; + + if (S->isZero()) { + // This should be handled by D93906 "Break backedge of loops when known + // not taken". + NumSCEV0Skipped++; + return LoopDeletionResult::Unmodified; + } + + // Compute two sets of blocks which are free of side-effets. Top starts + // from header, and Bot starts from latch. + SmallPtrSet NoSEBBsTop, NoSEBBsBot; + findNoSEBlocks(NoSEBBsTop, L, true /*Forward*/); + findNoSEBlocks(NoSEBBsBot, L, false /*Forward*/); + LLVM_DEBUG(dbgs() << "Trying to insert early exits:\n"; + dumpBBSet("Top region", NoSEBBsTop); + dumpBBSet("Bot region", NoSEBBsBot);); + + bool Change = false; + for (auto BB : NoSEBBsTop) { + Instruction *TI = BB->getTerminator(); + // We can replace an edge if the conditions will always evaluate the same + // on the dead path from header to BB, with only one possible exit block + // from the target BB in the bottom region. + for (unsigned i = 0, e = TI->getNumOperands(); i != e; ++i) + if (BasicBlock *SuccBB = dyn_cast(TI->getOperand(i))) + if (NoSEBBsBot.count(SuccBB)) + if (BasicBlock *ExitBB = findExitBlock(SuccBB, L)) { + LLVM_DEBUG(dbgs() << "Inserting early exit in " << BB->getName() << ":\n";); + LLVM_DEBUG(TI->dump(); dbgs() << " =>\n";); + TI->setOperand(i, ExitBB); + for (PHINode &Phi : SuccBB->phis()) + Phi.removeIncomingValue(BB); + LLVM_DEBUG(TI->dump();); + Change = true; + NumEarlyExits++; + } + } + + if (!Change) + return LoopDeletionResult::Unmodified; + + // Update data structures. + // NB! Did not yet manage to update everything correctly, so relying on + // recomputation of the analyses (see getAnalysisUsage()). + SE.forgetLoop(L); + DT.recalculate(*const_cast(LatchBB->getParent())); + Loop *CurrLoop = L; + while (CurrLoop != nullptr) { + // Iteratively remove disconnected blocks from CurrLoop. + Change = true; + while (Change) { + Change = false; + std::vector LoopBlocks(CurrLoop->block_begin(), + CurrLoop->block_end()); + for (auto BB : LoopBlocks) + if (!hasPredecessorInLoop(BB, CurrLoop) || + !hasSuccessorInLoop(BB, CurrLoop)) { + CurrLoop->removeBlockFromLoop(BB); + Change = true; + } + } + CurrLoop = CurrLoop->getParentLoop(); + } + + // If all blocks have been removed, return 'Deleted', or LoopPass will try + // to dump it which doesn't work with an emtpy loop. + LoopDeletionResult Result = L->getNumBlocks() ? LoopDeletionResult::Modified + : LoopDeletionResult::Deleted; + if (Result == LoopDeletionResult::Deleted) { + LI.erase(L); + NumLoopsElim++; + LLVM_DEBUG(dbgs() << "Loop eliminated: all blocks removed.\n"; ); + } + return Result; +} + PreservedAnalyses LoopDeletionPass::run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { @@ -273,6 +500,10 @@ Result = merge(Result, breakBackedgeIfNotTaken(&L, AR.DT, AR.SE, AR.LI, AR.MSSA, ORE)); + if (Result != LoopDeletionResult::Deleted) + Result = merge(Result, tryInsertEarlyExit(&L, AR.DT, AR.SE, AR.LI, AR.MSSA, + ORE)); + if (Result == LoopDeletionResult::Unmodified) return PreservedAnalyses::all(); @@ -298,7 +529,7 @@ void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addPreserved(); - getLoopAnalysisUsage(AU); + getLoopAnalysisUsage(AU, false/*Preserve: Experimental*/); } }; } @@ -331,12 +562,13 @@ LLVM_DEBUG(L->dump()); LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI, MSSA, ORE); - // If we can prove the backedge isn't taken, just break it and be done. This // leaves the loop structure in place which means it can handle dispatching // to the right exit based on whatever loop invariant structure remains. if (Result != LoopDeletionResult::Deleted) Result = merge(Result, breakBackedgeIfNotTaken(L, DT, SE, LI, MSSA, ORE)); + if (Result != LoopDeletionResult::Deleted) + Result = merge(Result, tryInsertEarlyExit(L, DT, SE, LI, MSSA, ORE)); if (Result == LoopDeletionResult::Deleted) LPM.markLoopAsDeleted(*L); Index: llvm/lib/Transforms/Utils/LoopUtils.cpp =================================================================== --- llvm/lib/Transforms/Utils/LoopUtils.cpp +++ llvm/lib/Transforms/Utils/LoopUtils.cpp @@ -147,27 +147,32 @@ return UsedOutside; } -void llvm::getLoopAnalysisUsage(AnalysisUsage &AU) { +void llvm::getLoopAnalysisUsage(AnalysisUsage &AU, bool Preserve) { // By definition, all loop passes need the LoopInfo analysis and the // Dominator tree it depends on. Because they all participate in the loop // pass manager, they must also preserve these. AU.addRequired(); - AU.addPreserved(); + if (Preserve) + AU.addPreserved(); AU.addRequired(); - AU.addPreserved(); + if (Preserve) + AU.addPreserved(); // We must also preserve LoopSimplify and LCSSA. We locally access their IDs // here because users shouldn't directly get them from this header. extern char &LoopSimplifyID; extern char &LCSSAID; AU.addRequiredID(LoopSimplifyID); - AU.addPreservedID(LoopSimplifyID); + if (Preserve) + AU.addPreservedID(LoopSimplifyID); AU.addRequiredID(LCSSAID); - AU.addPreservedID(LCSSAID); + if (Preserve) + AU.addPreservedID(LCSSAID); // This is used in the LPPassManager to perform LCSSA verification on passes // which preserve lcssa form AU.addRequired(); - AU.addPreserved(); + if (Preserve) + AU.addPreserved(); // Loop passes are designed to run inside of a loop pass manager which means // that any function analyses they require must be required by the first loop @@ -180,9 +185,11 @@ AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); - AU.addPreserved(); + if (Preserve) + AU.addPreserved(); AU.addRequired(); - AU.addPreserved(); + if (Preserve) + AU.addPreserved(); // FIXME: When all loop passes preserve MemorySSA, it can be required and // preserved here instead of the individual handling in each pass. } Index: llvm/test/Transforms/LoopDeletion/early-exits.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/LoopDeletion/early-exits.ll @@ -0,0 +1,507 @@ +; RUN: opt < %s -loop-deletion -S | FileCheck %s +; +; Test insertion of early exits from dead paths. + +@g = external global i8 + +; Known trip count. If %loop branches to %latch, the loop is dead. +define void @f0() { +; CHECK-LABEL: @f0( +entry: + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK: br i1 %cmp, label %body, label %exit + %IV = phi i64 [ 0, %entry ], [ %next, %latch ] + %b = load i8, i8* @g + %cmp = icmp ne i8 %b, 0 + br i1 %cmp, label %body, label %latch + +body: + call void @foo() + br label %latch + +latch: + %next = add i64 %IV, 1 + %cmp2 = icmp ne i64 %IV, 128 + br i1 %cmp2, label %loop, label %exit + +exit: + ret void +} + +; Loop has mustprogress attribute and @Rb_tree_increment is readonly. +; If %loop branches to %latch, the loop is dead. +%0 = type { i32, %0*, %0*, %0* } +define void @f1() { +; CHECK-LABEL: @f1( +entry: + br label %loop + +loop: ; preds = %entry, %latch +; CHECK-LABEL: loop: +; CHECK: br i1 %i3.i3.not, label %body, label %exit + %i2.i2 = load i8, i8* inttoptr (i64 8 to i8*) + %0 = and i8 %i2.i2, 1 + %i3.i3.not = icmp eq i8 %0, 0 + br i1 %i3.i3.not, label %body, label %latch + +body: ; preds = %loop + tail call void @foo() + br label %latch + +latch: ; preds = %body, %loop + %i2.i = tail call %0* @Rb_tree_increment() #0 + %i5.i.not = icmp eq %0* %i2.i, null + br i1 %i5.i.not, label %exit, label %loop, !llvm.loop !1 + +exit: ; preds = %latch + ret void +} + +; Header has side-effects +define void @f2() { +; CHECK-LABEL: @f2( +entry: + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK: br i1 %cmp, label %body, label %latch + %IV = phi i64 [ 0, %entry ], [ %next, %latch ] + %b = load volatile i8, i8* @g + %cmp = icmp ne i8 %b, 0 + br i1 %cmp, label %body, label %latch + +body: + call void @foo() + br label %latch + +latch: + %next = add i64 %IV, 1 + %cmp2 = icmp ne i64 %IV, 128 + br i1 %cmp2, label %loop, label %exit + +exit: + ret void +} + +; Latch has side-effects +define void @f3(i64* %dst) { +; CHECK-LABEL: @f3( +entry: + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK: br i1 %cmp, label %body, label %latch + %IV = phi i64 [ 0, %entry ], [ %next, %latch ] + %b = load i8, i8* @g + %cmp = icmp ne i8 %b, 0 + br i1 %cmp, label %body, label %latch + +body: + call void @foo() + br label %latch + +latch: + %next = add i64 %IV, 1 + store volatile i64 0, i64* %dst + %cmp2 = icmp ne i64 %IV, 128 + br i1 %cmp2, label %loop, label %exit + +exit: + ret void +} + +; Condition is not loop-invariant +define void @f4(i64 %src) { +; CHECK-LABEL: @f4( +entry: + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK: br i1 %cmp, label %body, label %latch + %IV = phi i64 [ %src, %entry ], [ %next, %latch ] + %cmp = icmp eq i64 %IV, 0 + br i1 %cmp, label %body, label %latch + +body: + call void @foo() + br label %latch + +latch: + %next = add i64 %IV, 1 + %cmp2 = icmp ne i64 %IV, 128 + br i1 %cmp2, label %loop, label %exit + +exit: + ret void +} + +; Header successors: one has side-effects. +define void @f5(i64 %src) { +; CHECK-LABEL: @f5( +entry: + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK: br i1 %cmp, label %exit, label %body1 + %IV = phi i64 [ %src, %entry ], [ %next, %latch ] + %b = load i8, i8* @g + %cmp = icmp eq i8 %b, 0 + br i1 %cmp, label %body0, label %body1 + +body0: +; CHECK-LABEL: body0: +; CHECK: br label %exit + br label %latch + +body1: +; CHECK-LABEL: body1: +; CHECK: br i1 %cmp1, label %body2, label %latch + call void @foo() + %cmp1 = icmp ne i8 %b, 2 + br i1 %cmp1, label %body2, label %latch + +body2: +; CHECK-LABEL: body2: +; CHECK: br label %latch + call void @foo() + br label %latch + +latch: + %next = add i64 %IV, 1 + %cmp2 = icmp ne i64 %IV, 128 + br i1 %cmp2, label %loop, label %exit + +exit: + ret void +} + +; Switch instruction and multiple latches: only early-exit from those with no +; side-effects. +define void @f6(i64 %src) mustprogress { +; CHECK-LABEL: @f6( +entry: + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK: switch i64 %src, label %exit [ +; CHECK-NEXT: i64 2, label %latch2 +; CHECK-NEXT: i64 4, label %exit + %IV = phi i64 [ %src, %entry ], [ %next1, %latch1 ], + [ %next2, %latch2 ], [ %next4, %latch4 ] + switch i64 %src, label %latch1 [ i64 2, label %latch2 + i64 4, label %latch4 ] + +latch1: + %next1 = add i64 %IV, 1 + %cmp1 = icmp ne i64 %IV, 128 + br i1 %cmp1, label %loop, label %exit + +latch2: + call void @foo() + %next2 = add i64 %IV, 2 + %cmp2 = icmp ne i64 %IV, 128 + br i1 %cmp2, label %loop, label %exit + +latch4: + %next4 = add i64 %IV, 4 + %cmp4 = icmp ne i64 %IV, 128 + br i1 %cmp4, label %loop, label %exit + +exit: + ret void +} + +; This loop has two exits which means deleteLoopIfDead() will bail. The loop +; will however be eliminated after inserting an early exit. +define void @f7(i1 %arg, i1 %arg2) mustprogress { +; CHECK-LABEL: @f7( +entry: + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK: br i1 %arg, label %exit1, label %exit0 + br i1 %arg, label %exit1, label %body + +body: ; preds = %bb1 + br i1 %arg2, label %exit0, label %latch + +exit0: ; preds = %bb2 + unreachable + +latch: ; preds = %bb2 + br label %loop + +exit1: ; preds = %bb1 + ret void +} + +; Another loop with two exits, containing just two dead blocks. +define void @f8() { +; CHECK-LABEL: @f8( +entry: + br label %header + +header: +; CHECK-LABEL: header: +; CHECK: br i1 false, label %exit1, label %exit0 + %i4 = phi i32 [ 0, %entry ], [ %i5, %latch ] + %i5 = add nuw i32 %i4, 1 + br i1 false, label %exit1, label %latch + +exit1: + unreachable + +latch: + %i = icmp ult i32 %i5, undef + br i1 %i, label %header, label %exit0 + +exit0: + unreachable + +} + +; Exiting block with an edge to a no-side-effects latch +define void @f9(i64* %dst) { +; CHECK-LABEL: @f9( +entry: + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK: br i1 %cmp, label %body, label %body2 + %IV = phi i64 [ 0, %entry ], [ %next, %latch ] + %b = load i8, i8* @g + %cmp = icmp ne i8 %b, 0 + br i1 %cmp, label %body, label %body2 + +body: + call void @foo() + br label %latch + +body2: +; CHECK-LABEL: body2: +; CHECK: br i1 false, label %latch, label %exit + br i1 false, label %latch, label %exit + +latch: + %next = add i64 %IV, 1 + store volatile i64 0, i64* %dst + %cmp2 = icmp ne i64 %IV, 128 + br i1 %cmp2, label %loop, label %exit + +exit: + ret void +} + +; Branch from Top (not header) to a Bot (not latch) +define void @f10() { +; CHECK-LABEL: @f10( +entry: + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK: br i1 %cmp, label %body, label %body2 + %IV = phi i64 [ 0, %entry ], [ %next, %latch ] + %b = load i8, i8* @g + %cmp = icmp ne i8 %b, 0 + br i1 %cmp, label %body, label %body2 + +body: + call void @foo() + br label %latch + +body2: +; CHECK-LABEL: body2: +; CHECK: br i1 false, label %body, label %exit + br i1 false, label %body, label %bot + +bot: +; CHECK-LABEL: bot: +; CHECK: br label %exit + br label %latch + +latch: + %next = add i64 %IV, 1 + %cmp2 = icmp ne i64 %IV, 128 + br i1 %cmp2, label %loop, label %exit + +exit: + ret void +} + +; Multiple exits, but only one on dead path. +define void @f11() { +; CHECK-LABEL: @f11( +entry: + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK: br i1 %cmp, label %body, label %exit + %IV = phi i64 [ 0, %entry ], [ %next, %latch ] + %b = load i8, i8* @g + %cmp = icmp ne i8 %b, 0 + br i1 %cmp, label %body, label %bot1 + +body: + call void @foo() + br label %latch + +bot0: + br i1 false, label %bot1, label %bot2 + +bot1: +; CHECK-LABEL: bot1: +; CHECK: br i1 false, label %exit, label %exit + br i1 false, label %latch, label %exit + +bot2: + br i1 false, label %latch, label %exit2 + +latch: + %next = add i64 %IV, 1 + %cmp2 = icmp ne i64 %IV, 128 + br i1 %cmp2, label %loop, label %exit + +exit: + ret void + +exit2: + ret void +} + +; Branches to two different blocks in Bot, two different and usable exit blocks. +define void @f12() mustprogress { +; CHECK-LABEL: @f12( +entry: + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK: br i1 %cmp, label %body, label %top1 + %IV = phi i64 [ 0, %entry ], [ %next, %latch ] + %b = load i8, i8* @g + %cmp = icmp ne i8 %b, 0 + br i1 %cmp, label %body, label %top1 + +body: + call void @foo() + br label %latch + +top1: +; CHECK-LABEL: top1: +; CHECK: br i1 false, label %exit, label %exit2 + br i1 false, label %bot1, label %bot2 + +bot1: + br i1 false, label %latch, label %exit + +bot2: + br i1 false, label %latch, label %exit2 + +latch: + %next = add i64 %IV, 1 + br label %loop + +exit: + ret void + +exit2: + ret void +} + +; %loop branches to %bot1, but not a single exit block. %bot1 branches to %bot2, +; from wich there is only one exit block. +define void @f13() mustprogress { +; CHECK-LABEL: @f13( +entry: + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK: br i1 %cmp, label %body, label %bot1 + %IV = phi i64 [ 0, %entry ], [ %next, %latch ] + %b = load i8, i8* @g + %cmp = icmp ne i8 %b, 0 + br i1 %cmp, label %body, label %bot1 + +body: + call void @foo() + br label %latch + +bot1: +; CHECK-LABEL: bot1: +; CHECK: br i1 false, label %exit2, label %exit + br i1 false, label %bot2, label %exit + +bot2: + br i1 false, label %latch, label %exit2 + +latch: + %next = add i64 %IV, 1 + br label %loop + +exit: + ret void + +exit2: + ret void +} + +; Loop nest +define void @f14() mustprogress { +; CHECK-LABEL: @f14( +entry: + br label %loop1 + +loop1: +; CHECK-LABEL: loop1: +; CHECK: br i1 %cmp, label %loop2.preheader, label %exit1 + %IV = phi i64 [ 0, %entry ], [ %next, %latch1 ] + %b = load i8, i8* @g + %cmp = icmp ne i8 %b, 0 + br i1 %cmp, label %loop2.preheader, label %latch1 + +loop2.preheader: + br label %loop2 + +loop2: +; CHECK-LABEL: loop2: +; CHECK: br i1 false, label %body2, label %exit2 + br i1 false, label %body2, label %latch2 + +body2: + call void @foo() + br label %latch2 + +latch2: + br i1 true, label %loop2, label %exit2 + +exit2: + br label %latch1 + +latch1: + %next = add i64 %IV, 1 + %cmp2 = icmp ne i64 %IV, 128 + br i1 %cmp2, label %loop1, label %exit1 + +exit1: + ret void +} + +declare void @foo() +declare %0* @Rb_tree_increment() +attributes #0 = { nounwind readonly } +!1 = distinct !{!1, !2, !3} +!2 = !{!"llvm.loop.mustprogress"} +!3 = !{!"llvm.loop.unroll.disable"}