[PDL] Some thoughts on the evolution of PDL

MLIR
1

There is a (relatively) recent set of patches aimed to introduce commutative matching in PDL. I have some concerns about the implementation, especially the ability of the bytecode to explode with the number of permutations, but I’m more worried about introducing “excessively powerful” bytecode instructions to implement higher-level constraints.

For example, the existence of a for_each loop, introduced by @sfuniak in the multi-root pattern implementation, I’m concerned sets a precedent. I’m not against a for_each loop itself, but I didn’t like that it was used to “traverse” down the IR by iterating over all users. Downward traversals in pattern matching is very unnatural. I didn’t have a strong opinion at the time because I didn’t have an alternative solution handy for implementing multi-root patterns. But recently I’ve wondered whether all multi-root patterns can be implemented as a sequence of single-root patterns. Let’s say I want to rewrite:

%a = "test.a" : () -> i32
%b = "test.b"(%a) : (i32) -> i32
%c = "test.c"(%a) : (i32) -> i32
"test.sink"(%b, %c) : i32, i32

To:

%foo = "test.foo"() -> i32
test.sink(%foo, %foo) : i32,i32

I can use a multi-root pattern

pdl.pattern {
  %type
  %a = operation "test.a" -> (%type: !pdl.type)
  %a_0 = result 0 of %a
  %b = operation "test.b"(%a: !pdl.value) -> (%type: !pdl.type)
  %c = operation "test.c"(%a: !pdl.value) -> (%type: !pdl.type)
  rewrite {
    %foo = operation "test.foo" -> (%type: !pdl.type)
    replace %b with %foo
    replace %c with %foo
    erase %a
  }
}

Or a sequence of single-root patterns (with assistance from DialectConversion):

pdl.pattern @one {
  %type = type
  %a = operation "test.a" -> (%type: !pdl.type)
  %a_0 = result 0 of %a
  %b = operation "test.b"(%a: !pdl.value) -> (%type: !pdl.type)
  rewrite {
    %placeholder = operation "test.placeholder" -> (%type: !pdl.type)
    replace %a with %placeholder
    replace %b with %placeholder
  }
}
pdl.pattern @two {
  %type = type
  %placeholder = operation "test.placeholder" -> (%type: !pdl.type)
  %a_0 = result 0 of %placeholder
  %c = operation "test.c"(%a: !pdl.value) -> (%type: !pdl.type)
  rewrite {
    %foo = operation "test.foo" -> (%type: !pdl.type)
    replace %c with %placeholder
    replace %placeholder with %foo
  }
}

Where I’ve marked test.placeholder as illegal. On a side note, what are the chances that the DialectConversion rollback mechanism can be exposed as a utility for writing more complex drivers? @River707 (Also there are some bugs with using PDL together with DialectConversion)

By the same token, the permutation in implementing commutative patterns can be achieved by permuting all the n! patterns instead (with the same rewrite function). And I wonder whether multi-root patterns in general and commutative patterns could be implemented as PDL to PDL rewrites.

I think the roles of PDLInterp and the bytecode have been misunderstood a little. PDL was from the start an attempt to use compiler techniques to implement an efficient (and dynamic) pattern rewrite system. PDLToPDLInterp is a kind of specialized CSE for match constraints. Part of the misunderstanding I’m inclined to believe is my fault. There is a hidden abstraction layer between PDL and PDLInterp (the position/predicate nodes), and because it’s not represented as a dialect, it’s been overlooked.

PDL was designed with performance primacy; consequently, the solution to adding new, powerful features to PDL is not to add new, powerful bytecode ops but to think about what kinds of transformations we can apply to PDL/PDLInterp to make it happen and what new fundamental bytecode operations we might need. Do we need a for_each op? Do we need function calls (e.g. PDLInterp outlining)? Can we implement a pattern scheduling language on top of PDL (e.g. allowing rewrites to “call” patterns with rollback)?

For example, the approach to implementing branches in PDL patterns would be to flatten them and let PDLToPDLIntern CSE the constraints later.

PDLL has a growing wishlist of features that don’t exist natively in PDL, so I think this something important to think about.

2

Thanks for starting the discussion @Mogball !

Where is the test.placeholder operation coming from here? Realistically, users should not need to create temporary operations to stitch together pattern fragments.

I would be wary here to not overgeneralize. PDL is intended to provide an abstract model for presenting pattern rewrites using MLIR. Performance is an obviously a highly important aspect of that, but that is only one aspect. If a new power bytecode op is required to make a specific construct more easily expressed, and more optimally expressed, we should be open to adding it. There is of course a trade off in the design space on how to implement specific features, but the bytecode can and will grow more powerful operations when necessary.

– River

3

Users will still write multi-root patterns. PDL would take these multi-root patterns and “lower” them to a sequence of patterns connected by, for example, temporary operations. This would be an automatic process.

I was trying to distinguish between “power” ops vs. “fundamental” ops. I want to introduce the dimension of PDL-to-PDL rewrites or transformations on the (currently hidden) predicate representation as a method of implementing features, rather than relying by-default on adding new opcodes.

4

Can you file an issue for these? I assume some of these are attempted uses of PDL patterns as ConversionPatterns, which they aren’t(e.g. they won’t use remapped operands). Those situations aren’t necessarily bugs in PDL, more of missing features.

Kind of with the previous point. We should definitely look at each individual feature request that wants to extend the representation with a heavily lens of scrutiny, but we should definitely be open to expanding the representation when it is beneficial.

This is quite dangerous. The concept of creating a temporary operation is something we should avoid in nearly all situations, for a myriad of reasons. You either need the user to define a temporary operation (that is often otherwise unnecessary), or you need one that is somehow always available (which is why we ended up creating builtin.unrealized_conversion_cast for type conversions). Even then it assumes a very specific driver model (how well does this work with canonicalization?). We should realistically be able to support most things that can be done naturally within a C++ pattern with as little convolution as possible. We have a lot of freedom when it comes to how we actually lower the PDL that we are given, but temporary operations/pattern stitching/etc. can often permeate expectations into the pattern driver being used.

Right, and I think that is a great distinction to make. My point is that the set of “fundamental” operations that we define do not necessarily have to be at the same level of abstraction/granularity. There is freedom there to define the abstractions that are most important for expressability/performance/etc. (which is definitely something good to have a heavy bit of scrutiny on).

– River

5

This was a bit of a bad example because it’s not something that can be supported with just PDL-to-PDL transformations (commutative patterns could be). The DialectConversion rollback system would need to be a permanent fixture of PDL patterns to make it independent of the pattern driver. Since it touches on pattern rewrites in MLIR in general, implementing multi-root patterns this way is out-of-scope for a discussion on just PDL. I wanted to focus on the idea of using PDL-to-PDL rewrites to potentially implemented more powerful features.

6

Should clarify that the rollback system would need to become a permanent fixture of all patterns to be able to rely on it in PDL. PDL patterns (like C++ patterns) delegate to the PatternRewriter, which could be implemented in any number of ways. (I think this is what you meant given the last sentence, just wanted to clarify for others reading that we can’t do rollbacks solely in PDL).

Right. Very strong +1 here. We should always be considering these types of things with new features.

– River

7

What would be your opinion on introducing layer between PDL and PDLInterp? I want to reify the hidden layer of positions and predicates that PDL patterns pass through before becoming PDLInterp.

8

It really depends on how that layer is structured, the purpose it serves and the complexity involved (e.g. adding a layer already adds in another conversion). I don’t want to add layers just to add layers, if we add something it has to be a proper abstraction and have a real benefit.

– River