[SCEV][LV] Introduce SCEV Predicates and use them to re-implement stride versioning

[sbaranga]

Summary

SCEV Predicates represent conditions that typically cannot be derived from
static analysis, but can be used to reduce SCEV expressions to forms which are
usable for different optimizers.

ScalarEvolution now has the rewriteUsingPredicate method which can simplify a
SCEV expression using a SCEVPredicateSet. The normal workflow of a pass using
SCEVPredicates would be to hold a SCEVPredicateSet and every time assumptions
need to be made a new SCEV Predicate would be created and added to the set.
Each time after calling getSCEV, the user will call the rewriteUsingPredicate
method.

We add two types of predicates
SCEVPredicateSet - implements a set of predicates
SCEVEqualPredicate - tests for equality between two SCEV expressions

We use the SCEVEqualPredicate to re-implement stride versioning. Every time we
version a stride, we will add a SCEVEqualPredicate to the context.
Instead of adding specific stride checks, LoopVectorize now adds a more
generic SCEV check.

We only need to add support for this in the LoopVectorizer since this is the
only pass that will do stride versioning.

The only effect of this change is that now the number of versioned strides
will be limited to 16 (which is should be better than having no limit).

[hfinkel]

include/llvm/Analysis/ScalarEvolution.h

244

Remove commented-out code.

lib/Analysis/ScalarEvolution.cpp

9157

Can this take a threshold override, or similar, as a parameter to override SCEVCheckThreshold? We had specifically decided that loops decorated with #pragma clang vectorize(enable), which asks for vectorization but does not assert safety, would generate as many checks as necessary to enable vectorization (or be bound by some very large limit). For this case, we'll need to override the limit (or, at least, have a much larger limit). Generically, I'm skeptical of embedding the limit in SCEV at all; I think that the caller should always provide an appropriate limit for whatever happens to be its use case.

[anemet]

Hi Silviu,

Thanks for splitting this out, this is a much easier read now!

Adam

include/llvm/Analysis/LoopAccessAnalysis.h

295

I think I've commented on this too: this should be plural or have set in the name.

545–576

I think I've already asked this before: why is the thing with unique_ptr needed?

include/llvm/Analysis/ScalarEvolution.h

176

I think the enum tags are uppercase. Also this should probably be inside the class.

190–196

Do these really ever happen aside for reaching the check threshold?

I think that we should just have an API to query the number of checks.

1186–1189

Stale comment. I also think that the function name should be plural.

lib/Analysis/ScalarEvolution.cpp

115–119

I don't think that this should be central threshold. It should be up to the client transformation to decide if the benefit of the transformation outweighs the overhead of the necessary checks.

8902–8909

Hmm, I think we're duplicating this now into the third file. Any better idea?

8911

Should probably be a class since not all members are public.

Also it needs a comment.

This may be a silly question but why we need to override all these members?

9090

OF for overflow? ;)

lib/Transforms/Vectorize/LoopVectorize.cpp

318–321

Overflow again.

[sbaranga]

Hi, Adam, Hal,

Thanks for the reviews! I've replied inline. I should have a new version shortly.

Silviu

include/llvm/Analysis/LoopAccessAnalysis.h

545–576

I'm sure I had some reason at some point of making it a unique_ptr, but I can't remember. I think it should be possible to remove the unique_ptr part.

include/llvm/Analysis/ScalarEvolution.h

190–196

isAlwaysFalse would currently be true only when reaching the threshold.
Having an API to return the number of checks (or maybe something that estimates the cost of the checks?), would be more clear.

lib/Analysis/ScalarEvolution.cpp

115–119

Ok, I'll remove this.

8911

I think because SCEVVisitor is a template that uses the visit* methods without defining them, users must define all the methods (or get a compilation error). Not really nice.

I'll make the changes (add a comment and convert to a class).

9157

That makes sense to me. There is currently the override in SCEV, but from your argument it looks like it should be passed in from the user.

Would that put a complexity bound on our rewriting algorithms / estimates for how expensive using these predicates can be? So far I've worked under the assumption that we would have a limited number of predicates.

[anemet]

lib/Analysis/ScalarEvolution.cpp

8911

I think because SCEVVisitor is a template that uses the visit* methods without defining them, users must define all the methods (or get a compilation error). Not really nice.

Can this be derived from SCEVParameterRewriter since we only support the equality predicate right now? Then we can extend it later as we add the other predicates.

[mzolotukhin]

Hi Silviu,

Thanks for doing this, I think this could be a nice improvement. As for now, several questions: does it work on any new cases, compared to the original StrideVersioning implementation? Do you plan to add any other types of predicates in future?

Also, some comments inline.

Thanks,
Michael

include/llvm/Analysis/LoopAccessAnalysis.h

574–575

Where is this used?

include/llvm/Analysis/ScalarEvolution.h

207

Please add some description for this class.

239–240

The names SCEVPredicate and SCEVPredicateSet are a bit confusing: usually, one doesn't assume that a SomethingSet is derived from Something. Would it make sense to rename them to something like SCEVPredicateBase/SCEVUnionPredicate (not insisting on these particular names)?

241–242

Should it be called Invalid or something like this then?

lib/Analysis/LoopAccessAnalysis.cpp

109–115

Instead of storing VOne and One in a separate variables, I think we can use ScalarEvolution::getConstant(Type *Ty, uint64_t V, bool isSigned) here.

lib/Analysis/ScalarEvolution.cpp

8911

users must define all the methods (or get a compilation error). Not really nice.

No, you don't have to override all of them, you only need to define the ones you want to change. For generic case, you could override visitInstruction method. As an example, you could look at class UnrolledInstAnalyzer in lib/Transforms/Scalar/LoopUnrollPass.cpp.

9158

I think it should be >= since we haven't added the new predicate yet.

[sbaranga]

In D12905#252980, @mzolotukhin wrote:

Hi Silviu,

Thanks for doing this, I think this could be a nice improvement. As for now, several questions: does it work on any new cases, compared to the original StrideVersioning implementation? Do you plan to add any other types of predicates in future?

Also, some comments inline.

Thanks,
Michael

Hi Michael,

This won't work on any new cases of StrideVersioning, it should be equivalent to the existing implementation.
The main motivation is to introduce the SCEV predicates. I plan to add predicates for overflow tests (see http://reviews.llvm.org/D10161 for the overall direction).

I've found that range checking predicates could also be useful in some cases (the use case I have for this would be canonicalization of "a <= b" into "a < b + 1" in SCEV), but I would have to think more if this is actually needed.

Thanks,
Silviu

include/llvm/Analysis/LoopAccessAnalysis.h

574–575

This is an artefact of rebasing and should be removed.

include/llvm/Analysis/ScalarEvolution.h

239–240

I'm not opposed to changing the names. SCEVPredicateBase/SCEVUnionPredicate could work.

241–242

"Invalid" would be better, yes.

[hfinkel]

lib/Analysis/ScalarEvolution.cpp

9157

Would that put a complexity bound on our rewriting algorithms / estimates for how expensive using these predicates can be? So far I've worked under the assumption that we would have a limited number of predicates.

I'm not too concerned about this. In cases where we want to override the "generally reasonable" limit with a large one, at least currently, this is always in response to a direct request from the user (due to a pragma or similar), and so we get to assume that the user knows what he or she is doing.

[mzolotukhin]

Hi Silviu,

Thanks, I see the general direction now. I found several spots that need some clean-up (you could find them inline), but apart from that I have a question - currently PredicateSet only works as OR of several checks. Do we need (or might we need in future) sets of predicates, combined with AND? I tend to think that we'll need both. I suspect that supporting them both might add non-trivial amount of work to this patch, so we can keep it for later, but I think that as a default option we need AND, not OR. What do you think?

Best regards,
Michael

include/llvm/Analysis/ScalarEvolution.h

245

What is IdPreds and how is it different from Preds?

254–255

This probably should be private/protected.

260–261

Does it return first and last instruction in the generated check? Could we document it?

lib/Analysis/ScalarEvolution.cpp

9030–9031

Maybe just
return E0 == E1;
?

9045

The predicate is called Equal, should we generate ICmpEQ for consistency here?

9061

Please avoid computing IdPreds.size() on every iteration. Even better, we could use range loop here.

9069

Another candidate for a range loop.

9070–9071

What does OA stand for? Maybe get rid of this var at all?

Actually, this entire function could probably be replaced with std::all_of.

9088

Could we just return std::make_pair(nullptr, nullptr) as we do below?

9101–9103

Why do we need to do or with False?

9117

Range loop?

9138–9148

Good candidates for std::all_of/std::any_of.

[sbaranga]

This update addresses part of the review comments:

Removed the isAlwaysFalse interface from the predicates and
replaced it with a getComplexity() method. The users will now
use this method to determine if it is acceptable to create
a new predicate.

Moved the SCEV limit from ScalarEvolution to the users
(LoopVectorize in this case).

Other small changes (removed the unique_ptr use, use range loops,
etc).

[sbaranga]

Hi Michael,

In D12905#254015, @mzolotukhin wrote:

Hi Silviu,

Thanks, I see the general direction now. I found several spots that need some clean-up (you could find them inline), but apart from that I have a question - currently PredicateSet only works as OR of several checks. Do we need (or might we need in future) sets of predicates, combined with AND? I tend to think that we'll need both. I suspect that supporting them both might add non-trivial amount of work to this patch, so we can keep it for later, but I think that as a default option we need AND, not OR. What do you think?

The current implementation of PredicateSet is actually an AND. The checks do (or (not p)), for p in the set. So we're effectively getting the condition that would be used to invalidate the predicates. I don't see a clear case for 'OR' at this moment but I guess it might be required at some point.

Thanks,
Silviu

include/llvm/Analysis/ScalarEvolution.h

245

Right now it's not different, but I was thinking that in the future it could contain different types of predicates.

260–261

It does, yes! This should be consistent with the interface used by the loop vectorizer / loop access analysis to add runtime checks. I'll add documentation for this in the next version.

lib/Analysis/ScalarEvolution.cpp

8911

I think we have a different case here, as we would like to visit SCEV expressions. I think that the LoopUnrollPass examples visits instructions?

9045

The convention that I used so far was to generate the negative test (ICmpNE). I think the loop vectorizer / loop access analysis were doing the same thing for their checks? Would keeping it like this be a problem?

9141

Makes sense. Thanks!

[mzolotukhin]

Hi Silviu,

Thanks for the changes, the code looks much better now! Please find some remarks inline.

Michael

include/llvm/Analysis/ScalarEvolution.h

245

I still don't understand the purpose of having IdPreds. Why can't Preds contain different types of predicates?

[mzolotukhin]

include/llvm/Analysis/ScalarEvolution.h

199–201

It might return nullptr in certain cases - please document them.

206–207

s/assume#/assume/

By the way, why is the assumption (that RHS is SCEVUnknown) needed?

252–253

Why do we need it as a public member?

lib/Analysis/LoopAccessAnalysis.cpp

429

Nitpick: here the predicate set is called Preds, in other functions (e.g. RuntimePointerChecking::insert) it's called Pred.

lib/Analysis/ScalarEvolution.cpp

8911

Yes, you're right, I misread the code.

I think it would make sense to factor out common ('default' implementation) part into a separate class. It will also remove some code duplication from SCEVApplyRewriter and SCEVParameterRewriter. That should be a separate NFC patch, but I think we need to do it before landing this one.

9045

I think it's fine, but at least we should explicitly state somewhere that we're doing it this way. It'll prevent future readers of this code from being caught by surprise.

9078

Why are this and 9224 lines different?

9080–9081

From previous iteration: Why do we need to do OR with False?

[sbaranga]

Thanks, Michael! Answers inline.

• Silviu

include/llvm/Analysis/ScalarEvolution.h

245

I'm basically using IdPreds for storage. It's not ideal. Would there be some other way of providing storage for different types of predicates while avoiding heap allocation?

Preds would hold a list of references and would be the thing that the algorithms use.

252–253

I needed to get access to Preds from the rewriter. Maybe having some interface for this would be better.

lib/Analysis/ScalarEvolution.cpp

8911

Makes sense. I've create another review for this change: http://reviews.llvm.org/D13242

9078

One of these should be removed, yes.

9080–9081

I wrote this code some time ago but if I remember correctly this was the same reason why LoopAccessInfo::addRuntimeChecks does an AND with True:

"We have to do this trickery because the IRBuilder might fold the check to a constant expression in which case there is no Instruction anchored in a the block.".

[sbaranga]

include/llvm/Analysis/ScalarEvolution.h

206–207

The assumption is not technically required. But if we wanted to have something general here we would have to change the visiting algorithm to test if this predicate matches on every sub-expression. This is technically easy to do, but we don't need it for the current uses (and we would just spend more time doing these checks).

[sbaranga]

Renamed SCEVPredicateSet to SCEVUnionPredicate.
Documented the behaviour of the check-generating functions.
We now should be using "Preds" instead of "Pred" everywhere.

Re-based this change on top of http://reviews.llvm.org/D13242
which simplified the implementation of the predicate rewriter.

Also included other small cleanups and ran the patch through clang-format.

[mzolotukhin]

Hi Silviu,

Thanks for the changes! Please find my comments inline.

Michael

include/llvm/Analysis/ScalarEvolution.h

206–207

Makes sense. But then we'll need to clarify, that another assumption is that the unknown part is always LHS (while RHS is always a constant?). Maybe it's worth enforcing these assumptions with some assertions too.

245

Hmm.. I don't think it'll work..

So, IdPreds is a vector of objects, and Preds is a vector of pointers to those objects, right? Are you going to keep different types of predicates in Preds? If so, where the actual objects will be stored? Will you create a separate IdPreds-like array for any new type of objects that can be stored in Preds (because you can't store objects of a type other than SCEVEqualPredicate in IdPreds, right?) ?

I think we'll have to heap allocate the objects to make the scheme versatile. For an example of how similar problem is solved, you could take a look at ScalarEvolution::getConstant and UniqueSCEVs member of class ScalarEvolution.

lib/Analysis/ScalarEvolution.cpp

8911

Thanks! FWIW, I like that patch, but I'd like to leave it up to Andy or Sanjoy for a final approval.

[anemet]

include/llvm/Analysis/LoopAccessAnalysis.h

466–469

I am not sure I understand this interface (it is certainly under-documented and so is getInfo):

What is the point of passing strides and SCEV complexity? Don't we know already that for each symbolic stride in Strides we will need exactly one check? I understand that this will change when we generate predicates for other SCEV assumption, but:

Wouldn't it be better to pass a PredicateSet here initialized with the strides?

[sanjoy]

Reviewed the SCEV bits. I don't know enough about the other bits to comment on those.

include/llvm/Analysis/ScalarEvolution.h

189

Minor: I'd put newlines between method declarations.

196

Also minor, but why not just call it implies?

202

Please document Loc, and pass in things that cannot be nullptr, like SE or DL as references.

213

The restriction that LHS is a SCEVUnknown seems somewhat arbitrary; but if you want to keep it, please change the type of E0 to be SCEVUnknown.

Also, rename E0 and E1 to LHS and RHS to sync with the documentation, or change the documentation to refer to these as E0 or E1.

225

Same comment here -- if your invariant is that E0 is a SCEVUnknown, then make that obvious in the type.

239

I haven't read the whole patch yet, but I think the doc should state if a SCEVUnionPredicate represents a logical and or a logical or (or sometimes one and sometimes the other) of the predicates it contains.

244

I agree with @mzolotukhin -- this won't work once you have different types of predicates. You'll need a "host" to contain the allocations, perhaps using a BumpPtrAllocator or something similar.

263

Why do you need to return a pair of instructions? Why not just return a Value * computing the result of the predicate? This will also obviate the need to create a "fake or" in the implementation, and you'll just be able to return what IRBuilder gave you.

lib/Analysis/ScalarEvolution.cpp

8951

Use const auto *.

8956

Why not just return (Op->E0 == E0 && Op->E1 == E1) || (Op->E0 == E1 && Op->E1 == E0)?

8972

Why not just return Builder.CreateICmpNE(...)?

8995

As I've mentioned in the declaration of generateGuardCond, I don't see why you need to return a range of instructions. I'd rather have this return a Value *, and do away with getFirstInst and the fake or instruction.

9044

I think this should be std::all_of to be consistent with the interpretation of SCEVUnionPredicate in generateCheck -- to prove (X|Y)->Z you need to prove (X->Z)&&(Y->Z).

9054

Nit: here and elsewhere, prefer using const auto * or auto * when the type is obvious from the RHS.

9055

[Optional] Why not std::any_of?

9058

As mentioned earlier, this allocation scheme is not quite right.

[sbaranga]

Thanks for the reviews! Replies inline.

include/llvm/Analysis/LoopAccessAnalysis.h

466–469

My understanding is that the strides in the Strides map can be replaced with 1 if needed. However it is not guaranteed that we will need to replace these strides with 1.

I was thinking that maybe it would be a good idea to have some VersioningParameters struct to hold all the parameters that tell us if we can use versioning? So at the moment it would be the strides map and the SCEV complexity. Do you think that would make sense?

include/llvm/Analysis/ScalarEvolution.h

244

Ok, this makes sense. I'll do the changes.

245

I agree, the current scheme is not ideal.

Using a ScalarEvolution-like allocation scheme seems reasonable to me for everything except SCEVUnionPredicate.
But we don't to allocate that anyway so it should be fine.

263

It is mostly for consistency. This is what some of the other versioning checks return - addRuntimeChecks in LoopAccessInfo and InnerLoopVectorizer::addStrideCheck (removed by this patch).

lib/Analysis/ScalarEvolution.cpp

8956

In fact if we know that LHS and RHS are different (one is a SCEVUnknown and the other a SCEVConstant) we can simplify that expression.

9044

The union predicate function is an "and", so I think this makes the current implementation correct?

[sbaranga]

Updated the SCEV predicate allocation scheme, so we now use the same allocator as the SCEVs
(and have the same scheme as the one used for SCEVs by ScalarEvolution).

Made explicit the assumption that LHS is a SCEVUnknown and RHS is a SCEVConstant in
the SCEVEqualPredicate.

This update should address all the other review comments (unless I've accidentally missed
something).

[anemet]

include/llvm/Analysis/LoopAccessAnalysis.h

466–469

My understanding is that the strides in the Strides map can be replaced with 1 if needed. However it is not guaranteed that we will need to replace these strides with 1.

Fair enough.

I was thinking that maybe it would be a good idea to have some VersioningParameters struct to hold all the parameters that tell us if we can use versioning? So at the moment it would be the strides map and the SCEV complexity. Do you think that would make sense?

Just to be clear, I am not looking for stylistic improvements here but trying to make sense of the semantics. If I understand correctly SCEVComplexity specifies the cost of the checks that we're allowed to accumulate to make LAA complete its analysis.

I don't understand why that is an incoming parameter. It seems to me that a better formulation would be to have LAA do its thing, accumulate whatever checks it needs and then make that cost value part of the LAI state. Then a client pass can query that and decide whether it's willing to pay that cost in order to get an analyzable loop or not.

To put it another way, it seem to me that with the current interface you can have this scenario:

1. One client specifies a low complexity value. There is no LAI for the loop so we compute it but fail because we need more checks than allowed. We *cache* the result.
2. Next client wants to specify a higher value but can't because LAI is already cached plus actually as the code is currently written this will lead to an assert.

So how do you envision this scenario to work?

[sbaranga]

include/llvm/Analysis/LoopAccessAnalysis.h

466–469

Yes, your analysis is correct and that scenario is a problem.

I chose the current solution because it was equivalent with the existing implementation. I agree with your assessment.

Some possible solutions:

a) no bounds in LAA on predicate sizes. This can have a negative impact on compile time.
b) LAA has its own logic for computing the limit, and we can make sure the limit is high enough to cover all the users.
c) we have some initial default bounds, but clients can request an increase by throwing away the cached LAI result and computing a new one (with an increased threshold). Recomputing the LAI would not be ideal.

I like variant b).
b) is orthogonal to c), but we theoretically wouldn't need c) right now.

[anemet]

include/llvm/Analysis/LoopAccessAnalysis.h

466–469

Do you know about any compile-time or algorithmic complexity issues?

I am not sure if we want to approximate compile time with the cost of the checks.

If we know some worse than linear algorithms here, I much rather control it locally rather hoping that the number of checks would catch it (especially once we start having checks for different type of predicates like non-wrapping, etc.)

[sbaranga]

include/llvm/Analysis/LoopAccessAnalysis.h

466–469

I don't think there are any problems that we can't fix. The predicates themselves have linear complexity for the methods, but the problem is the places where we're using them (using them in some algorithm that was already linear is not great).

The problem with the current code is that it was written for a low number of predicates. There are some places where we do linear traversals of the set (for example in SCEVPredicateRewriter::visitUnknown). We can fix this by having a map from SCEVs to predicates (in the case of the SCEVEqualPredicate this would map the SCEVUnknown to the predicate).

I'll make the required changes.

[sbaranga]

Add a getExpr() method to the SCEVPredicate interface. This will return the
expression on which the predicate is applied. The return value of this call
is used by SCEVUnionPredicate to effciently lookup the adequate predicate
during expression rewriting. Now the algorithm should be able to scale with
the number of predicates.

Removed the limit to the number of predicates in LAA. The loop vectorizer will
check at the end of the legality phase to see if the number of predicates is
acceptable.

Fixed several instances where a Loop * parameter was passed but not used.

[sanjoy]

Overall, I think this is looking much better. I have few minor comments inline. The only design issue (according to me) is that (I've said this inline) we're creating a fake instruction solely to satisfy an internal interface. I think that's a code smell, but I can live with it if that's hard to fix and others are okay with having it.

include/llvm/Analysis/ScalarEvolution.h

196

This is optional to fix, but I'd prefer renaming this to getKind, since getType in LLVM has the connotation of returning a Type *.

215

Please document Loc.

218

Newline here?

269

Here, and in getLHS, please start the sentence with uppercase.

287

Why not DenseMap?

314

I'd prefer returning an ArrayRef<const SCEVPredicate *>, and returning an empty ArrayRef if there are no predicates for Expr.

1211

Please construct this in the move constructor.

lib/Analysis/LoopAccessAnalysis.cpp

115

There is now a ScalarEvolution::getOne, can you use that here?

lib/Analysis/ScalarEvolution.cpp

8906

Use auto *I here.

8906

Isn't V always an instruction?

8917

Don't you need to add the type of the predicate to ID?

8942

Use const auto * because the type is obvious from the RHS.

8960

Use three slashes.

9019

If the IRBuilder returned a constant Check, why do you need to generate the check? I'd either

• change this to assert(isa<Instruction>(Check)), and fix the cases where the assert fails to return true from isAlwaysTrue (i.e. if the IRBuilder can prove the check is redundant, SCEV should be able to as well)
• change the interface to allow returning something that says "always true" / "always false" in addition to returning a pair of instructions

I think creating a completely redundant instruction to satisfy internal interfaces is a code smell, and we should try to avoid it if reasonable.

9044

In that case, shouldn't you have

AllCheck = CheckBuilder.CreateAnd(AllCheck, CheckResult);

in SCEVUnionPredicate::generateCheck? Or are you checking something different there?

9053

Shouldn't this be CreateAnd?

9053

As mentioned earlier, IIUC this should be a CreateAnd.

9096

Why not just SCEVToPreds[Key].push_back(N);?

[anemet]

There is a huge number of inline comments from earlier revisions that are still popping up in the new version. This makes it pretty hard to read the patch. Can you please check if marking those "done" would make them disappear?

include/llvm/Analysis/LoopAccessAnalysis.h

294

Please expand this comment to explain how they are used for dep-checking.

336–340

Explain the Preds parameter

545–546

Same here, please expand comment to explain how they are used.

596–606

Comment the Preds parameter.

607–610

Here too.

637–638

Didn't you want to get rid of MaxSCEVPredicates?

lib/Analysis/LoopAccessAnalysis.cpp

1790–1791

Ah, MaxSCEVPredicates is unused.

lib/Transforms/Vectorize/LoopVectorize.cpp

402–404

Comment missing

511–512

Here too please expand the comment to explain what these assumptions are used for.

781–782

Here too.

1350

Missing comment.

1691–1700

Any reason this whole logic can't be pushed into LVLegality?

[sbaranga]

lib/Analysis/ScalarEvolution.cpp

8902–8909

We remove this from the loop vectorizer so we end up with the same number of copies. There's still some code duplication.

9019

Yes, I think you're right. I would go with the first option.

9044

See the comment bellow.

9053

The generated code checks for the negated condtion. So we basically end up with
(or (not predicate1), (not predicate2), ...) which is the same as
(not (and prediacte1, predicate2, ..)

We do this because the current users already use this interface.
This also avoids the need to explicitly create negations (we just create the negated check for each predicate).

I think this at least needs a comment. Do you have a strong preference about this?

[sbaranga]

In D12905#262511, @anemet wrote:

There is a huge number of inline comments from earlier revisions that are still popping up in the new version. This makes it pretty hard to read the patch. Can you please check if marking those "done" would make them disappear?

I've marked the comments as done, but phabricator is still showing them. Do you think it would be better to start a new review?

Thanks,
Silviu

[anemet]

I've marked the comments as done, but phabricator is still showing them. Do you think it would be better to start a new review?

Wow, silly Phab. Yeah I think, unless other reviewers object, we should move this to a new review. Thanks!

[sbaranga]

Ok. Moving the review to http://reviews.llvm.org/D13595.

Thanks,
Silviu

include/llvm/Analysis/LoopAccessAnalysis.h

 
 namespace llvm {
 
 class Value;
 class DataLayout;
 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();
     Checks.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
     /// pointer, with index \p Index in RtCheck.

 /// is delegated to the MemoryDepChecker class.
 ///
 /// For memory dependences that cannot be determined at compile time, it
 /// generates run-time checks to prove independence.  This is done by
 /// AccessAnalysis::canCheckPtrAtRT and the checks are maintained by the
 /// RuntimePointerCheck class.
 class LoopAccessInfo {
 public:
   LoopAccessInfo(Loop *L, ScalarEvolution *SE, const DataLayout &DL,
                  const TargetLibraryInfo *TLI, AliasAnalysis *AA,
                  DominatorTree *DT, LoopInfo *LI,
                  const ValueToValueMap &Strides);
 
   /// Return true we can analyze the memory accesses in the loop and there are
   /// no memory dependence cycles.
   bool canVectorizeMemory() const { return CanVecMem; }
 
   const RuntimePointerChecking *getRuntimePointerChecking() const {
     return &PtrRtChecking;
   }
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();
 
   void emitAnalysis(LoopAccessReport &Message);
 
   /// We need to check that all of the pointers in this list are disjoint
   /// at runtime.
   RuntimePointerChecking PtrRtChecking;
 
   /// \brief the Memory Dependence Checker which can determine the
   /// loop-independent and loop-carried dependences between memory accesses.
   MemoryDepChecker DepChecker;
 
   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;
 
   /// \brief Indicator for storing to uniform addresses.
   /// If a loop has write to a loop invariant address then it should be true.
   bool StoreToLoopInvariantAddress;
 
   /// \brief The diagnostics report generated for the analysis.  E.g. why we
   /// couldn't analyze the loop.
   Optional<LoopAccessReport> Report;
 };
 
 Value *stripIntegerCast(Value *V);
 
 ///\brief Return the SCEV corresponding to a pointer with the symbolic stride
 ///replaced with constant one.
 ///
 /// 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,
+                                      SCEVPredicateSet &Pred, const Loop *L,
                                       Value *Ptr, Value *OrigPtr = nullptr);
 
 /// \brief Check the stride of the pointer and ensure that it does not wrap in
 /// the address space.
 int isStridedPtr(ScalarEvolution *SE, Value *Ptr, const Loop *Lp,
-                 const ValueToValueMap &StridesMap);
+                 const ValueToValueMap &StridesMap, SCEVPredicateSet &Pred);
 
 /// \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.
   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.
   void print(raw_ostream &OS, const Module *M = nullptr) const override;
 

include/llvm/Analysis/ScalarEvolution.h

namespace llvm {
   class TargetLibraryInfo;
   class LLVMContext;
   class Loop;
   class LoopInfo;
   class Operator;
   class SCEVUnknown;
   class SCEVAddRecExpr;
   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 { pSet, pEqual };
+
+  //===--------------------------------------------------------------------===//
+  /// 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);
+    virtual ~SCEVPredicate() {}
+    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 isAlwaysTrue() 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 isAlwaysFalse() 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;
+  };
+
+  class SCEVEqualPredicate : public SCEVPredicate {
+    // We assume that E0 == E1
+    const SCEV *E0;
+    const SCEV *E1;
+
+  public:
+    SCEVEqualPredicate()
+        : SCEVPredicate(pEqual), E0(nullptr), E1(nullptr) {}
+    SCEVEqualPredicate(const SCEV *E0, const SCEV *E1);
+
+    /// Implementation of the SCEVPredicate interface
+    bool contains(const SCEVPredicate *N) const override;
+    void print(raw_ostream &OS, unsigned Depth) const override;
+    bool isAlwaysTrue() const override;
+    bool isAlwaysFalse() const override;
+
+    const SCEV *getLHS() { return E0; }
+    const SCEV *getRHS() { return E1; }
+
+    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() == pEqual;
+    }
+  };
+
+  //===--------------------------------------------------------------------===//
+  /// SCEVPredicateSet - This class represents a composition of other
+  /// SCEV predicates, and is the class that most clients will interact with.
+  ///
+  class SCEVPredicateSet : public SCEVPredicate {
+  protected:
+    /// Flag used to track if this predicate set is invalid.
+    bool Never;
+    /// Storage for different predicates that make up this Predicate Set.
+    //SmallVector<SCEVAddRecOverflowPredicate, 16> AddRecOverflows;
+    SmallVector<SCEVEqualPredicate, 16> IdPreds;
+
+  public:
+    SCEVPredicateSet();
+    /// The copy constructor.
+    SCEVPredicateSet(const SCEVPredicateSet &Old);
+    /// Adds a predicate to this predicate set.
+    void add(const SCEVPredicate *N);
+
+    /// Vector with references to all predicates in this set.
+    SmallVector<SCEVPredicate *, 16> Preds;
+
+    /// 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 isAlwaysTrue() const override;
+    bool isAlwaysFalse() 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;
+      IdPreds = RHS.IdPreds;
+      Preds.clear();
+      for (unsigned II = 0; II < IdPreds.size(); ++II)
+        Preds.push_back(&IdPreds[II]);
+      assert(Preds.size() == RHS.Preds.size() && "Wrong Preds size after copy");
+      return *this;
+    }
+  };
+
   /// 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:
     /// LoopDisposition - An enum describing the relationship between a
     /// SCEV and a loop.
     enum LoopDisposition {
enum BlockDisposition {
       ProperlyDominatesBlock ///< The SCEV properly dominates the block.
     };
 
     /// Convenient NoWrapFlags manipulation that hides enum casts and is
     /// visible in the ScalarEvolution name space.
     static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT
     maskFlags(SCEV::NoWrapFlags Flags, int Mask) {
       return (SCEV::NoWrapFlags)(Flags & Mask);
     }
     static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT
     setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags) {
       return (SCEV::NoWrapFlags)(Flags | OnFlags);
     }
     static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT
     clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) {
       return (SCEV::NoWrapFlags)(Flags & ~OffFlags);
     }
public:
     /// The subscript of the outermost dimension is the Quotient: [j+k].
     ///
     /// Overall, we have: A[][n][m], and the access function: A[j+k][2i][5i].
     void delinearize(const SCEV *Expr,
                      SmallVectorImpl<const SCEV *> &Subscripts,
                      SmallVectorImpl<const SCEV *> &Sizes,
                      const SCEV *ElementSize);
 
+    /// Re-writes the SCEV according to the Predicates in \p Preds, by
+    /// applying overflow assumptions and sinking sext/zext expressions.
+    const SCEV *rewriteUsingPredicate(const SCEV *Scev, const Loop *L,
+                                      SCEVPredicateSet &A);
+
   private:
     /// Compute the backedge taken count knowing the interval difference, the
     /// stride and presence of the equality in the comparison.
     const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride,
                                bool Equality);
 
     /// Verify if an linear IV with positive stride can overflow when in a
     /// less-than comparison, knowing the invariant term of the comparison,
     /// the stride and the knowledge of NSW/NUW flags on the recurrence.
     bool doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride,
                             bool IsSigned, bool NoWrap);
 
     /// Verify if an linear IV with negative stride can overflow when in a
     /// greater-than comparison, knowing the invariant term of the comparison,
     /// the stride and the knowledge of NSW/NUW flags on the recurrence.
     bool doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride,
                             bool IsSigned, bool NoWrap);
 
   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;
   };
 
   /// \brief Analysis pass that exposes the \c ScalarEvolution for a function.

lib/Analysis/LoopAccessAnalysis.cpp

 // The implementation for the loop memory dependence that was originally
 // developed for the loop vectorizer.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
+#include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Analysis/VectorUtils.h"
Value *llvm::stripIntegerCast(Value *V) {
   if (CastInst *CI = dyn_cast<CastInst>(V))
     if (CI->getOperand(0)->getType()->isIntegerTy())
       return CI->getOperand(0);
   return V;
 }
 
 const SCEV *llvm::replaceSymbolicStrideSCEV(ScalarEvolution *SE,
                                             const ValueToValueMap &PtrToStride,
+                                            SCEVPredicateSet &Pred, const Loop *L,
                                             Value *Ptr, Value *OrigPtr) {
 
   const SCEV *OrigSCEV = SE->getSCEV(Ptr);
 
   // If there is an entry in the map return the SCEV of the pointer with the
   // symbolic stride replaced by one.
   ValueToValueMap::const_iterator SI =
       PtrToStride.find(OrigPtr ? OrigPtr : Ptr);
   if (SI != PtrToStride.end()) {
     Value *StrideVal = SI->second;
 
     // Strip casts.
     StrideVal = stripIntegerCast(StrideVal);
 
     // Replace symbolic stride by one.
-    Value *One = ConstantInt::get(StrideVal->getType(), 1);
+    Value *VOne = ConstantInt::get(StrideVal->getType(), 1);
+    ConstantInt *One = static_cast<ConstantInt *>(VOne);
     ValueToValueMap RewriteMap;
     RewriteMap[StrideVal] = One;
 
-    const SCEV *ByOne =
-        SCEVParameterRewriter::rewrite(OrigSCEV, *SE, RewriteMap, true);
+    SCEVPredicateSet P = Pred;
+    const SCEVEqualPredicate SI(SE->getSCEV(StrideVal), SE->getConstant(One));
+    P.add(&SI);
+    if (!P.isAlwaysFalse()) {
+      const SCEV *ByOne = SE->rewriteUsingPredicate(OrigSCEV, L, P);
       DEBUG(dbgs() << "LAA: Replacing SCEV: " << *OrigSCEV << " by: " << *ByOne
                    << "\n");
+      Pred = P;
       return ByOne;
     }
+  }
 
   // Otherwise, just return the SCEV of the original pointer.
   return SE->getSCEV(Ptr);
 }
 
 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 = replaceSymbolicStrideSCEV(SE, Strides, Pred, Lp, Ptr);
   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc);
   assert(AR && "Invalid addrec expression");
   const SCEV *Ex = SE->getBackedgeTakenCount(Lp);
-
   const SCEV *ScStart = AR->getStart();
   const SCEV *ScEnd = AR->evaluateAtIteration(Ex, *SE);
   const SCEV *Step = AR->getStepRecurrence(*SE);
 
   // For expressions with negative step, the upper bound is ScStart and the
   // lower bound is ScEnd.
   if (const SCEVConstant *CStep = dyn_cast<const SCEVConstant>(Step)) {
     if (CStep->getValue()->isNegative())

 /// 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 = replaceSymbolicStrideSCEV(SE, Strides, Pred, L, Ptr);
   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) &&
+      if (hasComputableBounds(SE, StridesMap, Ptr, TheLoop, Pred) &&
           // 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)) {
+           isStridedPtr(SE, Ptr, TheLoop, StridesMap, Pred) == 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;
         } 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) {
   Type *Ty = Ptr->getType();
   assert(Ty->isPointerTy() && "Unexpected non-ptr");
 
   // Make sure that the pointer does not point to aggregate types.
   auto *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 = replaceSymbolicStrideSCEV(SE, StridesMap, Pred,
+                                                  Lp, Ptr);
 
   const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev);
   if (!AR) {
     DEBUG(dbgs() << "LAA: Bad stride - Not an AddRecExpr pointer "
           << *Ptr << " SCEV: " << *PtrScev << "\n");
     return 0;
   }
 
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);
+  const SCEV *AScev = replaceSymbolicStrideSCEV(SE, Strides, Pred,
+                                                InnermostLoop, APtr);
+  const SCEV *BScev = replaceSymbolicStrideSCEV(SE, Strides, Pred,
+                                                InnermostLoop, BPtr);
 
-  int StrideAPtr = isStridedPtr(SE, APtr, InnermostLoop, Strides);
-  int StrideBPtr = isStridedPtr(SE, BPtr, InnermostLoop, Strides);
+  int StrideAPtr = isStridedPtr(SE, APtr, InnermostLoop, Strides, Pred);
+  int StrideBPtr = isStridedPtr(SE, BPtr, InnermostLoop, Strides, Pred);
 
   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;
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)) {
       ++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.
LoopAccessInfo::addRuntimeChecks(Instruction *Loc) const {
   return addRuntimeChecks(Loc, PtrRtChecking.getChecks());
 }
 
 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),
+    : 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) {
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];
 
 #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>
+SCEVCheckThreshold("force-max-scev-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)"));
 
 //===----------------------------------------------------------------------===//
 //                           SCEV class definitions
 //===----------------------------------------------------------------------===//

 
 void ScalarEvolutionWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequiredTransitive<AssumptionCacheTracker>();
   AU.addRequiredTransitive<LoopInfoWrapperPass>();
   AU.addRequiredTransitive<DominatorTreeWrapperPass>();
   AU.addRequiredTransitive<TargetLibraryInfoWrapperPass>();
 }
+
+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;
+}
+
+struct SCEVPredicateRewriter
+    : public SCEVVisitor<SCEVPredicateRewriter, const SCEV *> {
+public:
+  SCEVPredicateSet &P;
+
+  static const SCEV *rewrite(const SCEV *Scev, const Loop *L,
+                             ScalarEvolution &SE, SCEVPredicateSet &A) {
+    SCEVPredicateRewriter Rewriter(L, SE, A);
+    return Rewriter.visit(Scev);
+  }
+
+  SCEVPredicateRewriter(const Loop *L, ScalarEvolution &S, SCEVPredicateSet &P)
+      : P(P), SE(S), L(L) {}
+
+  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());
+  }
+
+  const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
+    const SCEV *Operand = visit(Expr->getOperand());
+    return SE.getZeroExtendExpr(Operand, Expr->getType());
+  }
+
+  const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) {
+    const SCEV *Operand = visit(Expr->getOperand());
+    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) {
+    for (SCEVPredicate *Pred : P.Preds) {
+      if (SCEVEqualPredicate *IPred = dyn_cast<SCEVEqualPredicate>(Pred)) {
+        if (IPred->getLHS() == Expr)
+          return IPred->getRHS();
+      }
+    }
+    return Expr;
+  }
+
+  const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) {
+    return Expr;
+  }
+
+private:
+  ScalarEvolution &SE;
+  const Loop *L;
+};
+
+const SCEV *
+ScalarEvolution::rewriteUsingPredicate(const SCEV *Scev, const Loop *L,
+                                       SCEVPredicateSet &Pred) {
+  return SCEVPredicateRewriter::rewrite(Scev, L, *this, Pred);
+}
+
+//// SCEV predicates
+SCEVPredicate::SCEVPredicate(unsigned short Type) : SCEVPredicateType(Type) {}
+
+SCEVEqualPredicate::SCEVEqualPredicate(
+    const SCEV *E0, const SCEV *E1)
+    : SCEVPredicate(pEqual), E0(E0), E1(E1) {}
+
+bool SCEVEqualPredicate::contains(const SCEVPredicate *N) const {
+  const SCEVEqualPredicate *Op =
+      dyn_cast<const SCEVEqualPredicate>(N);
+
+  if (!Op)
+    return false;
+
+  if ((Op->E0 == E0 && Op->E1 == E1) ||
+      (Op->E0 == E1 && Op->E1 == E0))
+    return true;
+
+  return false;
+}
+
+bool SCEVEqualPredicate::isAlwaysTrue() const {
+  if (E0 == E1) return true;
+  return false;
+}
+
+bool SCEVEqualPredicate::isAlwaysFalse() const { return false; }
+
+Value *SCEVEqualPredicate::generateCheck(Instruction *Loc,
+                                         ScalarEvolution *SE,
+                                         const DataLayout *DL,
+                                         SCEVExpander &Exp) {
+  IRBuilder<> Builder(Loc);
+
+  Value *Expr0 = Exp.expandCodeFor(E0, E0->getType(), Loc);
+  Value *Expr1 = Exp.expandCodeFor(E1, E1->getType(), Loc);
+
+  Value *C = Builder.CreateICmpNE(Expr0, Expr1, "ident.check");
+  return C;
+}
+
+void SCEVEqualPredicate::print(raw_ostream &OS, unsigned Depth) const {
+  OS.indent(Depth) << "Equal predicate: " << *E0 << " == " << *E1 << "\n";
+}
+
+SCEVPredicateSet::SCEVPredicateSet() : SCEVPredicate(pSet), Never(false) {}
+
+SCEVPredicateSet::SCEVPredicateSet(const SCEVPredicateSet &Old)
+    : SCEVPredicateSet() {
+  this->Never = Old.Never;
+  if (Never)
+    return;
+  IdPreds = Old.IdPreds;
+  for (unsigned II = 0; II < IdPreds.size(); ++II)
+    Preds.push_back(&IdPreds[II]);
+}
+
+bool SCEVPredicateSet::isAlwaysTrue() const {
+  if (Never)
+    return false;
+
+  for (auto II = Preds.begin(), EE = Preds.end(); II != EE; ++II) {
+    const SCEVPredicate *OA = *II;
+    if (!OA->isAlwaysTrue())
+      return false;
+  }
+
+  return true;
+}
+
+bool SCEVPredicateSet::isAlwaysFalse() 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 (isAlwaysTrue())
+    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->isAlwaysTrue())
+      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() > SCEVCheckThreshold || N->isAlwaysFalse()) {
+    Never = true;
+    return;
+  }
+  if (const SCEVEqualPredicate *OP =
+      dyn_cast<const SCEVEqualPredicate>(N)) {
+    for (unsigned II = 0, EE = IdPreds.size(); II < EE; ++II)
+      if (IdPreds[II].contains(OP))
+        return;
+
+    IdPreds.push_back(*OP);
+    Preds.push_back(&IdPreds.back());
+
+    return;
+  }
+  if (const SCEVPredicateSet *Set =
+                 dyn_cast<const SCEVPredicateSet>(N)) {
+    for (auto II = Set->Preds.begin(), EE = Set->Preds.end(); II != EE; ++II) {
+      add(*II);
+    }
+    return;
+  }
+  llvm_unreachable("Unknown SCEV predicate type!");
+}

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),
         TripCount(nullptr), VectorTripCount(nullptr), Legal(nullptr),
-        AddedSafetyChecks(false) {}
+        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();
   /// Create a new induction variable inside L.
   PHINode *createInductionVariable(Loop *L, Value *Start, Value *End,
                                    Value *Step, Instruction *DL);
   /// Copy and widen the instructions from the old loop.
   virtual void vectorizeLoop();
 
protected:
   /// Returns (and creates if needed) the trip count of the widened loop.
   Value *getOrCreateVectorTripCount(Loop *NewLoop);
 
   /// Emit a bypass check to see if the trip count would overflow, or we
   /// wouldn't have enough iterations to execute one vector loop.
   void emitMinimumIterationCountCheck(Loop *L, BasicBlock *Bypass);
   /// Emit a bypass check to see if the vector trip count is nonzero.
   void emitVectorLoopEnteredCheck(Loop *L, BasicBlock *Bypass);
-  /// Emit bypass checks to check if strides we've assumed to be one really are.
-  void emitStrideChecks(Loop *L, BasicBlock *Bypass);
+
+  void emitSCEVChecks(Loop *L, BasicBlock *Bypass);
   /// Emit bypass checks to check any memory assumptions we may have made.
   void emitMemRuntimeChecks(Loop *L, BasicBlock *Bypass);
   
   /// This is a helper class that holds the vectorizer state. It maps scalar
   /// instructions to vector instructions. When the code is 'unrolled' then
   /// then a single scalar value is mapped to multiple vector parts. The parts
   /// are stored in the VectorPart type.
   struct ValueMap {
     /// C'tor.  UnrollFactor controls the number of vectors ('parts') that
protected:
   Value *TripCount;
   /// Trip count of the widened loop (TripCount - TripCount % (VF*UF))
   Value *VectorTripCount;
 
   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)
         : Stride(Stride), Scev(Scev), Size(Size), Align(Align) {}
 
     StrideDescriptor() : Stride(0), Scev(nullptr), Size(0), Align(0) {}

 /// 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,
                             LoopVectorizationRequirements *R,
-                            const LoopVectorizeHints *H)
+                            const LoopVectorizeHints *H,
+                            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),
-        Requirements(R), Hints(H) {}
+        TTI(TTI), DT(DT), LAA(LAA), LAI(nullptr),
+        InterleaveInfo(SE, L, DT, Pred), Induction(nullptr),
+        WidestIndTy(nullptr), HasFunNoNaNAttr(false), Requirements(R),
+        Hints(H), Pred(Pred) {}
 
   /// ReductionList contains the reduction descriptors for all
   /// of the reductions that were found in the loop.
   typedef DenseMap<PHINode *, RecurrenceDescriptor> ReductionList;
 
   /// InductionList saves induction variables and maps them to the
   /// induction descriptor.
   typedef MapVector<PHINode*, InductionDescriptor> InductionList;
private:
   /// Used to emit an analysis of any legality issues.
   const LoopVectorizeHints *Hints;
 
   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,
-                             SmallPtrSetImpl<const Value *> &ValuesToIgnore)
+                             SmallPtrSetImpl<const Value *> &ValuesToIgnore,
+                             SCEVPredicateSet &Pred)
       : TheLoop(L), SE(SE), LI(LI), Legal(Legal), TTI(TTI), TLI(TLI),
-        TheFunction(F), Hints(Hints), ValuesToIgnore(ValuesToIgnore) {}
+        TheFunction(F), Hints(Hints), ValuesToIgnore(ValuesToIgnore),
+        Pred(Pred) {}
 
   /// Information about vectorization costs
   struct VectorizationFactor {
     unsigned Width; // Vector width with best cost
     unsigned Cost; // Cost of the loop with that width
   };
   /// \return The most profitable vectorization factor and the cost of that VF.
   /// This method checks every power of two up to VF. If UserVF is not ZERO
private:
   const TargetTransformInfo &TTI;
   /// Target Library Info.
   const TargetLibraryInfo *TLI;
   const Function *TheFunction;
   // Loop Vectorize Hint.
   const LoopVectorizeHints *Hints;
   // Values to ignore in the cost model.
   const SmallPtrSetImpl<const Value *> &ValuesToIgnore;
+  /// The SCEV predicate containing all the SCEV-related assumptions.
+  SCEVPredicateSet &Pred;
 };
 
 /// \brief This holds vectorization requirements that must be verified late in
 /// the process. The requirements are set by legalize and costmodel. Once
 /// vectorization has been determined to be possible and profitable the
 /// requirements can be verified by looking for metadata or compiler options.
 /// For example, some loops require FP commutativity which is only allowed if
 /// vectorization is explicitly specified or if the fast-math compiler option
if (TC > 0u && TC < TinyTripCountVectorThreshold) {
       else {
         DEBUG(dbgs() << "\n");
         emitAnalysisDiag(F, L, Hints, VectorizationReport()
                                           << "vectorization is not beneficial "
                                              "and is not explicitly forced");
         return false;
       }
     }
+    SCEVPredicateSet Pred;
 
     // Check if it is legal to vectorize the loop.
     LoopVectorizationRequirements Requirements;
     LoopVectorizationLegality LVL(L, SE, DT, TLI, AA, F, TTI, LAA,
-                                  &Requirements, &Hints);
+                                  &Requirements, &Hints, Pred);
     if (!LVL.canVectorize()) {
       DEBUG(dbgs() << "LV: Not vectorizing: Cannot prove legality.\n");
       emitMissedWarning(F, L, Hints);
       return false;
     }
 
     // Collect values we want to ignore in the cost model. This includes
     // type-promoting instructions we identified during reduction detection.
     SmallPtrSet<const Value *, 32> ValuesToIgnore;
     CodeMetrics::collectEphemeralValues(L, AC, ValuesToIgnore);
     for (auto &Reduction : *LVL.getReductionVars()) {
       RecurrenceDescriptor &RedDes = Reduction.second;
       SmallPtrSetImpl<Instruction *> &Casts = RedDes.getCastInsts();
       ValuesToIgnore.insert(Casts.begin(), Casts.end());
     }
 
     // Use the cost model.
     LoopVectorizationCostModel CM(L, SE, LI, &LVL, *TTI, TLI, AC, F, &Hints,
-                                  ValuesToIgnore);
+                                  ValuesToIgnore, Pred);
 
     // Check the function attributes to find out if this function should be
     // optimized for size.
     bool OptForSize = Hints.getForce() != LoopVectorizeHints::FK_Enabled &&
                       F->optForSize();
 
     // 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 (!VectorizeLoop && !InterleaveLoop) {
                    << DebugLocStr << '\n');
       DEBUG(dbgs() << "LV: Interleave Count is " << IC << '\n');
     }
 
     if (!VectorizeLoop) {
       assert(IC > 1 && "interleave count should not be 1 or 0");
       // If we decided that it is not legal to vectorize the loop then
       // interleave it.
-      InnerLoopUnroller Unroller(L, SE, LI, DT, TLI, TTI, IC);
+      InnerLoopUnroller Unroller(L, SE, LI, DT, TLI, TTI, IC, Pred);
       Unroller.vectorize(&LVL);
 
       emitOptimizationRemark(F->getContext(), LV_NAME, *F, L->getStartLoc(),
                              Twine("interleaved loop (interleaved count: ") +
                                  Twine(IC) + ")");
     } 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);
else {
     // 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,
+    Last = replaceSymbolicStrideSCEV(SE, Strides, Pred, TheLoop,
                                      Gep->getOperand(InductionOperand), Gep);
     if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(Last))
       Last =
           (C->getSCEVType() == scSignExtend || C->getSCEVType() == scZeroExtend)
               ? C->getOperand()
               : Last;
   }
   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Last)) {
BasicBlock *NewBB = BB->splitBasicBlock(BB->getTerminator(),
                                           "vector.ph");
   if (L->getParentLoop())
     L->getParentLoop()->addBasicBlockToLoop(NewBB, *LI);
   ReplaceInstWithInst(BB->getTerminator(),
                       BranchInst::Create(Bypass, NewBB, Cmp));
   LoopBypassBlocks.push_back(BB);
 }
 
-void InnerLoopVectorizer::emitStrideChecks(Loop *L,
-                                           BasicBlock *Bypass) {
+void InnerLoopVectorizer::emitSCEVChecks(Loop *L, BasicBlock *Bypass) {
   BasicBlock *BB = L->getLoopPreheader();
-  
   // Generate the code to check that the strides we assumed to be one are really
   // one. We want the new basic block to start at the first instruction in a
   // sequence of instructions that form a check.
-  Instruction *StrideCheck;
+  Instruction *SCEVCheck;
   Instruction *FirstCheckInst;
-  std::tie(FirstCheckInst, StrideCheck) = addStrideCheck(BB->getTerminator());
-  if (!StrideCheck)
+  std::tie(FirstCheckInst, SCEVCheck) =
+      Pred.generateGuardCond(BB->getTerminator(), SE);
+  if (!SCEVCheck)
     return;
 
   // Create a new block containing the stride check.
-  BB->setName("vector.stridecheck");
+  BB->setName("vector.scevcheck");
   auto *NewBB = BB->splitBasicBlock(BB->getTerminator(), "vector.ph");
   if (L->getParentLoop())
     L->getParentLoop()->addBasicBlockToLoop(NewBB, *LI);
   ReplaceInstWithInst(BB->getTerminator(),
-                      BranchInst::Create(Bypass, NewBB, StrideCheck));
+                      BranchInst::Create(Bypass, NewBB, SCEVCheck));
   LoopBypassBlocks.push_back(BB);
   AddedSafetyChecks = true;
 }
 
 void InnerLoopVectorizer::emitMemRuntimeChecks(Loop *L,
                                                BasicBlock *Bypass) {
   BasicBlock *BB = L->getLoopPreheader();
 
void InnerLoopVectorizer::createEmptyLoop() {
   // We need to test whether the backedge-taken count is uint##_max. Adding one
   // to it will cause overflow and an incorrect loop trip count in the vector
   // body. In case of overflow we want to directly jump to the scalar remainder
   // loop.
   emitMinimumIterationCountCheck(Lp, ScalarPH);
   // Now, compare the new count to zero. If it is zero skip the vector loop and
   // jump to the scalar loop.
   emitVectorLoopEnteredCheck(Lp, ScalarPH);
-  // Generate the code to check that the strides we assumed to be one are really
-  // one. We want the new basic block to start at the first instruction in a
-  // sequence of instructions that form a check.
-  emitStrideChecks(Lp, ScalarPH);
+  // Generate the code to check any assumptions that we've made for SCEV
+  // expressions.
+  emitSCEVChecks(Lp, ScalarPH);
+
   // Generate the code that checks in runtime if arrays overlap. We put the
   // checks into a separate block to make the more common case of few elements
   // faster.
   emitMemRuntimeChecks(Lp, ScalarPH);
   
   // Generate the induction variable.
   // The loop step is equal to the vectorization factor (num of SIMD elements)
   // times the unroll factor (num of SIMD instructions).
if (LAI->hasStoreToLoopInvariantAddress()) {
     emitAnalysis(
         VectorizationReport()
         << "write to a loop invariant address could not be vectorized");
     DEBUG(dbgs() << "LV: We don't allow storing to uniform addresses\n");
     return false;
   }
 
   Requirements->addRuntimePointerChecks(LAI->getNumRuntimePointerChecks());
+  Pred.add(&*LAI->Pred);
+
+  if (Pred.isAlwaysFalse()) {
+    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;
 }
 
 bool LoopVectorizationLegality::isInductionVariable(const Value *V) {
   Value *In0 = const_cast<Value*>(V);
   PHINode *PN = dyn_cast_or_null<PHINode>(In0);
   if (!PN)
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);
 
     // 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;
 
-    const SCEV *Scev = replaceSymbolicStrideSCEV(SE, Strides, Ptr);
+    const SCEV *Scev = replaceSymbolicStrideSCEV(SE, Strides, Pred, TheLoop, Ptr);
     PointerType *PtrTy = dyn_cast<PointerType>(Ptr->getType());
     unsigned Size = DL.getTypeAllocSize(PtrTy->getElementType());
 
     // An alignment of 0 means target ABI alignment.
     unsigned Align = LI ? LI->getAlignment() : SI->getAlignment();
     if (!Align)
       Align = DL.getABITypeAlignment(PtrTy->getElementType());