diff --git a/llvm/lib/Transforms/Scalar/LoopDeletion.cpp b/llvm/lib/Transforms/Scalar/LoopDeletion.cpp --- a/llvm/lib/Transforms/Scalar/LoopDeletion.cpp +++ b/llvm/lib/Transforms/Scalar/LoopDeletion.cpp @@ -18,6 +18,7 @@ #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopIterator.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/MemorySSA.h" @@ -36,6 +37,11 @@ STATISTIC(NumDeleted, "Number of loops deleted"); +static cl::opt EnableSymbolicExecution( + "loop-deletion-enable-symbolic-execution", cl::Hidden, cl::init(true), + cl::desc("Break backedge through symbolic execution of 1st iteration " + "attempting to prove that the backedge is never taken")); + enum class LoopDeletionResult { Unmodified, Modified, @@ -168,6 +174,171 @@ return true; } +static Value * +getValueOnFirstIteration(Value *V, DenseMap &FirstIterValue, + const SimplifyQuery &SQ) { + // Quick hack: do not flood cache with non-instruction values. + if (!isa(V)) + return V; + // Do we already know cached result? + auto Existing = FirstIterValue.find(V); + if (Existing != FirstIterValue.end()) + return Existing->second; + Value *FirstIterV = nullptr; + if (auto *BO = dyn_cast(V)) { + Value *LHS = + getValueOnFirstIteration(BO->getOperand(0), FirstIterValue, SQ); + Value *RHS = + getValueOnFirstIteration(BO->getOperand(1), FirstIterValue, SQ); + FirstIterV = SimplifyBinOp(BO->getOpcode(), LHS, RHS, SQ); + } + if (!FirstIterV) + FirstIterV = V; + FirstIterValue[V] = FirstIterV; + return FirstIterV; +} + +// Try to prove that one of conditions that dominates the latch must exit on 1st +// iteration. +static bool canProveExitOnFirstIteration(Loop *L, DominatorTree &DT, + LoopInfo &LI) { + // Disabled by option. + if (!EnableSymbolicExecution) + return false; + + BasicBlock *Latch = L->getLoopLatch(); + + if (!Latch) + return false; + + LoopBlocksRPO RPOT(L); + RPOT.perform(&LI); + + // For the optimization to be correct, we need RPOT to have a property that + // each block is processed after all its predecessors, which may only be + // violated for headers of the current loop and all nested loops. Irreducible + // CFG provides multiple ways to break this assumption, so we do not want to + // deal with it. + if (containsIrreducibleCFG(RPOT, LI)) + return false; + + BasicBlock *Header = L->getHeader(); + // Blocks that are reachable on the 1st iteration. + SmallPtrSet LiveBlocks; + // Edges that are reachable on the 1st iteration. + DenseSet LiveEdges; + LiveBlocks.insert(L->getHeader()); + + SmallPtrSet Visited; + auto MarkLiveEdge = [&](BasicBlock *From, BasicBlock *To) { + assert(LiveBlocks.count(From) && "Must be live!"); + assert((LI.isLoopHeader(To) || !Visited.count(To)) && + "Only canonical backedges are allowed. Irreducible CFG?"); + assert((LiveBlocks.count(To) || !Visited.count(To)) && + "We already discarded this block as dead!"); + LiveBlocks.insert(To); + LiveEdges.insert({ From, To }); + }; + + auto MarkAllSuccessorsLive = [&](BasicBlock *BB) { + for (auto *Succ : successors(BB)) + MarkLiveEdge(BB, Succ); + }; + + // Check if there is only one predecessor on 1st iteration. Note that because + // we iterate in RPOT, we have already visited all its (non-latch) + // predecessors. + auto GetSolePredecessorOnFirstIteration = [&](BasicBlock * BB)->BasicBlock * { + if (BB == Header) + return L->getLoopPredecessor(); + BasicBlock *OnlyPred = nullptr; + for (auto *Pred : predecessors(BB)) + if (OnlyPred != Pred && LiveEdges.count({ Pred, BB })) { + // 2 live preds. + if (OnlyPred) + return nullptr; + OnlyPred = Pred; + } + + assert(OnlyPred && "No live predecessors?"); + return OnlyPred; + }; + DenseMap FirstIterValue; + + // Use the following algorithm to prove we never take the latch on the 1st + // iteration: + // 1. Traverse in topological order, so that whenever we visit a block, all + // its predecessors are already visited. + // 2. If we can prove that the block may have only 1 predecessor on the 1st + // iteration, map all its phis onto input from this predecessor. + // 3a. If we can prove which successor of out block is taken on the 1st + // iteration, mark this successor live. + // 3b. If we cannot prove it, conservatively assume that all successors are + // live. + auto &DL = L->getHeader()->getModule()->getDataLayout(); + const SimplifyQuery SQ(DL); + for (auto *BB : RPOT) { + Visited.insert(BB); + + // This block is not reachable on the 1st iterations. + if (!LiveBlocks.count(BB)) + continue; + + // Skip inner loops. + if (LI.getLoopFor(BB) != L) { + MarkAllSuccessorsLive(BB); + continue; + } + + // If this block has only one live pred, map its phis onto their SCEVs. + if (auto *OnlyPred = GetSolePredecessorOnFirstIteration(BB)) + for (auto &PN : BB->phis()) { + if (!PN.getType()->isIntegerTy()) + continue; + auto *Incoming = PN.getIncomingValueForBlock(OnlyPred); + if (DT.dominates(Incoming, BB->getTerminator())) { + Value *FirstIterV = + getValueOnFirstIteration(Incoming, FirstIterValue, SQ); + FirstIterValue[&PN] = FirstIterV; + } + } + + using namespace PatternMatch; + ICmpInst::Predicate Pred; + Value *LHS, *RHS; + BasicBlock *IfTrue, *IfFalse; + auto *Term = BB->getTerminator(); + // TODO: Handle switch. + if (!match(Term, m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)), + m_BasicBlock(IfTrue), m_BasicBlock(IfFalse)))) { + MarkAllSuccessorsLive(BB); + continue; + } + + if (!LHS->getType()->isIntegerTy()) { + MarkAllSuccessorsLive(BB); + continue; + } + + // Can we prove constant true or false for this condition? + LHS = getValueOnFirstIteration(LHS, FirstIterValue, SQ); + RHS = getValueOnFirstIteration(RHS, FirstIterValue, SQ); + auto *KnownCondition = + dyn_cast_or_null(SimplifyICmpInst(Pred, LHS, RHS, SQ)); + if (!KnownCondition) { + MarkAllSuccessorsLive(BB); + continue; + } + if (KnownCondition->isAllOnesValue()) + MarkLiveEdge(BB, IfTrue); + else + MarkLiveEdge(BB, IfFalse); + } + + // We can break the latch if it wasn't live. + return !LiveEdges.count({ Latch, Header }); +} + /// 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. @@ -181,7 +352,9 @@ return LoopDeletionResult::Unmodified; auto *BTC = SE.getBackedgeTakenCount(L); - if (!BTC->isZero()) + if (!isa(BTC) && SE.isKnownNonZero(BTC)) + return LoopDeletionResult::Unmodified; + if (!BTC->isZero() && !canProveExitOnFirstIteration(L, DT, LI)) return LoopDeletionResult::Unmodified; breakLoopBackedge(L, DT, SE, LI, MSSA); diff --git a/llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll b/llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll --- a/llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll +++ b/llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll @@ -338,23 +338,24 @@ unreachable } -; TODO: We can break the backedge here. define i32 @test_ne_const() { ; CHECK-LABEL: @test_ne_const( ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ] ; CHECK-NEXT: [[SUB:%.*]] = sub i32 4, [[SUM]] ; CHECK-NEXT: [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0 -; CHECK-NEXT: br i1 [[IS_POSITIVE]], label [[BACKEDGE]], label [[IF_FALSE:%.*]] +; CHECK-NEXT: br i1 [[IS_POSITIVE]], label [[BACKEDGE:%.*]], label [[IF_FALSE:%.*]] ; CHECK: if.false: ; CHECK-NEXT: br label [[BACKEDGE]] ; CHECK: backedge: ; CHECK-NEXT: [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[LOOP]] ] -; CHECK-NEXT: [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]] +; CHECK-NEXT: [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]] ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 4 -; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]] +; CHECK-NEXT: br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]] +; CHECK: backedge.loop_crit_edge: +; CHECK-NEXT: unreachable ; CHECK: done: ; CHECK-NEXT: [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[SUM_NEXT_LCSSA]] @@ -388,23 +389,24 @@ unreachable } -; TODO: We can break the backedge here. define i32 @test_slt_const() { ; CHECK-LABEL: @test_slt_const( ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ] ; CHECK-NEXT: [[SUB:%.*]] = sub i32 4, [[SUM]] ; CHECK-NEXT: [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0 -; CHECK-NEXT: br i1 [[IS_POSITIVE]], label [[BACKEDGE]], label [[IF_FALSE:%.*]] +; CHECK-NEXT: br i1 [[IS_POSITIVE]], label [[BACKEDGE:%.*]], label [[IF_FALSE:%.*]] ; CHECK: if.false: ; CHECK-NEXT: br label [[BACKEDGE]] ; CHECK: backedge: ; CHECK-NEXT: [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[LOOP]] ] -; CHECK-NEXT: [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]] +; CHECK-NEXT: [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]] ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp slt i32 [[SUM_NEXT]], 4 -; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]] +; CHECK-NEXT: br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]] +; CHECK: backedge.loop_crit_edge: +; CHECK-NEXT: unreachable ; CHECK: done: ; CHECK-NEXT: [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[SUM_NEXT_LCSSA]] @@ -438,23 +440,24 @@ unreachable } -; TODO: We can break the backedge here. define i32 @test_ult_const() { ; CHECK-LABEL: @test_ult_const( ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ] ; CHECK-NEXT: [[SUB:%.*]] = sub i32 4, [[SUM]] ; CHECK-NEXT: [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0 -; CHECK-NEXT: br i1 [[IS_POSITIVE]], label [[BACKEDGE]], label [[IF_FALSE:%.*]] +; CHECK-NEXT: br i1 [[IS_POSITIVE]], label [[BACKEDGE:%.*]], label [[IF_FALSE:%.*]] ; CHECK: if.false: ; CHECK-NEXT: br label [[BACKEDGE]] ; CHECK: backedge: ; CHECK-NEXT: [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[LOOP]] ] -; CHECK-NEXT: [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]] +; CHECK-NEXT: [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]] ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp ult i32 [[SUM_NEXT]], 4 -; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]] +; CHECK-NEXT: br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]] +; CHECK: backedge.loop_crit_edge: +; CHECK-NEXT: unreachable ; CHECK: done: ; CHECK-NEXT: [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[SUM_NEXT_LCSSA]] @@ -488,23 +491,24 @@ unreachable } -; TODO: We can break the backedge here. define i32 @test_sgt_const() { ; CHECK-LABEL: @test_sgt_const( ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ] ; CHECK-NEXT: [[SUB:%.*]] = sub i32 4, [[SUM]] ; CHECK-NEXT: [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0 -; CHECK-NEXT: br i1 [[IS_POSITIVE]], label [[BACKEDGE]], label [[IF_FALSE:%.*]] +; CHECK-NEXT: br i1 [[IS_POSITIVE]], label [[BACKEDGE:%.*]], label [[IF_FALSE:%.*]] ; CHECK: if.false: ; CHECK-NEXT: br label [[BACKEDGE]] ; CHECK: backedge: ; CHECK-NEXT: [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[LOOP]] ] -; CHECK-NEXT: [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]] +; CHECK-NEXT: [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]] ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp sgt i32 [[SUM_NEXT]], 4 -; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]] +; CHECK-NEXT: br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]] +; CHECK: backedge.loop_crit_edge: +; CHECK-NEXT: unreachable ; CHECK: done: ; CHECK-NEXT: [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[SUM_NEXT_LCSSA]] @@ -538,23 +542,24 @@ unreachable } -; TODO: We can break the backedge here. define i32 @test_ugt_const() { ; CHECK-LABEL: @test_ugt_const( ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ] ; CHECK-NEXT: [[SUB:%.*]] = sub i32 4, [[SUM]] ; CHECK-NEXT: [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0 -; CHECK-NEXT: br i1 [[IS_POSITIVE]], label [[BACKEDGE]], label [[IF_FALSE:%.*]] +; CHECK-NEXT: br i1 [[IS_POSITIVE]], label [[BACKEDGE:%.*]], label [[IF_FALSE:%.*]] ; CHECK: if.false: ; CHECK-NEXT: br label [[BACKEDGE]] ; CHECK: backedge: ; CHECK-NEXT: [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[LOOP]] ] -; CHECK-NEXT: [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]] +; CHECK-NEXT: [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]] ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp ugt i32 [[SUM_NEXT]], 4 -; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]] +; CHECK-NEXT: br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]] +; CHECK: backedge.loop_crit_edge: +; CHECK-NEXT: unreachable ; CHECK: done: ; CHECK-NEXT: [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[SUM_NEXT_LCSSA]] @@ -588,28 +593,29 @@ unreachable } -; TODO: We can break the backedge here. define i32 @test_multiple_pred_const() { ; CHECK-LABEL: @test_multiple_pred_const( ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ] ; CHECK-NEXT: [[SUB:%.*]] = sub i32 4, [[SUM]] ; CHECK-NEXT: [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0 ; CHECK-NEXT: br i1 [[IS_POSITIVE]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]] ; CHECK: if.true: ; CHECK-NEXT: switch i32 4, label [[FAILURE:%.*]] [ -; CHECK-NEXT: i32 100, label [[BACKEDGE]] +; CHECK-NEXT: i32 100, label [[BACKEDGE:%.*]] ; CHECK-NEXT: i32 200, label [[BACKEDGE]] ; CHECK-NEXT: ] ; CHECK: if.false: ; CHECK-NEXT: br label [[BACKEDGE]] ; CHECK: backedge: ; CHECK-NEXT: [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE]] ], [ [[SUB]], [[IF_TRUE]] ], [ [[SUB]], [[IF_TRUE]] ] -; CHECK-NEXT: [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]] +; CHECK-NEXT: [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]] ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 4 -; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]] +; CHECK-NEXT: br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]] +; CHECK: backedge.loop_crit_edge: +; CHECK-NEXT: unreachable ; CHECK: done: ; CHECK-NEXT: [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ] ; CHECK-NEXT: ret i32 [[SUM_NEXT_LCSSA]] diff --git a/llvm/test/Transforms/LoopDeletion/unreachable-loops.ll b/llvm/test/Transforms/LoopDeletion/unreachable-loops.ll --- a/llvm/test/Transforms/LoopDeletion/unreachable-loops.ll +++ b/llvm/test/Transforms/LoopDeletion/unreachable-loops.ll @@ -319,9 +319,7 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[L1:%.*]] ; CHECK: L1.loopexit: -; CHECK-NEXT: br label [[L1_LOOPEXIT_SPLIT:%.*]] -; CHECK: L1.loopexit.split: -; CHECK-NEXT: unreachable +; CHECK-NEXT: br label [[L1]] ; CHECK: L1: ; CHECK-NEXT: br i1 true, label [[EXIT:%.*]], label [[L2_PREHEADER:%.*]] ; CHECK: L2.preheader: @@ -331,7 +329,9 @@ ; CHECK-NEXT: br label [[L3:%.*]] ; CHECK: L3: ; CHECK-NEXT: [[COND2:%.*]] = icmp slt i64 [[Y_L2_LCSSA]], [[N:%.*]] -; CHECK-NEXT: br i1 [[COND2]], label [[L3]], label [[L1_LOOPEXIT:%.*]] +; CHECK-NEXT: br i1 [[COND2]], label [[L3_L3_CRIT_EDGE:%.*]], label [[L1_LOOPEXIT:%.*]] +; CHECK: L3.L3_crit_edge: +; CHECK-NEXT: unreachable ; CHECK: exit: ; CHECK-NEXT: ret void ; diff --git a/llvm/test/Transforms/LoopDeletion/zero-btc.ll b/llvm/test/Transforms/LoopDeletion/zero-btc.ll --- a/llvm/test/Transforms/LoopDeletion/zero-btc.ll +++ b/llvm/test/Transforms/LoopDeletion/zero-btc.ll @@ -155,20 +155,21 @@ ret void } -; TODO: SCEV seems not to recognize this as a zero btc loop define void @test_multi_exit3(i1 %cond1) { ; CHECK-LABEL: @test_multi_exit3( ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_INC:%.*]], [[LATCH:%.*]] ] +; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ] ; CHECK-NEXT: store i32 0, i32* @G, align 4 -; CHECK-NEXT: br i1 [[COND1:%.*]], label [[LATCH]], label [[EXIT:%.*]] +; CHECK-NEXT: br i1 [[COND1:%.*]], label [[LATCH:%.*]], label [[EXIT:%.*]] ; CHECK: latch: ; CHECK-NEXT: store i32 1, i32* @G, align 4 -; CHECK-NEXT: [[IV_INC]] = add i32 [[IV]], 1 +; CHECK-NEXT: [[IV_INC:%.*]] = add i32 [[IV]], 1 ; CHECK-NEXT: [[BE_TAKEN:%.*]] = icmp ne i32 [[IV_INC]], 1 -; CHECK-NEXT: br i1 [[BE_TAKEN]], label [[LOOP]], label [[EXIT]] +; CHECK-NEXT: br i1 [[BE_TAKEN]], label [[LATCH_LOOP_CRIT_EDGE:%.*]], label [[EXIT]] +; CHECK: latch.loop_crit_edge: +; CHECK-NEXT: unreachable ; CHECK: exit: ; CHECK-NEXT: ret void ;