[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

613

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

990

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

1041

You should clear the cache here?

lib/Analysis/ScalarEvolution.cpp

8816

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

lib/Transforms/Vectorize/LoopVectorize.cpp

2242

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

613

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

527–528

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

187

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

243

No description?

244

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

271

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 ↗

(On Diff #29882)

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

115

Why are you using the llvm namespace here?

Shouldn't these functions be static?

120

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 ↗

(On Diff #29882)

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

lib/Analysis/ScalarEvolution.cpp

8057

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

244

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 ↗

(On Diff #29882)

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

294–295

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.

476

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

122

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.

134–141

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.

334–335

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

294–296

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

476

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

121–123

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

134–141

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.

334–335

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

294–296

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

121–123

I don't follow.

134–141

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.

[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

private:
   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);
 };
 
 /// \brief Drive the analysis of memory accesses in the loop
 ///
 /// This class is responsible for analyzing the memory accesses of a loop.  It
 /// collects the accesses and then its main helper the AccessAnalysis class
 /// finds and categorizes the dependences in buildDependenceSets.
 ///
 /// For memory dependences that can be analyzed at compile time, it determines
 /// whether the dependence is part of cycle inhibiting vectorization.  This work
 /// is delegated to the MemoryDepChecker class.
private:
   ScalarEvolution *SE;
   const DataLayout &DL;
   const TargetLibraryInfo *TLI;
   AliasAnalysis *AA;
   DominatorTree *DT;
   LoopInfo *LI;
 
   unsigned NumLoads;
   unsigned NumStores;
 
   unsigned MaxSafeDepDistBytes;
 
   /// \brief Cache the result of analyzeLoop.
   bool CanVecMem;
 
   /// \brief Indicator for storing to uniform addresses.
   /// If a loop has write to a loop invariant address then it should be true.
public:
   bool runOnFunction(Function &F) override;
 
   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.
-  const LoopAccessInfo &getInfo(Loop *L, const ValueToValueMap &Strides);
+  /// 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,
+                                bool UseAssumptions = false);
 
   void releaseMemory() override {
     // Invalidate the cache when the pass is freed.
     LoopAccessInfoMap.clear();
+    AssumeLoopAccessInfoMap.clear();
   }
 
   /// \brief Print the result of the analysis when invoked with -analyze.
   void print(raw_ostream &OS, const Module *M = nullptr) const override;
 
 private:
-  /// \brief The cache.
+  /// \brief The cache for answers computed without ussing the
+  /// AssumingScalarEvolution pass.
   DenseMap<Loop *, std::unique_ptr<LoopAccessInfo>> LoopAccessInfoMap;
-
+  /// \brief A separate cache used for answers computed using the
+  /// AsummingScalarEvolution pass.
+  DenseMap<Loop *, std::unique_ptr<LoopAccessInfo>> AssumeLoopAccessInfoMap;
   // The used analysis passes.
   ScalarEvolution *SE;
+  ScalarEvolution *ASE;
   const TargetLibraryInfo *TLI;
   AliasAnalysis *AA;
   DominatorTree *DT;
   LoopInfo *LI;
 };
 } // End llvm namespace
 
 #endif

include/llvm/Analysis/ScalarEvolution.h

public:
     /// SCEV and a loop.
     enum LoopDisposition {
       LoopVariant,    ///< The SCEV is loop-variant (unknown).
       LoopInvariant,  ///< The SCEV is loop-invariant.
       LoopComputable  ///< The SCEV varies predictably with the loop.
     };
 
     /// BlockDisposition - An enum describing the relationship between a
     /// SCEV and a basic block.
     enum BlockDisposition {
       DoesNotDominateBlock,  ///< The SCEV does not dominate the block.
       DominatesBlock,        ///< The SCEV dominates the block.
       ProperlyDominatesBlock ///< The SCEV properly dominates the block.
     };
 
     /// Convenient NoWrapFlags manipulation that hides enum casts and is
     /// visible in the ScalarEvolution name space.
private:
     /// TLI - The target library information for the target we are targeting.
     ///
     TargetLibraryInfo *TLI;
 
     /// DT - The dominator tree.
     ///
     DominatorTree *DT;
 
     /// CouldNotCompute - This SCEV is used to represent unknown trip
     /// counts and things.
     SCEVCouldNotCompute CouldNotCompute;
 
     /// ValueExprMapType - The typedef for ValueExprMap.
     ///
     typedef DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *> >
       ValueExprMapType;
 
     /// ValueExprMap - This is a cache of the values we have analyzed so far.
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;
 
       /*implicit*/ ExitLimit(const SCEV *E) : Exact(E), Max(E) {}
 
       ExitLimit(const SCEV *E, const SCEV *M) : Exact(E), Max(M) {}
 
       /// 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);
private:
     //
     template<typename ExtendOpTy>
     bool proveNoWrapByVaryingStart(const SCEV *Start, const SCEV *Step,
                                    const Loop *L);
 
   public:
     static char ID; // Pass identification, replacement for typeid
     ScalarEvolution();
+    ScalarEvolution(bool AddToRegistry, char &ID);
 
     LLVMContext &getContext() const { return F->getContext(); }
 
     /// isSCEVable - Test if values of the given type are analyzable within
     /// the SCEV framework. This primarily includes integer types, and it
     /// can optionally include pointer types if the ScalarEvolution class
     /// has access to target-specific information.
     bool isSCEVable(Type *Ty) const;
 
     /// getTypeSizeInBits - Return the size in bits of the specified type,
     /// for which isSCEVable must return true.
     uint64_t getTypeSizeInBits(Type *Ty) const;
 
     /// getEffectiveSCEVType - Return a type with the same bitwidth as
     /// the given type and which represents how SCEV will treat the given
     /// type, for which isSCEVable must return true. For pointer types,
     /// this is the pointer-sized integer type.
     Type *getEffectiveSCEVType(Type *Ty) const;
 
     /// getSCEV - Return a SCEV expression for the full generality of the
     /// specified expression.
-    const SCEV *getSCEV(Value *V);
+    virtual 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);
+
+    virtual const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty);
+    virtual 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);
public:
     /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop
     /// has an analyzable loop-invariant backedge-taken count.
     bool hasLoopInvariantBackedgeTakenCount(const Loop *L);
 
     /// forgetLoop - This method should be called by the client when it has
     /// changed a loop in a way that may effect ScalarEvolution's ability to
     /// compute a trip count, or if the loop is deleted.  This call is
     /// potentially expensive for large loop bodies.
-    void forgetLoop(const Loop *L);
+    virtual void forgetLoop(const Loop *L);
 
     /// forgetValue - This method should be called by the client when it has
     /// changed a value in a way that may effect its value, or which may
     /// disconnect it from a def-use chain linking it to a loop.
     void forgetValue(Value *V);
 
     /// \brief Called when the client has changed the disposition of values in
     /// this loop.
private:
     FoldingSet<SCEV> UniqueSCEVs;
     BumpPtrAllocator SCEVAllocator;
 
     /// 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;
   };
+
+  /// AssumingScalarEvolution - a version of ScalarEvolution that will
+  /// make and track assumptions. The rationale behind this is that most
+  /// users of ScalarEvolution need a chrec returned as a result in order
+  /// to perform some other action.
+  ///
+  /// The pass provides an interface to generate run-time checks for the
+  /// assumptions that were made.
+  ///
+  /// We will lazily make the assumptions as getSCEV(), getBackedgeCount(), etc
+  /// are used.
+  ///
+  /// So far We can make the following assumptions to return a chrec where
+  /// otherwise we would not:
+  ///   - if A is a chrec, and we need to return sext/zext(A) we will
+  ///     add a nsw/nuw assumption for A. This allows us to fold the
+  ///     extend operation an return a chrec instead. We expect the runtime
+  ///     check will evaluate to 'true' in most cases.
+  class AssumingScalarEvolution : public ScalarEvolution {
+  private:
+    const Loop *AnalyzedLoop;
+    /// Use the normal Scalar Evolution analysis for any querries of
+    /// values outside the loop. This limits the recomputing we have to
+    /// do for each loop.
+    ScalarEvolution *SE;
+  public:
+    AssumingScalarEvolution();
+    static char ID; // Pass identification, replacement for typeid
+
+  private:
+    /// Assumption tracking structures
+
+    /// OverflowAssumption - An assumption that has been made by SCEV
+    /// regarding the possibility of overflow of an expression.
+    struct OverflowAssumption {
+      const SCEV *Expression;
+      SCEV::NoWrapFlags AddedFlags;
+      OverflowAssumption() : Expression(nullptr),
+                             AddedFlags(SCEV::FlagAnyWrap) {}
+    };
+
+    typedef DenseMap<const SCEV*, struct OverflowAssumption> AssumptionMapTy;
+    DenseMap<const Loop*, AssumptionMapTy> LoopAssumptions;
+
+    AssumptionMapTy::iterator getLoopAssumptionBegin(const Loop *L) {
+      AssumptionMapTy &Map = LoopAssumptions.FindAndConstruct(L).second;
+      return Map.begin();
+    }
+    AssumptionMapTy::iterator getLoopAssumptionEnd(const Loop *L) {
+      AssumptionMapTy &Map = LoopAssumptions.FindAndConstruct(L).second;
+      return Map.end();
+    }
+
+  public:
+    void setAnalyzedLoop(const Loop *L) {AnalyzedLoop = L;}
+
+    /// Override the virtual methods from the ScalarEvolution analysis.
+    void getAnalysisUsage(AnalysisUsage &AU) const override;
+    /// Override the methods for producing extending expressions.
+    /// This allows us to add overflow assumptions whenever SCEV can't
+    /// prove NSW/NUW.
+    const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty) override;
+    const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty) override;
+
+    void releaseMemory() override;
+    void forgetLoop(const Loop *L) override;
+    const SCEV *getSCEV(Value *V) override;
+    bool runOnFunction(Function &F) override;
+
+    /// Add an assumption that the expression S has the wrapping behaviour
+    /// implied by Flags. All added assumptions need to be checked
+    /// at runtime, otherwise the results of this analysis are invalid.
+    void addOverflowAssumption(const SCEV *S, SCEV::NoWrapFlags Flags);
+
+    /// Method for generating run-time checks. The results of the
+    /// analysis are invalid if these run-time checks are not added.
+    std::pair<Instruction *, Instruction *>
+      addRuntimeOverflowChecks(Instruction *Loc);
+
+    /// Checks that the added assumptions can actually be checked
+    /// at runtime (and returns true we can generate code for these
+    /// checks).
+    bool canPerformOverflowChecks();
+
+    /// Clears the assumption tracking structures.
+    void forgetLoopAssumptions(const Loop *L);
+  };
 }
 
 #endif

include/llvm/InitializePasses.h

 /// initializeCodeGen - Initialize all passes linked into the CodeGen library.
 void initializeCodeGen(PassRegistry&);
 
 /// initializeCodeGen - Initialize all passes linked into the CodeGen library.
 void initializeTarget(PassRegistry&);
 
 void initializeAAEvalPass(PassRegistry&);
 void initializeAddDiscriminatorsPass(PassRegistry&);
+void initializeAssumingScalarEvolutionPass(PassRegistry&);
 void initializeADCEPass(PassRegistry&);
 void initializeBDCEPass(PassRegistry&);
 void initializeAliasAnalysisAnalysisGroup(PassRegistry&);
 void initializeAliasAnalysisCounterPass(PassRegistry&);
 void initializeAliasDebuggerPass(PassRegistry&);
 void initializeAliasSetPrinterPass(PassRegistry&);
 void initializeAlwaysInlinerPass(PassRegistry&);
 void initializeArgPromotionPass(PassRegistry&);

lib/Analysis/Analysis.cpp

 
 /// initializeAnalysis - Initialize all passes linked into the Analysis library.
 void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeAliasAnalysisAnalysisGroup(Registry);
   initializeAliasAnalysisCounterPass(Registry);
   initializeAAEvalPass(Registry);
   initializeAliasDebuggerPass(Registry);
   initializeAliasSetPrinterPass(Registry);
+  initializeAssumingScalarEvolutionPass(Registry);
   initializeNoAAPass(Registry);
   initializeBasicAliasAnalysisPass(Registry);
   initializeBlockFrequencyInfoPass(Registry);
   initializeBranchProbabilityInfoPass(Registry);
   initializeCostModelAnalysisPass(Registry);
   initializeCFGViewerPass(Registry);
   initializeCFGPrinterPass(Registry);
   initializeCFGOnlyViewerPass(Registry);

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);
 }
 
 void LoopAccessInfo::RuntimePointerCheck::insert(
     ScalarEvolution *SE, Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId,
     unsigned ASId, const ValueToValueMap &Strides) {
   // Get the stride replaced scev.
   const SCEV *Sc = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc);
   assert(AR && "Invalid addrec expression");
   const SCEV *Ex = SE->getBackedgeTakenCount(Lp);
   const SCEV *ScEnd = AR->evaluateAtIteration(Ex, *SE);
   Pointers.push_back(Ptr);
   Starts.push_back(AR->getStart());
   Ends.push_back(ScEnd);
   IsWritePtr.push_back(WritePtr);
   DependencySetId.push_back(DepSetId);
   AliasSetId.push_back(ASId);
 }
 
 bool LoopAccessInfo::RuntimePointerCheck::needsChecking(
     unsigned I, unsigned J, const SmallVectorImpl<int> *PtrPartition) const {
   // No need to check if two readonly pointers intersect.
   if (!IsWritePtr[I] && !IsWritePtr[J])
     return false;
 
   // Only need to check pointers between two different dependency sets.
   if (DependencySetId[I] == DependencySetId[J])
     return false;
 
   // Only need to check pointers in the same alias set.
   if (AliasSetId[I] != AliasSetId[J])
     return false;
 
   // If PtrPartition is set omit checks between pointers of the same partition.
   // Partition number -1 means that the pointer is used in multiple partitions.
   // In this case we can't omit the check.
   if (PtrPartition && (*PtrPartition)[I] != -1 &&
for (auto A : AS) {
         ++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)) {
         // 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;
void LoopAccessInfo::print(raw_ostream &OS, unsigned Depth) const {
   OS << "\n";
 
   OS.indent(Depth) << "Store to invariant address was "
                    << (StoreToLoopInvariantAddress ? "" : "not ")
                    << "found in loop.\n";
 }
 
 const LoopAccessInfo &
-LoopAccessAnalysis::getInfo(Loop *L, const ValueToValueMap &Strides) {
-  auto &LAI = LoopAccessInfoMap[L];
+LoopAccessAnalysis::getInfo(Loop *L, const ValueToValueMap &Strides,
+                            bool UseAssumptions) {
+  DenseMap<Loop *, std::unique_ptr<LoopAccessInfo>> &Map =
+      UseAssumptions ? LoopAccessInfoMap : AssumeLoopAccessInfoMap;
+
+  auto &LAI = Map[L];
+
+  // FIXME: Swapping the Scalar Evolution analysis isn't nice,
+  // but it allows us to only teach some of the users
+  // of LoopAccessAnalysis about the AssumingScalarEvolution pass.
+  // At some point if all the users know about the
+  // AssumingScalarEvolution pass, we can remove this.
+
+  // Swap the normal Scalar Evolution analysis with the assuming one
+  // if the user has requested to use assumptions.
+  if (UseAssumptions) std::swap(SE, ASE);
 
 #ifndef NDEBUG
   assert((!LAI || LAI->NumSymbolicStrides == Strides.size()) &&
          "Symbolic strides changed for loop");
 #endif
 
   if (!LAI) {
     const DataLayout &DL = L->getHeader()->getModule()->getDataLayout();
     LAI = llvm::make_unique<LoopAccessInfo>(L, SE, DL, TLI, AA, DT, LI,
                                             Strides);
 #ifndef NDEBUG
     LAI->NumSymbolicStrides = Strides.size();
 #endif
   }
+  if (UseAssumptions) std::swap(SE, ASE);
+
   return *LAI.get();
 }
 
 void LoopAccessAnalysis::print(raw_ostream &OS, const Module *M) const {
   LoopAccessAnalysis &LAA = *const_cast<LoopAccessAnalysis *>(this);
 
   ValueToValueMap NoSymbolicStrides;
 
   for (Loop *TopLevelLoop : *LI)
     for (Loop *L : depth_first(TopLevelLoop)) {
       OS.indent(2) << L->getHeader()->getName() << ":\n";
       auto &LAI = LAA.getInfo(L, NoSymbolicStrides);
       LAI.print(OS, 4);
     }
 }
 
 bool LoopAccessAnalysis::runOnFunction(Function &F) {
   SE = &getAnalysis<ScalarEvolution>();
+  ASE = &getAnalysis<AssumingScalarEvolution>();
   auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
   TLI = TLIP ? &TLIP->getTLI() : nullptr;
   AA = &getAnalysis<AliasAnalysis>();
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 
   return false;
 }
 
 void LoopAccessAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
     AU.addRequired<ScalarEvolution>();
+    AU.addRequired<AssumingScalarEvolution>();
     AU.addRequired<AliasAnalysis>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
 
     AU.setPreservesAll();
 }
 
 char LoopAccessAnalysis::ID = 0;
 static const char laa_name[] = "Loop Access Analysis";
 #define LAA_NAME "loop-accesses"
 
 INITIALIZE_PASS_BEGIN(LoopAccessAnalysis, LAA_NAME, laa_name, false, true)
 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
+INITIALIZE_PASS_DEPENDENCY(AssumingScalarEvolution)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_END(LoopAccessAnalysis, LAA_NAME, laa_name, false, true)
 
 namespace llvm {
   Pass *createLAAPass() {
     return new LoopAccessAnalysis();
   }
 }

lib/Analysis/ScalarEvolution.cpp

 #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/Analysis/ScalarEvolutionExpander.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"
 #include <algorithm>
 using namespace llvm;
 

 
 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 vectorize if the number of added "
+                                 "overflow checks would be greater than this "
+                                  "value."));
+
+
 // 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)

 }
 
 ScalarEvolution::SCEVCallbackVH::SCEVCallbackVH(Value *V, ScalarEvolution *se)
   : CallbackVH(V), SE(se) {}
 
 //===----------------------------------------------------------------------===//
 //                   ScalarEvolution Class Implementation
 //===----------------------------------------------------------------------===//
-
-ScalarEvolution::ScalarEvolution()
+ScalarEvolution::ScalarEvolution(bool AddToRegistry, char &ID)
     : FunctionPass(ID), WalkingBEDominatingConds(false), ValuesAtScopes(64),
       LoopDispositions(64), BlockDispositions(64), FirstUnknown(nullptr) {
+  if (AddToRegistry) {
     initializeScalarEvolutionPass(*PassRegistry::getPassRegistry());
   }
+}
+
+ScalarEvolution::ScalarEvolution() : ScalarEvolution(true, ID) {}
 
 bool ScalarEvolution::runOnFunction(Function &F) {
   this->F = &F;
   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   return false;
if (OldI->second != NewI->second &&
              << "' changed from '" << OldI->second
              << "' to '" << NewI->second << "'!\n";
       std::abort();
     }
   }
 
   // TODO: Verify more things.
 }
+
+char AssumingScalarEvolution::ID = 0;
+
+INITIALIZE_PASS_BEGIN(AssumingScalarEvolution, "assuming-scalar-evolution",
+                "Assuming Scalar Evolution Analysis", false, true)
+INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
+INITIALIZE_PASS_END(AssumingScalarEvolution, "assuming-scalar-evolution",
+                "Assuming Scalar Evolution Analysis", false, true)
+
+AssumingScalarEvolution::AssumingScalarEvolution() :
+  ScalarEvolution(false, ID), SE(nullptr) {
+  initializeAssumingScalarEvolutionPass(*PassRegistry::getPassRegistry());
+}
+
+void AssumingScalarEvolution::getAnalysisUsage(AnalysisUsage &AU) const{
+  ScalarEvolution::getAnalysisUsage(AU);
+  AU.addRequired<ScalarEvolution>();
+}
+void AssumingScalarEvolution::addOverflowAssumption(const SCEV *S,
+                                            SCEV::NoWrapFlags Flags) {
+  // We should only be adding overflow assumptions for AddRecExpr.
+  const SCEVAddRecExpr *Expr = static_cast<const SCEVAddRecExpr *>(S);
+
+  SCEVAddRecExpr *RE = const_cast<SCEVAddRecExpr*>(Expr);
+  RE->setNoWrapFlags(Flags);
+
+  const Loop *L = Expr->getLoop();
+  AssumptionMapTy &Map = LoopAssumptions.FindAndConstruct(L).second;
+
+  // FIXME: assumptions can become redundant when stronger assumptions are
+  // added. We should try and reduce the number of assumptions once we have
+  // finished gathering them.
+  auto II = Map.find(S);
+  if (II == Map.end()) {
+    struct OverflowAssumption OA;
+    OA.Expression = S;
+    OA.AddedFlags = Flags;
+    Map[OA.Expression] = OA;
+    return;
+  }
+
+  struct OverflowAssumption &Existing = II->second;
+  Existing.AddedFlags = setFlags(Flags, Existing.AddedFlags);
+}
+
+const SCEV *
+AssumingScalarEvolution::getZeroExtendExpr(const SCEV *OP, Type *T) {
+
+  const SCEV *BaseResult = ScalarEvolution::getZeroExtendExpr(OP, T);
+  if (dyn_cast<const SCEVAddRecExpr>(BaseResult))
+    return BaseResult;
+
+  // We only know how to add assumptions for affine
+  // expressions.
+  const SCEVAddRecExpr *AR = dyn_cast<const SCEVAddRecExpr>(OP);
+  if(!AR) return BaseResult;
+  if (!AR->isAffine()) return BaseResult;
+  if (!(AR->getLoop() == AnalyzedLoop)) return BaseResult;
+
+  addOverflowAssumption(AR, SCEV::FlagNUW);
+
+  const Loop *L = AR->getLoop();
+  const SCEV *Step = AR->getStepRecurrence(*this);
+
+  return getAddRecExpr(
+      getExtendAddRecStart<SCEVZeroExtendExpr>(AR, T, this),
+      getZeroExtendExpr(Step, T), L, AR->getNoWrapFlags());
+}
+
+const SCEV *
+AssumingScalarEvolution::getSignExtendExpr(const SCEV *OP, Type *T) {
+
+  const SCEV *BaseResult = ScalarEvolution::getSignExtendExpr(OP, T);
+  if (dyn_cast<const SCEVAddRecExpr>(BaseResult))
+    return BaseResult;
+
+  // We only know how to add assumptions for affine
+  // expressions.
+  const SCEVAddRecExpr *AR = dyn_cast<const SCEVAddRecExpr>(OP);
+  if(!AR) return BaseResult;
+  if (!AR->isAffine()) return BaseResult;
+  if (!(AR->getLoop() == AnalyzedLoop)) return BaseResult;
+
+  addOverflowAssumption(AR, SCEV::FlagNSW);
+
+  const Loop *L = AR->getLoop();
+  const SCEV *Step = AR->getStepRecurrence(*this);
+
+  return getAddRecExpr(
+      getExtendAddRecStart<SCEVSignExtendExpr>(AR, T, this),
+      getSignExtendExpr(Step, T), L, AR->getNoWrapFlags());
+}
+
+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;
+
+  const SCEV *ExitCount = SE->getBackedgeTakenCount(AR->getLoop());
+
+  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;
+}
+
+std::pair<Instruction *, Instruction *>
+AssumingScalarEvolution::addRuntimeOverflowChecks(Instruction *Loc) {
+  Instruction *tnullptr = nullptr;
+
+  if (getLoopAssumptionBegin(AnalyzedLoop) ==
+      getLoopAssumptionEnd(AnalyzedLoop))
+    return std::pair<Instruction *, Instruction *>(tnullptr, tnullptr);
+
+  IRBuilder<> OFBuilder(Loc);
+  Instruction *FirstInst = nullptr;
+  Module *M = Loc->getParent()->getParent()->getParent();
+  const DataLayout &DL = M->getDataLayout();
+  Value *OverflowRuntimeCheck = nullptr;
+  SCEVExpander Exp(*this, DL, "start");
+
+  for (auto II = getLoopAssumptionBegin(AnalyzedLoop),
+            EE = getLoopAssumptionEnd(AnalyzedLoop);
+       II != EE; ++II) {
+    struct OverflowAssumption &OA = II->second;
+
+    const SCEVAddRecExpr *AR = static_cast<const SCEVAddRecExpr*>(OA.Expression);
+
+    assert(AR->isAffine() &&
+      "We don't know how to check non-affine expressions for overflow");
+
+    if (OA.AddedFlags & SCEV::FlagNUW) {
+      // Add a check for NUW
+      Value *Overflow = generateOverflowCheck(AR, Loc, false, this, &DL, Exp);
+
+      if (!OverflowRuntimeCheck)
+        OverflowRuntimeCheck = Overflow;
+      else
+        OverflowRuntimeCheck = OFBuilder.CreateOr(OverflowRuntimeCheck,
+                                                  Overflow);
+    }
+    if (OA.AddedFlags & SCEV::FlagNSW) {
+      // Add a check for NSW
+      Value *Overflow = generateOverflowCheck(AR, Loc, true, this, &DL, Exp);
+
+      if (!OverflowRuntimeCheck)
+        OverflowRuntimeCheck = Overflow;
+      else
+        OverflowRuntimeCheck = OFBuilder.CreateOr(OverflowRuntimeCheck,
+                                                  Overflow);
+    }
+  }
+
+  if (!OverflowRuntimeCheck)
+    return std::make_pair(nullptr, nullptr);
+  Instruction *Check = BinaryOperator::CreateOr(OverflowRuntimeCheck,
+                                          ConstantInt::getFalse(M->getContext()));
+  OFBuilder.Insert(Check, "overflow.check");
+
+  FirstInst = getFirstInst(FirstInst, Check, Loc);
+  return std::make_pair(FirstInst, Check);
+}
+
+bool AssumingScalarEvolution::canPerformOverflowChecks() {
+  unsigned NumChecks = 0;
+  for (auto II = getLoopAssumptionBegin(AnalyzedLoop),
+            EE = getLoopAssumptionEnd(AnalyzedLoop); II != EE; ++II) {
+    NumChecks++;
+    struct OverflowAssumption &OA = II->second;
+    DEBUG(dbgs() << "ASCEV: Processing overflow assumption "
+                 << *OA.Expression << "\n");
+    if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(OA.Expression)) {
+      if (AR->isAffine()) {
+        // We know how to check affine expressions.
+        // {u, + v} executed l times will not overflow as long as v*l does not
+        // overflow and u + v * l does not overflow.
+        continue;
+      }
+    }
+    DEBUG(dbgs() << "ASCEV: Unable to check " << *OA.Expression << "\n");
+    return false;
+  }
+  // FIXME: Some of these checks can be redundant.  We should remove them here.
+  // FIXME: The number of overflow checks is not a good metric. A lot of
+  // checks are expected to share code and will be CSE'ed away.
+  // Furthermore, instcombine is expected to simplify these checks further.
+  if (NumChecks > OverflowCheckThreshold) {
+    DEBUG(dbgs() << "ASCEV: Too many overflow checks needed.\n");
+    return false;
+  }
+  return true;
+}
+
+void AssumingScalarEvolution::forgetLoopAssumptions(const Loop *L) {
+  auto It = LoopAssumptions.find(L);
+  if (It == LoopAssumptions.end()) return;
+  It->second.clear();
+}
+
+void AssumingScalarEvolution::forgetLoop(const Loop *L) {
+  ScalarEvolution::forgetLoop(L);
+  SE->forgetLoop(L);
+  forgetLoopAssumptions(L);
+}
+
+void AssumingScalarEvolution::releaseMemory() {
+  ScalarEvolution::releaseMemory();
+  LoopAssumptions.clear();
+}
+
+const SCEV *AssumingScalarEvolution::getSCEV(Value *V) {
+  Instruction *Inst = dyn_cast<Instruction>(V);
+  if (!Inst)
+    return ScalarEvolution::getSCEV(V);
+  // If this value is not produced in the analyzed loop use
+  // the normal ScalarEvolution.
+  if (!AnalyzedLoop->contains(Inst))
+    return SE->getSCEV(Inst);
+
+  return ScalarEvolution::getSCEV(V);
+}
+
+bool AssumingScalarEvolution::runOnFunction(Function &F) {
+  SE = &getAnalysis<ScalarEvolution>();
+  return ScalarEvolution::runOnFunction(F);
+}

lib/Transforms/Vectorize/LoopVectorize.cpp

 ///   instructions.
 /// InnerLoopVectorizer does not perform any vectorization-legality
 /// checks, and relies on the caller to check for the different legality
 /// 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,
+  InnerLoopVectorizer(Loop *OrigLoop, AssumingScalarEvolution *SE, LoopInfo *LI,
                       DominatorTree *DT, const TargetLibraryInfo *TLI,
                       const TargetTransformInfo *TTI, unsigned VecWidth,
                       unsigned UnrollFactor)
       : 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) {}
 
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'.
private:
 
     /// Map storage. We use std::map and not DenseMap because insertions to a
     /// dense map invalidates its iterators.
     std::map<Value *, VectorParts> MapStorage;
   };
 
   /// The original loop.
   Loop *OrigLoop;
-  /// Scev analysis to use.
-  ScalarEvolution *SE;
+  /// Scev analysis to use (with assumptions).
+  AssumingScalarEvolution *SE;
   /// Loop Info.
   LoopInfo *LI;
   /// Dominator Tree.
   DominatorTree *DT;
   /// Alias Analysis.
   AliasAnalysis *AA;
   /// Target Library Info.
   const TargetLibraryInfo *TLI;
protected:
   LoopVectorizationLegality *Legal;
 
   // Record whether runtime check is added.
   bool AddedSafetyChecks;
 };
 
 class InnerLoopUnroller : public InnerLoopVectorizer {
 public:
-  InnerLoopUnroller(Loop *OrigLoop, ScalarEvolution *SE, LoopInfo *LI,
+  InnerLoopUnroller(Loop *OrigLoop, AssumingScalarEvolution *SE, LoopInfo *LI,
                     DominatorTree *DT, const TargetLibraryInfo *TLI,
                     const TargetTransformInfo *TTI, unsigned UnrollFactor)
       : InnerLoopVectorizer(OrigLoop, SE, LI, DT, TLI, TTI, 1, UnrollFactor) {}
 
 private:
   void scalarizeInstruction(Instruction *Instr,
                             bool IfPredicateStore = false) override;
   void vectorizeMemoryInstruction(Instruction *Instr) override;

 /// * Scalars checks - The code in canVectorizeInstrs and canVectorizeMemory
 /// checks for a number of different conditions, such as the availability of a
 /// single induction variable, that all types are supported and vectorize-able,
 /// 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,
+  LoopVectorizationLegality(Loop *L, AssumingScalarEvolution *SE, DominatorTree *DT,
                             TargetLibraryInfo *TLI, AliasAnalysis *AA,
                             Function *F, const TargetTransformInfo *TTI,
                             LoopAccessAnalysis *LAA)
       : NumPredStores(0), TheLoop(L), SE(SE), TLI(TLI), TheFunction(F),
         TTI(TTI), DT(DT), LAA(LAA), LAI(nullptr), Induction(nullptr),
         WidestIndTy(nullptr), HasFunNoNaNAttr(false) {}
 
   /// This enum represents the kinds of inductions that we support.
void emitAnalysis(const LoopAccessReport &Message) {
     LoopAccessReport::emitAnalysis(Message, TheFunction, TheLoop, LV_NAME);
   }
 
   unsigned NumPredStores;
 
   /// The loop that we evaluate.
   Loop *TheLoop;
   /// Scev analysis.
-  ScalarEvolution *SE;
+  AssumingScalarEvolution *SE;
   /// Target Library Info.
   TargetLibraryInfo *TLI;
   /// Parent function
   Function *TheFunction;
   /// Target Transform Info
   const TargetTransformInfo *TTI;
   /// Dominator Tree.
   DominatorTree *DT;

 /// 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,
+  LoopVectorizationCostModel(Loop *L, AssumingScalarEvolution *SE, LoopInfo *LI,
                              LoopVectorizationLegality *Legal,
                              const TargetTransformInfo &TTI,
                              const TargetLibraryInfo *TLI, AssumptionCache *AC,
                              const Function *F, const LoopVectorizeHints *Hints)
       : TheLoop(L), SE(SE), LI(LI), Legal(Legal), TTI(TTI), TLI(TLI),
         TheFunction(F), Hints(Hints) {
     CodeMetrics::collectEphemeralValues(L, AC, EphValues);
   }
private:
   }
 
   /// Values used only by @llvm.assume calls.
   SmallPtrSet<const Value *, 32> EphValues;
 
   /// The loop that we evaluate.
   Loop *TheLoop;
   /// Scev analysis.
-  ScalarEvolution *SE;
+  AssumingScalarEvolution *SE;
   /// Loop Info analysis.
   LoopInfo *LI;
   /// Vectorization legality.
   LoopVectorizationLegality *Legal;
   /// Vector target information.
   const TargetTransformInfo &TTI;
   /// Target Library Info.
   const TargetLibraryInfo *TLI;
struct LoopVectorize : public FunctionPass {
 
   explicit LoopVectorize(bool NoUnrolling = false, bool AlwaysVectorize = true)
     : FunctionPass(ID),
       DisableUnrolling(NoUnrolling),
       AlwaysVectorize(AlwaysVectorize) {
     initializeLoopVectorizePass(*PassRegistry::getPassRegistry());
   }
 
-  ScalarEvolution *SE;
+  AssumingScalarEvolution *SE;
   LoopInfo *LI;
   TargetTransformInfo *TTI;
   DominatorTree *DT;
   BlockFrequencyInfo *BFI;
   TargetLibraryInfo *TLI;
   AliasAnalysis *AA;
   AssumptionCache *AC;
   LoopAccessAnalysis *LAA;
   bool DisableUnrolling;
   bool AlwaysVectorize;
 
   BlockFrequency ColdEntryFreq;
 
   bool runOnFunction(Function &F) override {
-    SE = &getAnalysis<ScalarEvolution>();
+    SE = &getAnalysis<AssumingScalarEvolution>();
     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     BFI = &getAnalysis<BlockFrequencyInfo>();
     auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
     TLI = TLIP ? &TLIP->getTLI() : nullptr;
     AA = &getAnalysis<AliasAnalysis>();
     AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
bool runOnFunction(Function &F) override {
 
     for (Loop *L : *LI)
       addInnerLoop(*L, Worklist);
 
     LoopsAnalyzed += Worklist.size();
 
     // Now walk the identified inner loops.
     bool Changed = false;
-    while (!Worklist.empty())
-      Changed |= processLoop(Worklist.pop_back_val());
+    while (!Worklist.empty()) {
+      Loop *L = Worklist.pop_back_val();
+      SE->setAnalyzedLoop(L);
+      Changed |= processLoop(L);
+    }
 
     // Process each loop nest in the function.
     return Changed;
   }
 
   static void AddRuntimeUnrollDisableMetaData(Loop *L) {
     SmallVector<Metadata *, 4> MDs;
     // Reserve first location for self reference to the LoopID metadata node.
#endif /* NDEBUG */
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequiredID(LoopSimplifyID);
     AU.addRequiredID(LCSSAID);
     AU.addRequired<BlockFrequencyInfo>();
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<LoopInfoWrapperPass>();
     AU.addRequired<ScalarEvolution>();
+    AU.addRequired<AssumingScalarEvolution>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
     AU.addRequired<AliasAnalysis>();
     AU.addRequired<LoopAccessAnalysis>();
     AU.addPreserved<LoopInfoWrapperPass>();
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<AliasAnalysis>();
   }
 
if (MemRuntimeCheck) {
     Instruction *OldTerm = LastBypassBlock->getTerminator();
     BranchInst::Create(MiddleBlock, CheckBlock, Cmp, OldTerm);
     OldTerm->eraseFromParent();
 
     Cmp = MemRuntimeCheck;
     LastBypassBlock = CheckBlock;
   }
 
+  // Overflow check
+  Instruction *OFCheck;
+  Instruction *FirstOFCheckInst;
+  std::tie(FirstOFCheckInst, OFCheck) =
+      SE->addRuntimeOverflowChecks(LastBypassBlock->getTerminator());
+  if (OFCheck) {
+    AddedSafetyChecks = true;
+    // Create a new block containing the stride check.
+    BasicBlock *CheckBlock =
+        LastBypassBlock->splitBasicBlock(FirstOFCheckInst, "vector.overflowcheck");
+    if (ParentLoop)
+      ParentLoop->addBasicBlockToLoop(CheckBlock, *LI);
+    LoopBypassBlocks.push_back(CheckBlock);
+
+    // Replace the branch into the memory check block with a conditional branch
+    // for the "few elements case".
+    Instruction *OldTerm = LastBypassBlock->getTerminator();
+    BranchInst::Create(MiddleBlock, CheckBlock, Cmp, OldTerm);
+    OldTerm->eraseFromParent();
+
+    Cmp = OFCheck;
+    LastBypassBlock = CheckBlock;
+  }
+
   LastBypassBlock->getTerminator()->eraseFromParent();
   BranchInst::Create(MiddleBlock, VectorPH, Cmp,
                      LastBypassBlock);
 
   // 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
bool LoopVectorizationLegality::canVectorize() {
   if (!canVectorizeMemory()) {
     DEBUG(dbgs() << "LV: Can't vectorize due to memory conflicts\n");
     return false;
   }
 
   // Collect all of the variables that remain uniform after vectorization.
   collectLoopUniforms();
 
+  /// Vectorizing some loops requires assuming that some operations do no
+  /// overflow. These assumptions need to be checked at run-time.
+  /// Returns true if we know how to generate code to check the required
+  /// assumptions.
+  if (!SE->canPerformOverflowChecks()) {
+    DEBUG(dbgs() << "LV: Can't vectorize - unable to add "
+                 << "overflow checks\n");
+    return false;
+  }
+
   DEBUG(dbgs() << "LV: We can vectorize this loop" <<
         (LAI->getRuntimePointerCheck()->Need ? " (with a runtime bound check)" :
          "")
         <<"!\n");
 
   // Okay! We can vectorize. At this point we don't have any other mem analysis
   // which may limit our maximum vectorization factor, so just return true with
   // no restrictions.
while (!Worklist.empty()) {
     Uniforms.insert(I);
 
     // Insert all operands.
     Worklist.insert(Worklist.end(), I->op_begin(), I->op_end());
   }
 }
 
 bool LoopVectorizationLegality::canVectorizeMemory() {
-  LAI = &LAA->getInfo(TheLoop, Strides);
+  LAI = &LAA->getInfo(TheLoop, Strides, true);
   auto &OptionalReport = LAI->getReport();
   if (OptionalReport)
     emitAnalysis(VectorizationReport(*OptionalReport));
   if (!LAI->canVectorizeMemory())
     return false;
 
   if (LAI->hasStoreToLoopInvariantAddress()) {
     emitAnalysis(

 char LoopVectorize::ID = 0;
 static const char lv_name[] = "Loop Vectorization";
 INITIALIZE_PASS_BEGIN(LoopVectorize, LV_NAME, lv_name, false, false)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfo)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
+INITIALIZE_PASS_DEPENDENCY(AssumingScalarEvolution)
 INITIALIZE_PASS_DEPENDENCY(LCSSA)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 INITIALIZE_PASS_DEPENDENCY(LoopAccessAnalysis)
 INITIALIZE_PASS_END(LoopVectorize, LV_NAME, lv_name, false, false)
 
 namespace llvm {
   Pass *createLoopVectorizePass(bool NoUnrolling, bool AlwaysVectorize) {

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: