diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -7264,62 +7264,43 @@ if (isSCEVExprNeverPoison(I)) return true; - // For an add recurrence specifically, we assume that infinite loops without - // side effects are undefined behavior, and then reason as follows: + // If the loop only has one exit, then we know that, if the loop is entered, + // any instruction dominating that exit will be executed. If any such + // instruction would result in UB, the addrec cannot be poison. // - // If the add recurrence is poison in any iteration, it is poison on all - // future iterations (since incrementing poison yields poison). If the result - // of the add recurrence is fed into the loop latch condition and the loop - // does not contain any throws or exiting blocks other than the latch, we now - // have the ability to "choose" whether the backedge is taken or not (by - // choosing a sufficiently evil value for the poison feeding into the branch) - // for every iteration including and after the one in which \p I first became - // poison. There are two possibilities (let's call the iteration in which \p - // I first became poison as K): - // - // 1. In the set of iterations including and after K, the loop body executes - // no side effects. In this case executing the backege an infinte number - // of times will yield undefined behavior. - // - // 2. In the set of iterations including and after K, the loop body executes - // at least one side effect. In this case, that specific instance of side - // effect is control dependent on poison, which also yields undefined - // behavior. + // This is basically the same reasoning as in isSCEVExprNeverPoison(), but + // also handles uses outside the loop header (they just need to dominate the + // single exit). auto *ExitingBB = L->getExitingBlock(); - auto *LatchBB = L->getLoopLatch(); - if (!ExitingBB || !LatchBB || ExitingBB != LatchBB) + if (!ExitingBB || !loopHasNoAbnormalExits(L)) return false; - SmallPtrSet Pushed; - SmallVector PoisonStack; + SmallPtrSet KnownPoison; + SmallVector Worklist; // We start by assuming \c I, the post-inc add recurrence, is poison. Only // things that are known to be poison under that assumption go on the - // PoisonStack. - Pushed.insert(I); - PoisonStack.push_back(I); + // Worklist. + KnownPoison.insert(I); + Worklist.push_back(I); - bool LatchControlDependentOnPoison = false; - while (!PoisonStack.empty() && !LatchControlDependentOnPoison) { - const Instruction *Poison = PoisonStack.pop_back_val(); + while (!Worklist.empty()) { + const Instruction *Poison = Worklist.pop_back_val(); for (const Use &U : Poison->uses()) { - const User *PoisonUser = U.getUser(); - if (propagatesPoison(U)) { - if (Pushed.insert(cast(PoisonUser)).second) - PoisonStack.push_back(cast(PoisonUser)); - } else if (auto *BI = dyn_cast(PoisonUser)) { - assert(BI->isConditional() && "Only possibility!"); - if (BI->getParent() == LatchBB) { - LatchControlDependentOnPoison = true; - break; - } - } + const Instruction *PoisonUser = cast(U.getUser()); + if (mustTriggerUB(PoisonUser, KnownPoison) && + DT.dominates(PoisonUser->getParent(), ExitingBB)) + return true; + + if (propagatesPoison(U) && L->contains(PoisonUser)) + if (KnownPoison.insert(PoisonUser).second) + Worklist.push_back(PoisonUser); } } - return LatchControlDependentOnPoison && loopHasNoAbnormalExits(L); + return false; } ScalarEvolution::LoopProperties diff --git a/llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll b/llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll --- a/llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll +++ b/llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll @@ -665,9 +665,9 @@ ; CHECK-NEXT: %nexti = add nsw i32 %i, 1 ; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %nexti2 = add nsw i32 %i2, 1 -; CHECK-NEXT: --> {(1 + %offset),+,1}<%loop> U: full-set S: full-set Exits: (%offset + %numIterations) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {(1 + %offset),+,1}<%loop> U: full-set S: full-set Exits: (%offset + %numIterations) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %ptr = getelementptr inbounds float, ptr %input, i32 %nexti2 -; CHECK-NEXT: --> ((4 * (sext i32 {(1 + %offset),+,1}<%loop> to i64)) + %input) U: full-set S: full-set Exits: ((4 * (sext i32 (%offset + %numIterations) to i64)) + %input) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {((4 * (sext i32 (1 + %offset) to i64)) + %input),+,4}<%loop> U: full-set S: full-set Exits: ((4 * (zext i32 (-1 + %numIterations) to i64)) + (4 * (sext i32 (1 + %offset) to i64)) + %input) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test-add-not-header6 ; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + %numIterations) ; CHECK-NEXT: Loop %loop: constant max backedge-taken count is -1 @@ -702,11 +702,11 @@ ; CHECK-NEXT: %i2 = phi i32 [ %nexti2, %loop.latch ], [ %offset, %entry ] ; CHECK-NEXT: --> {%offset,+,1}<%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %nexti = add nsw i32 %i, 1 -; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,0) S: [1,0) Exits: %numIterations LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %nexti2 = add nsw i32 %i2, 1 -; CHECK-NEXT: --> {(1 + %offset),+,1}<%loop> U: full-set S: full-set Exits: (%offset + %numIterations) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {(1 + %offset),+,1}<%loop> U: full-set S: full-set Exits: (%offset + %numIterations) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %ptr = getelementptr inbounds float, ptr %input, i32 %nexti2 -; CHECK-NEXT: --> ((4 * (sext i32 {(1 + %offset),+,1}<%loop> to i64)) + %input) U: full-set S: full-set Exits: ((4 * (sext i32 (%offset + %numIterations) to i64)) + %input) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {((4 * (sext i32 (1 + %offset) to i64)) + %input),+,4}<%loop> U: full-set S: full-set Exits: ((4 * (zext i32 (-1 + %numIterations) to i64)) + (4 * (sext i32 (1 + %offset) to i64)) + %input) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: Determining loop execution counts for: @test-add-not-header7 ; CHECK-NEXT: Loop %loop: backedge-taken count is (-1 + %numIterations) ; CHECK-NEXT: Loop %loop: constant max backedge-taken count is -1 @@ -743,7 +743,7 @@ ; CHECK-NEXT: %i2 = phi i32 [ %nexti2, %loop.latch ], [ %offset, %entry ] ; CHECK-NEXT: --> {%offset,+,1}<%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %nexti = add nsw i32 %i, 1 -; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,0) S: [1,0) Exits: %numIterations LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %nexti2 = add nsw i32 %i2, 1 ; CHECK-NEXT: --> {(1 + %offset),+,1}<%loop> U: full-set S: full-set Exits: (%offset + %numIterations) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %ptr = getelementptr inbounds float, ptr %input, i32 %nexti2