This is an archive of the discontinued LLVM Phabricator instance.

[mlir] Add redundant copy removal transform
ClosedPublic

Authored by dfki-ehna on Jun 29 2020, 4:12 AM.

Details

Summary

This pass removes unnecessary copy operations in the following scenario which is useful for removing the redundant copy operations created by the Buffer Placement.

%from = ...
...
%to = ...
... (no user for %to)
copy(%from, %to)
... (no user for %from)
dealloc %from
...
use(%to)

Diff Detail

Event Timeline

dfki-ehna created this revision.Jun 29 2020, 4:12 AM

@dfki-ehna Thank you!

mlir/lib/Dialect/Linalg/Transforms/CopyRemoval.cpp
30

please, remove /// ... lines. I don't think that they add a lot here. It should be obvious that there are operations in-between.

59

nit: this empty line is not needed.

75

Operation* toFreeingOp = FindDeallocation(from.getUsers());

and the corresponding private method.

77

redundant comment.

79

redundant comment.

81

redundant comment.

85

redundant comment.

90

just curious, if there is a nicer way to put 4 elements in the set. Also it probably should be SmallDenseSet.

herhut added inline comments.Jun 29 2020, 9:07 AM
mlir/lib/Dialect/Linalg/Transforms/CopyRemoval.cpp
70

What happens if there are multiple de-allocation nodes? Something could be allocated in block A, and then flow into B and C where it gets de-allocated. I don't think we create this yet but your rewrite needs to handle this.

90

Also, as it is just 4 of them, you could pointer compare.

111

This gets more complicated with aliasing. You could have something like

%1 = alloc
%2 = memref_cast %1 /// This aliases %1 as %2
%3 = copy(%1)
write_to(%2)
read_from(%2)
free(%1)

At least leave a TODO. It would be safer to disallow any operation with memory effects between the copy and dealloc.

rriddle added inline comments.Jun 29 2020, 11:10 AM
mlir/lib/Dialect/Linalg/Transforms/CopyRemoval.cpp
16

nit: This include isn't necessary.

73

nit: llvm::is_contained

103

isBeforeInBlock asserts that the operations are within the same block, is this guaranteed here?

mehdi_amini added a comment.EditedJun 29 2020, 9:46 PM

Can this pass be made to not be Linalg-specific?
Can you clarify the restriction on it and when is it safe or not to use?

dfki-ehna updated this revision to Diff 274461.Jun 30 2020, 7:06 AM

Comments are addressed.

dfki-ehna marked 16 inline comments as done.Jun 30 2020, 7:24 AM

@mehdi_amini Is there any generic copy interface available? The other problem would be in test files that how we can specify the copy operation class for the pass. @herhut suggested that since it is going to be a dialect independent and unique copy at the end, we can start with linalg.copy and generalize it later on.
In summary, what we'd like to achieve is to remove %to value and the Copy operation, and replace all its uses with %from value. In both of these examples, if we remove %to and the copy operation, and replace it with %from, the logic of the program will change.

There are users or aliases of %to between the allocation of %to and CopyOp:
%from = alloc()
in_place_changes_to(%from)
%to = alloc()
in_place_changes_to(%to)
%1 = exp(%to)
%2 = exp(%from)
copy(%from, %to)
dealloc(%from)
%3 = exp(%to)

There are users or aliases of %from between CopyOp and the deallocation of %from:
%from = alloc()
%to = alloc()
in_place_changes_to(%from)
copy(%from, %to)
in_place_changes_to(%to)
%1 = exp(%to)
%2 = exp(%from)
dealloc(%from)
%3 = exp(%to)

We capture both of these cases to not to change the IR.

mlir/lib/Dialect/Linalg/Transforms/CopyRemoval.cpp
90

I Initialized the SmallDenseSet instead of inserting them into it.

103

Yes, line 86 to 90 guarantees that they are in the same block.

111

Added another check "hasMemoryEffectOp" beside checking "hasUsers".

dfki-ehna updated this revision to Diff 274710.Jul 1 2020, 1:07 AM
dfki-ehna marked 3 inline comments as done.

Address the multiple deallocation issue.

dfki-ehna marked 3 inline comments as done.Jul 1 2020, 1:11 AM
dfki-ehna added inline comments.
mlir/lib/Dialect/Linalg/Transforms/CopyRemoval.cpp
70

Thanks for catching this. Fixed and an extra test case was added.

103

I misunderstood your point. I added an extra condition for checking if the user operations are also in the same block as the start and end operations. Thanks.

dfki-ehna updated this revision to Diff 274806.Jul 1 2020, 7:40 AM
dfki-ehna marked an inline comment as done.

Add another copy removal condition and a few more test cases.

herhut accepted this revision.Jul 2 2020, 5:17 AM

Thanks, please address comments and land.

mlir/include/mlir/Dialect/Linalg/Passes.td
15

nit: drop the the

mlir/lib/Dialect/Linalg/Transforms/CopyRemoval.cpp
68

Maybe SmallPtrSet?

100

Maybe call this ReuseCopySourceAsTarget? Not sure that is much better but it improves on case1.

150

Maybe call this ReuseCopyTargetAsSource?

mlir/test/Dialect/Linalg/copy-removal.mlir
31

I think a CHECK-NOT cannot bind a variable anyway, so why not just use {{.*}} instead of PERCENT10?

82

CHECK-SAME?

83

CHECK-NEXT here to ensure nothing else is left?

103

If you want to make sure there is nothing else in the function, use CHECK-NEXT. Otherwise matching the constant does not provide value.

This revision is now accepted and ready to land.Jul 2 2020, 5:17 AM

@mehdi_amini Is there any generic copy interface available?

In general, we create interfaces when we create the first pass that needs it. This seems like a good time to do this.

The other problem would be in test files that how we can specify the copy operation class for the pass.

Not sure I understand: we have the test dialect where you can add a copy operation implementing the interface, and you can also just add the interface to the Linalg copy.

@herhut suggested that since it is going to be a dialect independent and unique copy at the end, we can start with linalg.copy and generalize it later on.

This is a fine strategy *if this is simpler*. I am not convinced you're making any simplification by doing this: you're increasing the review load and the churn and overall this is slowing down the development.
Can you look into adding an interface? This seems like a fairly easy addition to me.

dfki-ehna updated this revision to Diff 275364.Jul 3 2020, 4:38 AM

The following points are addressed:

  • The remaining comments are resolved.
  • CopyOpInterface is introduced and added to linalg.copy.
  • Make this pass generic for all copies.
  • The pass is moved to mlir/lib/transforms.
  • copy-removal.mlir is moved to mlir/test/transforms.
dfki-ehna retitled this revision from [mlir][linalg] Add redundant copy removal transform to [mlir]Add redundant copy removal transform.Jul 3 2020, 4:40 AM
dfki-ehna edited the summary of this revision. (Show Details)
dfki-ehna retitled this revision from [mlir]Add redundant copy removal transform to [mlir] Add redundant copy removal transform.
dfki-ehna marked 8 inline comments as done.Jul 3 2020, 4:47 AM
herhut accepted this revision.Jul 3 2020, 6:08 AM

Thanks!

This revision was automatically updated to reflect the committed changes.
rriddle added inline comments.Jul 6 2020, 6:43 PM
mlir/lib/Transforms/CopyRemoval.cpp
22 ↗(On Diff #275386)

nit: Add a newline before this line.

47 ↗(On Diff #275386)

nit: Use isa<> if you aren't using the result.

70 ↗(On Diff #275386)

nit: This seems extremely inefficient. Can you just grab the first block and check to see if any of the others don't match?

100 ↗(On Diff #275386)

Please fix the case of this function, it should be camelCase

150 ↗(On Diff #275386)

Same here.

173 ↗(On Diff #275386)

nit: Can you move the public section to the top?

@rriddle Thanks for the comments. They will be fixed in the upcoming PR for the copy removal.