This will, at least on x86_64, compile down to simpler, shorter assembly that uses a zeroed allocation instead of a regular allocation, a memset and various `raw_vec` methods.
* Make regalloc2 `#![no_std]`
This crate doesn't require any features from the standard library, so it
can be made `no_std` to allow it to be used in environments that can't
use the Rust standard library.
This PR mainly performs the following mechanical changes:
- `std::collections` is replaced with `alloc::collections`.
- `std::*` is replaced with `core::*`.
- `Vec`, `vec!`, `format!` and `ToString` are imported when needed since
they are no longer in the prelude.
- `HashSet` and `HashMap` are taken from the `hashbrown` crate, which is
the same implementation that the standard library uses.
- `FxHashSet` and `FxHashMap` are typedefs in `lib.rs` that are based on
the `hashbrown` types.
The only functional change is that `RegAllocError` no longer implements
the `Error` trait since that is not available in `core`.
Dependencies were adjusted to not require `std` and this is tested in CI
by building against the `thumbv6m-none-eabi` target that doesn't have
`std`.
* Add the Error trait impl back under a "std" feature
* Re-introduce optional dedicated scratch registers
Dedicated scratch registers used for resolving move cycles were removed
in #51 and replaced with an algorithm to automatically allocate a
scratch register as needed.
However in many cases, a client will already have a non-allocatable
scratch register available for things like extended jumps (see #91). It
makes sense to re-use this register for regalloc than potentially
spilling an existing register.
* Clarify comment
* Use a while-let instead of checking is_empty and popping
* This conditional should always be true, as we expect the input is in ssa
* Use iter_mut instead of iterating the index
* We don't support multiple defs of the same vreg anymore
* Drain instead of clear
The checker works by keeping a worklist of blocks to process, and adds a
block to the worklist when its entry state changes. Every entry state is
initially `Top` (in a lattice). The entry block is explicitly added to
the worklist to kick off the processing.
In ordinary cases, the entry block has some instructions that change
state from `Top` to something else (lower in the lattice), and this is
propagated to its successors; its successors are added to the worklist;
and so on. No other state is `Top` from then on (because of
monotonicity) so every reachable block is processed.
However, if the entry block is completely empty except for the
terminating branch, the state remains `Top`; then the entry state of its
successors, even when updated, is still `Top`; and the state didn't
change so the blocks are not added to the worklist. (Nevermind that they
were not processed in the first place!) The bug is that the invariant
"has been processed already with current state" is not true initially,
when the current state is set to `Top` but nothing has been processed.
This PR makes a simple fix: it adds every block to the worklist
initially to be processed, in input order (which is usually RPO order in
practice) as a good first heuristic; then if after processing the input
state changes again, it can be reprocessed until fixpoint as always.
Fixesbytecodealliance/wasmtime#5791.
In #108, we had removed a conditional that became constant-false with
the removal of pinned vregs. Unfortunately, in a pretty embarrassing
text-editing error, I removed the wrong end-brace and re-indented. This
had the effect of moving some of the move-resolution code around in the
regalloc backend, skipping moves in some cases and generating incorrect
results.
Caught as a fuzzbug by OSS-Fuzz in [0] (public after this merges and is
detected as fixed).
[0]: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=55391
* Use maximum inline capacity available for `SmallVec<VRegIndex>` in `SpillSet`
We were using 2, which is the maximum for 32-bit architectures, but on 64-bit
architectures we can get 4 inline elements without growing the size of the
`SmallVec`.
This is a statistically significant speed up, but is so small that our
formatting of floats truncates it (so less than 1%).
```
compilation :: instructions-retired :: benchmarks/bz2/benchmark.wasm
Δ = 3360297.85 ± 40136.18 (confidence = 99%)
more-inline-capacity.so is 1.00x to 1.00x faster than main.so!
[945563401 945906690.73 946043245] main.so
[942192473 942546392.88 942729104] more-inline-capacity.so
compilation :: instructions-retired :: benchmarks/pulldown-cmark/benchmark.wasm
Δ = 1780540.13 ± 39362.84 (confidence = 99%)
more-inline-capacity.so is 1.00x to 1.00x faster than main.so!
[1544990595 1545359408.41 1545626251] main.so
[1543269057 1543578868.28 1543851201] more-inline-capacity.so
compilation :: instructions-retired :: benchmarks/spidermonkey/benchmark.wasm
Δ = 36577153.54 ± 243753.54 (confidence = 99%)
more-inline-capacity.so is 1.00x to 1.00x faster than main.so!
[33956158997 33957780594.50 33959538220] main.so
[33919762415 33921203440.96 33923023358] more-inline-capacity.so
```
* Use a `const fn` to calculate number of inline elements
