This is an archive of the discontinued LLVM Phabricator instance.

[SLPVectorizer] Operand reordering across multiple instructions.
Needs ReviewPublic

Authored by vporpo on Jun 21 2019, 11:50 AM.

Details

Summary

This patch implements operand reordering across trees of Add/Subs, referred to as "SuperNodes".
For example, it helps vectorize code like this:
S[0] = (A[0] - B[0]) - C[0]
S[1] = (B[1] + C[1]) + A[1]
A more detailed description of the technique can be found here: http://www.llvm.org/devmtg/2019-04/slides/Poster-Porpodas-Supernode_SLP.pdf.

The two main changes introduced by this patch are:
i. The SuperNode class that represents the Add/Sub trees and their immediate operands that we are reordering.
ii. A local change in the buildTree_rec() recursion that forms the SuperNode.

Please note that this patch depends on the scheduler changes of D62432.

Event Timeline

vporpo created this revision.Jun 21 2019, 11:50 AM

Please can you precommit the tests?

bjope added a subscriber: bjope.Jun 24 2019, 1:44 AM
rcorcs added a subscriber: rcorcs.Jun 24 2019, 3:22 AM
xbolva00 added inline comments.
lib/Transforms/Vectorize/SLPVectorizer.cpp
1608 ↗(On Diff #206038)

llvm::all_of

1622 ↗(On Diff #206038)

This looks quite generic so maybe it can be reused. Reassoc pass should have similar code too?

@spatel

3223 ↗(On Diff #206038)

This is same code as the code added just above ? Please move it to own function.

xbolva00 added inline comments.Jun 25 2019, 8:02 AM
lib/Transforms/Vectorize/SLPVectorizer.cpp
4959 ↗(On Diff #206038)

pop_val_back?

RKSimon added inline comments.Jun 25 2019, 8:47 AM
lib/Transforms/Vectorize/SLPVectorizer.cpp
1181 ↗(On Diff #206038)

Tweak the brackets to make the ordering more readable:

return (OpIdx == 0) ? UserAPO : (IsUserInverse ? !UserAPO : UserAPO);
2620 ↗(On Diff #206038)

Don't use auto unless the type is obvious - there's a number of these in the patch that fixing.

vporpo updated this revision to Diff 206487.Jun 25 2019, 11:05 AM
vporpo marked 5 inline comments as done.

Addressed comments and rebased.

lib/Transforms/Vectorize/SLPVectorizer.cpp
3223 ↗(On Diff #206038)

I am not sure what you mean. The only repetition I could move to its own function is the checks in the if condition.
If you are referring to the whole if-else block, then I agree there is a lot of repetition in buildTree_rec(), but it should be part of a separate cleanup patch.

@vporpo Are you still looking at this please?

@RKSimon Yes, I will update this patch in a day or two.

vporpo updated this revision to Diff 229662.Nov 15 2019, 4:22 PM

Rebased.

RKSimon resigned from this revision.Jul 8 2021, 2:10 PM