[SCEV] More precise trip multiples

[caojoshua]

Summary

We currently have getMinTrailingZeros(), from which we can get a SCEV's
multiple by computing 1 << MinTrailingZeroes. However, this only gets us
multiples that are a power of 2. This patch introduces a way to get max
constant multiples that are not just a power of 2. The logic is similar
to that of getMinTrailingZeros. getMinTrailingZerosImpl is replaced by
computing the max constant multiple, and counting the number of trailing
bits.

I have so far found this useful in two places:

1. Computing unsigned constant ranges. For example, if we have i8 {10,+,10}<nuw>, we know the max constant it can be is 250.

2. My original intent was to use this in getSmallConstantTripMultiples, but it has no effect right now due to change from D110587. For example, if we have backedge count (6 * %N) - 1, the trip count becomes 1 + zext((6 * %N) - 1), and we cannot say that 6 is a multiple of the SCEV. I plan to look further into this separately.

The implementation assumes the value is unsigned. It can probably be
extended to handle signed values as well.

If the code sees that a SCEV does not have <nuw>, it will fall back to
finding the max multiple that is a power of 2. Multiples that are a
power of 2 will still be a multiple even after the SCEV overflows. This
does not apply to other values.

[caojoshua]

Small code updates

[caojoshua]

Move a code comment

[nikic]

Precommit tests please.

llvm/lib/Analysis/ScalarEvolution.cpp

6317

APInt::getOneBitSet

6321

I don't think this is correct. trunc(X nuw* C) is not, in general, the same as trunc(X) nuw* trunc(C).

6370

minimum

[caojoshua]

In D141823#4055951, @nikic wrote:

Precommit tests please.

What is precommit test? I've been running llvm-lit llvm/test

llvm/lib/Analysis/ScalarEvolution.cpp

6321

Thats a good point. Need to think about this. I think we can fall back to count min trailing zeros.

[nikic]

In D141823#4056673, @caojoshua wrote:

In D141823#4055951, @nikic wrote:

Precommit tests please.

What is precommit test? I've been running llvm-lit llvm/test

Commit the new tests with baseline checks (without your patch), and then rebase on top, so it only shows diffs.

[caojoshua]

• Fix typos
• Don't assume multiples hold through truncation, unless they are a power of 2
• only show diffs for updated test outputs

[caojoshua]

In D141823#4057047, @nikic wrote:

In D141823#4056673, @caojoshua wrote:

In D141823#4055951, @nikic wrote:

Precommit tests please.

What is precommit test? I've been running llvm-lit llvm/test

Commit the new tests with baseline checks (without your patch), and then rebase on top, so it only shows diffs.

Thanks. I've done this for the newest revision. I see why this is preferable, but unless I think I'm missing something, this should be included somewhere in LLVM docs i.e. https://llvm.org/docs/CodeReview.html or https://llvm.org/docs/TestingGuide.html.

I have another question. When patches get approved, should owners squash the commits before pushing? Or push two separate commits.

[caojoshua]

ping

[nikic]

In D141823#4057780, @caojoshua wrote:

In D141823#4057047, @nikic wrote:

In D141823#4056673, @caojoshua wrote:

In D141823#4055951, @nikic wrote:

Precommit tests please.

What is precommit test? I've been running llvm-lit llvm/test

Commit the new tests with baseline checks (without your patch), and then rebase on top, so it only shows diffs.

Thanks. I've done this for the newest revision. I see why this is preferable, but unless I think I'm missing something, this should be included somewhere in LLVM docs i.e. https://llvm.org/docs/CodeReview.html or https://llvm.org/docs/TestingGuide.html.

I've put up https://reviews.llvm.org/D142441 to update the TestingGuide.

I have another question. When patches get approved, should owners squash the commits before pushing? Or push two separate commits.

It should be two separate commits. In fact, you can just land the test commit now, without waiting for the patch to be approved.

I believe this patch needs a rebase, because of some recent refactorings.

My original intent was to use this in getSmallConstantTripMultiples, but it has no effect right now due to change from D110587. For example, if we have backedge count (6 * %N) - 1, the trip count becomes 1 + zext((6 * %N) - 1), and we cannot say that 6 is a multiple of the SCEV. I plan to look further into this separately.

I wonder if it might make sense to address this first? I'm a bit worried that the only test coverage for this functionality we have right now is very indirect, by the effect the multiple has on ranges. It would be great if we could test this functionality directly based on the trip multiple.

[nikic]

Logic looks about right to me.

When I tested the original patch, there was a significant impact on compile-time: http://llvm-compile-time-tracker.com/compare.php?from=68a534e9bf69e7e5f081a515e05f1d3cb4c21761&to=8f3c56e720e64e569f930190b246e4af61be2323&stat=instructions:u But I'm not sure if it's avoidable :(

llvm/include/llvm/Analysis/ScalarEvolution.h

961

than -> then

965

Missing doc comment.

llvm/lib/Analysis/ScalarEvolution.cpp

6306

Unnecessary reference

6336–6338

6345

Unnecessary braces

6363

6372

Or use the same operands().drop_front() style as above.

8266

So, is getRawData() here supposed to be an implicit truncate? Let's not do that...

[caojoshua]

I wonder if it might make sense to address this first? I'm a bit worried that the only test coverage for this functionality we have right now is very indirect, by the effect the multiple has on ranges. It would be great if we could test this functionality directly based on the trip multiple.

This does make sense. Let me try to get this working.

When I tested the original patch, there was a significant impact on compile-time: http://llvm-compile-time-tracker.com/compare.php?from=68a534e9bf69e7e5f081a515e05f1d3cb4c21761&to=8f3c56e720e64e569f930190b246e4af61be2323&stat=instructions:u But I'm not sure if it's avoidable :(

I was not expecting those numbers. Computing multiples is very similar to GetMinTrailingZeros. The main difference I can think of is that multiples uses GreatestCommonDivisor, but I don't think it should be too expensive, and in most cases it probably just returns 1. I'll look into this as well.

[mkazantsev]

I think this needs stronger test coverage. At least I want tests for all operations (either IR tests or unittests in CPP, whatever is easier) exercising corner case scenarios, such as bit width overflow with mul.

llvm/include/llvm/Analysis/ScalarEvolution.h

971

Separate NFC?

llvm/lib/Analysis/ScalarEvolution.cpp

6308

Why zero and not APInt::getOneBitSet(BitWidth, BitWidth - 1)? Zero is not even a power of 2, how to interpret that?

6312

/*param name/* nullptr

6365

Early bail if GCD has become 1? It won't get any better anyways.

[caojoshua]

In D141823#4092531, @mkazantsev wrote:

I think this needs stronger test coverage. At least I want tests for all operations (either IR tests or unittests in CPP, whatever is easier) exercising corner case scenarios, such as bit width overflow with mul.

Agree that more test coverage is needed here. I'd like to go with nikic's suggestion to figure out the issues with trip multiples first. I think that will make testing this much easier.

llvm/include/llvm/Analysis/ScalarEvolution.h

971

You're right. I'll take this out.

[mkazantsev]

Marking as "request changes" to shrink my review list, will take a look once comments are addressed.

[caojoshua]

• Big rebasing
• rename getMaxConstantMultiple -> getConstantMultiple
• Apply getConstantMultiple to getSmallConstantTripMultiple() with a lot of tests
• early bail loop if GCD of add SCEV is 1
• stylistic changes based on feedback

[caojoshua]

When I tested the original patch, there was a significant impact on compile-time: http://llvm-compile-time-tracker.com/compare.php?from=68a534e9bf69e7e5f081a515e05f1d3cb4c21761&to=8f3c56e720e64e569f930190b246e4af61be2323&stat=instructions:u But I'm not sure if it's avoidable :(

@nikic The patch is quite a bit different now. I followed the test suite guide and compared compilation of SingleSource, MultiSource, Bitcode, and MicroBenchmarks tests and saw no compile time differences. I think the source files might be too small to see significant difference. I'm also not sure how much these tests will stress SCEV, but I do see the MicroBenchmarks directory has vectorization and other tests, so at least those tests should test SCEV.

Any recommendations to further benchmark compile time? If you feel appropriate, could you run this patch through your compile time tracker?

[caojoshua]

Rename GetPowerOfTwo -> GetShiftedByZeros

[caojoshua]

llvm/lib/Analysis/ScalarEvolution.cpp

6308

I renamed it to GetShiftByZeros(). Happy for better suggestions.

getConstantMultiple needs to be able to return zero sometimes. For example, if we have SCEV 0 + 10<nuw>, the true constant multiple is 10. Since its an addition, we want to compute GCD(0, 10), instead of something like GCD(1<<31, 10). I use a constant in this example, but the logic that we need to return 0 applies to all cases.

[mkazantsev]

Whenever a new cache is introduced, it is highly recommended to add logic to ScalarEvoltion::verify for it to make sure it is sane. Can you please add that?

Yeah I see that it has existed before, but having a cache we don't verify is a potential point for bugs.

llvm/lib/Analysis/ScalarEvolution.cpp

6343

hasNoUnsignedWrap doesn't make sense for min/max. How about:

case scAddExpr:
case scAddRecExpr:
case scUMaxExpr:
  <handling for nuw>
  // fallthrough
case scUMaxExpr:
case scSMaxExpr:
case scUMinExpr:
case scSMinExpr:
case scSequentialUMinExpr:
  <common part>

?

6347

This might be overly conservative for mul. You can just take constant multiple of any operand, or even their product from all operands. I'm OK if it's not in this patch, but maybe you should consider this.

[mkazantsev]

Some style comments & request to see if smth is doable in verifier with this cache.

[caojoshua]

llvm/lib/Analysis/ScalarEvolution.cpp

6347

Maybe you missed this. There is a case scMulExpr above that takes the product if there is no unsigned wrap.

[caojoshua]

• Don't check for wrap flags for min/max SCEVs
• add validation to ScalarEvolution::verify()

[caojoshua]

Whenever a new cache is introduced, it is highly recommended to add logic to ScalarEvoltion::verify for it to make sure it is sane. Can you please add that?

I'm not sure what it means to be sane in this case. It makes sense for certain caches. For example, I see that verify() checks that Values that exist in ExprValueMap also exist in the reversed ValueExprMap. From what I can see, the current validations all expect some certain values to currently be in a cache, but this does not apply to ConstantMultipleCache.

For now, I added verification that the cached value is aligned with getConstantMultipleImpl(). It looks like the first verification of this kind. I'm not sure how useful it is, because getConstantMultipleImpl() makes calls to getConstantMultiple(), which retrieves from the cache. I also added -passes=verify<scalar-evolution> to two tests, since there are actually very few tests that do run verification.

[mkazantsev]

LG, thanks! It's better to have more verification than needed than less than needed. :) Bugs with corrupted caches are so annoying.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

6343

min/max are implicitly nuw/nsw. With the new code structure we will use only the trailing zeros for min/max, while using the GCD would be legal.

6383–6385

This should probably return const APInt &?

8264

Should be getZExtValue() instead of getRawData().

14319

Hm, can this end up modifying the map we're iterating?

[caojoshua]

llvm/lib/Analysis/ScalarEvolution.cpp

14319

I think its possible. I'm going to revert this change and investigate later. Looks like buildbot is failing 027a4c8b96c7f97df8e98b1dac069b956810ab94.

[caojoshua]

Bad link in previous comment. Buildbot failing link is https://lab.llvm.org/buildbot/#/builders/16/builds/47038

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

14319

SE2 is a different entity, so how could it?

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

14319

Oh yeah, good point. I missed that this is on SE2.

[caojoshua]

llvm/lib/Analysis/ScalarEvolution.cpp

6383–6385

The APInts are local variables. Can't return reference.

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
 
   /// Called when the client has changed the disposition of values in
   /// a loop or block.
   ///
   /// We don't have a way to invalidate per-loop/per-block dispositions. Clear
   /// and recompute is simpler.
   void forgetBlockAndLoopDispositions(Value *V = nullptr);
 
+  /// Determine the maximum constant multiple C such that `S % C == 0`. This
+  /// assumes that S is an unsigned SCEV. If S does not guarentee no unsigned
+  /// wrap, then we compute the max multiple such that the multiple is a power
+  /// of 2. Multiples that are powers of 2 will still divide S even if S wraps.
+  ///
+  /// If S is a multiple of 0, than any integer is a multiple of S. We return 0
+  /// in this case.
+  APInt getMaxConstantMultiple(const SCEV *S);
+
+  APInt getMaxNonZeroConstantMultiple(const SCEV *S);
+
   /// Determine the minimum number of zero bits that S is guaranteed to end in
   /// (at every loop iteration).  It is, at the same time, the minimum number
   /// of times S is divisible by 2.  For example, given {4,+,8} it returns 2.
   /// If S is guaranteed to be 0, it returns the bitwidth of S.
-  uint32_t GetMinTrailingZeros(const SCEV *S);
+  uint32_t getMinTrailingZeros(const SCEV *S);
 
   /// Determine the unsigned range for a particular SCEV.
   /// NOTE: This returns a copy of the reference returned by getRangeRef.
   ConstantRange getUnsignedRange(const SCEV *S) {
     return getRangeRef(S, HINT_RANGE_UNSIGNED);
   }
 
   /// Determine the min of the unsigned range for a particular SCEV.
private:
   /// Set to true by isLoopBackedgeGuardedByCond when we're walking the set of
   /// conditions dominating the backedge of a loop.
   bool WalkingBEDominatingConds = false;
 
   /// Set to true by isKnownPredicateViaSplitting when we're trying to prove a
   /// predicate by splitting it into a set of independent predicates.
   bool ProvingSplitPredicate = false;
 
-  /// Memoized values for the GetMinTrailingZeros
-  DenseMap<const SCEV *, uint32_t> MinTrailingZerosCache;
+  /// Memoized values for the GetMaxConstantTripMultiple
+  DenseMap<const SCEV *, APInt> MaxConstantTripMultipleCache;
 
   /// Return the Value set from which the SCEV expr is generated.
   ArrayRef<Value *> getSCEVValues(const SCEV *S);
 
-  /// Private helper method for the GetMinTrailingZeros method
-  uint32_t GetMinTrailingZerosImpl(const SCEV *S);
+  /// Private helper method for the GetMaxConstantTripMultiple method
+  APInt getMaxConstantMultipleImpl(const SCEV *S);
 
   /// Information about the number of loop iterations for which a loop exit's
   /// branch condition evaluates to the not-taken path.  This is a temporary
   /// pair of exact and max expressions that are eventually summarized in
   /// ExitNotTakenInfo and BackedgeTakenInfo.
   struct ExitLimit {
     const SCEV *ExactNotTaken; // The exit is not taken exactly this many times
     const SCEV *ConstantMaxNotTaken; // The exit is not taken at most this many

llvm/lib/Analysis/ScalarEvolution.cpp

const SCEV *ScalarEvolution::getTruncateExpr(const SCEV *Op, Type *Ty,
   if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(Op)) {
     SmallVector<const SCEV *, 4> Operands;
     for (const SCEV *Op : AddRec->operands())
       Operands.push_back(getTruncateExpr(Op, Ty, Depth + 1));
     return getAddRecExpr(Operands, AddRec->getLoop(), SCEV::FlagAnyWrap);
   }
 
   // Return zero if truncating to known zeros.
-  uint32_t MinTrailingZeros = GetMinTrailingZeros(Op);
+  uint32_t MinTrailingZeros = getMinTrailingZeros(Op);
   if (MinTrailingZeros >= getTypeSizeInBits(Ty))
     return getZero(Ty);
 
   // The cast wasn't folded; create an explicit cast node. We can reuse
   // the existing insert position since if we get here, we won't have
   // made any changes which would invalidate it.
   SCEV *S = new (SCEVAllocator) SCEVTruncateExpr(ID.Intern(SCEVAllocator),
                                                  Op, Ty);

 static APInt extractConstantWithoutWrapping(ScalarEvolution &SE,
                                             const SCEVConstant *ConstantTerm,
                                             const SCEVAddExpr *WholeAddExpr) {
   const APInt &C = ConstantTerm->getAPInt();
   const unsigned BitWidth = C.getBitWidth();
   // Find number of trailing zeros of (x + y + ...) w/o the C first:
   uint32_t TZ = BitWidth;
   for (unsigned I = 1, E = WholeAddExpr->getNumOperands(); I < E && TZ; ++I)
-    TZ = std::min(TZ, SE.GetMinTrailingZeros(WholeAddExpr->getOperand(I)));
+    TZ = std::min(TZ, SE.getMinTrailingZeros(WholeAddExpr->getOperand(I)));
   if (TZ) {
     // Set D to be as many least significant bits of C as possible while still
     // guaranteeing that adding D to (C - D + x + y + ...) won't cause a wrap:
     return TZ < BitWidth ? C.trunc(TZ).zext(BitWidth) : C;
   }
   return APInt(BitWidth, 0);
 }
 
 // Finds an integer D for an affine AddRec expression {C,+,x} such that the top
 // level addition in (D + {C-D,+,x}) would not wrap (signed or unsigned) and the
 // number of trailing zeros of (C - D + x * n) is maximized, where C is the \p
 // ConstantStart, x is an arbitrary \p Step, and n is the loop trip count.
 static APInt extractConstantWithoutWrapping(ScalarEvolution &SE,
                                             const APInt &ConstantStart,
                                             const SCEV *Step) {
   const unsigned BitWidth = ConstantStart.getBitWidth();
-  const uint32_t TZ = SE.GetMinTrailingZeros(Step);
+  const uint32_t TZ = SE.getMinTrailingZeros(Step);
   if (TZ)
     return TZ < BitWidth ? ConstantStart.trunc(TZ).zext(BitWidth)
                          : ConstantStart;
   return APInt(BitWidth, 0);
 }
 
 static void insertFoldCacheEntry(
     const ScalarEvolution::FoldID &ID, const SCEV *S,
assert(GEP->getSourceElementType()->isSized() &&
          "GEP source element type must be sized");
 
   SmallVector<const SCEV *, 4> IndexExprs;
   for (Value *Index : GEP->indices())
     IndexExprs.push_back(getSCEV(Index));
   return getGEPExpr(GEP, IndexExprs);
 }
 
-uint32_t ScalarEvolution::GetMinTrailingZerosImpl(const SCEV *S) {
-  if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
-    return C->getAPInt().countTrailingZeros();
-
-  if (const SCEVPtrToIntExpr *I = dyn_cast<SCEVPtrToIntExpr>(S))
-    return GetMinTrailingZeros(I->getOperand());
+APInt ScalarEvolution::getMaxConstantMultipleImpl(const SCEV *S) {
+  uint64_t BitWidth = getTypeSizeInBits(S->getType());
+  switch (S->getSCEVType()) {
+  case scConstant:
+    return cast<SCEVConstant>(S)->getAPInt();
+  case scUnknown: {
+    const SCEVUnknown *U = cast<SCEVUnknown>(S);
+    // For a SCEVUnknown, ask ValueTracking for known bits.
+    KnownBits Known =
+        computeKnownBits(U->getValue(), getDataLayout(), 0, &AC, nullptr, &DT);
+    return APInt(BitWidth, (uint64_t)1 << Known.countMinTrailingZeros());
+  }
+  case scPtrToInt:
+    return getMaxConstantMultiple(cast<SCEVPtrToIntExpr>(S)->getOperand());
+  case scTruncate: {
+    const SCEVTruncateExpr *T = cast<SCEVTruncateExpr>(S);
+    return getMaxConstantMultiple(T->getOperand()).trunc(BitWidth);
+  }
+  case scZeroExtend: {
+    const SCEVZeroExtendExpr *Z = cast<SCEVZeroExtendExpr>(S);
+    return getMaxConstantMultiple(Z->getOperand()).zext(BitWidth);
+  }
+  case scSignExtend: {
+    const SCEVSignExtendExpr *E = cast<SCEVSignExtendExpr>(S);
+    return getMaxConstantMultiple(E->getOperand()).sext(BitWidth);
+  }
 
-  if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S))
-    return std::min(GetMinTrailingZeros(T->getOperand()),
-                    (uint32_t)getTypeSizeInBits(T->getType()));
-
-  if (const SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) {
-    uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
-    return OpRes == getTypeSizeInBits(E->getOperand()->getType())
-               ? getTypeSizeInBits(E->getType())
-               : OpRes;
-  }
-
-  if (const SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S)) {
-    uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
-    return OpRes == getTypeSizeInBits(E->getOperand()->getType())
-               ? getTypeSizeInBits(E->getType())
-               : OpRes;
-  }
-
-  if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
-    // The result is the sum of all operands results.
-    uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0));
-    uint32_t BitWidth = getTypeSizeInBits(M->getType());
-    for (unsigned i = 1, e = M->getNumOperands();
-         SumOpRes != BitWidth && i != e; ++i)
-      SumOpRes =
-          std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i)), BitWidth);
-    return SumOpRes;
-  }
-
-  if (isa<SCEVAddExpr>(S) || isa<SCEVAddRecExpr>(S) || isa<SCEVMinMaxExpr>(S) ||
-      isa<SCEVSequentialMinMaxExpr>(S)) {
-    // The result is the min of all operands results.
-    const SCEVNAryExpr *M = cast<SCEVNAryExpr>(S);
-    uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
-    for (unsigned I = 1, E = M->getNumOperands(); MinOpRes && I != E; ++I)
-      MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(I)));
-    return MinOpRes;
+  case scMulExpr: {
+    const SCEVMulExpr *M = cast<SCEVMulExpr>(S);
+    if (M->hasNoUnsignedWrap()) {
+      // The result is the product of all operand results.
+      APInt Res = APInt(BitWidth, 1);
+      for (unsigned I = 0, E = M->getNumOperands(); I != E; ++I)
+        Res = Res * getMaxConstantMultiple(M->getOperand(I));
+      return Res;
+    }
+
+    // If there are no wrap guarentees, find the trailing zeros, which is the
+    // sum of trailing zeros for all its operands. power of 2.
+    uint32_t TZ = 0;
+    for (const SCEV *Operand : M->operands()) {
+      TZ += getMinTrailingZeros(Operand);
+    }
+    return TZ > BitWidth ? APInt::getZero(BitWidth)
+                         : APInt(BitWidth, 1).shl(TZ);
   }
 
-  if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
-    // For a SCEVUnknown, ask ValueTracking.
-    KnownBits Known = computeKnownBits(U->getValue(), getDataLayout(), 0, &AC, nullptr, &DT);
-    return Known.countMinTrailingZeros();
+  case scAddExpr:
+  case scAddRecExpr:
+  case scUMinExpr:
+  case scUMaxExpr:
+  case scSMinExpr:
+  case scSMaxExpr:
+  case scSequentialUMinExpr: {
+    // The result is GCD of all operands results.
+    const SCEVNAryExpr *N = cast<SCEVNAryExpr>(S);
+    if (N->hasNoUnsignedWrap()) {
+      APInt Res = getMaxConstantMultiple(N->getOperand(0));
+      for (const SCEV *Operand : N->operands())
+        Res = APIntOps::GreatestCommonDivisor(Res,
+                                              getMaxConstantMultiple(Operand));
+      return Res;
+    }
+
+    // If there are no wrap guarantees, find the trailing bits, which is the
+    // miminum of its operands.
+    uint32_t TZ = getMinTrailingZeros(N->getOperand(0));
+    for (int I = 0, E = N->getNumOperands(); I != E && TZ; ++I)
+      TZ = std::min(TZ, getMinTrailingZeros(N->getOperand(I)));
+    return TZ > BitWidth ? APInt::getZero(BitWidth)
+                         : APInt(BitWidth, 1).shl(TZ);
   }
 
-  // SCEVUDivExpr
-  return 0;
+  default:
+    return APInt(BitWidth, 1);
+  }
 }
 
-uint32_t ScalarEvolution::GetMinTrailingZeros(const SCEV *S) {
-  auto I = MinTrailingZerosCache.find(S);
-  if (I != MinTrailingZerosCache.end())
+APInt ScalarEvolution::getMaxConstantMultiple(const SCEV *S) {
+  auto I = MaxConstantTripMultipleCache.find(S);
+  if (I != MaxConstantTripMultipleCache.end())
     return I->second;
 
-  uint32_t Result = GetMinTrailingZerosImpl(S);
-  auto InsertPair = MinTrailingZerosCache.insert({S, Result});
+  APInt Multiple = getMaxConstantMultipleImpl(S);
+  auto InsertPair = MaxConstantTripMultipleCache.insert({S, Multiple});
   assert(InsertPair.second && "Should insert a new key");
-  return InsertPair.first->second;
+  return Multiple;
+}
+
+APInt ScalarEvolution::getMaxNonZeroConstantMultiple(const SCEV *S) {
+  return APIntOps::umax(getMaxConstantMultiple(S),
+                        APInt(getTypeSizeInBits(S->getType()), 1));
+}
+
+uint32_t ScalarEvolution::getMinTrailingZeros(const SCEV *S) {
+  return std::min(getMaxConstantMultiple(S).countTrailingZeros(),
+                  (unsigned)getTypeSizeInBits(S->getType()));
 }
 
 /// Helper method to assign a range to V from metadata present in the IR.
 static std::optional<ConstantRange> GetRangeFromMetadata(Value *V) {
   if (Instruction *I = dyn_cast<Instruction>(V))
     if (MDNode *MD = I->getMetadata(LLVMContext::MD_range))
       return getConstantRangeFromMetadata(*MD);
 
const ConstantRange &ScalarEvolution::getRangeRef(
   // nested expression.
   if (Depth > RangeIterThreshold)
     return getRangeRefIter(S, SignHint);
 
   unsigned BitWidth = getTypeSizeInBits(S->getType());
   ConstantRange ConservativeResult(BitWidth, /*isFullSet=*/true);
   using OBO = OverflowingBinaryOperator;
 
-  // If the value has known zeros, the maximum value will have those known zeros
-  // as well.
-  uint32_t TZ = GetMinTrailingZeros(S);
-  if (TZ != 0) {
-    if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED)
+  // The largest possible value is `Max - (Max % Multiple)`.
+  if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
+    APInt MaxMultiple = getMaxNonZeroConstantMultiple(S);
+    APInt Remainder = APInt::getMaxValue(BitWidth).urem(MaxMultiple);
+    if (!Remainder.isZero()) {
       ConservativeResult =
           ConstantRange(APInt::getMinValue(BitWidth),
-                        APInt::getMaxValue(BitWidth).lshr(TZ).shl(TZ) + 1);
-    else
+                        APInt::getMaxValue(BitWidth) - Remainder + 1);
+    }
+  } else {
+    uint32_t TZ = getMinTrailingZeros(S);
+    if (TZ != 0)
       ConservativeResult = ConstantRange(
           APInt::getSignedMinValue(BitWidth),
           APInt::getSignedMaxValue(BitWidth).ashr(TZ).shl(TZ) + 1);
   }
 
   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
     ConstantRange X = getRangeRef(Add->getOperand(0), SignHint, Depth + 1);
     unsigned WrapType = OBO::AnyWrap;
unsigned ScalarEvolution::getSmallConstantTripMultiple(const Loop *L,
                                                        const SCEV *ExitCount) {
   if (ExitCount == getCouldNotCompute())
     return 1;
 
   // Get the trip count
   const SCEV *TCExpr = getTripCountFromExitCount(ExitCount);
 
   const SCEVConstant *TC = dyn_cast<SCEVConstant>(TCExpr);
-  if (!TC)
+  if (!TC) {
     // Attempt to factor more general cases. Returns the greatest power of
     // two divisor. If overflow happens, the trip count expression is still
     // divisible by the greatest power of 2 divisor returned.
-    return 1U << std::min((uint32_t)31,
-                          GetMinTrailingZeros(applyLoopGuards(TCExpr, L)));
+    APInt Multiple =
+        getMaxNonZeroConstantMultiple(applyLoopGuards(TCExpr, L));
+    if (*Multiple.getRawData() > UINT_MAX)
+      return 1U << std::min((uint32_t)1U << Multiple.countTrailingZeros(),
+                            (uint32_t)1);
+    return *Multiple.getRawData();
+  }
 
   ConstantInt *Result = TC->getValue();
 
   // Guard against huge trip counts (this requires checking
   // for zero to handle the case where the trip count == -1 and the
   // addition wraps).
   if (!Result || Result->getValue().getActiveBits() > 32 ||
       Result->getValue().getActiveBits() == 0)
void ScalarEvolution::forgetAllLoops() {
   ValuesAtScopes.clear();
   ValuesAtScopesUsers.clear();
   LoopDispositions.clear();
   BlockDispositions.clear();
   UnsignedRanges.clear();
   SignedRanges.clear();
   ExprValueMap.clear();
   HasRecMap.clear();
-  MinTrailingZerosCache.clear();
+  MaxConstantTripMultipleCache.clear();
   PredicatedSCEVRewrites.clear();
   FoldCache.clear();
   FoldCacheUser.clear();
 }
 
 void ScalarEvolution::forgetLoop(const Loop *L) {
   SmallVector<const Loop *, 16> LoopWorklist(1, L);
   SmallVector<Instruction *, 32> Worklist;
static const SCEV *SolveLinEquationWithOverflow(const APInt &A, const SCEV *B,
   // trailing zeros in A is its multiplicity
   uint32_t Mult2 = A.countTrailingZeros();
   // D = 2^Mult2
 
   // 2. Check if B is divisible by D.
   //
   // B is divisible by D if and only if the multiplicity of prime factor 2 for B
   // is not less than multiplicity of this prime factor for D.
-  if (SE.GetMinTrailingZeros(B) < Mult2)
+  if (SE.getMinTrailingZeros(B) < Mult2)
     return SE.getCouldNotCompute();
 
   // 3. Compute I: the multiplicative inverse of (A / D) in arithmetic
   // modulo (N / D).
   //
   // If D == 1, (N / D) == N == 2^BW, so we need one extra bit to represent
   // (N / D) in general. The inverse itself always fits into BW bits, though,
   // so we immediately truncate it.

 
 ScalarEvolution::ScalarEvolution(ScalarEvolution &&Arg)
     : F(Arg.F), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT),
       LI(Arg.LI), CouldNotCompute(std::move(Arg.CouldNotCompute)),
       ValueExprMap(std::move(Arg.ValueExprMap)),
       PendingLoopPredicates(std::move(Arg.PendingLoopPredicates)),
       PendingPhiRanges(std::move(Arg.PendingPhiRanges)),
       PendingMerges(std::move(Arg.PendingMerges)),
-      MinTrailingZerosCache(std::move(Arg.MinTrailingZerosCache)),
+      MaxConstantTripMultipleCache(std::move(Arg.MaxConstantTripMultipleCache)),
       BackedgeTakenCounts(std::move(Arg.BackedgeTakenCounts)),
       PredicatedBackedgeTakenCounts(
           std::move(Arg.PredicatedBackedgeTakenCounts)),
       BECountUsers(std::move(Arg.BECountUsers)),
       ConstantEvolutionLoopExitValue(
           std::move(Arg.ConstantEvolutionLoopExitValue)),
       ValuesAtScopes(std::move(Arg.ValuesAtScopes)),
       ValuesAtScopesUsers(std::move(Arg.ValuesAtScopesUsers)),

 }
 
 void ScalarEvolution::forgetMemoizedResultsImpl(const SCEV *S) {
   LoopDispositions.erase(S);
   BlockDispositions.erase(S);
   UnsignedRanges.erase(S);
   SignedRanges.erase(S);
   HasRecMap.erase(S);
-  MinTrailingZerosCache.erase(S);
+  MaxConstantTripMultipleCache.erase(S);
 
   if (auto *AR = dyn_cast<SCEVAddRecExpr>(S)) {
     UnsignedWrapViaInductionTried.erase(AR);
     SignedWrapViaInductionTried.erase(AR);
   }
 
   auto ExprIt = ExprValueMap.find(S);
   if (ExprIt != ExprValueMap.end()) {
for (auto &FoldID : IDs) {
                << *I->second << " != " << *Expr << "!\n";
         std::abort();
       }
     }
   }
 }
 
 bool ScalarEvolution::invalidate(
     Function &F, const PreservedAnalyses &PA,
     FunctionAnalysisManager::Invalidator &Inv) {
   // Invalidate the ScalarEvolution object whenever it isn't preserved or one
   // of its dependencies is invalidated.
   auto PAC = PA.getChecker<ScalarEvolutionAnalysis>();
   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
          Inv.invalidate<AssumptionAnalysis>(F, PA) ||
          Inv.invalidate<DominatorTreeAnalysis>(F, PA) ||
          Inv.invalidate<LoopAnalysis>(F, PA);

llvm/test/Analysis/ScalarEvolution/nsw.ll

 
 
 define void @bad_postinc_nsw_a(i32 %n) {
 ; CHECK-LABEL: 'bad_postinc_nsw_a'
 ; CHECK-NEXT:  Classifying expressions for: @bad_postinc_nsw_a
 ; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
 ; CHECK-NEXT:    --> {0,+,7}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (7 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 7) + (1 umin %n))) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.inc = add nsw i32 %iv, 7
-; CHECK-NEXT:    --> {7,+,7}<nuw><%loop> U: [7,0) S: [7,0) Exits: (7 + (7 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 7) + (1 umin %n)))) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {7,+,7}<nuw><%loop> U: [7,-3) S: [7,0) Exits: (7 + (7 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 7) + (1 umin %n)))) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @bad_postinc_nsw_a
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 7) + (1 umin %n))
 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 613566756
 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 7) + (1 umin %n))
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 7) + (1 umin %n))
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1
 ;

llvm/test/Analysis/ScalarEvolution/ranges.ll

 entry:
   br label %loop
 
 loop:
   %range.1 = phi i32 [ 0, %entry ], [ %shr, %loop ]
   %shr = lshr i32 %range.1, 1
   br label %loop
 }
+
+define void @add_1(i32 %n) {
+; CHECK-LABEL: 'add_1'
+; CHECK-NEXT:  Classifying expressions for: @add_1
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: %n LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.inc = add nsw i32 %iv, 1
+; CHECK-NEXT:    --> {1,+,1}<nuw><%loop> U: [1,0) S: [1,0) Exits: (1 + %n) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @add_1
+; CHECK-NEXT:  Loop %loop: backedge-taken count is %n
+; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is -1
+; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is %n
+; 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 ult i32 %iv, %n
+  br i1 %becond, label %loop, label %leave
+
+leave:
+  ret void
+}
+
+define void @add_2(i32 %n) {
+; CHECK-LABEL: 'add_2'
+; CHECK-NEXT:  Classifying expressions for: @add_2
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+; CHECK-NEXT:    --> {0,+,2}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,2147483647) Exits: (2 * ((1 + %n) /u 2))<nuw> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.inc = add nsw i32 %iv, 2
+; CHECK-NEXT:    --> {2,+,2}<nuw><%loop> U: [2,-1) S: [-2147483648,2147483647) Exits: (2 + (2 * ((1 + %n) /u 2))<nuw>) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @add_2
+; CHECK-NEXT:  Loop %loop: backedge-taken count is ((1 + %n) /u 2)
+; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 2147483647
+; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((1 + %n) /u 2)
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((1 + %n) /u 2)
+; 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, 2
+  %becond = icmp ult i32 %iv, %n
+  br i1 %becond, label %loop, label %leave
+
+leave:
+  ret void
+}
+define void @add_3(i32 %n) {
+; CHECK-LABEL: 'add_3'
+; CHECK-NEXT:  Classifying expressions for: @add_3
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+; CHECK-NEXT:    --> {0,+,3}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (3 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 3) + (1 umin %n))) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.inc = add nsw i32 %iv, 3
+; CHECK-NEXT:    --> {3,+,3}<nuw><%loop> U: [3,0) S: [3,0) Exits: (3 + (3 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 3) + (1 umin %n)))) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @add_3
+; CHECK-NEXT:  Loop %loop: backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 3) + (1 umin %n))
+; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 1431655765
+; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 3) + (1 umin %n))
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 3) + (1 umin %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, 3
+  %becond = icmp ult i32 %iv, %n
+  br i1 %becond, label %loop, label %leave
+
+leave:
+  ret void
+}
+define void @add_4(i32 %n) {
+; CHECK-LABEL: 'add_4'
+; CHECK-NEXT:  Classifying expressions for: @add_4
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+; CHECK-NEXT:    --> {0,+,4}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,2147483645) Exits: (4 * ((3 + %n) /u 4))<nuw> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.inc = add nsw i32 %iv, 4
+; CHECK-NEXT:    --> {4,+,4}<nuw><%loop> U: [4,-3) S: [-2147483648,2147483645) Exits: (4 + (4 * ((3 + %n) /u 4))<nuw>) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @add_4
+; CHECK-NEXT:  Loop %loop: backedge-taken count is ((3 + %n) /u 4)
+; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 1073741823
+; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((3 + %n) /u 4)
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((3 + %n) /u 4)
+; 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, 4
+  %becond = icmp ult i32 %iv, %n
+  br i1 %becond, label %loop, label %leave
+
+leave:
+  ret void
+}
+define void @add_5(i32 %n) {
+; CHECK-LABEL: 'add_5'
+; CHECK-NEXT:  Classifying expressions for: @add_5
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+; CHECK-NEXT:    --> {0,+,5}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (5 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 5) + (1 umin %n))) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.inc = add nsw i32 %iv, 5
+; CHECK-NEXT:    --> {5,+,5}<nuw><%loop> U: [5,0) S: [5,0) Exits: (5 + (5 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 5) + (1 umin %n)))) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @add_5
+; CHECK-NEXT:  Loop %loop: backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 5) + (1 umin %n))
+; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 858993459
+; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 5) + (1 umin %n))
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 5) + (1 umin %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, 5
+  %becond = icmp ult i32 %iv, %n
+  br i1 %becond, label %loop, label %leave
+
+leave:
+  ret void
+}
+define void @add_6(i32 %n) {
+; CHECK-LABEL: 'add_6'
+; CHECK-NEXT:  Classifying expressions for: @add_6
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+; CHECK-NEXT:    --> {0,+,6}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,2147483647) Exits: (6 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 6) + (1 umin %n))) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.inc = add nsw i32 %iv, 6
+; CHECK-NEXT:    --> {6,+,6}<nuw><%loop> U: [6,-3) S: [-2147483648,2147483647) Exits: (6 + (6 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 6) + (1 umin %n)))) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @add_6
+; CHECK-NEXT:  Loop %loop: backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 6) + (1 umin %n))
+; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 715827882
+; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 6) + (1 umin %n))
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 6) + (1 umin %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, 6
+  %becond = icmp ult i32 %iv, %n
+  br i1 %becond, label %loop, label %leave
+
+leave:
+  ret void
+}
+define void @add_7(i32 %n) {
+; CHECK-LABEL: 'add_7'
+; CHECK-NEXT:  Classifying expressions for: @add_7
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+; CHECK-NEXT:    --> {0,+,7}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (7 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 7) + (1 umin %n))) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.inc = add nsw i32 %iv, 7
+; CHECK-NEXT:    --> {7,+,7}<nuw><%loop> U: [7,-3) S: [7,0) Exits: (7 + (7 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 7) + (1 umin %n)))) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @add_7
+; CHECK-NEXT:  Loop %loop: backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 7) + (1 umin %n))
+; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 613566756
+; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 7) + (1 umin %n))
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 7) + (1 umin %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, 7
+  %becond = icmp ult i32 %iv, %n
+  br i1 %becond, label %loop, label %leave
+
+leave:
+  ret void
+}
+define void @add_8(i32 %n) {
+; CHECK-LABEL: 'add_8'
+; CHECK-NEXT:  Classifying expressions for: @add_8
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+; CHECK-NEXT:    --> {0,+,8}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,2147483641) Exits: (8 * ((7 + %n) /u 8))<nuw> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.inc = add nsw i32 %iv, 8
+; CHECK-NEXT:    --> {8,+,8}<nuw><%loop> U: [8,-7) S: [-2147483648,2147483641) Exits: (8 + (8 * ((7 + %n) /u 8))<nuw>) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @add_8
+; CHECK-NEXT:  Loop %loop: backedge-taken count is ((7 + %n) /u 8)
+; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 536870911
+; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((7 + %n) /u 8)
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((7 + %n) /u 8)
+; 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, 8
+  %becond = icmp ult i32 %iv, %n
+  br i1 %becond, label %loop, label %leave
+
+leave:
+  ret void
+}
+
+define void @add_9(i32 %n) {
+; CHECK-LABEL: 'add_9'
+; CHECK-NEXT:  Classifying expressions for: @add_9
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+; CHECK-NEXT:    --> {0,+,9}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (9 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 9) + (1 umin %n))) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.inc = add nsw i32 %iv, 9
+; CHECK-NEXT:    --> {9,+,9}<nuw><%loop> U: [9,-3) S: [9,0) Exits: (9 + (9 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 9) + (1 umin %n)))) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @add_9
+; CHECK-NEXT:  Loop %loop: backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 9) + (1 umin %n))
+; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 477218588
+; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 9) + (1 umin %n))
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 9) + (1 umin %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, 9
+  %becond = icmp ult i32 %iv, %n
+  br i1 %becond, label %loop, label %leave
+
+leave:
+  ret void
+}
+
+define void @add_10(i32 %n) {
+; CHECK-LABEL: 'add_10'
+; CHECK-NEXT:  Classifying expressions for: @add_10
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+; CHECK-NEXT:    --> {0,+,10}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,2147483647) Exits: (10 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 10) + (1 umin %n))) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.inc = add nsw i32 %iv, 10
+; CHECK-NEXT:    --> {10,+,10}<nuw><%loop> U: [10,-5) S: [-2147483648,2147483647) Exits: (10 + (10 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 10) + (1 umin %n)))) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @add_10
+; CHECK-NEXT:  Loop %loop: backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 10) + (1 umin %n))
+; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 429496729
+; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 10) + (1 umin %n))
+; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 10) + (1 umin %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, 10
+  %becond = icmp ult i32 %iv, %n
+  br i1 %becond, label %loop, label %leave
+
+leave:
+  ret void
+}
+
+define void @add_8_nowrap(i32 %n) {
+; CHECK-LABEL: 'add_8_nowrap'
+; CHECK-NEXT:  Classifying expressions for: @add_8_nowrap
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+; CHECK-NEXT:    --> {0,+,8}<%loop> U: [0,-7) S: [-2147483648,2147483641) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.inc = add i32 %iv, 8
+; CHECK-NEXT:    --> {8,+,8}<%loop> U: [0,-7) S: [-2147483648,2147483641) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @add_8_nowrap
+; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable symbolic 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 i32 %iv, 8
+  %becond = icmp ult i32 %iv, %n
+  br i1 %becond, label %loop, label %leave
+
+leave:
+  ret void
+}
+
+define void @add_10_nowrap(i32 %n) {
+; CHECK-LABEL: 'add_10_nowrap'
+; CHECK-NEXT:  Classifying expressions for: @add_10_nowrap
+; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.inc, %loop ]
+; CHECK-NEXT:    --> {0,+,10}<%loop> U: [0,-1) S: [-2147483648,2147483647) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    %iv.inc = add i32 %iv, 10
+; CHECK-NEXT:    --> {10,+,10}<%loop> U: [0,-1) S: [-2147483648,2147483647) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @add_10_nowrap
+; CHECK-NEXT:  Loop %loop: Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable constant max backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable symbolic 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 i32 %iv, 10
+  %becond = icmp ult i32 %iv, %n
+  br i1 %becond, label %loop, label %leave
+
+leave:
+  ret void
+}