This is an archive of the discontinued LLVM Phabricator instance.

[MLIR] Add parallel loop coalescing.
ClosedPublic

Authored by tpopp on Mar 18 2020, 7:22 AM.

Details

Summary
This allows conversion of a ParallelLoop from N induction variables to
some nuber of induction variables less than N.

The first intended use of this is for the GPUDialect to convert
ParallelLoops to iterate over 3 dimensions so they can be launched as
GPU Kernels.

To implement this:
- Normalize each iteration space of the ParallelLoop
- Use the same induction variable in a new ParallelLoop for multiple
  original iterations.
- Split the new induction variable back into the original set of values
  inside the body of the ParallelLoop.

Diff Detail

Event Timeline

tpopp created this revision.Mar 18 2020, 7:22 AM
tpopp updated this revision to Diff 251096.Mar 18 2020, 8:32 AM

Refactored some code to be more proper.

tpopp updated this revision to Diff 251099.Mar 18 2020, 8:42 AM

Save loops.getLoc in a variable and use variable everywhere instead.

Would it *please* be possible for MLIR patches to be named as such, please?

lebedev.ri retitled this revision from Add parallel loop coalescing. to [MLIR] Add parallel loop coalescing..Mar 18 2020, 8:51 AM

(Just some drive-by nits)

mlir/include/mlir/InitAllPasses.h
115

Let's keep these sorted.

mlir/include/mlir/Transforms/LoopUtils.h
229

Can you please add a comment here?

mlir/lib/Transforms/ParallelLoopCoalescing.cpp
23 ↗(On Diff #251099)
mlir/lib/Transforms/Utils/LoopUtils.cpp
976–983

nit: Use /// for top-level comments

1000–1001

nit: Please drop all trivial braces.

1032

nit: Please use /// for top-level comments.

1119

nit: Cache the end iterator of the loop, and prefer pre-increment.

1152

Same here and below.

bondhugula requested changes to this revision.Mar 18 2020, 10:48 AM
bondhugula added a subscriber: bondhugula.

Could you please add a summary to the commit message - even if it's a couple of lines? On a side note, do you want to use the term 'collapse' instead of 'coalesce'? OpenMP uses collapse for such linearization, and coalesce could also imply fusion of loops, which this isn't. I do see that colaesceLoops already existed prior to this patch

mlir/lib/Transforms/ParallelLoopCoalescing.cpp
52 ↗(On Diff #251099)

List initialize?

This revision now requires changes to proceed.Mar 18 2020, 10:48 AM

Would it *please* be possible for MLIR patches to be named as such, please?

Where is this coming from?
It'd be nice to clearly understand the goal and where is it coming from. In particular I don't understand why this isn't the role of separate tooling and it has to be encoded directly in commit messages. Are we going to prefix down to the last component manually? Is something like [LLVM][Backend][X86][Register allocator] to be expected?

Could you please add a summary to the commit message - even if it's a couple of lines?

+1, we document it here: https://mlir.llvm.org/getting_started/Contributing/#commit-messages

tpopp added a comment.Mar 19 2020, 1:42 AM

Could you please add a summary to the commit message - even if it's a couple of lines?

+1, we document it here: https://mlir.llvm.org/getting_started/Contributing/#commit-messages

I'll add to the summary. Is there a reason arc diff didn't pick up my git commit message? Does it only create the summary based on the first arc diff and not any subsequent calls?

tpopp edited the summary of this revision. (Show Details)Mar 19 2020, 2:07 AM
tpopp updated this revision to Diff 251306.Mar 19 2020, 2:18 AM
tpopp marked 7 inline comments as done.

Handle formatting and naming feedback.

tpopp updated this revision to Diff 251312.Mar 19 2020, 2:41 AM

Use OptionList instead of llvm:🆑:list

herhut requested changes to this revision.Mar 19 2020, 2:49 AM

Thanks. Looks great with some nits.

mlir/lib/Transforms/ParallelLoopCoalescing.cpp
44 ↗(On Diff #251099)

Can you make this an OperationPass instead?

52 ↗(On Diff #251099)

Use llvm::SmallVector instead?

mlir/lib/Transforms/Utils/LoopUtils.cpp
979

Maybe have a little struct here instead of a tuple? Or use std::tie at use sites to improve readability.

983

Move these closer to their first use.

1006

Maybe Value newLowerBound = isZeroBased ? lowerBound : boundsBuilder.create<ConstantIndexOp>(loc, 0)?

1012

Here, too?

1050

Mega-nit: The order lower, step, upper is strange...

1138

Why not newUpperBound = cst1 here?

1154

A comment what this computes would help readability.

1158

Should this be the normalized upper bound?

1160

It would read easier for me if updating previous was also done here except for the last case. Would that make sense?

1163

Normalized here, too?

This revision now requires changes to proceed.Mar 19 2020, 2:49 AM
tpopp marked 3 inline comments as done.Mar 19 2020, 3:56 AM
tpopp updated this revision to Diff 251361.Mar 19 2020, 6:14 AM
tpopp marked 12 inline comments as done.

Handle herhut's comments and fix broken collapsing
logic that used the wrong upper bound value.

tpopp marked an inline comment as done.Mar 19 2020, 6:14 AM
tpopp added inline comments.
mlir/lib/Transforms/Utils/LoopUtils.cpp
1138

No real reason. I thought it would be easier for debugging purposes if each string of calculations is fully unconnected from other calculations.

1158

Yes

1163

Yes

tpopp marked an inline comment as done.Mar 19 2020, 6:28 AM
tpopp added inline comments.
mlir/lib/Transforms/Utils/LoopUtils.cpp
1160

I think this trades one mess for a different one because then it's just a different bounds check and not all indexing is happening at ivar_idx anymore.

tpopp updated this revision to Diff 251369.Mar 19 2020, 6:45 AM

Change loop form inside of collapsePLoops.

tpopp marked 2 inline comments as done.Mar 19 2020, 6:45 AM
tpopp added inline comments.
mlir/lib/Transforms/Utils/LoopUtils.cpp
1160

I tried to restructure it to be more readable.

tpopp updated this revision to Diff 251574.Mar 20 2020, 2:11 AM

Use correct variable to fix undefined variable error.

tpopp updated this revision to Diff 251610.Mar 20 2020, 4:46 AM

Rename variable for clang tidy reasons.

herhut accepted this revision.Mar 25 2020, 7:21 AM

Thanks.

This revision was not accepted when it landed; it landed in state Needs Review.Mar 26 2020, 1:35 AM
This revision was automatically updated to reflect the committed changes.

Could you please add a summary to the commit message - even if it's a couple of lines?

+1, we document it here: https://mlir.llvm.org/getting_started/Contributing/#commit-messages

I'll add to the summary. Is there a reason arc diff didn't pick up my git commit message? Does it only create the summary based on the first arc diff and not any subsequent calls?

I've noticed this too. It doesn't pick up subsequent commit message updates. I just manually update the commit message here when needed.

Mostly minor suggestions on readability

mlir/lib/Transforms/Utils/LoopUtils.cpp
1045

OpBuilder innerBuilder(inner.getBody()) will be sufficient.

1109

But to spell this out? PLoops -> ParallelLoops?

1130

Nit: period at the end.

mlir/test/Transforms/parallel-loop-collapsing.mlir
6–15

Can you drop the extra indent? Also VAL_0 -> C6, VAL_1 -> C7, ...?

32

Can you use more descriptive names? VAL_10 -> IV0, VAL_11 -> IV1, ...

35

Drop the additional indent between the CHECK and the string?

50

CHECK-NEXT

51–52

CHECK-NEXT

mlir/test/Transforms/single-parallel-loop-collapsing.mlir
26 ↗(On Diff #252767)

VAL_14 isn't used; no need to capture it.

32–33 ↗(On Diff #252767)

CHECK-NEXT

34 ↗(On Diff #252767)

Not needed.

35 ↗(On Diff #252767)

Drop trailing blank lines.