[SCEV] Fold umin_seq to umin using implied poison reasoning

[nikic]

Summary

Similar to how we convert logical and/or to bitwise and/or, we should also convert umin_seq to umin based on implied poison reasoning. In %x umin_seq %y, if %y being poison implies %x being poison, then we don't need the sequential evaluation: Having %y contribute towards the result will never make the result more poisonous. An important corollary of this is that if %y is never poison, we also don't need the sequential evaluation.

This avoids some of the regressions in D124910.

[nikic]

Simplify implementation

[reames]

LGTM w/minor comments

llvm/lib/Analysis/ScalarEvolution.cpp

4042

Can you add a small comment reminding the reader that constantexprs are not SCEVConstants? Save the next person the quick search to confirm. :)

4052

Can you add the early return here for when PCI.MayBePoison is empty? Might as well avoid walking the second SCEV.

Also gives you a good place to put for your comment about the corollary.

llvm/lib/Analysis/ScalarEvolution.cpp

public:
 
   RetVal visitUnknown(const SCEVUnknown *Expr) { return Expr; }
 
   RetVal visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { return Expr; }
 };
 
 } // 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<const SCEV *, 4> 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<SCEVSequentialMinMaxExpr>(S))
+        return false;
+
+      if (auto *SU = dyn_cast<SCEVUnknown>(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<const SCEV *> &Ops) {
   assert(SCEVSequentialMinMaxExpr::isSequentialMinMaxType(Kind) &&
          "Not a SCEVSequentialMinMaxExpr!");
   assert(!Ops.empty() && "Cannot get empty (u|s)(min|max)!");
   if (Ops.size() == 1)
     return Ops[0];
while (Idx < Ops.size()) {
       Ops.insert(Ops.begin() + Idx, SMME->op_begin(), SMME->op_end());
       DeletedAny = true;
     }
 
     if (DeletedAny)
       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<const SCEV *> 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;
   ID.AddInteger(Kind);
   for (unsigned i = 0, e = Ops.size(); i != e; ++i)
     ID.AddPointer(Ops[i]);
   void *IP = nullptr;
   const SCEV *ExistingSCEV = UniqueSCEVs.FindNodeOrInsertPos(ID, IP);

llvm/test/Analysis/ScalarEvolution/exit-count-select-safe.ll

 }
 
 define i32 @logical_and_implies_poison1(i32 %n) {
 ; CHECK-LABEL: 'logical_and_implies_poison1'
 ; CHECK-NEXT:  Classifying expressions for: @logical_and_implies_poison1
 ; 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: <<Unknown>> 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
 ;
 entry:
   %add = add i32 %n, 1
   br label %loop
 loop:
   %i = phi i32 [0, %entry], [%i.next, %loop]
   %i.next = add i32 %i, 1
   %cond_p0 = icmp ult i32 %i, %n
   %cond_p1 = icmp ult i32 %i, %add
   %cond = select i1 %cond_p0, i1 %cond_p1, i1 false
   br i1 %cond, label %loop, label %exit
 exit:
   ret i32 %i
 }
 
 define i32 @logical_and_implies_poison2(i32 %n) {
 ; CHECK-LABEL: 'logical_and_implies_poison2'
 ; CHECK-NEXT:  Classifying expressions for: @logical_and_implies_poison2
 ; 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: <<Unknown>> 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
 ;
 entry:
   %add = add i32 %n, 1
   br label %loop
 loop:
   %i = phi i32 [0, %entry], [%i.next, %loop]
   %i.next = add i32 %i, 1
   %cond_p0 = icmp ult i32 %i, %add
   %cond_p1 = icmp ult i32 %i, %n
   %cond = select i1 %cond_p0, i1 %cond_p1, i1 false
   br i1 %cond, label %loop, label %exit
 exit:
   ret i32 %i
 }
 
 define i32 @logical_and_implies_poison3(i32 %n, i32 %m) {
 ; CHECK-LABEL: 'logical_and_implies_poison3'
 ; CHECK-NEXT:  Classifying expressions for: @logical_and_implies_poison3
 ; 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: <<Unknown>> 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
 ;
 entry:
   %add = add i32 %n, %m
   br label %loop
 loop:
   %i = phi i32 [0, %entry], [%i.next, %loop]

 exit:
   ret i32 %i
 }
 
 define i32 @logical_and_implies_poison_noundef(i32 %n, i32 noundef %m) {
 ; 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: <<Unknown>> 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
 ;
 entry:
   br label %loop
 loop:
   %i = phi i32 [0, %entry], [%i.next, %loop]
   %i.next = add i32 %i, 1
loop:
   %cond_p0 = icmp ult i32 %i, %m
   %cond_p1 = icmp ult i32 %i, %n
   %cond = select i1 %cond_p0, i1 %cond_p1, i1 false
   br i1 %cond, label %loop, label %exit
 exit:
   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
 ; CHECK-NEXT:    %add = add i32 %n, %m
 ; CHECK-NEXT:    --> (%n + %m) U: full-set S: full-set
 ; CHECK-NEXT:    %add1 = add i32 %add, 1
 ; CHECK-NEXT:    --> (1 + %n + %m) U: full-set S: full-set
 ; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]

 }
 
 define i32 @logical_and_implies_multiple_ops(i32 %n, i32 %m) {
 ; CHECK-LABEL: 'logical_and_implies_multiple_ops'
 ; CHECK-NEXT:  Classifying expressions for: @logical_and_implies_multiple_ops
 ; 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: <<Unknown>> 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: <<Unknown>> 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
 ;
 entry:
   %add = add i32 %n, 1
   br label %loop
 loop:
   %i = phi i32 [0, %entry], [%i.next, %loop]

 }
 
 define i32 @logical_and_implies_multiple_ops3(i32 %n, i32 %m) {
 ; CHECK-LABEL: 'logical_and_implies_multiple_ops3'
 ; CHECK-NEXT:  Classifying expressions for: @logical_and_implies_multiple_ops3
 ; 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: <<Unknown>> 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: <<Unknown>> 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
 ;
 entry:
   %add = add i32 %n, 1
   br label %loop
 loop:
   %i = phi i32 [0, %entry], [%i.next, %loop]