[SCEV][LoopVectorize] Allow ScalarEvolution to make assumptions about overflows

[sbaranga]

Summary

Add a new pass - AssumingScalarEvolution - that extends
SCEV, but can make assumptions and generate code that
can check these assumptions. This pass uses the normal
ScalarEvolution pass for anything outside the current
analyzed loop, but uses its own data structures to handle
the SCEVs within the loop. For now, the pass assumes
that chrec expressions will not overflow.

The AssumingScalarEvolution pass can add checks for the
made assumptions, so that a loop can be versioned.

We use this pass in order to add runtime overflow checks
in the Loop Vectorize pass of expressions which can
in theory overflow and would prevent the vectorization
a loop. Also note that the runtime checks will almost always
pass, since having an overflow is usually a sign of a
coding error on the part of user.

The main reasons behind inheriting from ScalarEvolution:
Since ScalarEvolution maintains its own cache for various
results, making any assumption would likely require invalidating
the entire cache.

This way we can use the new pass as an almost drop-in
replacement for ScalarEvolution. The users that are doing
a transformation would have to know about it in order to add
the checks.

However, there are probably a lot more ways in which this could
be implemented.

Any comments are much appreciated!

Thanks,
Silviu

[hfinkel]

Thanks for working on this! cc'ing Andy in case he has an opinion regarding the general approach.

include/llvm/Analysis/ScalarEvolution.h

750

Are these two methods special in theory, in this context, or in the future would overrides for more methods be useful?

1207

Don't use 'chrec' here without defining it.

1258

You should clear the cache here?

lib/Analysis/ScalarEvolution.cpp

8943

Given that the SCEVs are uniqued, you could at least eliminate those that are structurally identical easily.

lib/Transforms/Vectorize/LoopVectorize.cpp

2746

Line too long?

[atrick]

Overall, it's great to see something like this working in practice. In the past, several alternatives have been discussed. IIRC the main objection to this approach is that SCEV could make assumptions that are not necessary for the optimization leading to overhead for unnecessary checks.

Given this is a major design decision, it would be good to have feedback from anyone who has done a lot of work in the area (thanks to Hal for the review). What about Sanjoy, Arnold (especially for the vectorizer change), MichaelZ, AdamN ??

I don't see a major problem with this approach. Just a few comments on the implementation...

I'm afraid that iterating over a DenseMap will produce SCEV expressions and IR checks in a nondeterministic order. We usually fix this with a MapVector.

+ AssumptionMapTy::iterator getLoopAssumptionBegin(const Loop *L) {

I don't see AnalyzedLoop being initialized in the ctor:

+ AssumingScalarEvolution::AssumingScalarEvolution() :
+ ScalarEvolution(false, ID), SE(nullptr) {

See Instruction::getModule()

+ Module *M = Loc->getParent()->getParent()->getParent();

On most targets, I think it's more efficient to check the high bits for overflow. e.g.

if ((a + 0x800000) & 0xffffff000000) overflow

Instead of:

+ if (Signed) {
+ APInt CmpMinValue = APInt::getSignedMinValue(DstBits).sext(SrcBits);
+ ConstantInt *CTMin = ConstantInt::get(M->getContext(), CmpMinValue);
+ Value *MinCheck = OFBuilder.CreateICmp(ICmpInst::ICMP_SLT,
+ TripCount,
+ CTMin);
+ TripCountCheck = OFBuilder.CreateOr(TripCountCheck, MinCheck);
+ }

[atrick]

Adding reviewers...

[sanjoy]

I'll make it a point to do a more detailed review this week, but I
have a high level question:

Instead of a separate AssumingScalarEvolution, why not have an
interface like:

NoOverflowResult ScalarEvolution::proveNoOverflow(SCEVAddRecExpr

*AddRec, FlagType, bool CanAddAssumptions);

NoOverflowResult can be Yes, No or (if CanAddAssumptions is true) a
predicate that, if satisfied, will guarantee AddRec does not overflow
in the FlagType sense. Then the client can choose if it is profitable
to actually emit the predicate if it is cheap enough relative to expected
payoff.

A much more general interface could be

Result ScalarEvolution::provePredicate(CmpInst::Pred, SCEV *LHS, SCEV *RHS)

and have it return one of "Yes | No | Guarded (Predicate)"

Then not only can you ask the "sext{addrec} == addrec{sext}" question
to check for no-wrap, but also push more general logic into
ScalarEvolution as needed in the future (i.e. is this add-rec equal to this
other add-rec at any iteration? if not, can I make it so by adding runtime
checks?).

• Sanjoy

[sbaranga]

Hi Hal,

Thanks for having a look! I've only replied to comments related to the design for now. I think we can get the others after we've converged on some conclusion.

Thanks,
Silviu

include/llvm/Analysis/ScalarEvolution.h

750

I think they are special because these expressions cannot fold sext/zext expressions. As far as I can see all the others can, so these seem like they are the only expressions that are stopping us for getting AddRecExprs as results?

For example if we have (add (sext({x, + , 1}), y). Getting rid of the sext gets us {x + y, +, 1}.

However, there are other methods which might be useful to override, but not related to expression folding. For example SimplifyICmpOperands when taking an ULE predicate can only canonicalize the comparison if it knows that it can add one to the right operand without overflowing (the operand is loop invariant and could possibly be checked). This issue appears mostly when trying to get the number of backedges taken.

[sbaranga]

Hi Andy,

Thanks for looking at this!

In D10161#192391, @atrick wrote:

Overall, it's great to see something like this working in practice. In the past, several alternatives have been discussed. IIRC the main objection to this approach is that SCEV could make assumptions that are not necessary for the optimization leading to overhead for unnecessary checks.

Would that be on the list? If so, it would be an interesting read.
Yes, in theory this can produce unnecessary checks. I think it works ok for the vectorizer (since any case where we wouldn't make this assumption would result in not vectorizing). It looks like a trade-off between not having all the users deal explicitly with this against the number of memchecks.

On most targets, I think it's more efficient to check the high bits for overflow. e.g.

if ((a + 0x800000) & 0xffffff000000) overflow

Instead of:

+ if (Signed) {
+ APInt CmpMinValue = APInt::getSignedMinValue(DstBits).sext(SrcBits);
+ ConstantInt *CTMin = ConstantInt::get(M->getContext(), CmpMinValue);
+ Value *MinCheck = OFBuilder.CreateICmp(ICmpInst::ICMP_SLT,
+ TripCount,
+ CTMin);
+ TripCountCheck = OFBuilder.CreateOr(TripCountCheck, MinCheck);
+ }

Nice. I wonder if the optimizers handle well the cases where we would test some consecutive values with this method, or if we don't end up generating something similar anyway.

Thanks,
Silviu

[sbaranga]

Hi Sanjoy,

In D10161#192468, @sanjoy wrote:

I'll make it a point to do a more detailed review this week, but I
have a high level question:

Instead of a separate AssumingScalarEvolution, why not have an
interface like:

NoOverflowResult ScalarEvolution::proveNoOverflow(SCEVAddRecExpr

*AddRec, FlagType, bool CanAddAssumptions);

I actually started from something similar, but ended up moving to the current form as it seemed cleaner and the loop vectorizer doesn't need the flexibility (if something doesn't come out as a SCEVAddRecExpr it will fail).

I think the users actually want to get a SCEVAddRecExpr (or a SCEVConstant if possible) form a normal SCEV. It is possible to parse the SCEV and, figure out if there are any assumptions that can be made and add them somewhere.

It would also be incorrect in this case to set the nuw/nsw bits (which didn't seem ideal).

Another problem is that ScalarEvolution's expression cache really gets in the way.

NoOverflowResult can be Yes, No or (if CanAddAssumptions is true) a
predicate that, if satisfied, will guarantee AddRec does not overflow
in the FlagType sense. Then the client can choose if it is profitable
to actually emit the predicate if it is cheap enough relative to expected
payoff.

A much more general interface could be

Result ScalarEvolution::provePredicate(CmpInst::Pred, SCEV *LHS, SCEV *RHS)

and have it return one of "Yes | No | Guarded (Predicate)"

Then not only can you ask the "sext{addrec} == addrec{sext}" question
to check for no-wrap, but also push more general logic into
ScalarEvolution as needed in the future (i.e. is this add-rec equal to this
other add-rec at any iteration? if not, can I make it so by adding runtime
checks?).

• Sanjoy

That would be also one way to do it. We would probably need some utility functions to drive that interface. The initial solution would be at the exact opposite side of the spectrum (easy to use, but not flexible).

Cheers,
Silviu

[anemet]

Hi Silviu,

Can you please discuss the use-cases? We all ran into SCEV not always being the right vehicle to prove no-overflow but this proposes a pretty big change, so I want to make sure we can't take more targeted/distributed solutions to the problem. (My general feeling is similar to what Andy and Sanjoy have already expressed.)

I feel like that in some cases, we can prove no-overflow at *compile* time by further analyzing the IR (like what I am proposing in D10472). Essentially this is relying on C/C++ signed overflow being undefined.

In other cases we may need prove no-overflow of smaller types so that we can up-level the sign/zero-extensions. Is this perhaps something that's better done in indvars? The idea is (maybe flawed) that you can eliminate an extension in the loop by using an overflow check outside the loop.

Anyhow, you collected some testcases so categorizing the issues would probably help the discussion.

I am also in favor of allowing finer level of control along the lines of Sanjoy's comments. Your approach may work for the vectorizer but in case of the general dependence analysis, we may not need to prove of no-overflow of all pointers. For example, if a pointer can't alias with any other accesses in the loop, we don't care that we can't get a true affine form for it.

Thanks,
Adam

[sbaranga]

Hi Adam,

In D10161#193173, @anemet wrote:

Can you please discuss the use-cases? We all ran into SCEV not always being the right vehicle to prove no-overflow but this proposes a pretty big change, so I want to make sure we can't take more targeted/distributed solutions to the problem. (My general feeling is similar to what Andy and Sanjoy have already expressed.)

I think the biggest problem would be where overflow can happen, depending on the input data. I would prefer to add some no overflow proving code for cases when it is possbile to prove rather than implementing something like this, but it looks like for certain cases there is no work-around. I've listed some examples below.

I feel like that in some cases, we can prove no-overflow at *compile* time by further analyzing the IR (like what I am proposing in D10472). Essentially this is relying on C/C++ signed overflow being undefined.

Ideally we would figure out at compile time, but I think it would be impossible (or impractical) to cover all the cases where we could prove this, and there are cases where we cannot prove no-overflow (and the overflow condition would depend on input data).

In other cases we may need prove no-overflow of smaller types so that we can up-level the sign/zero-extensions. Is this perhaps something that's better done in indvars? The idea is (maybe flawed) that you can eliminate an extension in the loop by using an overflow check outside the loop.

Anyhow, you collected some testcases so categorizing the issues would probably help the discussion.

I am also in favor of allowing finer level of control along the lines of Sanjoy's comments. Your approach may work for the vectorizer but in case of the general dependence analysis, we may not need to prove of no-overflow of all pointers. For example, if a pointer can't alias with any other accesses in the loop, we don't care that we can't get a true affine form for it.

Yes, good point! I need to think a bit about the interface (and perhaps do some experimenting), but it should definitely be possible to have something similar to what Sanjoy suggested (and I like the idea).

The test cases I have come from C/C++ where unsigned integers are being used as induction variables and for some reason they would get extended at some point. There are cases where we wouldn't need the extend, but those are outside current scope. The problem with these cases is that the behaviour of unsigned overflow is defined (at least in C/C++), and there is no way of statically reasoning about these cases (we can overflow, and it can for example cause infinite loops). For example:

void test(uint32_t n) {

for (uint16_t i = 0; i < n; ++i) {
  <do something>
}

}

Here we would need to compare i can overflow, and for values larger than 2^16-1 we'll get an infinite loop.
In fact there is no way to progress here besides versioning the loop as far as I can see.

A related example:

void test(uint32_t n) {

for (uint32_t i = 0; i <= n; ++i) {
  <do something>
}

}

Here we have no extend operations, but for n == 2^32-1 this will be an infinite loop and i will overflow. SCEV gives up on computing the backedge count because there is no correct result that it can give.

This can affect memory accesses as well:

void test(uint32_t n, uint16_t ind, uint32_t offset, char *a, char *b) {

for (uint16_t i = 0; i < n; ++i) {
  ind++;
  a[ind + offset] = b[ind + offset] * 3;
}

}

ind + offset does not evaluate here as a chrec. ind is a chrec, but then we apply zext to it and add it to the offset. The absence of nsw/nuw means that we actually get add(offset, zext({ind, +, 1}) for ind + offset. This causes a number of problems (accesses to a are not consecutive, etc) And that's correct, they can be non-consecutive for some values of n - but unlikely to ever happen at execution.

In fact since we would get or not sign extends here depending on the pointer size, this would mean that it's possible to run into issues when porting code from a 32-bit target to a 64-bit one.

I think there are valid reasons to use usigned integers (eg. for the extra range), so it may be easy to hit these cases. But it looks like any combination of unsigned integers and zext will disable most loop optimizations? Having unsigned integers in the exit condition will probably cause issues on its own.

Thanks,
Silviu

[sbaranga]

Re-designed to allow the users to make only the assumptions that they need.

The new implementation does not need the AssumingScalarEvolution pass.

Added "SCEVPredicate" as a class in SCEV as an interface for an assumption that
can be made and checked at run-time. Currently we only have implementations for
the SCEVAddRec overflow assumptions, and a SCEVPredicate that can hold
multiple other predicates (SCEVPredicateSet).

We use a SCEV rewriter to take a SCEV and transform it according to the
predicates in a predicate set. Combined with the SCEV AddRec overflow
predicate, this allows us to fold sext/zext expressions into AddRec
expressions and will produce folded SCEVs equivalent with what
the AssumingScalarEvolution pass was producing.

Added a SCEVPredicate in ExitLimit, to allow getting a backedge count
guarded by a SCEV predicate and patched the ExitLimit logic to handle the
predicate. Added code to generate SCEV overflow predicates when
computing the loop count from an icmp condition (more code paths could also
theoretically do this).

Added a getGuardedBackedgeCount method to ScalarEvolution that can return
the backedge count as a SCEV guarded by a predicate. Now LoopAccessAnalysis
and LoopVectorize are using this method.

Modified LoopAccessAnalysis and LoopVectorize to use the SCEV rewriter.
These passes were already using something similar for the symbolic stride.

We now also allow LoopDistribute to use generate the SCEV run-time checks.
This allows us to remove special handling in the LoopAccessAnalysis for the
case where a client wasn't aware of the new run-time checks.

[rengolin]

Hi Silviu,

I have some comments, mostly nitpicks. I'll continue the review as I go, but here are the first ones.

cheers,
--renato

include/llvm/Analysis/LoopAccessAnalysis.h

636

this comment seems a bit terse. UseAssumptions is an argument to some methods in SCEV, nothing to do with LoopInfo.

include/llvm/Analysis/ScalarEvolution.h

189

nitpick: maybe isAlwaysTrue / isNeverTrue or isAlwaysTrue / isAlwaysFalse would be more descriptive?

245

No description?

246

Why the duplication? Will you have one for each further type?

273

Why here, and not in SCEVPredicate?

[sbaranga]

In D10161#206332, @rengolin wrote:

Hi Silviu,

I have some comments, mostly nitpicks. I'll continue the review as I go, but here are the first ones.

cheers,
--renato

Thanks! I'll make sure to fix these in the next upload. Some comments from the last review should also apply, so I'll do that as well.

Cheers,
Silviu

[aschwaighofer]

I think this change is orthogonal to improving SCEV for cases where we can prove no wrapping by looking at the IR. At the high level this change looks good to me (I have always wanted to have the ability for SCEV to gather assumptions needed to prove no wrapping) - and the examples demonstrate that there is a need. Silviu has addressed the issue of only generating the checks when needed.

I'll leave it to Sanjoy and Adam to do a detailed review.

[rengolin]

include/llvm/Analysis/ScalarEvolutionExpressions.h

753

Do you need to keep this public?

In addOverflowAssumption, you check for MakeAssumptions to add or not the SCEV to it, and if it remains public, anyone will be able to bypass this check.

[rengolin]

lib/Analysis/LoopAccessAnalysis.cpp

122

Why are you using the llvm namespace here?

Shouldn't these functions be static?

127

replaceSymbolicStrideSCEV is defined on the header, as namespace llvm, static, and leads to confusions like these.

If you need it in more than one place, it shouldn't be static and it should be implemented in its own cpp file. If these are local only, they should be static or in anonymous namespaces.

[hfinkel]

include/llvm/Analysis/ScalarEvolutionExpressions.h

898

Why not make this a member function of SCEV (same for rewriteSCEVWithAssumptions below)?

lib/Analysis/ScalarEvolution.cpp

8061

Don't remove blank line.

[sbaranga]

Thanks for the reviews! I'll have a new version out soon to fix all of the highlighted issues.

-Silviu

include/llvm/Analysis/ScalarEvolution.h

246

I was thinking of having a SmallVector for storage of each predicate, plus all the references in Preds. So adding further types would require adding additional SmallVectors (we will probably have more types, I can think of at least one more for checking the range of an expression).

include/llvm/Analysis/ScalarEvolutionExpressions.h

898

Makes sense.

[sbaranga]

Rebased the patch on trunk (which is the largest part of this update).

Moved the SCEV rewriter implementation from the ScalarEvolutionExpressions header
to the ScalarEvolution .cpp file. ScalarEvolution now has methods to perform
the SCEV rewrite.

Renamed the isAlways/isNever methods from SCEVPredicate to isAlwaysTrue/isAlwaysFalse.

[anemet]

Hi Silviu,

Sorry about the delay! Also my comments below are somewhat disorganized because I am still trying to wrap my head around this large patch. I *think* that the overall direction is good but I have a hard time seeing how the different parts connect at this point. I also have some ideas below of how you could probably restructure this patch to help the review.

As a high-level comment, why doesn't the strided assumption become another type of assumption after these changes?

Added a SCEVPredicate in ExitLimit, to allow getting a backedge count
guarded by a SCEV predicate and patched the ExitLimit logic to handle the
predicate. Added code to generate SCEV overflow predicates when
computing the loop count from an icmp condition (more code paths could also theoretically do this).

Why is this needed? It's not explained.

As another high-level comment, I am also wondering if this 1000+ line patch can be split up to ease review. The steps I am thinking:

1. Somehow generalize/refactor the stride-checks to make them more similar to the overflow assumptions
2. Add the minimal predicate set logic and drive it from LAA or somewhere so that you can add tests for simple cases. Perhaps only make strided assumptions work with predicate sets first.
3. Add overflow assumptions
4. Add the guarded back-edge count extension along with analysis tests
5. Add the ExitLimit mods with some more tests. This may have to come before 4 but I don't really understand this change at this point.

This is just an quick idea, feel free to structure the patches differently but I would be more comfortable with a more incremental approach.

Thanks,
Adam

include/llvm/Analysis/LoopAccessAnalysis.h

295–296

Can you please make this a bit more precise? E.g.

With these assumption satisfied the memory accesses become simple AddRecs which allows them to get analyzed.

Also it should either be called Preds or PredSet.

556

What's the deal with unique_ptr above and this here? Can you explaining the ownership situation?

Also it's probably less confusing if we use the same variable name for PredicateSets.

lib/Analysis/LoopAccessAnalysis.cpp

141–148

Hmm, why don't you only write Preds after to ensure that we succeeded? Isn't this the same as:

if (R.Ret && !R.P.isNever()) {

R.P.add(&Preds);  <-- write Preds here.
return R.Ret:

}

if not it needs a comment.

159

We should not recompute this for every insert. Also we need to bound the number of predicates so getting the guarded backedge count at a more central place is probably a better idea.

568–572

This does not look tight enough.

Can't we fail in hasComputable... for reasons other than the SCEV not being an AddRec?
Also the return value of convertSCEV... should be checked rather than just repeating hasComputable... blindly.

lib/Transforms/Vectorize/LoopVectorize.cpp

311–313

There is no def for this function.

[sbaranga]

Hi Adam,

In D10161#232197, @anemet wrote:

Hi Silviu,

Sorry about the delay! Also my comments below are somewhat disorganized because I am still trying to wrap my head around this large patch. I *think* that the overall direction is good but I have a hard time seeing how the different parts connect at this point. I also have some ideas below of how you could probably restructure this patch to help the review.

Thanks! Restructuring the patch sounds like a good idea.

As a high-level comment, why doesn't the strided assumption become another type of assumption after these changes?

That's a good idea, we should be able to do that. I don't see any problem with making a predicate for it in one of the patches.

Added a SCEVPredicate in ExitLimit, to allow getting a backedge count
guarded by a SCEV predicate and patched the ExitLimit logic to handle the
predicate. Added code to generate SCEV overflow predicates when
computing the loop count from an icmp condition (more code paths could also theoretically do this).

Why is this needed? It's not explained.

The exit limit is what's being cached. That result is used to generate the (exact) backedge count, and other things. In order to keep caching mostly the same, we need to add the predicate to the ExitLimit. So this is all part of getting getBackedgeCount to work with predicates.

As another high-level comment, I am also wondering if this 1000+ line patch can be split up to ease review. The steps I am thinking:

1. Somehow generalize/refactor the stride-checks to make them more similar to the overflow assumptions
2. Add the minimal predicate set logic and drive it from LAA or somewhere so that you can add tests for simple cases. Perhaps only make strided assumptions work with predicate sets first.
3. Add overflow assumptions
4. Add the guarded back-edge count extension along with analysis tests
5. Add the ExitLimit mods with some more tests. This may have to come before 4 but I don't really understand this change at this point.

Yes, I've also felt the need to split this up. At least all the places where we're making assumptions should probably be reviewed separately. My plans were slightly different though (more focused towards being able to get the backedge count). I'll have to think about the exact details, but it will probably end up being similar to what you've listed above.

This is just an quick idea, feel free to structure the patches differently but I would be more comfortable with a more incremental approach.

Thanks,
Adam

include/llvm/Analysis/LoopAccessAnalysis.h

556

This should be removed as it doesn't do anything. The unique_ptr above should contain the predicates, LoopAccessInfo ownes it and all other classes/structs have reference to it.

lib/Analysis/LoopAccessAnalysis.cpp

141–148

R.P.add(&Preds) adds Preds to R.P, so that wouldn't write Preds. We use the temporary because we can only be sure if we've succeeded or not after we see the final set of predicates.

158–160

Caching expressions would make sense to me. We would have to recompute the expressions every time we commit to a new predicate though.

568–583

Yes, you're correct. A better solution seems to only make the assumption after we've seen that hasComputableBounds.. now returns true.

This change probably needs a closer look.

lib/Transforms/Vectorize/LoopVectorize.cpp

311–313

Must be an artefact from the rebase. It's not being used anywhere either, so it just needs to be removed.

[anemet]

In D10161#233173, @sbaranga wrote:

1. Somehow generalize/refactor the stride-checks to make them more similar to the overflow assumptions
2. Add the minimal predicate set logic and drive it from LAA or somewhere so that you can add tests for simple cases. Perhaps only make strided assumptions work with predicate sets first.
3. Add overflow assumptions
4. Add the guarded back-edge count extension along with analysis tests
5. Add the ExitLimit mods with some more tests. This may have to come before 4 but I don't really understand this change at this point.

Yes, I've also felt the need to split this up. At least all the places where we're making assumptions should probably be reviewed separately. My plans were slightly different though (more focused towards being able to get the backedge count). I'll have to think about the exact details, but it will probably end up being similar to what you've listed above.

Great! I understand that your actual goal to get the backedge count into a suitable form for analysis by using predicates. The tricky part that that needs multiple things: the whole predicated SCEV infrastructure *plus* a good way to expose this otherwise implicit step to clients so that they have a way to reason about the cost of adding these predicates.

That's why if possible I'd like to get the first set in where the clients are in full control (based on potentially wrapping pointers for example) and then start bringing in the whole backedge count complexity.

That's said it's entirely possible that I am oversimplifying things.

Thanks,
Adam

lib/Analysis/LoopAccessAnalysis.cpp

141–148

I see. It still feels like a common multi-step pattern that clients can get wrong. I wonder if we can make the API better here. We can discuss this after you split this into multiple patches.

158–160

I don't follow.

[sanjoy]

Is this still relevant, or has this been superseded by D13595 ?

[sbaranga]

In D10161#274408, @sanjoy wrote:

Is this still relevant, or has this been superseded by D13595 ?

It is only relevant as a reference for future work I'll be splitting out patches from here in the future, although we've already diverged with D13595 in some points. I'll mark it as abandoned.

include/llvm/Analysis/LoopAccessAnalysis.h

 namespace llvm {
 
 class Value;
 class DataLayout;
 class AliasAnalysis;
 class ScalarEvolution;
 class Loop;
 class SCEV;
+class SCEVPredicateSet;
 
 /// Optimization analysis message produced during vectorization. Messages inform
 /// the user why vectorization did not occur.
 class LoopAccessReport {
   std::string Message;
   const Instruction *Instr;
 
 protected:
struct Dependence {
     bool isPossiblyBackward() const;
 
     /// \brief Print the dependence.  \p Instr is used to map the instruction
     /// indices to instructions.
     void print(raw_ostream &OS, unsigned Depth,
                const SmallVectorImpl<Instruction *> &Instrs) const;
   };
 
-  MemoryDepChecker(ScalarEvolution *Se, const Loop *L)
+  MemoryDepChecker(ScalarEvolution *Se, const Loop *L, SCEVPredicateSet &Pred)
       : SE(Se), InnermostLoop(L), AccessIdx(0),
         ShouldRetryWithRuntimeCheck(false), SafeForVectorization(true),
-        RecordInterestingDependences(true) {}
+        RecordInterestingDependences(true), Pred(Pred) {}
 
   /// \brief Register the location (instructions are given increasing numbers)
   /// of a write access.
   void addAccess(StoreInst *SI) {
     Value *Ptr = SI->getPointerOperand();
     Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx);
     InstMap.push_back(SI);
     ++AccessIdx;
private:
   /// Otherwise, this function returns true signaling a possible dependence.
   Dependence::DepType isDependent(const MemAccessInfo &A, unsigned AIdx,
                                   const MemAccessInfo &B, unsigned BIdx,
                                   const ValueToValueMap &Strides);
 
   /// \brief Check whether the data dependence could prevent store-load
   /// forwarding.
   bool couldPreventStoreLoadForward(unsigned Distance, unsigned TypeByteSize);
+
+  /// The SCEV predicate containing all the SCEV-related assumptions.
+  SCEVPredicateSet &Pred;
 };
 
 /// \brief Holds information about the memory runtime legality checks to verify
 /// that a group of pointers do not overlap.
 class RuntimePointerChecking {
 public:
   struct PointerInfo {
     /// Holds the pointer value that we need to check.
public:
   /// Reset the state of the pointer runtime information.
   void reset() {
     Need = false;
     Pointers.clear();
   }
 
   /// Insert a pointer and calculate the start and end SCEVs.
   void insert(Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId,
-              unsigned ASId, const ValueToValueMap &Strides);
+              unsigned ASId, const ValueToValueMap &Strides,
+              SCEVPredicateSet &Pred);
 
   /// \brief No run-time memory checking is necessary.
   bool empty() const { return Pointers.empty(); }
 
   /// A grouping of pointers. A single memcheck is required between
   /// two groups.
   struct CheckingPtrGroup {
     /// \brief Create a new pointer checking group containing a single
public:
 
   /// \brief Checks existence of store to invariant address inside loop.
   /// If the loop has any store to invariant address, then it returns true,
   /// else returns false.
   bool hasStoreToLoopInvariantAddress() const {
     return StoreToLoopInvariantAddress;
   }
 
+  /// The SCEV predicate containing all the SCEV-related assumptions.
+  std::unique_ptr<SCEVPredicateSet> Pred;
+
 private:
   /// \brief Analyze the loop.  Substitute symbolic strides using Strides.
   void analyzeLoop(const ValueToValueMap &Strides);
 
   /// \brief Check if the structure of the loop allows it to be analyzed by this
   /// pass.
   bool canAnalyzeLoop();
 
private:
   Loop *TheLoop;
   ScalarEvolution *SE;
   const DataLayout &DL;
   const TargetLibraryInfo *TLI;
   AliasAnalysis *AA;
   DominatorTree *DT;
   LoopInfo *LI;
 
+  /// The SCEV predicate containing all the SCEV-related assumptions.
+  SCEVPredicateSet ScPredicates;
+
   unsigned NumLoads;
   unsigned NumStores;
 
   unsigned MaxSafeDepDistBytes;
 
   /// \brief Cache the result of analyzeLoop.
   bool CanVecMem;
 

 ///
 /// If \p OrigPtr is not null, use it to look up the stride value instead of \p
 /// Ptr.  \p PtrToStride provides the mapping between the pointer value and its
 /// stride as collected by LoopVectorizationLegality::collectStridedAccess.
 const SCEV *replaceSymbolicStrideSCEV(ScalarEvolution *SE,
                                       const ValueToValueMap &PtrToStride,
                                       Value *Ptr, Value *OrigPtr = nullptr);
 
+///\brief Return the SCEV of a value having with all assumptions applied. This
+/// will replace symbolic strides according to \p PtrToStride and apply any
+/// existing SCEV assumptions contained in \p Preds.
+const SCEV *rewriteSCEV(ScalarEvolution *SE, const ValueToValueMap &PtrToStride,
+                        Value *Ptr, Value *OrigPtr, const Loop *L,
+                        SCEVPredicateSet &Preds);
+
+///\brief Try and add a minimal set of assumptions that will cause the
+/// re-written SCEV of \p Ptr to be an AddRecExpr. If successful we will
+/// return a modified AddRecExpr and add any assumptions made to \p Preds.
+/// Otherwise, we will make no new assumption and return the same result as
+/// rewriteSCEV.
+const SCEV *convertSCEVToAddRec(ScalarEvolution *SE,
+                                const ValueToValueMap &PtrToStride, Value *Ptr,
+                                Value *OrigPtr, const Loop *L,
+                                SCEVPredicateSet &Preds);
+
 /// \brief Check the stride of the pointer and ensure that it does not wrap in
-/// the address space.
+/// the address space. If \p MakeAssumptions is true, we will try to add
+/// SCEV assumptions as necessary to \Pred in order to return true. If we
+/// cannot return true, \p Pred will remain unchanged.
 int isStridedPtr(ScalarEvolution *SE, Value *Ptr, const Loop *Lp,
-                 const ValueToValueMap &StridesMap);
+                 const ValueToValueMap &StridesMap, SCEVPredicateSet &Pred,
+                 bool MakeAssumptions);
 
 /// \brief This analysis provides dependence information for the memory accesses
 /// of a loop.
 ///
 /// It runs the analysis for a loop on demand.  This can be initiated by
 /// querying the loop access info via LAA::getInfo.  getInfo return a
 /// LoopAccessInfo object.  See this class for the specifics of what information
 /// is provided.
public:
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   /// \brief Query the result of the loop access information for the loop \p L.
   ///
   /// If the client speculates (and then issues run-time checks) for the values
   /// of symbolic strides, \p Strides provides the mapping (see
   /// replaceSymbolicStrideSCEV).  If there is no cached result available run
-  /// the analysis.
+  /// the analysis. If UseAssumptions is true, the user must add the
+  /// run-time checks collected by the AssumingScalarEvolution pass if
+  /// making any changes to the loop.
   const LoopAccessInfo &getInfo(Loop *L, const ValueToValueMap &Strides);
 
   void releaseMemory() override {
     // Invalidate the cache when the pass is freed.
     LoopAccessInfoMap.clear();
   }
 
   /// \brief Print the result of the analysis when invoked with -analyze.

include/llvm/Analysis/ScalarEvolution.h

namespace llvm {
   class DataLayout;
   class TargetLibraryInfo;
   class LLVMContext;
   class Loop;
   class LoopInfo;
   class Operator;
   class SCEVUnknown;
   class SCEV;
+  class SCEVExpander;
+
   template<> struct FoldingSetTrait<SCEV>;
 
   /// SCEV - 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>;
#endif
   /// marker.
   struct SCEVCouldNotCompute : public SCEV {
     SCEVCouldNotCompute();
 
     /// Methods for support type inquiry through isa, cast, and dyn_cast:
     static bool classof(const SCEV *S);
   };
 
+  enum SCEVPredicateTypes { pAddRecOverflow, pSet };
+
+  //===--------------------------------------------------------------------===//
+  /// SCEVPredicate - This class represents an assumption made using SCEV
+  /// expressions which can be checked at run-time.
+  ///
+  class SCEVPredicate {
+  protected:
+    unsigned short SCEVPredicateType;
+
+  public:
+    SCEVPredicate(unsigned short Type);
+    unsigned short getType() const { return SCEVPredicateType; }
+    /// Returns true if the predicate is always true. This means that no
+    /// assumptions were made and nothing needs to be checked at run-time.
+    virtual bool isAlways() const = 0;
+    /// Return true if we consider this to be always false or if we've
+    /// given up on this set of assumptions (for example because of the
+    /// high cost of checking at run-time).
+    virtual bool isNever() const = 0;
+    /// Returns true if this predicate implies \p N.
+    virtual bool contains(const SCEVPredicate *N) const = 0;
+    /// Prints a textual representation of this predicate.
+    virtual void print(raw_ostream &OS, unsigned Depth) const = 0;
+
+    /// Generates a run-time check for this predicate.
+    virtual Value *generateCheck(Instruction *Loc, ScalarEvolution *SE,
+                                 const DataLayout *DL, SCEVExpander &Exp) = 0;
+  };
+
+  //===--------------------------------------------------------------------===//
+  /// SCEVAddRecOverflowPredicate - This class represents an assumption
+  /// made using on an AddRec expression. Given an affine AddRec expression
+  /// (a,+,b), we assume that it has nsw or nuw flags.
+  class SCEVAddRecOverflowPredicate : public SCEVPredicate {
+    const SCEV *AR;
+    SCEV::NoWrapFlags Flags;
+
+  public:
+    SCEVAddRecOverflowPredicate()
+        : SCEVPredicate(pAddRecOverflow), AR(nullptr),
+          Flags(SCEV::FlagAnyWrap) {}
+    SCEVAddRecOverflowPredicate(const SCEV *AR, SCEV::NoWrapFlags Flags);
+
+    /// Returns the set assumed no overflow flags.
+    SCEV::NoWrapFlags getFlags() const { return Flags; }
+    /// Add an assumption of no overflow for \p AddedFlags.
+    void addFlags(SCEV::NoWrapFlags AddedFlags);
+    /// Returns the AddRec expression that we've made assumptions for.
+    const SCEV *getExpr() const { return AR; }
+
+    /// Implementation of the SCEVPredicate interface
+    bool contains(const SCEVPredicate *N) const override;
+    void print(raw_ostream &OS, unsigned Depth) const override;
+    bool isAlways() const override;
+    bool isNever() const override;
+    Value *generateCheck(Instruction *Loc, ScalarEvolution *SE,
+                         const DataLayout *DL, SCEVExpander &Exp) override;
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVPredicate *P) {
+      return P->getType() == pAddRecOverflow;
+    }
+  };
+
+  //===--------------------------------------------------------------------===//
+  /// SCEVPredicateSet - This class represents a composition of other
+  /// SCEV predicates, and is the class that most clients will interact with.
+  ///
+  class SCEVPredicateSet : public SCEVPredicate {
+  private:
+    bool Never;
+    /// Storage for different predicates that make up this Predicate Set.
+    SmallVector<SCEVAddRecOverflowPredicate, 16> AddRecOverflows;
+    /// Vector with references to all predicates in this set.
+    SmallVector<SCEVPredicate *, 16> Preds;
+
+  public:
+    SCEVPredicateSet();
+    /// The copy constructor.
+    SCEVPredicateSet(const SCEVPredicateSet &Old);
+    /// Adds a predicate to this predicate set.
+    void add(const SCEVPredicate *N);
+
+    /// Generates a run-time check for all the contained predicates.
+    /// This is a wrapper around generateCheck, and provides an interface
+    /// similar to other run-time checks used for versioning.
+    std::pair<Instruction *, Instruction *>
+    generateGuardCond(Instruction *Loc, ScalarEvolution *SE);
+
+    /// Implementation of the SCEVPredicate interface
+    bool isAlways() const override;
+    bool isNever() const override;
+    bool contains(const SCEVPredicate *N) const override;
+    void print(raw_ostream &OS, unsigned Depth) const;
+    Value *generateCheck(Instruction *Loc, ScalarEvolution *SE,
+                         const DataLayout *DL, SCEVExpander &Exp) override;
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVPredicate *P) {
+      return P->getType() == pSet;
+    }
+
+    /// The copy operator.
+    const SCEVPredicateSet &operator=(const SCEVPredicateSet &RHS) {
+      Never = RHS.Never;
+      AddRecOverflows = RHS.AddRecOverflows;
+      Preds.clear();
+      for (unsigned II = 0; II < AddRecOverflows.size(); ++II) {
+        Preds.push_back(&AddRecOverflows[II]);
+      }
+      assert(Preds.size() == RHS.Preds.size() && "Wrong Preds size after copy");
+      return *this;
+    }
+  };
+
   /// ScalarEvolution - This class is the main scalar evolution driver.  Because
   /// client code (intentionally) can't do much with the SCEV objects directly,
   /// they must ask this class for services.
   ///
   class ScalarEvolution : public FunctionPass {
   public:
     /// LoopDisposition - An enum describing the relationship between a
     /// SCEV and a loop.
private:
     /// ExitLimit - Information about the number of loop iterations for which a
     /// loop exit's branch condition evaluates to the not-taken path.  This is a
     /// temporary pair of exact and max expressions that are eventually
     /// summarized in ExitNotTakenInfo and BackedgeTakenInfo.
     struct ExitLimit {
       const SCEV *Exact;
       const SCEV *Max;
 
+      /// A predicate set guard for this ExitLimit. The result is only
+      /// valid if this predicate evaluates to 'true' at run-time.
+      SCEVPredicateSet Pred;
+
       /*implicit*/ ExitLimit(const SCEV *E) : Exact(E), Max(E) {}
 
-      ExitLimit(const SCEV *E, const SCEV *M) : Exact(E), Max(M) {}
+      ExitLimit(const SCEV *E, const SCEV *M, SCEVPredicateSet &P)
+          : Exact(E), Max(M), Pred(P) {}
 
       /// hasAnyInfo - Test whether this ExitLimit contains any computed
       /// information, or whether it's all SCEVCouldNotCompute values.
       bool hasAnyInfo() const {
         return !isa<SCEVCouldNotCompute>(Exact) ||
           !isa<SCEVCouldNotCompute>(Max);
       }
     };
 
     /// ExitNotTakenInfo - Information about the number of times a particular
     /// loop exit may be reached before exiting the loop.
     struct ExitNotTakenInfo {
       AssertingVH<BasicBlock> ExitingBlock;
       const SCEV *ExactNotTaken;
-      PointerIntPair<ExitNotTakenInfo*, 1> NextExit;
+      PointerIntPair<ExitNotTakenInfo *, 1> NextExit;
+      SCEVPredicateSet Pred;
 
       ExitNotTakenInfo() : ExitingBlock(nullptr), ExactNotTaken(nullptr) {}
 
       /// isCompleteList - Return true if all loop exits are computable.
       bool isCompleteList() const {
         return NextExit.getInt() == 0;
       }
 
class BackedgeTakenInfo {
       /// count of the loop that is known, or a SCEVCouldNotCompute.
       const SCEV *Max;
 
     public:
       BackedgeTakenInfo() : Max(nullptr) {}
 
       /// Initialize BackedgeTakenInfo from a list of exact exit counts.
       BackedgeTakenInfo(
-        SmallVectorImpl< std::pair<BasicBlock *, const SCEV *> > &ExitCounts,
-        bool Complete, const SCEV *MaxCount);
+          SmallVectorImpl<std::pair<BasicBlock *, const SCEV *>> &ExitCounts,
+          SmallVectorImpl<SCEVPredicateSet *> &ExitPreds, bool Complete,
+          const SCEV *MaxCount);
 
       /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any
       /// computed information, or whether it's all SCEVCouldNotCompute
       /// values.
       bool hasAnyInfo() const {
         return ExitNotTaken.ExitingBlock || !isa<SCEVCouldNotCompute>(Max);
       }
 
       /// getExact - Return an expression indicating the exact backedge-taken
-      /// count of the loop if it is known, or SCEVCouldNotCompute
-      /// otherwise. This is the number of times the loop header can be
-      /// guaranteed to execute, minus one.
+      /// count of the loop if it is known and always correct (independent
+      /// of any assumptions that should be checked at run-time), or
+      /// SCEVCouldNotCompute otherwise. This is the number of times the
+      /// loop header can be guaranteed to execute, minus one.
       const SCEV *getExact(ScalarEvolution *SE) const;
 
+      /// getGuardedExact - Return an expression indicating the exact
+      /// backedge-taken count of the loop if it is known, or
+      /// SCEVCouldNotCompute otherwise. Returns the SCEV predicates that
+      /// need to be checked at run-time in order for this answer to be valid
+      /// in \p Predicates. This is the number of times the loop header can be
+      /// guaranteed to execute, minus one.
+      const SCEV *getGuardedExact(ScalarEvolution *SE,
+                                  SCEVPredicateSet &Predicates) const;
       /// getExact - Return the number of times this loop exit may fall through
       /// to the back edge, or SCEVCouldNotCompute. The loop is guaranteed not
       /// to exit via this block before this number of iterations, but may exit
       /// via another block.
       const SCEV *getExact(BasicBlock *ExitingBlock, ScalarEvolution *SE) const;
 
       /// getMax - Get the max backedge taken count for the loop.
       const SCEV *getMax(ScalarEvolution *SE) const;
ExitLimit ComputeExitLimitFromCond(const Loop *L,
                                        Value *ExitCond,
                                        BasicBlock *TBB,
                                        BasicBlock *FBB,
                                        bool IsSubExpr);
 
     /// ComputeExitLimitFromICmp - Compute the number of times the backedge of
     /// the specified loop will execute if its exit condition were a conditional
     /// branch of the ICmpInst ExitCond, TBB, and FBB.
-    ExitLimit ComputeExitLimitFromICmp(const Loop *L,
-                                       ICmpInst *ExitCond,
-                                       BasicBlock *TBB,
-                                       BasicBlock *FBB,
-                                       bool IsSubExpr);
+    ExitLimit ComputeExitLimitFromICmp(const Loop *L, ICmpInst *ExitCond,
+                                       BasicBlock *TBB, BasicBlock *FBB,
+                                       bool IsSubExpr,
+                                       bool UseAssumptions = false);
 
     /// ComputeExitLimitFromSingleExitSwitch - Compute the number of times the
     /// backedge of the specified loop will execute if its exit condition were a
     /// switch with a single exiting case to ExitingBB.
     ExitLimit
     ComputeExitLimitFromSingleExitSwitch(const Loop *L, SwitchInst *Switch,
                                BasicBlock *ExitingBB, bool IsSubExpr);
 
private:
     /// evaluate the exit count of the loop, return CouldNotCompute.
     const SCEV *ComputeExitCountExhaustively(const Loop *L,
                                              Value *Cond,
                                              bool ExitWhen);
 
     /// HowFarToZero - Return the number of times an exit condition comparing
     /// the specified value to zero will execute.  If not computable, return
     /// CouldNotCompute.
-    ExitLimit HowFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr);
+    ExitLimit HowFarToZero(const SCEV *V, const Loop *L, bool IsSubExpr,
+                           bool UseAssumptions = false);
 
     /// HowFarToNonZero - Return the number of times an exit condition checking
     /// the specified value for nonzero will execute.  If not computable, return
     /// CouldNotCompute.
-    ExitLimit HowFarToNonZero(const SCEV *V, const Loop *L);
+    ExitLimit HowFarToNonZero(const SCEV *V, const Loop *L,
+                              bool UseAssumptions = false);
 
     /// HowManyLessThans - Return the number of times an exit condition
     /// containing the specified less-than comparison will execute.  If not
     /// computable, return CouldNotCompute. isSigned specifies whether the
     /// less-than is signed.
-    ExitLimit HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
-                               const Loop *L, bool isSigned, bool IsSubExpr);
+    ExitLimit HowManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L,
+                               bool isSigned, bool IsSubExpr,
+                               bool UseAssumptions = false);
     ExitLimit HowManyGreaterThans(const SCEV *LHS, const SCEV *RHS,
-                                  const Loop *L, bool isSigned, bool IsSubExpr);
+                                  const Loop *L, bool isSigned, bool IsSubExpr,
+                                  bool UseAssumptions = false);
 
     /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB
     /// (which may not be an immediate predecessor) which has exactly one
     /// successor from which BB is reachable, or null if no such block is
     /// found.
     std::pair<BasicBlock *, BasicBlock *>
     getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB);
 
public:
     const SCEV *getSCEV(Value *V);
 
     const SCEV *getConstant(ConstantInt *V);
     const SCEV *getConstant(const APInt& Val);
     const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);
     const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty);
     const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty);
     const SCEV *getSignExtendExpr(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);
     const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS,
                            SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) {
       SmallVector<const SCEV *, 2> Ops;
       Ops.push_back(LHS);
       Ops.push_back(RHS);
       return getAddExpr(Ops, Flags);
public:
     /// when the header is branched to from outside the loop.
     ///
     /// Note that it is not valid to call this method on a loop without a
     /// loop-invariant backedge-taken count (see
     /// hasLoopInvariantBackedgeTakenCount).
     ///
     const SCEV *getBackedgeTakenCount(const Loop *L);
 
+    const SCEV *getGuardedBackedgeTakenCount(const Loop *L,
+                                             SCEVPredicateSet &Predicates);
+
     /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except
     /// return the least SCEV value that is known never to be less than the
     /// actual backedge taken count.
     const SCEV *getMaxBackedgeTakenCount(const Loop *L);
 
     /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop
     /// has an analyzable loop-invariant backedge-taken count.
     bool hasLoopInvariantBackedgeTakenCount(const Loop *L);
private:
 
     /// FirstUnknown - The head of a linked list of all SCEVUnknown
     /// values that have been allocated. This is used by releaseMemory
     /// to locate them all and call their destructors.
     SCEVUnknown *FirstUnknown;
   };
 }
 
 #endif

include/llvm/Analysis/ScalarEvolutionExpressions.h

 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Support/ErrorHandling.h"
 
 namespace llvm {
   class ConstantInt;
   class ConstantRange;
   class DominatorTree;
+  class SCEVExpander;
 
   enum SCEVTypes {
     // These should be ordered in terms of increasing complexity to make the
     // folders simpler.
     scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr,
     scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr,
     scUnknown, scCouldNotCompute
   };
const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
       return Expr;
     }
 
   private:
     ScalarEvolution &SE;
     LoopToScevMapT ⤅
   };
 
+  /// Removes overflows and records the assumptions that were made.
+  struct SCEVOverflowRewriter
+      : public SCEVVisitor<SCEVOverflowRewriter, const SCEV *> {
+  public:
+    SCEVPredicateSet &P;
+
+    static const SCEV *rewrite(const SCEV *Scev, const Loop *L,
+                               ScalarEvolution &SE, SCEVPredicateSet &A,
+                               bool Assume) {
+      SCEVOverflowRewriter Rewriter(L, SE, A, Assume);
+      return Rewriter.visit(Scev);
+    }
+
+    bool addOverflowAssumption(const SCEV *S, SCEV::NoWrapFlags AddedFlags) {
+      SCEVAddRecOverflowPredicate A(S, AddedFlags);
+      if (!MakeAssumptions) {
+        // Check if we've already made this assumption.
+        if (P.contains(&A))
+          return true;
+        return false;
+      }
+      P.add(&A);
+      return true;
+    }
+
+    SCEVOverflowRewriter(const Loop *L, ScalarEvolution &S, SCEVPredicateSet &P,
+                         bool MakeAssumptions)
+        : P(P), SE(S), L(L), MakeAssumptions(MakeAssumptions) {}
+
+    const SCEV *visitConstant(const SCEVConstant *Constant) { return Constant; }
+
+    const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) {
+      const SCEV *Operand = visit(Expr->getOperand());
+      return SE.getTruncateExpr(Operand, Expr->getType());
+    }
+
+    // We should only need to add assumptions when encountering the
+    // sext/zext expressions, as other expressions will fold into
+    // the AddRecExprs.
+    const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
+      const SCEV *Operand = visit(Expr->getOperand());
+      const SCEVAddRecExpr *AR = dyn_cast<const SCEVAddRecExpr>(Operand);
+      if (AR && AR->getLoop() == L && AR->isAffine()) {
+        // This couldn't be folded because the operand didn't have the nuw
+        // flag. Add the nuw flag as an assumption that we could make.
+        const SCEV *Step = AR->getStepRecurrence(SE);
+        Type *Ty = Expr->getType();
+        // We would also like to add the NUW flag here. We add the NUW
+        // flag to the assumption set but cannot set it on the expression
+        // because it would pollute ScalarEvolution's cache.
+        if (addOverflowAssumption(AR, SCEV::FlagNUW))
+          return SE.getAddRecExpr(SE.getZeroExtendExpr(AR->getStart(), Ty),
+                                  SE.getZeroExtendExpr(Step, Ty), L,
+                                  AR->getNoWrapFlags());
+      }
+      return SE.getZeroExtendExpr(Operand, Expr->getType());
+    }
+
+    const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
+      const SCEV *Operand = visit(Expr->getOperand());
+      const SCEVAddRecExpr *AR = dyn_cast<const SCEVAddRecExpr>(Operand);
+      if (AR && AR->getLoop() == L && AR->isAffine()) {
+        // This couldn't be folded because the operand didn't have the nsw
+        // flag. Add the nsw flag as an assumption that we could make.
+        const SCEV *Step = AR->getStepRecurrence(SE);
+        Type *Ty = Expr->getType();
+        // We would also like to add the NUW flag here. We add the NUW
+        // flag to the assumption set but cannot set it on the expression
+        // because it would pollute ScalarEvolution's cache.
+        if (addOverflowAssumption(AR, SCEV::FlagNSW))
+          return SE.getAddRecExpr(SE.getSignExtendExpr(AR->getStart(), Ty),
+                                  SE.getSignExtendExpr(Step, Ty), L,
+                                  AR->getNoWrapFlags());
+      }
+      return SE.getSignExtendExpr(Operand, Expr->getType());
+    }
+
+    const SCEV *visitAddExpr(const SCEVAddExpr *Expr) {
+      SmallVector<const SCEV *, 2> Operands;
+      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
+        Operands.push_back(visit(Expr->getOperand(i)));
+      return SE.getAddExpr(Operands);
+    }
+
+    const SCEV *visitMulExpr(const SCEVMulExpr *Expr) {
+      SmallVector<const SCEV *, 2> Operands;
+      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
+        Operands.push_back(visit(Expr->getOperand(i)));
+      return SE.getMulExpr(Operands);
+    }
+
+    const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) {
+      return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS()));
+    }
+
+    const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) {
+      SmallVector<const SCEV *, 2> Operands;
+      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
+        Operands.push_back(visit(Expr->getOperand(i)));
+
+      const Loop *L = Expr->getLoop();
+      return SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags());
+    }
+
+    const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) {
+      SmallVector<const SCEV *, 2> Operands;
+      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
+        Operands.push_back(visit(Expr->getOperand(i)));
+      return SE.getSMaxExpr(Operands);
+    }
+
+    const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) {
+      SmallVector<const SCEV *, 2> Operands;
+      for (int i = 0, e = Expr->getNumOperands(); i < e; ++i)
+        Operands.push_back(visit(Expr->getOperand(i)));
+      return SE.getUMaxExpr(Operands);
+    }
+
+    const SCEV *visitUnknown(const SCEVUnknown *Expr) { return Expr; }
+
+    const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
+      return Expr;
+    }
+
+  private:
+    ScalarEvolution &SE;
+    const Loop *L;
+    bool MakeAssumptions;
+  };
+
   /// Applies the Map (Loop -> SCEV) to the given Scev.
   static inline const SCEV *apply(const SCEV *Scev, LoopToScevMapT &Map,
                                   ScalarEvolution &SE) {
     return SCEVApplyRewriter::rewrite(Scev, Map, SE);
   }
 
+  /// Associates a SCEV predicate to a SCEV.
+  struct OFAssumptionResult {
+    const SCEV *Ret;
+    SCEVPredicateSet P;
+    OFAssumptionResult() : Ret(nullptr) {}
+  };
+
+  /// Tries to convert a SCEV into an AddRecExpr by making overflow
+  /// assumptions and sinking SCEV nodes. If unsuccessful, we will return
+  /// a nullptr in the Ret field. If succesful, the predicate set of the
+  /// answer must be checked at run-time in order for the answer to be
+  /// valid.
+  static inline const OFAssumptionResult
+  removeOverflowsWithAssumptions(const SCEV *S, const Loop *L,
+                                 ScalarEvolution *SE) {
+    OFAssumptionResult R;
+    const SCEV *Ret = SCEVOverflowRewriter::rewrite(S, L, *SE, R.P, true);
+    if (dyn_cast<const SCEVConstant>(Ret) ||
+        dyn_cast<const SCEVAddRecExpr>(Ret)) {
+      R.Ret = Ret;
+    }
+    return R;
+  }
+
+  /// Re-writes the SCEV according to the Predicates in \p Preds, by
+  /// applying overflow assumptions and sinking sext/zext expressions.
+  static inline const SCEV *
+  rewriteSCEVWithAssumptions(const SCEV *S, const Loop *L, ScalarEvolution *SE,
+                             SCEVPredicateSet &Preds) {
+    return SCEVOverflowRewriter::rewrite(S, L, *SE, Preds, false);
+  }
   }
 
 #endif

include/llvm/Transforms/Utils/LoopVersioning.h

 
 #include "llvm/Transforms/Utils/ValueMapper.h"
 
 namespace llvm {
 
 class Loop;
 class LoopAccessInfo;
 class LoopInfo;
+class ScalarEvolution;
 
 /// \brief This class emits a version of the loop where run-time checks ensure
 /// that may-alias pointers can't overlap.
 ///
 /// It currently only supports single-exit loops and assumes that the loop
 /// already has a preheader.
 class LoopVersioning {
 public:
   LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
-                 DominatorTree *DT,
+                 DominatorTree *DT, ScalarEvolution *SE,
                  const SmallVector<int, 8> *PtrToPartition = nullptr);
 
   /// \brief Returns true if we need memchecks to disambiguate may-aliasing
   /// accesses.
   bool needsRuntimeChecks() const;
 
   /// \brief Performs the CFG manipulation part of versioning the loop including
   /// the DominatorTree and LoopInfo updates.
private:
   /// \brief This maps the instructions from VersionedLoop to their counterpart
   /// in NonVersionedLoop.
   ValueToValueMapTy VMap;
 
   /// \brief Analyses used.
   const LoopAccessInfo &LAI;
   LoopInfo *LI;
   DominatorTree *DT;
+  ScalarEvolution *SE;
 };
 }
 
 #endif

lib/Analysis/LoopAccessAnalysis.cpp

DEBUG(dbgs() << "LAA: Replacing SCEV: " << *OrigSCEV << " by: " << *ByOne
                  << "\n");
     return ByOne;
   }
 
   // Otherwise, just return the SCEV of the original pointer.
   return SE->getSCEV(Ptr);
 }
 
+const SCEV *llvm::rewriteSCEV(ScalarEvolution *SE,
+                              const ValueToValueMap &PtrToStride, Value *Ptr,
+                              Value *OrigPtr, const Loop *L,
+                              SCEVPredicateSet &Preds) {
+
+  const SCEV *Ret = replaceSymbolicStrideSCEV(SE, PtrToStride, Ptr, OrigPtr);
+  Ret = rewriteSCEVWithAssumptions(Ret, L, SE, Preds);
+  return Ret;
+}
+
+const SCEV *llvm::convertSCEVToAddRec(ScalarEvolution *SE,
+                                      const ValueToValueMap &PtrToStride,
+                                      Value *Ptr, Value *OrigPtr, const Loop *L,
+                                      SCEVPredicateSet &Preds) {
+
+  const SCEV *Ret = rewriteSCEV(SE, PtrToStride, Ptr, OrigPtr, L, Preds);
+  if (dyn_cast<const SCEVAddRecExpr>(Ret))
+    return Ret;
+
+  OFAssumptionResult R = removeOverflowsWithAssumptions(Ret, L, SE);
+  R.P.add(&Preds);
+  // Only commit to the new predicates if we've succeeded.
+  if (R.Ret && !R.P.isNever()) {
+    Preds = R.P;
+    return R.Ret;
+  }
+  return Ret;
+}
+
 void RuntimePointerChecking::insert(Loop *Lp, Value *Ptr, bool WritePtr,
                                     unsigned DepSetId, unsigned ASId,
-                                    const ValueToValueMap &Strides) {
+                                    const ValueToValueMap &Strides,
+                                    SCEVPredicateSet &Pred) {
   // Get the stride replaced scev.
-  const SCEV *Sc = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
+  const SCEV *Sc = rewriteSCEV(SE, Strides, Ptr, nullptr, Lp, Pred);
   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc);
   assert(AR && "Invalid addrec expression");
-  const SCEV *Ex = SE->getBackedgeTakenCount(Lp);
+  const SCEV *Ex = SE->getGuardedBackedgeTakenCount(Lp, Pred);
   const SCEV *ScEnd = AR->evaluateAtIteration(Ex, *SE);
   Pointers.emplace_back(Ptr, AR->getStart(), ScEnd, WritePtr, DepSetId, ASId,
                         Sc);
 }
 
 bool RuntimePointerChecking::needsChecking(
     const CheckingPtrGroup &M, const CheckingPtrGroup &N,
     const SmallVectorImpl<int> *PtrPartition) const {
   for (unsigned I = 0, EI = M.Members.size(); EI != I; ++I)

 /// dependence checking.
 class AccessAnalysis {
 public:
   /// \brief Read or write access location.
   typedef PointerIntPair<Value *, 1, bool> MemAccessInfo;
   typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet;
 
   AccessAnalysis(const DataLayout &Dl, AliasAnalysis *AA, LoopInfo *LI,
-                 MemoryDepChecker::DepCandidates &DA)
-      : DL(Dl), AST(*AA), LI(LI), DepCands(DA),
-        IsRTCheckAnalysisNeeded(false) {}
+                 MemoryDepChecker::DepCandidates &DA, SCEVPredicateSet &Pred)
+      : DL(Dl), AST(*AA), LI(LI), DepCands(DA), IsRTCheckAnalysisNeeded(false),
+        Pred(Pred) {}
 
   /// \brief Register a load  and whether it is only read from.
   void addLoad(MemoryLocation &Loc, bool IsReadOnly) {
     Value *Ptr = const_cast<Value*>(Loc.Ptr);
     AST.add(Ptr, MemoryLocation::UnknownSize, Loc.AATags);
     Accesses.insert(MemAccessInfo(Ptr, false));
     if (IsReadOnly)
       ReadOnlyPtr.insert(Ptr);
private:
   /// \brief Initial processing of memory accesses determined that we may need
   /// to add memchecks.  Perform the analysis to determine the necessary checks.
   ///
   /// Note that, this is different from isDependencyCheckNeeded.  When we retry
   /// memcheck analysis without dependency checking
   /// (i.e. ShouldRetryWithRuntimeCheck), isDependencyCheckNeeded is cleared
   /// while this remains set if we have potentially dependent accesses.
   bool IsRTCheckAnalysisNeeded;
+
+  /// The SCEV predicate containing all the SCEV-related assumptions.
+  SCEVPredicateSet &Pred;
 };
 
 } // end anonymous namespace
 
 /// \brief Check whether a pointer can participate in a runtime bounds check.
 static bool hasComputableBounds(ScalarEvolution *SE,
-                                const ValueToValueMap &Strides, Value *Ptr) {
-  const SCEV *PtrScev = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
+                                const ValueToValueMap &Strides, Value *Ptr,
+                                Loop *L, SCEVPredicateSet &Pred) {
+  const SCEV *PtrScev = rewriteSCEV(SE, Strides, Ptr, nullptr, L, Pred);
   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
   if (!AR)
     return false;
 
   return AR->isAffine();
 }
 
 bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck,
for (auto A : AS) {
       bool IsWrite = Accesses.count(MemAccessInfo(Ptr, true));
       MemAccessInfo Access(Ptr, IsWrite);
 
       if (IsWrite)
         ++NumWritePtrChecks;
       else
         ++NumReadPtrChecks;
 
-      if (hasComputableBounds(SE, StridesMap, Ptr) &&
-          // When we run after a failing dependency check we have to make sure
-          // we don't have wrapping pointers.
-          (!ShouldCheckStride ||
-           isStridedPtr(SE, Ptr, TheLoop, StridesMap) == 1)) {
+      bool Bounded = hasComputableBounds(SE, StridesMap, Ptr, TheLoop, Pred);
+      if (!Bounded) {
+        convertSCEVToAddRec(SE, StridesMap, Ptr, nullptr, TheLoop, Pred);
+        Bounded = hasComputableBounds(SE, StridesMap, Ptr, TheLoop, Pred);
+      }
+
+      bool ValidStride = true;
+      if (ShouldCheckStride) {
+        ValidStride =
+            (isStridedPtr(SE, Ptr, TheLoop, StridesMap, Pred, true) == 1);
+      }
+
+      if (Bounded && ValidStride) {
         // The id of the dependence set.
         unsigned DepId;
 
         if (IsDepCheckNeeded) {
           Value *Leader = DepCands.getLeaderValue(Access).getPointer();
           unsigned &LeaderId = DepSetId[Leader];
           if (!LeaderId)
             LeaderId = RunningDepId++;
           DepId = LeaderId;
         } else
           // Each access has its own dependence set.
           DepId = RunningDepId++;
 
-        RtCheck.insert(TheLoop, Ptr, IsWrite, DepId, ASId, StridesMap);
+        RtCheck.insert(TheLoop, Ptr, IsWrite, DepId, ASId, StridesMap, Pred);
 
         DEBUG(dbgs() << "LAA: Found a runtime check ptr:" << *Ptr << '\n');
       } else {
         DEBUG(dbgs() << "LAA: Can't find bounds for ptr:" << *Ptr << '\n');
         CanDoRT = false;
       }
     }
 
if (OBO->hasNoSignedWrap() &&
         return OpAR->getLoop() == L && OpAR->getNoWrapFlags(SCEV::FlagNSW);
     }
 
   return false;
 }
 
 /// \brief Check whether the access through \p Ptr has a constant stride.
 int llvm::isStridedPtr(ScalarEvolution *SE, Value *Ptr, const Loop *Lp,
-                       const ValueToValueMap &StridesMap) {
+                       const ValueToValueMap &StridesMap,
+                       SCEVPredicateSet &Pred, bool MakeAssumptions) {
   const Type *Ty = Ptr->getType();
   assert(Ty->isPointerTy() && "Unexpected non-ptr");
 
   // Make sure that the pointer does not point to aggregate types.
   const PointerType *PtrTy = cast<PointerType>(Ty);
   if (PtrTy->getElementType()->isAggregateType()) {
     DEBUG(dbgs() << "LAA: Bad stride - Not a pointer to a scalar type"
           << *Ptr << "\n");
     return 0;
   }
 
-  const SCEV *PtrScev = replaceSymbolicStrideSCEV(SE, StridesMap, Ptr);
+  const SCEV *PtrScev = rewriteSCEV(SE, StridesMap, Ptr, nullptr, Lp, Pred);
 
   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
   if (!AR) {
-    DEBUG(dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer "
-          << *Ptr << " SCEV: " << *PtrScev << "\n");
+    // It's not an AddRecExpr. Try to force an AddRecExpr by making
+    // assumptions which can be checked at run-time.
+    const SCEV *Retry =
+        convertSCEVToAddRec(SE, StridesMap, Ptr, nullptr, Lp, Pred);
+    AR = dyn_cast<const SCEVAddRecExpr>(Retry);
+    if (!AR) {
+      DEBUG(dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer " << *Ptr
+                   << " SCEV: " << *PtrScev << "\n");
       return 0;
     }
+  }
 
-  // The accesss function must stride over the innermost loop.
+  // The access function must stride over the innermost loop.
   if (Lp != AR->getLoop()) {
     DEBUG(dbgs() << "LAA: Bad stride - Not striding over innermost loop " <<
           *Ptr << " SCEV: " << *PtrScev << "\n");
   }
 
   // The address calculation must not wrap. Otherwise, a dependence could be
   // inverted.
   // An inbounds getelementptr that is a AddRec with a unit stride
MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   if (!AIsWrite && !BIsWrite)
     return Dependence::NoDep;
 
   // We cannot check pointers in different address spaces.
   if (APtr->getType()->getPointerAddressSpace() !=
       BPtr->getType()->getPointerAddressSpace())
     return Dependence::Unknown;
 
-  const SCEV *AScev = replaceSymbolicStrideSCEV(SE, Strides, APtr);
-  const SCEV *BScev = replaceSymbolicStrideSCEV(SE, Strides, BPtr);
-
-  int StrideAPtr = isStridedPtr(SE, APtr, InnermostLoop, Strides);
-  int StrideBPtr = isStridedPtr(SE, BPtr, InnermostLoop, Strides);
+  const SCEV *AScev =
+      rewriteSCEV(SE, Strides, APtr, nullptr, InnermostLoop, Pred);
+  const SCEV *BScev =
+      rewriteSCEV(SE, Strides, BPtr, nullptr, InnermostLoop, Pred);
+
+  // Make assumptions here, otherwise we're guaranteed to end up with
+  // an unknown dependence.
+  int StrideAPtr = isStridedPtr(SE, APtr, InnermostLoop, Strides, Pred, true);
+  int StrideBPtr = isStridedPtr(SE, BPtr, InnermostLoop, Strides, Pred, true);
 
   const SCEV *Src = AScev;
   const SCEV *Sink = BScev;
 
   // If the induction step is negative we have to invert source and sink of the
   // dependence.
   if (StrideAPtr < 0) {
     //Src = BScev;
MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx,
   DEBUG(dbgs() << "LAA: Src Scev: " << *Src << "Sink Scev: " << *Sink
         << "(Induction step: " << StrideAPtr <<  ")\n");
   DEBUG(dbgs() << "LAA: Distance for " << *InstMap[AIdx] << " to "
         << *InstMap[BIdx] << ": " << *Dist << "\n");
 
   // Need accesses with constant stride. We don't want to vectorize
   // "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in
   // the address space.
-  if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){
+  if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr) {
     DEBUG(dbgs() << "Pointer access with non-constant stride\n");
     return Dependence::Unknown;
   }
 
   const SCEVConstant *C = dyn_cast<SCEVConstant>(Dist);
   if (!C) {
     DEBUG(dbgs() << "LAA: Dependence because of non-constant distance\n");
     ShouldRetryWithRuntimeCheck = true;
if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch()) {
     DEBUG(dbgs() << "LAA: loop control flow is not understood by analyzer\n");
     emitAnalysis(
         LoopAccessReport() <<
         "loop control flow is not understood by analyzer");
     return false;
   }
 
   // ScalarEvolution needs to be able to find the exit count.
-  const SCEV *ExitCount = SE->getBackedgeTakenCount(TheLoop);
+  const SCEV *ExitCount = SE->getGuardedBackedgeTakenCount(TheLoop, *Pred);
+
   if (ExitCount == SE->getCouldNotCompute()) {
-    emitAnalysis(LoopAccessReport() <<
-                 "could not determine number of loop iterations");
+    emitAnalysis(LoopAccessReport()
+                 << "could not determine number of loop iterations");
     DEBUG(dbgs() << "LAA: SCEV could not compute the loop exit count.\n");
     return false;
   }
 
   return true;
 }
 
 void LoopAccessInfo::analyzeLoop(const ValueToValueMap &Strides) {
void LoopAccessInfo::analyzeLoop(const ValueToValueMap &Strides) {
   if (!Stores.size()) {
     DEBUG(dbgs() << "LAA: Found a read-only loop!\n");
     CanVecMem = true;
     return;
   }
 
   MemoryDepChecker::DepCandidates DependentAccesses;
   AccessAnalysis Accesses(TheLoop->getHeader()->getModule()->getDataLayout(),
-                          AA, LI, DependentAccesses);
+                          AA, LI, DependentAccesses, *Pred);
 
   // Holds the analyzed pointers. We don't want to call GetUnderlyingObjects
   // multiple times on the same object. If the ptr is accessed twice, once
   // for read and once for write, it will only appear once (on the write
   // list). This is okay, since we are going to check for conflicts between
   // writes and between reads and writes, but not between reads and reads.
   ValueSet Seen;
 
for (I = Loads.begin(), IE = Loads.end(); I != IE; ++I) {
     // read list. If we *did* see it before, then it is already in
     // the read-write list. This allows us to vectorize expressions
     // such as A[i] += x;  Because the address of A[i] is a read-write
     // pointer. This only works if the index of A[i] is consecutive.
     // If the address of i is unknown (for example A[B[i]]) then we may
     // read a few words, modify, and write a few words, and some of the
     // words may be written to the same address.
     bool IsReadOnlyPtr = false;
-    if (Seen.insert(Ptr).second || !isStridedPtr(SE, Ptr, TheLoop, Strides)) {
+    if (Seen.insert(Ptr).second ||
+        !isStridedPtr(SE, Ptr, TheLoop, Strides, *Pred, false)) {
       ++NumReads;
       IsReadOnlyPtr = true;
     }
 
     MemoryLocation Loc = MemoryLocation::get(LD);
     // The TBAA metadata could have a control dependency on the predication
     // condition, so we cannot rely on it when determining whether or not we
     // need runtime pointer checks.
std::pair<Instruction *, Instruction *> LoopAccessInfo::addRuntimeCheck(
   return std::make_pair(FirstInst, Check);
 }
 
 LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE,
                                const DataLayout &DL,
                                const TargetLibraryInfo *TLI, AliasAnalysis *AA,
                                DominatorTree *DT, LoopInfo *LI,
                                const ValueToValueMap &Strides)
-    : PtrRtChecking(SE), DepChecker(SE, L), TheLoop(L), SE(SE), DL(DL),
-      TLI(TLI), AA(AA), DT(DT), LI(LI), NumLoads(0), NumStores(0),
-      MaxSafeDepDistBytes(-1U), CanVecMem(false),
+    : Pred(new SCEVPredicateSet), PtrRtChecking(SE), DepChecker(SE, L, *Pred),
+      TheLoop(L), SE(SE), DL(DL), TLI(TLI), AA(AA), DT(DT), LI(LI),
+      NumLoads(0), NumStores(0), MaxSafeDepDistBytes(-1U), CanVecMem(false),
       StoreToLoopInvariantAddress(false) {
   if (canAnalyzeLoop())
     analyzeLoop(Strides);
 }
 
 void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
   if (CanVecMem) {
     if (PtrRtChecking.Need)
void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
 
   // List the pair of accesses need run-time checks to prove independence.
   PtrRtChecking.print(OS, Depth);
   OS << "\n";
 
   OS.indent(Depth) << "Store to invariant address was "
                    << (StoreToLoopInvariantAddress ? "" : "not ")
                    << "found in loop.\n";
+
+  OS.indent(Depth) << "SCEV assumptions:\n";
+  Pred->print(OS, Depth);
 }
 
 const LoopAccessInfo &
 LoopAccessAnalysis::getInfo(Loop *L, const ValueToValueMap &Strides) {
-  auto &LAI = LoopAccessInfoMap[L];
+  DenseMap<Loop *, std::unique_ptr<LoopAccessInfo>> &Map = LoopAccessInfoMap;
+
+  auto &LAI = Map[L];
 
 #ifndef NDEBUG
   assert((!LAI || LAI->NumSymbolicStrides == Strides.size()) &&
          "Symbolic strides changed for loop");
 #endif
 
   if (!LAI) {
     const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();

lib/Analysis/ScalarEvolution.cpp

 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"

 
 static cl::opt<unsigned>
 MaxBruteForceIterations("scalar-evolution-max-iterations", cl::ReallyHidden,
                         cl::desc("Maximum number of iterations SCEV will "
                                  "symbolically execute a constant "
                                  "derived loop"),
                         cl::init(100));
 
+static cl::opt<unsigned>
+OverflowCheckThreshold("force-max-overflow-checks", cl::init(16),
+                        cl::Hidden,
+                        cl::desc("Don't create SCEV predicates with more than "
+                                 "this number of assumptions."));
+
+
 // FIXME: Enable this with XDEBUG when the test suite is clean.
 static cl::opt<bool>
 VerifySCEV("verify-scev",
            cl::desc("Verify ScalarEvolution's backedge taken counts (slow)"));
 
 INITIALIZE_PASS_BEGIN(ScalarEvolution, "scalar-evolution",
                 "Scalar Evolution Analysis", false, true)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)

 /// Note that it is not valid to call this method on a loop without a
 /// loop-invariant backedge-taken count (see
 /// hasLoopInvariantBackedgeTakenCount).
 ///
 const SCEV *ScalarEvolution::getBackedgeTakenCount(const Loop *L) {
   return getBackedgeTakenInfo(L).getExact(this);
 }
 
+const SCEV *
+ScalarEvolution::getGuardedBackedgeTakenCount(const Loop *L,
+                                              SCEVPredicateSet &Predicates) {
+  return getBackedgeTakenInfo(L).getGuardedExact(this, Predicates);
+}
+
 /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except
 /// return the least SCEV value that is known never to be less than the
 /// actual backedge taken count.
 const SCEV *ScalarEvolution::getMaxBackedgeTakenCount(const Loop *L) {
   return getBackedgeTakenInfo(L).getMax(this);
 }
 
 /// PushLoopPHIs - Push PHI nodes in the header of the given loop
ScalarEvolution::BackedgeTakenInfo::getExact(ScalarEvolution *SE) const {
   assert(ExitNotTaken.ExactNotTaken && "uninitialized not-taken info");
 
   const SCEV *BECount = nullptr;
   for (const ExitNotTakenInfo *ENT = &ExitNotTaken;
        ENT != nullptr; ENT = ENT->getNextExit()) {
 
     assert(ENT->ExactNotTaken != SE->getCouldNotCompute() && "bad exit SCEV");
 
+    if (ENT->Pred.isNever() || !ENT->Pred.isAlways())
+      return SE->getCouldNotCompute();
+
     if (!BECount)
       BECount = ENT->ExactNotTaken;
     else if (BECount != ENT->ExactNotTaken)
       return SE->getCouldNotCompute();
   }
   assert(BECount && "Invalid not taken count for loop exit");
   return BECount;
 }
 
+const SCEV *ScalarEvolution::BackedgeTakenInfo::getGuardedExact(
+    ScalarEvolution *SE, SCEVPredicateSet &Predicates) const {
+  // If any exits were not computable, the loop is not computable.
+  if (!ExitNotTaken.isCompleteList())
+    return SE->getCouldNotCompute();
+
+  // We need exactly one computable exit.
+  if (!ExitNotTaken.ExitingBlock)
+    return SE->getCouldNotCompute();
+  assert(ExitNotTaken.ExactNotTaken && "uninitialized not-taken info");
+
+  const SCEV *BECount = nullptr;
+  SCEVPredicateSet Pred;
+  for (const ExitNotTakenInfo *ENT = &ExitNotTaken; ENT != nullptr;
+       ENT = ENT->getNextExit()) {
+
+    assert(ENT->ExactNotTaken != SE->getCouldNotCompute() && "bad exit SCEV");
+
+    if (!BECount) {
+      BECount = ENT->ExactNotTaken;
+    } else if (BECount != ENT->ExactNotTaken) {
+      return SE->getCouldNotCompute();
+    }
+    Predicates.add(&(ENT->Pred));
+  }
+  assert(BECount && "Invalid not taken count for loop exit");
+
+  if (Predicates.isNever())
+    return SE->getCouldNotCompute();
+
+  return BECount;
+}
+
 /// getExact - Get the exact not taken count for this loop exit.
 const SCEV *
 ScalarEvolution::BackedgeTakenInfo::getExact(BasicBlock *ExitingBlock,
                                              ScalarEvolution *SE) const {
-  for (const ExitNotTakenInfo *ENT = &ExitNotTaken;
-       ENT != nullptr; ENT = ENT->getNextExit()) {
+  for (const ExitNotTakenInfo *ENT = &ExitNotTaken; ENT != nullptr;
+       ENT = ENT->getNextExit()) {
 
-    if (ENT->ExitingBlock == ExitingBlock)
+    if (ENT->ExitingBlock == ExitingBlock && ENT->Pred.isAlways())
       return ENT->ExactNotTaken;
   }
   return SE->getCouldNotCompute();
 }
 
 /// getMax - Get the max backedge taken count for the loop.
 const SCEV *
 ScalarEvolution::BackedgeTakenInfo::getMax(ScalarEvolution *SE) const {
+  for (const ExitNotTakenInfo *ENT = &ExitNotTaken; ENT != nullptr;
+       ENT = ENT->getNextExit()) {
+    if (!ENT->Pred.isAlways())
+      return SE->getCouldNotCompute();
+  }
   return Max ? Max : SE->getCouldNotCompute();
 }
 
 bool ScalarEvolution::BackedgeTakenInfo::hasOperand(const SCEV *S,
                                                     ScalarEvolution *SE) const {
   if (Max && Max != SE->getCouldNotCompute() && SE->hasOperand(Max, S))
     return true;
 
for (const ExitNotTakenInfo *ENT = &ExitNotTaken;
     }
   }
   return false;
 }
 
 /// Allocate memory for BackedgeTakenInfo and copy the not-taken count of each
 /// computable exit into a persistent ExitNotTakenInfo array.
 ScalarEvolution::BackedgeTakenInfo::BackedgeTakenInfo(
-  SmallVectorImpl< std::pair<BasicBlock *, const SCEV *> > &ExitCounts,
-  bool Complete, const SCEV *MaxCount) : Max(MaxCount) {
+    SmallVectorImpl<std::pair<BasicBlock *, const SCEV *>> &ExitCounts,
+    SmallVectorImpl<SCEVPredicateSet *> &ExitPreds, bool Complete,
+    const SCEV *MaxCount)
+    : Max(MaxCount) {
 
   if (!Complete)
     ExitNotTaken.setIncomplete();
 
   unsigned NumExits = ExitCounts.size();
   if (NumExits == 0) return;
 
   ExitNotTaken.ExitingBlock = ExitCounts[0].first;
   ExitNotTaken.ExactNotTaken = ExitCounts[0].second;
-  if (NumExits == 1) return;
+  ExitNotTaken.Pred = *ExitPreds[0];
+
+  if (NumExits == 1)
+    return;
 
   // Handle the rare case of multiple computable exits.
   ExitNotTakenInfo *ENT = new ExitNotTakenInfo[NumExits-1];
 
   ExitNotTakenInfo *PrevENT = &ExitNotTaken;
   for (unsigned i = 1; i < NumExits; ++i, PrevENT = ENT, ++ENT) {
     PrevENT->setNextExit(ENT);
     ENT->ExitingBlock = ExitCounts[i].first;
     ENT->ExactNotTaken = ExitCounts[i].second;
+    ENT->Pred = *ExitPreds[i];
   }
 }
 
 /// clear - Invalidate this result and free the ExitNotTakenInfo array.
 void ScalarEvolution::BackedgeTakenInfo::clear() {
   ExitNotTaken.ExitingBlock = nullptr;
   ExitNotTaken.ExactNotTaken = nullptr;
   delete[] ExitNotTaken.getNextExit();
 }
 
 /// ComputeBackedgeTakenCount - Compute the number of times the backedge
 /// of the specified loop will execute.
 ScalarEvolution::BackedgeTakenInfo
 ScalarEvolution::ComputeBackedgeTakenCount(const Loop *L) {
   SmallVector<BasicBlock *, 8> ExitingBlocks;
   L->getExitingBlocks(ExitingBlocks);
 
   SmallVector<std::pair<BasicBlock *, const SCEV *>, 4> ExitCounts;
+  SmallVector<SCEVPredicateSet *, 4> ExitCountPreds;
   bool CouldComputeBECount = true;
   BasicBlock *Latch = L->getLoopLatch(); // may be NULL.
   const SCEV *MustExitMaxBECount = nullptr;
   const SCEV *MayExitMaxBECount = nullptr;
 
   // Compute the ExitLimit for each loop exit. Use this to populate ExitCounts
   // and compute maxBECount.
+  // Do a union of all the predicates here.
   for (unsigned i = 0, e = ExitingBlocks.size(); i != e; ++i) {
     BasicBlock *ExitBB = ExitingBlocks[i];
     ExitLimit EL = ComputeExitLimit(L, ExitBB);
 
     // 1. For each exit that can be computed, add an entry to ExitCounts.
     // CouldComputeBECount is true only if all exits can be computed.
     if (EL.Exact == getCouldNotCompute())
       // We couldn't compute an exact value for this exit, so
       // we won't be able to compute an exact value for the loop.
       CouldComputeBECount = false;
-    else
+    else {
       ExitCounts.push_back(std::make_pair(ExitBB, EL.Exact));
+      ExitCountPreds.push_back(&EL.Pred);
+    }
 
     // 2. Derive the loop's MaxBECount from each exit's max number of
     // non-exiting iterations. Partition the loop exits into two kinds:
     // LoopMustExits and LoopMayExits.
     //
     // If the exit dominates the loop latch, it is a LoopMustExit otherwise it
     // is a LoopMayExit.  If any computable LoopMustExit is found, then
     // MaxBECount is the minimum EL.Max of computable LoopMustExits. Otherwise,
if (EL.Max != getCouldNotCompute() && Latch &&
       if (!MayExitMaxBECount || EL.Max == getCouldNotCompute())
         MayExitMaxBECount = EL.Max;
       else {
         MayExitMaxBECount =
           getUMaxFromMismatchedTypes(MayExitMaxBECount, EL.Max);
       }
     }
   }
-  const SCEV *MaxBECount = MustExitMaxBECount ? MustExitMaxBECount :
-    (MayExitMaxBECount ? MayExitMaxBECount : getCouldNotCompute());
-  return BackedgeTakenInfo(ExitCounts, CouldComputeBECount, MaxBECount);
+  const SCEV *MaxBECount =
+      MustExitMaxBECount
+          ? MustExitMaxBECount
+          : (MayExitMaxBECount ? MayExitMaxBECount : getCouldNotCompute());
+  return BackedgeTakenInfo(ExitCounts, ExitCountPreds, CouldComputeBECount,
+                           MaxBECount);
 }
 
 /// ComputeExitLimit - Compute the number of times the backedge of the specified
 /// loop will execute if it exits via the specified block.
 ScalarEvolution::ExitLimit
 ScalarEvolution::ComputeExitLimit(const Loop *L, BasicBlock *ExitingBlock) {
 
   // Okay, we've chosen an exiting block.  See what condition causes us to
if (BO->getOpcode() == Instruction::And) {
         // For now, be conservative.
         assert(L->contains(FBB) && "Loop block has no successor in loop!");
         if (EL0.Max == EL1.Max)
           MaxBECount = EL0.Max;
         if (EL0.Exact == EL1.Exact)
           BECount = EL0.Exact;
       }
 
-      return ExitLimit(BECount, MaxBECount);
+      SCEVPredicateSet NP;
+      NP.add(&EL0.Pred);
+      NP.add(&EL1.Pred);
+      return ExitLimit(BECount, MaxBECount, NP);
     }
     if (BO->getOpcode() == Instruction::Or) {
       // Recurse on the operands of the or.
       bool EitherMayExit = L->contains(FBB);
       ExitLimit EL0 = ComputeExitLimitFromCond(L, BO->getOperand(0), TBB, FBB,
                                                ControlsExit && !EitherMayExit);
       ExitLimit EL1 = ComputeExitLimitFromCond(L, BO->getOperand(1), TBB, FBB,
                                                ControlsExit && !EitherMayExit);
if (BO->getOpcode() == Instruction::Or) {
         // For now, be conservative.
         assert(L->contains(TBB) && "Loop block has no successor in loop!");
         if (EL0.Max == EL1.Max)
           MaxBECount = EL0.Max;
         if (EL0.Exact == EL1.Exact)
           BECount = EL0.Exact;
       }
 
-      return ExitLimit(BECount, MaxBECount);
+      SCEVPredicateSet NP;
+      NP.add(&EL0.Pred);
+      NP.add(&EL1.Pred);
+      return ExitLimit(BECount, MaxBECount, NP);
     }
   }
 
   // With an icmp, it may be feasible to compute an exact backedge-taken count.
   // Proceed to the next level to examine the icmp.
   if (ICmpInst *ExitCondICmp = dyn_cast<ICmpInst>(ExitCond))
     return ComputeExitLimitFromICmp(L, ExitCondICmp, TBB, FBB, ControlsExit);
 
ScalarEvolution::ComputeExitLimitFromCond(const Loop *L,
 
   // If it's not an integer or pointer comparison then compute it the hard way.
   return ComputeExitCountExhaustively(L, ExitCond, !L->contains(TBB));
 }
 
 /// ComputeExitLimitFromICmp - Compute the number of times the
 /// backedge of the specified loop will execute if its exit condition
 /// were a conditional branch of the ICmpInst ExitCond, TBB, and FBB.
-ScalarEvolution::ExitLimit
-ScalarEvolution::ComputeExitLimitFromICmp(const Loop *L,
-                                          ICmpInst *ExitCond,
-                                          BasicBlock *TBB,
-                                          BasicBlock *FBB,
-                                          bool ControlsExit) {
+ScalarEvolution::ExitLimit ScalarEvolution::ComputeExitLimitFromICmp(
+    const Loop *L, ICmpInst *ExitCond, BasicBlock *TBB, BasicBlock *FBB,
+    bool ControlsExit, bool UseAssumptions) {
 
   // If the condition was exit on true, convert the condition to exit on false
   ICmpInst::Predicate Cond;
   if (!L->contains(FBB))
     Cond = ExitCond->getPredicate();
   else
     Cond = ExitCond->getInversePredicate();
 
if (const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(LHS))
         ConstantRange CompRange(
             ICmpInst::makeConstantRange(Cond, RHSC->getValue()->getValue()));
 
         const SCEV *Ret = AddRec->getNumIterationsInRange(CompRange, *this);
         if (!isa<SCEVCouldNotCompute>(Ret)) return Ret;
       }
 
   switch (Cond) {
-  case ICmpInst::ICMP_NE: {                     // while (X != Y)
+  case ICmpInst::ICMP_NE: { // while (X != Y)
     // Convert to: while (X-Y != 0)
-    ExitLimit EL = HowFarToZero(getMinusSCEV(LHS, RHS), L, ControlsExit);
-    if (EL.hasAnyInfo()) return EL;
+    ExitLimit EL =
+        HowFarToZero(getMinusSCEV(LHS, RHS), L, ControlsExit, UseAssumptions);
+    if (EL.hasAnyInfo())
+      return EL;
     break;
   }
-  case ICmpInst::ICMP_EQ: {                     // while (X == Y)
+  case ICmpInst::ICMP_EQ: { // while (X == Y)
     // Convert to: while (X-Y == 0)
-    ExitLimit EL = HowFarToNonZero(getMinusSCEV(LHS, RHS), L);
-    if (EL.hasAnyInfo()) return EL;
+    ExitLimit EL = HowFarToNonZero(getMinusSCEV(LHS, RHS), L, UseAssumptions);
+    if (EL.hasAnyInfo())
+      return EL;
     break;
   }
   case ICmpInst::ICMP_SLT:
-  case ICmpInst::ICMP_ULT: {                    // while (X < Y)
+  case ICmpInst::ICMP_ULT: { // while (X < Y)
     bool IsSigned = Cond == ICmpInst::ICMP_SLT;
-    ExitLimit EL = HowManyLessThans(LHS, RHS, L, IsSigned, ControlsExit);
-    if (EL.hasAnyInfo()) return EL;
+    ExitLimit EL =
+        HowManyLessThans(LHS, RHS, L, IsSigned, ControlsExit, UseAssumptions);
+    if (EL.hasAnyInfo())
+      return EL;
     break;
   }
   case ICmpInst::ICMP_SGT:
-  case ICmpInst::ICMP_UGT: {                    // while (X > Y)
+  case ICmpInst::ICMP_UGT: { // while (X > Y)
     bool IsSigned = Cond == ICmpInst::ICMP_SGT;
-    ExitLimit EL = HowManyGreaterThans(LHS, RHS, L, IsSigned, ControlsExit);
-    if (EL.hasAnyInfo()) return EL;
+    ExitLimit EL = HowManyGreaterThans(LHS, RHS, L, IsSigned, ControlsExit,
+                                       UseAssumptions);
+    if (EL.hasAnyInfo())
+      return EL;
     break;
   }
   default:
 #if 0
     dbgs() << "ComputeBackedgeTakenCount ";
     if (ExitCond->getOperand(0)->getType()->isUnsigned())
       dbgs() << "[unsigned] ";
     dbgs() << *LHS << "   "
          << Instruction::getOpcodeName(Instruction::ICmp)
          << "   " << *RHS << "\n";
 #endif
     break;
   }
-  return ComputeExitCountExhaustively(L, ExitCond, !L->contains(TBB));
+  ExitLimit EL = ComputeExitCountExhaustively(L, ExitCond, !L->contains(TBB));
+
+  if (EL.hasAnyInfo() || UseAssumptions)
+    return EL;
+
+  // We could not prove what the exit limit is without making
+  // assumptions. Try to compute it using assumptions.
+  return ComputeExitLimitFromICmp(L, ExitCond, TBB, FBB, ControlsExit, true);
 }
 
 ScalarEvolution::ExitLimit
 ScalarEvolution::ComputeExitLimitFromSingleExitSwitch(const Loop *L,
                                                       SwitchInst *Switch,
                                                       BasicBlock *ExitingBlock,
                                                       bool ControlsExit) {
   assert(!L->contains(ExitingBlock) && "Not an exiting block!");

 
 /// HowFarToZero - Return the number of times a backedge comparing the specified
 /// value to zero will execute.  If not computable, return CouldNotCompute.
 ///
 /// This is only used for loops with a "x != y" exit test. The exit condition is
 /// now expressed as a single expression, V = x-y. So the exit test is
 /// effectively V != 0.  We know and take advantage of the fact that this
 /// expression only being used in a comparison by zero context.
-ScalarEvolution::ExitLimit
-ScalarEvolution::HowFarToZero(const SCEV *V, const Loop *L, bool ControlsExit) {
+ScalarEvolution::ExitLimit ScalarEvolution::HowFarToZero(const SCEV *V,
+                                                         const Loop *L,
+                                                         bool ControlsExit,
+                                                         bool UseAssumptions) {
+  SCEVPredicateSet P;
+
   // If the value is a constant
   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
     // If the value is already zero, the branch will execute zero times.
     if (C->getValue()->isZero()) return C;
     return getCouldNotCompute();  // Otherwise it will loop infinitely.
   }
 
   const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(V);
+  if ((!AddRec) && UseAssumptions) {
+    // Try to make this a chrec using runtime assumptions.
+    OFAssumptionResult R = removeOverflowsWithAssumptions(V, L, this);
+    if (!R.Ret)
+      return getCouldNotCompute();
+    if (R.P.isNever())
+      return getCouldNotCompute();
+    AddRec = dyn_cast<SCEVAddRecExpr>(R.Ret);
+    if (!AddRec)
+      return getCouldNotCompute();
+    P.add(&R.P);
+  }
+
   if (!AddRec || AddRec->getLoop() != L)
     return getCouldNotCompute();
 
   // If this is a quadratic (3-term) AddRec {L,+,M,+,N}, find the roots of
   // the quadratic equation to solve it.
   if (AddRec->isQuadratic() && AddRec->getType()->isIntegerTy()) {
     std::pair<const SCEV *,const SCEV *> Roots =
       SolveQuadraticEquation(AddRec, *this);
#endif
         if (!CB->getZExtValue())
           std::swap(R1, R2);   // R1 is the minimum root now.
 
         // We can only use this value if the chrec ends up with an exact zero
         // value at this index.  When solving for "X*X != 5", for example, we
         // should not accept a root of 2.
         const SCEV *Val = AddRec->evaluateAtIteration(R1, *this);
         if (Val->isZero())
-          return R1;  // We found a quadratic root!
+          return ExitLimit(R1, R1, P); // We found a quadratic root!
       }
     }
     return getCouldNotCompute();
   }
 
   // Otherwise we can only handle this if it is affine.
   if (!AddRec->isAffine())
     return getCouldNotCompute();
if (StepC->getValue()->equalsInt(1) || StepC->getValue()->isAllOnesValue()) {
     ConstantRange CR = getUnsignedRange(Start);
     const SCEV *MaxBECount;
     if (!CountDown && CR.getUnsignedMin().isMinValue())
       // When counting up, the worst starting value is 1, not 0.
       MaxBECount = CR.getUnsignedMax().isMinValue()
         ? getConstant(APInt::getMinValue(CR.getBitWidth()))
         : getConstant(APInt::getMaxValue(CR.getBitWidth()));
     else
-      MaxBECount = getConstant(CountDown ? CR.getUnsignedMax()
-                                         : -CR.getUnsignedMin());
-    return ExitLimit(Distance, MaxBECount);
+      MaxBECount =
+          getConstant(CountDown ? CR.getUnsignedMax() : -CR.getUnsignedMin());
+    return ExitLimit(Distance, MaxBECount, P);
   }
 
   // As a special case, handle the instance where Step is a positive power of
   // two. In this case, determining whether Step divides Distance evenly can be
   // done by counting and comparing the number of trailing zeros of Step and
   // Distance.
   if (!CountDown) {
     const APInt &StepV = StepC->getValue()->getValue();
     // StepV.isPowerOf2() returns true if StepV is an positive power of two.  It
     // also returns true if StepV is maximally negative (eg, INT_MIN), but that
     // case is not handled as this code is guarded by !CountDown.
     if (StepV.isPowerOf2() &&
-        GetMinTrailingZeros(Distance) >= StepV.countTrailingZeros())
-      return getUDivExactExpr(Distance, Step);
+        GetMinTrailingZeros(Distance) >= StepV.countTrailingZeros()) {
+      const SCEV *E = getUDivExactExpr(Distance, Step);
+      return ExitLimit(E, E, P);
+    }
   }
 
   // If the condition controls loop exit (the loop exits only if the expression
   // is true) and the addition is no-wrap we can use unsigned divide to
   // compute the backedge count.  In this case, the step may not divide the
   // distance, but we don't care because if the condition is "missed" the loop
   // will have undefined behavior due to wrapping.
   if (ControlsExit && AddRec->getNoWrapFlags(SCEV::FlagNW)) {
     const SCEV *Exact =
         getUDivExpr(Distance, CountDown ? getNegativeSCEV(Step) : Step);
-    return ExitLimit(Exact, Exact);
+    return ExitLimit(Exact, Exact, P);
   }
 
   // Then, try to solve the above equation provided that Start is constant.
-  if (const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start))
-    return SolveLinEquationWithOverflow(StepC->getValue()->getValue(),
-                                        -StartC->getValue()->getValue(),
-                                        *this);
+  if (const SCEVConstant *StartC = dyn_cast<SCEVConstant>(Start)) {
+    const SCEV *E = SolveLinEquationWithOverflow(
+        StepC->getValue()->getValue(), -StartC->getValue()->getValue(), *this);
+    return ExitLimit(E, E, P);
+  }
   return getCouldNotCompute();
 }
 
 /// HowFarToNonZero - Return the number of times a backedge checking the
 /// specified value for nonzero will execute.  If not computable, return
 /// CouldNotCompute
 ScalarEvolution::ExitLimit
-ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L) {
+ScalarEvolution::HowFarToNonZero(const SCEV *V, const Loop *L,
+                                 bool UseAssumptions) {
   // Loops that look like: while (X == 0) are very strange indeed.  We don't
   // handle them yet except for the trivial case.  This could be expanded in the
   // future as needed.
 
   // If the value is a constant, check to see if it is known to be non-zero
   // already.  If so, the backedge will execute zero times.
   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(V)) {
     if (!C->getValue()->isNullValue())

 /// CouldNotCompute.
 ///
 /// @param ControlsExit is true when the LHS < RHS condition directly controls
 /// the branch (loops exits only if condition is true). In this case, we can use
 /// NoWrapFlags to skip overflow checks.
 ScalarEvolution::ExitLimit
 ScalarEvolution::HowManyLessThans(const SCEV *LHS, const SCEV *RHS,
                                   const Loop *L, bool IsSigned,
-                                  bool ControlsExit) {
+                                  bool ControlsExit, bool UseAssumptions) {
+  SCEVPredicateSet P;
+
   // We handle only IV < Invariant
   if (!isLoopInvariant(RHS, L))
     return getCouldNotCompute();
 
   const SCEVAddRecExpr *IV = dyn_cast<SCEVAddRecExpr>(LHS);
 
+  if (!IV && UseAssumptions) {
+    // Try to make this a chrec using runtime assumptions.
+    OFAssumptionResult R = removeOverflowsWithAssumptions(LHS, L, this);
+    if (!R.Ret)
+      return getCouldNotCompute();
+    if (R.P.isNever())
+      return getCouldNotCompute();
+    IV = dyn_cast<SCEVAddRecExpr>(R.Ret);
+    if (!IV)
+      return getCouldNotCompute();
+    P.add(&R.P);
+  }
+
   // Avoid weird loops
   if (!IV || IV->getLoop() != L || !IV->isAffine())
     return getCouldNotCompute();
 
+  // FIXME: we can assume NoWrap here if necessary and check at runtime.
   bool NoWrap = ControlsExit &&
                 IV->getNoWrapFlags(IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW);
 
   const SCEV *Stride = IV->getStepRecurrence(*this);
 
   // Avoid negative or zero stride values
   if (!isKnownPositive(Stride))
     return getCouldNotCompute();
if (isa<SCEVConstant>(BECount))
     MaxBECount = BECount;
   else
     MaxBECount = computeBECount(getConstant(MaxEnd - MinStart),
                                 getConstant(MinStride), false);
 
   if (isa<SCEVCouldNotCompute>(MaxBECount))
     MaxBECount = BECount;
 
-  return ExitLimit(BECount, MaxBECount);
+  return ExitLimit(BECount, MaxBECount, P);
 }
 
 ScalarEvolution::ExitLimit
 ScalarEvolution::HowManyGreaterThans(const SCEV *LHS, const SCEV *RHS,
                                      const Loop *L, bool IsSigned,
-                                     bool ControlsExit) {
+                                     bool ControlsExit, bool UseAssumptions) {
+  SCEVPredicateSet P;
+
   // We handle only IV > Invariant
   if (!isLoopInvariant(RHS, L))
     return getCouldNotCompute();
 
   const SCEVAddRecExpr *IV = dyn_cast<SCEVAddRecExpr>(LHS);
+  if (!IV && UseAssumptions) {
+    // Try to make this a chrec using runtime assumptions.
+    OFAssumptionResult R = removeOverflowsWithAssumptions(LHS, L, this);
+    if (!R.Ret)
+      return getCouldNotCompute();
+    if (R.P.isNever())
+      return getCouldNotCompute();
+    IV = dyn_cast<SCEVAddRecExpr>(R.Ret);
+    if (!IV)
+      return getCouldNotCompute();
+    P.add(&R.P);
+  }
 
   // Avoid weird loops
   if (!IV || IV->getLoop() != L || !IV->isAffine())
     return getCouldNotCompute();
 
   bool NoWrap = ControlsExit &&
                 IV->getNoWrapFlags(IsSigned ? SCEV::FlagNSW : SCEV::FlagNUW);
 
if (isa<SCEVConstant>(BECount))
     MaxBECount = BECount;
   else
     MaxBECount = computeBECount(getConstant(MaxStart - MinEnd),
                                 getConstant(MinStride), false);
 
   if (isa<SCEVCouldNotCompute>(MaxBECount))
     MaxBECount = BECount;
 
-  return ExitLimit(BECount, MaxBECount);
+  return ExitLimit(BECount, MaxBECount, P);
 }
 
 /// getNumIterationsInRange - Return the number of iterations of this loop that
 /// produce values in the specified constant range.  Another way of looking at
 /// this is that it returns the first iteration number where the value is not in
 /// the condition, thus computing the exit count. If the iteration count can't
 /// be computed, an instance of SCEVCouldNotCompute is returned.
 const SCEV *SCEVAddRecExpr::getNumIterationsInRange(ConstantRange Range,

 }
 
 ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
   : CallbackVH(V), SE(se) {}
 
 //===----------------------------------------------------------------------===//
 //                   ScalarEvolution Class Implementation
 //===----------------------------------------------------------------------===//
-
 ScalarEvolution::ScalarEvolution()
     : FunctionPass(ID), WalkingBEDominatingConds(false), ValuesAtScopes(64),
       LoopDispositions(64), BlockDispositions(64), FirstUnknown(nullptr) {
   initializeScalarEvolutionPass(*PassRegistry::getPassRegistry());
 }
 
 bool ScalarEvolution::runOnFunction(Function &F) {
   this->F = &F;
if (OldI->second != NewI->second &&
              << "' changed from '" << OldI->second
              << "' to '" << NewI->second << "'!\n";
       std::abort();
     }
   }
 
   // TODO: Verify more things.
 }
+
+static Value *generateOverflowCheck(const SCEVAddRecExpr *AR, Instruction *Loc,
+                                    bool Signed, ScalarEvolution *SE,
+                                    const DataLayout *DL, SCEVExpander &Exp) {
+
+  Module *M = Loc->getParent()->getParent()->getParent();
+  IRBuilder<> OFBuilder(Loc);
+  Value *AddF, *MulF;
+  if (Signed) {
+    AddF = Intrinsic::getDeclaration(M, Intrinsic::sadd_with_overflow,
+                                     AR->getType());
+    MulF = Intrinsic::getDeclaration(M, Intrinsic::smul_with_overflow,
+                                     AR->getType());
+  } else {
+    AddF = Intrinsic::getDeclaration(M, Intrinsic::uadd_with_overflow,
+                                     AR->getType());
+    MulF = Intrinsic::getDeclaration(M, Intrinsic::umul_with_overflow,
+                                     AR->getType());
+  }
+  Value *Start;
+  Value *Stride;
+
+  SCEVPredicateSet MP;
+  const SCEV *ExitCount = SE->getGuardedBackedgeTakenCount(AR->getLoop(), MP);
+
+  unsigned DstBits = AR->getType()->getPrimitiveSizeInBits();
+  unsigned SrcBits = ExitCount->getType()->getPrimitiveSizeInBits();
+
+  if (SrcBits < DstBits) {
+    // We need to extend
+    if (Signed)
+      ExitCount = SE->getNoopOrSignExtend(ExitCount, AR->getType());
+    else
+      ExitCount = SE->getNoopOrZeroExtend(ExitCount, AR->getType());
+  }
+
+  assert(ExitCount != SE->getCouldNotCompute() && "Invalid loop count");
+  Value *TripCount = Exp.expandCodeFor(ExitCount, ExitCount->getType(), Loc);
+  Value *TripCountCheck = nullptr;
+
+  // We might need to truncate TripCount
+  // If this is the case, we need to make sure that this is legal.
+  if (SrcBits > DstBits) {
+    APInt CmpMaxValue = Signed ? APInt::getSignedMaxValue(DstBits).sext(SrcBits)
+                               : APInt::getMaxValue(DstBits).zext(SrcBits);
+    // The min value only makes sense for signed checks.
+
+    ConstantInt *CTMax = ConstantInt::get(M->getContext(), CmpMaxValue);
+    CmpInst::Predicate P = Signed ? ICmpInst::ICMP_SGT : ICmpInst::ICMP_UGT;
+    TripCountCheck = OFBuilder.CreateICmp(P, TripCount, CTMax);
+
+    if (Signed) {
+      APInt CmpMinValue = APInt::getSignedMinValue(DstBits).sext(SrcBits);
+      ConstantInt *CTMin = ConstantInt::get(M->getContext(), CmpMinValue);
+      Value *MinCheck =
+          OFBuilder.CreateICmp(ICmpInst::ICMP_SLT, TripCount, CTMin);
+      TripCountCheck = OFBuilder.CreateOr(TripCountCheck, MinCheck);
+    }
+
+    TripCount = OFBuilder.CreateTrunc(TripCount, AR->getType());
+  }
+
+  // We need to truncate or extend TripCount to the type used by the SCEV
+  // Extension is not a problem.
+  Start = Exp.expandCodeFor(AR->getStart(), AR->getStart()->getType(), Loc);
+
+  // This is an affine expression
+  Stride =
+      Exp.expandCodeFor(AR->getOperand(1), AR->getOperand(1)->getType(), Loc);
+
+  CallInst *Mul = OFBuilder.CreateCall(MulF, {Stride, TripCount}, "mul");
+  Value *MulV = OFBuilder.CreateExtractValue(Mul, 0, "mul.result");
+  Value *OfMul = OFBuilder.CreateExtractValue(Mul, 1, "mul.overflow");
+  CallInst *Add = OFBuilder.CreateCall(AddF, {MulV, Start}, "uadd");
+  Value *OfAdd = OFBuilder.CreateExtractValue(Add, 1, "add.overflow");
+  Value *Overflow = OFBuilder.CreateOr(OfMul, OfAdd, "overflow");
+
+  if (TripCountCheck) {
+    Overflow = OFBuilder.CreateOr(Overflow, TripCountCheck);
+  }
+
+  return Overflow;
+}
+
+static Instruction *getFirstInst(Instruction *FirstInst, Value *V,
+                                 Instruction *Loc) {
+  if (FirstInst)
+    return FirstInst;
+  if (Instruction *I = dyn_cast<Instruction>(V))
+    return I->getParent() == Loc->getParent() ? I : nullptr;
+  return nullptr;
+}
+
+//// SCEV predicates
+SCEVPredicate::SCEVPredicate(unsigned short Type) : SCEVPredicateType(Type) {}
+
+SCEVAddRecOverflowPredicate::SCEVAddRecOverflowPredicate(
+    const SCEV *AR, SCEV::NoWrapFlags Flags)
+    : SCEVPredicate(pAddRecOverflow), AR(AR), Flags(Flags) {
+  assert(dyn_cast<const SCEVAddRecExpr>(AR) &&
+         "Can only create a"
+         "SCEVAddRecOverflowPredicate using a SCEVAddRecExpr");
+}
+
+bool SCEVAddRecOverflowPredicate::contains(const SCEVPredicate *N) const {
+  const SCEVAddRecOverflowPredicate *OP =
+      dyn_cast<const SCEVAddRecOverflowPredicate>(N);
+
+  if (!OP)
+    return false;
+
+  if (OP->getExpr() != AR)
+    return false;
+
+  if ((OP->getFlags() & getFlags()) != OP->getFlags())
+    return false;
+
+  return true;
+}
+
+bool SCEVAddRecOverflowPredicate::isAlways() const {
+  const SCEVAddRecExpr *A = static_cast<const SCEVAddRecExpr *>(AR);
+  return ScalarEvolution::clearFlags(Flags, A->getNoWrapFlags()) ==
+         SCEV::FlagAnyWrap;
+}
+
+bool SCEVAddRecOverflowPredicate::isNever() const { return false; }
+
+Value *SCEVAddRecOverflowPredicate::generateCheck(Instruction *Loc,
+                                                  ScalarEvolution *SE,
+                                                  const DataLayout *DL,
+                                                  SCEVExpander &Exp) {
+  IRBuilder<> OFBuilder(Loc);
+  const SCEVAddRecExpr *A = static_cast<const SCEVAddRecExpr *>(AR);
+  Value *OverflowRuntimeCheck = nullptr;
+
+  if (Flags & SCEV::FlagNUW) {
+    // Add a check for NUW
+    Value *Overflow = generateOverflowCheck(A, Loc, false, SE, DL, Exp);
+
+    if (!OverflowRuntimeCheck)
+      OverflowRuntimeCheck = Overflow;
+    else
+      OverflowRuntimeCheck = OFBuilder.CreateOr(OverflowRuntimeCheck, Overflow);
+  }
+  if (Flags & SCEV::FlagNSW) {
+    // Add a check for NSW
+    Value *Overflow = generateOverflowCheck(A, Loc, true, SE, DL, Exp);
+
+    if (!OverflowRuntimeCheck)
+      OverflowRuntimeCheck = Overflow;
+    else
+      OverflowRuntimeCheck = OFBuilder.CreateOr(OverflowRuntimeCheck, Overflow);
+  }
+  return OverflowRuntimeCheck;
+}
+
+void SCEVAddRecOverflowPredicate::print(raw_ostream &OS, unsigned Depth) const {
+  OS.indent(Depth) << *getExpr() << " Added Flags: ";
+  if (SCEV::FlagNUW & getFlags())
+    OS << "<nuw>";
+  if (SCEV::FlagNSW & getFlags())
+    OS << "<nsw>";
+  OS << "\n";
+}
+
+SCEVPredicateSet::SCEVPredicateSet() : SCEVPredicate(pSet), Never(false) {}
+
+SCEVPredicateSet::SCEVPredicateSet(const SCEVPredicateSet &Old)
+    : SCEVPredicateSet() {
+  this->Never = Old.Never;
+  if (Never)
+    return;
+  AddRecOverflows = Old.AddRecOverflows;
+  for (unsigned II = 0; II < AddRecOverflows.size(); ++II) {
+    Preds.push_back(&AddRecOverflows[II]);
+  }
+}
+
+bool SCEVPredicateSet::isAlways() const {
+  if (Never)
+    return false;
+
+  for (auto II = Preds.begin(), EE = Preds.end(); II != EE; ++II) {
+    const SCEVPredicate *OA = *II;
+    if (!OA->isAlways())
+      return false;
+  }
+
+  return true;
+}
+
+bool SCEVPredicateSet::isNever() const { return Never; }
+
+std::pair<Instruction *, Instruction *>
+SCEVPredicateSet::generateGuardCond(Instruction *Loc, ScalarEvolution *SE) {
+  Instruction *tnullptr = nullptr;
+
+  assert(!Never && "Cannot generate a runtime check on "
+                   "a predicate with the Never flag set");
+
+  if (isAlways())
+    return std::pair<Instruction *, Instruction *>(tnullptr, tnullptr);
+
+  IRBuilder<> OFBuilder(Loc);
+  Instruction *FirstInst = nullptr;
+  Module *M = Loc->getParent()->getParent()->getParent();
+  const DataLayout &DL = M->getDataLayout();
+  SCEVExpander Exp(*SE, DL, "start");
+
+  Value *Check = generateCheck(Loc, SE, &DL, Exp);
+
+  if (!Check)
+    return std::make_pair(nullptr, nullptr);
+
+  Instruction *CheckInst =
+      BinaryOperator::CreateOr(Check, ConstantInt::getFalse(M->getContext()));
+  OFBuilder.Insert(CheckInst, "scev.check");
+
+  FirstInst = getFirstInst(FirstInst, CheckInst, Loc);
+  return std::make_pair(FirstInst, CheckInst);
+}
+
+Value *SCEVPredicateSet::generateCheck(Instruction *Loc, ScalarEvolution *SE,
+                                       const DataLayout *DL,
+                                       SCEVExpander &Exp) {
+
+  IRBuilder<> OFBuilder(Loc);
+  Value *AllCheck = nullptr;
+
+  // Loop over all checks in this set.
+  for (auto II = Preds.begin(), EE = Preds.end(); II != EE; ++II) {
+    SCEVPredicate *OA = *II;
+
+    if (OA->isAlways())
+      continue;
+
+    Value *CheckResult = OA->generateCheck(Loc, SE, DL, Exp);
+
+    if (!AllCheck)
+      AllCheck = CheckResult;
+    else
+      AllCheck = OFBuilder.CreateOr(AllCheck, CheckResult);
+  }
+
+  return AllCheck;
+}
+
+bool SCEVPredicateSet::contains(const SCEVPredicate *N) const {
+  if (Never)
+    return false;
+
+  if (const SCEVPredicateSet *Set = dyn_cast<const SCEVPredicateSet>(N)) {
+    for (auto II = Set->Preds.begin(), EE = Set->Preds.end(); II != EE; ++II) {
+      if (!contains(*II))
+        return false;
+    }
+    return true;
+  }
+  for (auto II = Preds.begin(), EE = Preds.end(); II != EE; ++II) {
+    if ((*II)->contains(N))
+      return true;
+  }
+  return false;
+}
+
+void SCEVPredicateSet::print(raw_ostream &OS, unsigned Depth) const {
+  for (auto II = Preds.begin(), EE = Preds.end(); II != EE; ++II)
+    (*II)->print(OS, Depth);
+}
+
+void SCEVPredicateSet::add(const SCEVPredicate *N) {
+  if (Preds.size() > OverflowCheckThreshold || N->isNever()) {
+    Never = true;
+    return;
+  }
+
+  if (const SCEVAddRecOverflowPredicate *OP =
+          dyn_cast<const SCEVAddRecOverflowPredicate>(N)) {
+
+    const SCEVAddRecExpr *AR =
+        static_cast<const SCEVAddRecExpr *>(OP->getExpr());
+    for (unsigned II = 0, EE = AddRecOverflows.size(); II < EE; ++II) {
+      if (AddRecOverflows[II].getExpr() == AR) {
+        AddRecOverflows[II].addFlags(OP->getFlags());
+        return;
+      }
+    }
+    AddRecOverflows.push_back(*OP);
+    Preds.push_back(&AddRecOverflows.back());
+
+  } else if (const SCEVPredicateSet *Set =
+                 dyn_cast<const SCEVPredicateSet>(N)) {
+    for (auto II = Set->Preds.begin(), EE = Set->Preds.end(); II != EE; ++II) {
+      add(*II);
+    }
+  } else
+    llvm_unreachable("Unknown SCEV predicate type!");
+}
+
+void SCEVAddRecOverflowPredicate::addFlags(SCEV::NoWrapFlags AddedFlags) {
+  Flags = ScalarEvolution::setFlags(Flags, AddedFlags);
+}

lib/Transforms/Scalar/LoopDistribute.cpp

public:
   LoopDistribute() : FunctionPass(ID) {
     initializeLoopDistributePass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &F) override {
     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     LAA = &getAnalysis<LoopAccessAnalysis>();
     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    SE = &getAnalysis<ScalarEvolution>();
 
     // Build up a worklist of inner-loops to vectorize. This is necessary as the
     // act of distributing a loop creates new loops and can invalidate iterators
     // across the loops.
     SmallVector<Loop *, 8> Worklist;
 
     for (Loop *TopLevelLoop : *LI)
       for (Loop *L : depth_first(TopLevelLoop))
         // We only handle inner-most loops.
         if (L->empty())
           Worklist.push_back(L);
 
     // Now walk the identified inner loops.
     bool Changed = false;
     for (Loop *L : Worklist)
       Changed |= processLoop(L);
 
     // Process each loop nest in the function.
     return Changed;
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<ScalarEvolution>();
     AU.addRequired<LoopInfoWrapperPass>();
     AU.addPreserved<LoopInfoWrapperPass>();
     AU.addRequired<LoopAccessAnalysis>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
   }
 
   static char ID;
bool processLoop(Loop *L) {
     // the loop.  (Also split if this has no predecessor, i.e. entry, because we
     // rely on PH having a predecessor.)
     if (!PH->getSinglePredecessor() || &*PH->begin() != PH->getTerminator())
       SplitBlock(PH, PH->getTerminator(), DT, LI);
 
     // If we need run-time checks to disambiguate pointers are run-time, version
     // the loop now.
     auto PtrToPartition = Partitions.computePartitionSetForPointers(LAI);
-    LoopVersioning LVer(LAI, L, LI, DT, &PtrToPartition);
+    LoopVersioning LVer(LAI, L, LI, DT, SE, &PtrToPartition);
     if (LVer.needsRuntimeChecks()) {
       DEBUG(dbgs() << "\nPointers:\n");
       DEBUG(LAI.getRuntimePointerChecking()->print(dbgs(), 0, &PtrToPartition));
       LVer.versionLoop(this);
       LVer.addPHINodes(DefsUsedOutside);
     }
 
     // Create identical copies of the original loop for each partition and hook
bool processLoop(Loop *L) {
     ++NumLoopsDistributed;
     return true;
   }
 
   // Analyses used.
   LoopInfo *LI;
   LoopAccessAnalysis *LAA;
   DominatorTree *DT;
+  ScalarEvolution *SE;
 };
 } // anonymous namespace
 
 char LoopDistribute::ID;
 static const char ldist_name[] = "Loop Distribition";
 
 INITIALIZE_PASS_BEGIN(LoopDistribute, LDIST_NAME, ldist_name, false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopAccessAnalysis)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
 INITIALIZE_PASS_END(LoopDistribute, LDIST_NAME, ldist_name, false, false)
 
 namespace llvm {
 FunctionPass *createLoopDistributePass() { return new LoopDistribute(); }
 }

lib/Transforms/Utils/LoopVersioning.cpp

 #include "llvm/IR/Dominators.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/LoopVersioning.h"
 
 using namespace llvm;
 
 LoopVersioning::LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
-                               DominatorTree *DT,
+                               DominatorTree *DT, ScalarEvolution *SE,
                                const SmallVector<int, 8> *PtrToPartition)
     : VersionedLoop(L), NonVersionedLoop(nullptr),
-      PtrToPartition(PtrToPartition), LAI(LAI), LI(LI), DT(DT) {
+      PtrToPartition(PtrToPartition), LAI(LAI), LI(LI), DT(DT), SE(SE) {
   assert(L->getExitBlock() && "No single exit block");
   assert(L->getLoopPreheader() && "No preheader");
 }
 
 bool LoopVersioning::needsRuntimeChecks() const {
-  return LAI.getRuntimePointerChecking()->needsAnyChecking(PtrToPartition);
+  return LAI.getRuntimePointerChecking()->needsAnyChecking(PtrToPartition) ||
+         !LAI.Pred->isAlways();
 }
 
 void LoopVersioning::versionLoop(Pass *P) {
   Instruction *FirstCheckInst;
   Instruction *MemRuntimeCheck;
+  Instruction *OverflowRuntimeCheck;
+  Instruction *RuntimeCheck = nullptr;
   // Add the memcheck in the original preheader (this is empty initially).
   BasicBlock *MemCheckBB = VersionedLoop->getLoopPreheader();
   std::tie(FirstCheckInst, MemRuntimeCheck) =
       LAI.addRuntimeCheck(MemCheckBB->getTerminator(), PtrToPartition);
-  assert(MemRuntimeCheck && "called even though needsAnyChecking = false");
+
+  std::tie(FirstCheckInst, OverflowRuntimeCheck) =
+      LAI.Pred->generateGuardCond(MemCheckBB->getTerminator(), SE);
+
+  if (MemRuntimeCheck && OverflowRuntimeCheck) {
+    RuntimeCheck = BinaryOperator::Create(Instruction::Or, MemRuntimeCheck,
+                                          OverflowRuntimeCheck, "ldist.safe");
+    RuntimeCheck->insertBefore(MemCheckBB->getTerminator());
+  } else
+    RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : OverflowRuntimeCheck;
+
+  assert(RuntimeCheck && "called even though we don't need "
+                         "any runtime checks");
 
   // Rename the block to make the IR more readable.
   MemCheckBB->setName(VersionedLoop->getHeader()->getName() + ".lver.memcheck");
 
   // Create empty preheader for the loop (and after cloning for the
   // non-versioned loop).
   BasicBlock *PH = SplitBlock(MemCheckBB, MemCheckBB->getTerminator(), DT, LI);
   PH->setName(VersionedLoop->getHeader()->getName() + ".ph");
 
   // Clone the loop including the preheader.
   //
   // FIXME: This does not currently preserve SimplifyLoop because the exit
   // block is a join between the two loops.
   SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks;
   NonVersionedLoop =
       cloneLoopWithPreheader(PH, MemCheckBB, VersionedLoop, VMap, ".lver.orig",
                              LI, DT, NonVersionedLoopBlocks);
   remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
 
   // Insert the conditional branch based on the result of the memchecks.
   Instruction *OrigTerm = MemCheckBB->getTerminator();
   BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
-                     VersionedLoop->getLoopPreheader(), MemRuntimeCheck,
-                     OrigTerm);
+                     VersionedLoop->getLoopPreheader(), RuntimeCheck, OrigTerm);
   OrigTerm->eraseFromParent();
 
   // The loops merge in the original exit block.  This is now dominated by the
   // memchecking block.
   DT->changeImmediateDominator(VersionedLoop->getExitBlock(), MemCheckBB);
 }
 
 void LoopVersioning::addPHINodes(

lib/Transforms/Vectorize/LoopVectorize.cpp

 /// aspects. The InnerLoopVectorizer relies on the
 /// LoopVectorizationLegality class to provide information about the induction
 /// and reduction variables that were found to a given vectorization factor.
 class InnerLoopVectorizer {
 public:
   InnerLoopVectorizer(Loop *OrigLoop, ScalarEvolution *SE, LoopInfo *LI,
                       DominatorTree *DT, const TargetLibraryInfo *TLI,
                       const TargetTransformInfo *TTI, unsigned VecWidth,
-                      unsigned UnrollFactor)
+                      unsigned UnrollFactor, SCEVPredicateSet &Pred)
       : OrigLoop(OrigLoop), SE(SE), LI(LI), DT(DT), TLI(TLI), TTI(TTI),
         VF(VecWidth), UF(UnrollFactor), Builder(SE->getContext()),
         Induction(nullptr), OldInduction(nullptr), WidenMap(UnrollFactor),
-        Legal(nullptr), AddedSafetyChecks(false) {}
+        Legal(nullptr), AddedSafetyChecks(false), Pred(Pred) {}
 
   // Perform the actual loop widening (vectorization).
   void vectorize(LoopVectorizationLegality *L) {
     Legal = L;
     // Create a new empty loop. Unlink the old loop and connect the new one.
     createEmptyLoop();
     // Widen each instruction in the old loop to a new one in the new loop.
     // Use the Legality module to find the induction and reduction variables.
typedef DenseMap<std::pair<BasicBlock*, BasicBlock*>,
                    VectorParts> EdgeMaskCache;
 
   /// \brief Add checks for strides that were assumed to be 1.
   ///
   /// Returns the last check instruction and the first check instruction in the
   /// pair as (first, last).
   std::pair<Instruction *, Instruction *> addStrideCheck(Instruction *Loc);
 
+  // Adds code to check the overflow assumptions made by SCEV
+  std::pair<Instruction *, Instruction *>
+  addRuntimeOverflowChecks(Instruction *Loc);
+
   /// Create an empty loop, based on the loop ranges of the old loop.
   void createEmptyLoop();
   /// Copy and widen the instructions from the old loop.
   virtual void vectorizeLoop();
 
   /// \brief The Loop exit block may have single value PHI nodes where the
   /// incoming value is 'Undef'. While vectorizing we only handled real values
   /// that were defined inside the loop. Here we fix the 'undef case'.
protected:
   /// Maps scalars to widened vectors.
   ValueMap WidenMap;
   EdgeMaskCache MaskCache;
 
   LoopVectorizationLegality *Legal;
 
   // Record whether runtime check is added.
   bool AddedSafetyChecks;
+
+  /// The SCEV predicate containing all the SCEV-related assumptions.
+  SCEVPredicateSet &Pred;
 };
 
 class InnerLoopUnroller : public InnerLoopVectorizer {
 public:
   InnerLoopUnroller(Loop *OrigLoop, ScalarEvolution *SE, LoopInfo *LI,
                     DominatorTree *DT, const TargetLibraryInfo *TLI,
-                    const TargetTransformInfo *TTI, unsigned UnrollFactor)
-      : InnerLoopVectorizer(OrigLoop, SE, LI, DT, TLI, TTI, 1, UnrollFactor) {}
+                    const TargetTransformInfo *TTI, unsigned UnrollFactor,
+                    SCEVPredicateSet &Pred)
+      : InnerLoopVectorizer(OrigLoop, SE, LI, DT, TLI, TTI, 1, UnrollFactor,
+                            Pred) {}
 
 private:
   void scalarizeInstruction(Instruction *Instr,
                             bool IfPredicateStore = false) override;
   void vectorizeMemoryInstruction(Instruction *Instr) override;
   Value *getBroadcastInstrs(Value *V) override;
   Value *getStepVector(Value *Val, int StartIdx, Value *Step) override;
   Value *reverseVector(Value *Vec) override;

 /// Use this class to analyze interleaved accesses only when we can vectorize
 /// a loop. Otherwise it's meaningless to do analysis as the vectorization
 /// on interleaved accesses is unsafe.
 ///
 /// The analysis collects interleave groups and records the relationships
 /// between the member and the group in a map.
 class InterleavedAccessInfo {
 public:
-  InterleavedAccessInfo(ScalarEvolution *SE, Loop *L, DominatorTree *DT)
-      : SE(SE), TheLoop(L), DT(DT) {}
+  InterleavedAccessInfo(ScalarEvolution *SE, Loop *L, DominatorTree *DT,
+                        SCEVPredicateSet &Pred)
+      : SE(SE), TheLoop(L), DT(DT), Pred(Pred) {}
 
   ~InterleavedAccessInfo() {
     SmallSet<InterleaveGroup *, 4> DelSet;
     // Avoid releasing a pointer twice.
     for (auto &I : InterleaveGroupMap)
       DelSet.insert(I.second);
     for (auto *Ptr : DelSet)
       delete Ptr;
if (InterleaveGroupMap.count(Instr))
       return InterleaveGroupMap.find(Instr)->second;
     return nullptr;
   }
 
 private:
   ScalarEvolution *SE;
   Loop *TheLoop;
   DominatorTree *DT;
+  /// The SCEV predicate containing all the SCEV-related assumptions.
+  SCEVPredicateSet &Pred;
 
   /// Holds the relationships between the members and the interleave group.
   DenseMap<Instruction *, InterleaveGroup *> InterleaveGroupMap;
 
   /// \brief The descriptor for a strided memory access.
   struct StrideDescriptor {
     StrideDescriptor(int Stride, const SCEV *Scev, unsigned Size,
                      unsigned Align)

 /// etc. This code reflects the capabilities of InnerLoopVectorizer.
 /// This class is also used by InnerLoopVectorizer for identifying
 /// induction variable and the different reduction variables.
 class LoopVectorizationLegality {
 public:
   LoopVectorizationLegality(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
                             TargetLibraryInfo *TLI, AliasAnalysis *AA,
                             Function *F, const TargetTransformInfo *TTI,
-                            LoopAccessAnalysis *LAA)
+                            LoopAccessAnalysis *LAA, SCEVPredicateSet &Pred)
       : NumPredStores(0), TheLoop(L), SE(SE), TLI(TLI), TheFunction(F),
-        TTI(TTI), DT(DT), LAA(LAA), LAI(nullptr), InterleaveInfo(SE, L, DT),
-        Induction(nullptr), WidestIndTy(nullptr), HasFunNoNaNAttr(false) {}
+        TTI(TTI), DT(DT), LAA(LAA), LAI(nullptr),
+        InterleaveInfo(SE, L, DT, Pred), Induction(nullptr),
+        WidestIndTy(nullptr), HasFunNoNaNAttr(false), Pred(Pred) {}
 
   /// This enum represents the kinds of inductions that we support.
   enum InductionKind {
     IK_NoInduction,  ///< Not an induction variable.
     IK_IntInduction, ///< Integer induction variable. Step = C.
     IK_PtrInduction  ///< Pointer induction var. Step = C / sizeof(elem).
   };
 
private:
   /// Can we assume the absence of NaNs.
   bool HasFunNoNaNAttr;
 
   ValueToValueMap Strides;
   SmallPtrSet<Value *, 8> StrideSet;
 
   /// While vectorizing these instructions we have to generate a
   /// call to the appropriate masked intrinsic
-  SmallPtrSet<const Instruction*, 8> MaskedOp;
+  SmallPtrSet<const Instruction *, 8> MaskedOp;
+
+  /// The SCEV predicate containing all the SCEV-related assumptions.
+  SCEVPredicateSet &Pred;
 };
 
 /// LoopVectorizationCostModel - estimates the expected speedups due to
 /// vectorization.
 /// In many cases vectorization is not profitable. This can happen because of
 /// a number of reasons. In this class we mainly attempt to predict the
 /// expected speedup/slowdowns due to the supported instruction set. We use the
 /// TargetTransformInfo to query the different backends for the cost of
 /// different operations.
 class LoopVectorizationCostModel {
 public:
   LoopVectorizationCostModel(Loop *L, ScalarEvolution *SE, LoopInfo *LI,
                              LoopVectorizationLegality *Legal,
                              const TargetTransformInfo &TTI,
                              const TargetLibraryInfo *TLI, AssumptionCache *AC,
-                             const Function *F, const LoopVectorizeHints *Hints)
+                             const Function *F, const LoopVectorizeHints *Hints,
+                             SCEVPredicateSet &Pred)
       : TheLoop(L), SE(SE), LI(LI), Legal(Legal), TTI(TTI), TLI(TLI),
-        TheFunction(F), Hints(Hints) {
+        TheFunction(F), Hints(Hints), Pred(Pred) {
     CodeMetrics::collectEphemeralValues(L, AC, EphValues);
   }
 
   /// Information about vectorization costs
   struct VectorizationFactor {
     unsigned Width; // Vector width with best cost
     unsigned Cost; // Cost of the loop with that width
   };
private:
   LoopVectorizationLegality *Legal;
   /// Vector target information.
   const TargetTransformInfo &TTI;
   /// Target Library Info.
   const TargetLibraryInfo *TLI;
   const Function *TheFunction;
   // Loop Vectorize Hint.
   const LoopVectorizeHints *Hints;
+
+  /// The SCEV predicate containing all the SCEV-related assumptions.
+  SCEVPredicateSet &Pred;
 };
 
 /// Utility class for getting and setting loop vectorizer hints in the form
 /// of loop metadata.
 /// This class keeps a number of loop annotations locally (as member variables)
 /// and can, upon request, write them back as metadata on the loop. It will
 /// initially scan the loop for existing metadata, and will update the local
 /// values based on information in the loop.
if (TC > 0u && TC < TinyTripCountVectorThreshold) {
       else {
         DEBUG(dbgs() << "\n");
         emitOptimizationRemarkAnalysis(
             F->getContext(), DEBUG_TYPE, *F, L->getStartLoc(),
             "vectorization is not beneficial and is not explicitly forced");
         return false;
       }
     }
+    SCEVPredicateSet Pred;
 
     // Check if it is legal to vectorize the loop.
-    LoopVectorizationLegality LVL(L, SE, DT, TLI, AA, F, TTI, LAA);
+    LoopVectorizationLegality LVL(L, SE, DT, TLI, AA, F, TTI, LAA, Pred);
     if (!LVL.canVectorize()) {
       DEBUG(dbgs() << "LV: Not vectorizing: Cannot prove legality.\n");
       emitMissedWarning(F, L, Hints);
       return false;
     }
 
     // Use the cost model.
-    LoopVectorizationCostModel CM(L, SE, LI, &LVL, *TTI, TLI, AC, F, &Hints);
+    LoopVectorizationCostModel CM(L, SE, LI, &LVL, *TTI, TLI, AC, F, &Hints,
+                                  Pred);
 
     // Check the function attributes to find out if this function should be
     // optimized for size.
     bool OptForSize = Hints.getForce() != LoopVectorizeHints::FK_Enabled &&
                       F->hasFnAttribute(Attribute::OptimizeForSize);
 
     // Compute the weighted frequency of this loop being executed and see if it
     // is less than 20% of the function entry baseline frequency. Note that we
if (VF.Width == 1) {
       }
       DEBUG(dbgs() << "LV: Trying to at least unroll the loops.\n");
 
       // Report the unrolling decision.
       emitOptimizationRemark(F->getContext(), DEBUG_TYPE, *F, L->getStartLoc(),
                              Twine("interleaved by " + Twine(IC) +
                                    " (vectorization not beneficial)"));
 
-      InnerLoopUnroller Unroller(L, SE, LI, DT, TLI, TTI, IC);
+      InnerLoopUnroller Unroller(L, SE, LI, DT, TLI, TTI, IC, Pred);
       Unroller.vectorize(&LVL);
     } else {
       // If we decided that it is *legal* to vectorize the loop then do it.
-      InnerLoopVectorizer LB(L, SE, LI, DT, TLI, TTI, VF.Width, IC);
+      InnerLoopVectorizer LB(L, SE, LI, DT, TLI, TTI, VF.Width, IC, Pred);
       LB.vectorize(&LVL);
       ++LoopsVectorized;
 
       // Add metadata to disable runtime unrolling scalar loop when there's no
       // runtime check about strides and memory. Because at this situation,
       // scalar loop is rarely used not worthy to be unrolled.
       if (!LB.IsSafetyChecksAdded())
         AddRuntimeUnrollDisableMetaData(L);
int LoopVectorizationLegality::isConsecutivePtr(Value *Ptr) {
   for (unsigned i = 0; i != NumOperands; ++i)
     if (i != InductionOperand &&
         !SE->isLoopInvariant(SE->getSCEV(Gep->getOperand(i)), TheLoop))
       return 0;
 
   // We can emit wide load/stores only if the last non-zero index is the
   // induction variable.
   const SCEV *Last = nullptr;
-  if (!Strides.count(Gep))
+  if (!Strides.count(Gep)) {
     Last = SE->getSCEV(Gep->getOperand(InductionOperand));
-  else {
+    Last = rewriteSCEVWithAssumptions(Last, TheLoop, SE, Pred);
+  } else {
     // Because of the multiplication by a stride we can have a s/zext cast.
     // We are going to replace this stride by 1 so the cast is safe to ignore.
     //
     //  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
     //  %0 = trunc i64 %indvars.iv to i32
     //  %mul = mul i32 %0, %Stride1
     //  %idxprom = zext i32 %mul to i64  << Safe cast.
     //  %arrayidx = getelementptr inbounds i32* %B, i64 %idxprom
     //
-    Last = replaceSymbolicStrideSCEV(SE, Strides,
-                                     Gep->getOperand(InductionOperand), Gep);
+    Last = rewriteSCEV(SE, Strides, Gep->getOperand(InductionOperand), Gep,
+                       TheLoop, Pred);
     if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(Last))
       Last =
           (C->getSCEVType() == scSignExtend || C->getSCEVType() == scZeroExtend)
               ? C->getOperand()
               : Last;
   }
+
+  SCEVPredicateSet P = Pred;
+  if (!dyn_cast<SCEVAddRecExpr>(Last)) {
+    // Attermpt to add new SCEV assumptions to Last in order to
+    // get an AddRecExpr.
+    OFAssumptionResult R = removeOverflowsWithAssumptions(Last, TheLoop, SE);
+    R.P.add(&Pred);
+
+    if (R.Ret && !R.P.isNever()) {
+      Last = R.Ret;
+      P = R.P;
+    }
+  }
+
   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Last)) {
     const SCEV *Step = AR->getStepRecurrence(*SE);
 
     // The memory is consecutive because the last index is consecutive
     // and all other indices are loop invariant.
-    if (Step->isOne())
+    if (Step->isOne()) {
+      Pred = P;
       return 1;
-    if (Step->isAllOnesValue())
+    }
+    if (Step->isAllOnesValue()) {
+      Pred = P;
       return -1;
     }
+  }
 
   return 0;
 }
 
 bool LoopVectorizationLegality::isUniform(Value *V) {
   return LAI->isUniform(V);
 }
 
void InnerLoopVectorizer::createEmptyLoop() {
   // Some loops have a single integer induction variable, while other loops
   // don't. One example is c++ iterators that often have multiple pointer
   // induction variables. In the code below we also support a case where we
   // don't have a single induction variable.
   OldInduction = Legal->getInduction();
   Type *IdxTy = Legal->getWidestInductionType();
 
   // Find the loop boundaries.
-  const SCEV *ExitCount = SE->getBackedgeTakenCount(OrigLoop);
+  const SCEV *ExitCount = SE->getGuardedBackedgeTakenCount(OrigLoop, Pred);
   assert(ExitCount != SE->getCouldNotCompute() && "Invalid loop count");
 
   // The exit count might have the type of i64 while the phi is i32. This can
   // happen if we have an induction variable that is sign extended before the
   // compare. The only way that we get a backedge taken count is that the
   // induction variable was signed and as such will not overflow. In such a case
   // truncation is legal.
   if (ExitCount->getType()->getPrimitiveSizeInBits() >
if (MemRuntimeCheck) {
     // for the "few elements case".
     ReplaceInstWithInst(
         VectorPH->getTerminator(),
         BranchInst::Create(MiddleBlock, NewVectorPH, MemRuntimeCheck));
 
     VectorPH = NewVectorPH;
   }
 
+  // Generate runtime checks for any SCEV assumptions that we've made.
+  Instruction *OFCheck;
+  std::tie(FirstCheckInst, OFCheck) =
+      Pred.generateGuardCond(VectorPH->getTerminator(), SE);
+  if (OFCheck) {
+    AddedSafetyChecks = true;
+    // Create a new block containing the scev check.
+    VectorPH->setName("vector.scevcheck");
+    NewVectorPH =
+        VectorPH->splitBasicBlock(VectorPH->getTerminator(), "vector.ph");
+
+    if (ParentLoop)
+      ParentLoop->addBasicBlockToLoop(NewVectorPH, *LI);
+    LoopBypassBlocks.push_back(VectorPH);
+
+    // Replace the branch into the scev check block with a conditional branch
+    // for the "few elements case".
+    ReplaceInstWithInst(VectorPH->getTerminator(),
+                        BranchInst::Create(MiddleBlock, NewVectorPH, OFCheck));
+
+    VectorPH = NewVectorPH;
+  }
+
   // We are going to resume the execution of the scalar loop.
   // Go over all of the induction variables that we found and fix the
   // PHIs that are left in the scalar version of the loop.
   // The starting values of PHI nodes depend on the counter of the last
   // iteration in the vectorized loop.
   // If we come from a bypass edge then we need to start from the original
   // start value.
 
bool LoopVectorizationLegality::canVectorize() {
   // Check if we can if-convert non-single-bb loops.
   unsigned NumBlocks = TheLoop->getNumBlocks();
   if (NumBlocks != 1 && !canVectorizeWithIfConvert()) {
     DEBUG(dbgs() << "LV: Can't if-convert the loop.\n");
     return false;
   }
 
   // ScalarEvolution needs to be able to find the exit count.
-  const SCEV *ExitCount = SE->getBackedgeTakenCount(TheLoop);
+  const SCEV *ExitCount = SE->getGuardedBackedgeTakenCount(TheLoop, Pred);
   if (ExitCount == SE->getCouldNotCompute()) {
-    emitAnalysis(VectorizationReport() <<
-                 "could not determine number of loop iterations");
+    emitAnalysis(VectorizationReport()
+                 << "could not determine number of loop iterations");
     DEBUG(dbgs() << "LV: SCEV could not compute the loop exit count.\n");
     return false;
   }
 
   // Check if we can vectorize the instructions and CFG in this loop.
   if (!canVectorizeInstrs()) {
     DEBUG(dbgs() << "LV: Can't vectorize the instructions or CFG\n");
     return false;
if (LAI->getNumRuntimePointerChecks() >
       VectorizerParams::RuntimeMemoryCheckThreshold) {
     emitAnalysis(VectorizationReport()
                  << LAI->getNumRuntimePointerChecks() << " exceeds limit of "
                  << VectorizerParams::RuntimeMemoryCheckThreshold
                  << " dependent memory operations checked at runtime");
     DEBUG(dbgs() << "LV: Too many memory checks needed.\n");
     return false;
   }
+
+  Pred.add(&*LAI->Pred);
+
+  if (Pred.isNever()) {
+    emitAnalysis(VectorizationReport()
+                 << "Too many SCEV assuptions need to be made and checked "
+                 << "at runtime");
+    DEBUG(dbgs() << "LV: Too many SCEV checks needed.\n");
+    return false;
+  }
+
   return true;
 }
 
 LoopVectorizationLegality::InductionKind
 LoopVectorizationLegality::isInductionVariable(PHINode *Phi,
                                                ConstantInt *&StepValue) {
   if (!isInductionPHI(Phi, SE, StepValue))
     return IK_NoInduction;
if (AccessList.empty())
     return;
 
   auto &DL = TheLoop->getHeader()->getModule()->getDataLayout();
   for (auto I : AccessList) {
     LoadInst *LI = dyn_cast<LoadInst>(I);
     StoreInst *SI = dyn_cast<StoreInst>(I);
 
     Value *Ptr = LI ? LI->getPointerOperand() : SI->getPointerOperand();
-    int Stride = isStridedPtr(SE, Ptr, TheLoop, Strides);
+    int Stride = isStridedPtr(SE, Ptr, TheLoop, Strides, Pred, false);
 
     // The factor of the corresponding interleave group.
     unsigned Factor = std::abs(Stride);
 
     // Ignore the access if the factor is too small or too large.
     if (Factor < 2 || Factor > MaxInterleaveGroupFactor)
       continue;
 

test/Transforms/LoopDistribute/distribute-with-overflows.ll

+; RUN: opt -mtriple=aarch64--linux-gnueabi -basicaa -loop-distribute -verify-loop-info -verify-dom-info -S \
+; RUN:   < %s | FileCheck %s
+
+; RUN: opt -basicaa -loop-distribute -loop-vectorize -force-vector-width=4 \
+; RUN:   -verify-loop-info -verify-dom-info -S < %s | \
+; RUN:   FileCheck --check-prefix=VECTORIZE %s
+
+; The memcheck version of basic.ll with overflows - the induction variables can
+; overflow.  We should distribute and vectorize the second part of this loop with
+; 5 memchecks (A+1 x {C, D, E} + C x {A, B})
+;
+;   for (i = 0; i < n; i++) {
+;     A[i + 1] = A[i] * B[i];
+; -------------------------------
+;     C[i] = D[i] * E[i];
+;   }
+
+@B = common global i32* null, align 8
+@A = common global i32* null, align 8
+@C = common global i32* null, align 8
+@D = common global i32* null, align 8
+@E = common global i32* null, align 8
+
+define void @f(i64 %n) {
+entry:
+  %a = load i32*, i32** @A, align 8
+  %b = load i32*, i32** @B, align 8
+  %c = load i32*, i32** @C, align 8
+  %d = load i32*, i32** @D, align 8
+  %e = load i32*, i32** @E, align 8
+  br label %for.body
+
+; We have two compares for each array overlap check which is a total of 10
+; compares.
+;
+; CHECK: for.body.lver.memcheck:
+
+; CHECK: icmp ugt i64 %{{[a-zA-Z0-9]+}}, 4294967295
+
+; CHECK:     %ldist.safe = or i1 %memcheck.conflict, %scev.check
+; CHECK:     br i1 %ldist.safe, label %for.body.ph.lver.orig, label %for.body.ph.ldist1
+
+
+; The non-distributed loop that the memchecks fall back on.
+
+; CHECK: for.body.ph.lver.orig:
+; CHECK:     br label %for.body.lver.orig
+; CHECK: for.body.lver.orig:
+; CHECK:    br i1 %exitcond.lver.orig, label %for.end, label %for.body.lver.orig
+
+; Verify the two distributed loops.
+
+; CHECK: for.body.ph.ldist1:
+; CHECK:     br label %for.body.ldist1
+; CHECK: for.body.ldist1:
+; CHECK:    %mulA.ldist1 = mul i32 %loadB.ldist1, %loadA.ldist1
+; CHECK:    br i1 %exitcond.ldist1, label %for.body.ph, label %for.body.ldist1
+
+; CHECK: for.body.ph:
+; CHECK:    br label %for.body
+; CHECK: for.body:
+; CHECK:    %mulC = mul i32 %loadD, %loadE
+; CHECK: for.end:
+
+
+; VECTORIZE: mul <4 x i32>
+
+for.body:                                         ; preds = %for.body, %entry
+  %ind = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %ind_ext = zext i32 %ind to i64
+
+  %arrayidxA = getelementptr inbounds i32, i32* %a, i64 %ind_ext
+  %loadA = load i32, i32* %arrayidxA, align 4
+
+  %arrayidxB = getelementptr inbounds i32, i32* %b, i64 %ind_ext
+  %loadB = load i32, i32* %arrayidxB, align 4
+
+  %mulA = mul i32 %loadB, %loadA
+
+  %add = add i32 %ind, 1
+  %add_ext = zext i32 %add to i64
+
+  %arrayidxA_plus_4 = getelementptr inbounds i32, i32* %a, i64 %add_ext
+  store i32 %mulA, i32* %arrayidxA_plus_4, align 4
+
+  %arrayidxD = getelementptr inbounds i32, i32* %d, i64 %ind_ext
+  %loadD = load i32, i32* %arrayidxD, align 4
+
+  %arrayidxE = getelementptr inbounds i32, i32* %e, i64 %ind_ext
+  %loadE = load i32, i32* %arrayidxE, align 4
+
+  %mulC = mul i32 %loadD, %loadE
+
+  %arrayidxC = getelementptr inbounds i32, i32* %c, i64 %ind_ext
+  store i32 %mulC, i32* %arrayidxC, align 4
+
+  %exitcond = icmp eq i64 %add_ext, %n
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body
+  ret void
+}

test/Transforms/LoopVectorize/safegep.ll

 ; RUN: opt -S -loop-vectorize -force-vector-width=4 -force-vector-interleave=1  < %s |  FileCheck %s
 target datalayout = "e-p:32:32:32-S128-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f16:16:16-f32:32:32-f64:32:64-f128:128:128-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32"
 
 
 ; We can vectorize this code because if the address computation would wrap then
 ; a load from 0 would take place which is undefined behaviour in address space 0
 ; according to LLVM IR semantics.
 
 ; PR16592
 
 ; CHECK-LABEL: @safe(
+; CHECK-LABEL-NOT: vector.overflowcheck
 ; CHECK: <4 x float>
 
+
 define void @safe(float* %A, float* %B, float %K) {
 entry:
   br label %"<bb 3>"
 
 "<bb 3>":
   %i_15 = phi i32 [ 0, %entry ], [ %i_19, %"<bb 3>" ]
   %pp3 = getelementptr float, float* %A, i32 %i_15
   %D.1396_10 = load float, float* %pp3, align 4

test/Transforms/LoopVectorize/scev-overflow-check.ll

+; RUN: opt -mtriple=aarch64--linux-gnueabi -loop-vectorize < %s -S | FileCheck %s
+
+; CHECK-LABEL: test0
+define void @test0(i32*  %A,
+                  i32*  %B,
+                  i32*  %C, i32 %N) {
+entry:
+  %cmp13 = icmp eq i32 %N, 0
+  br i1 %cmp13, label %for.end, label %for.body.preheader
+
+; If N is greater then 65535, this would loop forever.
+; CHECK: icmp ugt i32 %N, 65535
+
+for.body.preheader:
+  br label %for.body
+
+for.body:
+  %indvars.iv = phi i16 [ %indvars.next, %for.body ], [ 0, %for.body.preheader ]
+  %indvars.next = add i16 %indvars.iv, 1
+  %indvars.ext = zext i16 %indvars.iv to i32
+
+  %arrayidx = getelementptr inbounds i32, i32* %B, i32 %indvars.ext
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx3 = getelementptr inbounds i32, i32* %C, i32 %indvars.ext
+  %1 = load i32, i32* %arrayidx3, align 4
+
+  %mul4 = mul i32 %1, %0
+
+  %arrayidx7 = getelementptr inbounds i32, i32* %A, i32 %indvars.ext
+  store i32 %mul4, i32* %arrayidx7, align 4
+
+  %exitcond = icmp eq i32 %indvars.ext, %N
+  br i1 %exitcond, label %for.end.loopexit, label %for.body
+
+for.end.loopexit:
+  br label %for.end
+
+for.end:
+  ret void
+}
+
+; CHECK-LABEL: test1
+define void @test1(i32* %A,
+                   i32* %B,
+                   i32* %C, i32 %N, i32 %Offset) {
+entry:
+  %cmp13 = icmp eq i32 %N, 0
+  br i1 %cmp13, label %for.end, label %for.body.preheader
+
+; Because of the GEPs, we need check that Offset + N does not overflow.
+; CHECK: [[MUL0:%[a-zA-Z_0-9.]+]]  = call { i32, i1 } @llvm.smul.with.overflow.i32(i32 1, i32 %N)
+; CHECK: [[MUL1:%[a-zA-Z_0-9.]+]] = extractvalue { i32, i1 } [[MUL0]], 0
+; CHECK: call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 [[MUL1]], i32 %Offset)
+
+for.body.preheader:
+  br label %for.body
+
+for.body:
+  %indvars.iv = phi i16 [ %indvars.next, %for.body ], [ 0, %for.body.preheader ]
+  %indvars.next = add i16 %indvars.iv, 1
+
+  %indvars.ext = zext i16 %indvars.iv to i32
+  %indvars.access = add i32 %Offset, %indvars.ext
+
+  %arrayidx = getelementptr inbounds i32, i32* %B, i32 %indvars.access
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx3 = getelementptr inbounds i32, i32* %C, i32 %indvars.access
+  %1 = load i32, i32* %arrayidx3, align 4
+
+  %mul4 = mul i32 %1, %0
+
+  %arrayidx7 = getelementptr inbounds i32, i32* %A, i32 %indvars.access
+  store i32 %mul4, i32* %arrayidx7, align 4
+
+  %exitcond = icmp eq i32 %indvars.ext, %N
+  br i1 %exitcond, label %for.end.loopexit, label %for.body
+
+for.end.loopexit:
+  br label %for.end
+
+for.end:
+  ret void
+}
+
+; CHECK-LABEL: test2
+define void @test2(i32* %A,
+                   i32* %B,
+                   i32* %C, i32 %N, i32 %Offset) {
+entry:
+  %cmp13 = icmp eq i32 %N, 0
+  br i1 %cmp13, label %for.end, label %for.body.preheader
+
+; CHECK: icmp sgt i32 %N, 32767
+; CHECK: icmp slt i32 %N, -32768
+
+for.body.preheader:
+  br label %for.body
+
+for.body:
+  %indvars.iv = phi i16 [ %indvars.next, %for.body ], [ 0, %for.body.preheader ]
+  %indvars.next = add i16 %indvars.iv, 1
+
+  %indvars.ext = sext i16 %indvars.iv to i32
+  %indvars.access = add i32 %Offset, %indvars.ext
+
+  %arrayidx = getelementptr inbounds i32, i32* %B, i32 %indvars.access
+  %0 = load i32, i32* %arrayidx, align 4
+  %arrayidx3 = getelementptr inbounds i32, i32* %C, i32 %indvars.access
+  %1 = load i32, i32* %arrayidx3, align 4
+
+  %mul4 = add i32 %1, %0
+
+  %arrayidx7 = getelementptr inbounds i32, i32* %A, i32 %indvars.access
+  store i32 %mul4, i32* %arrayidx7, align 4
+
+  %exitcond = icmp eq i32 %indvars.ext, %N
+  br i1 %exitcond, label %for.end.loopexit, label %for.body
+
+for.end.loopexit:
+  br label %for.end
+
+for.end:
+  ret void
+}
+

test/Transforms/LoopVectorize/version-mem-access.ll

 ; CHECK-LABEL: test
 define void @test(i32*  %A, i64 %AStride,
                   i32*  %B, i32 %BStride,
                   i32*  %C, i64 %CStride, i32 %N) {
 entry:
   %cmp13 = icmp eq i32 %N, 0
   br i1 %cmp13, label %for.end, label %for.body.preheader
 
+; We don't need to check the symbolic stride for B, we can assume instead
+; that {0,+,BStride} will not overflow.
+
 ; CHECK-DAG: icmp ne i64 %AStride, 1
-; CHECK-DAG: icmp ne i32 %BStride, 1
 ; CHECK-DAG: icmp ne i64 %CStride, 1
 ; CHECK: or
-; CHECK: or
 ; CHECK: br
 
 ; CHECK: vector.body
 ; CHECK: load <2 x i32>
 
 for.body.preheader:
   br label %for.body
 

 for.end.loopexit:
   br label %for.end
 
 for.end:
   ret void
 }
 
 ; We used to crash on this function because we removed the fptosi cast when
-; replacing the symbolic stride '%conv'.
-; PR18480
+; replacing the symbolic stride '%conv' (PR18480). However, replacing the
+; symbolic stride is no longer required since we can do an overflow check.
 
 ; CHECK-LABEL: fn1
-; CHECK: load <2 x double>
+; CHECK: store <2 x double>
 
 define void @fn1(double* noalias %x, double* noalias %c, double %a) {
 entry:
   %conv = fptosi double %a to i32
   %cmp8 = icmp sgt i32 %conv, 0
   br i1 %cmp8, label %for.body.preheader, label %for.end
 
 for.body.preheader: