Introduction
We propose to introduce arithmetic, logical and comparison expression into PDLL
to enable writing patterns like
Pattern {
let root = op<my_dialect.foo> {shift = val: Attr} (inputOp: Value);
let doubled = val * attr<"2 : i32">;
doubled >= attr<"10 : i32">;
rewrite root with {
let newOp = op<my_dialect.bar> {upper_bound = -doubled} (inputOp) -> ();
replace root with newOp;
}
}
Motivation
We use PDLL a lot for pattern matching.
One of the use cases is matching parts of the IR into hand-optimized
kernels and configuring them appropriately.
We are generally happy with its precise language and we have made heavy use of
defining our own native constraints/rewrites to extend the capabilities of the language, e.g. when checking and transforming attributes.
Since a few weeks, native constraints can return results, which allows to break up monolithic native constraints (like isSumGreaterThan) into more atomic expressions (like add and greater_than).
We would like to move those into the core PDL language to make writing PDLL
patterns easier, improve readability and make them less dependent on a large
set of custom native constraints/rewrites.
Proposal
We propose to add arithmetic, logical and comparison operators with their usual representation into PDLL. As an example, let’s discuss the addition operator +.
The expression a + b requires a and b to be of type Attr.
It produces a result of type of type FailureOr<Attr>.
When the expression is evaluated at runtime, we perform the following legality checks
- both
aandbneed to beIntegerAttror bothaandbneed to beFloatAttr - their types (as given by
Attribute.getType()) are the same.
Then we perform the addition, failing if an overflow occurs.
If any of the legality checks or the addition itself fails,
- and the expression is in a constraint section, the constraint fails to match.
- and the expression is in a rewrite section, the rewrite is aborted and rolled-back (if possible).
We would like to disallow arithmetic operations as toplevel expression, i.e. make
Pattern {
...
val + attr<"2 : i32">; // arithmetic as toplevel expression - disallowed
syntactically illegal, and only allow comparison and logical operators there:
Pattern {
...
let a = val + attr<"2 : i32">; // `let` as toplevel expression - allowed
val < attr<"2 : i32">; // comparison operator - allowed
boolval && attr<"1 : i1">; // logical operator - allowed
When comparison and logical operators (those result in FailureOr<IntegerAttr> with type i1) appear as toplevel expressions in a constraint section, the constraint only matches if both the operation succeeded and the returned attribute is 1 : i1 (i.e. true).
Design alternatives / options
Type promotion
Instead of requiring the types of the left-hand-side and right-hand-side in binary operators to match, we could instead go for type promotions. At this stage we don’t see much benefit from it, but developers would need to learn the promotion rules to understand the constraint matching correctly.
This could be lifted at a later time if necessary.
Allow arithmetic operations on toplevel
We could make
Pattern {
...
val + attr<"2 : i32">;
legal by discarding the result of the addition and make the constraint match if val is an IntegerAttr of type i32 and the addition doesn’t overflow.
To avoid the ambiguity with the interpretation in the next section, we prefer making this illegal and requiring let unused = val + attr<"2 : i32">; instead.
Convert Attr values on toplevel into match failures
We could give
Pattern {
...
val + attr<"2 : i32">;
the meaning of “match whenever val + 2 is not zero”.
More formally, when the toplevel expression’s result type in a constraint section is FailureOr<Attr>, we could consider the constraint to match when the result is not a failure and the attribute value, converted to boolean, is true.
To avoid the ambiguity with the interpretation in the previous section, we prefer making this illegal and require an explicit comparison, i.e. val + attr<"2 : i32"> != attr<"0 : i32">; here.
Implementation
On the PDLL parser, we have a pretty straightforward implementation of this proposal.
For the representation of the operators in PDL, we see the following options, where we have prototyped A (see here and here).
A) Builtin native calls
We can make use of the native constraints/rewrites pdl ops, and turn operations like + into
calling builtin native calls pdl.apply_native_constraint "__builtin_addConstraint"(%a, %b).
This allows to keep the PDL dialect and their consumers (Bytecode interpreter) unchanged.
MLIR can ship with those builtin native calls, which are automatically declared in the PDLL parser, and have their definitions automatically available in the PDL bytecode interpreter.
B) Define new PDL ops
Introduce new ops into the PDL dialect, either
one per operations (like pdl.add %a, %b) or one for all expressions (like pdl.attr_expr add, %a, %b). Introduce the same ops into the PDLInterp dialect.
The PDLL parser would emit the corresponding PDL op for each expression,
the PDLToPDLInterp pass lowers those into pdl_interp. The bytecode
generator turns those into new bytecode ops, and the bytecode interpreter learns
to interpret those.
(B) requires more changes and we don’t
see much gain from it, assuming that the compiler will likely handle those as
constraints/rewrites in an opaque way.
Thus we think that the tradeoffs are in favor of (A).
Future work
Other PDLL extensions we have prototyped/looked into are syntax for creating
and manipulating ArrayAttr and DictionaryAttr. Those follow a similar
implementation, but are not part of this RFC.
Request for comments
What do you think? We love to hear your comments.
I’m currently at EuroLLVM, love to talk to you there, too!
For visibility: @Mogball @martin.luecke