Stream: git-wasmtime

Topic: wasmtime / issue #4475 Do ISLE rewriting rules rewrite th...

Wasmtime GitHub notifications bot (Jul 20 2022 at 11:41):

wmstack opened issue #4475:

Relevant Question: https://cstheory.stackexchange.com/questions/6256/whats-the-difference-between-term-rewriting-and-pattern-matching?rq=1&newreg=4ad61442dc214a2d8e999c01f8651e0c

It seems to me that as the answer says, that pattern matching can only rewrite the top-level structure that is pattern matched, while rewriting rules can rewrite any sub-expression (or sub-computation) that is anywhere in the tree or directed-acyclic graph of computations.

Does ISLE rewrite subexpressions in the cranelift IR CFG?

Wasmtime GitHub notifications bot (Jul 20 2022 at 16:16):

bjorn3 commented on issue #4475:

ISLE works on one instruction at a time (walking backwards for DCE without requiring a separate DCE pass), potentially matching the instructions that produce values used by this instruction. Instructions don't can't have sub-expressions. They are atomic units. For example for

v1 = iconst.i32 42
v2 = load.i32 v0
v3 = iadd.i32 v1, v2

it would first visit v3 = iadd.i32 v1, v2 and try the rule at https://github.com/bytecodealliance/wasmtime/blob/b28abb620e3d41a3457f58b5dfb8f74b8321c398/cranelift/codegen/src/isa/x64/lower.isle#L80-L84 This rule will match v3 = iadd.i32 v1, v2 and v2 = load.i32 v0 and turn it into an add instruction with a direct memory reference as operand. After this the v2 = load.i32 v0 is skipped as it is already lowered and isn't used anywhere else (sinkable_load won't match when there is more than 1 use of a loaded value I believe) and then v1 = iconst.i32 42 is lowered to a mov of a constant value.

Wasmtime GitHub notifications bot (Jul 20 2022 at 16:17):

cfallin commented on issue #4475:

Hi @wmstack -- I think the most accurate answer to your question is "both", but with significant subtleties. To start with:

Does ISLE rewrite subexpressions in the cranelift IR CFG?

can be answered either with "not applicable", because ISLE-the-DSL doesn't do anything except invoke extractors and constructors, and the behavior of these is up to the embedder of the DSL's generated code (in our case, Cranelift); or "no", because our current use of ISLE is to generate code for lowering, so there is no rewriting of the CLIF at all, only matching on the CLIF and then generating machine instructions (MachInsts).

But if you widen the scope of the question to "can ISLE be used to rewrite arbitrary subterms", the answer is absolutely yes; all the DSL concerns itself with is pattern-matching on the left-hand side, and then building a new expression with those parts on the right-hand side. Given those building-blocks one could construct a system with ISLE that arbitrarily rewrites subexpressions.

For what it's worth I think the StackExchange answer linked has a bit more nuance than "top-level vs sub-expression"; the first answer has good points with respect to term-rewriting generally being a model for computation and pattern-matching as an area of study focused more on efficient destructuring. Those two are orthogonal: one can build a term-rewriting system that steps through computation with pattern-matching.

Wasmtime GitHub notifications bot (Jul 20 2022 at 16:18):

cfallin closed issue #4475:

Relevant Question: https://cstheory.stackexchange.com/questions/6256/whats-the-difference-between-term-rewriting-and-pattern-matching?rq=1&newreg=4ad61442dc214a2d8e999c01f8651e0c

It seems to me that as the answer says, that pattern matching can only rewrite the top-level structure that is pattern matched, while rewriting rules can rewrite any sub-expression (or sub-computation) that is anywhere in the tree or directed-acyclic graph of computations.

Does ISLE rewrite subexpressions in the cranelift IR CFG?

Last updated: Dec 23 2024 at 12:05 UTC