Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -4015,6 +4015,61 @@ } // namespace +/// Return true if V is poison given that AssumedPoison is already poison. +static bool impliesPoison(const SCEV *AssumedPoison, const SCEV *S) { + // The only way poison may be introduced in a SCEV expression is from a + // poison SCEVUnknown. Notably, nowrap flags in SCEV nodes can *not* + // introduce poison -- they encode guaranteed, non-speculated knowledge. + // + // Additionally, all SCEV nodes propagate poison from inputs to outputs, + // with the notable exception of umin_seq, where only poison from the first + // operand is (unconditionally) propagated. + struct SCEVPoisonCollector { + bool LookThroughSeq; + SmallPtrSet MaybePoison; + SCEVPoisonCollector(bool LookThroughSeq) : LookThroughSeq(LookThroughSeq) {} + + bool follow(const SCEV *S) { + // TODO: We can always follow the first operand, but the SCEVTraversal + // API doesn't support this. + if (!LookThroughSeq && isa(S)) + return false; + + if (auto *SU = dyn_cast(S)) { + if (!isGuaranteedNotToBePoison(SU->getValue())) + MaybePoison.insert(S); + } + return true; + } + bool isDone() const { return false; } + }; + + // First collect all SCEVs that might result in AssumedPoison to be poison. + // We need to look through umin_seq here, because we want to find all SCEVs + // that *might* result in poison, not only those that are *required* to. + SCEVPoisonCollector PC1(/* LookThroughSeq */ true); + visitAll(AssumedPoison, PC1); + + // Contradiction in assumption. + if (PC1.MaybePoison.empty()) + return true; + + // TODO: For now, only handle the case where we know a single root SCEV that + // must be poison. More general cases require careful reasoning about + // contribution of poison towards certain subexpressions. + if (PC1.MaybePoison.size() > 1) + return false; + + const SCEV *MustBePoison = *PC1.MaybePoison.begin(); + + // Collect all SCEVs in S that, if poison, *will* result in S being poison + // as well. We cannot look through umin_seq here, as its argument only *may* + // make the result poison. + SCEVPoisonCollector PC2(/* LookThroughSeq */ false); + visitAll(S, PC2); + return PC2.MaybePoison.contains(MustBePoison); +} + const SCEV * ScalarEvolution::getSequentialMinMaxExpr(SCEVTypes Kind, SmallVectorImpl &Ops) { @@ -4076,6 +4131,19 @@ return getSequentialMinMaxExpr(Kind, Ops); } + // In %x umin_seq %y, if %y being poison implies %x is also poison, we can + // use a non-sequential umin instead. + for (unsigned i = 1, e = Ops.size(); i != e; ++i) { + if (::impliesPoison(Ops[i], Ops[i - 1])) { + SmallVector SeqOps = {Ops[i - 1], Ops[i]}; + Ops[i - 1] = getMinMaxExpr( + SCEVSequentialMinMaxExpr::getEquivalentNonSequentialSCEVType(Kind), + SeqOps); + Ops.erase(Ops.begin() + i); + return getSequentialMinMaxExpr(Kind, Ops); + } + } + // Okay, it looks like we really DO need an expr. Check to see if we // already have one, otherwise create a new one. FoldingSetNodeID ID; Index: llvm/test/Analysis/ScalarEvolution/exit-count-select-safe.ll =================================================================== --- llvm/test/Analysis/ScalarEvolution/exit-count-select-safe.ll +++ llvm/test/Analysis/ScalarEvolution/exit-count-select-safe.ll @@ -553,15 +553,15 @@ ; CHECK-NEXT: %add = add i32 %n, 1 ; CHECK-NEXT: --> (1 + %n) U: full-set S: full-set ; CHECK-NEXT: %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] -; CHECK-NEXT: --> {0,+,1}<%loop> U: full-set S: full-set Exits: (%n umin_seq (1 + %n)) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,1}<%loop> U: full-set S: full-set Exits: ((1 + %n) umin %n) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %i.next = add i32 %i, 1 -; CHECK-NEXT: --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + (%n umin_seq (1 + %n))) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + ((1 + %n) umin %n)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %cond = select i1 %cond_p0, i1 %cond_p1, i1 false ; CHECK-NEXT: --> (%cond_p0 umin_seq %cond_p1) U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Variant } ; CHECK-NEXT: Determining loop execution counts for: @logical_and_implies_poison1 -; CHECK-NEXT: Loop %loop: backedge-taken count is (%n umin_seq (1 + %n)) +; CHECK-NEXT: Loop %loop: backedge-taken count is ((1 + %n) umin %n) ; CHECK-NEXT: Loop %loop: max backedge-taken count is -1 -; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (%n umin_seq (1 + %n)) +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((1 + %n) umin %n) ; CHECK-NEXT: Predicates: ; CHECK: Loop %loop: Trip multiple is 1 ; @@ -585,15 +585,15 @@ ; CHECK-NEXT: %add = add i32 %n, 1 ; CHECK-NEXT: --> (1 + %n) U: full-set S: full-set ; CHECK-NEXT: %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] -; CHECK-NEXT: --> {0,+,1}<%loop> U: full-set S: full-set Exits: ((1 + %n) umin_seq %n) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,1}<%loop> U: full-set S: full-set Exits: ((1 + %n) umin %n) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %i.next = add i32 %i, 1 -; CHECK-NEXT: --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + ((1 + %n) umin_seq %n)) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + ((1 + %n) umin %n)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %cond = select i1 %cond_p0, i1 %cond_p1, i1 false ; CHECK-NEXT: --> (%cond_p0 umin_seq %cond_p1) U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Variant } ; CHECK-NEXT: Determining loop execution counts for: @logical_and_implies_poison2 -; CHECK-NEXT: Loop %loop: backedge-taken count is ((1 + %n) umin_seq %n) +; CHECK-NEXT: Loop %loop: backedge-taken count is ((1 + %n) umin %n) ; CHECK-NEXT: Loop %loop: max backedge-taken count is -1 -; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((1 + %n) umin_seq %n) +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((1 + %n) umin %n) ; CHECK-NEXT: Predicates: ; CHECK: Loop %loop: Trip multiple is 1 ; @@ -617,15 +617,15 @@ ; CHECK-NEXT: %add = add i32 %n, %m ; CHECK-NEXT: --> (%n + %m) U: full-set S: full-set ; CHECK-NEXT: %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] -; CHECK-NEXT: --> {0,+,1}<%loop> U: full-set S: full-set Exits: ((%n + %m) umin_seq %n) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,1}<%loop> U: full-set S: full-set Exits: ((%n + %m) umin %n) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %i.next = add i32 %i, 1 -; CHECK-NEXT: --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + ((%n + %m) umin_seq %n)) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + ((%n + %m) umin %n)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %cond = select i1 %cond_p0, i1 %cond_p1, i1 false ; CHECK-NEXT: --> (%cond_p0 umin_seq %cond_p1) U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Variant } ; CHECK-NEXT: Determining loop execution counts for: @logical_and_implies_poison3 -; CHECK-NEXT: Loop %loop: backedge-taken count is ((%n + %m) umin_seq %n) +; CHECK-NEXT: Loop %loop: backedge-taken count is ((%n + %m) umin %n) ; CHECK-NEXT: Loop %loop: max backedge-taken count is -1 -; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((%n + %m) umin_seq %n) +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is ((%n + %m) umin %n) ; CHECK-NEXT: Predicates: ; CHECK: Loop %loop: Trip multiple is 1 ; @@ -679,15 +679,15 @@ ; CHECK-LABEL: 'logical_and_implies_poison_noundef' ; CHECK-NEXT: Classifying expressions for: @logical_and_implies_poison_noundef ; CHECK-NEXT: %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] -; CHECK-NEXT: --> {0,+,1}<%loop> U: full-set S: full-set Exits: (%n umin_seq %m) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,1}<%loop> U: full-set S: full-set Exits: (%n umin %m) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %i.next = add i32 %i, 1 -; CHECK-NEXT: --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + (%n umin_seq %m)) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + (%n umin %m)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %cond = select i1 %cond_p0, i1 %cond_p1, i1 false ; CHECK-NEXT: --> (%cond_p0 umin_seq %cond_p1) U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Variant } ; CHECK-NEXT: Determining loop execution counts for: @logical_and_implies_poison_noundef -; CHECK-NEXT: Loop %loop: backedge-taken count is (%n umin_seq %m) +; CHECK-NEXT: Loop %loop: backedge-taken count is (%n umin %m) ; CHECK-NEXT: Loop %loop: max backedge-taken count is -1 -; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (%n umin_seq %m) +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (%n umin %m) ; CHECK-NEXT: Predicates: ; CHECK: Loop %loop: Trip multiple is 1 ; @@ -733,6 +733,7 @@ ret i32 %i } +; TODO: Converting this to umin would be safe as well. define i32 @logical_and_implies_poison_complex(i32 %n, i32 %m) { ; CHECK-LABEL: 'logical_and_implies_poison_complex' ; CHECK-NEXT: Classifying expressions for: @logical_and_implies_poison_complex @@ -774,17 +775,17 @@ ; CHECK-NEXT: %add = add i32 %n, 1 ; CHECK-NEXT: --> (1 + %n) U: full-set S: full-set ; CHECK-NEXT: %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] -; CHECK-NEXT: --> {0,+,1}<%loop> U: full-set S: full-set Exits: (%n umin_seq (1 + %n) umin_seq %m) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,1}<%loop> U: full-set S: full-set Exits: (((1 + %n) umin %n) umin_seq %m) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %i.next = add i32 %i, 1 -; CHECK-NEXT: --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + (%n umin_seq (1 + %n) umin_seq %m)) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + (((1 + %n) umin %n) umin_seq %m)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %cond = select i1 %cond_p0, i1 %cond_p1, i1 false ; CHECK-NEXT: --> (%cond_p0 umin_seq %cond_p1) U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Variant } ; CHECK-NEXT: %cond2 = select i1 %cond, i1 %cond_p2, i1 false ; CHECK-NEXT: --> (%cond_p0 umin_seq %cond_p1 umin_seq %cond_p2) U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Variant } ; CHECK-NEXT: Determining loop execution counts for: @logical_and_implies_multiple_ops -; CHECK-NEXT: Loop %loop: backedge-taken count is (%n umin_seq (1 + %n) umin_seq %m) +; CHECK-NEXT: Loop %loop: backedge-taken count is (((1 + %n) umin %n) umin_seq %m) ; CHECK-NEXT: Loop %loop: max backedge-taken count is -1 -; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (%n umin_seq (1 + %n) umin_seq %m) +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (((1 + %n) umin %n) umin_seq %m) ; CHECK-NEXT: Predicates: ; CHECK: Loop %loop: Trip multiple is 1 ; @@ -846,17 +847,17 @@ ; CHECK-NEXT: %add = add i32 %n, 1 ; CHECK-NEXT: --> (1 + %n) U: full-set S: full-set ; CHECK-NEXT: %i = phi i32 [ 0, %entry ], [ %i.next, %loop ] -; CHECK-NEXT: --> {0,+,1}<%loop> U: full-set S: full-set Exits: (%m umin_seq %n umin_seq (1 + %n)) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {0,+,1}<%loop> U: full-set S: full-set Exits: (%m umin_seq ((1 + %n) umin %n)) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %i.next = add i32 %i, 1 -; CHECK-NEXT: --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + (%m umin_seq %n umin_seq (1 + %n))) LoopDispositions: { %loop: Computable } +; CHECK-NEXT: --> {1,+,1}<%loop> U: full-set S: full-set Exits: (1 + (%m umin_seq ((1 + %n) umin %n))) LoopDispositions: { %loop: Computable } ; CHECK-NEXT: %cond = select i1 %cond_p0, i1 %cond_p1, i1 false ; CHECK-NEXT: --> (%cond_p0 umin_seq %cond_p1) U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Variant } ; CHECK-NEXT: %cond2 = select i1 %cond, i1 %cond_p2, i1 false ; CHECK-NEXT: --> (%cond_p0 umin_seq %cond_p1 umin_seq %cond_p2) U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Variant } ; CHECK-NEXT: Determining loop execution counts for: @logical_and_implies_multiple_ops3 -; CHECK-NEXT: Loop %loop: backedge-taken count is (%m umin_seq %n umin_seq (1 + %n)) +; CHECK-NEXT: Loop %loop: backedge-taken count is (%m umin_seq ((1 + %n) umin %n)) ; CHECK-NEXT: Loop %loop: max backedge-taken count is -1 -; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (%m umin_seq %n umin_seq (1 + %n)) +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is (%m umin_seq ((1 + %n) umin %n)) ; CHECK-NEXT: Predicates: ; CHECK: Loop %loop: Trip multiple is 1 ;