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

Unit TestsFailed

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
114 ↗(On Diff #251099)

Let's keep these sorted.

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

Can you please add a comment here?

mlir/lib/Transforms/ParallelLoopCoalescing.cpp
24
mlir/lib/Transforms/Utils/LoopUtils.cpp
976–980

nit: Use /// for top-level comments

998–1000

nit: Please drop all trivial braces.

1034

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

1120

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

1153

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
53

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
45

Can you make this an OperationPass instead?

53

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?

1052

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

1139

Why not newUpperBound = cst1 here?

1155

A comment what this computes would help readability.

1159

Should this be the normalized upper bound?

1161

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

1164

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
1139

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

1159

Yes

1164

Yes

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

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
1161

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
1047

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

1110

But to spell this out? PLoops -> ParallelLoops?

1131

Nit: period at the end.

mlir/test/Transforms/parallel-loop-collapsing.mlir
5–14 ↗(On Diff #252767)

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

31 ↗(On Diff #252767)

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

34 ↗(On Diff #252767)

Drop the additional indent between the CHECK and the string?

49 ↗(On Diff #252767)

CHECK-NEXT

50–51 ↗(On Diff #252767)

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.