Strategy dialect for precise specification of complex rewrite rules about iree-llvm-sandbox HOT 6 OPEN

Nice!

apply/apply_dynamic seem analogous to call/call_indirect, right?

I think I see recursion being useful in cases where we write super generic stuff that targets an abstract machine model.
I also have in the back of my mind some Darkroom / Terra use cases but eventually I think the tradeoff between nesting/recursion and more structured IR design favors IR design: the apparent simplicity really gets moved to complex combinations of small things.. maybe I am diverging a bit :)
Could you share some other use cases that you could solve well thanks to recursion?

My inclination is to start without recursion and see where this brings us, as we can likely start scaling in a more naive fashion on fixed HW models. Generalization can come later.

I have a somewhat similar thinking for failures: I wonder how much "can fail" is a property of application of a complex pattern to "too low-level IR objects". Experience with the current system seems to show that our very progressive lowering approach from high-level IR allows us to not worry about rollbacks. There seems to be a connection to more static vs more dynamic programs; i.e. can you hoist all your conditions upfront or not.

I imagine we'll encounter plenty of use cases for failures as we scale up but similarly, to get off the ground, I think we can do without most of the infra complexity.

How about a proto ? :)

from iree-llvm-sandbox.

apply/apply_dynamic seem analogous to call/call_indirect, right?

Correct!

Could you share some other use cases that you could solve well thanks to recursion?

Recursion is mostly useful for expressing rewrites that need to traverse down arbitrary unknown operations, and we certainly could start without it, or only with some special forms (e.g. exhaustive greedy application like in the default driver).

I have a somewhat similar thinking for failures: I wonder how much "can fail" is a property of application of a complex pattern to "too low-level IR objects".

I think that you're right in that proper IR design can let you avoid thinking about failures in many cases, but I don't think it's always possible. Linalg might be a neat enough use-case and design such that you can get away without it, but you might run into trouble trying to scale it up to arbitrary MLIR transforms. And IMO things like loop-interchange should be also expressible as rewrites, even though this is out of scope for linalg.

How about a proto ? :)

Sounds good to me! :)

from iree-llvm-sandbox.

!strategy.strategy: Roughly represents a function with signature (!pdl.operation) -> (). Note that an application might fail which is represented as a side effect and not as a return value.

What happens if the strategy mutates the operation, or replaces it entirely? E.g.

strategy.apply @canonicalize(%op) // %op is canonicalized away/replaced
strategy.apply @myStrategy(%op)  // %op is now invalid?

I will also propose that "strategies" can return IR handles, i.e.

%tiledOp = strategy.apply @tile(%op, %tileSize) : (!pdl.operation, i64) -> (!pdl.operation)
strategy.apply @canonicalize(%tiledOp) : (!pdl.operation) -> ()

from iree-llvm-sandbox.

Extending strategies to have additional return values is definitely possible (in functional terms those would run in the Either monad, which roughly means that every strategy either succeeds with a value or fails with an error).

The question of what happens if an op is destroyed is a good one and it does tie to the difficulties around mutability. I think there are multiple ways we can potentially handling that. First, we could consider this to be a programmer error and rooting a strategy at a deleted operation could cause the overall strategy to fail. Alternatively, we could make it so that patterns cannot delete operations and they are expected to be later cleaned up by DCE if they end up being unnecessary.

from iree-llvm-sandbox.

I would add a strategy.define operation that, similarly to function definitions, associates a region with a symbol name. This is a symbol-level counterpart to strategy.reify that produces a value. Relying on builtin.func for this purpose will quickly turn problematic.

In general, do you think we can survive with non-parametric strategies (i.e. ones that only take a !pdl.operation) or will there be some parametricity?

Plus the usual concerns about complexity of the rewrite engine and action-at-a-distance on the IR that make debugging hard should something go wrong. I suppose these cannot be answered without a prototype.

from iree-llvm-sandbox.

In general, do you think we can survive with non-parametric strategies (i.e. ones that only take a !pdl.operation) or will there be some parametricity?

I think adding parameters to patterns is relatively straightforward (attributes on apply?).

Alternatively, we could make it so that patterns cannot delete operations and they are expected to be later cleaned up by DCE if they end up being unnecessary.

This sounds to me like too strict of a restriction. We can instead have the pattern explicitly return the operation handles that can be chained.

from iree-llvm-sandbox.