This is an archive of the discontinued LLVM Phabricator instance.

[SLP] Allow reordering of vectorization trees with reused instructions.
ClosedPublic

Authored by ABataev on Apr 4 2018, 8:59 AM.

Details

Summary

If some leaves have the same instructions to be vectorized, we may
incorrectly evaluate the best order for the root node (it is built for the
vector of instructions without repeated instructions and, thus, has less
elements than the root node). In this case we just can not try to reorder
the tree + we may calculate the wrong number of nodes that requre the
same reordering.
For example, if the root node is \<a+b, a+c, a+d, f+e\>, then the leaves
are \<a, a, a, f\> and \<b, c, d, e\>. When we try to vectorize the first
leaf, it will be shrink to \<a, b\>. If instructions in this leaf should
be reordered, the best order will be \<1, 0\>. We need to extend this
order for the root node. For the root node this order should look like
\<3, 0, 1, 2\>. This patch allows extension of the orders of the nodes
with the reused instructions.

Diff Detail

Event Timeline

ABataev created this revision.Apr 4 2018, 8:59 AM

Would it be possible to increase test coverage?

lib/Transforms/Vectorize/SLPVectorizer.cpp
5787

This assert doesn't seem to tally with the TODO just above?

Would it be possible to increase test coverage?

Yes, I will try to add some more tests.

lib/Transforms/Vectorize/SLPVectorizer.cpp
5787

Actually, it does, I just need to remove this TODO. This patch fixes this TODO.

ABataev updated this revision to Diff 141713.Apr 9 2018, 12:24 PM

Updated tests check + fixed building of the root order.

RKSimon added inline comments.Apr 14 2018, 4:36 AM
lib/Transforms/Vectorize/SLPVectorizer.cpp
525

Set default value in the resize?

ABataev marked an inline comment as done.Apr 16 2018, 11:05 AM
ABataev updated this revision to Diff 142667.Apr 16 2018, 11:22 AM

Update after review

ABataev updated this revision to Diff 144170.Apr 26 2018, 11:32 AM

Rebase against latest version.

Herald added a project: Restricted Project. · View Herald TranscriptSep 4 2019, 9:17 AM
Matt added a subscriber: Matt.Sep 16 2020, 1:51 PM
RKSimon accepted this revision.Sep 17 2020, 5:54 AM

LGTM - cheers

This revision is now accepted and ready to land.Sep 17 2020, 5:54 AM
ABataev updated this revision to Diff 292584.Sep 17 2020, 12:17 PM

Rebase + fixes

RKSimon accepted this revision.Sep 18 2020, 2:51 AM

LGTM again (thanks for rebasing - I didn't notice how old the last patch was!). One minor.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
530 ↗(On Diff #292584)

2 x Mask.clear() - merge issue?

ABataev added inline comments.Sep 18 2020, 6:23 AM
llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
530 ↗(On Diff #292584)

Yes, missed it, thanks!