This is an archive of the discontinued LLVM Phabricator instance.

Multi-root PDL matching using upward traversals.
ClosedPublic

Authored by sfuniak on Aug 23 2021, 5:58 AM.

Details

Summary

This is commit 4 of 4 for the multi-root matching in PDL, discussed in https://llvm.discourse.group/t/rfc-multi-root-pdl-patterns-for-kernel-matching/4148 (topic flagged for review).

This PR integrates the various components (root ordering algorithm, nondeterministic execution of PDL bytecode) to implement multi-root PDL matching. The main idea is for the pattern to specify mulitple candidate roots. The PDL-to-PDLInterp lowering selects one of these roots and "hangs" the pattern from this root, traversing the edges downwards (from operation to its operands) when possible and upwards (from values to its uses) when needed. The root is selected by invoking the optimal matching multiple times, once for each candidate root, and the connectors are determined form the optimal matching. The costs in the directed graph are equal to the number of upward edges that need to be traversed when connecting the given two candidate roots. It can be shown that, for this choice of the cost function, "hanging" the pattern an inner node is no better than from the optimal root.

The following three main additions were implemented as a part of this PR:

  1. OperationPos predicate has been extended to allow tracing the operation accepting a value (the opposite of operation defining a value).
  2. Predicate checking if two values are not equal - this is useful to ensure that we do not traverse the edge back downwards after we traversed it upwards.
  3. Function for for building the cost graph among the candidate roots.
  4. Updated buildPredicateList, building the predicates optimal branching has been determined.

Testing: unit tests (an integration test to follow once the stack of commits has landed)

Diff Detail

Event Timeline

sfuniak created this revision.Aug 23 2021, 5:58 AM
sfuniak requested review of this revision.Aug 23 2021, 5:58 AM

Made my way through most of it, will check the rest tomorrow.

mlir/include/mlir/Dialect/PDL/IR/PDLOps.td
454

Why remove the accessor but not the rootKind argument?

622–623
mlir/lib/Conversion/PDLToPDLInterp/PDLToPDLInterp.cpp
252

Does this revision not build directly? (i.e. are you intending to land all of the commits together?)

394

Can you use a different name than nominal? Confused me for a second when I looked at this (before I saw that EqualTo also corresponds to NE).

548–549

I'm a bit apprehensive about asserting this. I intend to support return values in constraints, and that would end up with an assert here. Can we have a method somewhere that provides this functionality in a fail-able way? (i.e. if the value isn't an OperationOp return None, otherwise return op.name()).

mlir/lib/Conversion/PDLToPDLInterp/PredicateTree.cpp
171
mlir/lib/Dialect/PDL/IR/PDL.cpp
37–38

This comment needs to be tweaked a bit.

sfuniak added inline comments.Sep 27 2021, 4:24 AM
mlir/include/mlir/Dialect/PDL/IR/PDLOps.td
454

Good point, will do.

mlir/lib/Conversion/PDLToPDLInterp/PDLToPDLInterp.cpp
252

It was supposed to build directly. I separated the functionality carefully. But I stacked the commits after-the-fact, which could be the reason why clang-tidy complains. Hopefully this error will go away when I update the diff.

394

Ok, I will just use is_true.

548–549

Sure, I can do that.

sfuniak updated this revision to Diff 378560.Oct 10 2021, 8:53 PM

Migrated to pdl_interp.foreach and autodetecting roots

This update migrates the PDL-to-PDLInterp lowering to use the new ForEach construct. I have unified the generate methods and made the block passed to getValueAt mutable, so that it can insert the nested regions for each of the pdl_interp.foreach it encouters.

Finally, following the recommendations in the review, I change pdl.rewrite to accept a single optional root, which forces the root of the search tree. In the absence of this root, the lowering will choose the optimal root among the ones detected in the pattern.

Nice!

mlir/include/mlir/Dialect/PDL/IR/PDLOps.td
587–594

Can you beef the documentation on what you mean by "search tree"? It isn't clear exactly what that is supposed to mean.

mlir/lib/Conversion/PDLToPDLInterp/PDLToPDLInterp.cpp
160
170

nit: Drop the const here

221

nit: Can you add a message here?

248

Can you switch this to early exit? i.e. the else branch is smaller, so you could do:

if (!operationPos->isUpward()) {

value = ...;
break;

}

257–258

Why is this calling the create directly? as opposed to using the builder.

262–263

builder.createBlock(...)?

337

Is the 2 a tuned value? or can we just use the default inline vector size?

338–342

nit: Use braces when the body is a nested control flow statement (the one exception to that though AFAIK is for (...) if (...))

394–397

nit: Use camelCase for variable names.

466

Is this still open?

mlir/lib/Conversion/PDLToPDLInterp/PredicateTree.cpp
171

unresolved?

336–341
384–391
443
593
643

nit; Assert messages should start with lower case

646

Is this guaranteed to be non-variadic?

797–810

Thank you for the review @rriddle. Will submit an update later today.

mlir/lib/Conversion/PDLToPDLInterp/PDLToPDLInterp.cpp
257–258

Just a MLIR rookie mistake, will fix.

337

I just copied whatever was there originally at line 348. Happy to use the default.

338–342

Thanks, I was not sure what the convention was.

mlir/lib/Conversion/PDLToPDLInterp/PredicateTree.cpp
171

Your suggested change did not compile: we have only comparison between two Optionals, not an Optional and a value. And because these are templates, implicit conversion from value to Optional is not invoked.

sfuniak marked 11 inline comments as done.Oct 18 2021, 4:29 AM
sfuniak added inline comments.
mlir/lib/Conversion/PDLToPDLInterp/PDLToPDLInterp.cpp
257–258

Actually, I remember now. ForEachOp::create is a custom function that creates the entry block with a loop variable (block argument). If I use a builder, then this will invoke OpTy::build, followed by Operation::create(state), which is not what I wanted.

Or is there another, more standard way to do this?

mlir/lib/Conversion/PDLToPDLInterp/PredicateTree.cpp
646

You are right, it can be variadic. I think the entire logic will still work, but we need to tweak the implementation of pdl_interp.get_users a bit. I will include that in an upcoming update.

sfuniak updated this revision to Diff 380916.Oct 20 2021, 5:43 AM

Addressed review feedback.

rriddle accepted this revision.Oct 28 2021, 11:39 AM

Did a quick scan, looks good to land and iterate!

mlir/include/mlir/Dialect/PDL/IR/PDLOps.td
587–594

unresolved?

mlir/lib/Conversion/PDLToPDLInterp/PDLToPDLInterp.cpp
257–258

We generally just use the build methods, create methods have generally been reserved for top-level things and are generally left-over from before FuncOp/ModuleOp were operations. Can we remove ForEachOp::create and use a build method instead?

mlir/lib/Conversion/PDLToPDLInterp/PredicateTree.cpp
608–609

Can you move these inner methods to separate functions? buildPredicateList has become quite large.

mlir/test/Conversion/PDLToPDLInterp/pdl-to-pdl-interp-matcher.mlir
494

Can you add tests for when this is variadic?

This revision is now accepted and ready to land.Oct 28 2021, 11:39 AM
sfuniak updated this revision to Diff 384964.Nov 4 2021, 9:52 PM

Final review feedback; also fixed the connected component checking code.

sfuniak marked 11 inline comments as done.Nov 4 2021, 9:55 PM
Mogball added inline comments.
mlir/lib/Conversion/PDLToPDLInterp/PredicateTree.cpp
338–340

Are there going to be more cases down the line?

384

Seeing a struct def inside a loop is... weird to me. I'm not sure if LLVM's coding standards say much about where structs defined inside functions should be, but it would make more sense to me at the top of the function body.

sfuniak added inline comments.Nov 18 2021, 5:06 PM
mlir/lib/Conversion/PDLToPDLInterp/PredicateTree.cpp
338–340

No, but you need a cast to pdl::ResultOp or pdl::ResultsOp to extract the parent. The TypeSwitch approach seems cleaner.

384

No problem, I will move it.

sfuniak updated this revision to Diff 388372.Nov 18 2021, 8:17 PM

Updated code to simplified pdl_interp.get_users.

sfuniak updated this revision to Diff 388848.Nov 22 2021, 3:09 AM

Use pdl_interp.get_value for upward traversal of value ranges.

sfuniak updated this revision to Diff 389900.Nov 25 2021, 9:13 PM

Switch from pdl_interp.get_value to pdl_interp.extract.

This revision was automatically updated to reflect the committed changes.

This broke the gcc 5.4 build:

/var/lib/buildkite-agent/builds/buildkite-588bd64db9-bjm5q-1/mlir/mlir-core/mlir/lib/Conversion/PDLToPDLInterp/PDLToPDLInterp.cpp:212:36: error: cannot call member function 'void {anonymous}::PatternLowering::generate(mlir::pdl_to_pdl_interp::BoolNode*, mlir::Block*&, mlir::Value)' without object
           [&](auto *derivedNode) { generate(derivedNode, currentBlock, val); })
                                    ^
/var/lib/buildkite-agent/builds/buildkite-588bd64db9-bjm5q-1/mlir/mlir-core/mlir/lib/Conversion/PDLToPDLInterp/PDLToPDLInterp.cpp: In instantiation of '{anonymous}::PatternLowering::generateMatcher(mlir::pdl_to_pdl_interp::MatcherNode&, mlir::Region&)::<lambda(auto:16*)> [with auto:16 = mlir::pdl_to_pdl_interp::SwitchNode]':
/var/lib/buildkite-agent/builds/buildkite-588bd64db9-bjm5q-1/mlir/mlir-core/llvm/include/llvm/ADT/TypeSwitch.h:169:13:   required from 'llvm::TypeSwitch<T, void>& llvm::TypeSwitch<T, void>::Case(CallableT&&) [with CaseT = mlir::pdl_to_pdl_interp::SwitchNode; CallableT = {anonymous}::PatternLowering::generateMatcher(mlir::pdl_to_pdl_interp::MatcherNode&, mlir::Region&)::<lambda(auto:16*)>&; T = mlir::pdl_to_pdl_interp::MatcherNode*]'
/var/lib/buildkite-agent/builds/buildkite-588bd64db9-bjm5q-1/mlir/mlir-core/llvm/include/llvm/ADT/TypeSwitch.h:46:49:   required from 'DerivedT& llvm::detail::TypeSwitchBase<DerivedT, T>::Case(CallableT&&) [with CaseT = mlir::pdl_to_pdl_interp::BoolNode; CaseT2 = mlir::pdl_to_pdl_interp::SwitchNode; CaseTs = {}; CallableT = {anonymous}::PatternLowering::generateMatcher(mlir::pdl_to_pdl_interp::MatcherNode&, mlir::Region&)::<lambda(auto:16*)>; DerivedT = llvm::TypeSwitch<mlir::pdl_to_pdl_interp::MatcherNode*, void>; T = mlir::pdl_to_pdl_interp::MatcherNode*]'
/var/lib/buildkite-agent/builds/buildkite-588bd64db9-bjm5q-1/mlir/mlir-core/mlir/lib/Conversion/PDLToPDLInterp/PDLToPDLInterp.cpp:212:79:   required from here
/var/lib/buildkite-agent/builds/buildkite-588bd64db9-bjm5q-1/mlir/mlir-core/mlir/lib/Conversion/PDLToPDLInterp/PDLToPDLInterp.cpp:212:36: error: cannot call member function 'void {anonymous}::PatternLowering::generate(mlir::pdl_to_pdl_interp::SwitchNode*, mlir::Block*, mlir::Value)' without object

@mehdi_amini thanks for bringing this up; I will take a look.

rriddle added a comment.EditedNov 26 2021, 3:11 PM

@mehdi_amini thanks for bringing this up; I will take a look.

This looks like the gcc5 bug for auto lambdas that capture this, you likely just need to use this-> for member calls.