[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

6315

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

6315

APInt::getOneBitSet

6379

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

6315

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

966

than -> then

970

Missing doc comment.

llvm/lib/Analysis/ScalarEvolution.cpp

6305

Unnecessary reference

6340–6342

6354

Unnecessary braces

6372

6381

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

8275

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

965

Separate NFC?

llvm/lib/Analysis/ScalarEvolution.cpp

6307

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

6310

/*param name/* nullptr

6374

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

965

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

6307

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

6352

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>

?

6356

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

6356

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

6352

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.

6372

This should probably return const APInt &?

8276

Should be getZExtValue() instead of getRawData().

14341

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

[caojoshua]

llvm/lib/Analysis/ScalarEvolution.cpp

14341

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

14341

SE2 is a different entity, so how could it?

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

14341

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

[caojoshua]

llvm/lib/Analysis/ScalarEvolution.cpp

6372

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

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   /// 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 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);
 
+  /// Returns the max constant multiple of S.
+  APInt getConstantMultiple(const SCEV *S);
+
+  // Returns the max constant multiple of S. If S is exactly 0, return 1.
+  APInt getNonZeroConstantMultiple(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.
   APInt getUnsignedRangeMin(const SCEV *S) {
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 getConstantMultiple
+  DenseMap<const SCEV *, APInt> ConstantMultipleCache;
 
   /// 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 getConstantMultiple method.
+  APInt getConstantMultipleImpl(const SCEV *S);
 
   /// Information about the number of times a particular loop exit may be
   /// reached before exiting the loop.
   struct ExitNotTakenInfo {
     PoisoningVH<BasicBlock> ExitingBlock;
     const SCEV *ExactNotTaken;
     const SCEV *ConstantMaxNotTaken;
     const SCEV *SymbolicMaxNotTaken;

llvm/lib/Analysis/ScalarEvolution.cpp

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) {
+APInt ScalarEvolution::getConstantMultipleImpl(const SCEV *S) {
+  uint64_t BitWidth = getTypeSizeInBits(S->getType());
+  auto GetShiftedByZeros = [BitWidth](uint32_t TrailingZeros) {
+    return TrailingZeros >= BitWidth
+               ? APInt::getZero(BitWidth)
+               : APInt::getOneBitSet(BitWidth, TrailingZeros);
+  };
+
   switch (S->getSCEVType()) {
   case scConstant:
-    return cast<SCEVConstant>(S)->getAPInt().countr_zero();
+    return cast<SCEVConstant>(S)->getAPInt();
+  case scPtrToInt:
+    return getConstantMultiple(cast<SCEVPtrToIntExpr>(S)->getOperand());
+  case scUDivExpr:
+  case scVScale:
+    return APInt(BitWidth, 1);
   case scTruncate: {
+    // Only multiples that are a power of 2 will hold after truncation.
     const SCEVTruncateExpr *T = cast<SCEVTruncateExpr>(S);
-    return std::min(getMinTrailingZeros(T->getOperand()),
-                    (uint32_t)getTypeSizeInBits(T->getType()));
+    uint32_t TZ = getMinTrailingZeros(T->getOperand());
+    return GetShiftedByZeros(TZ);
+  }
+  case scZeroExtend: {
+    const SCEVZeroExtendExpr *Z = cast<SCEVZeroExtendExpr>(S);
+    return getConstantMultiple(Z->getOperand()).zext(BitWidth);
   }
-  case scZeroExtend:
   case scSignExtend: {
-    const SCEVIntegralCastExpr *E = cast<SCEVIntegralCastExpr>(S);
-    uint32_t OpRes = getMinTrailingZeros(E->getOperand());
-    return OpRes == getTypeSizeInBits(E->getOperand()->getType())
-               ? getTypeSizeInBits(E->getType())
-               : OpRes;
+    const SCEVSignExtendExpr *E = cast<SCEVSignExtendExpr>(S);
+    return getConstantMultiple(E->getOperand()).sext(BitWidth);
   }
   case scMulExpr: {
     const SCEVMulExpr *M = 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 (M->hasNoUnsignedWrap()) {
+      // The result is the product of all operand results.
+      APInt Res = getConstantMultiple(M->getOperand(0));
+      for (const SCEV *Operand : M->operands().drop_front())
+        Res = Res * getConstantMultiple(Operand);
+      return Res;
+    }
+
+    // If there are no wrap guarentees, find the trailing zeros, which is the
+    // sum of trailing zeros for all its operands.
+    uint32_t TZ = 0;
+    for (const SCEV *Operand : M->operands())
+      TZ += getMinTrailingZeros(Operand);
+    return GetShiftedByZeros(TZ);
   }
-  case scVScale:
-    return 0;
-  case scUDivExpr:
-    return 0;
-  case scPtrToInt:
   case scAddExpr:
-  case scAddRecExpr:
+  case scAddRecExpr: {
+    const SCEVNAryExpr *N = cast<SCEVNAryExpr>(S);
+    if (N->hasNoUnsignedWrap()) {
+      // The result is GCD of all operands results.
+      APInt Res = getConstantMultiple(N->getOperand(0));
+      for (unsigned I = 1, E = N->getNumOperands(); I < E && Res != 1; ++I)
+        Res = APIntOps::GreatestCommonDivisor(
+            Res, getConstantMultiple(N->getOperand(I)));
+      return Res;
+    }
+  }
+    // If there is no unsigned wrap guarentees, fall through to find trailing
+    // bits.
+    LLVM_FALLTHROUGH;
   case scUMaxExpr:
   case scSMaxExpr:
   case scUMinExpr:
   case scSMinExpr:
   case scSequentialUMinExpr: {
-    // The result is the min of all operands results.
-    ArrayRef<const SCEV *> Ops = S->operands();
-    uint32_t MinOpRes = getMinTrailingZeros(Ops[0]);
-    for (unsigned I = 1, E = Ops.size(); MinOpRes && I != E; ++I)
-      MinOpRes = std::min(MinOpRes, getMinTrailingZeros(Ops[I]));
-    return MinOpRes;
+    const SCEVNAryExpr *N = cast<SCEVNAryExpr>(S);
+    // Find the trailing bits, which is the minimum of its operands.
+    uint32_t TZ = getMinTrailingZeros(N->getOperand(0));
+    for (const SCEV *Operand : N->operands().drop_front())
+      TZ = std::min(TZ, getMinTrailingZeros(Operand));
+    return GetShiftedByZeros(TZ);
   }
   case scUnknown: {
+    // ask ValueTracking for known bits
     const SCEVUnknown *U = cast<SCEVUnknown>(S);
-    // For a SCEVUnknown, ask ValueTracking.
-    KnownBits Known =
-        computeKnownBits(U->getValue(), getDataLayout(), 0, &AC, nullptr, &DT);
-    return Known.countMinTrailingZeros();
+    unsigned Known =
+        computeKnownBits(U->getValue(), getDataLayout(), 0, &AC, nullptr, &DT)
+            .countMinTrailingZeros();
+    return GetShiftedByZeros(Known);
   }
   case scCouldNotCompute:
     llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
   }
   llvm_unreachable("Unknown SCEV kind!");
 }
 
-uint32_t ScalarEvolution::getMinTrailingZeros(const SCEV *S) {
-  auto I = MinTrailingZerosCache.find(S);
-  if (I != MinTrailingZerosCache.end())
+APInt ScalarEvolution::getConstantMultiple(const SCEV *S) {
+  auto I = ConstantMultipleCache.find(S);
+  if (I != ConstantMultipleCache.end())
     return I->second;
 
-  uint32_t Result = getMinTrailingZerosImpl(S);
-  auto InsertPair = MinTrailingZerosCache.insert({S, Result});
+  APInt Result = getConstantMultipleImpl(S);
+  auto InsertPair = ConstantMultipleCache.insert({S, Result});
   assert(InsertPair.second && "Should insert a new key");
   return InsertPair.first->second;
 }
 
+APInt ScalarEvolution::getNonZeroConstantMultiple(const SCEV *S) {
+  APInt Multiple = getConstantMultiple(S);
+  return Multiple == 0 ? APInt(Multiple.getBitWidth(), 1) : Multiple;
+}
+
+uint32_t ScalarEvolution::getMinTrailingZeros(const SCEV *S) {
+  return std::min(getConstantMultiple(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);
 
   return std::nullopt;
 }
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)
+  if (SignHint == ScalarEvolution::HINT_RANGE_UNSIGNED) {
+    APInt Multiple = getNonZeroConstantMultiple(S);
+    APInt Remainder = APInt::getMaxValue(BitWidth).urem(Multiple);
+    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);
     }
+  }
 
   switch (S->getSCEVType()) {
   case scConstant:
     llvm_unreachable("Already handled above.");
   case scVScale:
     return setRange(S, SignHint, getVScaleRange(&F, BitWidth));
   case scTruncate: {
     const SCEVTruncateExpr *Trunc = cast<SCEVTruncateExpr>(S);
unsigned ScalarEvolution::getSmallConstantTripMultiple(const Loop *L,
 
   // If a trip multiple is huge (>=2^32), the trip count is still divisible by
   // the greatest power of 2 divisor less than 2^32.
   auto GetSmallMultiple = [](unsigned TrailingZeros) {
     return 1U << std::min((uint32_t)31, TrailingZeros);
   };
 
   const SCEVConstant *TC = dyn_cast<SCEVConstant>(TCExpr);
-  if (!TC)
-    // Attempt to factor more general cases. Returns the greatest power of
-    // two divisor.
-    return GetSmallMultiple(getMinTrailingZeros(TCExpr));
+  if (!TC) {
+    APInt Multiple = getNonZeroConstantMultiple(TCExpr);
+    return Multiple.getActiveBits() > 32 ? 1 : *Multiple.getRawData();
+  }
 
   ConstantInt *Result = TC->getValue();
   assert(Result && "SCEVConstant expected to have non-null ConstantInt");
   assert(Result->getValue() != 0 && "trip count should never be zero");
 
   // Guard against huge trip multiples.
   if (Result->getValue().getActiveBits() > 32)
     return GetSmallMultiple(Result->getValue().countTrailingZeros());
void ScalarEvolution::forgetAllLoops() {
   ValuesAtScopes.clear();
   ValuesAtScopesUsers.clear();
   LoopDispositions.clear();
   BlockDispositions.clear();
   UnsignedRanges.clear();
   SignedRanges.clear();
   ExprValueMap.clear();
   HasRecMap.clear();
-  MinTrailingZerosCache.clear();
+  ConstantMultipleCache.clear();
   PredicatedSCEVRewrites.clear();
   FoldCache.clear();
   FoldCacheUser.clear();
 }
 void ScalarEvolution::visitAndClearUsers(
     SmallVectorImpl<Instruction *> &Worklist,
     SmallPtrSetImpl<Instruction *> &Visited,
     SmallVectorImpl<const SCEV *> &ToForget) {

 
 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)),
+      ConstantMultipleCache(std::move(Arg.ConstantMultipleCache)),
       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);
+  ConstantMultipleCache.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) {
       }
       if (I->second != Expr) {
         dbgs() << "Entry in FoldCache doesn't match FoldCacheUser: "
                << *I->second << " != " << *Expr << "!\n";
         std::abort();
       }
     }
   }
+
+  // Verify that ConstantMultipleCache computations are correct.
+  for (auto [S, Multiple] : ConstantMultipleCache) {
+    APInt RecomputedMultiple = SE2.getConstantMultipleImpl(S);
+    if (Multiple != RecomputedMultiple) {
+      dbgs() << "Incorrect computation in ConstantMultipleCache for " << *S
+             << " : Expected " << RecomputedMultiple << " but got " << Multiple
+             << "!\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>();

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

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
- ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
- ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" -scev-range-iter-threshold=1 2>&1 | FileCheck %s
+ ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>,verify<scalar-evolution>" 2>&1 | FileCheck %s
+ ; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>,verify<scalar-evolution>" -scev-range-iter-threshold=1 2>&1 | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64"
 
 ; Collection of cases exercising range logic, mostly (but not exclusively)
 ; involving SCEVUnknowns.
 
 declare void @llvm.assume(i1)
 

 }
 
 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,-1) S: [-2147483648,2147483647) Exits: (6 + (6 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 6) + (1 umin %n)))) LoopDispositions: { %loop: Computable }
+; 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
 ;
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,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: @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
 ;

 }
 
 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,0) S: [9,0) Exits: (9 + (9 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 9) + (1 umin %n)))) LoopDispositions: { %loop: Computable }
+; 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
 ;

 }
 
 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,-1) S: [-2147483648,2147483647) Exits: (10 + (10 * ((((-1 * (1 umin %n))<nuw><nsw> + %n) /u 10) + (1 umin %n)))) LoopDispositions: { %loop: Computable }
+; 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
 ;

llvm/test/Analysis/ScalarEvolution/trip-multiple-guard-info.ll

 ; CHECK-NEXT:    %inc = add nuw nsw i32 %i.010, 1
 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%for.body> U: [1,-2147483648) S: [1,-2147483648) Exits: %num LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test_trip_multiple_5
 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -2
 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:   Predicates:
-; CHECK:       Loop %for.body: Trip multiple is 1
+; CHECK:       Loop %for.body: Trip multiple is 5
 ;
 entry:
   %u = urem i32 %num, 5
   %cmp = icmp eq i32 %u, 0
   tail call void @llvm.assume(i1 %cmp)
   %cmp.1 = icmp uge i32 %num, 5
   tail call void @llvm.assume(i1 %cmp.1)
   br label %for.body

llvm/test/Analysis/ScalarEvolution/trip-multiple.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
-; RUN: opt -passes='print<scalar-evolution>' -disable-output %s 2>&1 | FileCheck %s
+; RUN: opt -passes='print<scalar-evolution>,verify<scalar-evolution>' -disable-output %s 2>&1 | FileCheck %s
 
 ; Test trip multiples with functions that look like:
 
 ; void foo();
 ; void square(unsigned num) {
 ;     if (num % 5 == 0)
 ;     for (unsigned i = 0; i < num; ++i)
 ;         foo();

 ; CHECK-NEXT:    %inc = add nuw i32 %i.05, 1
 ; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,0) S: [1,0) Exits: %num LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @trip_multiple_3
 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -2
 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:   Predicates:
-; CHECK:       Loop %for.body: Trip multiple is 1
+; CHECK:       Loop %for.body: Trip multiple is 3
 ;
 entry:
   %rem = urem i32 %num, 3
   %cmp = icmp eq i32 %rem, 0
   %cmp14 = icmp ne i32 %num, 0
   %or.cond = and i1 %cmp, %cmp14
   br i1 %or.cond, label %for.body, label %if.end
 

 ; CHECK-NEXT:    %inc = add nuw i32 %i.05, 1
 ; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,0) S: [1,0) Exits: %num LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @trip_multiple_5
 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -2
 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:   Predicates:
-; CHECK:       Loop %for.body: Trip multiple is 1
+; CHECK:       Loop %for.body: Trip multiple is 5
 ;
 entry:
   %rem = urem i32 %num, 5
   %cmp = icmp eq i32 %rem, 0
   %cmp14 = icmp ne i32 %num, 0
   %or.cond = and i1 %cmp, %cmp14
   br i1 %or.cond, label %for.body, label %if.end
 

 ; CHECK-NEXT:    %inc = add nuw i32 %i.05, 1
 ; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-3) S: [1,-3) Exits: %num LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @trip_multiple_6
 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -5
 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:   Predicates:
-; CHECK:       Loop %for.body: Trip multiple is 2
+; CHECK:       Loop %for.body: Trip multiple is 6
 ;
 entry:
   %rem = urem i32 %num, 6
   %cmp = icmp eq i32 %rem, 0
   %cmp14 = icmp ne i32 %num, 0
   %or.cond = and i1 %cmp, %cmp14
   br i1 %or.cond, label %for.body, label %if.end
 

 ; CHECK-NEXT:    %inc = add nuw i32 %i.05, 1
 ; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-3) S: [1,-3) Exits: %num LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @trip_multiple_7
 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -5
 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:   Predicates:
-; CHECK:       Loop %for.body: Trip multiple is 1
+; CHECK:       Loop %for.body: Trip multiple is 7
 ;
 entry:
   %rem = urem i32 %num, 7
   %cmp = icmp eq i32 %rem, 0
   %cmp14 = icmp ne i32 %num, 0
   %or.cond = and i1 %cmp, %cmp14
   br i1 %or.cond, label %for.body, label %if.end
 

 ; CHECK-NEXT:    %inc = add nuw i32 %i.05, 1
 ; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-3) S: [1,-3) Exits: %num LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @trip_multiple_9
 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -5
 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:   Predicates:
-; CHECK:       Loop %for.body: Trip multiple is 1
+; CHECK:       Loop %for.body: Trip multiple is 9
 ;
 entry:
   %rem = urem i32 %num, 9
   %cmp = icmp eq i32 %rem, 0
   %cmp14 = icmp ne i32 %num, 0
   %or.cond = and i1 %cmp, %cmp14
   br i1 %or.cond, label %for.body, label %if.end
 

 ; CHECK-NEXT:    %inc = add nuw i32 %i.05, 1
 ; CHECK-NEXT:    --> {1,+,1}<nuw><%for.body> U: [1,-5) S: [1,-5) Exits: %num LoopDispositions: { %for.body: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @trip_multiple_10
 ; CHECK-NEXT:  Loop %for.body: backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: constant max backedge-taken count is -7
 ; CHECK-NEXT:  Loop %for.body: symbolic max backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:  Loop %for.body: Predicated backedge-taken count is (-1 + %num)
 ; CHECK-NEXT:   Predicates:
-; CHECK:       Loop %for.body: Trip multiple is 2
+; CHECK:       Loop %for.body: Trip multiple is 10
 ;
 entry:
   %rem = urem i32 %num, 10
   %cmp = icmp eq i32 %rem, 0
   %cmp14 = icmp ne i32 %num, 0
   %or.cond = and i1 %cmp, %cmp14
   br i1 %or.cond, label %for.body, label %if.end