This is an archive of the discontinued LLVM Phabricator instance.

[MLIR][Affine] Add utility to check if the slice is valid
ClosedPublic

Authored by vinayaka-polymage on Mar 9 2021, 12:39 AM.

Details

Summary

Fixes a bug in affine fusion pipeline where an incorrect slice is computed.
After the slice computation is done, original domain of the the source is
compared with the new domain that will result if the fusion succeeds. If the
new domain must be a subset of the original domain for the slice to be
valid. If the slice computed is incorrect, fusion based on such a slice is
avoided.

Relevant test cases are added/edited.

Fixes https://bugs.llvm.org/show_bug.cgi?id=49203

Diff Detail

Event Timeline

vinayaka-polymage requested review of this revision.Mar 9 2021, 12:39 AM

If this change/approach is acceptable, we can also change ComputationSliceState::isMaximal() to use the set difference the other way (source - slice), reusing these computations.

Thanks for fixing this bug, Vinayaka! The direction looks good to me. Adding some comments.

If this change/approach is acceptable, we can also change ComputationSliceState::isMaximal() to use the set difference the other way (source - slice), reusing these computations.

That sounds great! We could refactor the code to utilities that would serve both cases, depending on the order of the inputs. I wonder if the fast checks that we introduced for isMaximal (isSliceMaximalFastCheck) would also be applicable to isSliceValid. If so, we should be able to refactor all the code!

mlir/lib/Analysis/Utils.cpp
68

please, add message to the assert.

215

My English probably falls short here :). For my education, is determinastically ok? or should it be deterministically?

220

This looks good to me! For the isMaximal method we implemented a fast check (isSliceMaximalFastCheck) to avoid the Presburger computation for trivial cases, since it's very expensive. The fast check ended up covering the vast majority of the cases. Could we please do something similar here?

254

Could you please also dump a small comment before each constraint set so that we can easily identify them?

961

nit: drop braces

mlir/lib/Transforms/Utils/LoopFusionUtils.cpp
531

is there an API to check this instead of creating a null AffineMap? Maybe !map?

mlir/test/Transforms/loop-fusion-slice-computation.mlir
70

These remarks are no longer needed because we now bail out before they are emitted? Would it possible to emit a new remark for cases where the slice is invalid and update the remarks instead of removing them?

mlir/test/Transforms/loop-fusion.mlir
3083

Adding a comment about what is the resulting slice and why is invalid would be very useful.

sgrechanik added inline comments.Mar 10 2021, 2:55 PM
mlir/lib/Analysis/Utils.cpp
960

Shouldn't we conservatively assume that the slice is invalid if we cannot determine if it's valid here (and return failure())?

Addressing easy comments and suggestions, some important ones
still pending.

vinayaka-polymage marked 5 inline comments as done.Mar 11 2021, 1:31 AM

Thanks for the review and suggestions !! I have completed the easy ones, and I will continue exploring the pending ones.

mlir/lib/Analysis/Utils.cpp
215

Your English is fine, bad typo by me :) Corrected.

220

That is crucial, thanks for pointing it out. I will definitely explore this.

960

This is an important comment, thanks for bringing this up. I have added as comments on why I went this way. But I would like to hear your and others' thoughts on this.
@bondhugula @dcaballe

mlir/test/Transforms/loop-fusion-slice-computation.mlir
70

Definitely makes sense. I will explore this.

mlir/test/Transforms/loop-fusion.mlir
3083

I have added descriptive comments as you suggested. Please review if this looks OK ?

dcaballe added inline comments.Mar 11 2021, 9:04 AM
mlir/lib/Analysis/Utils.cpp
960

Do we have many fusion tests that wouldn't be fused if we returned failure? Maybe the fast checks could also help reduce the impact on tests that wouldn't be fused and we could be more conservative here and return failure?

mlir/lib/Analysis/Utils.cpp
960

About the first question:
In loop-fusion.mlir, test case @fuse_symbolic_bounds is an example that would fail. It currently results in fusion when -affine-loop-fusion=fusion-maximal is used. I think, this is because fusion profit computing utilities do not work with symbolic bounds well either.
About the second suggestion:
Yes, fast checks should be designed keeping such cases in mind. Then, returning failure in undetermined cases makes sense.

bondhugula requested changes to this revision.Mar 12 2021, 8:56 PM
bondhugula added inline comments.
mlir/lib/Analysis/Utils.cpp
220

Agree with @dcaballe here. It's key to have a fast check for the simpler cases which are going to be a vast majority. Being an upstream pass, speed is quite important here. One can of course later create versions that handle more complex/advanced cases as needed but those may not be on the default/standard path/pass.

This revision now requires changes to proceed.Mar 12 2021, 8:56 PM

Some minor comments.

mlir/include/mlir/Analysis/Utils.h
95–99

All of these should have been triple /// comments. I believe doxygen won't pick them up otherwise.

119

Likewise.

mlir/lib/Analysis/Utils.cpp
959

undetermined -> indeterminate

Added back the slice computation remarks in tests, marked them incorrect slices.
Added a fast check, reused the utility - isSliceMaximalFastCheck.

vinayaka-polymage marked 2 inline comments as done.Mar 27 2021, 3:43 AM

I have addressed the remaining comments:

  1. Instead of not printing the slice at all if it is incorrect, this change prints them but with a remark : "Incorrect slice" during testing.
  2. Fast check is being done, and is reusing the bounds checking utility function isSliceMaximalFastCheck. I have verified that with today's test file loop-fusion.mlir, of 156 calls to isSliceValid, 107 calls are returned after the this fast check itself.

Please review.

mlir/lib/Analysis/Utils.cpp
220

Done. Reused fast check isSliceMaximalFastCheck that verifies slice and destination bounds.

960

This is done.

mlir/test/Transforms/loop-fusion-slice-computation.mlir
70

New remarks added.

Looks great with the fast check. Relatively minor comments.

mlir/include/mlir/Analysis/Utils.h
57

exit statuses -> result statuses?

99

MLIR later changed to pass by reference for output parameters if the parameters are never going to be null. So, FlatAffineConstraints &cst. Some of the older methods are only updated when they are touched again.

124

Nit: slice -> the slice

128

This TODO has already been addressed?

mlir/lib/Analysis/AffineStructures.cpp
2132

that the source loop

2141

No else after return. Please see the auto warnings.

mlir/lib/Analysis/Utils.cpp
67

Pass by reference.

231

return true;

242

Nit: > 0

bondhugula accepted this revision.Mar 30 2021, 7:04 AM
This revision is now accepted and ready to land.Mar 30 2021, 7:04 AM

Addressing recent comments, minor.

vinayaka-polymage marked 9 inline comments as done.

Addressing minor comments.

vinayaka-polymage marked 7 inline comments as done and an inline comment as not done.Mar 31 2021, 2:51 AM

Recent suggestions incorporated. I have asked for clarification on one comment.

mlir/lib/Analysis/AffineStructures.cpp
2141

This else is functional, and cannot be removed because of the nesting, right ?

bondhugula accepted this revision.Apr 1 2021, 2:05 AM
bondhugula added inline comments.
mlir/lib/Analysis/AffineStructures.cpp
2141

Sorry, I missed that.

This revision was automatically updated to reflect the committed changes.