Index: llvm/lib/Transforms/Scalar/LoopDeletion.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LoopDeletion.cpp +++ llvm/lib/Transforms/Scalar/LoopDeletion.cpp @@ -135,6 +135,187 @@ return true; } +// Forward declaration. +static const SCEV * +getSCEVOnFirstIteration(Value *V, Loop *L, const DominatorTree &DT, + ScalarEvolution &SE, const LoopInfo &LI, + DenseMap &FirstIterSCEV); + +static Value *evaluateMergePhiOnFirstIteration( + PHINode *PN, Loop *L, const DominatorTree &DT, ScalarEvolution &SE, + const LoopInfo &LI, DenseMap &FirstIterSCEV) { + const BasicBlock *BB = PN->getParent(); + // For header phis, the value on 1st iteration is known. + if (BB == L->getHeader()) + return PN->getIncomingValueForBlock(L->getLoopPredecessor()); + // Skip phis from other loops. + if (LI.getLoopFor(BB) != L) + return PN; + // If we have something like: + // if (cond) + // / \ + // ... ... + // \ / + // phi [v1] [v2] + // And somehow know `cond` on the 1st iteration, then we also can evaluate + // phi on the 1st iteration. + if (PN->getNumIncomingValues() != 2) + return PN; + + const BasicBlock *In1 = PN->getIncomingBlock(0); + const BasicBlock *In2 = PN->getIncomingBlock(1); + if (In1 == In2) + return PN; + BasicBlock *IDom = DT.getNode(BB)->getIDom()->getBlock(); + using namespace PatternMatch; + ICmpInst::Predicate Pred; + Value *LHS, *RHS; + const BasicBlock *IfTrue, *IfFalse; + if (!match(IDom->getTerminator(), + m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)), + m_BasicBlock(IfTrue), m_BasicBlock(IfFalse)))) + return PN; + if (IfTrue == IfFalse) + return PN; + + if (!SE.isSCEVable(LHS->getType())) + return PN; + + BasicBlockEdge OutEdgeIfTrue(IDom, IfTrue); + BasicBlockEdge OutEdgeIfFalse(IDom, IfFalse); + BasicBlockEdge InEdge1(In1, BB); + BasicBlockEdge InEdge2(In2, BB); + if (DT.dominates(OutEdgeIfTrue, InEdge2) && + DT.dominates(OutEdgeIfFalse, InEdge1)) { + std::swap(InEdge1, InEdge2); + std::swap(In1, In2); + } + + if (!DT.dominates(OutEdgeIfTrue, InEdge1) || + !DT.dominates(OutEdgeIfFalse, InEdge2)) + return PN; + // Now we know that branching from IDom to IfTrue means coming to PN from In1, + // and branching from IDom to IfFalse means coming to PN from In2. If we can + // evaluate the condition on the 1st iteration, we can also evaluate PN. + const SCEV *LHSS = getSCEVOnFirstIteration(LHS, L, DT, SE, LI, FirstIterSCEV); + const SCEV *RHSS = getSCEVOnFirstIteration(RHS, L, DT, SE, LI, FirstIterSCEV); + + // Take Phi's input if it's available. Do not take values that are defined in + // conditional blocks to avoid comparisons of values that don't exist at the + // same time. + if (SE.isKnownPredicateAt(Pred, LHSS, RHSS, IDom->getTerminator())) { + auto *Incoming = PN->getIncomingValueForBlock(In1); + if (auto *IncInsn = dyn_cast(Incoming)) + if (!DT.dominates(IncInsn, IDom->getTerminator())) + return PN; + return Incoming; + } + if (SE.isKnownPredicateAt(ICmpInst::getInversePredicate(Pred), LHSS, RHSS, + IDom->getTerminator())) { + auto *Incoming = PN->getIncomingValueForBlock(In2); + if (auto *IncInsn = dyn_cast(Incoming)) + if (!DT.dominates(IncInsn, IDom->getTerminator())) + return PN; + return Incoming; + } + // We could prove nothing, PN is always a fallback. + return PN; +} + +static const SCEV * +getSCEVOnFirstIteration(Value *V, Loop *L, const DominatorTree &DT, + ScalarEvolution &SE, const LoopInfo &LI, + 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 (auto *PN = dyn_cast(V)) { + auto *Val = + evaluateMergePhiOnFirstIteration(PN, L, DT, SE, LI, FirstIterSCEV); + // If we could prove that this Phi is equivalent to one of its inputs on the + // first iteration, take its SCEV. Otherwise, take the conservative + // approach. + if (Val != PN) + S = getSCEVOnFirstIteration(Val, L, DT, SE, LI, FirstIterSCEV); + else + S = SE.getSCEV(Val); + } else if (match(V, m_Add(m_Value(LHS), m_Value(RHS)))) { + const SCEV *LHSS = + getSCEVOnFirstIteration(LHS, L, DT, SE, LI, FirstIterSCEV); + const SCEV *RHSS = + getSCEVOnFirstIteration(RHS, L, DT, SE, LI, FirstIterSCEV); + S = SE.getAddExpr(LHSS, RHSS); + } else if (match(V, m_Sub(m_Value(LHS), m_Value(RHS)))) { + const SCEV *LHSS = + getSCEVOnFirstIteration(LHS, L, DT, SE, LI, FirstIterSCEV); + const SCEV *RHSS = + getSCEVOnFirstIteration(RHS, L, DT, SE, LI, FirstIterSCEV); + S = SE.getMinusSCEV(LHSS, RHSS); + } else if (match(V, m_Mul(m_Value(LHS), m_Value(RHS)))) { + const SCEV *LHSS = + getSCEVOnFirstIteration(LHS, L, DT, SE, LI, FirstIterSCEV); + const SCEV *RHSS = + getSCEVOnFirstIteration(RHS, L, DT, SE, LI, 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, const DominatorTree &DT, + ScalarEvolution &SE, + const LoopInfo &LI) { + BasicBlock *Latch = L->getLoopLatch(); + if (!Latch || !DT.isReachableFromEntry(Latch)) + return false; + + BasicBlock *Predecessor = L->getLoopPredecessor(); + DenseMap FirstIterSCEV; + + for (auto *Node = DT.getNode(Latch); Node->getBlock() != Predecessor; + Node = Node->getIDom()) { + const auto *BB = Node->getBlock(); + // Skip inner loops. + if (LI.getLoopFor(BB) != L) + continue; + using namespace PatternMatch; + ICmpInst::Predicate Pred; + Value *LHS, *RHS; + const BasicBlock *IfTrue, *IfFalse; + if (!match(BB->getTerminator(), + m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)), + m_BasicBlock(IfTrue), m_BasicBlock(IfFalse)))) + continue; + if (L->contains(IfTrue) && L->contains(IfFalse)) + continue; + if (!SE.isSCEVable(LHS->getType())) + continue; + if (L->contains(IfTrue)) + Pred = ICmpInst::getInversePredicate(Pred); + // Now, if condition (Pred, LHS, RHS) is true on the 1st iteration, the loop + // will not have the 2nd iteration. + const SCEV *LHSS = + getSCEVOnFirstIteration(LHS, L, DT, SE, LI, FirstIterSCEV); + const SCEV *RHSS = + getSCEVOnFirstIteration(RHS, L, DT, SE, LI, FirstIterSCEV); + if (SE.isKnownPredicateAt(Pred, LHSS, RHSS, BB->getTerminator())) + return true; + } + + return false; +} + /// 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 +329,7 @@ return LoopDeletionResult::Unmodified; auto *BTC = SE.getBackedgeTakenCount(L); - if (!BTC->isZero()) + 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 @@ -7,7 +7,6 @@ ; and therefore prove that %sum.next = %sum + %sub = %sum + %limit - %sum = %limit, ; and predicate is false. -; TODO: We can break the backedge here. define i32 @test_ne(i32 %limit) { ; CHECK-LABEL: @test_ne( ; CHECK-NEXT: entry: @@ -16,17 +15,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]] @@ -60,7 +61,6 @@ unreachable } -; TODO: We can break the backedge here. define i32 @test_slt(i32 %limit) { ; CHECK-LABEL: @test_slt( ; CHECK-NEXT: entry: @@ -69,17 +69,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]] @@ -113,7 +115,6 @@ unreachable } -; TODO: We can break the backedge here. define i32 @test_ult(i32 %limit) { ; CHECK-LABEL: @test_ult( ; CHECK-NEXT: entry: @@ -122,17 +123,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]] @@ -166,7 +169,6 @@ unreachable } -; TODO: We can break the backedge here. define i32 @test_sgt(i32 %limit) { ; CHECK-LABEL: @test_sgt( ; CHECK-NEXT: entry: @@ -175,17 +177,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]] @@ -219,7 +223,6 @@ unreachable } -; TODO: We can break the backedge here. define i32 @test_ugt(i32 %limit) { ; CHECK-LABEL: @test_ugt( ; CHECK-NEXT: entry: @@ -228,17 +231,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/unreachable-loops.ll =================================================================== --- llvm/test/Transforms/LoopDeletion/unreachable-loops.ll +++ llvm/test/Transforms/LoopDeletion/unreachable-loops.ll @@ -317,7 +317,23 @@ define void @test9(i64 %n) { ; CHECK-LABEL: @test9( ; CHECK-NEXT: entry: -; CHECK-NEXT: br label [[EXIT:%.*]] +; CHECK-NEXT: br label [[L1:%.*]] +; CHECK: L1.loopexit: +; CHECK-NEXT: br label [[L1_LOOPEXIT_SPLIT:%.*]] +; CHECK: L1.loopexit.split: +; CHECK-NEXT: unreachable +; CHECK: L1: +; CHECK-NEXT: br i1 true, label [[EXIT:%.*]], label [[L2_PREHEADER:%.*]] +; CHECK: L2.preheader: +; CHECK-NEXT: br label [[L3_PREHEADER:%.*]] +; CHECK: L3.preheader: +; CHECK-NEXT: [[Y_L2_LCSSA:%.*]] = phi i64 [ undef, [[L2_PREHEADER]] ] +; CHECK-NEXT: br label [[L3:%.*]] +; CHECK: L3: +; CHECK-NEXT: [[COND2:%.*]] = icmp slt i64 [[Y_L2_LCSSA]], [[N:%.*]] +; 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 ; @@ -350,7 +366,36 @@ define void @test10(i64 %n) { ; CHECK-LABEL: @test10( ; CHECK-NEXT: entry: -; CHECK-NEXT: br label [[EXIT:%.*]] +; CHECK-NEXT: br label [[L1:%.*]] +; CHECK: L1.loopexit: +; CHECK-NEXT: br label [[L1_LOOPEXIT_SPLIT:%.*]] +; CHECK: L1.loopexit.split: +; CHECK-NEXT: unreachable +; CHECK: L1: +; CHECK-NEXT: br i1 true, label [[EXIT:%.*]], label [[L2_PREHEADER:%.*]] +; CHECK: L2.preheader: +; CHECK-NEXT: br label [[L2:%.*]] +; CHECK: L2.loopexit: +; CHECK-NEXT: br label [[L2_LOOPEXIT_SPLIT:%.*]] +; CHECK: L2.loopexit.split: +; CHECK-NEXT: unreachable +; CHECK: L2: +; CHECK-NEXT: [[X:%.*]] = phi i64 [ 0, [[L2_PREHEADER]] ] +; CHECK-NEXT: [[X_NEXT:%.*]] = add i64 [[X]], 1 +; CHECK-NEXT: [[Y_L2:%.*]] = call i64 @foo(i64 [[X_NEXT]]) +; CHECK-NEXT: [[COND:%.*]] = icmp slt i64 [[X_NEXT]], [[N:%.*]] +; CHECK-NEXT: br i1 [[COND]], label [[L1_LOOPEXIT:%.*]], label [[L3_PREHEADER:%.*]] +; CHECK: L3.preheader: +; CHECK-NEXT: [[Y_L2_LCSSA:%.*]] = phi i64 [ [[Y_L2]], [[L2]] ] +; CHECK-NEXT: br label [[L3:%.*]] +; CHECK: L3: +; CHECK-NEXT: [[Y_L3:%.*]] = phi i64 [ [[Y_L2_LCSSA]], [[L3_PREHEADER]] ] +; CHECK-NEXT: [[Y_L3_NEXT:%.*]] = add i64 [[Y_L3]], 1 +; CHECK-NEXT: [[DUMMY:%.*]] = call i64 @foo(i64 [[Y_L3_NEXT]]) +; CHECK-NEXT: [[COND2:%.*]] = icmp slt i64 [[Y_L3]], [[N]] +; CHECK-NEXT: br i1 [[COND2]], label [[L3_L3_CRIT_EDGE:%.*]], label [[L2_LOOPEXIT:%.*]] +; CHECK: L3.L3_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 @@ -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 ;