This is an archive of the discontinued LLVM Phabricator instance.

[SLP]Improve bottom-to-top reordering.
ClosedPublic

Authored by ABataev on Feb 24 2022, 8:31 AM.

Details

Summary

Currently bottom-to-top reordering analysis counts orders of the
operands and then adds natural order counts for the operand users. It is
very conservative, this the user nodes themselves may require
reordering. Patch improves bottom-to-top analysis by checking for the
user nodes if they require/allows the reordring. If the user node must
be reordered, has reused scalars, is an alternate op vectorization node,
is a non-ordered gather node or may allow reordering because of the
reordered operands, such node is considered as the node that allows
reodring and is not counted as a node with the natural order.

Diff Detail

Event Timeline

ABataev created this revision.Feb 24 2022, 8:31 AM
ABataev requested review of this revision.Feb 24 2022, 8:31 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 24 2022, 8:31 AM
vporpo added inline comments.Feb 24 2022, 10:32 PM
llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
3478–3479

Please rename Data to something more descriptive. I think it contains a pair of the TreeEntry and a vector of its uses along with their indexes, so something like TEAndUses would be fine.

Also it is probably better to use the actual type here instead of auto, ti would make it easier to read.

3478–3479

I think that this needs a better name, perhaps something like CanReorderOperands.
Also this lambda is getting a bit too long, wdyt about replacing it with a member function?

3478–3479

If I understand correctly, this block of code could be a separate member function of the TreeEntry struct that returns the operand TreeEntry: TreeEntry *getOperandTE(unsigned OpIdx). Wdyt ?

3481

It is hard to remember what Data and Data.first refers to at this point. I think it would be better to use a variable to hold the value like TreeEntry *TE = Data.first. I think Data.first also appears earlier in the code.

3486

I am a bit confused with what is going on here. I was under the impression that the Users map holds the edges towards the operands (which btw should probably be part of TreeEntry and built during buildTree?). Why are we adding edges here?

3568

I am not sure what Res refers to. Please use a better name and/or add a comment ?
Also, since it is used after the lambda, it should probably be moved closer to where it is being used.

3569

Perhaps move the comment from line 3554 here?

3583

Could you add a brief comment explaining what this loop does?

ABataev added inline comments.Feb 25 2022, 1:00 PM
llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
3486

Oririginally, Users contains edges between reorderable operands only (vector operands with reordering data or loads/extractelements and/or gathers of extractselements that require reordering). Here we add some extra vectorizable operands, if they were not added, because they did not have the reordering data.
We add the vectorizable operands here as they still may require reordering, while gathers are free for reroder.

ABataev updated this revision to Diff 411514.Feb 25 2022, 1:41 PM

Rebase + address comments

vporpo accepted this revision.Feb 25 2022, 4:53 PM

Thanks for the changes LG.

This revision is now accepted and ready to land.Feb 25 2022, 4:53 PM
This revision was landed with ongoing or failed builds.Feb 28 2022, 6:52 AM
This revision was automatically updated to reflect the committed changes.
xbolva00 added inline comments.
llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
1910

There is no NonVectorized parameter. Should be ReorderableGathers?

Herald added a project: Restricted Project. · View Herald TranscriptMar 24 2022, 2:47 AM
ABataev added inline comments.Mar 24 2022, 4:50 AM
llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
1910

Yep, will fix it