Overloading of RMW and wait operations

[tlively]

As @rossberg brought up in #110 (review) and as we discussed at the recent CG meeting, the current design overloads the new RMW and wait operations to work with several types. For example struct.atomic.rmw.add x y works on both i32 and i64 fields. This does not violate our principal types properties because the type of the field is determined by the type and field immediates x and y. However, the execution of the instruction needs to handle addition on both i32 and i64 fields in a way we have historically avoided, by e.g. making i32.add and i64.add separate instructions. (Although it is the case that separating i32.add and i64.add is necessary to preserve principal types as well.)

The "no overloading" rule is also already somewhat fuzzy in practice. Instructions like ref.is_null are parametric over all heap types, so need to handle comparisons with potentially different null values and representations for each heap type hierarchy. Instructions like struct.get obviously have different implementations for different field types in real implementations, even if the spec can be written to handle all types generically.

So I argue that the "no overloading" rule is not buying us much in practice, and it would be well worth dropping it to reduce the need to introduce dozens of new instructions. We won't immediately descend into chaos because we still have the principal types properties imposing order on the instruction set.

In the CG meeting, @titzer raised the point that in-place interpreters need to do extra work when instructions are overloaded. @kmiller68 said he would have to go see how this would affect the JSC interpreter. My question is: given that these interpreters already have to handle e.g. struct.get, is it really worth adding dozens of instructions to save them this work on instructions that will be much less common than struct.get?

[rossberg]

I think the deferral to principal types is missing the point a bit. The principal types principle exists for the sake of validation. The no overloading principle exists — as far as I'm concerned — for the sake of execution. It's the principle that "different" operations are different instructions. And two operations are "different" if they actually need to apply different interpretations of a value.

That principle helps e.g. interpreters, because it minimises type lookup at runtime (for something like struct.atomic.rmw, the type information may be multiple indirections away). It is a fair point that they already have to do some of that for certain parametric operations, and the boundary is fuzzy(*). But that alone does not make the principle useless. Having to rewrite some instructions like @titzer explained is not great. But having to rewrite more instructions is of course worse. (Just consider the limit: if an interpreter had to rewrite all instructions, could it still be considered an interpreter instead of a jit?)

PS: And that is assuming all interpreters have the luxury of code mutation, which of course won't be the case.

(*) In the abstract, the qualitative difference with parametric operations is that those do not interpret the value. They only need to know the size of a value. Value sizes, in general, are implementation-dependent, so whether two instances of a parametric op are "different" is more like an implementation detail, unlike with overloaded ops. In theory, an interpreter could use a "uniform" representation to avoid the problem (@titzer, didn't Wizard essentially do that for locals, by using 128 bits for every stack slot?).

[titzer]

I agree the overloading line seems fuzzy, but there is still a red line at using operand stack types to disambiguate execution: no operation currently depends on the type of an operand stack slot alone at runtime, unless, as Andreas says, it is fully parametric. All instructions we have now that work on multiple types have some part of the static context that disambiguates the type: the function context for local.get, the control stack for br, the module context for call, etc. The only parametric instructions we have are select and drop. Those instructions already force an interpreter to move "slot-to-slot", which means using tagged values (i.e. a universal representation) without knowing the specific representation of a value. (It would require recording operand stack types from validation to specialize these--i.e. using a sidetable entry).

The instructions in question fall into the same category as struct.get; the static information needed at runtime to choose which machine load (or read-modify-write) operation is a couple indirections away, through the instance, to the module, the struct declaration, to the field declaration. That's already not great; Wizard is currently very slow in the interpreter for these instructions. Two options to make, e.g. struct.get faster are a sidetable entry (field_offset + machine_rep) which then still requires a secondary dispatch on the machine type, or to use an internal opcode which encodes the machine_rep with an immediate that represents the offset (e.g. internal_struct_get_i32 [offset]). Rewriting the actual bytecode in-place is possible (struct.get is minimum 4 bytes) but tricky and really complicates other things.

In Wizard we are now sadly doing one cheat to make memory64 faster: we steal one of the reserved bits of the flags byte for all memory access instructions that have it to indicate whether the memory is 64-bit or not. This information would otherwise only be available through the chain of instance->memories[memory_index].addrType, necessitating three more loads (!). Instead, Wizard's code validator flips the reserved bit in-place in the instruction for 64-bit memories. That means that accidentally not flipping the bit results in incorrectly treating it like a 32-bit access...which is incorrect. A sidetable entry here would probably be OK, but not great for space, as memory accesses are super common.

These cheats are pretty gross and I'm not sure we need to be saving the opcode space at this point. We already allocated 250+ instructions to SIMD and ~65ish for atomics--which already have the size of RMW operations built into the opcode.

didn't Wizard essentially do that for locals, by using 128 bits for every stack slot?.

They are actually 256 bits (32 bytes), because we use a 1-byte value tag for GC. Otherwise computing stack maps for the operand stack would negate the startup advantage of the interpreter. (We could lazily compute them, but that's likely to be a bug farm). If Wizard is configured to disable SIMD and stack-switching, it goes back to using 128 bits per slot (64bits + value tag). The cost is 3-5% for the really fat values on the stack. Disabling value tags altogether, for reference, is about 5-11% execution time gain in the interpreter.

[tlively]

@Liedtke made a good point to me offline, which is that we also currently use immediates rather than opcodes to control memory orders, i.e. whether an operation should be sequentially consistent or acquire/release. That seems like it would fall into the same category as using struct field immediates to determine what RMW operations should do. "Fixing" this would require doubling the number of new instructions again, plus more for all the existing atomic accesses that would need to be duplicated. That would be over 100 additional instructions.

[rossberg]

Immediates are part of the instruction, as far as I'm concerned. What differs is whether behaviour depends on out-of-band type information that needs to be inferred or looked up elsewhere. Though I think we all agree that the line is a bit fuzzy.

[tlively]

Other instructions that require out-of-band information for something as basic as determining how many values to pop include all of the branch instructions, return, all of the call instructions, struct.new, throw, and most of the new stack switching instructions. Whatever "no overloading" has meant in practice, I don't think we've ever considered a distinction between in-band and out-of-band information from immediates.

[tlively]

@rossberg, is there a way to formalize the "no overloading" property in such a way that we could put it in an appendix, like we have with the principal types properties? That would help clear my objection to adding new instructions. Without that, it's not clear that we have a "no overloading" property in practice (beyond what we get for free from principal types), so I don't see why we would add the extra instructions here.

[rossberg]

@tlively, it is a property of the execution semantics, so it is a constraint on the form that execution rules can take.

Concretely, it means that a rule should never have to "dispatch" on a value type that is looked up in the store, either directly or by using it for a "static" parameter (subscript) to a primitive. (For auxiliary functions, the spec carefully distinguishes between regular runtime parameters, and "static" ones that select one of many instantiations, similar to a template parameter. The latter ones are written as subscripts.)

In theory it should be possible to formalise this as either an information flow property (value types in the store are hi, while values are lo), or more directly as a type erasure property (we can erase/abstract value type information from the store without affecting the execution rules). But not sure if it's worth it.