[SCEV] Extend ability to infer flags to more complicates scopes

[reames]

Summary

At it's heart, this change simply extends the reasoning for proving that B must execute if A does to allow a single-successor or loop preheader chain of blocks. The majority of the change is in making that reasonable efficient.

To make this efficient, we need to cache the per-block queries for the intermediate nodes in the found path. (I'd love to do the edge cases too, but the invalidation is trickier.) This patch does so by taking an existing loop level cache, and essentially splitting it into a per-block cache and then summarizing back to loop level. In particular, we exactly parallel the construction and invalidation of the new-block cache so that no new invalidation events should be needed. The new cache should be "as correct" as the original code.

The invalidation actions we need to worry about are adding and removing instructions from a block. For removal, we might end up in an imprecise state. For addition, we might end up in a incorrect state. The existing LoopProperties cache has exactly the same issues, and depends on forgetLoop calls for correctness when we insert new instructions (with interesting properties) into a loop.

Long term, I'm actually hoping to sink the notion of block properties into BasicBlock itself, but starting here with a standalone patch makes a lot of sense.

[mkazantsev]

Why am I getting more and more scared every time a new cache is added in SCEV? :) Please add verifiation info ::verify().

I think you might be also missing preheader invalidation in forgetLoop.

llvm/lib/Analysis/ScalarEvolution.cpp

7663

What about preheader?

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

6839–6840

Does it handle invoke terminator correctly?

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

6650–6651

Quick check: A dominates B?

6669

I guess this will hand if you call it on 2 unreachable blocks going to one another.

6669

hang*

6696

nit: capitalize lambda name.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

6650–6651

Two answers:
As actually used, that's trivially true.

For the interface, we don't need this property. Consider B in the header of some loop L, with A in the (unconditional) latch block. A must reach B even though A does not dominate B.

This could be an optimization since the case implemented doesn't catch the case just mentioned. Will add with that as a comment.

6669

Good catch, we should filter by reachability since unreachable CFGs are weird.

6696

They're methods, not variables. (Or at least, I believe that's our style convention.)

6839–6840

Er, it's calling the same function as previously? Not sure what you mean?

7663

Good catch, had not considered the implication of this combined with the attempted caching of the last element in the path.

[reames]

Rebase and address review comments.

The added verify routine reveals a bug in LoopFusion, which appears to be broader than this patch. I'm going to look into that, but need to finish something else first, so it might be a day or two.

[reames]

I was wrong about the loop-fusion failures being a bug in loop fusion, it was a bug in the verification I'd added.

However, the complexity of the "fixed" version of the verification makes me really doubt that verification here is worthwhile at all. Our infrastructure of value handles of const types is *awful*. I'm posting this so that anyone interested can see the cleanest version I could come up with. (The addition of the new constructor to SCEVCallbackVH hides the needs for a *lot* of const_casts otherwise required for e.g. WeakVH which would be a more natural fit.)

Given I don't plan to do the core ValueHandle work needed to make the verification readable (at this time), I'm going to drop the verification entirely in the next revision.

[reames]

Drop verification complexity.

[mkazantsev]

I'm generally OK now, but please give your opinion on forgetLoop question since there might be a bug lurking here.

llvm/lib/Analysis/ScalarEvolution.cpp

6636

This is a really strange and counter-intuitive limitation. I'm OK with it for now, but I think we might want to remove it in the future. Should we add a TODO here or in method description?

6650–6651

Fair, I didn't think of this case. Unconditional latches are rare, though, so I think this is fine.

6660

Makes sense to check reachibility of A as well, just to avoid useless work and save some CT.

6675

As an idea for follow-up: if PrevBB is the only exit of a loop (w/o abnormal exits or locks etc), we can also return it, because the loop should be finite. Maybe makes sense to add a TODO.

6696

I was certain they are treated as variables, and there is a lot of examples of this in this very file (grep by "= [", most are capitalized).

./ScalarEvolution.cpp:639:    const auto IsGVNameSemantic = [&](const GlobalValue *GV) {
./ScalarEvolution.cpp:854:  auto IsLessComplex = [&](const SCEV *LHS, const SCEV *RHS) {
./ScalarEvolution.cpp:2356:  auto IsKnownNonNegative = [&](const SCEV *S) {
./ScalarEvolution.cpp:2370:    auto Opcode = [&] {
./ScalarEvolution.cpp:2469:  auto ComputeFlags = [this, OrigFlags](const ArrayRef<const SCEV *> Ops) {
./ScalarEvolution.cpp:2513:  auto FindTruncSrcType = [&]() -> Type * {
./ScalarEvolution.cpp:3058:  auto ComputeFlags = [this, OrigFlags](const ArrayRef<const SCEV *> Ops) {
./ScalarEvolution.cpp:3638:  const bool AssumeInBoundsFlags = [&]() {
./ScalarEvolution.cpp:3752:    auto FoldOp = [&](const APInt &LHS, const APInt &RHS) {
./ScalarEvolution.cpp:4196:    auto MatchMinMaxNegation = [&](const SCEVMinMaxExpr *MME) {
./ScalarEvolution.cpp:5193:  auto getExtendedExpr = [&](const SCEV *Expr,
./ScalarEvolution.cpp:5208:  auto PredIsKnownFalse = [&](const SCEV *Expr,
./ScalarEvolution.cpp:5228:  auto AppendPredicate = [&](const SCEV *Expr,
./ScalarEvolution.cpp:5300:  auto areExprsEqual = [&](const SCEV *Expr1, const SCEV *Expr2) -> bool {
./ScalarEvolution.cpp:5738:      auto CoerceOperand = [&](const SCEV *Op) -> const SCEV * {
./ScalarEvolution.cpp:6626:  auto pushOp = [&](const SCEV *S) {
./ScalarEvolution.cpp:6771:    auto HasSideEffects = [](Instruction *I) {
./ScalarEvolution.cpp:7692:  auto PredicateNotAlwaysTrue = [](const ExitNotTakenInfo &ENT) {
./ScalarEvolution.cpp:7715:  auto PredicateNotAlwaysTrue = [](const ExitNotTakenInfo &ENT) {
./ScalarEvolution.cpp:9404:  auto SolveForBoundary = [&](APInt Bound) -> std::pair<Optional<APInt>,bool> {
./ScalarEvolution.cpp:9422:    auto LeavesRange = [&] (const APInt &X) {
./ScalarEvolution.cpp:9688:  auto ComputesEqualValues = [](const Instruction *A, const Instruction *B) {
./ScalarEvolution.cpp:9714:  auto TrivialCase = [&](bool TriviallyTrue) {
./ScalarEvolution.cpp:10230:  auto CheckRanges = [&](const ConstantRange &RangeLHS,
./ScalarEvolution.cpp:10261:  auto MatchBinaryAddToConst = [this](const SCEV *X, const SCEV *Y,
./ScalarEvolution.cpp:10529:    auto ProofFn = [&](ICmpInst::Predicate P) {
./ScalarEvolution.cpp:10537:  auto ProveViaGuard = [&](const BasicBlock *Block) {
./ScalarEvolution.cpp:10541:      auto ProofFn = [&](ICmpInst::Predicate P) {
./ScalarEvolution.cpp:10551:  auto ProveViaCond = [&](const Value *Condition, bool Inverse) {
./ScalarEvolution.cpp:10556:      auto ProofFn = [&](ICmpInst::Predicate P) {
./ScalarEvolution.cpp:10790:  auto IsSignFlippedPredicate = [](CmpInst::Predicate P1,
./ScalarEvolution.cpp:11143:  auto ProvedEasily = [&](const SCEV *S1, const SCEV *S2) {
./ScalarEvolution.cpp:11337:  auto GetOpFromSExt = [&](const SCEV *S) {
./ScalarEvolution.cpp:11352:  auto IsSGTViaContext = [&](const SCEV *S1, const SCEV *S2) {
./ScalarEvolution.cpp:11376:    auto IsSumGreaterThanRHS = [&](const SCEV *S1, const SCEV *S2) {
./ScalarEvolution.cpp:11696:  auto canAssumeNoSelfWrap = [&](const SCEVAddRecExpr *AR) {
./ScalarEvolution.cpp:11842:      auto wouldZeroStrideBeUB = [&]() {
./ScalarEvolution.cpp:11859:    auto isUBOnWrap = [&]() {
./ScalarEvolution.cpp:11954:    auto canProveRHSGreaterThanEqualStart = [&]() {
./ScalarEvolution.cpp:12007:    bool MayAddOverflow = [&] {
./ScalarEvolution.cpp:13581:  const auto MatchURemWithDivisor = [&](const SCEV *B) {
./ScalarEvolution.cpp:13653:  auto CollectCondition = [&](ICmpInst::Predicate Predicate, const SCEV *LHS,

6698

just an idea: merge the two loops together?

6718

Can we use lookup?

6839–6840

I thought there might have been a bug before your patch, but it seems that isGuaranteedToTransferExecutionToSuccessor handles it correctly.

7665

What still worries me (though I can't say if there is a bug here) is that your path might contain blocks from multiple (nested) loops, and here we might only forget inner loop. Will that still be correct?

[reames]

Placing this on hold. I was expecting to see perf regressions reported against the flag redefinition changes, and this was expected to be needed to help claw back some of that performance. As there's been nothing reported, I'd prefer not to add further complexity here without cause. Placing this on hold for the moment, if we go a couple more weeks without reported regressions I'll abandon this change.

llvm/lib/Analysis/ScalarEvolution.cpp

6660

We know A dominates B. From B being reachable, A must also be.

6675

We have this same basic pattern repeating in a bunch of places. If we ever implement this idea, we'd need to visit all of them. I don't think having a comment in one place really helps.

[reames]

Still no reported issues with the original patch. Abandoning for now, will return if warranted.

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
   DenseMap<const SCEV *, SmallVector<std::pair<const Loop *, const SCEV *>, 2>>
       ValuesAtScopes;
 
   /// Memoized computeLoopDisposition results.
   DenseMap<const SCEV *,
            SmallVector<PointerIntPair<const Loop *, 2, LoopDisposition>, 2>>
       LoopDispositions;
 
+  /// Cache for \c isGuaranteedToTransferExecutionToSuccessor(BB)
+  DenseMap<const BasicBlock *, bool> BlockTransferExecutionToSuccessorCache;
+
+  /// A version of the ValueTracking routine, but cached for efficiency, and
+  /// restricted to blocks inside a Loop.
+  bool isGuaranteedToTransferExecutionToSuccessor(const BasicBlock *BB);
+
   struct LoopProperties {
     /// Set to true if the loop contains no instruction that can abnormally exit
     /// the loop (i.e. via throwing an exception, by terminating the thread
     /// cleanly or by infinite looping in a called function).  Strictly
     /// speaking, the last one is not leaving the loop, but is identical to
     /// leaving the loop for reasoning about undefined behavior.
     bool HasNoAbnormalExits;
 

llvm/lib/Analysis/ScalarEvolution.cpp

else if (auto *S2 = dyn_cast<SCEVNAryExpr>(S))
         pushOp(Op);
     else if (auto *S2 = dyn_cast<SCEVUDivExpr>(S))
       for (auto *Op : S2->operands())
         pushOp(Op);
   }
   return Bound ? Bound : &*F.getEntryBlock().begin();
 }
 
+bool ScalarEvolution::
+isGuaranteedToTransferExecutionToSuccessor(const BasicBlock *BB) {
+  assert(LI.getLoopFor(BB) && "must be in a loop for invalidation!");
+  if (!BlockTransferExecutionToSuccessorCache.count(BB))
+    BlockTransferExecutionToSuccessorCache[BB] =
+      llvm::isGuaranteedToTransferExecutionToSuccessor(BB);
+
+  return BlockTransferExecutionToSuccessorCache[BB];
+}
+
 bool ScalarEvolution::isGuaranteedToTransferExecutionTo(const Instruction *A,
                                                         const Instruction *B) {
   if (A->getParent() == B->getParent() &&
-      isGuaranteedToTransferExecutionToSuccessor(A->getIterator(),
+      llvm::isGuaranteedToTransferExecutionToSuccessor(A->getIterator(),
                                                        B->getIterator()))
     return true;
 
-  auto *BLoop = LI.getLoopFor(B->getParent());
-  if (BLoop && BLoop->getHeader() == B->getParent() &&
-      BLoop->getLoopPreheader() == A->getParent() &&
-      isGuaranteedToTransferExecutionToSuccessor(A->getIterator(),
-                                                 A->getParent()->end()) &&
-      isGuaranteedToTransferExecutionToSuccessor(B->getParent()->begin(),
-                                                 B->getIterator()))
-    return true;
+  // The current implementation only handles the case where A dominates B.
+  // Note that cases where A does not dominate B, but where A must reach B do
+  // exist.  An example would be B in the header of some loop L, and A in the
+  // (unconditional) latch block of L.
+  if (!DT.dominates(A->getParent(), B->getParent()))
+    return false;
+
+  // Unreachable CFGs can get very weird.  To avoid infinite loops below,
+  // require reachability
+  if (!DT.isReachableFromEntry(B->getParent()))
+    return false;
+
+  // First find a path from B to A where if all blocks along path
+  // are transparent, then we can prove A reaches B.  Defer the actual
+  // checks for transparence until the end as (even cached) that's expensive.
+  SmallVector<const BasicBlock *> Path;
+  Path.push_back(B->getParent());
+
+  auto getPrevBB = [&](const BasicBlock *BB) -> const BasicBlock * {
+    auto *L = LI.getLoopFor(BB);
+    if (L && L->getHeader() == BB)
+      return L->getLoopPreheader();
+
+    auto *PrevBB = BB->getUniquePredecessor();
+    return PrevBB && PrevBB->getUniqueSuccessor() ? PrevBB : nullptr;
+  };
+
+  auto *PrevBB = getPrevBB(B->getParent());
+  if (!PrevBB)
+    return false;
+
+  while (true) {
+    Path.push_back(PrevBB);
+    if (PrevBB == A->getParent())
+      break;
+
+    PrevBB = getPrevBB(PrevBB);
+    if (!PrevBB)
       return false;
   }
+  assert(Path.front() == B->getParent());
+  assert(Path.back() == A->getParent());
+  assert(Path.size() >= 2);
+
+  // We rely on forgetLoop for invalidation of the cache, as a result, we
+  // can only query blocks in loops.  This restriction can be removed once
+  // we find a better cache update mechanism.
+  for (unsigned i = 1; i < Path.size() - 1; i++)
+    if (!LI.getLoopFor(Path[i]))
+      return false;
+
+  // Do the cacheable part first
+  for (unsigned i = 1; i < Path.size() - 1; i++)
+    if (!isGuaranteedToTransferExecutionToSuccessor(Path[i]))
+      return false;
+
+  // Finally, check the prefix of B's block and the suffix of A's.  For the
+  // local search, we use the block local cache as a filter.
+  auto doLocalSearch = [&](BasicBlock::const_iterator Begin,
+                           BasicBlock::const_iterator End) {
+    if (Begin == End)
+      return true;
 
+    auto *BB = Begin->getParent();
+
+    // Knowing the block isn't transparent isn't enough to answer this query;
+    // we'd need to know where in the block the blockage is.
+    if (BlockTransferExecutionToSuccessorCache.count(BB) &&
+        BlockTransferExecutionToSuccessorCache[BB])
+      return true;
+
+    // It's tempting to cache this, but since we're using a bounded search
+    // here, we'd risk saving false positives into the block cache.
+    return ::isGuaranteedToTransferExecutionToSuccessor(Begin, End);
+  };
+
+  return (doLocalSearch(B->getParent()->begin(), B->getIterator()) &&
+          doLocalSearch(A->getIterator(), A->getParent()->end()));
+}
 
 bool ScalarEvolution::isSCEVExprNeverPoison(const Instruction *I) {
   // Only proceed if we can prove that I does not yield poison.
   if (!programUndefinedIfPoison(I))
     return false;
 
   // At this point we know that if I is executed, then it does not wrap
   // according to at least one of NSW or NUW. If I is not executed, then we do
auto HasSideEffects = [](Instruction *I) {
         return !SI->isSimple();
 
       return I->mayThrow() || I->mayWriteToMemory();
     };
 
     LoopProperties LP = {/* HasNoAbnormalExits */ true,
                          /*HasNoSideEffects*/ true};
 
-    for (auto *BB : L->getBlocks())
+    for (auto *BB : L->getBlocks()) {
+      LoopProperties Local = {true, true};
       for (auto &I : *BB) {
-        if (!isGuaranteedToTransferExecutionToSuccessor(&I))
-          LP.HasNoAbnormalExits = false;
+        if (!llvm::isGuaranteedToTransferExecutionToSuccessor(&I))
+          Local.HasNoAbnormalExits = false;
         if (HasSideEffects(&I))
-          LP.HasNoSideEffects = false;
-        if (!LP.HasNoAbnormalExits && !LP.HasNoSideEffects)
-          break; // We're already as pessimistic as we can get.
-      }
+          Local.HasNoSideEffects = false;
+        if (!Local.HasNoAbnormalExits && !Local.HasNoSideEffects)
+          break; // We're already as pessimistic as we can get.
+      }
+      BlockTransferExecutionToSuccessorCache[BB] = Local.HasNoAbnormalExits; 
+      LP.HasNoAbnormalExits &= Local.HasNoAbnormalExits;
+      LP.HasNoSideEffects &= Local.HasNoSideEffects;
 
     auto InsertPair = LoopPropertiesCache.insert({L, LP});
     assert(InsertPair.second && "We just checked!");
     Itr = InsertPair.first;
   }
 
   return Itr->second;
 }

 void ScalarEvolution::forgetAllLoops() {
   // This method is intended to forget all info about loops. It should
   // invalidate caches as if the following happened:
   // - The trip counts of all loops have changed arbitrarily
   // - Every llvm::Value has been updated in place to produce a different
   // result.
   BackedgeTakenCounts.clear();
   PredicatedBackedgeTakenCounts.clear();
+  BlockTransferExecutionToSuccessorCache.clear();
   LoopPropertiesCache.clear();
   ConstantEvolutionLoopExitValue.clear();
   ValueExprMap.clear();
   ValuesAtScopes.clear();
   LoopDispositions.clear();
   BlockDispositions.clear();
   UnsignedRanges.clear();
   SignedRanges.clear();
while (!Worklist.empty()) {
         forgetMemoizedResults(It->second);
         if (PHINode *PN = dyn_cast<PHINode>(I))
           ConstantEvolutionLoopExitValue.erase(PN);
       }
 
       PushDefUseChildren(I, Worklist);
     }
 
+    // Removing the blocks is probably overly conservative here, but it's not
+    // clear what client code might assume that forgetLoop handled the code
+    // motion invalidation required.
+    if (auto *BB = CurrL->getLoopPreheader())
+      BlockTransferExecutionToSuccessorCache.erase(BB);
+    for (auto *BB : CurrL->getBlocks())
+      BlockTransferExecutionToSuccessorCache.erase(BB);
     LoopPropertiesCache.erase(CurrL);
     // Forget all contained loops too, to avoid dangling entries in the
     // ValuesAtScopes map.
     LoopWorklist.append(CurrL->begin(), CurrL->end());
   }
 }
 
 void ScalarEvolution::forgetTopmostLoop(const Loop *L) {
: F(Arg.F), HasGuards(Arg.HasGuards), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT),
       MinTrailingZerosCache(std::move(Arg.MinTrailingZerosCache)),
       BackedgeTakenCounts(std::move(Arg.BackedgeTakenCounts)),
       PredicatedBackedgeTakenCounts(
           std::move(Arg.PredicatedBackedgeTakenCounts)),
       ConstantEvolutionLoopExitValue(
           std::move(Arg.ConstantEvolutionLoopExitValue)),
       ValuesAtScopes(std::move(Arg.ValuesAtScopes)),
       LoopDispositions(std::move(Arg.LoopDispositions)),
+      BlockTransferExecutionToSuccessorCache(std::move(Arg.BlockTransferExecutionToSuccessorCache)),
       LoopPropertiesCache(std::move(Arg.LoopPropertiesCache)),
       BlockDispositions(std::move(Arg.BlockDispositions)),
       UnsignedRanges(std::move(Arg.UnsignedRanges)),
       SignedRanges(std::move(Arg.SignedRanges)),
       UniqueSCEVs(std::move(Arg.UniqueSCEVs)),
       UniquePreds(std::move(Arg.UniquePreds)),
       SCEVAllocator(std::move(Arg.SCEVAllocator)),
       LoopUsers(std::move(Arg.LoopUsers)),

llvm/test/Analysis/Delinearization/multidim_ivs_and_integer_offsets_3d.ll

 ; RUN: opt < %s -passes='print<delinearization>' -disable-output  2>&1 | FileCheck %s
 
 ; void foo(long n, long m, long o, double A[n][m][o]) {
 ;
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       for (long k = 0; k < o; k++)
 ;         A[i+3][j-4][k+7] = 1.0;
 ; }
 
 ; AddRec: {{{(56 + (8 * (-4 + (3 * %m)) * %o) + %A),+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j>,+,8}<%for.k>
 ; CHECK: Base offset: %A
 ; CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of 8 bytes.
-; CHECK: ArrayRef[{3,+,1}<nuw><%for.i>][{-4,+,1}<nsw><%for.j>][{7,+,1}<nuw><nsw><%for.k>]
+; CHECK: ArrayRef[{3,+,1}<nuw><nsw><%for.i>][{-4,+,1}<nsw><%for.j>][{7,+,1}<nuw><nsw><%for.k>]
 
 define void @foo(i64 %n, i64 %m, i64 %o, double* %A) {
 entry:
   br label %for.i
 
 for.i:
   %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]
   br label %for.j

llvm/test/Analysis/Delinearization/multidim_ivs_and_parameteric_offsets_3d.ll

 ; RUN: opt < %s -passes='print<delinearization>' -disable-output 2>&1 | FileCheck %s
 
 ; void foo(long n, long m, long o, double A[n][m][o], long p, long q, long r) {
 ;
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       for (long k = 0; k < o; k++)
 ;         A[i+p][j+q][k+r] = 1.0;
 ; }
 
 ; AddRec: {{{((8 * ((((%m * %p) + %q) * %o) + %r)) + %A),+,(8 * %m * %o)}<%for.i>,+,(8 * %o)}<%for.j>,+,8}<%for.k>
 ; CHECK: Base offset: %A
 ; CHECK: ArrayDecl[UnknownSize][%m][%o] with elements of 8 bytes.
-; CHECK: ArrayRef[{%p,+,1}<nw><%for.i>][{%q,+,1}<nsw><%for.j>][{%r,+,1}<nsw><%for.k>]
+; CHECK: ArrayRef[{%p,+,1}<nsw><%for.i>][{%q,+,1}<nsw><%for.j>][{%r,+,1}<nsw><%for.k>]
 
 define void @foo(i64 %n, i64 %m, i64 %o, double* %A, i64 %p, i64 %q, i64 %r) {
 entry:
   br label %for.i
 
 for.i:
   %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]
   br label %for.j

llvm/test/Analysis/ScalarEvolution/flags-from-poison.ll

 ; it should not infer nsw in this case, as that would require looking
 ; outside the loop header.
 define void @test-add-not-header(float* %input, i32 %offset, i32 %numIterations) {
 ; CHECK-LABEL: 'test-add-not-header'
 ; CHECK-NEXT:  Classifying expressions for: @test-add-not-header
 ; CHECK-NEXT:    %i = phi i32 [ %nexti, %loop2 ], [ 0, %entry ]
 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,-2147483648) S: [0,-2147483648) Exits: (-1 + %numIterations) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %index32 = add nsw i32 %i, %offset
-; CHECK-NEXT:    --> {%offset,+,1}<nw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {%offset,+,1}<nsw><%loop> U: full-set S: full-set Exits: (-1 + %offset + %numIterations) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %ptr = getelementptr inbounds float, float* %input, i32 %index32
-; CHECK-NEXT:    --> ((4 * (sext i32 {%offset,+,1}<nw><%loop> to i64))<nsw> + %input) U: full-set S: full-set Exits: ((4 * (sext i32 (-1 + %offset + %numIterations) to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {((4 * (sext i32 %offset to i64))<nsw> + %input),+,4}<nw><%loop> U: full-set S: full-set Exits: ((4 * (zext i32 (-1 + %numIterations) to i64))<nuw><nsw> + (4 * (sext i32 %offset to i64))<nsw> + %input) LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %nexti = add nsw i32 %i, 1
 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,-2147483648) S: [1,-2147483648) Exits: %numIterations LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test-add-not-header
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is (-1 + %numIterations)
 ; CHECK-NEXT:  Loop %loop: max backedge-taken count is -1
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (-1 + %numIterations)
 ; CHECK-NEXT:   Predicates:
 ; CHECK:       Loop %loop: Trip multiple is 1

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

 ; CHECK-NEXT:  Classifying expressions for: @f
 ; CHECK-NEXT:    %storemerge23 = phi i32 [ 3, %entry ], [ %dec16, %for.inc13.3 ]
 ; CHECK-NEXT:    --> {3,+,-1}<nsw><%outer.loop> U: [1,4) S: [1,4) Exits: <<Unknown>> LoopDispositions: { %outer.loop: Computable, %for.cond6: Invariant, %inner.loop: Invariant }
 ; CHECK-NEXT:    %storemerge1921 = phi i32 [ 3, %outer.loop ], [ %dec, %for.end ]
 ; CHECK-NEXT:    --> {3,+,-1}<nuw><nsw><%for.cond6> U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %for.cond6: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %idxprom20 = zext i32 %storemerge1921 to i64
 ; CHECK-NEXT:    --> {3,+,4294967295}<nuw><nsw><%for.cond6> U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %for.cond6: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %arrayidx7 = getelementptr inbounds [1 x [4 x i16]], [1 x [4 x i16]]* @__const.f.g, i64 0, i64 0, i64 %idxprom20
-; CHECK-NEXT:    --> {(6 + @__const.f.g),+,8589934590}<nuw><%for.cond6> U: [0,-1) S: [-9223372036854775808,9223372036854775807) Exits: <<Unknown>> LoopDispositions: { %for.cond6: Computable, %outer.loop: Variant }
+; CHECK-NEXT:    --> {(6 + @__const.f.g)<nuw>,+,8589934590}<nuw><%for.cond6> U: [6,-1) S: [-9223372036854775808,9223372036854775807) Exits: <<Unknown>> LoopDispositions: { %for.cond6: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %i = load i16, i16* %arrayidx7, align 2
 ; CHECK-NEXT:    --> %i U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond6: Variant, %outer.loop: Variant }
 ; CHECK-NEXT:    %storemerge1822.lcssa.ph = phi i32 [ 0, %for.cond6 ]
 ; CHECK-NEXT:    --> 0 U: [0,1) S: [0,1)
 ; CHECK-NEXT:    %storemerge1822.lcssa.ph32 = phi i32 [ 3, %inner.loop ]
 ; CHECK-NEXT:    --> 3 U: [3,4) S: [3,4)
 ; CHECK-NEXT:    %storemerge1822.lcssa = phi i32 [ %storemerge1822.lcssa.ph, %if.end.loopexit ], [ %storemerge1822.lcssa.ph32, %if.end.loopexit31 ]
 ; CHECK-NEXT:    --> %storemerge1822.lcssa U: [0,4) S: [0,4)
 ; CHECK-NEXT:    %i1 = load i32, i32* @e, align 4
 ; CHECK-NEXT:    --> %i1 U: full-set S: full-set
 ; CHECK-NEXT:    %i2 = load volatile i32, i32* @b, align 4
 ; CHECK-NEXT:    --> %i2 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %for.cond6: Variant, %outer.loop: Variant }
 ; CHECK-NEXT:    %dec = add nsw i32 %storemerge1921, -1
 ; CHECK-NEXT:    --> {2,+,-1}<nsw><%for.cond6> U: [2,3) S: [2,3) Exits: <<Unknown>> LoopDispositions: { %for.cond6: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %inc.lcssa.lcssa = phi i32 [ 4, %for.inc13.3 ]
 ; CHECK-NEXT:    --> 4 U: [4,5) S: [4,5)
 ; CHECK-NEXT:    %retval.0 = phi i32 [ %i1, %if.end ], [ 0, %cleanup.loopexit ]
 ; CHECK-NEXT:    --> %retval.0 U: full-set S: full-set
 ; CHECK-NEXT:    %storemerge1921.3 = phi i32 [ 3, %for.end ], [ %dec.3, %for.end.3 ]
 ; CHECK-NEXT:    --> {3,+,-1}<nuw><nsw><%inner.loop> U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %inner.loop: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %idxprom20.3 = zext i32 %storemerge1921.3 to i64
 ; CHECK-NEXT:    --> {3,+,4294967295}<nuw><nsw><%inner.loop> U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %inner.loop: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %arrayidx7.3 = getelementptr inbounds [1 x [4 x i16]], [1 x [4 x i16]]* @__const.f.g, i64 0, i64 0, i64 %idxprom20.3
-; CHECK-NEXT:    --> {(6 + @__const.f.g),+,8589934590}<nuw><%inner.loop> U: [0,-1) S: [-9223372036854775808,9223372036854775807) Exits: <<Unknown>> LoopDispositions: { %inner.loop: Computable, %outer.loop: Variant }
+; CHECK-NEXT:    --> {(6 + @__const.f.g)<nuw>,+,8589934590}<nuw><%inner.loop> U: [6,-1) S: [-9223372036854775808,9223372036854775807) Exits: <<Unknown>> LoopDispositions: { %inner.loop: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %i7 = load i16, i16* %arrayidx7.3, align 2
 ; CHECK-NEXT:    --> %i7 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %inner.loop: Variant, %outer.loop: Variant }
 ; CHECK-NEXT:    %i8 = load volatile i32, i32* @b, align 4
 ; CHECK-NEXT:    --> %i8 U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %inner.loop: Variant, %outer.loop: Variant }
 ; CHECK-NEXT:    %dec.3 = add nsw i32 %storemerge1921.3, -1
 ; CHECK-NEXT:    --> {2,+,-1}<nsw><%inner.loop> U: [2,3) S: [2,3) Exits: <<Unknown>> LoopDispositions: { %inner.loop: Computable, %outer.loop: Variant }
 ; CHECK-NEXT:    %storemerge1921.lcssa25.3 = phi i32 [ %storemerge1921.3, %for.end.3 ]
 ; CHECK-NEXT:    --> %storemerge1921.lcssa25.3 U: [3,4) S: [3,4) Exits: <<Unknown>> LoopDispositions: { %outer.loop: Variant, %for.cond6: Invariant, %inner.loop: Invariant }

llvm/test/Analysis/ScalarEvolution/nsw.ll

 ; CHECK-NEXT:    --> {%p,+,8}<%bb> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb: Computable }
 ; CHECK-NEXT:    %tmp8 = add nsw i32 %i.01, 1
 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%bb> U: [1,-2147483648) S: [1,-2147483648) Exits: <<Unknown>> LoopDispositions: { %bb: Computable }
 ; CHECK-NEXT:    %p.gep = getelementptr double, double* %p, i32 %tmp8
 ; CHECK-NEXT:    --> {(8 + %p),+,8}<%bb> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb: Computable }
 ; CHECK-NEXT:    %phitmp = sext i32 %tmp8 to i64
 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%bb> U: [1,-9223372036854775808) S: [1,-9223372036854775808) Exits: <<Unknown>> LoopDispositions: { %bb: Computable }
 ; CHECK-NEXT:    %tmp9 = getelementptr inbounds double, double* %p, i64 %phitmp
-; CHECK-NEXT:    --> {(8 + %p),+,8}<%bb> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb: Computable }
+; CHECK-NEXT:    --> {(8 + %p),+,8}<nuw><%bb> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %bb: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @test1
 ; CHECK-NEXT:  Loop %bb: Unpredictable backedge-taken count.
 ; CHECK-NEXT:  Loop %bb: Unpredictable max backedge-taken count.
 ; CHECK-NEXT:  Loop %bb: Unpredictable predicated backedge-taken count.
 ;
 entry:
   %tmp = load double, double* %p, align 8    ; <double> [#uses=1]
   %tmp1 = fcmp ogt double %tmp, 2.000000e+00    ; <i1> [#uses=1]