This is an archive of the discontinued LLVM Phabricator instance.

[Canonicalize] Reapply logic to suppport operating top-down on the initial pass, NFC.
ClosedPublic

Authored by lattner on May 8 2021, 5:27 PM.

Details

Summary

This adds all the support for top-down traversals and constant prefolding that was
reverted in this patch:
https://reviews.llvm.org/D99329

This has two changes from the previous patch:

  1. It disables the 'processExistingConstants' prefolding call when doing a bottom-up traversal.
  2. It defaults applyPatternsAndFoldGreedily to bottom-up traversal instead of top-down.

The consequence of these two changes is that there is *no behavior change* from this
patch. We can stage in the new behavior on a case by case basis over time.

Diff Detail

Event Timeline

lattner created this revision.May 8 2021, 5:27 PM
lattner requested review of this revision.May 8 2021, 5:27 PM
lattner added a comment.EditedMay 8 2021, 5:32 PM

FWIW, the change to the testsuite isn't necessary. I am not sure how to retroactively drop them from the patch, but if someone wants that and can help me with the right arc/git command then i'd be happy to do so!

> Done.

lattner updated this revision to Diff 343873.May 8 2021, 5:35 PM

Microoptimize patch to reduce out a few comment deltas

lattner updated this revision to Diff 343875.May 8 2021, 5:38 PM

Remove the testcase changes, further tweeze out spurious comment change.

There are two changes here: the option to change the (initial) traversal order and the constant materialization change, can you split the constant materialization in a follow up patch?

mlir/include/mlir/Transforms/GreedyPatternRewriteDriver.h
48

Can you update the doc?

Yes, I can split it if there is a good reason to. This patch was approved before, why does it need to be split now? This seems like needless work.

I'll update PatternRewriter.md, thanks for remembering that!

lattner updated this revision to Diff 343878.May 8 2021, 6:21 PM

Document the new argument to applyPatternsAndFoldGreedily in both comments and markdown dox.

jpienaar added inline comments.
mlir/include/mlir/Transforms/FoldUtils.h
37

Wouldn't DialectFoldInterface::shouldMaterializeInto affect where these get moved to rather than always to entry?

I have no idea what shouldMaterializeInto is about. I see the comment in FoldInterfaces.h but it doesn't make much sense to me, and there are no clients of this in tree.

Can you give a concrete example of when this gets used?

I have no idea what shouldMaterializeInto is about. I see the comment in FoldInterfaces.h but it doesn't make much sense to me, and there are no clients of this in tree.

Can you give a concrete example of when this gets used?

It is used in the test dialect as an example.
In general this allows to decouple the "IsolatedFromAbove" property from the point of insertions for constants.
For example you may have something like:

func @foo() {
  ...
  // not isolated from above
  remote.dispatch() {
     ...
     op.fold() ... // Folding this op, we want the constant to be created in the `remote.dispatch` region and not in the parent region.
    ..
  }
  ...
}

The logic is in lib/Transforms/Utils/FoldUtils.cpp getInsertionRegion(). When folding op.fold() above, it'll walk the parent ops until it finds an "IsolatedFromAbove" operation or one that implement this interface.

bondhugula added inline comments.May 13 2021, 11:09 PM
mlir/docs/PatternRewriter.md
255–257

As far as the hierarchy goes, the traversal is actually pre order in both cases. (Parents are visited before children in the existing scheme and in the one you are adding.) Within a block, the old one is doing bottom up and the one being added is doing top down. This description needs an update? Perhaps you could just drop "post-order" and instead mention that parent ops are processed before child ops in both cases?

lattner added inline comments.May 15 2021, 3:47 PM
mlir/include/mlir/Transforms/FoldUtils.h
37

This implementation already handles DialectFoldInterface::shouldMaterializeInto correctly because it uses getInsertionRegion which handles it. I'll update the commend and add a testcase to show this.

lattner updated this revision to Diff 345655.May 15 2021, 3:53 PM

Update the comment to make it more clear that the logic obeys the
'shouldMaterializeInto' hook.

Add a command line flag for canonicalize that enables the new behavior

Add a testcase showing that we don't hoist constants out of a
test.one_region_op, which implements the shouldMaterializeInto hook.

Ok, I think this is really really ready to land as a staging patch. As a reminder, this does not change behavior of any passes in tree or out of tree. This is intended to get the logic into the MLIR repo, so we can gently adopt it in the ecosystem over time. Can I get a LGTM please?

lattner updated this revision to Diff 345656.May 15 2021, 3:57 PM

Clarify the documention as Uday suggests, thanks!

bondhugula requested changes to this revision.EditedMay 15 2021, 11:26 PM

Looks good to me in general, but several comments and some potential minor improvements.

mlir/docs/PatternRewriter.md
255

It's "pre-order over the region tree" because the old scheme is doing post-order + reverse which would be pre-order since this is a directed tree. With the new scheme, you are doing pre-order + reverse + reverse, which is again pre-order. The original traversal is post order but since the rewriter is popping from the end, we might refer to the combined thing here?

mlir/include/mlir/Transforms/GreedyPatternRewriteDriver.h
42–44

Update here.

-> walks the operations in a block top-down

-> When set to false, operations in a block are processed bottom-up, which may match ....

?

mlir/include/mlir/Transforms/Passes.td
367 ↗(On Diff #345656)

The convention for cmd-line option names isn't camel case I think - just hyphen separated. "enable" can be dropped as well.

enableTopDown -> top-down ?

369 ↗(On Diff #345656)

-> `Process operations in a block top-down" ?

mlir/lib/Transforms/Utils/FoldUtils.cpp
97

auto -> ConstantMap.

102

You can easily make this return true when the op is erased - and let the subsequent walk go ahead if the op isn't erased. It is rare though that a constant op has a region, but no harm in that walk continuing.

104

Assert on single result for op?

123

This can be simplified into a single comparison. You don't need the constantIterator == insertBlock.end() part. If constantIterator is at the end, then it won't be equal to op. So,

if (constantIterator != Block::iterator(op))

?

129

Comment here please.

135

Side comment: even if you didn't delete it, a constant op will probably never have regions!

You can make processConstant return true/false and let the walk continue?

139

Nit: This comment doesn't seem to match logic below.

is isolated -> has a different region to insert constants into

The op may or may not be isolated.

340–342

auto -> Operation please.

mlir/lib/Transforms/Utils/GreedyPatternRewriteDriver.cpp
140

-> ... for operations in a block.

mlir/test/Transforms/canonicalize-td.mlir
5 ↗(On Diff #345656)

TD-LABEL:
BU-LABEL:

9 ↗(On Diff #345656)

BU -> BU-NEXT?

24 ↗(On Diff #345656)

Same here. This isn't really being looked at by FileCheck?

26 ↗(On Diff #345656)

BU -> BU-NEXT?

29 ↗(On Diff #345656)

TD -> TD-NEXT?

This revision now requires changes to proceed.May 15 2021, 11:26 PM
lattner marked 16 inline comments as done.May 16 2021, 9:50 AM

Thank you for the feedback Uday, incorporated. At this point, this patch has been thoroughly nit-picked. I plan to land it tomorrow and we can continue to iterate in tree, thanks.

mlir/docs/PatternRewriter.md
255

It is worse than this. The original order is extremely hard to describe because of this code that it is using:

template <WalkOrder Order = WalkOrder::PostOrder, typename FnT,
          typename RetT = detail::walkResultType<FnT>>
typename std::enable_if<std::is_same<RetT, void>::value, RetT>::type
walk(FnT &&callback) {
  for (auto &block : *this)
    block.walk<Order>(callback);
}

It is calling it with the default post-order traversal, but notice that it walks the blocks in the region in-order! I will generalize the writing because it isn't the point of this to go into all the details, this is an overview doc.

mlir/include/mlir/Transforms/GreedyPatternRewriteDriver.h
42–44

tweaked again, generalizing the claim. The old walk isn't principled as mentioned above.

mlir/include/mlir/Transforms/Passes.td
367 ↗(On Diff #345656)

Right, thanks

369 ↗(On Diff #345656)

Made more pedantically correct.

mlir/lib/Transforms/Utils/FoldUtils.cpp
97

No. This is following the convention of the file.

102

I think this approach is ok.

123

Nice improvement, yes.

139

I only just recently learned about this distinction. I will fix.

340–342

I'm changing this, but this has nothing to do with my patch. I don't think it is good form to try to impose your opinion of auto on patches touching general code like this.

mlir/test/Transforms/canonicalize-td.mlir
5 ↗(On Diff #345656)

nice catch thx

24 ↗(On Diff #345656)

No this is being ignored.

lattner updated this revision to Diff 345713.May 16 2021, 9:51 AM
lattner marked 10 inline comments as done.

Incorporate feedback from Uday

bondhugula accepted this revision.May 16 2021, 7:49 PM
bondhugula added inline comments.
mlir/docs/PatternRewriter.md
259

Typo: "is may"

mlir/lib/Transforms/Utils/FoldUtils.cpp
340–342

All your changes to this method have nothing to do with this patch - in that spirit, I just pointed this out since I felt it improved readability further.

This revision is now accepted and ready to land.May 16 2021, 7:49 PM
lattner updated this revision to Diff 345912.May 17 2021, 9:39 AM

One more typo

Thank you for the review Uday!

lattner closed this revision.May 17 2021, 11:20 AM

Landed in 648f34a2840b thanks all