[SCEV] recognize logical and/or pattern

[aqjune]

Summary

This patch makes SCEV recognize 'select A, B, false' and 'select A, true, B'.
This is a performance improvement that will be helpful after unsound select -> and/or transformation is removed, as discussed in D93065.

SCEV's answers for the select form should be a bit more conservative than the equivalent and A, B / or A, B.
Take this example: https://alive2.llvm.org/ce/z/NsP9ue .
To check whether it is valid for SCEV's computeExitLimit to return min(n, m) as ExactNotTaken value, I put llvm.assume at tgt.
It fails because the exit limit becomes poison if n is zero and m is poison. This is problematic if e.g. the exit value of i is replaced with min(n, m).
If either n or m is constant, we can revive the analysis again. I added relevant tests and put alive2 links there.

If and is used instead, this is okay: https://alive2.llvm.org/ce/z/K9rbJk . Hence the existing analysis is sound.

[aqjune]

llvm/test/Analysis/ScalarEvolution/trip-count-andor-selectform.ll

2

This file is copied from test/Analysis/ScalarEvolution/trip-count-andor.ll .
It shows that the result does not degenerate even if select form is used instead of and/or.

[nikic]

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

125

Is there a test where we actually infer something from the first condition? i < 10 && i < m for example?

Unfortunately we don't currently track symbolic max exit count per-exit, so it would have to be constant.

[aqjune]

make SCEV work if either n or m is constant

[aqjune]

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

125

Oh yes, actually there were quite a few cases where SCEV can return an exact trip count.
I updated the SCEV code & added relevant tests.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

7617

I think we can still do slightly better here: Even if the exact count is non-constant, we should still be able to take the min of the max (constant) counts in any case, right? In which case I would move this check into the EitherMayExit branch below and only adjust the BECount calculation, while keeping MaxBECount the same.

I think the condition you use here may also need more comment, as I would have expected the check to be only !isa<SCEVConstant>(EL1.ExactNotTaken) initially. Is the reasoning here that if EL0.ExactNotTaken is constant but EL1.ExactNotTaken is not, then either EL0.ExactNotTaken is zero, in which case umin will fold to zero and we won't use the second (potentially poison exit count), or it is non-zero, in which case we know that the other condition will be checked at least once and thus can't be poison.

So basically the general condition here would be if (isKnownNotPoison(EL1.ExactNotTaken) || isKnownNonZero(EL0.ExactNotTaken) || isConstantZero(EL0.ExactNotTaken), where the last case is only safe if we do fold down to zero.

[aqjune]

Calculate MaxBECount, add more comments, guarantee that BECount is folded into zero

[aqjune]

llvm/lib/Analysis/ScalarEvolution.cpp

7617

I think it depends on the meaning of MaxNotTaken. If it is always safe to introduce llvm.assume(i < MaxNotTaken) after exiting the loop, then the same rule will be applied, making umin(EL0.MaxNotTaken, EL1.MaxNotTaken) unsafe.
But, it *seems* MaxNotTaken is okay to be relaxed to allow poison because unlike ExactNotTaken it is unlikely to introduce such assumption or any equation that is equivalent to it. I imagined whether loop versioning would introduce something like that, but loop vectorization needs ExactNotTaken, and for other optimizations there might be other workarounds for this.

[nikic]

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp

7641

This will warn about unused BECC in release builds. There is an SCEV::isZero() helper though that checks for SCEVConstant that is zero.

I think you can simplify this whole block to something like:

// Make sure that if EL0.ExactNotTaken was zero, BECount is folded to zero,
// to satisfy condition (3) above.
assert(!EL0.ExactNotTaken->isZero() || BECount->isZero())

[aqjune]

Update assertion

[nikic]

Something that crossed my mind: While we now handle logical and/or correctly, the same underlying problem also exists for multi-exit loops. In that case we'd combine exit limits from multiple branches via umin(), even though some of them may be poisonous.

[aqjune]

In D93882#2475917, @nikic wrote:

Something that crossed my mind: While we now handle logical and/or correctly, the same underlying problem also exists for multi-exit loops. In that case we'd combine exit limits from multiple branches via umin(), even though some of them may be poisonous.

Would the place be computeSymbolicMaxBackedgeTakenCount ?
I think UMinUsingSelect or something like that is needed. Expander can lower it into instructions with select performing whether the first argument is non-zero.

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
   ExitLimit computeExitLimitFromCondImpl(ExitLimitCacheTy &Cache, const Loop *L,
                                          Value *ExitCond, bool ExitIfTrue,
                                          bool ControlsExit,
                                          bool AllowPredicates);
   Optional<ScalarEvolution::ExitLimit>
   computeExitLimitFromCondFromBinOp(ExitLimitCacheTy &Cache, const Loop *L,
                                     Value *ExitCond, bool ExitIfTrue,
                                     bool ControlsExit, bool AllowPredicates);
-  ExitLimit computeExitLimitFromCondFromBinOpHelper(
-      ExitLimitCacheTy &Cache, const Loop *L, BinaryOperator *BO,
-      bool EitherMayExit, bool ExitIfTrue, bool ControlsExit,
-      bool AllowPredicates, const Constant *NeutralElement);
+
   /// Compute the number of times the backedge of the specified loop will
   /// execute if its exit condition were a conditional branch of the ICmpInst
   /// ExitCond and ExitIfTrue. If AllowPredicates is set, this call will try
   /// to use a minimal set of SCEV predicates in order to return an exact
   /// answer.
   ExitLimit computeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond,
                                      bool ExitIfTrue,
                                      bool IsSubExpr,

llvm/lib/Analysis/ScalarEvolution.cpp

 #include <cstdlib>
 #include <map>
 #include <memory>
 #include <tuple>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
+using namespace PatternMatch;
 
 #define DEBUG_TYPE "scalar-evolution"
 
 STATISTIC(NumArrayLenItCounts,
           "Number of trip counts computed with array length");
 STATISTIC(NumTripCountsComputed,
           "Number of loops with predictable loop counts");
 STATISTIC(NumTripCountsNotComputed,
ScalarEvolution::ExitLimit ScalarEvolution::computeExitLimitFromCondImpl(
   return computeExitCountExhaustively(L, ExitCond, ExitIfTrue);
 }
 
 Optional<ScalarEvolution::ExitLimit>
 ScalarEvolution::computeExitLimitFromCondFromBinOp(
     ExitLimitCacheTy &Cache, const Loop *L, Value *ExitCond, bool ExitIfTrue,
     bool ControlsExit, bool AllowPredicates) {
   // Check if the controlling expression for this loop is an And or Or.
-  if (auto *BO = dyn_cast<BinaryOperator>(ExitCond)) {
-    if (BO->getOpcode() == Instruction::And)
-      return computeExitLimitFromCondFromBinOpHelper(
-          Cache, L, BO, !ExitIfTrue, ExitIfTrue, ControlsExit, AllowPredicates,
-          ConstantInt::get(BO->getType(), 1));
-    if (BO->getOpcode() == Instruction::Or)
-      return computeExitLimitFromCondFromBinOpHelper(
-          Cache, L, BO, ExitIfTrue, ExitIfTrue, ControlsExit, AllowPredicates,
-          ConstantInt::get(BO->getType(), 0));
-  }
+  Value *Op0, *Op1;
+  bool IsAnd = false;
+  if (match(ExitCond, m_LogicalAnd(m_Value(Op0), m_Value(Op1))))
+    IsAnd = true;
+  else if (match(ExitCond, m_LogicalOr(m_Value(Op0), m_Value(Op1))))
+    IsAnd = false;
+  else
     return None;
-}
 
-ScalarEvolution::ExitLimit
-ScalarEvolution::computeExitLimitFromCondFromBinOpHelper(
-    ExitLimitCacheTy &Cache, const Loop *L, BinaryOperator *BO,
-    bool EitherMayExit, bool ExitIfTrue, bool ControlsExit,
-    bool AllowPredicates, const Constant *NeutralElement) {
-  ExitLimit EL0 = computeExitLimitFromCondCached(
-      Cache, L, BO->getOperand(0), ExitIfTrue, ControlsExit && !EitherMayExit,
+  // EitherMayExit is true in these two cases:
+  //   br (and Op0 Op1), loop, exit
+  //   br (or  Op0 Op1), exit, loop
+  bool EitherMayExit = IsAnd ^ ExitIfTrue;
+  ExitLimit EL0 = computeExitLimitFromCondCached(Cache, L, Op0, ExitIfTrue,
+                                                 ControlsExit && !EitherMayExit,
                                                  AllowPredicates);
-  ExitLimit EL1 = computeExitLimitFromCondCached(
-      Cache, L, BO->getOperand(1), ExitIfTrue, ControlsExit && !EitherMayExit,
+  ExitLimit EL1 = computeExitLimitFromCondCached(Cache, L, Op1, ExitIfTrue,
+                                                 ControlsExit && !EitherMayExit,
                                                  AllowPredicates);
-  // Be robust against unsimplified IR for the form "op i1 X,
-  // NeutralElement"
-  if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1)))
-    return CI == NeutralElement ? EL0 : EL1;
-  if (ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(0)))
-    return CI == NeutralElement ? EL1 : EL0;
+
+  // Be robust against unsimplified IR for the form "op i1 X, NeutralElement"
+  const Constant *NeutralElement = ConstantInt::get(ExitCond->getType(), IsAnd);
+  if (isa<ConstantInt>(Op1))
+    return Op1 == NeutralElement ? EL0 : EL1;
+  if (isa<ConstantInt>(Op0))
+    return Op0 == NeutralElement ? EL1 : EL0;
+
   const SCEV *BECount = getCouldNotCompute();
   const SCEV *MaxBECount = getCouldNotCompute();
   if (EitherMayExit) {
     // Both conditions must be same for the loop to continue executing.
     // Choose the less conservative count.
-    if (EL0.ExactNotTaken == getCouldNotCompute() ||
-        EL1.ExactNotTaken == getCouldNotCompute())
-      BECount = getCouldNotCompute();
-    else
+    // If ExitCond is a short-circuit form (select), using
+    // umin(EL0.ExactNotTaken, EL1.ExactNotTaken) is unsafe in general.
+    // To see the detailed examples, please see
+    // test/Analysis/ScalarEvolution/exit-count-select.ll
+    bool PoisonSafe = isa<BinaryOperator>(ExitCond);
+    if (!PoisonSafe)
+      // Even if ExitCond is select, we can safely derive BECount using both
+      // EL0 and EL1 in these cases:
+      // (1) EL0.ExactNotTaken is non-zero
+      // (2) EL1.ExactNotTaken is non-poison
+      // (3) EL0.ExactNotTaken is zero (BECount should be simply zero and
+      //     it cannot be umin(0, ..))
+      // The PoisonSafe assignment below is simplified and the assertion after
+      // BECount calculation fully guarantees the condition (3).
+      PoisonSafe = isa<SCEVConstant>(EL0.ExactNotTaken) ||
+                   isa<SCEVConstant>(EL1.ExactNotTaken);
+    if (EL0.ExactNotTaken != getCouldNotCompute() &&
+        EL1.ExactNotTaken != getCouldNotCompute() && PoisonSafe) {
       BECount =
           getUMinFromMismatchedTypes(EL0.ExactNotTaken, EL1.ExactNotTaken);
+
+      // If EL0.ExactNotTaken was zero and ExitCond was a short-circuit form,
+      // it should have been simplified to zero (see the condition (3) above)
+      assert(!isa<BinaryOperator>(ExitCond) || !EL0.ExactNotTaken->isZero() ||
+             BECount->isZero());
+    }
     if (EL0.MaxNotTaken == getCouldNotCompute())
       MaxBECount = EL1.MaxNotTaken;
     else if (EL1.MaxNotTaken == getCouldNotCompute())
       MaxBECount = EL0.MaxNotTaken;
     else
       MaxBECount = getUMinFromMismatchedTypes(EL0.MaxNotTaken, EL1.MaxNotTaken);
   } else {
     // Both conditions must be same at the same time for the loop to exit.
     // For now, be conservative.
     if (EL0.ExactNotTaken == EL1.ExactNotTaken)

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

+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
+; RUN: opt -analyze -enable-new-pm=0 -scalar-evolution %s | FileCheck %s
+; RUN: opt -disable-output "-passes=print<scalar-evolution>" %s 2>&1 | FileCheck %s
+
+
+; exact-not-taken cannot be umin(n, m) because it is possible for (n, m) to be (0, poison)
+; https://alive2.llvm.org/ce/z/NsP9ue
+define void @logical_and(i32 %n, i32 %m) {
+; CHECK-LABEL: 'logical_and'
+; CHECK-NEXT:  Classifying expressions for: @logical_and
+; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %i.next = add i32 %i, 1
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %cond = select i1 %cond_i, i1 %cond_i2, i1 false
+; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:  Determining loop execution counts for: @logical_and
+; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
+;
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [0, %entry], [%i.next, %loop]
+  %i.next = add i32 %i, 1
+  %cond_i = icmp ult i32 %i, %n
+  %cond_i2 = icmp ult i32 %i, %m
+  %cond = select i1 %cond_i, i1 %cond_i2, i1 false
+  br i1 %cond, label %loop, label %exit
+exit:
+  ret void
+}
+
+; If m is constant, exact-not-taken is umin(n, m)
+; https://alive2.llvm.org/ce/z/ZTNXgY
+define void @logical_and_m_const(i32 %n) {
+; CHECK-LABEL: 'logical_and_m_const'
+; CHECK-NEXT:  Classifying expressions for: @logical_and_m_const
+; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,3) S: [0,3) Exits: (2 umin %n) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %i.next = add i32 %i, 1
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,4) S: [1,4) Exits: (1 + (2 umin %n))<nuw><nsw> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %cond = select i1 %cond_i, i1 %cond_i2, i1 false
+; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:  Determining loop execution counts for: @logical_and_m_const
+; CHECK-NEXT:  Loop %loop: backedge-taken count is (2 umin %n)
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 2
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (2 umin %n)
+; 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
+  %cond_i = icmp ult i32 %i, %n
+  %cond_i2 = icmp ult i32 %i, 2
+  %cond = select i1 %cond_i, i1 %cond_i2, i1 false
+  br i1 %cond, label %loop, label %exit
+exit:
+  ret void
+}
+
+; exact-not-taken is umin(2, m) because m participates in the exit branch condition.
+; https://alive2.llvm.org/ce/z/rCVMmp
+define void @logical_and_nonzero(i32 %m) {
+; CHECK-LABEL: 'logical_and_nonzero'
+; CHECK-NEXT:  Classifying expressions for: @logical_and_nonzero
+; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,3) S: [0,3) Exits: (2 umin %m) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %i.next = add i32 %i, 1
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,4) S: [1,4) Exits: (1 + (2 umin %m))<nuw><nsw> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %cond = select i1 %cond_i, i1 %cond_i2, i1 false
+; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:  Determining loop execution counts for: @logical_and_nonzero
+; CHECK-NEXT:  Loop %loop: backedge-taken count is (2 umin %m)
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 2
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (2 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
+  %cond_i = icmp ult i32 %i, 2
+  %cond_i2 = icmp ult i32 %i, %m
+  %cond = select i1 %cond_i, i1 %cond_i2, i1 false
+  br i1 %cond, label %loop, label %exit
+exit:
+  ret void
+}
+
+; exact-not-taken cannot be umin(0, m) because m never participates in the exit branch condition.
+; https://alive2.llvm.org/ce/z/rlaN4a
+; Instead, it should be just 0.
+define void @logical_and_zero(i32 %m) {
+; CHECK-LABEL: 'logical_and_zero'
+; CHECK-NEXT:  Classifying expressions for: @logical_and_zero
+; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,1) S: [0,1) Exits: 0 LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %i.next = add i32 %i, 1
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,2) S: [1,2) Exits: 1 LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %cond = select i1 %cond_i, i1 %cond_i2, i1 false
+; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:  Determining loop execution counts for: @logical_and_zero
+; CHECK-NEXT:  Loop %loop: backedge-taken count is 0
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 0
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 0
+; 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
+  %cond_i = icmp ult i32 %i, 0
+  %cond_i2 = icmp ult i32 %i, %m
+  %cond = select i1 %cond_i, i1 %cond_i2, i1 false
+  br i1 %cond, label %loop, label %exit
+exit:
+  ret void
+}
+
+; exact-not-taken is umax(n, m) because both conditions (cond_i, cond_i2) participate in branching,
+; preventing them from being poison.
+; https://alive2.llvm.org/ce/z/8_p-zu
+; Currently SCEV is conservative in this case and simply returns unknown.
+define void @logical_and_inversed(i32 %n, i32 %m) {
+; CHECK-LABEL: 'logical_and_inversed'
+; CHECK-NEXT:  Classifying expressions for: @logical_and_inversed
+; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %i.next = add i32 %i, 1
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %cond = select i1 %cond_i, i1 %cond_i2, i1 false
+; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:  Determining loop execution counts for: @logical_and_inversed
+; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable max backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
+;
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [0, %entry], [%i.next, %loop]
+  %i.next = add i32 %i, 1
+  %cond_i = icmp uge i32 %i, %n
+  %cond_i2 = icmp uge i32 %i, %m
+  %cond = select i1 %cond_i, i1 %cond_i2, i1 false
+  br i1 %cond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; exact-not-taken cannot be umin(n, m) because it is possible for (n, m) to be (0, poison)
+; https://alive2.llvm.org/ce/z/ApRitq
+define void @logical_or(i32 %n, i32 %m) {
+; CHECK-LABEL: 'logical_or'
+; CHECK-NEXT:  Classifying expressions for: @logical_or
+; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %i.next = add i32 %i, 1
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %cond = select i1 %cond_i, i1 true, i1 %cond_i2
+; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:  Determining loop execution counts for: @logical_or
+; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
+;
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [0, %entry], [%i.next, %loop]
+  %i.next = add i32 %i, 1
+  %cond_i = icmp uge i32 %i, %n
+  %cond_i2 = icmp uge i32 %i, %m
+  %cond = select i1 %cond_i, i1 true, i1 %cond_i2
+  br i1 %cond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; If m is constant,  exact-not-taken is umin(n, m)
+; https://alive2.llvm.org/ce/z/RQmJiq
+define void @logical_or_m_const(i32 %n) {
+; CHECK-LABEL: 'logical_or_m_const'
+; CHECK-NEXT:  Classifying expressions for: @logical_or_m_const
+; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,3) S: [0,3) Exits: (2 umin %n) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %i.next = add i32 %i, 1
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,4) S: [1,4) Exits: (1 + (2 umin %n))<nuw><nsw> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %cond = select i1 %cond_i, i1 true, i1 %cond_i2
+; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:  Determining loop execution counts for: @logical_or_m_const
+; CHECK-NEXT:  Loop %loop: backedge-taken count is (2 umin %n)
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 2
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (2 umin %n)
+; 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
+  %cond_i = icmp uge i32 %i, %n
+  %cond_i2 = icmp uge i32 %i, 2
+  %cond = select i1 %cond_i, i1 true, i1 %cond_i2
+  br i1 %cond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; exact-not-taken is umin(2, m) because m participates in exit branch condition.
+; https://alive2.llvm.org/ce/z/zcHS_d
+define void @logical_or_nonzero(i32 %m) {
+; CHECK-LABEL: 'logical_or_nonzero'
+; CHECK-NEXT:  Classifying expressions for: @logical_or_nonzero
+; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,3) S: [0,3) Exits: (2 umin %m) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %i.next = add i32 %i, 1
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,4) S: [1,4) Exits: (1 + (2 umin %m))<nuw><nsw> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %cond = select i1 %cond_i, i1 true, i1 %cond_i2
+; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:  Determining loop execution counts for: @logical_or_nonzero
+; CHECK-NEXT:  Loop %loop: backedge-taken count is (2 umin %m)
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 2
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (2 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
+  %cond_i = icmp uge i32 %i, 2
+  %cond_i2 = icmp uge i32 %i, %m
+  %cond = select i1 %cond_i, i1 true, i1 %cond_i2
+  br i1 %cond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; exact-not-taken cannot be umin(0, m) because m does not participate in exit branch condition.
+; https://alive2.llvm.org/ce/z/-dUmmc
+; Instead, exact-not-taken should be just 0.
+define void @logical_or_zero(i32 %m) {
+; CHECK-LABEL: 'logical_or_zero'
+; CHECK-NEXT:  Classifying expressions for: @logical_or_zero
+; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,1) S: [0,1) Exits: 0 LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %i.next = add i32 %i, 1
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,2) S: [1,2) Exits: 1 LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %cond = select i1 %cond_i, i1 true, i1 %cond_i2
+; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:  Determining loop execution counts for: @logical_or_zero
+; CHECK-NEXT:  Loop %loop: backedge-taken count is 0
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is 0
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 0
+; 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
+  %cond_i = icmp uge i32 %i, 0
+  %cond_i2 = icmp uge i32 %i, %m
+  %cond = select i1 %cond_i, i1 true, i1 %cond_i2
+  br i1 %cond, label %exit, label %loop
+exit:
+  ret void
+}
+
+; exact-not-taken is umax(n, m) because both conditions (cond_i, cond_i2) participate in branching,
+; preventing them from being poison.
+; https://alive2.llvm.org/ce/z/VaCu9C
+; Currently SCEV is conservative in this case and simply returns unknown.
+define void @logical_or_inversed(i32 %n, i32 %m) {
+; CHECK-LABEL: 'logical_or_inversed'
+; CHECK-NEXT:  Classifying expressions for: @logical_or_inversed
+; CHECK-NEXT:    %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
+; CHECK-NEXT:    --> {0,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %i.next = add i32 %i, 1
+; CHECK-NEXT:    --> {1,+,1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %cond = select i1 %cond_i, i1 true, i1 %cond_i2
+; CHECK-NEXT:    --> %cond U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:  Determining loop execution counts for: @logical_or_inversed
+; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable max backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
+;
+entry:
+  br label %loop
+loop:
+  %i = phi i32 [0, %entry], [%i.next, %loop]
+  %i.next = add i32 %i, 1
+  %cond_i = icmp ult i32 %i, %n
+  %cond_i2 = icmp ult i32 %i, %m
+  %cond = select i1 %cond_i, i1 true, i1 %cond_i2
+  br i1 %cond, label %loop, label %exit
+exit:
+  ret void
+}

llvm/test/Analysis/ScalarEvolution/trip-count-andor-selectform.ll

+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
+; RUN: opt < %s -analyze -enable-new-pm=0 -scalar-evolution -scalar-evolution-classify-expressions=0 2>&1 | FileCheck %s
+; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" -scalar-evolution-classify-expressions=0 2>&1 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @unsimplified_and1(i32 %n) {
+; CHECK-LABEL: 'unsimplified_and1'
+; CHECK-NEXT:  Determining loop execution counts for: @unsimplified_and1
+; CHECK-NEXT:  Loop %loop: backedge-taken count is %n
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is %n
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 1
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i32 %iv, 1
+  %becond = icmp ule i32 %iv.inc, %n
+  %and = select i1 %becond, i1 true, i1 false
+  br i1 %and, label %loop, label %leave
+
+leave:
+  ret void
+}
+
+define void @unsimplified_and2(i32 %n) {
+; CHECK-LABEL: 'unsimplified_and2'
+; CHECK-NEXT:  Determining loop execution counts for: @unsimplified_and2
+; CHECK-NEXT:  Loop %loop: backedge-taken count is %n
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is %n
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 1
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i32 %iv, 1
+  %becond = icmp ule i32 %iv.inc, %n
+  %and = select i1 true, i1 %becond, i1 false
+  br i1 %and, label %loop, label %leave
+
+leave:
+  ret void
+}
+
+define void @unsimplified_and3(i32 %n) {
+; CHECK-LABEL: 'unsimplified_and3'
+; CHECK-NEXT:  Determining loop execution counts for: @unsimplified_and3
+; CHECK-NEXT:  Loop %loop: backedge-taken count is false
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is false
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is false
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 1
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i32 %iv, 1
+  %becond = icmp ule i32 %iv.inc, %n
+  %and = select i1 false, i1 %becond, i1 false
+  br i1 %and, label %loop, label %leave
+
+leave:
+  ret void
+}
+
+define void @unsimplified_and4(i32 %n) {
+; CHECK-LABEL: 'unsimplified_and4'
+; CHECK-NEXT:  Determining loop execution counts for: @unsimplified_and4
+; CHECK-NEXT:  Loop %loop: backedge-taken count is false
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is false
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is false
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 1
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i32 %iv, 1
+  %becond = icmp ule i32 %iv.inc, %n
+  %and = select i1 %becond, i1 false, i1 false
+  br i1 %and, label %loop, label %leave
+
+leave:
+  ret void
+}
+
+define void @unsimplified_or1(i32 %n) {
+; CHECK-LABEL: 'unsimplified_or1'
+; CHECK-NEXT:  Determining loop execution counts for: @unsimplified_or1
+; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable max backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i32 %iv, 1
+  %becond = icmp ule i32 %iv.inc, %n
+  %or = select i1 %becond, i1 true, i1 true
+  br i1 %or, label %loop, label %leave
+
+leave:
+  ret void
+}
+
+define void @unsimplified_or2(i32 %n) {
+; CHECK-LABEL: 'unsimplified_or2'
+; CHECK-NEXT:  Determining loop execution counts for: @unsimplified_or2
+; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable max backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i32 %iv, 1
+  %becond = icmp ule i32 %iv.inc, %n
+  %or = select i1 true, i1 true, i1 %becond
+  br i1 %or, label %loop, label %leave
+
+leave:
+  ret void
+}
+
+define void @unsimplified_or3(i32 %n) {
+; CHECK-LABEL: 'unsimplified_or3'
+; CHECK-NEXT:  Determining loop execution counts for: @unsimplified_or3
+; CHECK-NEXT:  Loop %loop: backedge-taken count is %n
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is %n
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 1
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i32 %iv, 1
+  %becond = icmp ule i32 %iv.inc, %n
+  %or = select i1 false, i1 true, i1 %becond
+  br i1 %or, label %loop, label %leave
+
+leave:
+  ret void
+}
+
+define void @unsimplified_or4(i32 %n) {
+; CHECK-LABEL: 'unsimplified_or4'
+; CHECK-NEXT:  Determining loop execution counts for: @unsimplified_or4
+; CHECK-NEXT:  Loop %loop: backedge-taken count is %n
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is %n
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 1
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i32 %iv, 1
+  %becond = icmp ule i32 %iv.inc, %n
+  %or = select i1 %becond, i1 true, i1 false
+  br i1 %or, label %loop, label %leave
+
+leave:
+  ret void
+}
+
+define void @reversed_and1(i32 %n) {
+; CHECK-LABEL: 'reversed_and1'
+; CHECK-NEXT:  Determining loop execution counts for: @reversed_and1
+; CHECK-NEXT:  Loop %loop: backedge-taken count is %n
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is %n
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 1
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i32 %iv, 1
+  %becond = icmp ugt i32 %iv.inc, %n
+  %and = select i1 %becond, i1 true, i1 false
+  br i1 %and, label %leave, label %loop
+
+leave:
+  ret void
+}
+
+define void @reversed_and2(i32 %n) {
+; CHECK-LABEL: 'reversed_and2'
+; CHECK-NEXT:  Determining loop execution counts for: @reversed_and2
+; CHECK-NEXT:  Loop %loop: backedge-taken count is %n
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is %n
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 1
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i32 %iv, 1
+  %becond = icmp ugt i32 %iv.inc, %n
+  %and = select i1 true, i1 %becond, i1 false
+  br i1 %and, label %leave, label %loop
+
+leave:
+  ret void
+}
+
+define void @reversed_and3(i32 %n) {
+; CHECK-LABEL: 'reversed_and3'
+; CHECK-NEXT:  Determining loop execution counts for: @reversed_and3
+; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable max backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i32 %iv, 1
+  %becond = icmp ugt i32 %iv.inc, %n
+  %and = select i1 false, i1 %becond, i1 false
+  br i1 %and, label %leave, label %loop
+
+leave:
+  ret void
+}
+
+define void @reversed_and4(i32 %n) {
+; CHECK-LABEL: 'reversed_and4'
+; CHECK-NEXT:  Determining loop execution counts for: @reversed_and4
+; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable max backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i32 %iv, 1
+  %becond = icmp ugt i32 %iv.inc, %n
+  %and = select i1 %becond, i1 false, i1 false
+  br i1 %and, label %leave, label %loop
+
+leave:
+  ret void
+}
+
+define void @reversed_or1(i32 %n) {
+; CHECK-LABEL: 'reversed_or1'
+; CHECK-NEXT:  Determining loop execution counts for: @reversed_or1
+; CHECK-NEXT:  Loop %loop: backedge-taken count is false
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is false
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is false
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 1
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i32 %iv, 1
+  %becond = icmp ugt i32 %iv.inc, %n
+  %or = select i1 %becond, i1 true, i1 true
+  br i1 %or, label %leave, label %loop
+
+leave:
+  ret void
+}
+
+define void @reversed_or2(i32 %n) {
+; CHECK-LABEL: 'reversed_or2'
+; CHECK-NEXT:  Determining loop execution counts for: @reversed_or2
+; CHECK-NEXT:  Loop %loop: backedge-taken count is false
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is false
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is false
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 1
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i32 %iv, 1
+  %becond = icmp ugt i32 %iv.inc, %n
+  %or = select i1 true, i1 true, i1 %becond
+  br i1 %or, label %leave, label %loop
+
+leave:
+  ret void
+}
+
+define void @reversed_or3(i32 %n) {
+; CHECK-LABEL: 'reversed_or3'
+; CHECK-NEXT:  Determining loop execution counts for: @reversed_or3
+; CHECK-NEXT:  Loop %loop: backedge-taken count is %n
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is %n
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 1
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i32 %iv, 1
+  %becond = icmp ugt i32 %iv.inc, %n
+  %or = select i1 false, i1 true, i1 %becond
+  br i1 %or, label %leave, label %loop
+
+leave:
+  ret void
+}
+
+define void @reversed_or4(i32 %n) {
+; CHECK-LABEL: 'reversed_or4'
+; CHECK-NEXT:  Determining loop execution counts for: @reversed_or4
+; CHECK-NEXT:  Loop %loop: backedge-taken count is %n
+; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is %n
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %loop: Trip multiple is 1
+;
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+  %iv.inc = add nsw i32 %iv, 1
+  %becond = icmp ugt i32 %iv.inc, %n
+  %or = select i1 %becond, i1 true, i1 false
+  br i1 %or, label %leave, label %loop
+
+leave:
+  ret void
+}