[SCEV] Re-enable "Use nw flag and symbolic iteration count to sharpen ranges of AddRecs", attempt 3

[mkazantsev]

Summary

We can sharpen the range of a AddRec if we know that it does not
self-wrap and know the symbolic iteration count in the loop. If we can
evaluate the value of AddRec on the last iteration and prove that at least
one its intermediate value lies between start and end, then no-wrap flag
allows us to conclude that all of them also lie between start and end. So
the estimate of range can be improved to union of ranges of start and end.

Switched off by default, can be turned on by flag.

[mkazantsev]

llvm/test/Analysis/ScalarEvolution/no-wrap-symbolic-becount.ll

10

Unsigned range here can also be made [0,0,4294967296)...

[xbolva00]

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

548

remove todo

[mkazantsev]

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

548

Not until the zext is removed.

[mkazantsev]

Sharpened unsigend flag too.

[mkazantsev]

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

548

Ideally, we should be able to widen everything to i64. Currently IV gives up because zext(iv) is not an addrec after the range is sharpened. It's weird but fixable I think.

[efriedma]

llvm/lib/Analysis/ScalarEvolution.cpp

5705

I'm concerned that evaluating at iteration MaxBECount won't do what you want. In particular, if MaxBECount is larger than the number of steps required to violate nw, then the way you're comparing Start and End doesn't work.

The actual backedge-taken count at runtime can't be that large, of course, but MaxBECount is an approximation in general; I don't think we make any relevant guarantees. In particular, if the step isn't constant, we can't get this right.

I think you could explicitly compute the largest number of non-wrapping iterations, and then take the minimum of that and MaxBECount to compute the "real" maximum count.

5744

At first I wasn't sure what isKnownPredicate(LEPred, Start, End)) was checking, but then I figured out it's accounting for the possibility of crossing INT_MAX/UINT_MAX, since nw doesn't exclude that. I think an alternate way of satisfying this condition would be to check for nsw/nuw.

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

5705

I think you could explicitly compute the largest number of non-wrapping iterations, and then take the minimum of that and MaxBECount to compute the "real" maximum count.

Unrelated to the patch directly, but I suppose we could also use this to clamp down the computed MaxBECount directly, if we do not already do so? But we still won't have a reliable way to indicate that the computed count can be used directly I think.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

5705

I don't think this situation is possible, but I don't have strong enough arguments to prove that. We can add an extra check that step * max num iterations must be known less than UINT_MAX for this type.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

5705

I'll think about adding clamp into MaxBECount computation. I'm concerned that SCEV may not always be able to derive required facts from clamped expressions. Let's not do it in this patch and just add a check against this situation.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

5744

nuw/nsw checks should be, in different ways, already incorporated inside of isKnownPredicate.

[mkazantsev]

Added check to address Eli's comment. Now we make sure that we can *prove* nw.

[efriedma]

LGTM

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

5757

Actually we do not need to prove anything about V1. Knowing start < end && step is positive is enough, as well as start > end is negative.

[mkazantsev]

Removed V1 check which is actually not needed.

[nikic]

I've reverted this change because it causes large compile-time regressions without a commensurate change in codegen: https://llvm-compile-time-tracker.com/compare.php?from=cc175c2cc8e638462bab74e0781e06f9b6eb5017&to=905101c36025fe1c8ecdf9a20cd59db036676073&stat=instructions For example, we have a 4% regression on mafft without any codegen change. This either needs a more efficient implementation or a stronger motivation.

[mkazantsev]

I'll try using less powerful proof methods here; isKnownPredicate might be an overkill.

[fhahn]

llvm/lib/Analysis/ScalarEvolution.cpp

5705

I started working on using this info for MaxBECount: D89586. Still needs some further work though.

[nikic]

I've reverted this change again for a couple of reasons:

First, the compile-time impact is now better, but still larger than the change justifies (at least without knowing the broader context): https://llvm-compile-time-tracker.com/compare.php?from=fbd62fe60fb2281ca33da35dc25ca3c87ec0bb51&to=32b72c3165bf65cca2e8e6197b59eb4c4b60392a&stat=instructions The mafft regression is no longer 4%, but it's still 3%.

Less importantly, I don't think the logic here is quite correct. The first issue is the use of the unionWith() API, which probably doesn't do what you want it to do. The way it is used here, it will return the smallest union of Start and End, which is not necessarily the range [Start, End], it can also be Start], [End, if we simplify this down to single-element ranges. Here is a test-case that I think illustrates the issue, if I didn't mess it up:

define i32 @test_02(i32 %start, i32* %p, i32* %q) {
; CHECK-LABEL: 'test_02'
; CHECK-NEXT:  Classifying expressions for: @test_02
; CHECK-NEXT:    %zext = zext i32 %start to i64
; CHECK-NEXT:    --> (zext i32 %start to i64) U: [0,4294967296) S: [0,4294967296)
; CHECK-NEXT:    %shl = shl i64 %zext, 31
; CHECK-NEXT:    --> (2147483648 * (zext i32 %start to i64))<nuw><nsw> U: [0,9223372034707292161) S: [0,9223372034707292161)
; CHECK-NEXT:    %indvars.iv = phi i64 [ %indvars.iv.next, %loop ], [ %shl, %entry ]
; CHECK-NEXT:    --> {(2147483648 * (zext i32 %start to i64))<nuw><nsw>,+,-1}<nsw><%loop> U: [-9223372036854775808,9223372034707292161) S: [-9223372036854775808,9223372034707292161) Exits: -9223372036854775806 LoopDispositions: { %loop: Computable }
; CHECK-NEXT:    %indvars.iv.next = add nsw i64 %indvars.iv, -1
; CHECK-NEXT:    --> {(-1 + (2147483648 * (zext i32 %start to i64))<nuw><nsw>)<nsw>,+,-1}<nw><%loop> U: full-set S: [-1,-9223372036854775806) Exits: -9223372036854775807 LoopDispositions: { %loop: Computable }
; CHECK-NEXT:  Determining loop execution counts for: @test_02
; CHECK-NEXT:  Loop %loop: backedge-taken count is (9223372036854775806 + (2147483648 * (zext i32 %start to i64))<nuw><nsw>)<nuw>
; CHECK-NEXT:  Loop %loop: max backedge-taken count is -2147483650
; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is (9223372036854775806 + (2147483648 * (zext i32 %start to i64))<nuw><nsw>)<nuw>
; CHECK-NEXT:   Predicates:
; CHECK:       Loop %loop: Trip multiple is 1
;
entry:
  %zext = zext i32 %start to i64
  %shl = shl i64 %zext, 31
  br label %loop

loop:                                             ; preds = %backedge, %entry
  %indvars.iv = phi i64 [ %indvars.iv.next, %loop ], [ %shl, %entry ]
  %cond = icmp eq i64 %indvars.iv, -9223372036854775806
  %indvars.iv.next = add nsw i64 %indvars.iv, -1
  br i1 %cond, label %exit, label %loop

exit:                                             ; preds = %loop
  ret i32 0
}

Note that the signed range of %indvars.iv.next is [-1,-9223372036854775806), while it should be [-9223372036854775807,9223372034707292161), give or take a few off by one errors.

This could be partially avoided by passing a sign preference to unionWith(). However, even with a sign preference, this may return a smaller wrapping range, if that avoid returning a full set. Similarly, the signed/unsigned ranges you request for start/end are also only sign preferences, you may still get back a wrapping range. I haven't followed it through in detail, but I don't think the logic is correct for wrapping ranges.

[mkazantsev]

That's a good point, thanks! I'll see what I can do.

[mkazantsev]

@nikic the output on your test is same with and without the patch. The point of checking of range's start and end is valid, but not in this case.

[mkazantsev]

Scratch that, I used wrong revision.

[mkazantsev]

@nikic I've checked in your test separately and added handling for it here, to make sure that its behavior does not change. Proof methods is reduced to isKnownPredicateViaConstantRanges which does not create new SCEVs and therefore should not lead to recursive behavior. Could you please confirm that the compile time is OK with this version?

[nikic]

Unfortunately the compile-time issue still exists and is not materially affected by the switch to isKnownPredicateViaConstantRanges(). I've looked at callgrind profiles for partSalignmm.c, which has a 5% regression with this change, and found that the additional 166M instructions are spread roughly as follows:

• 72M: evaluateAtIteration
• 35M: isKnownPredicate for the TODO check
• 32M: Various SCEV expression construction for the TODO check
• 9M: computeMaxBackedgeTakenCount

Resolving the TODO would be a significant optimization, but unfortunately the largest part of the cost is inside evaluateAtIteration(), which seems like a more fundamental part of this calculation.

[Meinersbur]

Is this patch being reverted again? It also broke the Polly buildbots:

Failed Tests (1):
  Polly :: ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll

[MaskRay]

In D89381#2343087, @Meinersbur wrote:

Is this patch being reverted again? It also broke the Polly buildbots:

Failed Tests (1):
  Polly :: ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll

Verified this did break the Polly test. Reverted. Changed nikic to a blocking reviewer.

[Meinersbur]

Thanks, The buildbot is green again: http://lab.llvm.org:8014/#/builders/5/builds/5

I would work on a fix (an integer range changed), but it would cause failure again if this patch was reverted.

[mkazantsev]

How come that polly buildbot breach is a reason for a revert?

[mkazantsev]

Hi @nikic, evaluateAtIteration is supposed to be completely free in this case, returning simply a+b. Do you have any info regarding what types of start/step are causing this?

[MaskRay]

In D89381#2343569, @mkazantsev wrote:

How come that polly buildbot breach is a reason for a revert?

The patch has been reverted multiple times (it is likely there are other unhandled issues) and the polly test demonstrates an internal difference which did not seem cosmetic. Plus nikic had several unaddressed comments. Hence the revert.

[lebedev.ri]

I think if we want to gatekeep new improvements based on their compile time impact, we should document that first in an appropriate documentation.

[mkazantsev]

All comments have been addressed, except for the compile time issue, and we are trying to figure out what case we are dealing with. I have no info about what, how and in which config is being regressed. https://llvm-compile-time-tracker.com/ gives no info in this. This is not a part of LLVM test suite, and the change is not introducing a functional bug.

I would expect that, if the compile time impact is treated as a problem, this problem would be filed on bugs.llvm.com. I will gladly help to resolve this issue once I have info about what, how, in which circumstances and which environment has regressed. I don't think that reverting patches without providing info about problematic tests is a constructive approach that will move us anywhere.

As for Polly, I'm pretty sure it wouldn't be a big problem to update the test. It's not the part of core LLVM, and this patch can only sharpen the analyzes results. If the polly test suffers from more precise SCEV ranges, it's clearly not a SCEV problem.

[mkazantsev]

Fixed Polly test. Looks like a clear improvement to me.

[xbolva00]

+1

[Meinersbur]

In D89381#2343856, @mkazantsev wrote:

Fixed Polly test. Looks like a clear improvement to me.

I agree, with this patch Polly is able to deduce that the range of k is between zero and 1024*1024 (instead of MAX_INT)

[mkazantsev]

Now isKnownPredicateViaConstantRanges is used for TODO check too, and Step is limited to the constant. If it still is not helping, then I have no slightest clue what it can be and need a reproducer for the problem.

[fhahn]

In D89381#2344199, @mkazantsev wrote:

Now isKnownPredicateViaConstantRanges is used for TODO check too, and Step is limited to the constant. If it still is not helping, then I have no slightest clue what it can be and need a reproducer for the problem.

From what I understand the revert commit specifically mentioned a large (+3%) regression in compile-time for mafft from CTMark, which is part of llvm-test-suite, built with -O3. And in particular mentioned a larger regression in a specific file of mafft (partSalignmm.c). IIUC it should be possible to reproduce the regression by building that file with -O3 for X86 with release builds (no assertions) with and without the change?

[mkazantsev]

@nikic is there a way to measure the CT impact of this version without actually merging it? If it's still too bad, please provide me something that I can analyze (either C++ test + run instructions or IR test).

[mkazantsev]

In D89381#2344217, @fhahn wrote:

In D89381#2344199, @mkazantsev wrote:

Now isKnownPredicateViaConstantRanges is used for TODO check too, and Step is limited to the constant. If it still is not helping, then I have no slightest clue what it can be and need a reproducer for the problem.

From what I understand the revert commit specifically mentioned a large (+3%) regression in compile-time for mafft from CTMark, which is part of llvm-test-suite, built with -O3. And in particular mentioned a larger regression in a specific file of mafft (partSalignmm.c). IIUC it should be possible to reproduce the regression by building that file with -O3 for X86 with release builds (no assertions) with and without the change?

I don't have it in my tree; is it https://github.com/llvm/llvm-test-suite/tree/master/CTMark what you are referencing? I can try this one...

[fhahn]

In D89381#2344230, @mkazantsev wrote:

In D89381#2344217, @fhahn wrote:

In D89381#2344199, @mkazantsev wrote:

Now isKnownPredicateViaConstantRanges is used for TODO check too, and Step is limited to the constant. If it still is not helping, then I have no slightest clue what it can be and need a reproducer for the problem.

From what I understand the revert commit specifically mentioned a large (+3%) regression in compile-time for mafft from CTMark, which is part of llvm-test-suite, built with -O3. And in particular mentioned a larger regression in a specific file of mafft (partSalignmm.c). IIUC it should be possible to reproduce the regression by building that file with -O3 for X86 with release builds (no assertions) with and without the change?

I don't have it in my tree; is it https://github.com/llvm/llvm-test-suite/tree/master/CTMark what you are referencing? I can try this one...

Yes, it's part of the separate llvm-test-suite repo, the sources for mafft specifically are here https://github.com/llvm/llvm-test-suite/tree/master/MultiSource/Benchmarks/mafft. The CTMark directory only contains links to the actual sources, because it is only a small subset targeted at tracking compile-time.

[fhahn]

It would probably be helpful to add a short snippet about how to build & run CTMark to reproduce the setup on the compile-time tracker website (clone, cmake, build and llvm-lit commands to run). And maybe linking to https://llvm.org/docs/TestSuiteGuide.html (and improving this page :))

[nikic]

Thank you @fhahn for providing some context. I have updated https://llvm-compile-time-tracker.com/about.php to add some basic reproducing instructions as well.

For reference, here are the results for the current patch, which still has roughly the same characteristics: https://llvm-compile-time-tracker.com/compare.php?from=4b7dafd9046f0ceaadacaafe0ea4a1fb00cf70a5&to=c713c1ef75612a3dae1ef4b99f766e0c7784381f&stat=instructions

In D89381#2343573, @mkazantsev wrote:

Hi @nikic, evaluateAtIteration is supposed to be completely free in this case, returning simply a+b. Do you have any info regarding what types of start/step are causing this?

I added some debug output and compiled the previously mentioned partSalignmm.c test case, with the following output: https://gist.github.com/nikic/40d676b9eeacee3ed38cb896a111e9f1 I couldn't say which ones of these are particularly slow though, and nothing seems particularly out of the ordinary there.

As you say, evaluateAtIteration() is simply a+b in this case, but this is not necessarily free, because potentially expensive expression folding may be involved. That expression folding is uncached, unless the expression doesn't fold.

I think the core issue here is that this optimization is a bit of a layering violation: All the existing getRangeRef() logic just recursively combines ranges of existing SCEV expressions. It does not create any new SCEV expressions. (Apart from calculating the constant max BE count, which is at least a cached calculation.)

I was going to suggest that we could use getSCEVAtScope on the parent loop to at least make this a cached addrec exit value, but that would not cover your motivating example (though probably would cover most other test changes). Unfortunately I'm not familiar enough with SCEV to make a good suggestion here.

[mkazantsev]

What's the impact on O1 and O2 modes?

[mkazantsev]

This comment was removed by mkazantsev.

[mkazantsev]

Let's try to cache symbolic max BE count, it's the only thing that still can be improved here.

[mkazantsev]

Rebased using caching version of BE count computation. Should be cheaper now.

[mkazantsev]

@nikic @fhahn thanks for help with the reproduction! I think I can reproduce the problem locally now. Investigating where the ticks are spent and why.

[mkazantsev]

Need to investigate why End computation is so expensive.

[mkazantsev]

The common pattern where the CT drops that I ovserve is following: Start is a constant (in most cases zero), Step is also a constant and MaxBECount is a pretty big expression. The time is spent in attempts to prove nuw/nsw flags on End computation in this case.

[mkazantsev]

Here's the study that I made on the example of rdopt_coding_state. Units below are Ir (hopefully it's "instructions retired") on compilation with clang O3.

Almost queries are made for start = 0, constant step & BE count expression that varies from small to really huge expressions.
IR without patch: 220370413
IR with previous version of patch (no SCEV size limits): 224114149 (2% regression).
When I started limiting the size of IRs involved in transform, the dynamics was following:
Limit = 2: 220517261
Limit = 3: 221761742
Limit = 4-6: 222841240

So starting size 4, we have 1% regression on this test (but wide picture might be different). In the patch I set the limit of 6 because it's the minimum value needed to pass all tests in the way as they passed without limits. @nikic could you please evaluate this one?

[nikic]

Here are the numbers for the new patch: https://llvm-compile-time-tracker.com/compare.php?from=13edfcc97d29574d1d38ded4fa9c2af6e6519472&to=45962d4244d46b1df0618701686a8756c6fb6b78&stat=instructions The geomean regression is now at 0.6% and the mafft regression is at a bit over 2%.

[mkazantsev]

In that case, I see no other way than merge it with threshold 0 for clang. Frankly, I don't care if we lose 2% CT on some corner case tests if we get better SCEV ranges from it. Limiting SCEV sizes is a dirty and unstable hack, so it's better be an "all or nothing" flag.

[xbolva00]

It would be great to get some benchmark data to see runtime performance / improvements as well.

[mkazantsev]

This patch alone does not give any improvements itself. However, it's an important enabling step for fighting incomplete IV widening (see dependent patches), which is a source of performance problems in many various cases, mostly with decrementing loops. I only ran Java benchmarks and see up to 30% boosts in some cases.

[mkazantsev]

@nikic @MaskRay any reasons to keep this out? It's effectively an NFC now. If we want to further measure its impact on compile time & performance of clang benchmarks, it can be a separate change switching the flag value.

[lebedev.ri]

@nikic any reason for this compile time re-measuring dance instead of explaining the onboarding process?
(I.e. telling https://github.com/max-azul to make a github fork off https://github.com/llvm/llvm-project
into https://github.com/max-azul/llvm-project and adding that as a tracked remote for http://llvm-compile-time-tracker.com/ ?
(then, push branch to be measured as perf/<...>, and it will get measured))

Current numbers: (+0.6% geomean)
https://llvm-compile-time-tracker.com/compare.php?from=0ac56e8eaaeb41b59a952fa465872f647c930347&to=b36e80eaf4b4e35c74d814babe722160ef164f9b&stat=instructions

In D89381#2355899, @mkazantsev wrote:

@nikic @MaskRay any reasons to keep this out? It's effectively an NFC now. If we want to further measure its impact on compile time & performance of clang benchmarks, it can be a separate change switching the flag value.

I don't see any reasons, especially if this doesn't change the default just yet.

[nikic]

LG for landing under the flag.

I already landed a couple of SCEV improvements on Sunday that improved compile-time (while also improving nowrap inference), and am still pursuing some more leads, so I hope we can drop the flag in the future.

llvm/lib/Analysis/ScalarEvolution.cpp

5709

You can use the recently added getMinusOne() here.

5738

It might make more sense to use getRangeRef(Start, SignHint) and getRangeRef(End, SignHint) here, rather than going SignHint -> IsSigned -> SignHint.

5747

You can use isWrappedSet() and isSignWrappedSet() here (there are some special cases due to the half-open range).

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

5738

Good point!

5747

Will do.

llvm/include/llvm/Analysis/ScalarEvolution.h

private:
   /// copied if its needed for longer.
   const ConstantRange &getRangeRef(const SCEV *S, RangeSignHint Hint);
 
   /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Stop}.
   /// Helper for \c getRange.
   ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Stop,
                                     const SCEV *MaxBECount, unsigned BitWidth);
 
+  /// Determines the range for the affine non-self-wrapping SCEVAddRecExpr {\p
+  /// Start,+,\p Stop}<nw>.
+  ConstantRange getRangeForAffineNoSelfWrappingAR(const SCEVAddRecExpr *AddRec,
+                                                  const SCEV *MaxBECount,
+                                                  unsigned BitWidth,
+                                                  RangeSignHint SignHint);
+
   /// Try to compute a range for the affine SCEVAddRecExpr {\p Start,+,\p
   /// Stop} by "factoring out" a ternary expression from the add recurrence.
   /// Helper called by \c getRange.
   ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Stop,
                                      const SCEV *MaxBECount, unsigned BitWidth);
 
   /// We know that there is no SCEV for the specified value.  Analyze the
   /// expression.

llvm/lib/Analysis/ScalarEvolution.cpp

if (AddRec->isAffine()) {
             ConservativeResult.intersectWith(RangeFromAffine, RangeType);
 
         auto RangeFromFactoring = getRangeViaFactoring(
             AddRec->getStart(), AddRec->getStepRecurrence(*this), MaxBECount,
             BitWidth);
         ConservativeResult =
             ConservativeResult.intersectWith(RangeFromFactoring, RangeType);
       }
+
+      // Now try symbolic BE count and more powerful methods.
+      MaxBECount = computeMaxBackedgeTakenCount(AddRec->getLoop());
+      if (!isa<SCEVCouldNotCompute>(MaxBECount) &&
+          getTypeSizeInBits(MaxBECount->getType()) <= BitWidth &&
+          AddRec->hasNoSelfWrap()) {
+        auto RangeFromAffineNew = getRangeForAffineNoSelfWrappingAR(
+            AddRec, MaxBECount, BitWidth, SignHint);
+        ConservativeResult =
+            ConservativeResult.intersectWith(RangeFromAffineNew, RangeType);
+      }
     }
 
     return setRange(AddRec, SignHint, std::move(ConservativeResult));
   }
 
   if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
     // Check if the IR explicitly contains !range metadata.
     Optional<ConstantRange> MDRange = GetRangeFromMetadata(U->getValue());
ConstantRange ScalarEvolution::getRangeForAffineAR(const SCEV *Start,
   ConstantRange UR = getRangeForAffineARHelper(
       getUnsignedRangeMax(Step), getUnsignedRange(Start),
       MaxBECountValue, BitWidth, /* Signed = */ false);
 
   // Finally, intersect signed and unsigned ranges.
   return SR.intersectWith(UR, ConstantRange::Smallest);
 }
 
+ConstantRange ScalarEvolution::getRangeForAffineNoSelfWrappingAR(
+    const SCEVAddRecExpr *AddRec, const SCEV *MaxBECount, unsigned BitWidth,
+    ScalarEvolution::RangeSignHint SignHint) {
+  assert(AddRec->isAffine() && "Non-affine ARs are not suppored!\n");
+  assert(AddRec->hasNoSelfWrap() &&
+         "This only works for non-self-wrapping AddRecs!");
+  const bool IsSigned = SignHint == HINT_RANGE_SIGNED;
+  const SCEV *Step = AddRec->getStepRecurrence(*this);
+  ICmpInst::Predicate LEPred =
+      IsSigned ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
+  ICmpInst::Predicate GEPred =
+      IsSigned ? ICmpInst::ICMP_SGE : ICmpInst::ICMP_UGE;
+  const SCEV *Start = AddRec->getStart();
+  const SCEV *End = AddRec->evaluateAtIteration(MaxBECount, *this);
+
+  // We know that there is no self-wrap. Let's take Start and End values and
+  // look at all intermediate values V1, V2, ..., Vn that IndVar takes during
+  // the iteration. They either lie inside the range [Min(Start, End),
+  // Max(Start, End)] or outside it:
+  //
+  // Case 1:   RangeMin    ...    Start V1 ... VN End ...           RangeMax;
+  // Case 2:   RangeMin Vk ... V1 Start    ...    End Vn ... Vk + 1 RangeMax;
+  //
+  // No self wrap flag guarantees that the intermediate values cannot be BOTH
+  // outside and inside the range [Min(Start, End), Max(Start, End)]. Using that
+  // knowledge, let's try to prove that we are dealing with Case 1. It is so if
+  // both End and V1 lie at the same side of Start.
+  ConstantRange StartRange =
+      IsSigned ? getSignedRange(Start) : getUnsignedRange(Start);
+  ConstantRange EndRange =
+      IsSigned ? getSignedRange(End) : getUnsignedRange(End);
+  ConstantRange RangeBetween = StartRange.unionWith(EndRange);
+  // If they already cover full iteration space, we will know nothing useful
+  // even if we prove what we want to prove.
+  if (RangeBetween.isFullSet())
+    return RangeBetween;
+
+  // TODO: Too big expressions here may lead to exponential explosions on
+  // recursion. So we limit the size of operands to avoid this. Maybe in the
+  // future we should find a better way to deal with it.
+  const unsigned Threshold = 3;
+  if (Start->getExpressionSize() > Threshold ||
+      Step->getExpressionSize() > Threshold)
+    return ConstantRange::getFull(BitWidth);
+  const Loop *L = AddRec->getLoop();
+  const SCEV *V1 = getAddExpr(Start, Step);
+
+  if (isKnownPositive(Step) && isKnownPredicate(LEPred, Start, End)) {
+    if (!isLoopBackedgeGuardedByCond(L, LEPred, Start, V1))
+      return ConstantRange::getFull(BitWidth);
+  } else if (isKnownNegative(Step) && isKnownPredicate(GEPred, Start, End)) {
+    if (!isLoopBackedgeGuardedByCond(L, GEPred, Start, V1))
+      return ConstantRange::getFull(BitWidth);
+  } else
+    return ConstantRange::getFull(BitWidth);
+
+  // All intermediate values lie between Start and End.
+  return RangeBetween;
+}
+
 ConstantRange ScalarEvolution::getRangeViaFactoring(const SCEV *Start,
                                                     const SCEV *Step,
                                                     const SCEV *MaxBECount,
                                                     unsigned BitWidth) {
   //    RangeOf({C?A:B,+,C?P:Q}) == RangeOf(C?{A,+,P}:{B,+,Q})
   // == RangeOf({A,+,P}) union RangeOf({B,+,Q})
 
   struct SelectPattern {
     Value *Condition = nullptr;
     APInt TrueValue;
     APInt FalseValue;
 
     explicit SelectPattern(ScalarEvolution &SE, unsigned BitWidth,
                            const SCEV *S) {

llvm/test/Analysis/ScalarEvolution/no-wrap-symbolic-becount.ll

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt < %s -S -analyze -scalar-evolution | FileCheck %s
 
 define i32 @test_01(i32 %start, i32* %p, i32* %q) {
 ; CHECK-LABEL: 'test_01'
 ; CHECK-NEXT:  Classifying expressions for: @test_01
 ; CHECK-NEXT:    %0 = zext i32 %start to i64
 ; CHECK-NEXT:    --> (zext i32 %start to i64) U: [0,4294967296) S: [0,4294967296)
 ; CHECK-NEXT:    %indvars.iv = phi i64 [ %indvars.iv.next, %backedge ], [ %0, %entry ]
-; CHECK-NEXT:    --> {(zext i32 %start to i64),+,-1}<nsw><%loop> U: [-4294967295,4294967296) S: [-4294967295,4294967296) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
+; CHECK-NEXT:    --> {(zext i32 %start to i64),+,-1}<nsw><%loop> U: [-4294967295,4294967296) S: [0,4294967296) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv = phi i32 [ %start, %entry ], [ %iv.next, %backedge ]
 ; CHECK-NEXT:    --> {%start,+,-1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %iv.next = add i32 %iv, -1
 ; CHECK-NEXT:    --> {(-1 + %start),+,-1}<%loop> U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %index = zext i32 %iv.next to i64
 ; CHECK-NEXT:    --> (zext i32 {(-1 + %start),+,-1}<%loop> to i64) U: [0,4294967296) S: [0,4294967296) Exits: <<Unknown>> LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %store.addr = getelementptr i32, i32* %p, i64 %index
 ; CHECK-NEXT:    --> ((4 * (zext i32 {(-1 + %start),+,-1}<%loop> to i64))<nuw><nsw> + %p) U: full-set S: full-set Exits: <<Unknown>> LoopDispositions: { %loop: Computable }

llvm/test/Transforms/IndVarSimplify/X86/eliminate-trunc.ll

 ; Widen NE as signed.
 define void @test_10(i32 %n) {
 ; CHECK-LABEL: @test_10(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[N:%.*]], 100
 ; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[TMP0]] to i64
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i64 [[TMP1]], 90
 ; CHECK-NEXT:    [[UMIN:%.*]] = select i1 [[TMP2]], i64 [[TMP1]], i64 90
-; CHECK-NEXT:    [[TMP3:%.*]] = add i64 [[UMIN]], -99
+; CHECK-NEXT:    [[TMP3:%.*]] = add nuw nsw i64 [[UMIN]], -99
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ -100, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1
 ; CHECK-NEXT:    [[EXITCOND:%.*]] = icmp ne i64 [[IV_NEXT]], [[TMP3]]
 ; CHECK-NEXT:    br i1 [[EXITCOND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void

llvm/test/Transforms/IndVarSimplify/promote-iv-to-eliminate-casts.ll

 ; CHECK-NEXT:    br label [[LOOPEXIT]]
 ; CHECK:       loopexit:
 ; CHECK-NEXT:    ret void
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ], [ [[TMP0]], [[PREHEADER]] ]
 ; CHECK-NEXT:    [[EL:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[INDVARS_IV]]
 ; CHECK-NEXT:    store atomic i32 0, i32* [[EL]] unordered, align 4
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
-; CHECK-NEXT:    [[LOOPCOND:%.*]] = icmp slt i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[LOOPCOND:%.*]] = icmp ult i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOPCOND]], label [[LOOPEXIT_LOOPEXIT:%.*]], label [[LOOP]]
 ;
 
 entry:
   %len = load i32, i32* %p, align 4, !range !0
   %zero_check = icmp eq i32 %len, 0
   br i1 %zero_check, label %loopexit, label %preheader
 

 ; CHECK-NEXT:    br label [[LOOPEXIT]]
 ; CHECK:       loopexit:
 ; CHECK-NEXT:    ret void
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ], [ [[TMP1]], [[PREHEADER]] ]
 ; CHECK-NEXT:    [[EL:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[INDVARS_IV]]
 ; CHECK-NEXT:    store atomic i32 0, i32* [[EL]] unordered, align 4
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
-; CHECK-NEXT:    [[LOOPCOND:%.*]] = icmp slt i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[LOOPCOND:%.*]] = icmp ult i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    br i1 [[LOOPCOND]], label [[LOOPEXIT_LOOPEXIT:%.*]], label [[LOOP]]
 ;
 
 entry:
   %len = load i32, i32* %p, align 4, !range !0
   %len.plus.1 = add i32 %len, 1
   %zero_check = icmp eq i32 %len, 0
   br i1 %zero_check, label %loopexit, label %preheader

 ; CHECK:       loopexit.loopexit:
 ; CHECK-NEXT:    br label [[LOOPEXIT]]
 ; CHECK:       loopexit:
 ; CHECK-NEXT:    ret void
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], [[LOOP]] ], [ [[TMP0]], [[PREHEADER]] ]
 ; CHECK-NEXT:    [[EL:%.*]] = getelementptr inbounds i32, i32* [[A:%.*]], i64 [[INDVARS_IV]]
 ; CHECK-NEXT:    store atomic i32 0, i32* [[EL]] unordered, align 4
-; CHECK-NEXT:    [[LOOPCOND:%.*]] = icmp slt i64 [[INDVARS_IV]], 1
+; CHECK-NEXT:    [[LOOPCOND:%.*]] = icmp ult i64 [[INDVARS_IV]], 1
 ; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nsw i64 [[INDVARS_IV]], -1
 ; CHECK-NEXT:    br i1 [[LOOPCOND]], label [[LOOPEXIT_LOOPEXIT:%.*]], label [[LOOP]]
 ;
 
 entry:
   %len = load i32, i32* %p, align 4, !range !0
   %len.minus.1 = add nsw i32 %len, -1
   br i1 %cond, label %if.true, label %if.false

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

;
   %ext = sext i32 %iv to i64
   call void @consume.i64(i64 %ext)
   br i1 %be.cond, label %loop, label %leave
 
   leave:
   ret i32 22
 }
 
 ; TODO: We don't really need trunc/zext here because when iv.next overflows,
 ; its value is not used.
 define i32 @test11(i32 %start, i32* %p, i32* %q) {
 ; CHECK-LABEL: @test11(
 ; 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:    [[TMP1:%.*]] = trunc i64 [[INDVARS_IV]] to i32
-; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i32 [[TMP1]], -1
-; CHECK-NEXT:    [[COND:%.*]] = icmp eq i64 [[INDVARS_IV]], 0
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[INDEX:%.*]] = zext i32 [[IV_NEXT]] to i64
 ; CHECK-NEXT:    [[STORE_ADDR:%.*]] = getelementptr i32, i32* [[P:%.*]], i64 [[INDEX]]
 ; 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:    [[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:    ret i32 0
 ; CHECK:       failure:
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   br label %loop

 
 failure:
   unreachable
 }
 
 define i32 @test12(i32 %start, i32* %p, i32* %q) {
 ; CHECK-LABEL: @test12(
 ; 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:    [[IV:%.*]] = phi i32 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[IV]], 0
 ; CHECK-NEXT:    br i1 [[COND]], label [[EXIT:%.*]], label [[BACKEDGE]]
 ; CHECK:       backedge:
-; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[INDVARS_IV]] to i32
-; CHECK-NEXT:    [[IV_NEXT:%.*]] = add i32 [[TMP1]], -1
+; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
 ; CHECK-NEXT:    [[INDEX:%.*]] = zext i32 [[IV_NEXT]] to i64
 ; CHECK-NEXT:    [[STORE_ADDR:%.*]] = getelementptr i32, i32* [[P:%.*]], i64 [[INDEX]]
 ; 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:    [[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:    ret i32 0
 ; CHECK:       failure:
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   br label %loop