This is an archive of the discontinued LLVM Phabricator instance.

[SLPVectorizer] Make the scheduler aware of the TreeEntry operands.
ClosedPublic

Authored by vporpo on May 24 2019, 3:45 PM.

Details

Summary

The scheduler's dependence graph gets the use-def dependencies by accessing the operands of the instructions in a bundle. However, buildTree_rec() may change the order of the operands in TreeEntry, and the scheduler is currently not aware of this. This is not causing any functional issues currently, because reordering is restricted to the operands of a single instruction. Once we support operand reordering across multiple TreeEntries, as shown here: http://www.llvm.org/devmtg/2019-04/slides/Poster-Porpodas-Supernode_SLP.pdf , the scheduler will need to get the correct operands from TreeEntry and not from the individual instructions.

In short, this patch:

  • Connects the scheduler's bundle with the corresponding TreeEntry. It introduces new TE and Lane fields in ScheduleData.
  • Moves the location where the operands of the TreeEntry are initialized. This used to take place in newTreeEntry() setting one operand at a time, but is now moved pre-order just before the recursion of buildTree_rec(). This is required because the scheduler needs to access both operands of the TreeEntry in tryScheduleBundle().
  • Updates the scheduler to access the instruction operands through the TreeEntry operands instead of accessing the instruction operands directly.

Event Timeline

vporpo created this revision.May 24 2019, 3:45 PM
rcorcs added a subscriber: rcorcs.May 28 2019, 8:30 AM
dtemirbulatov added inline comments.May 28 2019, 12:19 PM
lib/Transforms/Vectorize/SLPVectorizer.cpp
1299 ↗(On Diff #201346)

I think it is better to use "while (BundleMember)"

vporpo added inline comments.May 28 2019, 12:41 PM
lib/Transforms/Vectorize/SLPVectorizer.cpp
1299 ↗(On Diff #201346)

I agree, BundleMember is a better variable name, but I don't see why a while loop is better here. We are simply iterating across all bundle members, so a for loop should be better, am I wrong?
The while() version of the code would look like this:

auto *BundleMember = SchedBundle;
while (BundleMember) {
    BundleMember->TE = Last;
    BundleMember->Lane = Lane;
    ++Lane;
    BundleMember = BundleMember->NextInBundle;
}

Isn't it a bit too verbose?

dtemirbulatov added inline comments.May 28 2019, 12:50 PM
lib/Transforms/Vectorize/SLPVectorizer.cpp
1299 ↗(On Diff #201346)

hmm, there is "auto* Bundle" is the loop header.

vporpo added inline comments.May 28 2019, 1:22 PM
lib/Transforms/Vectorize/SLPVectorizer.cpp
1299 ↗(On Diff #201346)

I am not sure I follow what you mean.

dtemirbulatov added inline comments.May 28 2019, 2:49 PM
lib/Transforms/Vectorize/SLPVectorizer.cpp
1299 ↗(On Diff #201346)

oh, I might be wrong, but I have a notion that for some compilers, it is additional overhead(runtime checks, etc.) to resolve auto in a loop header vs
loop body.

vporpo marked an inline comment as done.May 28 2019, 3:00 PM
vporpo added inline comments.
lib/Transforms/Vectorize/SLPVectorizer.cpp
1299 ↗(On Diff #201346)

I am not aware of this, but I can replace auto * with ScheduleData *.

vporpo updated this revision to Diff 201773.May 28 2019, 3:09 PM

Addressed @dtemirbulatov 's comment.

llvm-commits isn't subscribed

vporpo updated this revision to Diff 204167.Jun 11 2019, 2:28 PM

Rebased.

vporpo updated this revision to Diff 206892.Jun 27 2019, 11:07 AM
vporpo edited the summary of this revision. (Show Details)

Rebased.

vporpo updated this revision to Diff 207895.Jul 3 2019, 2:58 PM

Rebased.

This comment was removed by dtemirbulatov.

Overall, I don't see any issues with linking TreeEntry and SchedularData with lane information.

Looks good to me, just tryScheduleBundle() function type. I think we could simplify it later, @RKSimon @ABataev any comments?

Some minors, @ABataev any thoughts?

lib/Transforms/Vectorize/SLPVectorizer.cpp
1438 ↗(On Diff #207895)

auto, also we're asserting for I0 != null below - so maybe just use cast<> and drop the assert?

1446 ↗(On Diff #207895)

auto, also we're asserting for I != null below - so maybe just use cast<> and just assert for getNumOperands?

1947 ↗(On Diff #207895)

Update description to explain the returned values?

2399 ↗(On Diff #207895)

Use Optional instead?

ABataev added inline comments.Jul 29 2019, 9:05 AM
lib/Transforms/Vectorize/SLPVectorizer.cpp
1509–1511 ↗(On Diff #207895)

Seems to me, the values of Vectorized and SchedBundle params are tied: SchedBundle cannot be nullptr if Vectorized is true. Can we exclude Vectorized in this case?

1511 ↗(On Diff #207895)

Set default value to = nullptr to reduce the number of changes in newTreeEntry function calls.

1867 ↗(On Diff #207895)

Better to use an explicit list of captures.

1896–1898 ↗(On Diff #207895)

The formatting here is very strange, better to put comment inside of the else block.

2490 ↗(On Diff #207895)

Do you really need to provide Bundle here for gathering node?

vporpo updated this revision to Diff 212251.Jul 29 2019, 4:47 PM
vporpo marked 10 inline comments as done.

Addressed comments (and rebased).

vporpo added inline comments.Jul 29 2019, 4:48 PM
lib/Transforms/Vectorize/SLPVectorizer.cpp
1509–1511 ↗(On Diff #207895)

No, they are not tied: PHIs don't get scheduled, so they get no bundle, but a TreeEntry is generated for them.
Also we cannot generalize this rule: having PHInodes does not guarantee that we can create a vectorizable TreeEntry. For example, if these PHIs are already in tree, we would need to gather.

So we cannot just use a single variable, like the bundle pointer, to represent this state. I wrapped the bundle pointer inside an Optional as @RKSimon suggested, which can carry the state we need.

2490 ↗(On Diff #207895)

Good catch, no need to provide bundle here.

RKSimon added inline comments.Jul 30 2019, 1:29 AM
llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
1239

cast includes an isa<>assert - do we really need an extra one?

1247

cast includes an isa<>assert - do we really need an extra one?

vporpo updated this revision to Diff 212385.Jul 30 2019, 11:02 AM
vporpo marked 2 inline comments as done.

Addressed comments.

cheer - no more comments from me. @dtemirbulatov @ABataev ?

ABataev added inline comments.Jul 31 2019, 8:38 AM
llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
1667

auto &&DecrUnshed

1695–1696

Bad formatting here

4344

return nullptr;

4426

return Bundle;

vporpo updated this revision to Diff 212630.Jul 31 2019, 11:25 AM
vporpo marked 4 inline comments as done.

Addressed comments.

looks good to me.

ABataev added inline comments.Aug 15 2019, 6:37 AM
llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
1746–1750

\returns

2231–2232

Better to use TreeEntry * instead of auto *

2352–2354

TreeEntry *

2360–2362

TreeEntry *

2399–2400

TreeEntry *

vporpo updated this revision to Diff 215459.Aug 15 2019, 12:54 PM
vporpo marked 5 inline comments as done.

Addressed latest comments

This revision is now accepted and ready to land.Aug 15 2019, 1:48 PM
This revision was automatically updated to reflect the committed changes.