From 9f37ecf8fae9a6fc87a216bee0c83d465e8466b4 Mon Sep 17 00:00:00 2001 From: Max Kazantsev Date: Wed, 11 Jan 2023 11:12:11 +0700 Subject: [PATCH] [IndVars] Support AND/OR in optimizeLoopExitWithUnknownExitCount This patch allows optimizeLoopExitWithUnknownExitCount to deal with branches by conditions that are not immediately ICmp's, but aggregates of ICmp's joined by arithmetic or logical AND/OR. Each ICmp is optimized independently. Differential Revision: https://reviews.llvm.org/D139832 Reviewed By: nikic --- llvm/lib/Transforms/Scalar/IndVarSimplify.cpp | 78 ++++++++++++--- .../IndVarSimplify/eliminate-backedge.ll | 7 +- .../Transforms/IndVarSimplify/turn-to-invariant.ll | 110 ++++++++++----------- 3 files changed, 120 insertions(+), 75 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp index 2c5f226..af665d9 100644 --- a/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp +++ b/llvm/lib/Transforms/Scalar/IndVarSimplify.cpp @@ -1372,18 +1372,16 @@ createInvariantCond(const Loop *L, BasicBlock *ExitingBB, } static std::optional -createReplacement(Value *V, const Loop *L, BasicBlock *ExitingBB, - const SCEV *MaxIter, bool SkipLastIter, ScalarEvolution *SE, - SCEVExpander &Rewriter) { - ICmpInst::Predicate Pred; - Value *LHS, *RHS; - if (!match(V, m_ICmp(Pred, m_Value(LHS), m_Value(RHS)))) - return std::nullopt; +createReplacement(ICmpInst *ICmp, const Loop *L, BasicBlock *ExitingBB, + const SCEV *MaxIter, bool Inverted, bool SkipLastIter, + ScalarEvolution *SE, SCEVExpander &Rewriter) { + ICmpInst::Predicate Pred = ICmp->getPredicate(); + Value *LHS = ICmp->getOperand(0); + Value *RHS = ICmp->getOperand(1); // 'LHS pred RHS' should now mean that we stay in loop. auto *BI = cast(ExitingBB->getTerminator()); - BasicBlock *FalseSucc = BI->getSuccessor(1); - if (L->contains(FalseSucc)) + if (Inverted) Pred = CmpInst::getInversePredicate(Pred); const SCEV *LHSS = SE->getSCEVAtScope(LHS, L); @@ -1429,12 +1427,62 @@ static bool optimizeLoopExitWithUnknownExitCount( assert( (L->contains(BI->getSuccessor(0)) != L->contains(BI->getSuccessor(1))) && "Not a loop exit!"); - auto NewCond = createReplacement(BI->getCondition(), L, ExitingBB, MaxIter, - SkipLastIter, SE, Rewriter); - if (!NewCond) - return false; - replaceExitCond(BI, *NewCond, DeadInsts); - return true; + + // For branch that stays in loop by TRUE condition, go through AND. For branch + // that stays in loop by FALSE condition, go through OR. Both gives the + // similar logic: "stay in loop iff all conditions are true(false)". + bool Inverted = L->contains(BI->getSuccessor(1)); + SmallVector LeafConditions; + SmallVector Worklist; + SmallPtrSet Visited; + Value *OldCond = BI->getCondition(); + Visited.insert(OldCond); + Worklist.push_back(OldCond); + + auto GoThrough = [&](Value *V) { + Value *LHS = nullptr, *RHS = nullptr; + if (Inverted) { + if (!match(V, m_LogicalOr(m_Value(LHS), m_Value(RHS)))) + return false; + } else { + if (!match(V, m_LogicalAnd(m_Value(LHS), m_Value(RHS)))) + return false; + } + if (Visited.insert(LHS).second) + Worklist.push_back(LHS); + if (Visited.insert(RHS).second) + Worklist.push_back(RHS); + return true; + }; + + do { + Value *Curr = Worklist.pop_back_val(); + // Go through AND/OR conditions. Collect leaf ICMPs. We only care about + // those with one use, to avoid instruction duplication. + if (Curr->hasOneUse()) + if (!GoThrough(Curr)) + if (auto *ICmp = dyn_cast(Curr)) + LeafConditions.push_back(ICmp); + } while (!Worklist.empty()); + + bool Changed = false; + for (auto *OldCond : LeafConditions) + if (auto Replaced = + createReplacement(OldCond, L, ExitingBB, MaxIter, Inverted, + SkipLastIter, SE, Rewriter)) { + Changed = true; + auto *NewCond = *Replaced; + if (auto *NCI = dyn_cast(NewCond)) { + NCI->setName(OldCond->getName() + ".first_iter"); + NCI->moveBefore(cast(OldCond)); + } + LLVM_DEBUG(dbgs() << "Unknown exit count: Replacing " << *OldCond + << " with " << *NewCond << "\n"); + assert(OldCond->hasOneUse() && "Must be!"); + OldCond->replaceAllUsesWith(NewCond); + DeadInsts.push_back(OldCond); + } + return Changed; } bool IndVarSimplify::canonicalizeExitCondition(Loop *L) { diff --git a/llvm/test/Transforms/IndVarSimplify/eliminate-backedge.ll b/llvm/test/Transforms/IndVarSimplify/eliminate-backedge.ll index 5e3f1bd..c7b52cf 100644 --- a/llvm/test/Transforms/IndVarSimplify/eliminate-backedge.ll +++ b/llvm/test/Transforms/IndVarSimplify/eliminate-backedge.ll @@ -23,8 +23,7 @@ define i1 @kill_backedge_and_phis(ptr align 1 %lhs, ptr align 1 %rhs, i32 %len) ; CHECK-NEXT: br i1 %bar_ret, label %exit.loopexit, label %exiting_3 ; CHECK: exiting_3: ; CHECK-NEXT: %baz_ret = call i1 @baz() -; CHECK-NEXT: %continue = icmp ne i32 1, %len -; CHECK-NEXT: %or.cond = select i1 %baz_ret, i1 %continue, i1 false +; CHECK-NEXT: %or.cond = select i1 %baz_ret, i1 true, i1 false ; CHECK-NEXT: br i1 %or.cond, label %loop, label %exit.loopexit ; CHECK: exit.loopexit: ; CHECK-NEXT: %val.ph = phi i1 [ %baz_ret, %exiting_3 ], [ %bar_ret, %exiting_2 ], [ false, %exiting_1 ], [ %result, %loop ] @@ -89,7 +88,6 @@ define i1 @siblings(ptr align 1 %lhs, ptr align 1 %rhs, i32 %len) { ; CHECK-NEXT: %weird.iv.lcssa = phi i32 [ %weird.iv, %weird_loop ] ; CHECK-NEXT: br label %loop ; CHECK: loop: -; CHECK-NEXT: %iv.next = add i32 %weird.iv.lcssa, 1 ; CHECK-NEXT: %left_ptr = getelementptr inbounds i8, ptr %lhs, i32 %weird.iv.lcssa ; CHECK-NEXT: %right_ptr = getelementptr inbounds i8, ptr %rhs, i32 %weird.iv.lcssa ; CHECK-NEXT: %result = call i1 @foo(ptr %left_ptr, ptr %right_ptr) @@ -101,8 +99,7 @@ define i1 @siblings(ptr align 1 %lhs, ptr align 1 %rhs, i32 %len) { ; CHECK-NEXT: br i1 %bar_ret, label %exit.loopexit, label %exiting_3 ; CHECK: exiting_3: ; CHECK-NEXT: %baz_ret = call i1 @baz() -; CHECK-NEXT: %continue = icmp ne i32 %iv.next, %len -; CHECK-NEXT: %or.cond = select i1 %baz_ret, i1 %continue, i1 false +; CHECK-NEXT: %or.cond = select i1 %baz_ret, i1 true, i1 false ; CHECK-NEXT: br i1 %or.cond, label %loop, label %exit.loopexit ; CHECK: exit.loopexit: ; CHECK-NEXT: %val.ph = phi i1 [ %baz_ret, %exiting_3 ], [ %bar_ret, %exiting_2 ], [ false, %exiting_1 ], [ %result, %loop ] diff --git a/llvm/test/Transforms/IndVarSimplify/turn-to-invariant.ll b/llvm/test/Transforms/IndVarSimplify/turn-to-invariant.ll index 9bab1ca..d6ef997 100644 --- a/llvm/test/Transforms/IndVarSimplify/turn-to-invariant.ll +++ b/llvm/test/Transforms/IndVarSimplify/turn-to-invariant.ll @@ -14,8 +14,8 @@ define i32 @test_simple_case(i32 %start, i32 %len) { ; CHECK-NEXT: [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0 ; CHECK-NEXT: br i1 [[ZERO_CHECK]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]] ; CHECK: range_check_block: -; CHECK-NEXT: [[RANGE_CHECK3:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]] -; CHECK-NEXT: br i1 [[RANGE_CHECK3]], label [[BACKEDGE]], label [[FAILED_2:%.*]] +; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]] +; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAILED_2:%.*]] ; CHECK: backedge: ; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], -1 ; CHECK-NEXT: [[LOOP_COND:%.*]] = call i1 @cond() @@ -56,25 +56,25 @@ failed_2: ret i32 -2 } -; TODO: This example is equivalent to @test_simple_case, with only difference that -; both checks are littered with extra irrelevant conditions. We should be able -; to replace it with invariant despite this fact. -; https://alive2.llvm.org/ce/z/G4iW8c +; This example is equivalent to @test_simple_case, with only difference that +; both checks are littered with extra irrelevant conditions. We should be able +; to replace it with invariant despite this fact. +; https://alive2.llvm.org/ce/z/G4iW8c define i32 @test_litter_conditions(i32 %start, i32 %len) { ; CHECK-LABEL: @test_litter_conditions( ; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[START:%.*]], -1 ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0 ; CHECK-NEXT: [[FAKE_1:%.*]] = call i1 @cond() ; CHECK-NEXT: [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]] ; CHECK-NEXT: br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]] ; CHECK: range_check_block: -; CHECK-NEXT: [[IV_MINUS_1:%.*]] = add i32 [[IV]], -1 -; CHECK-NEXT: [[RANGE_CHECK:%.*]] = icmp ult i32 [[IV_MINUS_1]], [[LEN:%.*]] +; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]] ; CHECK-NEXT: [[FAKE_2:%.*]] = call i1 @cond() -; CHECK-NEXT: [[AND_2:%.*]] = and i1 [[RANGE_CHECK]], [[FAKE_2]] +; CHECK-NEXT: [[AND_2:%.*]] = and i1 [[RANGE_CHECK_FIRST_ITER]], [[FAKE_2]] ; CHECK-NEXT: br i1 [[AND_2]], label [[BACKEDGE]], label [[FAILED_2:%.*]] ; CHECK: backedge: ; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], -1 @@ -120,23 +120,23 @@ failed_2: ret i32 -2 } -; TODO: Same as test_litter_conditions, but swapped exit block branches -; and exit condition expressed by OR. Still optimizable. +; Same as test_litter_conditions, but swapped exit block branches +; and exit condition expressed by OR. Still optimizable. define i32 @test_litter_conditions_inverse(i32 %start, i32 %len) { ; CHECK-LABEL: @test_litter_conditions_inverse( ; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[START:%.*]], -1 ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0 ; CHECK-NEXT: [[FAKE_1:%.*]] = call i1 @cond() ; CHECK-NEXT: [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]] ; CHECK-NEXT: br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]] ; CHECK: range_check_block: -; CHECK-NEXT: [[IV_MINUS_1:%.*]] = add i32 [[IV]], -1 -; CHECK-NEXT: [[RANGE_CHECK_FAILED:%.*]] = icmp uge i32 [[IV_MINUS_1]], [[LEN:%.*]] +; CHECK-NEXT: [[RANGE_CHECK_FAILED_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]] ; CHECK-NEXT: [[FAKE_2:%.*]] = call i1 @cond() -; CHECK-NEXT: [[OR_2:%.*]] = or i1 [[RANGE_CHECK_FAILED]], [[FAKE_2]] +; CHECK-NEXT: [[OR_2:%.*]] = or i1 [[RANGE_CHECK_FAILED_FIRST_ITER]], [[FAKE_2]] ; CHECK-NEXT: br i1 [[OR_2]], label [[FAILED_2:%.*]], label [[BACKEDGE]] ; CHECK: backedge: ; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], -1 @@ -194,8 +194,8 @@ define i32 @test_litter_conditions_01(i32 %start, i32 %len) { ; CHECK-NEXT: [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]] ; CHECK-NEXT: br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]] ; CHECK: range_check_block: -; CHECK-NEXT: [[RANGE_CHECK3:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]] -; CHECK-NEXT: br i1 [[RANGE_CHECK3]], label [[BACKEDGE]], label [[FAILED_2:%.*]] +; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]] +; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAILED_2:%.*]] ; CHECK: backedge: ; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], -1 ; CHECK-NEXT: [[LOOP_COND:%.*]] = call i1 @cond() @@ -238,8 +238,8 @@ failed_2: ret i32 -2 } -; TODO: Same as test_litter_conditions_01, but swapped exit block branches -; and condition expressed by OR. Still optimizable. +; Same as test_litter_conditions_01, but swapped exit block branches +; and condition expressed by OR. Still optimizable. define i32 @test_litter_conditions_01_inverse(i32 %start, i32 %len) { ; CHECK-LABEL: @test_litter_conditions_01_inverse( ; CHECK-NEXT: entry: @@ -252,8 +252,8 @@ define i32 @test_litter_conditions_01_inverse(i32 %start, i32 %len) { ; CHECK-NEXT: [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]] ; CHECK-NEXT: br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]] ; CHECK: range_check_block: -; CHECK-NEXT: [[RANGE_CHECK_FAILED3:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]] -; CHECK-NEXT: br i1 [[RANGE_CHECK_FAILED3]], label [[FAILED_2:%.*]], label [[BACKEDGE]] +; CHECK-NEXT: [[RANGE_CHECK_FAILED_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]] +; CHECK-NEXT: br i1 [[RANGE_CHECK_FAILED_FIRST_ITER]], label [[FAILED_2:%.*]], label [[BACKEDGE]] ; CHECK: backedge: ; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], -1 ; CHECK-NEXT: [[LOOP_COND:%.*]] = call i1 @cond() @@ -300,16 +300,16 @@ failed_2: define i32 @test_litter_conditions_02(i32 %start, i32 %len) { ; CHECK-LABEL: @test_litter_conditions_02( ; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[START:%.*]], -1 ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0 ; CHECK-NEXT: br i1 [[ZERO_CHECK]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]] ; CHECK: range_check_block: -; CHECK-NEXT: [[IV_MINUS_1:%.*]] = add i32 [[IV]], -1 -; CHECK-NEXT: [[RANGE_CHECK:%.*]] = icmp ult i32 [[IV_MINUS_1]], [[LEN:%.*]] +; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]] ; CHECK-NEXT: [[FAKE_2:%.*]] = call i1 @cond() -; CHECK-NEXT: [[AND_2:%.*]] = and i1 [[RANGE_CHECK]], [[FAKE_2]] +; CHECK-NEXT: [[AND_2:%.*]] = and i1 [[RANGE_CHECK_FIRST_ITER]], [[FAKE_2]] ; CHECK-NEXT: br i1 [[AND_2]], label [[BACKEDGE]], label [[FAILED_2:%.*]] ; CHECK: backedge: ; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], -1 @@ -353,21 +353,21 @@ failed_2: ret i32 -2 } -; TODO: Same as test_litter_conditions_02, but swapped exit block branches, -; and condition is expressed as OR. Still optimizable. +; Same as test_litter_conditions_02, but swapped exit block branches, +; and condition is expressed as OR. Still optimizable. define i32 @test_litter_conditions_02_inverse(i32 %start, i32 %len) { ; CHECK-LABEL: @test_litter_conditions_02_inverse( ; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[START:%.*]], -1 ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0 ; CHECK-NEXT: br i1 [[ZERO_CHECK]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]] ; CHECK: range_check_block: -; CHECK-NEXT: [[IV_MINUS_1:%.*]] = add i32 [[IV]], -1 -; CHECK-NEXT: [[RANGE_CHECK_FAILED:%.*]] = icmp uge i32 [[IV_MINUS_1]], [[LEN:%.*]] +; CHECK-NEXT: [[RANGE_CHECK_FAILED_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]] ; CHECK-NEXT: [[FAKE_2:%.*]] = call i1 @cond() -; CHECK-NEXT: [[OR_2:%.*]] = or i1 [[RANGE_CHECK_FAILED]], [[FAKE_2]] +; CHECK-NEXT: [[OR_2:%.*]] = or i1 [[RANGE_CHECK_FAILED_FIRST_ITER]], [[FAKE_2]] ; CHECK-NEXT: br i1 [[OR_2]], label [[FAILED_2:%.*]], label [[BACKEDGE]] ; CHECK: backedge: ; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], -1 @@ -411,22 +411,22 @@ failed_2: ret i32 -2 } -; TODO: Same as @test_litter_conditions, but all conditions are computed in -; header block. Make sure we infer fact from the right context. -; https://alive2.llvm.org/ce/z/JiD-Pw +; Same as @test_litter_conditions, but all conditions are computed in +; header block. Make sure we infer fact from the right context. +; https://alive2.llvm.org/ce/z/JiD-Pw define i32 @test_litter_conditions_bad_context(i32 %start, i32 %len) { ; CHECK-LABEL: @test_litter_conditions_bad_context( ; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[START:%.*]], -1 ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0 ; CHECK-NEXT: [[FAKE_1:%.*]] = call i1 @cond() ; CHECK-NEXT: [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]] -; CHECK-NEXT: [[IV_MINUS_1:%.*]] = add i32 [[IV]], -1 -; CHECK-NEXT: [[RANGE_CHECK:%.*]] = icmp ult i32 [[IV_MINUS_1]], [[LEN:%.*]] +; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]] ; CHECK-NEXT: [[FAKE_2:%.*]] = call i1 @cond() -; CHECK-NEXT: [[AND_2:%.*]] = and i1 [[RANGE_CHECK]], [[FAKE_2]] +; CHECK-NEXT: [[AND_2:%.*]] = and i1 [[RANGE_CHECK_FIRST_ITER]], [[FAKE_2]] ; CHECK-NEXT: br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]] ; CHECK: range_check_block: ; CHECK-NEXT: br i1 [[AND_2]], label [[BACKEDGE]], label [[FAILED_2:%.*]] @@ -474,21 +474,21 @@ failed_2: ret i32 -2 } -; TODO: Same as @test_litter_conditions_bad_context, but swapped exit block branches, -; and conditions expressed as OR. Still optimizable. +; Same as @test_litter_conditions_bad_context, but swapped exit block branches, +; and conditions expressed as OR. Still optimizable. define i32 @test_litter_conditions_bad_context_inverse(i32 %start, i32 %len) { ; CHECK-LABEL: @test_litter_conditions_bad_context_inverse( ; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[START:%.*]], -1 ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0 ; CHECK-NEXT: [[FAKE_1:%.*]] = call i1 @cond() ; CHECK-NEXT: [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]] -; CHECK-NEXT: [[IV_MINUS_1:%.*]] = add i32 [[IV]], -1 -; CHECK-NEXT: [[RANGE_CHECK_FAILED:%.*]] = icmp uge i32 [[IV_MINUS_1]], [[LEN:%.*]] +; CHECK-NEXT: [[RANGE_CHECK_FAILED_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]] ; CHECK-NEXT: [[FAKE_2:%.*]] = call i1 @cond() -; CHECK-NEXT: [[OR_2:%.*]] = or i1 [[RANGE_CHECK_FAILED]], [[FAKE_2]] +; CHECK-NEXT: [[OR_2:%.*]] = or i1 [[RANGE_CHECK_FAILED_FIRST_ITER]], [[FAKE_2]] ; CHECK-NEXT: br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]] ; CHECK: range_check_block: ; CHECK-NEXT: br i1 [[OR_2]], label [[FAILED_2:%.*]], label [[BACKEDGE]] @@ -630,22 +630,22 @@ failed: ret i32 -3 } -; TODO: Same as test_litter_conditions, but with logical AND. +; Same as test_litter_conditions, but with logical AND. define i32 @test_litter_conditions_logical_and(i32 %start, i32 %len) { ; CHECK-LABEL: @test_litter_conditions_logical_and( ; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[START:%.*]], -1 ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0 ; CHECK-NEXT: [[FAKE_1:%.*]] = call i1 @cond() ; CHECK-NEXT: [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]] ; CHECK-NEXT: br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]] ; CHECK: range_check_block: -; CHECK-NEXT: [[IV_MINUS_1:%.*]] = add i32 [[IV]], -1 -; CHECK-NEXT: [[RANGE_CHECK:%.*]] = icmp ult i32 [[IV_MINUS_1]], [[LEN:%.*]] +; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN:%.*]] ; CHECK-NEXT: [[FAKE_2:%.*]] = call i1 @cond() -; CHECK-NEXT: [[AND_2:%.*]] = select i1 [[RANGE_CHECK]], i1 [[FAKE_2]], i1 false +; CHECK-NEXT: [[AND_2:%.*]] = select i1 [[RANGE_CHECK_FIRST_ITER]], i1 [[FAKE_2]], i1 false ; CHECK-NEXT: br i1 [[AND_2]], label [[BACKEDGE]], label [[FAILED_2:%.*]] ; CHECK: backedge: ; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], -1 @@ -691,22 +691,22 @@ failed_2: ret i32 -2 } -; TODO: Same as test_litter_conditions_inverse, but with logical OR. +; Same as test_litter_conditions_inverse, but with logical OR. define i32 @test_litter_conditions_inverse_logical_or(i32 %start, i32 %len) { ; CHECK-LABEL: @test_litter_conditions_inverse_logical_or( ; CHECK-NEXT: entry: +; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[START:%.*]], -1 ; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK: loop: -; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] +; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[ZERO_CHECK:%.*]] = icmp ne i32 [[IV]], 0 ; CHECK-NEXT: [[FAKE_1:%.*]] = call i1 @cond() ; CHECK-NEXT: [[AND_1:%.*]] = and i1 [[ZERO_CHECK]], [[FAKE_1]] ; CHECK-NEXT: br i1 [[AND_1]], label [[RANGE_CHECK_BLOCK:%.*]], label [[FAILED_1:%.*]] ; CHECK: range_check_block: -; CHECK-NEXT: [[IV_MINUS_1:%.*]] = add i32 [[IV]], -1 -; CHECK-NEXT: [[RANGE_CHECK_FAILED:%.*]] = icmp uge i32 [[IV_MINUS_1]], [[LEN:%.*]] +; CHECK-NEXT: [[RANGE_CHECK_FAILED_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN:%.*]] ; CHECK-NEXT: [[FAKE_2:%.*]] = call i1 @cond() -; CHECK-NEXT: [[OR_2:%.*]] = select i1 [[RANGE_CHECK_FAILED]], i1 true, i1 [[FAKE_2]] +; CHECK-NEXT: [[OR_2:%.*]] = select i1 [[RANGE_CHECK_FAILED_FIRST_ITER]], i1 true, i1 [[FAKE_2]] ; CHECK-NEXT: br i1 [[OR_2]], label [[FAILED_2:%.*]], label [[BACKEDGE]] ; CHECK: backedge: ; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], -1 -- 2.7.4