[SCEV] Cache ZExt SCEV expressions.

[fhahn]

Summary

When creating SCEV expressions for ZExt, there's quite a bit of
reasoning done and in many places the reasoning in turn will try to
create new SCEVs for other ZExts.

This can have a huge compile-time impact. The attached test from #58402
takes an excessive amount of compile time; without the patch, the test
doesn't complete in 1500+ seconds, but with the patch it completes in 1
second.

To speed up this case, cache created ZExt expressions for given (SCEV, Ty) pairs.
Caching just ZExts is relatively straight-forward, but it might make
sense to extend it to other expressions in the future.

This has a slight positive impact on CTMark:

• O3: -0.07%
• ReleaseThinLTO: -0.06%
• ReleaseLTO-g: -0.04%

https://llvm-compile-time-tracker.com/compare.php?from=1f034e207885d7edfa34b5408c7c872a966febcd&to=08d9e0f7966745fa300ac4a6c55692666daab68c&stat=instructions:u

The patch also improves compile-time for some internal real-world workloads
where time spent in SCEV goes from ~300 seconds to ~3 seconds.

There are a few cases where computing & caching the result earlier may
return more pessimistic results, but the compile-time savings seem to
outweigh that.

Fixes #58402.

[nikic]

To make sure I understand the idea here correctly: We already cache the case where the zext does not fold through the early folding set lookup. This additional cache only helps with the case where the zext does fold, and the early lookup thus fails, is that correct?

If so, I feel like this needs some more general solution. We're using the same pattern (early folding set lookup to bypass most of the folding logic) in most (all?) other SCEV creation methods as well, and introducing an independent cache for each of these would not be great. I wonder if we could insert a "forwarding" node into the folding set for all folded SCEV expressions, which points to the folding result, or something along those lines.

[mkazantsev]

Agreed with Nikita that generalizing it to something wider than zext could be a good idea. How hard is that?

One more cache always scares me. Any ideas how we can strengthen verifier to find problems with it? I am specifically interested in dangling pointers.

llvm/lib/Analysis/ScalarEvolution.cpp

13752

Why not ZExtCacheUser.erase(S); after this loop?

[fhahn]

In D137505#3910603, @nikic wrote:

To make sure I understand the idea here correctly: We already cache the case where the zext does not fold through the early folding set lookup. This additional cache only helps with the case where the zext does fold, and the early lookup thus fails, is that correct?

If so, I feel like this needs some more general solution. We're using the same pattern (early folding set lookup to bypass most of the folding logic) in most (all?) other SCEV creation methods as well, and introducing an independent cache for each of these would not be great. I wonder if we could insert a "forwarding" node into the folding set for all folded SCEV expressions, which points to the folding result, or something along those lines.

Yes, that's exactly the issue. Currently the folding set (UniqueSCEV) only contains ZExt entries if we actually created a ZExt expression, not if it got folded to a different expression.

Adding forwarding nodes so we can add references to folded expressions would work I think, but it might be easier to have maintain a separate map for folds with a more general key. I updated the patch to use a more flexible key (similar to FoldingSetNodeID, but with a smaller bits vector) to sketch this out. The new version is mostly neutral in compile-time on CTMark, but still has the same huge improvements on the cases mentioned in the description. (https://llvm-compile-time-tracker.com/compare.php?from=2116d69f100c243069be1e76ac7fdac65ea5328a&to=05897510fbf52a59e0ce28f3f4ea4d06d59e380e&stat=instructions:u)

If we go down the forwarding route, IIUC we would have the add a new SCEV type for that. Happy to play around with that option as well, if people feel this would be more desirable.

One more cache always scares me. Any ideas how we can strengthen verifier to find problems with it? I am specifically interested in dangling pointers.

That's a good point! I am not sure, but it looks like we never actually deallocate SCEV objects, so not sure what to best verify. I updated to code to with the extra invalidation and also added it to forgetAllLoops.

[mkazantsev]

One thing we can do in verifier is to check that FoldCache and FoldCacheUser are in sync, meaning that for each {SCEV, FoldID} in FoldCacheUser there is {FoldId, SCEV} in FoldCache and vice versa. Just in case if one of them will be erased without doing the 2nd part.

llvm/include/llvm/Analysis/ScalarEvolution.h

73

It looks general enough to be moved to some utils, no? Just to think in the future.

79

The fact that we have different API for signed and unsigned leads me to think that we might be able to distinguish between them, e.g. distinguish set with single (int)1 from set with (unsigned) 1, but in fact we can't. What was the intention?

Maybe better remove signed version.

84

What worries me is that how easy to get a collision here. Basically, {0, 0, ~0, ~0, 0, 0} will collide with {0ULL, ~0ULL, 0ULL}. In your use case it should really be fine, because we add a lot of pointers, but if it is to be done more universal, need to think on making it harder to cheat (mix in types into hash?).

97

assert(!Bits.empty())?
Otherwise, if we want to allow empty sets (dunno why, just for generality), maybe start with Hash =Bits.size() and then mix in all elements?

125

is it just & std::max<int>()? Not asking to change, just trying to understand what was the intention.

[fhahn]

In D137505#3930144, @mkazantsev wrote:

One thing we can do in verifier is to check that FoldCache and FoldCacheUser are in sync, meaning that for each {SCEV, FoldID} in FoldCacheUser there is {FoldId, SCEV} in FoldCache and vice versa. Just in case if one of them will be erased without doing the 2nd part.

Thanks for elaborating! I added such verificatio and addressed the other comments.

[fhahn]

llvm/include/llvm/Analysis/ScalarEvolution.h

73

It is similar to FoldingSetNodeID which is used in multiple places. I played around with that quite a bit, but didn't manage to reach the same performance as with the version inline here.

Having this separate here is not ideal, but at the moment I don't see an easy way to unify/share the code.

79

The main reason for the integer overload is to avoid ambiguous function calls when addInteger is called with signed ints. In the end the signdness doesn't really matter, as we only look at the bits.

84

Yeah, unfortunately this is a potential issue. I went with your suggestion to include the number of entries in the vector in the hash, which should hopefully help a bit.

97

Otherwise, if we want to allow empty sets (dunno why, just for generality), maybe start with Hash =Bits.size() and then mix in all elements?

I went with adding Hash = Bits.size().

125

The main reason was to avoid potential conflicts with the empty/tombstone values, but that shouldn't really help much. Also, now that the hash uses Hash = Bits.size() it should be even less of an issue.

[fhahn]

ping :)

[mkazantsev]

LG, thanks for doing this!

[nikic]

In D137505#3921762, @fhahn wrote:

In D137505#3910603, @nikic wrote:

To make sure I understand the idea here correctly: We already cache the case where the zext does not fold through the early folding set lookup. This additional cache only helps with the case where the zext does fold, and the early lookup thus fails, is that correct?

If so, I feel like this needs some more general solution. We're using the same pattern (early folding set lookup to bypass most of the folding logic) in most (all?) other SCEV creation methods as well, and introducing an independent cache for each of these would not be great. I wonder if we could insert a "forwarding" node into the folding set for all folded SCEV expressions, which points to the folding result, or something along those lines.

Yes, that's exactly the issue. Currently the folding set (UniqueSCEV) only contains ZExt entries if we actually created a ZExt expression, not if it got folded to a different expression.

Adding forwarding nodes so we can add references to folded expressions would work I think, but it might be easier to have maintain a separate map for folds with a more general key. I updated the patch to use a more flexible key (similar to FoldingSetNodeID, but with a smaller bits vector) to sketch this out. The new version is mostly neutral in compile-time on CTMark, but still has the same huge improvements on the cases mentioned in the description. (https://llvm-compile-time-tracker.com/compare.php?from=2116d69f100c243069be1e76ac7fdac65ea5328a&to=05897510fbf52a59e0ce28f3f4ea4d06d59e380e&stat=instructions:u)

If we go down the forwarding route, IIUC we would have the add a new SCEV type for that. Happy to play around with that option as well, if people feel this would be more desirable.

My main thought here was that a forwarding node would avoid the need to do two folding set lookups, and should also avoid the need for the separate FoldID.

[nikic]

Looks like the new test fails on pre-commit CI.

[nikic]

llvm/lib/Analysis/ScalarEvolution.cpp

1619

I'm a bit uncertain about the invalidation story here. We will invalidate the cache if the folding result is invalidated. We will not invalidate if the original zext operand is invalidated. Could this result in problems?

[nikic]

In D137505#3977595, @nikic wrote:

My main thought here was that a forwarding node would avoid the need to do two folding set lookups, and should also avoid the need for the separate FoldID.

For what it's worth, I roughly sketched out what I had in mind here: https://github.com/llvm/llvm-project/commit/b158b70df1bb49036da8312a76f0b54de6466f7f This causes a change in incorrect-
exit-count.ll though, so probably it's not right.

[fhahn]

In D137505#3978188, @nikic wrote:

In D137505#3977595, @nikic wrote:

My main thought here was that a forwarding node would avoid the need to do two folding set lookups, and should also avoid the need for the separate FoldID.

For what it's worth, I roughly sketched out what I had in mind here: https://github.com/llvm/llvm-project/commit/b158b70df1bb49036da8312a76f0b54de6466f7f This causes a change in incorrect-
exit-count.ll though, so probably it's not right.

Thanks for sharing! I went ahead and cleaned up the code in my patch a bit, with an early exit if the entry is cached and only add the resulting SCEV to the cache if it is not a SCEVZeroExtendExpr.

This improves the compile-time impact a bit further:
https://llvm-compile-time-tracker.com/compare.php?from=bf9de7464946c65f488fe86ea61bfdecb8c654c1&to=5ac0108553992fb3d58bc27b1518e8cf06658a32&stat=instructions:u

[fhahn]

The latest update also moves the FoldID definition inside ScalarEvolution and the template specialization to the bottom of the file.

llvm/lib/Analysis/ScalarEvolution.cpp

1619

I think in that case, invalidation of the ZExt operand will trigger invalidation of the SCEV for the ZExt via the IR use-list based invalidation.

[uabelho]

Hi,

We see a verifier error with this patch:

opt -verify-scev -passes="require<iv-users>" bbi-77099.ll -o /dev/null

results in

Entry in FoldCache doesn't match FoldCacheUser: (1 + (zext i16 {-4,+,4}<nsw><%for.body919.i> to i32))<nuw><nsw> != {65533,+,4}<nuw><nsw><%for.body919.i>!
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: ../../main-github/llvm/build-all/bin/opt -verify-scev -passes=require<iv-users> bbi-77099.ll -o /dev/null
 #0 0x0000000002ef65a3 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (../../main-github/llvm/build-all/bin/opt+0x2ef65a3)
 #1 0x0000000002ef42ce llvm::sys::RunSignalHandlers() (../../main-github/llvm/build-all/bin/opt+0x2ef42ce)
 #2 0x0000000002ef6926 SignalHandler(int) Signals.cpp:0:0
 #3 0x00007f6e840f4630 __restore_rt sigaction.c:0:0
 #4 0x00007f6e8183b387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007f6e8183ca78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x0000000001ef311d llvm::ScalarEvolution::verify() const (../../main-github/llvm/build-all/bin/opt+0x1ef311d)
 #7 0x00000000038d666b llvm::FunctionToLoopPassAdaptor::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0x38d666b)
 #8 0x000000000326cc1d llvm::detail::PassModel<llvm::Function, llvm::FunctionToLoopPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) crtstuff.c:0:0
 #9 0x0000000002700edc llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0x2700edc)
#10 0x0000000000b0ff1d llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) crtstuff.c:0:0
#11 0x000000000270516e llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../main-github/llvm/build-all/bin/opt+0x270516e)
#12 0x0000000000b0fcfd llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) crtstuff.c:0:0
#13 0x000000000270018c llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../main-github/llvm/build-all/bin/opt+0x270018c)
#14 0x0000000000729aa3 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) (../../main-github/llvm/build-all/bin/opt+0x729aa3)
#15 0x0000000000738cc7 main (../../main-github/llvm/build-all/bin/opt+0x738cc7)
#16 0x00007f6e81827555 __libc_start_main (/lib64/libc.so.6+0x22555)
#17 0x0000000000722b10 _start (../../main-github/llvm/build-all/bin/opt+0x722b10)
Abort (core dumped)

bbi-77099.ll780 BDownload

[fhahn]

Thanks, I am looking into it.

[fhahn]

Should be fixed by a564048899a1

[uabelho]

In D137505#4017966, @fhahn wrote:

Should be fixed by a564048899a1

Yep, thanks!

llvm/include/llvm/Analysis/ScalarEvolution.h

 class StructType;
 class TargetLibraryInfo;
 class Type;
 class Value;
 enum SCEVTypes : unsigned short;
 
 extern bool VerifySCEV;
 
+
+class FoldID {
+  SmallVector<unsigned, 4> Bits;
+
+public:
+  void addInteger(unsigned long I) { Bits.push_back(I); }
+  void addInteger(unsigned I) { Bits.push_back(I); }
+  void addInteger(int I) { Bits.push_back(I); }
+
+  void addInteger(unsigned long long I) {
+    addInteger(unsigned(I));
+    addInteger(unsigned(I >> 32));
+  }
+
+  void addPointer(const void *Ptr) {
+    // Note: this adds pointers to the hash using sizes and endianness that
+    // depend on the host. It doesn't matter, however, because hashing on
+    // pointer values is inherently unstable. Nothing should depend on the
+    // ordering of nodes in the folding set.
+    static_assert(sizeof(uintptr_t) <= sizeof(unsigned long long),
+                  "unexpected pointer size");
+    addInteger(reinterpret_cast<uintptr_t>(Ptr));
+  }
+
+  unsigned computeHash() const {
+    unsigned Hash = Bits[0];
+    for (unsigned I = 1; I != Bits.size(); ++I)
+      Hash = detail::combineHashValue(Hash, Bits[I]);
+    return Hash;
+  }
+  bool operator==(const FoldID &RHS) const {
+    if (Bits.size() != RHS.Bits.size())
+      return false;
+    for (unsigned I = 0; I != Bits.size(); ++I)
+      if (Bits[I] != RHS.Bits[I])
+        return false;
+    return true;
+  }
+};
+
+template <> struct DenseMapInfo<FoldID> {
+  static inline FoldID getEmptyKey() {
+    FoldID ID;
+    ID.addInteger(~0ULL);
+    return ID;
+  }
+  static inline FoldID getTombstoneKey() {
+    FoldID ID;
+    ID.addInteger(~0ULL - 1ULL);
+    return ID;
+  }
+
+  static unsigned getHashValue(const FoldID &Val) {
+    return Val.computeHash() & ~(1 << (8 * sizeof(unsigned) - 1));
+  }
+
+  static bool isEqual(const FoldID &LHS,
+                      const FoldID &RHS) {
+    return LHS == RHS;
+  }
+};
+
 /// This class represents an analyzed expression in the program.  These are
 /// opaque objects that the client is not allowed to do much with directly.
 ///
 class SCEV : public FoldingSetNode {
   friend struct FoldingSetTrait<SCEV>;
 
   /// A reference to an Interned FoldingSetNodeID for this node.  The
   /// ScalarEvolution's BumpPtrAllocator holds the data.
public:
 
   const SCEV *getConstant(ConstantInt *V);
   const SCEV *getConstant(const APInt &Val);
   const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);
   const SCEV *getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth = 0);
   const SCEV *getPtrToIntExpr(const SCEV *Op, Type *Ty);
   const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
   const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
+  const SCEV *getZeroExtendExprImpl(const SCEV *Op, Type *Ty,
+                                    unsigned Depth = 0);
   const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
   const SCEV *getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty);
   const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty);
   const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops,
                          SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
                          unsigned Depth = 0);
   const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,
                          SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap,
private:
 
   /// The type for ValueExprMap.
   using ValueExprMapType =
       DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *>>;
 
   /// This is a cache of the values we have analyzed so far.
   ValueExprMapType ValueExprMap;
 
+  /// This is a cache for expressions that got folded to a different existing SCEV.
+  DenseMap<FoldID, const SCEV *> FoldCache;
+  DenseMap<const SCEV *, SmallVector<FoldID, 2>> FoldCacheUser;
+
   /// Mark predicate values currently being processed by isImpliedCond.
   SmallPtrSet<const Value *, 6> PendingLoopPredicates;
 
   /// Mark SCEVUnknown Phis currently being processed by getRangeRef.
   SmallPtrSet<const PHINode *, 6> PendingPhiRanges;
 
   // Mark SCEVUnknown Phis currently being processed by isImpliedViaMerge.
   SmallPtrSet<const PHINode *, 6> PendingMerges;

llvm/lib/Analysis/ScalarEvolution.cpp

 ScalarEvolution::getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth) {
   assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
          "This is not an extending conversion!");
   assert(isSCEVable(Ty) &&
          "This is not a conversion to a SCEVable type!");
   assert(!Op->getType()->isPointerTy() && "Can't extend pointer!");
   Ty = getEffectiveSCEVType(Ty);
 
+  FoldID ID;
+  ID.addInteger(scZeroExtend);
+  ID.addPointer(Op);
+  ID.addPointer(Ty);
+  auto Iter = FoldCache.insert({ID, nullptr});
+  if (Iter.second || !Iter.first->second) {
+    auto *S = getZeroExtendExprImpl(Op, Ty, Depth);
+
+    Iter = FoldCache.insert({ID, nullptr});
+    Iter.first->second = S;
+
+    auto R = FoldCacheUser.insert({S, {}});
+    R.first->second.push_back(ID);
+  }
+  return Iter.first->second;
+}
+
+const SCEV *ScalarEvolution::getZeroExtendExprImpl(const SCEV *Op, Type *Ty,
+                                                   unsigned Depth) {
+  assert(getTypeSizeInBits(Op->getType()) < getTypeSizeInBits(Ty) &&
+         "This is not an extending conversion!");
+  assert(isSCEVable(Ty) && "This is not a conversion to a SCEVable type!");
+  assert(!Op->getType()->isPointerTy() && "Can't extend pointer!");
+
   // Fold if the operand is constant.
   if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(Op))
     return getConstant(
       cast<ConstantInt>(ConstantExpr::getZExt(SC->getValue(), Ty)));
 
   // zext(zext(x)) --> zext(x)
   if (const SCEVZeroExtendExpr *SZ = dyn_cast<SCEVZeroExtendExpr>(Op))
     return getZeroExtendExpr(SZ->getOperand(), Ty, Depth + 1);
void ScalarEvolution::forgetAllLoops() {
   LoopDispositions.clear();
   BlockDispositions.clear();
   UnsignedRanges.clear();
   SignedRanges.clear();
   ExprValueMap.clear();
   HasRecMap.clear();
   MinTrailingZerosCache.clear();
   PredicatedSCEVRewrites.clear();
+  FoldCache.clear();
+  FoldCacheUser.clear();
 }
 
 void ScalarEvolution::forgetLoop(const Loop *L) {
   SmallVector<const Loop *, 16> LoopWorklist(1, L);
   SmallVector<Instruction *, 32> Worklist;
   SmallPtrSet<Instruction *, 16> Visited;
   SmallVector<const SCEV *, 16> ToForget;
 
void ScalarEvolution::forgetMemoizedResultsImpl(const SCEV *S) {
   auto BEUsersIt = BECountUsers.find(S);
   if (BEUsersIt != BECountUsers.end()) {
     // Work on a copy, as forgetBackedgeTakenCounts() will modify the original.
     auto Copy = BEUsersIt->second;
     for (const auto &Pair : Copy)
       forgetBackedgeTakenCounts(Pair.getPointer(), Pair.getInt());
     BECountUsers.erase(BEUsersIt);
   }
+
+  auto FoldUser = FoldCacheUser.find(S);
+  if (FoldUser != FoldCacheUser.end())
+    for (auto &KV : FoldUser->second)
+      FoldCache.erase(KV);
+  FoldCacheUser.erase(S);
 }
 
 void
 ScalarEvolution::getUsedLoops(const SCEV *S,
                               SmallPtrSetImpl<const Loop *> &LoopsUsed) {
   struct FindUsedLoops {
     FindUsedLoops(SmallPtrSetImpl<const Loop *> &LoopsUsed)
         : LoopsUsed(LoopsUsed) {}

llvm/test/Analysis/ScalarEvolution/pr58402-large-number-of-zext-exprs.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
+
+define i32 @pr58402_large_number_of_zext(ptr %dst) {
+; CHECK-LABEL: 'pr58402_large_number_of_zext'
+; CHECK-NEXT:  Classifying expressions for: @pr58402_large_number_of_zext
+; CHECK-NEXT:    %d.0 = phi i32 [ 0, %entry ], [ %add7.15, %header ]
+; CHECK-NEXT:    --> %d.0 U: [0,65) S: [0,65) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %b.0 = phi i32 [ 59, %entry ], [ %b.0, %header ]
+; CHECK-NEXT:    --> 59 U: [59,60) S: [59,60) Exits: 59 LoopDispositions: { %header: Invariant }
+; CHECK-NEXT:    %conv.neg = sext i1 %cmp to i32
+; CHECK-NEXT:    --> (sext i1 %cmp to i32) U: [-1,1) S: [-1,1) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %conv = zext i1 %cmp to i32
+; CHECK-NEXT:    --> (zext i1 %cmp to i32) U: [0,2) S: [0,2) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %i = and i32 %conv, -2
+; CHECK-NEXT:    --> (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw> U: [0,1) S: [0,1) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %add7 = add i32 %i, 4
+; CHECK-NEXT:    --> (4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> U: [4,5) S: [4,5) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %i1 = and i32 %add7, -2
+; CHECK-NEXT:    --> (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw> U: [4,5) S: [4,5) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %add7.1 = add i32 %i1, 4
+; CHECK-NEXT:    --> (4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> U: [8,9) S: [8,9) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %i2 = and i32 %add7.1, -2
+; CHECK-NEXT:    --> (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw> U: [8,9) S: [8,9) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %add7.2 = add i32 %i2, 4
+; CHECK-NEXT:    --> (4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> U: [12,13) S: [12,13) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %i3 = and i32 %add7.2, -2
+; CHECK-NEXT:    --> (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw> U: [12,13) S: [12,13) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %add7.3 = add i32 %i3, 4
+; CHECK-NEXT:    --> (4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> U: [16,17) S: [16,17) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %i4 = and i32 %add7.3, -2
+; CHECK-NEXT:    --> (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw> U: [16,17) S: [16,17) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %add7.4 = add i32 %i4, 4
+; CHECK-NEXT:    --> (4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> U: [20,21) S: [20,21) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %i5 = and i32 %add7.4, -2
+; CHECK-NEXT:    --> (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw> U: [20,21) S: [20,21) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %add7.5 = add i32 %i5, 4
+; CHECK-NEXT:    --> (4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> U: [24,25) S: [24,25) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %i6 = and i32 %add7.5, -2
+; CHECK-NEXT:    --> (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw> U: [24,25) S: [24,25) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %add7.6 = add i32 %i6, 4
+; CHECK-NEXT:    --> (4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> U: [28,29) S: [28,29) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %i7 = and i32 %add7.6, -2
+; CHECK-NEXT:    --> (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw> U: [28,29) S: [28,29) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %add7.7 = add i32 %i7, 4
+; CHECK-NEXT:    --> (4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> U: [32,33) S: [32,33) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %i8 = and i32 %add7.7, -2
+; CHECK-NEXT:    --> (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw> U: [32,33) S: [32,33) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %add7.8 = add i32 %i8, 4
+; CHECK-NEXT:    --> (4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> U: [36,37) S: [36,37) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %i9 = and i32 %add7.8, -2
+; CHECK-NEXT:    --> (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw> U: [36,37) S: [36,37) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %add7.9 = add i32 %i9, 4
+; CHECK-NEXT:    --> (4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> U: [40,41) S: [40,41) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %i10 = and i32 %add7.9, -2
+; CHECK-NEXT:    --> (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw> U: [40,41) S: [40,41) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %add7.10 = add i32 %i10, 4
+; CHECK-NEXT:    --> (4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> U: [44,45) S: [44,45) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %i11 = and i32 %add7.10, -2
+; CHECK-NEXT:    --> (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw> U: [44,45) S: [44,45) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %add7.11 = add i32 %i11, 4
+; CHECK-NEXT:    --> (4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> U: [48,49) S: [48,49) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %i12 = and i32 %add7.11, -2
+; CHECK-NEXT:    --> (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw> U: [48,49) S: [48,49) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %add7.12 = add i32 %i12, 4
+; CHECK-NEXT:    --> (4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> U: [52,53) S: [52,53) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %i13 = and i32 %add7.12, -2
+; CHECK-NEXT:    --> (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw> U: [52,53) S: [52,53) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %add7.13 = add i32 %i13, 4
+; CHECK-NEXT:    --> (4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> U: [56,57) S: [56,57) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %i14 = and i32 %add7.13, -2
+; CHECK-NEXT:    --> (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw> U: [56,57) S: [56,57) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %add7.14 = add i32 %i14, 4
+; CHECK-NEXT:    --> (4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> U: [60,61) S: [60,61) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %i15 = and i32 %add7.14, -2
+; CHECK-NEXT:    --> (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw> U: [60,61) S: [60,61) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %add7.15 = add i32 %i15, 4
+; CHECK-NEXT:    --> (4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> U: [64,65) S: [64,65) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:    %i16 = and i32 %add7.15, -2
+; CHECK-NEXT:    --> (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((4 + (2 * ((zext i1 %cmp to i32) /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw>)<nuw><nsw> /u 2))<nuw><nsw> U: [64,65) S: [64,65) Exits: <<Unknown>> LoopDispositions: { %header: Variant }
+; CHECK-NEXT:  Determining loop execution counts for: @pr58402_large_number_of_zext
+; CHECK-NEXT:  Loop %header: <multiple exits> Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %header: Unpredictable max backedge-taken count.
+; CHECK-NEXT:  Loop %header: Unpredictable predicated backedge-taken count.
+;
+entry:
+  br label %header
+
+header:
+  %d.0 = phi i32 [ 0, %entry ], [ %add7.15, %header ]
+  %b.0 = phi i32 [ 59, %entry ], [ %b.0, %header ]
+  %cmp = icmp slt i32 %b.0, 1
+  %conv.neg = sext i1 %cmp to i32
+  %conv = zext i1 %cmp to i32
+  %i = and i32 %conv, -2
+  %add7 = add i32 %i, 4
+  %i1 = and i32 %add7, -2
+  %add7.1 = add i32 %i1, 4
+  %i2 = and i32 %add7.1, -2
+  %add7.2 = add i32 %i2, 4
+  %i3 = and i32 %add7.2, -2
+  %add7.3 = add i32 %i3, 4
+  %i4 = and i32 %add7.3, -2
+  %add7.4 = add i32 %i4, 4
+  %i5 = and i32 %add7.4, -2
+  %add7.5 = add i32 %i5, 4
+  %i6 = and i32 %add7.5, -2
+  %add7.6 = add i32 %i6, 4
+  %i7 = and i32 %add7.6, -2
+  %add7.7 = add i32 %i7, 4
+  %i8 = and i32 %add7.7, -2
+  %add7.8 = add i32 %i8, 4
+  %i9 = and i32 %add7.8, -2
+  %add7.9 = add i32 %i9, 4
+  %i10 = and i32 %add7.9, -2
+  %add7.10 = add i32 %i10, 4
+  %i11 = and i32 %add7.10, -2
+  %add7.11 = add i32 %i11, 4
+  %i12 = and i32 %add7.11, -2
+  %add7.12 = add i32 %i12, 4
+  %i13 = and i32 %add7.12, -2
+  %add7.13 = add i32 %i13, 4
+  %i14 = and i32 %add7.13, -2
+  %add7.14 = add i32 %i14, 4
+  %i15 = and i32 %add7.14, -2
+  %add7.15 = add i32 %i15, 4
+  %i16 = and i32 %add7.15, -2
+  store i32 %add7.15, ptr %dst, align 4
+  br label %header
+}

llvm/test/Transforms/IndVarSimplify/AArch64/widen-loop-comp.ll

 define i32 @test16_unsigned_pos2(i32 %start, i32* %p, i32* %q, i32 %x) {
 ; CHECK-LABEL: @test16_unsigned_pos2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = zext i32 [[START:%.*]] to i64
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ [[TMP0]], [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[COND:%.*]] = icmp eq i64 [[INDVARS_IV]], 0
-; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[INDVARS_IV]] to i32
-; CHECK-NEXT:    [[FOO:%.*]] = add i32 [[TMP1]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = add nsw i64 [[INDVARS_IV]], -1
 ; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[GUARDED:%.*]]
 ; CHECK:       guarded:
-; CHECK-NEXT:    [[ICMP_USER:%.*]] = icmp ne i32 [[FOO]], [[X:%.*]]
-; CHECK-NEXT:    br i1 [[ICMP_USER]], label [[BACKEDGE]], label [[SIDE_EXIT:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = zext i32 [[X:%.*]] to i64
+; CHECK-NEXT:    [[ICMP_USER_WIDE:%.*]] = icmp ne i64 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    br i1 [[ICMP_USER_WIDE]], label [[BACKEDGE]], label [[SIDE_EXIT:%.*]]
 ; CHECK:       backedge:
-; CHECK-NEXT:    [[INDEX:%.*]] = zext i32 [[FOO]] to i64
-; CHECK-NEXT:    [[STORE_ADDR:%.*]] = getelementptr i32, i32* [[P:%.*]], i64 [[INDEX]]
+; CHECK-NEXT:    [[STORE_ADDR:%.*]] = getelementptr i32, i32* [[P:%.*]], i64 [[TMP1]]
 ; CHECK-NEXT:    store i32 1, i32* [[STORE_ADDR]], align 4
-; CHECK-NEXT:    [[LOAD_ADDR:%.*]] = getelementptr i32, i32* [[Q:%.*]], i64 [[INDEX]]
-; CHECK-NEXT:    [[STOP:%.*]] = load i32, i32* [[Q]], align 4
+; CHECK-NEXT:    [[STOP:%.*]] = load i32, i32* [[Q:%.*]], align 4
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[STOP]], 0
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[FAILURE:%.*]]
 ; CHECK:       exit:
-; CHECK-NEXT:    call void @use(i32 -1)
-; CHECK-NEXT:    ret i32 -1
+; CHECK-NEXT:    [[TMP3:%.*]] = trunc i64 -1 to i32
+; CHECK-NEXT:    call void @use(i32 [[TMP3]])
+; CHECK-NEXT:    ret i32 [[TMP3]]
 ; CHECK:       failure:
-; CHECK-NEXT:    [[FOO_LCSSA2:%.*]] = phi i32 [ [[FOO]], [[BACKEDGE]] ]
-; CHECK-NEXT:    call void @use(i32 [[FOO_LCSSA2]])
+; CHECK-NEXT:    [[FOO_LCSSA2_WIDE:%.*]] = phi i64 [ [[TMP1]], [[BACKEDGE]] ]
+; CHECK-NEXT:    [[TMP4:%.*]] = trunc i64 [[FOO_LCSSA2_WIDE]] to i32
+; CHECK-NEXT:    call void @use(i32 [[TMP4]])
 ; CHECK-NEXT:    unreachable
 ; CHECK:       side_exit:
 ; CHECK-NEXT:    ret i32 0
 ;
 entry:
   br label %loop
 
 loop: