Kill Recipes With Fire 🔥

[bnjbvr]

(Really a meta-issue about the meta-crate!)

Nobody likes Recipes. They were supposed to contain factored-out fields of the encodings. But they're mostly one indirection layer that's hard to understand, that needs to be explained to newcomers, and doesn't solve the factoring out problem ideally. For instance, if you want to use one recipe, but just one register allocation constraint differs from the one you're looking at, you'll need to duplicate it and change the one constraint. Other things that are always unclear are whether an instruction/ISA predicate should be attached to an Encoding or to the underlying Recipe.

Let's kill recipes with fire. There's been discussions about this, and a general agreement that it's the right thing to do: it'll make the code easier to understand, more straightforward, and it'll be more pleasant for contributors in general.

The general plan is backed by the following idea:

1. take a subset of related fields in the Recipe
2. put them in the Encoding instead
3. rinse and repeat step 1 until there's nothing anymore in the Recipe
4. ???
5. fun and profit

I've thought about this, and I think the following groups can be done in chunks, so they can serve as divides of the work that's needed here:

• On x86, have the REX byte emission be a runtime decision in the binemit code, rather than a different encoding. That's Use variable-length encodings for REX encodings #1130.
  • Once that's done, replace x86's Template by helper functions that take an Encoding and tweak it to return a new encoding.
• Move ISA and instruction predicates over to Encoding (This is likely to make legalization slightly faster, since the ISel interpreter is able to deduplicate tests for a given pair of (ISA, instruction) predicates attached to several encodings.)
  • Then we can simplify code in the ISel interpreter to not store and check recipe predicates.
• Move register allocation constraints over to Encoding; these are operands_in/operands_out right now, giving constraints to Value inputs and outputs of a given Instruction.
• Move binemit code + size computation information over to Encoding (base_size/compute_size/branch_range). Note (I think) we don't need to move the format field, because an Encoding is attached to an Instruction that has its own format. (Because of recipes, one could attach different formats to the Instruction / Encoding, causing a runtime error in the build script. Good riddance!)
  • Create an enum for binemit functions, so they can still be shared across Encodings.
  • Use enums instead of plain function pointers for compute_size, to avoid indirect calls in the codegen crate.
  • (Bonus) Find a way so binemit function bodies are compiled as part of the meta crate itself (macro?).
• Move clobbers_flags to the Encoding.

Some of these items might not be doable as I expect; I tried to imagine what the could would ideally look like, but the reality of how things are in Cranelift may have us go down a different road.

Each step will imply some work in the codegen crate too, to make sure it's still working properly, as well as opportunities for simplifications. I haven't put items for each simplification, because it's somewhat unclear in general what these could be, but they may exist. It'd be nice that each step belonged to its own PR (substeps can go in commits), to avoid boiling the ocean at once ;)

[abrown]

I'm all for this. In fact, reading it through carefully I realized that a lot of what I'm trying to work around in the re-factoring I started in bytecodealliance/cranelift#1149 would be easier if we were a couple steps down this road. I started to factor out the common patterns for adding encodings (32, 64, x86_64, both, i32_i64, etc.) but realized that instead of only having to interact with EncodingBuilders, I had to sometimes use Templates or Recipes for adding the patterns. If Encoding gets smarter then I would expect EncodingBuilder to get smarter and I can just use it in encodings.rs for the patterns (@bnjbvr what do you think of just interacting with EncodingBuilder to add encodings? And what will take the place of the custom code in Recipe--does that just move to the Encoding/EncodingBuilder?). I am going to put bytecodealliance/cranelift#1149 on hold until we've completed more of this.

[bnjbvr]

@bnjbvr what do you think of just interacting with EncodingBuilder to add encodings?

Yes, this would be nice. I still think there's a need to "inherit" encodings, that is, to be able to use an Encoding as the base of another one, and then just selectively change a few bits; that would maintain factoring opportunities when only the REX.w bit value changes etc., and would effectively be the last step before removing Templates. It could be done through a special EncodingBuilder ctor, or just a function that takes an Encoding input and returns a modified copy.

And what will take the place of the custom code in Recipe--does that just move to the Encoding/EncodingBuilder?

If I understand correctly you're referring to binemit code, which will live in the Encoding, or ideally in a separate function that's indirectly referenced through an enum living in the Encoding, since these binemit functions may still be common to many Encodings.

[julian-seward1]

@bnjbvr Is there any need to "inherit" encodings other than to support generation (or omission) of REX prefixes?

[bnjbvr]

@bnjbvr Is there any need to "inherit" encodings other than to support generation (or omission) of REX prefixes?

I think so, see rrr helper for bits in the ModR/M byte, or setting another bits of the REX prefix (W bit). The alternative would be to just copy/paste code, which is also possible; it would become overly prolix though.

[sstangl]

@bnjbvr In trying to follow instructions to remove Template, I get the feeling that I'm just reinventing it on the EncodingRecipe. I wanted to make sure that I understand the end-state here. Please let me know if I have misunderstood something.

A "recipe" is a shared function that knows how to emit instructions that share a similar byte pattern.

"Kill Recipes With Fire" does not mean getting rid of these shared functions as I originally thought. (If we were to do that, then x86 wouldn't need a real Encoding at all -- it could just be an enum of instruction kinds, and there would be a function that matched on the enum value and outputted the bits just for that one instruction. There would be no need to store opcode bits in the Encoding at all.)

Instead, this issue is to basically keep the same behavior as recipes, but just move the EncodingRecipeBuilder requirements to be on the Encoding instead of on the EncodingRecipe or Recipe so that they are significantly more verbose in the meta/src/isa/x86/encodings.rs.

Do I have that right? I have been a bit confused by the direction to have more run-time decision making of REX prefix emission while simultaneously eliminating recipes, because different opcodes encode REX in a different position, so there is no simple logic that's valid in all cases (that I'm aware of).

[bnjbvr]

Do I have that right?

It sounds right to me. Note that the above plan is an outline, and there is definitely room for exploration of alternative ways to implement it.

I have been a bit confused by the direction to have more run-time decision making of REX prefix emission while simultaneously eliminating recipes

Could we eliminate the REX-prefixed recipes without eliminating recipes as a whole at the same time, so work could remain incremental? I think the former can be implemented without the latter.

[bjorn3]

The new backend framework doesn't use recipes.

[cfallin]

Indeed; we might as well close this one now!