This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by sbaranga on Oct 9 2015, 8:31 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.

Diff Detail

Event Timeline

sbaranga updated this revision to Diff 36953.Oct 9 2015, 8:31 AM
sbaranga retitled this revision from to [SCEV][LV] Add SCEV Predicates and use them to re-implement stride versioning.
sbaranga updated this object.
sbaranga added reviewers: mzolotukhin, anemet, sanjoy.
sbaranga added a comment.EditedOct 9 2015, 8:34 AM

Hi,

I've cloned this from http://reviews.llvm.org/D12905, since the old comments were getting in the way.

This is also an updated version where I hope all the old issues have been solved.

This still depends on http://reviews.llvm.org/D13242.

Thanks,
Silviu

Hi Silviu,

It looks like Michael and Sanjoy have done most of the heavy lifting on this review, so for me I think it's in a good shape by this point.

I have a bunch of comments though.

James

include/llvm/Analysis/LoopAccessAnalysis.h
181

It doesn't make sense to me that this is plural when it doesn't relate to a set/list/vector of items. It's just one predicate, that happens to be a union.

In fact, why is this a unionpredicate anyway? Why can't it just be the superclass?

include/llvm/Analysis/ScalarEvolution.h
51

The sorting seems off here.

172

Is there a need for this separator line? I can't see any prior art anywhere else in the file

184

Why is this an unsigned short and not an enum SCEVPredicateTypes?

187

These don't match the usual LLVM style of enum naming. Normally we use a prefix, underscore then an UpperCamelCase identifier:

P_Set, P_Equal
207

What does Depth mean here? does it make sense to have a default parameter for people who "just want" to print something?

209

If you're going to use \brief, keep the first sentence separate from the rest of the text with an empty line.

214

Is it guaranteed that the values are contiguous and that no other instrucitons are interleaved between them? (i assume not, best to make this explicit).

265

Remove unneeded blank line.

323

Unneeded blank line.

335

Surely PUNION would be more appropriate?

lib/Analysis/LoopAccessAnalysis.cpp
130

Removed useful newline

lib/Analysis/ScalarEvolution.cpp
9505

You can just do:

return {static_cast..., static_cast...};

Yay C++11!

9532

Either all braces or no braces - don't mix braces in if/else statements.

9540

Can use C++11 syntax here too.

9547

You could probably use std::bind here.

9555

and here.

lib/Transforms/Vectorize/LoopVectorize.cpp
410–412

bypassssssss

Thanks, James! Replies inline.

include/llvm/Analysis/LoopAccessAnalysis.h
181

There are two ways to see it: as a collection of predicates or as one predicate. If we are adding more predicates to it maybe it makes sense to call it Preds?

We need this to be a union predicate because we're using the union predicate specific methods (that is we're adding new predicates to it, which we can only with the union predicates). I don't expect there would aver be a need to have something different then a union predicate there.

include/llvm/Analysis/ScalarEvolution.h
207

Depth is for indentation. Having the Depth be 0 by default makes sense to me.

sbaranga updated this revision to Diff 38135.Oct 22 2015, 9:08 AM

Addressing comments received from James.

  • renamed enum members to P_Union, P_Equal
  • renamed SCEVPredicateTypes to SCEVPredicateKind
  • renamed SCEVPredicateType to 'Kind'
  • now kind is of type SCEVPredicateKind instead of unsigned short
  • etc
sbaranga marked 15 inline comments as done.Oct 22 2015, 9:12 AM
sbaranga added inline comments.
lib/Analysis/ScalarEvolution.cpp
9547

I've tried using bind here but the code comes out horrible. For example:

std::any_of(SCEVPreds.begin(), SCEVPreds.end(),

std::bind(&SCEVPredicate::implies, std::placeholders::_1, N));

This requires more characters to write and seems more difficult to read. Maybe we should skip using bind here?

Ping? If there's anything I can do to make the review process go faster, please let me know.

-Silviu

sanjoy edited edge metadata.Oct 23 2015, 12:50 PM

The SCEV parts of the change is looking much better now. I didn't read through the logic carefully this time, and I only have minor stylistic issues. I'm happy to give a LGTM for the SCEV bits contingent on the stylistic issues getting addressed.

include/llvm/Analysis/ScalarEvolution.h
265

Use a default value for Depth here as well.

Also, very minor, you might want to override operator<< too, just for consistency with the rest of the codebase.

lib/Analysis/LoopAccessAnalysis.cpp
111–117

Use cast<>

lib/Analysis/ScalarEvolution.cpp
9386

Can we name this function better? I don't have a better suggestion though.

9391

When can I->getParent() be not equal to Loc->getParent()?

The non-SCEV stuff LGTM.

anemet accepted this revision.Oct 25 2015, 1:02 PM
anemet edited edge metadata.

Non-SCEV parts LGTM too.

Silviu,

I guess one thing that's missing form your summary which is another advantage to this approach that now we will only issue stride-checks when we actually had to assume stride=1 during analysis. Correct?

Thanks,
Adam

This revision is now accepted and ready to land.Oct 25 2015, 1:02 PM

Thanks for the reviews!

I guess one thing that's missing form your summary which is another advantage to this approach that now we will only issue stride-checks when we actually had to assume stride=1 during analysis. Correct?

We're not currently changing that behaviour (we're always adding the SCEVEqualPredicate when we see a pointer that we can version). Although that is certainly something we could do in the future.

Thanks,
Silviu

sbaranga updated this revision to Diff 38424.Oct 26 2015, 9:22 AM
sbaranga edited edge metadata.

Address review comments from Sanjoy.

sbaranga marked an inline comment as done.Oct 26 2015, 9:25 AM

Is this ok to commit? Maybe we could maybe handle the getFirstInst as a follow-up?

Thanks,
Silviu

lib/Analysis/ScalarEvolution.cpp
9386

I don't have any good idea here.

It should also probably be moved into some place where it can be shared with LoopAccessAnalysis, but I don't know where exactly it would fit.

9391

This was part of the original "getFirstInst" implementation lifted out of LoopVectorize. This can potentially happen when theIRBuilder is folding instructions outside of the current basic block produced by the SCEV expander (I think the SCEV expander is able to produce such instructions - at least for SCEVUnknowns).

sanjoy added inline comments.Oct 26 2015, 11:39 AM
lib/Analysis/ScalarEvolution.cpp
9391

I know I'm bikeshedding a lot on this, but I think a better utility would be

BasicBlock *getValueParent(Value *V) {
  if (I = dyn_cast<Instruction>(V))
    return I->getParent();
  return nullptr;
}

then where you call getFirstInst you could instead do

if (!FirstInst && getValueParent(C) == Loc)
  FirstInst = cast<Instruction>(C);

I think that will be clearer and almost as concise -- reading getFirstInst(A,B,C) does not really tell me anything about what it is supposed to do, especially since one of the parameters is named FirstInst.

sbaranga updated this revision to Diff 38530.Oct 27 2015, 5:44 AM

Change the RT check generation interface to return a Value*, instead of a pair of instructions.

We were previosly returning a pair of instructions to confirm with the existing versioning
interfaces. However, that created a bunch of problems, and made the checking code less nice.

It also turns out that we don't really need to return the first added instruction (and it would
be easy for a user to get anyway).

sbaranga added inline comments.Oct 27 2015, 5:53 AM
lib/Analysis/ScalarEvolution.cpp
9391

I've removed the versioning interface that was causing us to use this function (I should have probably done so the when you've previously asked for it).

We're now returning a Value*, so no need to use this getFirstInst function (which was removed). This removes a whole bunch of other problems (we aren't casting Value * to Instruction * anymore), so it should be much nicer.

hfinkel added inline comments.Oct 27 2015, 5:48 PM
lib/Analysis/ScalarEvolution.cpp
70

We currently have SCEVExpander use SCEV, but not the other-way around. Could you move the IR-building code into SCEVExpander to avoid changing the layering here?

sbaranga updated this revision to Diff 38651.Oct 28 2015, 6:15 AM

Resolve the layering issue raised by Hal.

  • the SCEVExpander now has an expandCodeForPredicate method which we use to generate the checks.
  • removed the generateGuardCond/generateCheck methods.

Why is all of the SCEVPredicate code in ScalarEvolution.{cpp.h}, as opposed to being in its own files? Is there a two-way coupling that I'm missing, or will there be one in the future?

Hi Hal,

Why is all of the SCEVPredicate code in ScalarEvolution.{cpp.h}, as opposed to being in its own files? Is there a two-way coupling that I'm missing, or will there be one in the future?

Currently we use the memory pool from ScalarEvolution for the allocation of Predicates.

In the future I plan to make ScalarEvolution give some answers for getBackedgeCount which will be guarded by SCEVPredicates, so there will probably a tight coupling there.

Also, there's also a lot of commonality between the SCEV rewritting use cases and some of the reasoning that SCEV does already (at least that's what I observed for overflows and sext/zext handling). So there might be some opportunity for sharing code in these cases.

Thanks,
Silviu

hfinkel accepted this revision.Oct 28 2015, 8:04 AM
hfinkel added a reviewer: hfinkel.

Hi Hal,

Why is all of the SCEVPredicate code in ScalarEvolution.{cpp.h}, as opposed to being in its own files? Is there a two-way coupling that I'm missing, or will there be one in the future?

Currently we use the memory pool from ScalarEvolution for the allocation of Predicates.

In the future I plan to make ScalarEvolution give some answers for getBackedgeCount which will be guarded by SCEVPredicates, so there will probably a tight coupling there.

Also, there's also a lot of commonality between the SCEV rewritting use cases and some of the reasoning that SCEV does already (at least that's what I observed for overflows and sext/zext handling). So there might be some opportunity for sharing code in these cases.

Thanks,
Silviu

In that case, LGTM too.

@sanjoy: are you happy with the current form of the patch? I think the previous issues should have been solved.

Thanks,
Silviu

sanjoy accepted this revision.Oct 31 2015, 10:01 AM
sanjoy edited edge metadata.

lgtm

sbaranga closed this revision.Nov 2 2015, 6:43 AM

Committed in r251800. Thanks all for the hard work you've put in reviewing this patch!

-Silviu

mmarjieh added inline comments.
include/llvm/Analysis/ScalarEvolutionExpander.h
154–157

Is the comment wrong? I see that in the implementation you do a invert of the operation.

I am talking about this:
The result will be of type i1 and will have a value of 0 when the
predicate is false and 1 otherwise.