x64: Refactor assembler ISLE constructors

[alexcrichton]

This commit is spawned out of discussion between me and Andrew in conjunction with the thoughts in #10238. The goal here is to pave a way forward for various kinds of instructions in the future as well as give access to more instructions today we already have formats for.

The major changes in this commit are:

• Assembler* types are gone from ISLE, except for immediates. Instead types like Gpr and GprMem are used instead.
• Rust-defined constructors for each instruction return MInst instead of implicitly performing an emit operation.
• Instructions with a read/write GprMem operand now generate two ISLE constructors instead of one. One constructor takes Gpr and returns Gpr, the other takes Amode and returns SideEffectNoResult.
• Generated ISLE constructors now match the SSA-like form of VCode/ISLE we already have. For example AssemblerReadWriteGpr is never used as a result, it's just Gpr instead. Conversions happen in Rust during construction of assembler instructions.

Using this new support various x64_*_mem instructions have now moved over to the new assembler and using that instead. Looking to the future this is intended to make it easier to generate constructors that return ProducesFlags or ConsumesFlags such as x64_adc and friends. This will require more refactoring to enable this but the goal is to move roughly in such a direction.

I've attempted to make this abstract enough that it'll be relatively easily extensible in the future to more ISLE constructors with minimal changes, so some abstractions here may not be fully used just yet but the hope is that they will be in the near future.

[alexcrichton]

I'll also note that this creates a lot of conflicts with #10273, and I'm happy to have that go through first and rebase around that, or also have this go in first and I can help that PR rebase around this. Either way works for me

[github-actions]

Subscribe to Label Action

cc @cfallin, @fitzgen

This issue or pull request has been labeled: "cranelift", "cranelift:area:x64", "isle"

Thus the following users have been cc'd because of the following labels:

• cfallin: isle
• fitzgen: isle

To subscribe or unsubscribe from this label, edit the .github/subscribe-to-label.json configuration file.

Learn more.

[alexcrichton]

An example of extending this is alexcrichton@ea299c4 where I've updated the add/adc instructions to using ProducesFlags and ConsumesFlags in ISLE. That enabled removing more adc/add constructors using the now-old MInst variants. It generates a lot of constructors that we don't actually use today, but they're all there and much more easily accessible than they are today.

[cfallin]

Adding myself as a reviewer here -- want to take a look, excited to see progress on untangling some of the layers of abstraction.

[alexcrichton]

Some before/after of ISLE constructors for this PR are:

before

(decl x64_addb_mi (AssemblerReadWriteGprMem AssemblerImm8) AssemblerReadWriteGprMem)
(extern constructor x64_addb_mi x64_addb_mi)
(decl x64_addb_mr (AssemblerReadWriteGprMem AssemblerReadGpr) AssemblerReadWriteGprMem)
(extern constructor x64_addb_mr x64_addb_mr)
(decl x64_addb_rm (AssemblerReadWriteGpr AssemblerReadGprMem) AssemblerReadWriteGpr)
(extern constructor x64_addb_rm x64_addb_rm)

after

(decl x64_addb_mi_raw (GprMem AssemblerImm8) MInstAndGprMem)
(extern constructor x64_addb_mi_raw x64_addb_mi_raw)
(decl x64_addb_mi_mem (Amode AssemblerImm8) SideEffectNoResult)
(rule (x64_addb_mi_mem rm8 imm8) (side_effect_minst_and_gpr_mem (x64_addb_mi_raw rm8 imm8)))
(decl x64_addb_mi (Gpr AssemblerImm8) Gpr)
(rule (x64_addb_mi rm8 imm8) (emit_minst_and_gpr_mem (x64_addb_mi_raw rm8 imm8)))

(decl x64_addb_mr_raw (GprMem Gpr) MInstAndGprMem)
(extern constructor x64_addb_mr_raw x64_addb_mr_raw)
(decl x64_addb_mr_mem (Amode Gpr) SideEffectNoResult)
(rule (x64_addb_mr_mem rm8 r8) (side_effect_minst_and_gpr_mem (x64_addb_mr_raw rm8 r8)))
(decl x64_addb_mr (Gpr Gpr) Gpr)
(rule (x64_addb_mr rm8 r8) (emit_minst_and_gpr_mem (x64_addb_mr_raw rm8 r8)))

(decl x64_addb_rm_raw (Gpr GprMem) MInstAndGpr)
(extern constructor x64_addb_rm_raw x64_addb_rm_raw)
(decl x64_addb_rm (Gpr GprMem) Gpr)
(rule (x64_addb_rm r8 rm8) (emit_minst_and_gpr (x64_addb_rm_raw r8 rm8)))

[abrown]

Ok, I'll take a look at this today. After we talked, I took the approach a few steps further so I'll try to reconcile that with this.

[abrown]

Ok, as a point of comparison, here is where I ended up for the same instructions above:

(decl x64_addb_mi (GprMem u8) AssemblerOutputs)
(extern constructor x64_addb_mi x64_addb_mi)
(decl emit_x64_addb_mi (GprMem u8) Gpr)
(rule (emit_x64_addb_mi GprMem u8)
  (let (
    (out AssemblerOutputs (x64_addb_mi GprMem u8))
    (inst MInst (asm_out_inst out))
    (gpr Gpr (asm_out_gpr out))
    (_ Unit (emit inst))
  )
  gpr))

(decl x64_addb_mr (GprMem Gpr) AssemblerOutputs)
(extern constructor x64_addb_mr x64_addb_mr)
(decl emit_x64_addb_mr (GprMem Gpr) Gpr)
(rule (emit_x64_addb_mr GprMem Gpr)
  (let (
    (out AssemblerOutputs (x64_addb_mr GprMem Gpr))
    (inst MInst (asm_out_inst out))
    (gpr Gpr (asm_out_gpr out))
    (_ Unit (emit inst))
  )
  gpr))

(decl x64_addb_rm (Gpr GprMem) AssemblerOutputs)
(extern constructor x64_addb_rm x64_addb_rm)
(decl emit_x64_addb_rm (Gpr GprMem) Gpr)
(rule (emit_x64_addb_rm Gpr GprMem)
  (let (
    (out AssemblerOutputs (x64_addb_rm Gpr GprMem))
    (inst MInst (asm_out_inst out))
    (gpr Gpr (asm_out_gpr out))
    (_ Unit (emit inst))
  )
  gpr))

What's going on in this version is that (1) the x64_addb_* ISLE now returns an AssemblerOutputs instead of actually emitting the instruction; the emission part is left to (2) some emit_x64_addb_* ISLE which we generate right beside it. Why? I was a bit concerned that if we keep on generating new variants of these things (_mem, _flags, etc.) we end up muddying the waters; instead, we can use the "return an inst" version in (1) to fit into all the existing conventions ISLE defines: ProducesFlags, ConsumesFlags, SideEffect, etc.

What is AssemblerOutputs, you ask?

(type AssemblerOutputs (enum
      (WritesMemory (inst MInst))
      (WritesGpr (inst MInst) (gpr Gpr))
))

I was thinking that this core enum can be matched on or auto-converted (AssemblerOutputs.WritesMemory --> SideEffect) into the existing compiler but don't perpetuate all the *Flags and SideEffect logic in the generator. If we were to change any of those conventions, I was hoping this approach would reduce the blast radius. Thoughts?

[edit: I know that up above we don't want some of those emit_* ISLE functions to return a Gpr... my branch is still a work in progress so that is not all the way there.]

[abrown]

Another thought: at some point soon we could move all the code that generates ISLE out of cranelift-assembler-x64-meta and into cranelift-codegen-meta.

[cfallin]

Two thoughts to add:

• In general it has been bothering me a bit that we have separate Assembler* types at all. I think a lot of the distaste for the binding code currently comes from the fact that we have to do these translations. I really like that this PR eliminates AssemblerGpr and friends at the inst.isle layer; the immediates are still there, but we can hopefully remove those in a future change. The ideal IMHO is that we actually reuse types directly -- so rather than define our own GprMem/GprMemImm on the Cranelift side, we use the assembler types throughout (and because we plug the regalloc2 types into the assembler types, everything will be compatible when we generate regalloc traversal code).
• I'm finding myself with a distaste for the "return the instruction as an object" APIs in general, because of the additional plumbing that this creates, though I understand the reason this side-quest started (ProducesFlags/ConsumesFlags constructors). I wonder whether we could instead avoid that extra plumbing in ISLE, and the definition of emit_* helpers and MInstAnd* auxiliary types, by instead pushing the ProducesFlags and ConsumesFlags types down into the generated ISLE; so we have the lowest-level constructors that either (i) emit the inst and return e.g. a Gpr (and that's it, no more types needed), or (ii) return a ProducesFlags/ConsumesFlags and we pass these to with_flags, which does the emission and returns Gpr / pair of Gprs / whatever.

Basically I'm hoping for simplicity via reduction in layers of abstraction as far as possible without losing type safety; that was the original state of play, the flags abstraction added a bit but it was seen as necessary, now the separate assembler layer whose types are being kept separate (rather than propagated through Cranelift) is ratcheting the boilerplate up past a critical threshold IMHO. Curious to hear your thoughts.

[alexcrichton]

@abrown

I think you and I basically converged on the same idea. In this PR the *_raw constructors return either MInst (your WritesMemory variant), MInstAndGpr (your WritesGpr variant), or MInstAndGprMem (same as your AssemblerOutputs type). The "middle parts" of then converting from the "raw" thing to the output thing is basically inline ISLE for you vs helper functions for you. Basically I think we're thinking the same thing, but the main difference for me is that no constructor takes GprMem as a first argument, but instead splits that into two constructors -- one taking Gpr and one taking Amode.

Also I can confirm that with something like AssemblerOutputs (or the more specific types I have in this PR) there need not be any changes to handle {Produces,Consumes}Flags. The commit above has no changes to *_raw and enables new flags-aware constructors.

---

@cfallin

The ideal IMHO is that we actually reuse types directly -- so rather than define our own GprMem/GprMemImm on the Cranelift side, we use the assembler types throughout

💯 from me on this, agreed that should be the end state.

so we have the lowest-level constructors that either (i) emit the inst and return e.g. a Gpr (and that's it, no more types needed), or (ii) return a ProducesFlags/ConsumesFlags and we pass these to with_flags, which does the emission and returns Gpr / pair of Gprs / whatever.

To me this is what it comes down to, the question of "what is the lowest level thing?" As-is today it's not possible to create {Produces,Consumes}Flags in ISLE because the emit happens in the Rust FFI layer. With your suggestion I think it would effectively double-the FFI layer by having one "raw" function return a Gpr and another return an MInst, which is something I was trying to avoid. In playing around with the assembler/generated code the FFI layer is the hardest to debug and reason about because the compiler doesn't show errors in the generated code, only on the asm::generate!() invocation. I've thought a bit about how to fix this and kept coming up blank.

In the end my goal here was to have the "raw" constructor be as general-purpose as possible, aka the "narrow waist" that all ISLE abstractions would be built on. It's more-or-less @abrown's AssemblerOutputs suggestion and personally I like that design over what I have here. It's just one type to think about and then ISLE constructors figure out what to do with it. The forseeable changes I can think of to AssemblerOutputs are (a) a variant returning two Gpr values for mul and (b) adding a variant returning an Xmm register instead of a Gpr.

---

Overall I feel like we're all basically in agreement about how to design this -- a "raw" thing with fancy ISLE abstractions on top -- and are more-or-less trying to figure out what to paint the bikeshed. What I might concretely propose is to hand-write this in ISLE:

(type AssemblerOutputs (enum
    ;; used for stores, instructions that modify memory, traps (?), etc
    (SideEffect (inst MInst))
    ;; used for anything that returns a gpr, including
    ;; "mr" variants where the first argument was a Gpr
    (RetGpr (inst MInst) (gpr Gpr))
    ;; used for `imul`, `mul` , `div`, etc
    (RetTwoGpr (inst MInst) (gpr1 Gpr) (gpr2 Gpr))
    ;; SSE/AVX/etc
    (RetXmm (inst MInst) (gpr Xmm))
    
    ;; maybe `RetXmm2`? Unsure if we have any of those
))

The FFI layer in Rust would always return an AssemblerOutputs from each and every method. Most raw constructors would statically return just one variant, for example "RM" encodings would always return RetGpr. The "MR" variants, however, would dynamically return either SideEffect or RetGpr depending on the input. The ISLE constructor would know which it passed in and there'd be one constructor for each (e.g. x64_addb_mi and x64_addb_mi_mem above).

To me this strikes a nice balance of:

• Generated FFI code in Rust is "simple" in the sense that everything is a round peg in a round hole. There's one constructor per instruction as well so no need to deal with a matrix of FFI constructors per instruction.
• ISLE types get to stay as ISLE types in constructors. No Assembler* once we transition immediates. Everything stays as Gpr, GprMem, etc.
• Dealing with constructs like {Produces,Consumes}Flags happens exclusively in ISLE.
• Each instruction gets an array of constructors for the various "type signatures" it can take -- e.g. return-gpr, read-modify-write memory, return-gpr-with-flags, read-modify-write memory-with-flags, etc.

I think it would also make sense to define all the helper functions that converts AssemblerOutputs to ctor outputs (e.g. AssemblerOutputs => Gpr) as hand-written functions in ISLE. These would be just below the AssemblerOutputs definition which would be easy to skim and would be relatively easily connect-able to the machine-generated instructions too.

---

That's a lot of words, but WDYT?

[cfallin]

To me this is what it comes down to, the question of "what is the lowest level thing?" As-is today it's not possible to create {Produces,Consumes}Flags in ISLE because the emit happens in the Rust FFI layer. With your suggestion I think it would effectively double-the FFI layer by having one "raw" function return a Gpr and another return an MInst, which is something I was trying to avoid.

Not quite; I'm imaging that the external Rust constructor for (e.g.) a variant of add returns only a ProducesFlags -- that's the fundamental thing -- and one could either use that in a with_flags or (via an automatic conversion) get a Gpr by pairing with a null ConsumesFlags. (call it something like (decl ignore_flags (ProducesFlags) Gpr) maybe?)

Some of this goes back to early ISLE design philosophy, but: my intent with the initial design was to hew as close to a "value semantics" view of the program operators and instructions as possible, because this is what enables reasoning about expression equivalence, makes verification possible, etc. From that point of view, it makes sense that some instruction that is a binary operator (i) takes two registers and (ii) returns a register, just like its CLIF cousins. The bit of lowering logic that bridges the gap is hiding the emit in the constructor and returning the value. The magic of data dependencies means that it is physically impossible to call the ctors in an order that is not a valid toposort of operations, so emitting-when-constructed is always valid.

We started carrying MInsts around instead when we invented the ProducesFlags/ConsumesFlags abstraction; that was the first time that we wanted to have some other way of controlling emission time, to ensure flags aren't clobbered. But we carefully wrapped the insts inside another enum and provided a combinator (with_flags) that itself hid the emission inside, so we were back to a world of value semantics with ensured ordering in the end.

This is part of the reason I'm not so sure that "return the MInst" is more fundamental: it's exposing more of the mechanism, certainly, but it's moving to a world where one has access to sharp tools that can be combined in the wrong way (emitting out of order), and where one has more pieces that one has to put together, more complex overall.

So if possible I'd prefer to bias us back toward implicit emission everywhere, and I do think it's possible here, as described above -- the fact that the instruction produces flags is fundamental, so that one is the one that we define; and an implicit converter can throw away the flags if we don't care. Thoughts?