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)

Last updated: Nov 22 2024 at 17:03 UTC