Stream: cranelift

Topic: AST traversal with ISLE

Leon von Mulert (Nov 18 2024 at 16:09):

I'm currently playing around with ISLE to check whether (and how) to use it for an AST->VmInstruction lowering, but all the examples I can find operate on an IR that does not seem to be deeply nested.

From my limited examples, ISLE only transforms the root node / value, e.g. given

(type Ast (enum
      (Add (src1 Index)
            (src2 Index))
      (Reg (src Reg))
      (Const (val i32))
))
(decl get_node (Ast) Index)
(extern extractor get_node get_node)
(convert Ast Index get_node)

(decl partial reduce (Ast) Ast)
(rule zero
    (reduce (Ast.Add (Ast.Reg src1) (Ast.Const 0)))
      (Ast.Reg src1)
)

A tree of form Add(Add(reg1, 1), Add(reg2, 0)) will not be reduced/simplified. I'm not sure whether this is due to the flattened nature of the AST (replacing recursive children with indices, and an extractor to turn Index->Ast), or maybe I'm misunderstanding the the usage of ISLE in general. Do I need to provide an external driver/traversal function, or is ISLE able to do a recursive traversal by itself with the correct definitions?

Chris Fallin (Nov 18 2024 at 19:56):

In general the ISLE user provides the traversal logic. The key to understanding ISLE is seeing that it isn't really a tree-rewriting system at all -- it's a DSL for generating matchers. If you define extractors for your AST nodes and use them on the left-hand side, you can match arbitrarily deep; but one top-level invocation of ISLE will only match one top-level rule and execute its right-hand side (whatever that does -- perhaps build more nodes).

For two examples of ISLE "embeddings" (envrionments in which it is invoked), take a look at Cranelift's mid-end and backend -- the mid-end egraph infra and the backend (with helpers here)

fitzgen (he/him) (Dec 04 2024 at 17:55):

to add on to what Chris said: in both Cranelift embeddings of ISLE (mid end and backends) the actual traversal over the IR is driven by host Rust code rather than ISLE code, and that traversal invokes an ISLE constructor on each IR node as it goes. the ISLE constructor then does complex pattern matching, matching arbitrarily (but ~O(1)) deep, and all that to transform/rewrite in a peephole style. but the ISLE does not itself recurse over the IR or drive the traversal.

Last updated: Dec 23 2024 at 12:05 UTC