Stream: cranelift

Topic: Recursive ISLE structure definition

Colton (Dec 20 2023 at 03:20):

I'm trying to define a simple recursive AST structure within ISLE, along these lines:

enum SimpleAst {
    Constant(u64),
    Add([Box<SimpleAst>; 2]),
    Mul([Box<SimpleAst>; 2]),
    Symbol(String),
}

Naively transliterating this struct definition to ISLE yields

(type u64 (primitive u64))
(type str (primitive str))

(type SimpleAst
  (enum
  (Add (a SimpleAst) (b SimpleAst))
  (Mul (a SimpleAst) (b SimpleAst))
  (Constant (c u64))
  (Symbol (s str))
  ))
  ))

, which is not valid because of the lack of indirection in the generated struct definition. What's the correct way to define a recursive structure like this within ISLE?

bjorn3 (Dec 20 2023 at 14:17):

One option is to flatten it into a single large list with indices instead of Box<SimpleAst>.

bjorn3 (Dec 20 2023 at 14:17):

ISLE likely doesn't support native recursive structures as Cranelift IR does this flattening too.

fitzgen (he/him) (Dec 20 2023 at 18:52):

You would have to declare an external BoxSimpleAst type in ISLE and then define it as an alias for Box<SimpleAst> in the rust glue code that pulls in the generated ISLE code

but in general, yeah, it is better to work with indices/ids than actual boxes for these things

Chris Fallin (Dec 20 2023 at 19:32):

@Colton it may be useful to look at our def_inst extractor in the lowering prelude as well -- this is how we go from an index (Inst) to the InstructionData (the actual enum). ISLE is also not super-flexible about non-Copy enums (def_inst returns a copy of InstructionData) which sort of fits a lot better with the index-arena-based design

Chris Fallin (Dec 20 2023 at 19:33):

or rather, inst_data I mean; def_inst goes from a Value to Inst, sorry

Colton (Feb 28 2024 at 14:00):

Thanks for the pointers here. I have a prototype working now.

One more thing I'm wondering about is commutativity and associativity. Currently I have the following rewrite rule: ((x&y)+(~(y&x))) => -1. In ISLE I defined the rule like this:

;; opaque-constant-1
(rule (lower (SimpleAst.Add (SimpleAst.And x y) (SimpleAst.Neg (SimpleAst.And x y))))
    (Constant 18446744073709551615)
)

If I want to extend this to support ((y&x)+(~(x&y))), should I just redefine the rewrite for each possible commutative / associative variant?

Colton (Feb 28 2024 at 14:00):

Hmm, one other thing I just ran into:

(type u64 (primitive u64))
(type str (primitive String))
(type index (primitive AstIdx))

(type SimpleAst extern
  (enum
  ;; Arithmetic operators
  (Add (a index) (b index))
  (Mul (a index) (b index))
  (Pow (a index) (b index))
  ;; Bitwise operators
  (And (a index) (b index))
  (Or (a index) (b index))
  (Xor (a index) (b index))
  (Neg (a index))
  ;; Special types
  (Constant (c u64))
  (Symbol (s str))
  ))

;; Below are wrappers for constructing instances of the AST types.
;; Arithmetic
(decl Add (index index) SimpleAst)
(extern constructor Add add)
(decl Mul (index index) SimpleAst)
(extern constructor Mul mul)
(decl Pow (index index) SimpleAst)
(extern constructor Pow pow)
;; Bitwise
(decl And (index index) SimpleAst)
(extern constructor And and)
(decl Or (index index) SimpleAst)
(extern constructor Or or)
(decl Xor (index index) SimpleAst)
(extern constructor Xor xor)
(decl Neg (index) SimpleAst)
(extern constructor Neg neg)
(decl Any (index) SimpleAst)
(extern constructor Any any)

(decl put_value_in_reg (SimpleAst) index)
(extern extractor put_value_in_reg put_value_in_reg)
(extern constructor put_value_in_reg put_value_in_reg_ctor)

;; Special types
(decl Constant (u64) SimpleAst)
(extern constructor Constant constant)
(decl Symbol (str) SimpleAst)
(extern constructor Symbol symbol)

;; Declare our top-level lowering function. We will attach rules to this
;; declaration for lowering various patterns of `SimpleAst` inputs.
(decl partial lower (SimpleAst) SimpleAst)

;; or-zero
(rule (lower (SimpleAst.Or a (SimpleAst.Constant 0)))
    (Any a)
)

;; or-itself
(rule (lower (SimpleAst.Or a a))
    (Any a)
)


(convert SimpleAst index
put_value_in_reg)

Given this ISLE file, islec errors out due to these two overlapping rules:

;; or-zero
(rule (lower (SimpleAst.Or a (SimpleAst.Constant 0)))
    (Any a)
)

;; or-itself
(rule (lower (SimpleAst.Or a a))
    (Any a)
)

Ideally I'd like to search for both of these patterns within the same matching routine(picking whichever rule matches first). Is there a way to do this?

fitzgen (he/him) (Feb 28 2024 at 14:46):

If I want to extend this to support ((y&x)+(~(x&y))), should I just redefine the rewrite for each possible commutative / associative variant?

for now, yes. there is https://github.com/bytecodealliance/wasmtime/issues/6128 for tracking ISLE doing this automatically in the future

fitzgen (he/him) (Feb 28 2024 at 14:47):

Ideally I'd like to search for both of these patterns within the same matching routine(picking whichever rule matches first). Is there a way to do this?

You can add a rule priority to make ISLE prefer the more-specific rule. We went back and forth on implicit priorities defined by which rule has more-specific matching structure, but that path is filled with ambiguities, so we ultimately decided on explicit rule priorities to resolve things here.

fitzgen (he/him) (Feb 28 2024 at 14:49):

https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/isle/docs/language-reference.md#rules has some docs on priorities

https://github.com/bytecodealliance/wasmtime/blob/main/cranelift/isle/isle/isle_examples/pass/prio_trie_bug.isle#L76 is an example rule with a priority

Last updated: Oct 23 2024 at 20:03 UTC