This is an archive of the discontinued LLVM Phabricator instance.

[mlir] Create a generic reduction detection utility
ClosedPublic

Authored by dcaballe on Sep 22 2021, 7:50 PM.

Details

Summary

This patch introduces a generic reduction detection utility that works
across different dialects. It is mostly a generalization of the reduction
detection algorithm in Affine. The reduction detection logic in Affine,
Linalg and SCFToOpenMP have been replaced with this new generic utility.

The utility takes some basic components of the potential reduction and
returns: 1) the reduced value, and 2) a list with the combiner operations.
The logic to match reductions involving multiple combiner operations disabled
until we can properly test it.

Diff Detail

Event Timeline

dcaballe created this revision.Sep 22 2021, 7:50 PM
dcaballe requested review of this revision.Sep 22 2021, 7:50 PM

Nice to see this! It's a bit weird though that Conversion depends on Analysis - looks fine for now.

Commit summary:
dialecs <-- typo

mlir/test/lib/Analysis/TestMatchReduction.cpp
23–32

Can you use an emitRemark instead? This gives you a location to anchor to and in general better output. It wasn't a good pattern that some tests started of printing out text when the information could have been emitted using emitRemark and attached to an Operation. The memref dependence analysis stuff and loop parallel marking for reference uses emitRemark.

bondhugula added inline comments.Sep 23 2021, 12:59 AM
mlir/test/lib/Analysis/TestMatchReduction.cpp
67–68

Just an ArrayRef with a drop_front() should do?

ftynse accepted this revision.Sep 23 2021, 1:23 AM
ftynse added inline comments.
mlir/include/mlir/Analysis/LoopAnalysis.h
99–100

Should combiner operations also be side effect-free?

mlir/lib/Analysis/AffineAnalysis.cpp
43–46

Nit: please drop the explicit number of stack elements from SmallVector, it is now capable of selecting one by default. We only use explicit numbers if there is a specific reason to do so.

mlir/lib/Analysis/LoopAnalysis.cpp
402

I think you can get ancestorOp as iterCarriedArgs.front().getOwner().getParent().getParentOp. This looks a bit long, but avoids the case of iterCarriedArgs not being the arguments of the block being held by ancestorOp.

This revision is now accepted and ready to land.Sep 23 2021, 1:23 AM
dcaballe edited the summary of this revision. (Show Details)Sep 23 2021, 9:40 AM
sgrechanik added inline comments.Sep 23 2021, 10:21 AM
mlir/include/mlir/Analysis/LoopAnalysis.h
115

In the future we might want to support reduction operations for which the reduced value does not exist explicitly (like a fused multiply-accumulate). I would recommend returning a bool to indicate whether reduction was detected, and making the reduced value an optional output parameter.

mlir/lib/Analysis/LoopAnalysis.cpp
467

Are there tests that will fail if this condition is removed?

dcaballe updated this revision to Diff 374724.Sep 23 2021, 9:17 PM
dcaballe marked 4 inline comments as done.
  • Addressed all the feedback.
  • Extended 'operator<<' for diagnostic printing.
  • Refactored code to a LinalgOp interface.

Nice to see this! It's a bit weird though that Conversion depends on Analysis - looks fine for now.

Yeah, I couldn't find a better place.

mlir/include/mlir/Analysis/LoopAnalysis.h
115

That's an interesting point! If we had a single fma op where only the addition part is the combiner operation in the reduction, I think some preprocessing should happen before using this utility. I don't think this utility should be responsible for, for example, splitting the fma. Returning the fma as a combiner operation would also be incorrect. In general, I think the mul+add->fma folding should be a peephole optimization that should happen later in the pipeline to avoid this kind of problems.

In any case, we can extend the utility when needed. The current version follows mostly the same API as the original utility in the Affine dialect. This is mostly a refactoring.

the combiner operation part if the combiner for the reduction? If that is the case, there

mlir/lib/Analysis/LoopAnalysis.cpp
402

I assumed ancestorOp could be a non-immediate parent but I can't think of a realistic use case for that. Ok, I'll simplify it but I'll move your suggestion to matchReduction. I'm adding a check to make sure all the combiner ops are immediately nested in this region

467

I thought it was covered by the OpenMP tests but it's not. I added a test. Thanks!

mlir/test/lib/Analysis/TestMatchReduction.cpp
23–32

Much better, thanks! I had to extend Diagnostics a bit, though .

bondhugula added inline comments.Sep 24 2021, 1:56 AM
mlir/lib/IR/Diagnostics.cpp
134

an -> a

mlir/test/lib/Analysis/TestMatchReduction.cpp
46

You can get rid of these as well? func->emitRemark.

pifon2a accepted this revision.Sep 24 2021, 7:08 AM

Thank you, Diego!

dcaballe marked 2 inline comments as done.Sep 24 2021, 10:07 AM

Thank you all! I'll commit this in a while if no more comments.

This revision was automatically updated to reflect the committed changes.