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?
One option is to flatten it into a single large list with indices instead of Box<SimpleAst>
.
ISLE likely doesn't support native recursive structures as Cranelift IR does this flattening too.
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
@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
or rather, inst_data
I mean; def_inst
goes from a Value
to Inst
, sorry
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?
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?
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
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.
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: Dec 23 2024 at 13:07 UTC