Wasmtime: Reduce codegen annoyances

[abrown]

Having worked with cranelift for a few weeks now, I've had several discussions about how to improve the code in the cranelift-codegen module. I am sure that moving meta from Python to Rust has made the code easier to understand and use but here are some things I've noticed as I've worked in this module:

1. __static references__: cranelift-codegen contains many by_name retrievals throughout the encodings, formats, legalization, etc. This means that when I add a new instruction, e.g., I can't encode it until I've found the alphabetically-ordered location to insert a by_name("my_inst")--and I forget to do this every time. @bnjbvr mentioned that we might be able to use lazy_static to initialize them. Then we could use instructions, e.g., by importing crate::shared and writing shared::splat where they are used. This may work for instructions, formats, recipes (maybe?), but we may run into issues with settings since SettingGroupBuilder::build does more than just collect predicates.
2. __eliminate templates__: cranelift-codegen has the concept of Recipes; the x86 subdirectory has the additional concept of Templates (previously TailRecipes). Perhaps I just don't understand the purpose of Template clearly enough (and would appreciate an explanation), but having both Recipe and Template is very confusing; it is unclear when to build one or the other and the difference seems minimal. Is there a way Recipe can be improved to cover any features it is missing and Template eliminated?
3. __recipe naming convention__: The x86 recipes have a confusing assortment of names: sometimes they make sense (null and null_fpr) but other times the naming is less than clear (e.g. brid might stand for a branch recipe with a double-word immediate?). This makes it difficult to find existing recipes that may already do what I need. Can we explain the naming convention in the documentation and/or adopt a naming convention that is more explanatory?
4. __non-string recipes__: The recipe code itself (i.e. in emit) is difficult to change because it is a string, not Rust code. If a recipe is coded incorrectly, usually the build will fail; if the code was statically analyzable the errors would be clearer sooner. If instead emit could be passed a closure or function to do the appropriate recipe work, then the code would be statically analyzable: .emit(|sink, bits, regs| { ... }. This won't work as-is because each recipe uses different parameters and types, but perhaps a procedural macro wrapped around this (i.e. emit(recipe_from!(|sink, bits, regs| { ... })) could reduce a real Rust closure/function to the strings emit expects while allowing IDEs to statically analyze the code.
5. __re-factor PerCpuModeEncodings__: The x86 encodings use a PerCpuModeEncodings struct to join an instruction, its bound types, its encodings, its recipes, etc. Currently there are a confusing assortment of methods for adding different subsets of these (e.g. enc_x86_64_instp, enc_both, enc_x86_64, enc_i32_i64, etc.). Perhaps a builder-like pattern would allow us to remove some of these methods and clarify what is happening; something like: e.inst(band).with_types([B1, B8, B16]).uses_recipe(rec_rr.opcodes(...)).when_isa([use_sse3]).when_predicate(...).encode();. For instructions that have several encodings following a pattern (i.e. like that of enc_i32_i64) we could add a .encode_with_pattern(...) accepting an enum for the various patterns.

I am opening this issue to discuss if any of the above are feasible and desirable. Please add to this list if there are other items.

[julian-seward1]

Speaking more generally, I am all in favour of simplifying the instruction description and encoding language. I haven't interacted with it nearly as much as you have, but when I did, I found it very confusing and had to constantly ask for help when modifying it.

A more conventional instruction-description framework might, for example, have a C++ tagged union or class hierarchy giving a type X86Instr, and a few methods on that: emit_instr to generate the encoding, get_regs to query register usage, map_regs to apply regalloc's decisions to the instruction, etc. I realise that the CL framework has some particular requirements -- a unified representation of the IR and machine instructions, and a compact representation of instructions. Coming from that background, though, CL's schemes seem really complex.

I can see the need for instruction definitions and encoding definitions. But are recipes really necessary? Would it be feasible to directly specify, in each encoding, a bit of Rust code that generates the encoding, calling some Rust helper functions to do so?

The multiple namespaces also confuse me. I recently added an instruction copy_to_ssa, basically a reg-reg copy. This entailed adding:

shared/instructions.rs
    an instruction with name "copy_to_ssa"

x86/encodings.rs
    let copy_to_ssa = shared.by_name("copy_to_ssa");
    let rec_umr_reg_to_ssa = r.template("umr_reg_to_ssa");
    e.enc_i32_i64(copy_to_ssa, rec_umr_reg_to_ssa.opcodes(vec![0x89]));

x86/recipes.rs
    let f_copy_to_ssa = formats.by_name("CopyToSsa");
    EncodingRecipeBuilder::new("umr_reg_to_ssa", f_copy_to_ssa, 1)

src/shared/formats.rs:
    registry.insert(Builder::new("CopyToSsa").imm(("src", regunit)));

and I wondered what the required relationships of these various names are. Eg, does having the text "copy_to_ssa" in one place somehow require text "CopyToSsa" in another? Are they in the same namespace or not?

[bjorn3]

Would it be feasible to directly specify, in each encoding, a bit of Rust code that generates the encoding, calling some Rust helper functions to do so?

That would probably cause the size of libcranelift_codegen.rlib to go up a lot.

[bjorn3]

Eg, does having the text "copy_to_ssa" in one place somehow require text "CopyToSsa" in another? Are they in the same namespace or not?

No, the first one is the instruction definition, the second one the actual encoding, the third one the recipe (reusable for multiple inst encodings) and the last one is the instruction format, which correspond to InstructionData variants in cranelift-codegen (reusable for multiple inst encodings)

[julian-seward1]

That would probably cause the size of libcranelift_codegen.rlib to go up a lot.

But that functionality has to be implemented somewhere anyway; we can't not implement it.

As a data point .. valgrind's emit_AMD64Instr [1] compiles to about 11.5K of code in the standard build and about 24K if I crank up inlining as much as I can. That's an optimised build, although with assertions. It emits the basic integer instruction set, some x87, and quite a wide range of SSE2 both single-lane and all-lanes insns, so .. at least as much as CL and probably more.

[1] https://sourceware.org/git/?p=valgrind.git;a=blob;f=VEX/priv/host_amd64_defs.c;h=29127c1258c54911b0cb104949614837f7bb8ab3;hb=HEAD#l2508

[bjorn3]

@julian-seward1 Some code for every recipe + a map from inst to a recipe and some extra data like encoding bytes is likely smaller than some code for every single instruction encoding.

As an aside I am curious which of the two approaches are faster. The current with recipes has better code locality, at the expense of data locality, while the other option without recipes has the opposite trade off.

[julian-seward1]

I've been doing some low level profiling of CL recently, while compiling large chunks of Wasm -- Embenchen's wasm_lua_binarytrees.c.js. From what I've seen, CL has no problems with locality, either I- or D-Cache. For that test case, CL achieves an I1 miss rate of 0.27% for 1816 million insns, and a D1 miss rate of 0.7% for 821 million D1 accesses. This strikes me as very good, particularly given that these numbers are pessimistic: they assume there's no prefetching happening.

On my Intel Skylake, CL achieves a CPI of 2.13 for this test, which IMO is atypically high. Compiling the same via Ion gets a CPI of 1.63. This also suggests there are no locality problems, nor any other bad interactions with the microarchitecture.

As an aside I am curious which of the two approaches are faster.

I suspect the answer is "it doesn't make any difference, since the vast majority of the time goes elsewhere, especially in register allocation". But I am speculating here.

[bjorn3]

since the vast majority of the time goes elsewhere, especially in register allocation

Yeah, noticed that during profiling a few months ago. I also noticed that for cg_clif rustc itself is the biggest time consumer.

[bnjbvr]

Fully agreed with points 1, 3 (I don't know the naming convention for recipes either; mostly copied it from Python). 5 strikes me as a good idea too.

Regarding 2: the role of Templates is really to make it either to encode REX and non-REX variants of the same instruction. In particular, the template may tweak the base encoding's size, name, and constraints (i.e., for non-REX, change register constraints to the set of non-REX registers). This can probably be done in another way that's simpler. Reuniting the concepts of Recipe and Template would be nice, yeah. I've kept them because they had different roles, and having different types made the chance of a misuse less likely.

Regarding 4: I agree writing Rust code in a string is suboptimal. That being said, I would be very careful with procedural macros. This is something we've discussed with @sunfishcode in the past, and I even wondered if all of the meta-code could just be procedural macros in the regular code, or if most of the meta-code could be in procedural macros in the meta code itself. Dan had a great argument that macros may be hard to debug, especially if they're procedural. I've tried to keep the number of macros to a minimum in the meta crate, and it should be easy to debug those because they just do dumb things.

One another idea was to share code between the meta crate and the non-meta crate, that is introduce a new shared crate in the codegen directory. Then, we could maybe move some concepts that are common to both (e.g. struct definition of something belongs in the shared crate, while the meta crate generates the static instances). The emit function could be defined in the shared crate, and be reused by the non-meta crate. I am not sure this will work because of circular dependencies, like meta creates the ir::Types, but the shared crate would probably like to use them. It might be applicable to some extent, though...

[bnjbvr]

I've started working on static references, for what it's worth. Porting immediates and entities was a breeze, now formats are more interesting...

[bjorn3]

Left some commenrs on your branch @bnjbvr.

[bnjbvr]

I've opened bytecodealliance/cranelift#968 which implements the first part for immediates and entityrefs, using lazy_static. @bjorn3 suggested using thread_local, which was a great idea, but implied less convenient ergonomics: in particular, every use must be preceded by a .with() call to make sure the value is properly initialized, while lazy_static does it for us by implementing Deref.

Next part will consist in porting formats. The FormatRegistry holds several roles:

1. be a global context for holding all the formats,
2. allow to infer the actual format when creating an instruction, by looking up the "signature" of the format. That's why it's not necessary to explicitly pass the Format when creating Instructions.
3. make sure that two formats aren't the same, otherwise it would result in dumb code duplication in the non-meta crate.

Note that 2. and 3. imply that we can't just have static Format instances, because they need to be passed around and stored in the FormatRegistry. It also makes the FormatRegistry a global mutable value, which is not great. Here is a proposal to entirely remove the format registry:

1. would be fixed just by using static Format instances.
2. We could pass explicit Formats to instructions. Even if it's a bit cumbersome, doing things explicitly is better, and would make debugging easier (I had to look at generated code sometimes to find what the InstructionFormat of an instruction was). There could be a check in the final builder method to make sure that format and input operands match.
3. When generating code for the formats, we could make a temporary set to make sure that they're not created twice.

Does this seem reasonable to you all?

[abrown]

Makes sense to me; I think point 2 is fine even if more verbose and 3 is reasonable as well.

[abrown]

To add to this thread, one additional re-factor that would be helpful is to __re-organize the legalization groups__. This is similar to the proposed __recipe naming convention__ change above in that it involves re-naming some things in a coherent way. I know that I did not understand how these groups were being used until @bnjbvr explained (https://github.com/CraneStation/cranelift/pull/974#discussion_r324713027) but what I gather from his comment is that a different naming convention is needed.

[jyn514]

I would like to add that building cranelift-codegen takes almost a minute on my i5, is there any way to trim that down? I used cargo -Z timings, which actually just came out today, it has a very good visualization attached below. Most of the time is coming from cranelift-codegen-meta.

timing visualization

all passes that take more than a second (generated with cargo rustc -- -Z time-passes 2>&1 | grep 'time: [^0]' for cranelift-codgen):

  time: 3.828; rss: 349MB       item-bodies checking
  time: 3.355; rss: 625MB       MIR borrow checking
      time: 1.646; rss: 660MB   collecting mono items
    time: 1.654; rss: 660MB     monomorphization collection
  time: 2.042; rss: 700MB       metadata encoding and writing
    time: 1.151; rss: 805MB     codegen passes [42u1gsbvkj1n2who]
    time: 6.603; rss: 707MB     codegen to LLVM IR
  time: 8.951; rss: 707MB       LLVM passes
  time: 9.795; rss: 816MB       codegen
  time: 4.066; rss: 712MB       linking
time: 26.517; rss: 682MB                total

all passes that take more than 1 second for cranelift-codegen-meta:

  time: 1.436; rss: 216MB       item-bodies checking
  time: 1.549; rss: 362MB       MIR borrow checking
      time: 1.022; rss: 409MB   collecting mono items
    time: 1.023; rss: 409MB     monomorphization collection
  time: 1.236; rss: 414MB       metadata encoding and writing
    time: 1.380; rss: 598MB     codegen passes [qkaaqza6jgvrfzz]
    time: 1.173; rss: 615MB     codegen passes [3449uk7s161e6plp]
    time: 5.377; rss: 593MB     codegen to LLVM IR
  time: 6.487; rss: 593MB       LLVM passes
  time: 7.081; rss: 642MB       codegen
time: 12.898; rss: 611MB                total

[bnjbvr]

Thanks @jyn514 for checking this! (I've wished this existed for a long time, to help figuring out what takes the most time in compiling.)

Reducing the number of generic functions could help in one way; avoiding manual lookups "by name" etc. should help for the build step runtime itself. I wonder if with incremental compilation, we could/should split up the meta crates into smaller ones: one for CDSL compiled first, then one for each architecture, so they could be built in parallel.

To wit: one can disable ISA support with features, to slightly reduce compile time. I don't expect this to make a big difference, though, since x86 is likely the one taking most time here.

[jyn514]

I wonder if with incremental compilation, we could/should split up the meta crates into smaller ones

I think you can still get this speedup by using modules instead of crates, which I think we already do.

one can disable ISA support with features, to slightly reduce compile time

I don't know how much of an impact that will have in practice, I have a bad feeling that the macros are taking up most of the time. The author of clap has a good writeup on how macros hide code size.

avoiding manual lookups "by name" etc. should help for the build step runtime itself

I would be interested to see how much of the time is spent on compiling the the runtime vs. actually running code. I've sped up link times in the past by omitting debug info, maybe we could do that for cranelift-codgen-meta?

[bjorn3]

I would be interested to see how much of the time is spent on compiling the the runtime vs. actually running code.

Only ~2s is spend in executing meta when compiled in debug mode.

Edit: ~5s for you @jyn514 it seems.

I've sped up link times in the past by omitting debug info, maybe we could do that for cranelift-codgen-meta?

+1 though I am afraid backtraces will be lost in that case, so maybe enable it somehow when compiling clif_util.

[jyn514]

I am afraid backtraces will be lost in that case

I'm only suggesting this for the meta crate, not for cranelift-codegen. If the meta crate panics we'll notice at compile time so I don't see that being an issue.

[bjorn3]

@jyn514 I mean that cranelift-codegen-meta backtraces are useful during development.

[jyn514]

I see, maybe add a feature to meta for backtraces that's disabled by default and enable it in clif_util?

[bjorn3]

I don't think features can influence compile flags.