This is an archive of the discontinued LLVM Phabricator instance.

[SLP] Initial rework for min/max horizontal reduction vectorization, NFC.
ClosedPublic

Authored by ABataev on Feb 1 2017, 10:05 AM.

Details

Summary

All getReductionCost() functions are renamed to getArithmeticReductionCost() + added basic infrastructure to handle non-binary reduction operations.

Diff Detail

Event Timeline

ABataev created this revision.Feb 1 2017, 10:05 AM
mkuper added inline comments.
lib/Analysis/CostModel.cpp
196

Can this ever be a Value that's not an Instruction?
(Same question applies to getReductionOpcode())

lib/Transforms/Vectorize/SLPVectorizer.cpp
4094

This basically complements the change in line 4803 - 4823, right, but taken together, those two changes are NFC, regardless of everything else here, right? Or am I confused and this depends on something else?

4197

This part of the change is completely orthogonal to the name change and using matchers, right?

Anyway, I think I see where this is going. This is possibly similar to what Ayal, Gil & company are doing for LV, in terms of recipes?
Adding them to take a look.

4198

What does being valid mean in this context? Just that this is a "non-null handle"

4245

only adds at this point. :-)
Also, if you're checking the op here, I'd expect a check of isAssociative() as well.

4249

So, by "of the same kind" you mean "both a reduction op or both a reduced value", which is something you determine by either both LHS/RHS being null, or both being non-null?
Can you please be more explicit about this? Also, maybe it's worth having an explicit flag for this, instead of relying on LHS and RHS being null?

4271

I've cleaned this up in the existing code, there's no need to special-case FAdd, you can just CreateBinOp for it.

ABataev updated this revision to Diff 86833.Feb 2 2017, 9:29 AM
ABataev marked 3 inline comments as done.

Update after review

RKSimon resigned from this revision.Feb 8 2017, 3:47 AM
RKSimon added a subscriber: RKSimon.
Ayal added inline comments.Feb 15 2017, 8:20 AM
lib/Analysis/CostModel.cpp
211

Can PatternMatch be put to more use, by asking it to match a BinOp whose L and R sides are both shuffles, when Level > 0?

Passing L and R by reference here saves little compared to the original direct calls to getOperand(0) and getOperand(1), and seems mostly redundant elsewhere.

404

Check if RdxOp, or use cast instead of dyn_cast?

lib/Transforms/Vectorize/SLPVectorizer.cpp
4094

V is-surely-a<BinaryOperator>, being a non-nullptr to BinaryOperator, right?

ABataev added inline comments.Feb 17 2017, 1:24 AM
lib/Analysis/CostModel.cpp
196

Of course no, only instructions can be used here. I'll convert these params to Instruction *.

211

This is just an initial patch. In future it will be extended with support of min/max patterns, that's why this kind of recognition of LHS/RHS operands is placed in function. Another thing, that it will be better just to return the record of opcode + LHS/RHS parts, rather than pass L/R by reference.

404

Yes, missed this, thanks. Will fix.

lib/Transforms/Vectorize/SLPVectorizer.cpp
4094

Yes, you're right, I'll remove these changes from this patch and prepare another one for CmpInsts.

4094

Yes, forgot to change type of parameter, will do it

4197

No, actually it is basic infrastructure for supporting horizontal reduction vectorization of not-BinOp instructions. It does not change the functionality, but allows later easily to support vectorization of other complex instructions, like min/max.

4198

Will try to remove it

4245

Yes, will fix this.
isAssociative() requires actual instruction instead of Opcode only, that's why I did not check it here.

4249

Yes, it is exactly what I meant.
Ok, will think about it.

4271

Ok, will fix it.

Ayal added inline comments.Feb 17 2017, 1:40 AM
lib/Transforms/Vectorize/SLPVectorizer.cpp
4213

Should IsReducedValue be set to false here?

4249

The IsReducedValue explicit flag indicates if its a reduction op or reduced value, right?

To implement the behavior documented above: "Checks if two operation data are both a reduction op or both a reduced value", it's enough to have the "IsReducedValue == OD.IsReducedValue" part.

4267

re[d]uction

ABataev updated this revision to Diff 88877.Feb 17 2017, 6:20 AM

Update after review

Ayal added inline comments.Mar 13 2017, 5:27 PM
lib/Transforms/Vectorize/SLPVectorizer.cpp
4094

I must be missing something here; tryToVectorize() is still being fed by BinaryOperator*, right? Wondering why the parameter type change. Better include this change in follow-up patch which tries to vectorize non BinaryOperators, if that's the intention.

4196

"+ validity" should be removed?

4219

Still a couple of "if (x.Opcode == 0)" cases, may as well make use of this bool().

4245

isVectorizable() is used only in conjuction with isAssociative(I), and as an assert when getOpcode() is called by getReductionCost(). Isn't it better to have isVectorizable(I) also call isAssociative?

4249

It sounds like you can

assert ((IsReducedValue != OD.IsReducedValue) || ((!LHS == !OD.LHS) && (!RHS == !OD.RHS) && Opcode == OD.Opcode) && "message");

no need to actually check them all to return true, right?

4267

typo

4269

Every other method fits with the passive, storage-type "OperationData" name of this struct, but this last method may look a bit odd doing "OperationData.createOp()". All that it's contributing is its Opcode which it can provide, and some asserts. Is there a better way of keeping OperationData's nature, or a better name for it?

4745

Not sure why you wanted this change; but how about simply "if (isa<BinaryOperator>(Inst))"?

ABataev marked an inline comment as not done.Jun 2 2017, 7:26 AM
ABataev added inline comments.
lib/Transforms/Vectorize/SLPVectorizer.cpp
4094

Restored back.

4196

Removed

4219

Tried to replace all

4245

Added isVectorized(Instruction *I)

4249

Modified it a bit, still need to compare the opcode

4267

Yes, thanks, fixed

4269

Modified this method, now it accepts only Builder and optional name

4745

Restored it

ABataev updated this revision to Diff 101209.Jun 2 2017, 7:37 AM

Update after review

anemet added a subscriber: anemet.Jun 2 2017, 8:07 AM
anemet added inline comments.
lib/Analysis/CostModel.cpp
189

Contains

Some minor style comments

lib/Analysis/CostModel.cpp
202

No need to initialize these.

Value *L, *R;
204

Use the ReductionData constructor for clarity?

lib/Transforms/Vectorize/SLPVectorizer.cpp
4228

?

4233

Add assert message

4238

Add assert message

4243

Add assert message

4302

Use OperationData constructor for clarity

4305

Add assert message

ABataev marked 9 inline comments as done.Jun 2 2017, 1:06 PM
RKSimon edited edge metadata.Jun 7 2017, 7:50 AM

@ABataev You marked a lot of the comments done but haven't updated the diff.

ABataev updated this revision to Diff 101750.Jun 7 2017, 8:53 AM

Update after review.

A couple of NFC changes that will reduce this patch.

include/llvm/CodeGen/BasicTTIImpl.h
993

You should probably move this comment (unchanged) as a NFC commit right away to reduce the patch. I can't tell if you've changed anything.

include/llvm/Transforms/Vectorize/SLPVectorizer.h
85

Do this as an NFC commit now - its a tidyup that isn't relevant to the patch.

ABataev updated this revision to Diff 101934.Jun 8 2017, 9:43 AM

Update to trunk

What's happening with this? It seems almost ready to go.

lib/Analysis/CostModel.cpp
196

Still not Instruction*

200

Worth making this an Optional<> instead of relying on Opcode == 0?

ABataev added inline comments.Jul 27 2017, 7:41 AM
lib/Analysis/CostModel.cpp
196

Investigated this problem once again, it maybe not of Instruction type, for example, it may be an Argument. So, we have to use Value * here.

200

Ok, will do

ABataev updated this revision to Diff 108463.Jul 27 2017, 7:45 AM

Update after review

There's still a lot going on in this patch but it looks alright to me (I noticed one minor).

Does anyone have any further comments?

lib/Transforms/Vectorize/SLPVectorizer.cpp
4213

If OperationData is a struct then this public can go?

avt77 added a subscriber: avt77.Jul 27 2017, 8:40 AM

Could we split it on 2 sub-parts:

1 - rename (maybe NFC?)
2 - new infrastructure

In this case it will be easier and smaller.

RKSimon accepted this revision.Jul 31 2017, 5:30 AM

LGTM - if possible please commit the getArithmeticReductionCost rename as a separate pre-commit.

This revision is now accepted and ready to land.Jul 31 2017, 5:30 AM
This revision was automatically updated to reflect the committed changes.