Index: llvm/include/llvm/Analysis/ScalarEvolution.h =================================================================== --- llvm/include/llvm/Analysis/ScalarEvolution.h +++ llvm/include/llvm/Analysis/ScalarEvolution.h @@ -963,6 +963,11 @@ bool isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS); + /// Test whether the condition described by Pred, LHS, and RHS is true. + /// Use only simple non-recursive types of checks, such as range analysis etc. + bool isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS); + /// Check whether the condition described by Pred, LHS, and RHS is true or /// false. If we know it, return the evaluation of this condition. If neither /// is proved, return None. @@ -1852,11 +1857,6 @@ const SCEV *FoundLHS, const SCEV *FoundRHS, unsigned Depth = 0); - /// Test whether the condition described by Pred, LHS, and RHS is true. - /// Use only simple non-recursive types of checks, such as range analysis etc. - bool isKnownViaNonRecursiveReasoning(ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS); - /// Test whether the condition described by Pred, LHS, and RHS is true /// whenever the condition described by Pred, FoundLHS, and FoundRHS is /// true. Index: llvm/lib/Transforms/Scalar/LoopDeletion.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LoopDeletion.cpp +++ llvm/lib/Transforms/Scalar/LoopDeletion.cpp @@ -16,7 +16,9 @@ #include "llvm/Transforms/Scalar/LoopDeletion.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Analysis/CFG.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" @@ -33,6 +35,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, @@ -159,6 +166,180 @@ 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, DominatorTree &DT, + ScalarEvolution &SE, 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 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) { + 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 (!SE.isSCEVable(PN.getType())) + continue; + auto *Incoming = PN.getIncomingValueForBlock(OnlyPred); + if (DT.dominates(Incoming, BB->getTerminator())) { + const SCEV *IncSCEV = + getSCEVOnFirstIteration(Incoming, L, SE, FirstIterSCEV); + FirstIterSCEV[&PN] = IncSCEV; + } + } + + using namespace PatternMatch; + ICmpInst::Predicate Pred; + Value *LHS, *RHS; + BasicBlock *IfTrue, *IfFalse; + auto *Term = BB->getTerminator(); + // TODO: Handle switches. + if (!match(Term, 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); + // Only query for liveness of in-loop edge if another successor is also + // in-loop. + // TODO: isKnownPredicateAt is more powerful, but it's too compile time + // consuming. So we avoid using it here. + if (L->contains(IfFalse) && + SE.isKnownViaNonRecursiveReasoning(Pred, LHSS, RHSS)) + MarkLiveEdge(BB, IfTrue); + else if (L->contains(IfTrue) && + SE.isKnownViaNonRecursiveReasoning( + ICmpInst::getInversePredicate(Pred), LHSS, RHSS)) + MarkLiveEdge(BB, IfFalse); + 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. @@ -172,7 +353,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, 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 @@ -344,17 +344,19 @@ ; 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]] @@ -394,17 +396,19 @@ ; 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]] @@ -444,17 +448,19 @@ ; 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]] @@ -494,17 +500,19 @@ ; 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]] @@ -544,17 +552,19 @@ ; 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]] @@ -594,22 +604,24 @@ ; 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]] 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 ;