[SCEV] Canonicalize ext(min/max(x, y)) to min/max(ext(x), ext(y))

[mkazantsev]

Summary

I stumbled over this when trying to improve our exit count work. These expressions
are equivalent for complementary signed/unsigned ext and min/max (including umin_seq),
but they are not canonicalized and SCEV cannot recognize them as the same.

The benefit of this canonicalization is that SCEV can prove some new equivalences which
it coudln't prove because of different forms. There is 1 test where trip count seems pessimized,
I could not directly figure out why, but it just seems an unrelated issue that we can fix.
Other changes seem neutral to me.

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/fold.ll

78

There are even some improvements from it.

[mkazantsev]

Ping?

[mkazantsev]

Ping

[nikic]

llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info-rewrite-expressions.ll

47

Why does this regress?

[mkazantsev]

Rebased.

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info-rewrite-expressions.ll

47

Investigating.

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info-rewrite-expressions.ll

47

I digged as deep as that inside of howFarToZero, there is code

if (Exact != getCouldNotCompute()) {
  APInt MaxInt = getUnsignedRangeMax(applyLoopGuards(Exact, L));
  ConstantMax =
      getConstant(APIntOps::umin(MaxInt, getUnsignedRangeMax(Exact)));
}

and here is the numbers are coming from. Good case:

Exact = ((-4 + (4 * ((zext i32 (16 umin %N) to i64) /u 4))<nuw><nsw>)<nsw> /u 4), ConstantMax = 3

Bad case:

Exact = ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4), ConstantMax = 4611686018427387903

I didn't go deep enough to understand what exactly was missing on range computation. Looks like that one of dozens of ad-hoc ways to compute it has failed. I could theoretically go deeper and try to understand this. I'm pretty sure this SCEV can be constructed with same result even now, just no test that would expose the problem.

Question is: do we care enough to be blocked on this? What the patch did makes perfect sense, it's just another heuristic missing somewhere. I can assign someone to take a look a bit later, unless this is a serious problem.

How much are you concerned by this?

[nikic]

llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info-rewrite-expressions.ll

47

Maybe it's related to the fact that applyLoopGuards rewriting supports zext but not umin? https://github.com/llvm/llvm-project/blob/c05ace1067bd21abf504d75f1efb5cf0e1c3fb51/llvm/lib/Analysis/ScalarEvolution.cpp#L14956

How much are you concerned by this?

Based on the comment above, it looks like this is a motivating case for the applyLoopGuards() logic, not just artificial test coverage, so it would be nice to not regress it.

[mkazantsev]

Ok, I'll see what I can do...

[mkazantsev]

Rebased and updated.

Short summary:

1. With improvements in SCEVLoopGuardRewriter, all old regressions are fixed.
2. I've added a bunch of new tests and two of them start working with D143259 but regress with this canonicalization back to the prior state. I don't know why exactly.
3. The whole thing with divisibility is raw and fragile, and this fragility is spiralling out of scope, this time the problem seems to be outside of SCEVLoopGuardRewriter.
4. Rather than doing all these crazy rewritings, I'd just prefer to have getRangeAtScope and it seems to solve all problems we've faced so far.

I'll try to find some time to take a look into it later myself or ask someone of my colleagues to investigate, but I absolutely don't want to be blocked on these new tests. They never worked, they don't work again, this is fine.

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info-rewrite-expressions.ll

94

This is a new test, improved by D143259 and regressed back by this due to some fragile algorithms somewhere.

94

Same

[mkazantsev]

Ping

[nikic]

LGTM

[efriedma]

This comment was removed by efriedma.

[efriedma]

Nevermind, ignore me, I somehow got it backwards; the given example gets improved.

llvm/lib/Analysis/ScalarEvolution.cpp

if (SM->getNumOperands() == 2)
             return getMulExpr(
                 getZeroExtendExpr(MulLHS, Ty),
                 getZeroExtendExpr(
                     getTruncateExpr(TruncRHS->getOperand(), NewTruncTy), Ty),
                 SCEV::FlagNUW, Depth + 1);
           }
   }
 
+  // zext(umin(x, y)) -> umin(zext(x), zext(y))
+  // zext(umax(x, y)) -> umax(zext(x), zext(y))
+  if (isa<SCEVUMinExpr>(Op) || isa<SCEVUMaxExpr>(Op)) {
+    auto *MinMax = cast<SCEVMinMaxExpr>(Op);
+    SmallVector<const SCEV *, 4> Operands;
+    for (auto *Operand : MinMax->operands())
+      Operands.push_back(getZeroExtendExpr(Operand, Ty));
+    if (isa<SCEVUMinExpr>(MinMax))
+      return getUMinExpr(Operands);
+    else
+      return getUMaxExpr(Operands);
+  }
+
+  // zext(umin_seq(x, y)) -> umin_seq(zext(x), zext(y))
+  if (auto *MinMax = dyn_cast<SCEVSequentialMinMaxExpr>(Op)) {
+    assert(isa<SCEVSequentialUMinExpr>(MinMax) && "Not supported!");
+    SmallVector<const SCEV *, 4> Operands;
+    for (auto *Operand : MinMax->operands())
+      Operands.push_back(getZeroExtendExpr(Operand, Ty));
+    return getUMinExpr(Operands, /*Sequential*/ true);
+  }
+
   // The cast wasn't folded; create an explicit cast node.
   // Recompute the insert position, as it may have been invalidated.
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
   SCEV *S = new (SCEVAllocator) SCEVZeroExtendExpr(ID.Intern(SCEVAllocator),
                                                    Op, Ty);
   UniqueSCEVs.InsertNode(S, IP);
   registerUser(S, Op);
   return S;
if (AR->isAffine()) {
       }
     }
 
   // If the input value is provably positive and we could not simplify
   // away the sext build a zext instead.
   if (isKnownNonNegative(Op))
     return getZeroExtendExpr(Op, Ty, Depth + 1);
 
+  // sext(smin(x, y)) -> smin(sext(x), sext(y))
+  // sext(smax(x, y)) -> smax(sext(x), sext(y))
+  if (isa<SCEVSMinExpr>(Op) || isa<SCEVSMaxExpr>(Op)) {
+    auto *MinMax = cast<SCEVMinMaxExpr>(Op);
+    SmallVector<const SCEV *, 4> Operands;
+    for (auto *Operand : MinMax->operands())
+      Operands.push_back(getSignExtendExpr(Operand, Ty));
+    if (isa<SCEVSMinExpr>(MinMax))
+      return getSMinExpr(Operands);
+    else
+      return getSMaxExpr(Operands);
+  }
+
   // The cast wasn't folded; create an explicit cast node.
   // Recompute the insert position, as it may have been invalidated.
   if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP)) return S;
   SCEV *S = new (SCEVAllocator) SCEVSignExtendExpr(ID.Intern(SCEVAllocator),
                                                    Op, Ty);
   UniqueSCEVs.InsertNode(S, IP);
   registerUser(S, { Op });
   return S;

llvm/test/Analysis/ScalarEvolution/ext_min_max.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt -S -disable-output "-passes=print<scalar-evolution>" < %s 2>&1 | FileCheck %s
 
-; TODO: Make sure that zext(umin(x, y)) has same SCEV as umin(zext(x), zext(y)).
+; Make sure that zext(umin(x, y)) has same SCEV as umin(zext(x), zext(y)).
 ; Equality proof: https://alive2.llvm.org/ce/z/vdsvmp
 define i1 @test_umin(i32 %x, i32 %y) {
 ; CHECK-LABEL: 'test_umin'
 ; CHECK-NEXT:  Classifying expressions for: @test_umin
 ; CHECK-NEXT:    %umin_x_y = select i1 %cmp_x_y, i32 %x, i32 %y
 ; CHECK-NEXT:    --> (%x umin %y) U: full-set S: full-set
 ; CHECK-NEXT:    %zext_umin_x_y = zext i32 %umin_x_y to i64
-; CHECK-NEXT:    --> (zext i32 (%x umin %y) to i64) U: [0,4294967296) S: [0,4294967296)
+; CHECK-NEXT:    --> ((zext i32 %x to i64) umin (zext i32 %y to i64)) U: [0,4294967296) S: [0,4294967296)
 ; CHECK-NEXT:    %zext_x = zext i32 %x to i64
 ; CHECK-NEXT:    --> (zext i32 %x to i64) U: [0,4294967296) S: [0,4294967296)
 ; CHECK-NEXT:    %zext_y = zext i32 %y to i64
 ; CHECK-NEXT:    --> (zext i32 %y to i64) U: [0,4294967296) S: [0,4294967296)
 ; CHECK-NEXT:    %umin_zext_x_zext_y = select i1 %cmp_zext_x_zext_y, i64 %zext_x, i64 %zext_y
 ; CHECK-NEXT:    --> ((zext i32 %x to i64) umin (zext i32 %y to i64)) U: [0,4294967296) S: [0,4294967296)
 ; CHECK-NEXT:  Determining loop execution counts for: @test_umin
 ;
   %cmp_x_y = icmp ult i32 %x, %y
   %umin_x_y = select i1 %cmp_x_y, i32 %x, i32 %y
   %zext_umin_x_y = zext i32 %umin_x_y to i64
 
   %zext_x = zext i32 %x to i64
   %zext_y = zext i32 %y to i64
   %cmp_zext_x_zext_y = icmp ult i64 %zext_x, %zext_y
   %umin_zext_x_zext_y = select i1 %cmp_zext_x_zext_y, i64 %zext_x, i64 %zext_y
 
   %they_are_same = icmp eq i64 %zext_umin_x_y, %umin_zext_x_zext_y
   ret i1 %they_are_same
 }
 
-; TODO: Make sure that zext(umax(x, y)) has same SCEV as umax(zext(x), zext(y)).
+; Make sure that zext(umax(x, y)) has same SCEV as umax(zext(x), zext(y)).
 ; Equality proof: https://alive2.llvm.org/ce/z/5JHgxZ
 define i1 @test_umax(i32 %x, i32 %y) {
 ; CHECK-LABEL: 'test_umax'
 ; CHECK-NEXT:  Classifying expressions for: @test_umax
 ; CHECK-NEXT:    %umax_x_y = select i1 %cmp_x_y, i32 %y, i32 %x
 ; CHECK-NEXT:    --> (%x umax %y) U: full-set S: full-set
 ; CHECK-NEXT:    %zext_umax_x_y = zext i32 %umax_x_y to i64
-; CHECK-NEXT:    --> (zext i32 (%x umax %y) to i64) U: [0,4294967296) S: [0,4294967296)
+; CHECK-NEXT:    --> ((zext i32 %x to i64) umax (zext i32 %y to i64)) U: [0,4294967296) S: [0,4294967296)
 ; CHECK-NEXT:    %zext_x = zext i32 %x to i64
 ; CHECK-NEXT:    --> (zext i32 %x to i64) U: [0,4294967296) S: [0,4294967296)
 ; CHECK-NEXT:    %zext_y = zext i32 %y to i64
 ; CHECK-NEXT:    --> (zext i32 %y to i64) U: [0,4294967296) S: [0,4294967296)
 ; CHECK-NEXT:    %umax_zext_x_zext_y = select i1 %cmp_zext_x_zext_y, i64 %zext_y, i64 %zext_x
 ; CHECK-NEXT:    --> ((zext i32 %x to i64) umax (zext i32 %y to i64)) U: [0,4294967296) S: [0,4294967296)
 ; CHECK-NEXT:  Determining loop execution counts for: @test_umax
 ;
   %cmp_x_y = icmp ult i32 %x, %y
   %umax_x_y = select i1 %cmp_x_y, i32 %y, i32 %x
   %zext_umax_x_y = zext i32 %umax_x_y to i64
 
   %zext_x = zext i32 %x to i64
   %zext_y = zext i32 %y to i64
   %cmp_zext_x_zext_y = icmp ult i64 %zext_x, %zext_y
   %umax_zext_x_zext_y = select i1 %cmp_zext_x_zext_y, i64 %zext_y, i64 %zext_x
 
   %they_are_same = icmp eq i64 %zext_umax_x_y, %umax_zext_x_zext_y
   ret i1 %they_are_same
 }
 
-; TODO: Make sure that sext(smin(x, y)) has same SCEV as smin(sext(x), sext(y)).
+; Make sure that sext(smin(x, y)) has same SCEV as smin(sext(x), sext(y)).
 ; Equality proof: https://alive2.llvm.org/ce/z/HhYHzR
 define i1 @test_smin(i32 %x, i32 %y) {
 ; CHECK-LABEL: 'test_smin'
 ; CHECK-NEXT:  Classifying expressions for: @test_smin
 ; CHECK-NEXT:    %smin_x_y = select i1 %cmp_x_y, i32 %x, i32 %y
 ; CHECK-NEXT:    --> (%x smin %y) U: full-set S: full-set
 ; CHECK-NEXT:    %sext_smin_x_y = sext i32 %smin_x_y to i64
-; CHECK-NEXT:    --> (sext i32 (%x smin %y) to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
+; CHECK-NEXT:    --> ((sext i32 %x to i64) smin (sext i32 %y to i64)) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
 ; CHECK-NEXT:    %sext_x = sext i32 %x to i64
 ; CHECK-NEXT:    --> (sext i32 %x to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
 ; CHECK-NEXT:    %sext_y = sext i32 %y to i64
 ; CHECK-NEXT:    --> (sext i32 %y to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
 ; CHECK-NEXT:    %smin_sext_x_sext_y = select i1 %cmp_sext_x_sext_y, i64 %sext_x, i64 %sext_y
 ; CHECK-NEXT:    --> ((sext i32 %x to i64) smin (sext i32 %y to i64)) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
 ; CHECK-NEXT:  Determining loop execution counts for: @test_smin
 ;
   %cmp_x_y = icmp slt i32 %x, %y
   %smin_x_y = select i1 %cmp_x_y, i32 %x, i32 %y
   %sext_smin_x_y = sext i32 %smin_x_y to i64
 
   %sext_x = sext i32 %x to i64
   %sext_y = sext i32 %y to i64
   %cmp_sext_x_sext_y = icmp slt i64 %sext_x, %sext_y
   %smin_sext_x_sext_y = select i1 %cmp_sext_x_sext_y, i64 %sext_x, i64 %sext_y
 
   %they_are_same = icmp eq i64 %sext_smin_x_y, %smin_sext_x_sext_y
   ret i1 %they_are_same
 }
 
-; TODO: Make sure that sext(smax(x, y)) has same SCEV as smax(sext(x), sext(y)).
+; Make sure that sext(smax(x, y)) has same SCEV as smax(sext(x), sext(y)).
 ; Equality proof: https://alive2.llvm.org/ce/z/uou_u-
 define i1 @test_smax(i32 %x, i32 %y) {
 ; CHECK-LABEL: 'test_smax'
 ; CHECK-NEXT:  Classifying expressions for: @test_smax
 ; CHECK-NEXT:    %smax_x_y = select i1 %cmp_x_y, i32 %y, i32 %x
 ; CHECK-NEXT:    --> (%x smax %y) U: full-set S: full-set
 ; CHECK-NEXT:    %sext_smax_x_y = sext i32 %smax_x_y to i64
-; CHECK-NEXT:    --> (sext i32 (%x smax %y) to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
+; CHECK-NEXT:    --> ((sext i32 %x to i64) smax (sext i32 %y to i64)) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
 ; CHECK-NEXT:    %sext_x = sext i32 %x to i64
 ; CHECK-NEXT:    --> (sext i32 %x to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
 ; CHECK-NEXT:    %sext_y = sext i32 %y to i64
 ; CHECK-NEXT:    --> (sext i32 %y to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
 ; CHECK-NEXT:    %smax_sext_x_sext_y = select i1 %cmp_sext_x_sext_y, i64 %sext_y, i64 %sext_x
 ; CHECK-NEXT:    --> ((sext i32 %x to i64) smax (sext i32 %y to i64)) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
 ; CHECK-NEXT:  Determining loop execution counts for: @test_smax
 ;
   %cmp_x_y = icmp slt i32 %x, %y
   %smax_x_y = select i1 %cmp_x_y, i32 %y, i32 %x
   %sext_smax_x_y = sext i32 %smax_x_y to i64
 
   %sext_x = sext i32 %x to i64
   %sext_y = sext i32 %y to i64
   %cmp_sext_x_sext_y = icmp slt i64 %sext_x, %sext_y
   %smax_sext_x_sext_y = select i1 %cmp_sext_x_sext_y, i64 %sext_y, i64 %sext_x
 
   %they_are_same = icmp eq i64 %sext_smax_x_y, %smax_sext_x_sext_y
   ret i1 %they_are_same
 }
 
-; TODO: Make sure that zext(umin_seq(x, y)) has same SCEV as umin_seq(zext(x), zext(y)).
+; Make sure that zext(umin_seq(x, y)) has same SCEV as umin_seq(zext(x), zext(y)).
 ; Equality proof: https://alive2.llvm.org/ce/z/X8kaNx
 define i1 @test_umin_seq(i1 %x, i1 %y) {
 ; CHECK-LABEL: 'test_umin_seq'
 ; CHECK-NEXT:  Classifying expressions for: @test_umin_seq
 ; CHECK-NEXT:    %x_umin_seq_y = select i1 %x, i1 %y, i1 false
 ; CHECK-NEXT:    --> (%x umin_seq %y) U: full-set S: full-set
 ; CHECK-NEXT:    %zext_x_umin_seq_y = zext i1 %x_umin_seq_y to i64
-; CHECK-NEXT:    --> (zext i1 (%x umin_seq %y) to i64) U: [0,2) S: [0,2)
+; CHECK-NEXT:    --> ((zext i1 %x to i64) umin_seq (zext i1 %y to i64)) U: [0,2) S: [0,2)
 ; CHECK-NEXT:    %zext_x = zext i1 %x to i64
 ; CHECK-NEXT:    --> (zext i1 %x to i64) U: [0,2) S: [0,2)
 ; CHECK-NEXT:    %zext_y = zext i1 %y to i64
 ; CHECK-NEXT:    --> (zext i1 %y to i64) U: [0,2) S: [0,2)
 ; CHECK-NEXT:    %umin_zext_x_zext_y = select i1 %cmp_zext_x_zext_y, i64 %zext_x, i64 %zext_y
 ; CHECK-NEXT:    --> ((zext i1 %x to i64) umin (zext i1 %y to i64)) U: [0,2) S: [0,2)
 ; CHECK-NEXT:    %umin_seq_zext_x_xext_y = select i1 %zext_x_is_0, i64 0, i64 %umin_zext_x_zext_y
 ; CHECK-NEXT:    --> ((zext i1 %x to i64) umin_seq (zext i1 %y to i64)) U: [0,2) S: [0,2)

llvm/test/Analysis/ScalarEvolution/fold.ll

 ; CHECK-NEXT:    --> ({0,+,1}<%loop> umax ((zext i2 (trunc i32 %y to i2) to i32) smax {0,+,1}<%loop>)) U: [0,21) S: [0,21) Exits: 20 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %B = trunc i32 %Z2 to i16
 ; CHECK-NEXT:    --> (trunc i32 ({0,+,1}<%loop> umax ((zext i2 (trunc i32 %y to i2) to i32) smax {0,+,1}<%loop>)) to i16) U: [0,21) S: [0,21) Exits: 20 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %C = sext i16 %B to i30
 ; CHECK-NEXT:    --> (trunc i32 ({0,+,1}<%loop> umax ((zext i2 (trunc i32 %y to i2) to i32) smax {0,+,1}<%loop>)) to i30) U: [0,21) S: [0,21) Exits: 20 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %D = sext i16 %B to i32
 ; CHECK-NEXT:    --> ({0,+,1}<%loop> umax ((zext i2 (trunc i32 %y to i2) to i32) smax {0,+,1}<%loop>)) U: [0,21) S: [0,21) Exits: 20 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %E = sext i16 %B to i34
-; CHECK-NEXT:    --> (zext i32 ({0,+,1}<%loop> umax ((zext i2 (trunc i32 %y to i2) to i32) smax {0,+,1}<%loop>)) to i34) U: [0,21) S: [0,21) Exits: 20 LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> ((zext i32 ((zext i2 (trunc i32 %y to i2) to i32) smax {0,+,1}<nuw><nsw><%loop>) to i34) umax {0,+,1}<nuw><nsw><%loop>) U: [0,21) S: [0,21) Exits: 20 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %F = zext i16 %B to i30
-; CHECK-NEXT:    --> (trunc i32 ({0,+,1}<%loop> umax ((zext i2 (trunc i32 %y to i2) to i32) smax {0,+,1}<%loop>)) to i30) U: [0,21) S: [0,21) Exits: 20 LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> (trunc i32 ({0,+,1}<nuw><nsw><%loop> umax ((zext i2 (trunc i32 %y to i2) to i32) smax {0,+,1}<nuw><nsw><%loop>)) to i30) U: [0,21) S: [0,21) Exits: 20 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %G = zext i16 %B to i32
-; CHECK-NEXT:    --> ({0,+,1}<%loop> umax ((zext i2 (trunc i32 %y to i2) to i32) smax {0,+,1}<%loop>)) U: [0,21) S: [0,21) Exits: 20 LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> ({0,+,1}<nuw><nsw><%loop> umax ((zext i2 (trunc i32 %y to i2) to i32) smax {0,+,1}<nuw><nsw><%loop>)) U: [0,21) S: [0,21) Exits: 20 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %H = zext i16 %B to i34
-; CHECK-NEXT:    --> (zext i32 ({0,+,1}<%loop> umax ((zext i2 (trunc i32 %y to i2) to i32) smax {0,+,1}<%loop>)) to i34) U: [0,21) S: [0,21) Exits: 20 LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> ((zext i32 ((zext i2 (trunc i32 %y to i2) to i32) smax {0,+,1}<nuw><nsw><%loop>) to i34) umax {0,+,1}<nuw><nsw><%loop>) U: [0,21) S: [0,21) Exits: 20 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %I = add i32 %A, 1
-; CHECK-NEXT:    --> {1,+,1}<%loop> U: [1,22) S: [1,22) Exits: 21 LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,22) S: [1,22) Exits: 21 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test4
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 20
 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 20
 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 20
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 20
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 21
 ;

llvm/test/Analysis/ScalarEvolution/logical-operations.ll

 }
 
 define i32 @umin_seq_x_y_zext_of_umin(i8 %x, i8 %y) {
 ; CHECK-LABEL: 'umin_seq_x_y_zext_of_umin'
 ; CHECK-NEXT:  Classifying expressions for: @umin_seq_x_y_zext_of_umin
 ; CHECK-NEXT:    %umin.narrow = call i8 @llvm.umin.i8(i8 %y, i8 %x)
 ; CHECK-NEXT:    --> (%x umin %y) U: full-set S: full-set
 ; CHECK-NEXT:    %umin = zext i8 %umin.narrow to i32
-; CHECK-NEXT:    --> (zext i8 (%x umin %y) to i32) U: [0,256) S: [0,256)
+; CHECK-NEXT:    --> ((zext i8 %x to i32) umin (zext i8 %y to i32)) U: [0,256) S: [0,256)
 ; CHECK-NEXT:    %r = select i1 %x.is.zero, i32 0, i32 %umin
-; CHECK-NEXT:    --> ((zext i8 %x to i32) umin_seq (zext i8 (%x umin %y) to i32)) U: [0,256) S: [0,256)
+; CHECK-NEXT:    --> ((zext i8 %x to i32) umin_seq (zext i8 %y to i32)) U: [0,256) S: [0,256)
 ; CHECK-NEXT:  Determining loop execution counts for: @umin_seq_x_y_zext_of_umin
 ;
   %umin.narrow = call i8 @llvm.umin.i8(i8 %y, i8 %x)
   %umin = zext i8 %umin.narrow to i32
   %x.is.zero = icmp eq i8 %x, 0
   %r = select i1 %x.is.zero, i32 0, i32 %umin
   ret i32 %r
 }

llvm/test/Analysis/ScalarEvolution/max-backedge-taken-count-guard-info-rewrite-expressions.ll

loop:
   %ec = icmp eq i64 %index.next, %n.vec
   br i1 %ec, label %exit, label %loop
 
 exit:
   ret void
 }
 
 ; Test case from PR40961.
+; TODO: Loop %loop: constant max backedge-taken count is 3
 define i32 @rewrite_zext_min_max(i32 %N, ptr %arr) {
 ; CHECK-LABEL: 'rewrite_zext_min_max'
 ; CHECK-NEXT:  Classifying expressions for: @rewrite_zext_min_max
 ; CHECK-NEXT:    %umin = call i32 @llvm.umin.i32(i32 %N, i32 16)
 ; CHECK-NEXT:    --> (16 umin %N) U: [0,17) S: [0,17)
 ; CHECK-NEXT:    %ext = zext i32 %umin to i64
-; CHECK-NEXT:    --> (zext i32 (16 umin %N) to i64) U: [0,17) S: [0,17)
+; CHECK-NEXT:    --> (16 umin (zext i32 %N to i64)) U: [0,17) S: [0,17)
 ; CHECK-NEXT:    %n.vec = and i64 %ext, 28
-; CHECK-NEXT:    --> (4 * ((zext i32 (16 umin %N) to i64) /u 4))<nuw><nsw> U: [0,17) S: [0,17)
+; CHECK-NEXT:    --> (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw> U: [0,17) S: [0,17)
 ; CHECK-NEXT:    %index = phi i64 [ 0, %loop.ph ], [ %index.next, %loop ]
-; CHECK-NEXT:    --> {0,+,4}<nuw><%loop> U: [0,13) S: [0,13) Exits: (4 * ((-4 + (4 * ((zext i32 (16 umin %N) to i64) /u 4))<nuw><nsw>)<nsw> /u 4))<nuw> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {0,+,4}<nuw><%loop> U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4))<nuw> LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %gep = getelementptr inbounds i32, ptr %arr, i64 %index
-; CHECK-NEXT:    --> {%arr,+,16}<nuw><%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * ((zext i32 (16 umin %N) to i64) /u 4))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {%arr,+,16}<%loop> U: full-set S: full-set Exits: ((16 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)) + %arr) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %index.next = add nuw i64 %index, 4
-; CHECK-NEXT:    --> {4,+,4}<nuw><%loop> U: [4,17) S: [4,17) Exits: (4 + (4 * ((-4 + (4 * ((zext i32 (16 umin %N) to i64) /u 4))<nuw><nsw>)<nsw> /u 4))<nuw>) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {4,+,4}<nuw><%loop> U: [4,-3) S: [-9223372036854775808,9223372036854775805) Exits: (4 + (4 * ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4))<nuw>) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @rewrite_zext_min_max
-; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (4 * ((zext i32 (16 umin %N) to i64) /u 4))<nuw><nsw>)<nsw> /u 4)
-; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 3
-; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * ((zext i32 (16 umin %N) to i64) /u 4))<nuw><nsw>)<nsw> /u 4)
-; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-4 + (4 * ((zext i32 (16 umin %N) to i64) /u 4))<nuw><nsw>)<nsw> /u 4)
+; CHECK-NEXT:  Loop %loop: backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)
+; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 4611686018427387903
+; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((-4 + (4 * ((16 umin (zext i32 %N to i64)) /u 4))<nuw><nsw>)<nsw> /u 4)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;
 entry:
   %umin = call i32 @llvm.umin.i32(i32 %N, i32 16)
   %ext = zext i32 %umin to i64
   %min.iters.check = icmp ult i64 %ext, 4
   br i1 %min.iters.check, label %exit, label %loop.ph
loop:
   %index.next = add nuw i64 %index, 4
   %ec = icmp eq i64 %index.next, %n.vec
   br i1 %ec, label %exit, label %loop
 
 exit:
   ret i32 0
 }
 
 ; Test case from PR52464. applyLoopGuards needs to apply information about %and
 ; to %ext, which requires rewriting the zext.
 define i32 @rewrite_zext_with_info_from_icmp_ne(i32 %N) {
 ; CHECK-LABEL: 'rewrite_zext_with_info_from_icmp_ne'
 ; CHECK-NEXT:  Classifying expressions for: @rewrite_zext_with_info_from_icmp_ne
 ; CHECK-NEXT:    %and = and i32 %N, 3
 ; CHECK-NEXT:    --> (zext i2 (trunc i32 %N to i2) to i32) U: [0,4) S: [0,4)
 ; CHECK-NEXT:    %and.sub.1 = add nsw i32 %and, -1
 ; CHECK-NEXT:    --> (-1 + (zext i2 (trunc i32 %N to i2) to i32))<nsw> U: [-1,3) S: [-1,3)

llvm/test/Analysis/ScalarEvolution/ptrtoint.ll

 ; X64-NEXT:    --> ((ptrtoint ptr %in0 to i64) umax (ptrtoint ptr %in1 to i64)) U: full-set S: full-set
 ; X64-NEXT:  Determining loop execution counts for: @ptrtoint_of_umax
 ;
 ; X32-LABEL: 'ptrtoint_of_umax'
 ; X32-NEXT:  Classifying expressions for: @ptrtoint_of_umax
 ; X32-NEXT:    %s = select i1 %c, ptr %in0, ptr %in1
 ; X32-NEXT:    --> (%in0 umax %in1) U: full-set S: full-set
 ; X32-NEXT:    %p0 = ptrtoint ptr %s to i64
-; X32-NEXT:    --> (zext i32 ((ptrtoint ptr %in0 to i32) umax (ptrtoint ptr %in1 to i32)) to i64) U: [0,4294967296) S: [0,4294967296)
+; X32-NEXT:    --> ((zext i32 (ptrtoint ptr %in0 to i32) to i64) umax (zext i32 (ptrtoint ptr %in1 to i32) to i64)) U: [0,4294967296) S: [0,4294967296)
 ; X32-NEXT:  Determining loop execution counts for: @ptrtoint_of_umax
 ;
   %c = icmp uge ptr %in0, %in1
   %s = select i1 %c, ptr %in0, ptr %in1
   %p0 = ptrtoint ptr %s to i64
   store i64  %p0, ptr  %out0
   ret void
 }

 ; X64-NEXT:    --> ((ptrtoint ptr %in0 to i64) umin (ptrtoint ptr %in1 to i64)) U: full-set S: full-set
 ; X64-NEXT:  Determining loop execution counts for: @ptrtoint_of_umin
 ;
 ; X32-LABEL: 'ptrtoint_of_umin'
 ; X32-NEXT:  Classifying expressions for: @ptrtoint_of_umin
 ; X32-NEXT:    %s = select i1 %c, ptr %in0, ptr %in1
 ; X32-NEXT:    --> (%in0 umin %in1) U: full-set S: full-set
 ; X32-NEXT:    %p0 = ptrtoint ptr %s to i64
-; X32-NEXT:    --> (zext i32 ((ptrtoint ptr %in0 to i32) umin (ptrtoint ptr %in1 to i32)) to i64) U: [0,4294967296) S: [0,4294967296)
+; X32-NEXT:    --> ((zext i32 (ptrtoint ptr %in0 to i32) to i64) umin (zext i32 (ptrtoint ptr %in1 to i32) to i64)) U: [0,4294967296) S: [0,4294967296)
 ; X32-NEXT:  Determining loop execution counts for: @ptrtoint_of_umin
 ;
   %c = icmp ule ptr %in0, %in1
   %s = select i1 %c, ptr %in0, ptr %in1
   %p0 = ptrtoint ptr %s to i64
   store i64  %p0, ptr  %out0
   ret void
 }

llvm/test/Analysis/ScalarEvolution/range_nw_flag.ll

 ; CHECK-NEXT:    --> (-10 smin %offset) U: [-2147483648,-9) S: [-2147483648,-9)
 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 ; CHECK-NEXT:    --> {0,+,-1}<nsw><%loop> U: [-2147483648,1) S: [-2147483648,1) Exits: (1 + %numIterations) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %nexti = add nsw i32 %i, -1
 ; CHECK-NEXT:    --> {-1,+,-1}<nsw><%loop> U: [-2147483648,0) S: [-2147483648,0) Exits: %numIterations LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %index32 = add nsw i32 %nexti, %max
 ; CHECK-NEXT:    --> {(-1 + (-10 smin %offset))<nsw>,+,-1}<nsw><%loop> U: [-2147483648,-10) S: [-2147483648,-10) Exits: ((-10 smin %offset) + %numIterations) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %index32
-; CHECK-NEXT:    --> {(-4 + (4 * (sext i32 (-10 smin %offset) to i64))<nsw> + %input),+,-4}<nw><%loop> U: full-set S: full-set Exits: (-4 + (4 * (sext i32 (-10 smin %offset) to i64))<nsw> + (-4 * (zext i32 (-1 + (-1 * %numIterations)) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {(-4 + (4 * (-10 smin (sext i32 %offset to i64)))<nsw> + %input),+,-4}<nw><%loop> U: full-set S: full-set Exits: (-4 + (4 * (-10 smin (sext i32 %offset to i64)))<nsw> + (-4 * (zext i32 (-1 + (-1 * %numIterations)) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test-addrec-nsw-start-neg-strip-neg
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + (-1 * %numIterations))
 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is -1
 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %numIterations))
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (-1 + (-1 * %numIterations))
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;

 ; CHECK-NEXT:    --> (10 smin %offset) U: [-2147483648,11) S: [-2147483648,11)
 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 ; CHECK-NEXT:    --> {0,+,-1}<nsw><%loop> U: [-2147483648,1) S: [-2147483648,1) Exits: (1 + %numIterations) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %nexti = add nsw i32 %i, -1
 ; CHECK-NEXT:    --> {-1,+,-1}<nsw><%loop> U: [-2147483648,0) S: [-2147483648,0) Exits: %numIterations LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %index32 = add nsw i32 %nexti, %max
 ; CHECK-NEXT:    --> {(-1 + (10 smin %offset))<nsw>,+,-1}<nsw><%loop> U: [-2147483648,10) S: [-2147483648,10) Exits: ((10 smin %offset) + %numIterations) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %index32
-; CHECK-NEXT:    --> {(-4 + (4 * (sext i32 (10 smin %offset) to i64))<nsw> + %input),+,-4}<nw><%loop> U: full-set S: full-set Exits: (-4 + (4 * (sext i32 (10 smin %offset) to i64))<nsw> + (-4 * (zext i32 (-1 + (-1 * %numIterations)) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {(-4 + (4 * (10 smin (sext i32 %offset to i64)))<nsw> + %input),+,-4}<nw><%loop> U: full-set S: full-set Exits: (-4 + (4 * (10 smin (sext i32 %offset to i64)))<nsw> + (-4 * (zext i32 (-1 + (-1 * %numIterations)) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test-addrec-nsw-start-pos-strip-neg
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + (-1 * %numIterations))
 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is -1
 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + (-1 * %numIterations))
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (-1 + (-1 * %numIterations))
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;

 ; CHECK-NEXT:    --> (-10 smax %offset) U: [-10,-2147483648) S: [-10,-2147483648)
 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop ], [ 0, %entry ]
 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %index32 = add nsw i32 %nexti, %min
 ; CHECK-NEXT:    --> {(1 + (-10 smax %offset))<nsw>,+,1}<nsw><%loop> U: [-9,-2147483648) S: [-9,-2147483648) Exits: ((-10 smax %offset) + %numIterations) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, ptr %input, i32 %index32
-; CHECK-NEXT:    --> {(4 + (4 * (sext i32 (-10 smax %offset) to i64))<nsw> + %input),+,4}<nw><%loop> U: full-set S: full-set Exits: (4 + (4 * (zext i32 (-1 + %numIterations) to i64))<nuw><nsw> + (4 * (sext i32 (-10 smax %offset) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {(4 + (4 * (-10 smax (sext i32 %offset to i64)))<nsw> + %input),+,4}<nw><%loop> U: full-set S: full-set Exits: (4 + (4 * (zext i32 (-1 + %numIterations) to i64))<nuw><nsw> + (4 * (-10 smax (sext i32 %offset to i64)))<nsw> + %input) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test-addrec-nsw-start-neg-strip-pos
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is -1
 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is (-1 + %numIterations)
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (-1 + %numIterations)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;