Cranelift: add patchable call instructions. (#12101)

* Cranelift: add patchable call instructions.

The new `patchable_call` CLIF instruction pairs with the `patchable`
ABI, and emits a callsite wit

Cranelift: add patchable call instructions. (#12101)

* Cranelift: add patchable call instructions.

The new `patchable_call` CLIF instruction pairs with the `patchable`
ABI, and emits a callsite with one new key property: the MachBuffer
carries metadata that describes exactly which byte range to "NOP out"
(overwrite with NOP instructions) to disable that callsite. Doing so is
semantically valid and explicitly supported.

This enables patching of code at runtime to dynamically turn on and off
features such as instrumentation or debugging hooks. We plan to use this
to implement breakpoints in Wasmtime's guest debugging support.

As part of this change, I added a notion of "unit of NOP bytes" to the
MachBuffer so that the consumer (e.g., Wasmtime's Cranelift-based code
compilation pipeline and metadata-producing logic) can handle patchable
callsites without any other special knowledge of the ISA.

For the "real metal" ISAs there are perfectly well-defined NOPs to use,
but for Pulley, where all opcodes are assigned at compile time by macro
magic, I explicitly defined NOP as opcode byte 0 by moving `Nop`'s
definition to the top of the list and adding a unit test asserting its
encoding.

A design note: in principle it would be possible, as an alternative, to
treat "patchability" as an orthogonal dimension of all callsites, and
emit the metadata describing the instruction-offset range for any
callsite with the flag set. The only truly necessary semantic
restriction is that there are no return values (because if we turn the
callsite off, nothing writes to them); we could support patchability for
other ABIs and for the other kinds of call instructions. The `patchable`
ABI would then be better described as something like the "no clobbers
ABI". I opted not to generalize in this way because it creates some
less-tested corners and the generalized form, at least at the MachInst
level, is not really much simpler in the end.

A testing note: I opted not to implement actual code patching in the
`cranelift-tools` filetest runner and test patching callsites in/out via
some actuation (e.g. a magic hostcall, like we do for throws) because
(i) that's a lot of new plumbing and (ii) we are going to test this very
shortly in Wasmtime anyway and (iii) the correctness (or not) of the
location-and-length metadata is easy enough to verify in the
disassemblies in the compile-tests.

* Review feedback: remove dependence on (and test for) NOP being the literal byte 0.

show more ...

pulley: Reimplement wasm loads/stores & memory opcodes (#10154)

* pulley: Reimplement wasm loads/stores & memory opcodes

This commit is a large refactoring to reimplement how WebAssembly
loads/stor

pulley: Reimplement wasm loads/stores & memory opcodes (#10154)

* pulley: Reimplement wasm loads/stores & memory opcodes

This commit is a large refactoring to reimplement how WebAssembly
loads/stores are translated to Pulley opcodes when using the
interpreter. Additionally the functionality related to memory support
has changed quite a bit with the interpreter as well. This is all based
off comments on #10102 with the end goal of folding the two Pulley
opcodes today of "do the bounds check" and "do the load" into one
opcode. This is intended to reduce the number of opcodes and overall
improve interpreter throughput by minimizing turns of the interpreter
loop.

The basic idea behind this PR is that a new basic suite of loads/stores
are added to Pulley which trap if the address is zero. This provides a
route to translate trapping loads/stores in CLIF to Pulley bytecode
without actually causing segfaults at runtime. WebAssembly translation
to CLIF is then updated to use the `select` trick for wasm loads/stores
where either 0 is loaded from or the actual address is loaded from.
Basic support for translation and such is added for this everywhere, and
this ensures that all loads/stores for wasm will be translated
successfully with Pulley.

The next step was to extend the "g32" addressing mode preexisting in
Pulley to support a bounds check as well. New pattern-matches were added
to ISLE to search for a bounds check in the address of a trapping
load/store. If found then the entire chain of operations necessary to
compute the address are folded into a single "g32" opcode which ends up
being a fallible load/store at runtime.

To fit all this into Pulley this commit contains a number of
refactorings to shuffle around existing opcodes related to memory and
extend various pieces of functionality here and there:

* Pulley now uses a `AddrFoo` types to represent addressing modes as a
single immediate rather than splitting it up into pieces for each
method. For example `AddrO32` represents "base + offset32". `AddrZ`
represents the same thing but traps if the address is zero. The
`AddrG32` mode represents a bounds-checked 32-bit linear memory access
on behalf of wasm.

* Pulley loads/stores were reduced to always using an `AddrFoo`
immediate. This means that the old `offset8` addressing mode was
removed without replacement here (to be added in the future if
necessary). Additionally the suite of sign-extension modes supported
were trimmed down to remove 8-to-64, 16-to-64, and 32-to-64 extensions
folded as part of the opcode. These can of course always be re-added
later but probably want to be added just for the `G32` addressing mode
as opposed to all addressing modes.

* The interpreter itself was refactored to have an `AddressingMode`
trait to ensure that all memory accesses, regardless of addressing
modes, are largely just copy/pastes of each other. In the future it
might make sense to implement these methods with a macro, but for now
it's copy/paste.

* In ISLE the `XLoad` generic instruction removed its `ext` field to
have extensions handled exclusively in ISLE instead of partly in
`emit.rs`.

* Float/vector loads/stores now have "g32" addressing (in addition to
the "z" that's required for wasm) since it was easy to add them.

* Translation of 1-byte accesses on Pulley from WebAssembly to CLIF no
longer has a special case for using `a >= b` instead of `a > b - 1` to
ensure that the same bounds-check instruction can be used for all
sizes of loads/stores.

* The bounds-check which folded a load-of-the-bound into the opcode is
now present as a "g32bne" addressing mode. with its of suite of
instructions to boo.

Overall this PR is not a 1:1 replacement of all previous opcodes with
exactly one opcode. For example loading 8 bits sign-extended to 64-bits
is now two opcodes instead of one. Additionally some previous opcodes
have expanded in size where for example the 8-bit offset mode was remove
in favor of only having 32-bit offsets. The goal of this PR is to reboot
how memory is handled in Pulley. All loads/stores now use a specific
addressing mode and currently all operations supported across addressing
modes are consistently supported. In the future it's expected that some
features will be added to some addressing modes and not others as
necessary, for example extending the "g32" addressing mode only instead
of all addressing modes.

For an evaluation of this PR:

* Code size: `spidermonkey.cwasm` file is reduced from 19M to 16M.
* Sightglass: `pulldown-cmark` is improved by 15%
* Sightglass: `bz2` is improved by 20%
* Sightglass: `spidermonkey` is improved by 22%
* Coremark: score improved by 40%

Overall this PR and new design looks to be a large win. This is all
driven by the reduction in opcodes both for compiled code size and
execution speed by minimizing turns of the interpreter loop. In the end
I'm also pretty happy with how this turned out and I think the
refactorings are well worth it.

* Use new `is_pulley` helper more

* Improve `addrz` helper, tighten up `memory-inbounds.wat` a bit

* Improve codegen in a few `memory-inbounds.wat` cases

* Fix test expectation

show more ...

pulley: Shrink frame save/restore instructions (#9999)

* pulley: Shrink frame save/restore instructions

This commit shrinks the size of the `PushFrameSave` and
`PopFrameRestore` functions which are

pulley: Shrink frame save/restore instructions (#9999)

* pulley: Shrink frame save/restore instructions

This commit shrinks the size of the `PushFrameSave` and
`PopFrameRestore` functions which are used in almost all wasm functions.
Previously these instructions allowed for 32-bits of stack space in
addition to saving/restoring all 32 X-registers. In reality though it's
quite uncommon to need more than 16-bits of stack space and ABI-wise the
most commonly saved registers are the upper 16 registers of the X
register set.

This commit therefore shrinks the frame size to 16 bits and only has the
ability to save/restore the upper 16 X-registers. Note that any
clobbered registers and frame sizes are still supported, they'll just
use more pessimal encodings which aren't a single opcode. If a function
uses >64KiB of stack space though it's probably not too important what
the dispatch cost is at the beginning.

The overall result of this change is that each instruction shaves of 4
bytes (2 from the frame size and 2 from the registers being
saved/restored). This results in a 4% faster execution time on the bz2
Sightglass benchmark, ~1% on pulldown-cmark, and while it shrinks
`spidermonkey.cwasm` slightly it's not significant.

* Remove no-longer-applicable test

* Fix clippy error

* Update test expectations

show more ...

pulley: Add immediate payloads to more opcodes (#9861)

* pulley: Add immediate payloads to more opcodes

This commit adds immediate payloads to the following instructions:

* `xmul32` - `xmul32_s8`

pulley: Add immediate payloads to more opcodes (#9861)

* pulley: Add immediate payloads to more opcodes

This commit adds immediate payloads to the following instructions:

* `xmul32` - `xmul32_s8` / `xmul32_s32`
* `xmul64` - `xmul64_s8` / `xmul64_s32`
* `xband32` - `xband32_s8` / `xband32_s32`
* `xband64` - `xband64_s8` / `xband64_s32`
* `xbor32` - `xbor32_s8` / `xbor32_s32`
* `xbor64` - `xbor64_s8` / `xbor64_s32`
* `xbxor32` - `xbxor32_s8` / `xbxor32_s32`
* `xbxor64` - `xbxor64_s8` / `xbxor64_s32`
* `xshl32` - `xshl32_u6`
* `xshl64` - `xshl64_u6`
* `xshr32_u` - `xshl32_u_u6`
* `xshr64_u` - `xshl64_u_u6`
* `xshr32_s` - `xshl32_s_u6`
* `xshr64_s` - `xshl64_s_u6`

For shifts there's no need to have 32-bit immediates (or even 8-bit)
since 6 bits is enough to encode all the immediates. This means that the
6-bit immediate is packed within `BinaryOperands` as a new `U6` type.

This commit unfortunately does not shrink `spidermonkey.cwasm`
significantly beyond the prior 29M. This is nevertheless expected to be
relatively important for performance.

* Fix test expectations

show more ...

pulley: Initial scaffold of SIMD support (#9820)

* pulley: Initial scaffold of SIMD support

This commit fills out some of the initial infrastructure necessary for
supporting the SIMD proposal to W

pulley: Initial scaffold of SIMD support (#9820)

* pulley: Initial scaffold of SIMD support

This commit fills out some of the initial infrastructure necessary for
supporting the SIMD proposal to WebAssembly in the Pulley interpreter,
namely 128-bit simd. The `VRegVal` union has been filled out with
various types, endianness questions are settled, and initial
implementations of a suite of opcodes are added to get a basic set of
tests working throughout the backend.

cc #9783

* Avoid dealing with big-endian vectors

* Change wasm `global`s to store `v128` in little-endian format.
* Change pulley stack loads/stores to work with vectors in little-endian
format.

show more ...

pulley: Track faulting opcode in stack overflow better (#9735)

* pulley: Track faulting opcode in stack overflow better

This commit updates the pulley `Encode` trait to have a `WIDTH`
associated wi

pulley: Track faulting opcode in stack overflow better (#9735)

* pulley: Track faulting opcode in stack overflow better

This commit updates the pulley `Encode` trait to have a `WIDTH`
associated with it to be able to calculate the size of an instruction by
name rather than hard-coding instruction details in multiple locations.
This constant is procedurally generated per-instruction given the
definition of the instruction. This for now assumes there are no
variable-width instructions.

* Fix tests

* Fix feature'd build

show more ...

pulley: superinstructions for pushing/popping list of registers (#9099)

* pulley: add `push` and `pop` instructions

Add `xpush{32, 64}` and `xpop{32, 64}` for pushing/popping XRegs from the stack,

pulley: superinstructions for pushing/popping list of registers (#9099)

* pulley: add `push` and `pop` instructions

Add `xpush{32, 64}` and `xpop{32, 64}` for pushing/popping XRegs from the stack,
and `push_frame`/`pop_frame` for saving/restoring LR and FP in function
prologue/epilogue.

Copyright (c) 2024, Arm Limited.

Signed-off-by: Karl Meakin <[email protected]>

* cranelift-bitset: more impls for `ScalarBitset`

Implement `Arbitrary` for `ScalarBitset`.

Also implement `DoubleEndedIterator` and `ExactSizeIterator` for `Iter`.
The `pop_min` method was added to help implement `DoubleEndedIterator`,
and `pop` was renamed to `pop_max` for consistency.

Copyright (c) 2024, Arm Limited.

Signed-off-by: Karl Meakin <[email protected]>

* pulley: add instructions for pushing/popping list of registers

Add `xpush{32,64}_many` and `xpop{32,64}_many` for pushing/popping any
combination of all 32 XRegs.

Copyright (c) 2024, Arm Limited.

Signed-off-by: Karl Meakin <[email protected]>

---------

Signed-off-by: Karl Meakin <[email protected]>

show more ...

pulley: pack `dst`, `src1` and `src2` registers into 2 bytes (#9088)

* pulley: use enums for `{X,F,V}Reg`

Copyright (c) 2024, Arm Limited.

Signed-off-by: Karl Meakin <[email protected]>

* pulle

pulley: pack `dst`, `src1` and `src2` registers into 2 bytes (#9088)

* pulley: use enums for `{X,F,V}Reg`

Copyright (c) 2024, Arm Limited.

Signed-off-by: Karl Meakin <[email protected]>

* pulley: add `BinaryOperands`

Copyright (c) 2024, Arm Limited.

Signed-off-by: Karl Meakin <[email protected]>

* pulley: use `BinaryOperands` for binary operators

Copyright (c) 2024, Arm Limited.

Signed-off-by: Karl Meakin <[email protected]>

---------

Signed-off-by: Karl Meakin <[email protected]>

show more ...

Introduce the `pulley-interpreter` crate (#9008)

* Introduce the `pulley-interpreter` crate

This commit is the first step towards implementing
https://github.com/bytecodealliance/rfcs/pull/35

This

Introduce the `pulley-interpreter` crate (#9008)

* Introduce the `pulley-interpreter` crate

This commit is the first step towards implementing
https://github.com/bytecodealliance/rfcs/pull/35

This commit introduces the `pulley-interpreter` crate which contains the Pulley
bytecode definition, encoder, decoder, disassembler, and interpreter.

This is still very much a work in progress! It is expected that we will tweak
encodings and bytecode definitions, that we will overhaul the interpreter (to,
for example, optionally support the unstable Rust `explicit_tail_calls`
feature), and otherwise make large changes. This is just a starting point to get
the ball rolling.

Subsequent commits and pull requests will do things like add the Cranelift
backend to produce Pulley bytecode from Wasm as well as the runtime integration
to run the Pulley interpreter inside Wasmtime.

* remove stray fn main

* Add small tests for special x registers

* Remove now-unused import

* always generate 0 pc rel offsets in arbitrary

* Add doc_auto_cfg feature for docs.rs

* enable all optional features for docs.rs

* Consolidate `BytecodeStream::{advance,get1,get2,...}` into `BytecodeStream::read`

* fix fuzz targets build

* inherit workspace lints in pulley's fuzz crate

* Merge fuzz targets into one target; fix a couple small fuzz bugs

* Add Pulley to our cargo vet config

* Add pulley as a crate to publish

* Move Pulley fuzz target into top level fuzz directory

show more ...