Index: llvm/lib/Transforms/Scalar/LoopDeletion.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LoopDeletion.cpp +++ llvm/lib/Transforms/Scalar/LoopDeletion.cpp @@ -17,6 +17,7 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/LoopIterator.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/OptimizationRemarkEmitter.h" @@ -135,6 +136,152 @@ return true; } +static const SCEV * +getSCEVOnFirstIteration(Value *V, Loop *L, ScalarEvolution &SE, + DenseMap &FirstIterSCEV) { + // Fist, check in cache. + auto Existing = FirstIterSCEV.find(V); + if (Existing != FirstIterSCEV.end()) + return Existing->second; + const SCEV *S = nullptr; + // TODO: Once ScalarEvolution supports getValueOnNthIteration for anything + // else but AddRecs, it's a good use case for it. So far, just consider some + // simple cases, like arithmetic operations. + Value *LHS, *RHS; + using namespace PatternMatch; + if (match(V, m_Add(m_Value(LHS), m_Value(RHS)))) { + const SCEV *LHSS = getSCEVOnFirstIteration(LHS, L, SE, FirstIterSCEV); + const SCEV *RHSS = getSCEVOnFirstIteration(RHS, L, SE, FirstIterSCEV); + S = SE.getAddExpr(LHSS, RHSS); + } else if (match(V, m_Sub(m_Value(LHS), m_Value(RHS)))) { + const SCEV *LHSS = getSCEVOnFirstIteration(LHS, L, SE, FirstIterSCEV); + const SCEV *RHSS = getSCEVOnFirstIteration(RHS, L, SE, FirstIterSCEV); + S = SE.getMinusSCEV(LHSS, RHSS); + } else if (match(V, m_Mul(m_Value(LHS), m_Value(RHS)))) { + const SCEV *LHSS = getSCEVOnFirstIteration(LHS, L, SE, FirstIterSCEV); + const SCEV *RHSS = getSCEVOnFirstIteration(RHS, L, SE, FirstIterSCEV); + S = SE.getMulExpr(LHSS, RHSS); + } else + S = SE.getSCEV(V); + assert(S && "Case not handled?"); + FirstIterSCEV[V] = S; + return S; +} + +// Try to prove that one of conditions that dominates the latch must exit on 1st +// iteration. +static bool canProveExitOnFirstIteration(Loop *L, ScalarEvolution &SE, + LoopInfo &LI) { + BasicBlock *Latch = L->getLoopLatch(); + + if (!Latch) + return false; + + LoopBlocksRPO RPOT(L); + RPOT.perform(&LI); + + 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()); + + auto MarkLiveEdge = [&](BasicBlock *From, BasicBlock *To) { + assert(LiveBlocks.count(From) && "Must be live!"); + 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 live predecessor. Note that because we iterate + // in RPOT, we have already visited all its (non-latch) predecessors. + auto GetOnlyLivePred = [&](BasicBlock * BB)->BasicBlock * { + if (BB == Header) + return L->getLoopPredecessor(); + BasicBlock *OnlyPred = nullptr; + for (auto *Pred : predecessors(BB)) + if (LiveEdges.count({ Pred, BB })) { + // 2 live preds. + if (OnlyPred) + return nullptr; + OnlyPred = Pred; + } + + assert(OnlyPred && "No live predecessors?"); + return OnlyPred; + }; + DenseMap FirstIterSCEV; + + // 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. + for (auto *BB : RPOT) { + // 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 = GetOnlyLivePred(BB)) + for (auto &PN : BB->phis()) { + if (!SE.isSCEVable(PN.getType())) + continue; + auto *Incoming = PN.getIncomingValueForBlock(OnlyPred); + const SCEV *IncSCEV = + getSCEVOnFirstIteration(Incoming, L, SE, FirstIterSCEV); + FirstIterSCEV[&PN] = IncSCEV; + } + + using namespace PatternMatch; + ICmpInst::Predicate Pred; + Value *LHS, *RHS; + const BasicBlock *IfTrue, *IfFalse; + // TODO: Handle switches. + if (!match(BB->getTerminator(), + m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)), + m_BasicBlock(IfTrue), m_BasicBlock(IfFalse)))) { + MarkAllSuccessorsLive(BB); + continue; + } + + if (!SE.isSCEVable(LHS->getType())) { + MarkAllSuccessorsLive(BB); + continue; + } + + // Can we prove constant true or false for this condition? + const SCEV *LHSS = getSCEVOnFirstIteration(LHS, L, SE, FirstIterSCEV); + const SCEV *RHSS = getSCEVOnFirstIteration(RHS, L, SE, FirstIterSCEV); + if (SE.isKnownPredicateAt(Pred, LHSS, RHSS, BB->getTerminator())) + MarkLiveEdge(BB, BB->getTerminator()->getSuccessor(0)); + else if (SE.isKnownPredicateAt(ICmpInst::getInversePredicate(Pred), LHSS, + RHSS, BB->getTerminator())) + MarkLiveEdge(BB, BB->getTerminator()->getSuccessor(1)); + else + MarkAllSuccessorsLive(BB); + } + + // 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. @@ -148,7 +295,7 @@ return LoopDeletionResult::Unmodified; auto *BTC = SE.getBackedgeTakenCount(L); - if (!BTC->isZero()) + if (!BTC->isZero() && !canProveExitOnFirstIteration(L, SE, LI)) return LoopDeletionResult::Unmodified; breakLoopBackedge(L, DT, SE, LI, MSSA); Index: llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll =================================================================== --- llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll +++ llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll @@ -16,17 +16,19 @@ ; CHECK: loop.preheader: ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] +; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ] ; CHECK-NEXT: [[SUB:%.*]] = sub i32 [[LIMIT]], [[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]], [[LIMIT]] -; 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]] @@ -69,17 +71,19 @@ ; CHECK: loop.preheader: ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] +; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ] ; CHECK-NEXT: [[SUB:%.*]] = sub i32 [[LIMIT]], [[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]], [[LIMIT]] -; 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]] @@ -122,17 +126,19 @@ ; CHECK: loop.preheader: ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] +; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ] ; CHECK-NEXT: [[SUB:%.*]] = sub i32 [[LIMIT]], [[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]], [[LIMIT]] -; 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]] @@ -175,17 +181,19 @@ ; CHECK: loop.preheader: ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] +; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ] ; CHECK-NEXT: [[SUB:%.*]] = sub i32 [[LIMIT]], [[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]], [[LIMIT]] -; 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]] @@ -228,17 +236,19 @@ ; CHECK: loop.preheader: ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] +; CHECK-NEXT: [[SUM:%.*]] = phi i32 [ 0, [[LOOP_PREHEADER]] ] ; CHECK-NEXT: [[SUB:%.*]] = sub i32 [[LIMIT]], [[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]], [[LIMIT]] -; 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]] Index: llvm/test/Transforms/LoopDeletion/noop-loops-with-subloops.ll =================================================================== --- llvm/test/Transforms/LoopDeletion/noop-loops-with-subloops.ll +++ llvm/test/Transforms/LoopDeletion/noop-loops-with-subloops.ll @@ -50,7 +50,7 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] ; CHECK: outer.header: -; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_IV_NEXT:%.*]], [[OUTER_LATCH:%.*]] ] +; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ] ; CHECK-NEXT: br label [[INNER:%.*]] ; CHECK: inner: ; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ 0, [[OUTER_HEADER]] ], [ [[INNER_IV_NEXT:%.*]], [[INNER]] ] @@ -60,13 +60,15 @@ ; CHECK-NEXT: [[V_1:%.*]] = extractvalue [[PAIR_T]] [[P]], 1 ; CHECK-NEXT: [[INNER_EC:%.*]] = icmp ult i64 [[V_0]], [[V_1]] ; CHECK-NEXT: [[INNER_IV_NEXT]] = add i64 [[INNER_IV]], 1 -; CHECK-NEXT: br i1 [[INNER_EC]], label [[OUTER_LATCH]], label [[INNER]] +; CHECK-NEXT: br i1 [[INNER_EC]], label [[OUTER_LATCH:%.*]], label [[INNER]] ; CHECK: outer.latch: ; CHECK-NEXT: [[LCSSA:%.*]] = phi i64 [ [[V_1]], [[INNER]] ] ; CHECK-NEXT: [[OUTER_EC:%.*]] = icmp ult i64 [[OUTER_IV]], [[LCSSA]] -; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1 +; CHECK-NEXT: [[OUTER_IV_NEXT:%.*]] = add i64 [[OUTER_IV]], 1 ; CHECK-NEXT: call void @sideeffect() -; CHECK-NEXT: br i1 [[OUTER_EC]], label [[EXIT:%.*]], label [[OUTER_HEADER]] +; CHECK-NEXT: br i1 [[OUTER_EC]], label [[EXIT:%.*]], label [[OUTER_LATCH_OUTER_HEADER_CRIT_EDGE:%.*]] +; CHECK: outer.latch.outer.header_crit_edge: +; CHECK-NEXT: unreachable ; CHECK: exit: ; CHECK-NEXT: ret void ; @@ -105,7 +107,7 @@ ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] ; CHECK: outer.header: -; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_IV_NEXT:%.*]], [[OUTER_LATCH:%.*]] ] +; CHECK-NEXT: [[OUTER_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ] ; CHECK-NEXT: br label [[INNER:%.*]] ; CHECK: inner: ; CHECK-NEXT: [[INNER_IV:%.*]] = phi i64 [ 0, [[OUTER_HEADER]] ], [ [[INNER_IV_NEXT:%.*]], [[INNER]] ] @@ -116,12 +118,14 @@ ; CHECK-NEXT: [[INNER_EC:%.*]] = icmp ult i64 [[V_0]], [[V_1]] ; CHECK-NEXT: [[INNER_IV_NEXT]] = add i64 [[INNER_IV]], 1 ; CHECK-NEXT: call void @sideeffect() -; CHECK-NEXT: br i1 [[INNER_EC]], label [[OUTER_LATCH]], label [[INNER]] +; CHECK-NEXT: br i1 [[INNER_EC]], label [[OUTER_LATCH:%.*]], label [[INNER]] ; CHECK: outer.latch: ; CHECK-NEXT: [[LCSSA:%.*]] = phi i64 [ [[V_1]], [[INNER]] ] ; CHECK-NEXT: [[OUTER_EC:%.*]] = icmp ult i64 [[OUTER_IV]], [[LCSSA]] -; CHECK-NEXT: [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1 -; CHECK-NEXT: br i1 [[OUTER_EC]], label [[EXIT:%.*]], label [[OUTER_HEADER]] +; CHECK-NEXT: [[OUTER_IV_NEXT:%.*]] = add i64 [[OUTER_IV]], 1 +; CHECK-NEXT: br i1 [[OUTER_EC]], label [[EXIT:%.*]], label [[OUTER_LATCH_OUTER_HEADER_CRIT_EDGE:%.*]] +; CHECK: outer.latch.outer.header_crit_edge: +; CHECK-NEXT: unreachable ; CHECK: exit: ; CHECK-NEXT: ret void ; Index: llvm/test/Transforms/LoopDeletion/zero-btc.ll =================================================================== --- llvm/test/Transforms/LoopDeletion/zero-btc.ll +++ llvm/test/Transforms/LoopDeletion/zero-btc.ll @@ -161,14 +161,16 @@ ; 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 ;