This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by sbaranga on Sep 16 2015, 7:53 AM.

Details

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).

Diff Detail

Event Timeline

sbaranga updated this revision to Diff 34892.Sep 16 2015, 7:53 AM
sbaranga retitled this revision from to [SCEV][LV] Introduce SCEV Predicates and use them to re-implement stride versioning.
sbaranga updated this object.
sbaranga added reviewers: anemet, mzolotukhin.
sbaranga added subscribers: hfinkel, sanjoy, rengolin and 2 others.
hfinkel added inline comments.Sep 22 2015, 4:32 PM
include/llvm/Analysis/ScalarEvolution.h
242

Remove commented-out code.

lib/Analysis/ScalarEvolution.cpp
9498

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 edited edge metadata.Sep 22 2015, 5:18 PM

Hi Silviu,

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

Adam

include/llvm/Analysis/LoopAccessAnalysis.h
296

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

546–577

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

include/llvm/Analysis/ScalarEvolution.h
174

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

188–194

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.

1245–1248

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

lib/Analysis/ScalarEvolution.cpp
114–118

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.

9243–9250

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

9252

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?

9431

OF for overflow? ;)

lib/Transforms/Vectorize/LoopVectorize.cpp
321–324

Overflow again.

Hi, Adam, Hal,

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

Silviu

include/llvm/Analysis/LoopAccessAnalysis.h
546–577

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
188–194

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
114–118

Ok, I'll remove this.

9252

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).

9498

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 added inline comments.Sep 24 2015, 9:51 AM
lib/Analysis/ScalarEvolution.cpp
9252

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 edited edge metadata.Sep 24 2015, 11:57 AM

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
575–576

Where is this used?

include/llvm/Analysis/ScalarEvolution.h
205

Please add some description for this class.

237–238

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)?

239–240

Should it be called Invalid or something like this then?

lib/Analysis/LoopAccessAnalysis.cpp
107–121

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
9252

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.

9499

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

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
575–576

This is an artefact of rebasing and should be removed.

include/llvm/Analysis/ScalarEvolution.h
237–238

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

239–240

"Invalid" would be better, yes.

hfinkel added inline comments.Sep 25 2015, 2:34 PM
lib/Analysis/ScalarEvolution.cpp
9498

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.

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
243

What is IdPreds and how is it different from Preds?

252–253

This probably should be private/protected.

258–259

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

lib/Analysis/ScalarEvolution.cpp
9371–9372

Maybe just
return E0 == E1;
?

9386

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

9402

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

9410

Another candidate for a range loop.

9411–9412

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.

9429

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

9442–9444

Why do we need to do or with False?

9458

Range loop?

9479–9489

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

sbaranga updated this revision to Diff 35882.Sep 28 2015, 9:39 AM
sbaranga edited edge metadata.

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).

Hi Michael,

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
243

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

258–259

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
9252

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

9386

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?

9482

Makes sense. Thanks!

Hi Silviu,

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

Michael

include/llvm/Analysis/ScalarEvolution.h
243

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

mzolotukhin added inline comments.Sep 28 2015, 12:16 PM
include/llvm/Analysis/ScalarEvolution.h
197–199

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

204–205

s/assume#/assume/

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

250–251

Why do we need it as a public member?

lib/Analysis/LoopAccessAnalysis.cpp
426

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

lib/Analysis/ScalarEvolution.cpp
9252

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.

9386

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.

9419

Why are this and 9224 lines different?

9421–9422

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

Thanks, Michael! Answers inline.

  • Silviu
include/llvm/Analysis/ScalarEvolution.h
243

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.

250–251

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

lib/Analysis/ScalarEvolution.cpp
9252

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

9419

One of these should be removed, yes.

9421–9422

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 added inline comments.Sep 30 2015, 2:53 AM
include/llvm/Analysis/ScalarEvolution.h
204–205

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 updated this revision to Diff 36096.Sep 30 2015, 6:26 AM

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.

Hi Silviu,

Thanks for the changes! Please find my comments inline.

Michael

include/llvm/Analysis/ScalarEvolution.h
204–205

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.

243

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
9252

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

anemet added inline comments.Sep 30 2015, 2:21 PM
include/llvm/Analysis/LoopAccessAnalysis.h
467–470

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 requested changes to this revision.Sep 30 2015, 3:14 PM
sanjoy added a reviewer: sanjoy.

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

include/llvm/Analysis/ScalarEvolution.h
187

Minor: I'd put newlines between method declarations.

194

Also minor, but why not just call it implies?

200

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

211

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.

223

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

237

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.

242

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.

261

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
9292

Use const auto *.

9297

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

9313

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

9336

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.

9385

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).

9395

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

9396

[Optional] Why not std::any_of?

9399

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

This revision now requires changes to proceed.Sep 30 2015, 3:14 PM

Thanks for the reviews! Replies inline.

include/llvm/Analysis/LoopAccessAnalysis.h
467–470

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
242

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

243

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.

261

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
9297

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.

9385

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

sbaranga updated this revision to Diff 36248.Oct 1 2015, 8:26 AM
sbaranga edited edge metadata.

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 added inline comments.Oct 1 2015, 9:44 AM
include/llvm/Analysis/LoopAccessAnalysis.h
467–470

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 added inline comments.Oct 2 2015, 7:08 AM
include/llvm/Analysis/LoopAccessAnalysis.h
467–470

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 added inline comments.Oct 3 2015, 9:56 PM
include/llvm/Analysis/LoopAccessAnalysis.h
467–470

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 added inline comments.Oct 5 2015, 5:48 AM
include/llvm/Analysis/LoopAccessAnalysis.h
467–470

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 updated this revision to Diff 36727.Oct 7 2015, 5:19 AM
sbaranga edited edge metadata.

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 added a comment.Oct 7 2015, 2:03 PM

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
194

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

213

Please document Loc.

216

Newline here?

267

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

285

Why not DenseMap?

312

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

1271

Please construct this in the move constructor.

lib/Analysis/LoopAccessAnalysis.cpp
113

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

lib/Analysis/ScalarEvolution.cpp
9247

Use auto *I here.

9247

Isn't V always an instruction?

9258

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

9283

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

9301

Use three slashes.

9360

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.

9385

In that case, shouldn't you have

AllCheck = CheckBuilder.CreateAnd(AllCheck, CheckResult);

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

9394

Shouldn't this be CreateAnd?

9394

As mentioned earlier, IIUC this should be a CreateAnd.

9437

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

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
295

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

337–340

Explain the Preds parameter

546–547

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

594–603

Comment the Preds parameter.

605–608

Here too.

635–636

Didn't you want to get rid of MaxSCEVPredicates?

lib/Analysis/LoopAccessAnalysis.cpp
1783–1784

Ah, MaxSCEVPredicates is unused.

lib/Transforms/Vectorize/LoopVectorize.cpp
401–402

Comment missing

510–511

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

778–779

Here too.

1351

Missing comment.

1692–1701

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

sbaranga marked 80 inline comments as done.Oct 8 2015, 3:53 AM
sbaranga added inline comments.
lib/Analysis/ScalarEvolution.cpp
9243–9250

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

9360

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

9385

See the comment bellow.

9394

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?

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 added a comment.Oct 8 2015, 9:33 AM

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 abandoned this revision.Oct 9 2015, 8:43 AM

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

Thanks,
Silviu