diff options
| -rw-r--r-- | llvm/lib/Analysis/ScalarEvolution.cpp | 75 | ||||
| -rw-r--r-- | llvm/test/Analysis/ScalarEvolution/exact_iter_count.ll | 34 | ||||
| -rw-r--r-- | llvm/test/Transforms/LoopSimplify/preserve-scev.ll | 2 |
3 files changed, 59 insertions, 52 deletions
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 87b0141c850..d6fee9be570 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -6890,12 +6890,63 @@ ScalarEvolution::computeBackedgeTakenCount(const Loop *L, ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimit(const Loop *L, BasicBlock *ExitingBlock, bool AllowPredicates) { - assert(L->contains(ExitingBlock) && "Exit count for non-loop block?"); - // If our exiting block does not dominate the latch, then its connection with - // loop's exit limit may be far from trivial. - const BasicBlock *Latch = L->getLoopLatch(); - if (!Latch || !DT.dominates(ExitingBlock, Latch)) - return getCouldNotCompute(); + // Okay, we've chosen an exiting block. See what condition causes us to exit + // at this block and remember the exit block and whether all other targets + // lead to the loop header. + bool MustExecuteLoopHeader = true; + BasicBlock *Exit = nullptr; + for (auto *SBB : successors(ExitingBlock)) + if (!L->contains(SBB)) { + if (Exit) // Multiple exit successors. + return getCouldNotCompute(); + Exit = SBB; + } else if (SBB != L->getHeader()) { + MustExecuteLoopHeader = false; + } + + // At this point, we know we have a conditional branch that determines whether + // the loop is exited. However, we don't know if the branch is executed each + // time through the loop. If not, then the execution count of the branch will + // not be equal to the trip count of the loop. + // + // Currently we check for this by checking to see if the Exit branch goes to + // the loop header. If so, we know it will always execute the same number of + // times as the loop. We also handle the case where the exit block *is* the + // loop header. This is common for un-rotated loops. + // + // If both of those tests fail, walk up the unique predecessor chain to the + // header, stopping if there is an edge that doesn't exit the loop. If the + // header is reached, the execution count of the branch will be equal to the + // trip count of the loop. + // + // More extensive analysis could be done to handle more cases here. + // + if (!MustExecuteLoopHeader && ExitingBlock != L->getHeader()) { + // The simple checks failed, try climbing the unique predecessor chain + // up to the header. + bool Ok = false; + for (BasicBlock *BB = ExitingBlock; BB; ) { + BasicBlock *Pred = BB->getUniquePredecessor(); + if (!Pred) + return getCouldNotCompute(); + TerminatorInst *PredTerm = Pred->getTerminator(); + for (const BasicBlock *PredSucc : PredTerm->successors()) { + if (PredSucc == BB) + continue; + // If the predecessor has a successor that isn't BB and isn't + // outside the loop, assume the worst. + if (L->contains(PredSucc)) + return getCouldNotCompute(); + } + if (Pred == L->getHeader()) { + Ok = true; + break; + } + BB = Pred; + } + if (!Ok) + return getCouldNotCompute(); + } bool IsOnlyExit = (L->getExitingBlock() != nullptr); TerminatorInst *Term = ExitingBlock->getTerminator(); @@ -6910,19 +6961,9 @@ ScalarEvolution::computeExitLimit(const Loop *L, BasicBlock *ExitingBlock, /*ControlsExit=*/IsOnlyExit, AllowPredicates); } - if (SwitchInst *SI = dyn_cast<SwitchInst>(Term)) { - // For switch, make sure that there is a single exit from the loop. - BasicBlock *Exit = nullptr; - for (auto *SBB : successors(ExitingBlock)) - if (!L->contains(SBB)) { - if (Exit) // Multiple exit successors. - return getCouldNotCompute(); - Exit = SBB; - } - assert(Exit && "Exiting block must have at least one exit"); + if (SwitchInst *SI = dyn_cast<SwitchInst>(Term)) return computeExitLimitFromSingleExitSwitch(L, SI, Exit, /*ControlsExit=*/IsOnlyExit); - } return getCouldNotCompute(); } diff --git a/llvm/test/Analysis/ScalarEvolution/exact_iter_count.ll b/llvm/test/Analysis/ScalarEvolution/exact_iter_count.ll index 443da146e77..ba0bc1f4cf3 100644 --- a/llvm/test/Analysis/ScalarEvolution/exact_iter_count.ll +++ b/llvm/test/Analysis/ScalarEvolution/exact_iter_count.ll @@ -25,37 +25,3 @@ exit: side.exit: ret void } - -define void @test_02(i1 %c) { - -; CHECK-LABEL: Determining loop execution counts for: @test_02 -; CHECK-NEXT: Loop %loop: <multiple exits> backedge-taken count is 50 - -entry: - br label %loop - -loop: - %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ] - br i1 %c, label %if.true, label %if.false - -if.true: - br label %merge - -if.false: - br label %merge - -merge: - %side.cond = icmp slt i32 %iv, 50 - br i1 %side.cond, label %backedge, label %side.exit - -backedge: - %iv.next = add i32 %iv, 1 - %loop.cond = icmp slt i32 %iv, 100 - br i1 %loop.cond, label %loop, label %exit - -exit: - ret void - -side.exit: - ret void -} diff --git a/llvm/test/Transforms/LoopSimplify/preserve-scev.ll b/llvm/test/Transforms/LoopSimplify/preserve-scev.ll index 07486ef2468..2def885353b 100644 --- a/llvm/test/Transforms/LoopSimplify/preserve-scev.ll +++ b/llvm/test/Transforms/LoopSimplify/preserve-scev.ll @@ -95,7 +95,7 @@ declare void @foo() nounwind ; CHECK: Loop %while.cond191: max backedge-taken count is 0 ; CHECK: Loop %while.cond191: Predicated backedge-taken count is 0 ; CHECK: Loop %while.cond191.outer: <multiple exits> Unpredictable backedge-taken count. -; CHECK: Loop %while.cond191.outer: max backedge-taken count is false +; CHECK: Loop %while.cond191.outer: Unpredictable max backedge-taken count. ; CHECK: Loop %while.cond191.outer: Unpredictable predicated backedge-taken count. define void @mergeExit(i32 %MapAttrCount) nounwind uwtable ssp { entry: |
