PCC: remove proof-carrying code (for now?). (#12800)

In late 2023, we built out an experimental feature called
Proof-Carrying Code (PCC), where we attached "facts" to values in the
CLIF IR and built

PCC: remove proof-carrying code (for now?). (#12800)

In late 2023, we built out an experimental feature called
Proof-Carrying Code (PCC), where we attached "facts" to values in the
CLIF IR and built verification of these facts after lowering to
machine instructions. We also added "memory types" describing layout
of memory and a "checked" flag on memory operations such that we could
verify that any checked memory operation accessed valid memory (as
defined by memory types attached to pointer values via
facts). Wasmtime's Cranelift backend then put appropriate memory types
and facts in its IR such that all accesses to memory (aspirationally)
could be checked, taking the whole mid-end and lowering backend of
Cranelift out of the trusted core that enforces SFI.

This basically worked, at the time, for static memories; but never for
dynamic memories, and then work on the feature lost
prioritization (aka I had to work on other things) and I wasn't able
to complete it and put it in fuzzing/enable it as a production option.

Unfortunately since then it has bit-rotted significantly -- as we add
new backend optimizations and instruction lowerings we haven't kept
the PCC framework up to date.

Inspired by the discussion in #12497 I think it's time to delete
it (hopefully just "for now"?) unless/until we can build it again. And
when we do that, we should probably get it to the point of validating
robust operation on all combinations of memory configurations before
merging. (That implies a big experiment branch rather than a bunch of
eager PRs in-tree, but so it goes.) I still believe it is possible to
build this (and I have ideas on how to do it!) but not right now.

show more ...

Partial support for no_std in cranelift_codegen (#12222)

* Move most things from std to core and alloc

* Port assembler_x64 to no_std

* before adding prelude to each file

* Most of the files now

Partial support for no_std in cranelift_codegen (#12222)

* Move most things from std to core and alloc

* Port assembler_x64 to no_std

* before adding prelude to each file

* Most of the files now work with no_std

* update isle to use alloc and core

* some instances shouldn't have been renamed, fixes cargo test

* add cranelift-assembler-x64 (no_std) to CI

* fix codegen_meta, missed one spot with std::slice

* automatically remove prelude with cargo fix

* update isle changes

* update assembler changes

* update assembler changes

* use latest codegen changes + fix FxHash problem

* add imports

* fix floating issues with libm

* remove unused import

* temporarily remove OnceLock

* add no_std arm support and add it into CI

* Move most things from std to core and alloc

* Port assembler_x64 to no_std

* before adding prelude to each file

* Most of the files now work with no_std

* update isle to use alloc and core

* some instances shouldn't have been renamed, fixes cargo test

* add cranelift-assembler-x64 (no_std) to CI

* automatically remove prelude with cargo fix

* update isle changes

* update assembler changes

* update assembler changes

* use latest codegen changes + fix FxHash problem

* add imports

* fix floating issues with libm

* remove unused import

* temporarily remove OnceLock

* add no_std arm support and add it into CI

* Move most things from std to core and alloc

* Port assembler_x64 to no_std

* before adding prelude to each file

* Most of the files now work with no_std

* update isle to use alloc and core

* add cranelift-assembler-x64 (no_std) to CI

* automatically remove prelude with cargo fix

* update isle changes

* update assembler changes

* use latest codegen changes + fix FxHash problem

* add imports

* fix floating issues with libm

* temporarily remove OnceLock

* add no_std arm support and add it into CI

* revert Cargo.toml formating

* remove prelude and fix cargo.toml

* cargo fmt

* remove empty lines

* bad renames

* macro_use only on no_std

* revert OnceLock change

* only use stable libm features

* update regalloc2

* update comment

* use continue instead

* Update vets

---------

Co-authored-by: Alex Crichton <[email protected]>

show more ...

cranelift-codegen: rename most uses of std to core and alloc (#12237)

* rename most std uses to core and alloc

* cargo fmt

Cranelift: add get_exception_handler_address. (#11629)

* Cranelift: add get_exception_handler_address.

This is designed to enable applications such as #11592 that use
alternative unwinding mechanis

Cranelift: add get_exception_handler_address. (#11629)

* Cranelift: add get_exception_handler_address.

This is designed to enable applications such as #11592 that use
alternative unwinding mechanisms that may not necessarily want to walk a
stack and look up exception tables. The idea is that whenever it would
be valid to resume to an exception handler that is active on the stack,
we can provide the same PC as a first-class runtime value that would be
found in the exception table for the given handler edge. A "custom"
resume step can then use this PC as a resume-point as long as it follows
the relevant exception ABI (i.e.: restore SP, FP, any other saved
registers that the exception ABI specifies, and provide appropriate
payload value(s)).

Handlers are associated with edges out of `try_call`s (or
`try_call_indirect`s); and edges specifically, not blocks, because there
could be multiple out-edges to one block. The instruction thus takes the
block that contains the try-call and an immediate that indexes its
exceptional edges.

This CLIF instruction required a bit of infrastructure to (i) allow
naming raw blocks, not just block calls, as instruction arguments, and
(ii) allow getting the MachLabel for any other lowered block during
lowering. But given that, the lowerings themselves are straightforward
uses of MachBuffer labels to fix-up PC-relative address-loading
instructions (e.g., `LEA` or `ADR` or `AUIPC`+`ADDI`).

* Review feedback.

* Review feedback: more tests.

show more ...

Update Wasmtime to the 2024 Rust Edition (#10806)

* Update Wasmtime to the 2024 Rust Edition

Now that our MSRV supports the 2024 edition it's possible to make this
switch. This commit moves Wasmtim

Update Wasmtime to the 2024 Rust Edition (#10806)

* Update Wasmtime to the 2024 Rust Edition

Now that our MSRV supports the 2024 edition it's possible to make this
switch. This commit moves Wasmtime to the 2024 Edition to keep
up-to-date with Rust idioms and access many of the edition features
exclusive to the 2024 edition.

prtest:full

* Reformat with the 2024 edition

show more ...

Cranelift: fix invalid regalloc constraints on try-call with empty handler list. (#10709)

(Reported by bjorn3 -- thanks!)

We handle edge splitting for regalloc moves in a way that is designed to
sp

Cranelift: fix invalid regalloc constraints on try-call with empty handler list. (#10709)

(Reported by bjorn3 -- thanks!)

We handle edge splitting for regalloc moves in a way that is designed to
split minimally (for compiler performance and codegen quality): we only
split edges that are truly critical, i.e., come from a block with more
than one successor and go to a block with more than one predecessor.
In all other cases, there is always a place for these moves to go: if a
block only has one successor, then edge-moves can go before its jump;
and if a block only has one predecessor, then edge-moves can go at the
beginning of that block (before the blockparams' parallel-move). The
former case -- before the branch -- works because of a restriction that
regalloc2 imposes: branches with only one target (that is, unconditional
branches) cannot have any arguments. Otherwise, those uses would occur
after the edge-moves have already shuffled the register state into a
state suitable for the next block. Violating this constraint leads to a
panic.

With ordinary unconditional branches, this is no problem. With
`try_call`s with at least one handler listed, this is also no problem:
such a terminator is seen as a branch with (at least) two targets by
regalloc, so no edge-moves are placed before it, so it's allowed to have
arguments, such as the arguments to the call itself. However, a
`try_call` with *no* handler clauses, though pathological, appears to
regalloc as an unconditional branch and so should not have any
arguments. The included test-case triggers this issue with such a
`try_call` together with a normal-return target branch that has more
than one incoming edge, forcing the location for the moves into the
`try_call`'s block. (The lack of actual edge-moves doesn't matter -- RA2
performs the check on the IR restriction first.) The result is a panic
at compile time.

This PR fixes the issue by extending a similar fix for `br_table`s
(which can trigger a very similar bug if they have only the default
case, i.e., one target) to `try_call{,_indirect}` as well: the
lowered-block order computation, where edge-splits are determined,
pretends that they always have at least two successors. This ensures
that edges will be split as necessary, satisfying the
no-arguments-to-unconditional-terminators restriction.

show more ...

Cranelift: remove block params on critical-edge blocks. (#10485)

When a block has a terminator branch that targets two or more other
blocks at the CLIF level, and any of these blocks have two or mor

Cranelift: remove block params on critical-edge blocks. (#10485)

When a block has a terminator branch that targets two or more other
blocks at the CLIF level, and any of these blocks have two or more
precessors, the edge is a "critical edge" and we split it (insert a
new empty block) so that the register allocator has a place to put
moves that happen only on that edge. Otherwise, there is no location
that works: in the predecessor, code runs no matter which outgoing
edge we take; and in the successor, code runs no matter which incoming
edge we came from.

Currently, when we generate these critical-edge blocks, we insert
exactly one instruction: an unconditional branch. We wire up the
blockparam dataflow by (i) adding block parameters to the
critical-edge block with the same signature as the original target,
and (ii) adding all of these arguments to the unconditional branch. In
other words, we maintain the original block signature throughout.

This is fine and correct, but it has two downsides. The first is a
minor loss in compile-time efficiency (more SSA values and
block-params to process). The second, more interesting, is that it
hinders future work with certain kinds of branches that may define
values *on edges*.

In particular, this approach prevents exception-handling support: a
`try_call` instruction that acts as a terminator branch (with
normal-return and exceptional out-edges) defines normal-return values
as block-call arguments that are usable on the normal-return
edge. Some of these normal-return values may be defined by loads from
a return-value area. These loads need somewhere to go; they can't go
"after the terminator" (then it wouldn't be a terminator), so they go
in an edge block; as a result, the block-call for the normal-return
needs to use its arguments only in the unconditional branch out of the
edge block, not in the initial branch to the edge block.

This PR alters the critical-edge blockparam handling to have no
block-call args on the branch into the edge block, and use the
original values (not the newly defined edge-block blockparams) in the
block-call out of the edge block. This will allow these values to be
possibly defined in the edge block rather than in the predecessor (the
block with the original terminator).

This has no functional change today other than some perturbation of
regalloc decisions and a possibly slight compile-time speedup.

show more ...

loop analysis simplification (#9613)

* loop analysis simplification

* add iterator over reverse post order

* review comments

* review comments

* use rpo iterator where possible

* make use of sa

loop analysis simplification (#9613)

* loop analysis simplification

* add iterator over reverse post order

* review comments

* review comments

* use rpo iterator where possible

* make use of same struct access pattern throughout

* use new directly instead of calling macro

show more ...

Enforce `clippy::clone_on_copy` for the workspace (#9025)

* Derive `Copy` for `Val`

* Fix `clippy::clone_on_copy` for the whole repo

* Enforce `clippy::clone_on_copy` for the workspace

* fix some

Enforce `clippy::clone_on_copy` for the workspace (#9025)

* Derive `Copy` for `Val`

* Fix `clippy::clone_on_copy` for the whole repo

* Enforce `clippy::clone_on_copy` for the workspace

* fix some more clippy::clone_on_copy that got missed

show more ...

Fix some typos (#8641)

* occurred

* winch typos

* tests typos

* cli typos

* fuzz typos

* examples typos

* docs typos

* crates/wasmtime typos

* crates/environ typos

* crates/cranelift typos

Fix some typos (#8641)

* occurred

* winch typos

* tests typos

* cli typos

* fuzz typos

* examples typos

* docs typos

* crates/wasmtime typos

* crates/environ typos

* crates/cranelift typos

* crates/test-programs typos

* crates/c-api typos

* crates/cache typos

* crates other typos

* cranelift/codegen/src/isa typos

* cranelift/codegen/src other typos

* cranelift/codegen other typos

* cranelift other typos

* ci js typo

* .github workflows typo

* RELEASES typo

* Fix clang-format documentation line

---------

Co-authored-by: Andrew Brown <[email protected]>

show more ...

Fxhash to rustchash (#8498)

* move fx hash to workspace level dep

* change internal fxhash to use fxhash crate

* remove unneeded HashSet import

* change fxhash crate to rustc hash

* undo migrat

Fxhash to rustchash (#8498)

* move fx hash to workspace level dep

* change internal fxhash to use fxhash crate

* remove unneeded HashSet import

* change fxhash crate to rustc hash

* undo migration to rustc hash

* manually implement hash function from fxhash

* change to rustc hash

show more ...

Update some CI dependencies (#7983)

* Update some CI dependencies

* Update to the latest nightly toolchain
* Update mdbook
* Update QEMU for cross-compiled testing
* Update `cargo nextest` for usag

Update some CI dependencies (#7983)

* Update some CI dependencies

* Update to the latest nightly toolchain
* Update mdbook
* Update QEMU for cross-compiled testing
* Update `cargo nextest` for usage with MIRI

prtest:full

* Remove lots of unnecessary imports

* Downgrade qemu as 8.2.1 seems to segfault

* Remove more imports

* Remove unused winch trait method

* Fix warnings about unused trait methods

* More unused imports

* More unused imports

show more ...

fuzz: randomize block lowering order (#6254)

* fuzz: randomize block lowering order

Co-authored-by: Moritz Waser <[email protected]>
Co-authored-by: Remo Senekowitsch <[email protected]>

* fix block

fuzz: randomize block lowering order (#6254)

* fuzz: randomize block lowering order

Co-authored-by: Moritz Waser <[email protected]>
Co-authored-by: Remo Senekowitsch <[email protected]>

* fix block lowering order randomization

Co-authored-by: Falk Zwimpfer <[email protected]>
Co-authored-by: Moritz Waser <[email protected]>

* simplify control plane internals

Co-authored-by: Falk Zwimpfer <[email protected]>
Co-authored-by: Moritz Waser <[email protected]>

* avoid unnecessary allocations

Co-authored-by: Falk Zwimpfer <[email protected]>
Co-authored-by: Moritz Waser <[email protected]>

* remove unused change_order function

Co-authored-by: Falk Zwimpfer <[email protected]>
Co-authored-by: Moritz Waser <[email protected]>

* add arbitrary 1.3.0 to cargo vet imports lock

Co-authored-by: Falk Zwimpfer <[email protected]>
Co-authored-by: Moritz Waser <[email protected]>

* optimize ControlPlane::shuffle

Co-authored-by: Falk Zwimpfer <[email protected]>
Co-authored-by: Moritz Waser <[email protected]>

* clarify shuffle being a noop without chaos mode

Co-authored-by: Falk Zwimpfer <[email protected]>
Co-authored-by: Moritz Waser <[email protected]>

* reorder only direct successors of a block

Co-authored-by: Falk Zwimpfer <[email protected]>
Co-authored-by: Moritz Waser <[email protected]>

* rename get_permutation -> shuffled

Co-authored-by: Falk Zwimpfer <[email protected]>
Co-authored-by: Moritz Waser <[email protected]>

---------

Co-authored-by: Falk Zwimpfer <[email protected]>
Co-authored-by: Moritz Waser <[email protected]>

show more ...

refactor BlockLoweringOrder::new (#6255)

Co-authored-by: Falk Zwimpfer <[email protected]>
Co-authored-by: Moritz Waser <[email protected]>

Reuse the DominatorTree postorder travesal in BlockLoweringOrder (#5843)

* Rework the blockorder module to reuse the dom tree's cfg postorder

* Update domtree tests

* Treat br_table with an empty

Reuse the DominatorTree postorder travesal in BlockLoweringOrder (#5843)

* Rework the blockorder module to reuse the dom tree's cfg postorder

* Update domtree tests

* Treat br_table with an empty jump table as multiple block exits

* Bless tests

* Change branch_idx to succ_idx and fix the comment

show more ...

cranelift: Remove brz and brnz (#5630)

Remove the brz and brnz instructions, as their behavior is now redundant with brif.

Make DataFlowGraph::insts public, but restricted (#5450)

We have some operations defined on DataFlowGraph purely to work around borrow-checker issues with InstructionData and other data on DataFlowG

Make DataFlowGraph::insts public, but restricted (#5450)

We have some operations defined on DataFlowGraph purely to work around borrow-checker issues with InstructionData and other data on DataFlowGraph. Part of the problem is that indexing the DFG directly hides the fact that we're only indexing the insts field of the DFG.

This PR makes the insts field of the DFG public, but wraps it in a newtype that only allows indexing. This means that the borrow checker is better able to tell when operations on memory held by the DFG won't conflict, which comes up frequently when mutating ValueLists held by InstructionData.

show more ...

Initial forward-edge CFI implementation (#3693)

* Initial forward-edge CFI implementation

Give the user the option to start all basic blocks that are targets
of indirect branches with the BTI in

Initial forward-edge CFI implementation (#3693)

* Initial forward-edge CFI implementation

Give the user the option to start all basic blocks that are targets
of indirect branches with the BTI instruction introduced by the
Branch Target Identification extension to the Arm instruction set
architecture.

Copyright (c) 2022, Arm Limited.

* Refactor `from_artifacts` to avoid second `make_executable` (#1)

This involves "parsing" twice but this is parsing just the header of an
ELF file so it's not a very intensive operation and should be ok to do
twice.

* Address the code review feedback

Copyright (c) 2022, Arm Limited.

Co-authored-by: Alex Crichton <[email protected]>

show more ...

Implement an incremental compilation cache for Cranelift (#4551)

This is the implementation of https://github.com/bytecodealliance/wasmtime/issues/4155, using the "inverted API" approach suggested b

Implement an incremental compilation cache for Cranelift (#4551)

This is the implementation of https://github.com/bytecodealliance/wasmtime/issues/4155, using the "inverted API" approach suggested by @cfallin (thanks!) in Cranelift, and trait object to provide a backend for an all-included experience in Wasmtime.

After the suggestion of Chris, `Function` has been split into mostly two parts:

- on the one hand, `FunctionStencil` contains all the fields required during compilation, and that act as a compilation cache key: if two function stencils are the same, then the result of their compilation (`CompiledCodeBase<Stencil>`) will be the same. This makes caching trivial, as the only thing to cache is the `FunctionStencil`.
- on the other hand, `FunctionParameters` contain the... function parameters that are required to finalize the result of compilation into a `CompiledCode` (aka `CompiledCodeBase<Final>`) with proper final relocations etc., by applying fixups and so on.

Most changes are here to accomodate those requirements, in particular that `FunctionStencil` should be `Hash`able to be used as a key in the cache:

- most source locations are now relative to a base source location in the function, and as such they're encoded as `RelSourceLoc` in the `FunctionStencil`. This required changes so that there's no need to explicitly mark a `SourceLoc` as the base source location, it's automatically detected instead the first time a non-default `SourceLoc` is set.
- user-defined external names in the `FunctionStencil` (aka before this patch `ExternalName::User { namespace, index }`) are now references into an external table of `UserExternalNameRef -> UserExternalName`, present in the `FunctionParameters`, and must be explicitly declared using `Function::declare_imported_user_function`.
- some refactorings have been made for function names:
- `ExternalName` was used as the type for a `Function`'s name; while it thus allowed `ExternalName::Libcall` in this place, this would have been quite confusing to use it there. Instead, a new enum `UserFuncName` is introduced for this name, that's either a user-defined function name (the above `UserExternalName`) or a test case name.
- The future of `ExternalName` is likely to become a full reference into the `FunctionParameters`'s mapping, instead of being "either a handle for user-defined external names, or the thing itself for other variants". I'm running out of time to do this, and this is not trivial as it implies touching ISLE which I'm less familiar with.

The cache computes a sha256 hash of the `FunctionStencil`, and uses this as the cache key. No equality check (using `PartialEq`) is performed in addition to the hash being the same, as we hope that this is sufficient data to avoid collisions.

A basic fuzz target has been introduced that tries to do the bare minimum:

- check that a function successfully compiled and cached will be also successfully reloaded from the cache, and returns the exact same function.
- check that a trivial modification in the external mapping of `UserExternalNameRef -> UserExternalName` hits the cache, and that other modifications don't hit the cache.
- This last check is less efficient and less likely to happen, so probably should be rethought a bit.

Thanks to both @alexcrichton and @cfallin for your very useful feedback on Zulip.

Some numbers show that for a large wasm module we're using internally, this is a 20% compile-time speedup, because so many `FunctionStencil`s are the same, even within a single module. For a group of modules that have a lot of code in common, we get hit rates up to 70% when they're used together. When a single function changes in a wasm module, every other function is reloaded; that's still slower than I expect (between 10% and 50% of the overall compile time), so there's likely room for improvement.

Fixes #4155.

show more ...

Cranelift: disallow marking entry block 'cold'. (#4659)

This is a nonsensical constraint: the entry block must come first in the
compiled code's layout, so it cannot also be sunk to the end of the

Cranelift: disallow marking entry block 'cold'. (#4659)

This is a nonsensical constraint: the entry block must come first in the
compiled code's layout, so it cannot also be sunk to the end of the
function.

This PR modifies the CLIF verifier to disallow this situation entirely.
It also adds an assert during final block-order computation to catch the
problem (and avoid a silent miscompile) even if the verifier is
disabled.

Fixes #4656.

show more ...

Propagate cold annotations to edge blocks (#4636)

Update the lowering stage to mark edge blocks as cold if either the
predecessor or successor block is cold.

Cranellift: remove Baldrdash support and related features. (#4571)

* Cranellift: remove Baldrdash support and related features.

As noted in Mozilla's bugzilla bug 1781425 [1], the SpiderMonkey te

Cranellift: remove Baldrdash support and related features. (#4571)

* Cranellift: remove Baldrdash support and related features.

As noted in Mozilla's bugzilla bug 1781425 [1], the SpiderMonkey team
has recently determined that their current form of integration with
Cranelift is too hard to maintain, and they have chosen to remove it
from their codebase. If and when they decide to build updated support
for Cranelift, they will adopt different approaches to several details
of the integration.

In the meantime, after discussion with the SpiderMonkey folks, they
agree that it makes sense to remove the bits of Cranelift that exist
to support the integration ("Baldrdash"), as they will not need
them. Many of these bits are difficult-to-maintain special cases that
are not actually tested in Cranelift proper: for example, the
Baldrdash integration required Cranelift to emit function bodies
without prologues/epilogues, and instead communicate very precise
information about the expected frame size and layout, then stitched
together something post-facto. This was brittle and caused a lot of
incidental complexity ("fallthrough returns", the resulting special
logic in block-ordering); this is just one example. As another
example, one particular Baldrdash ABI variant processed stack args in
reverse order, so our ABI code had to support both traversal
orders. We had a number of other Baldrdash-specific settings as well
that did various special things.

This PR removes Baldrdash ABI support, the `fallthrough_return`
instruction, and pulls some threads to remove now-unused bits as a
result of those two, with the understanding that the SpiderMonkey folks
will build new functionality as needed in the future and we can perhaps
find cleaner abstractions to make it all work.

[1] https://bugzilla.mozilla.org/show_bug.cgi?id=1781425

* Review feedback.

* Fix (?) DWARF debug tests: add `--disable-cache` to wasmtime invocations.

The debugger tests invoke `wasmtime` from within each test case under
the control of a debugger (gdb or lldb). Some of these tests started to
inexplicably fail in CI with unrelated changes, and the failures were
only inconsistently reproducible locally. It seems to be cache related:
if we disable cached compilation on the nested `wasmtime` invocations,
the tests consistently pass.

* Review feedback.

show more ...

cranelift: Introduce a feature to enable `trace` logs (#4484)

* Don't use `log::trace` directly but a feature-enabled `trace` macro
* Don't emit disassembly based on the log level

Add a basic alias analysis with redundant-load elim and store-to-load fowarding opts. (#4163)

This PR adds a basic *alias analysis*, and optimizations that use it.
This is a "mid-end optimization":

Add a basic alias analysis with redundant-load elim and store-to-load fowarding opts. (#4163)

This PR adds a basic *alias analysis*, and optimizations that use it.
This is a "mid-end optimization": it operates on CLIF, the
machine-independent IR, before lowering occurs.

The alias analysis (or maybe more properly, a sort of memory-value
analysis) determines when it can prove a particular memory
location is equal to a given SSA value, and when it can, it replaces any
loads of that location.

This subsumes two common optimizations:

* Redundant load elimination: when the same memory address is loaded two
times, and it can be proven that no intervening operations will write
to that memory, then the second load is *redundant* and its result
must be the same as the first. We can use the first load's result and
remove the second load.

* Store-to-load forwarding: when a load can be proven to access exactly
the memory written by a preceding store, we can replace the load's
result with the store's data operand, and remove the load.

Both of these optimizations rely on a "last store" analysis that is a
sort of coloring mechanism, split across disjoint categories of abstract
state. The basic idea is that every memory-accessing operation is put
into one of N disjoint categories; it is disallowed for memory to ever
be accessed by an op in one category and later accessed by an op in
another category. (The frontend must ensure this.)

Then, given this, we scan the code and determine, for each
memory-accessing op, when a single prior instruction is a store to the
same category. This "colors" the instruction: it is, in a sense, a
static name for that version of memory.

This analysis provides an important invariant: if two operations access
memory with the same last-store, then *no other store can alias* in the
time between that last store and these operations. This must-not-alias
property, together with a check that the accessed address is *exactly
the same* (same SSA value and offset), and other attributes of the
access (type, extension mode) are the same, let us prove that the
results are the same.

Given last-store info, we scan the instructions and build a table from
"memory location" key (last store, address, offset, type, extension) to
known SSA value stored in that location. A store inserts a new mapping.
A load may also insert a new mapping, if we didn't already have one.
Then when a load occurs and an entry already exists for its "location",
we can reuse the value. This will be either RLE or St-to-Ld depending on
where the value came from.

Note that this *does* work across basic blocks: the last-store analysis
is a full iterative dataflow pass, and we are careful to check dominance
of a previously-defined value before aliasing to it at a potentially
redundant load. So we will do the right thing if we only have a
"partially redundant" load (loaded already but only in one predecessor
block), but we will also correctly reuse a value if there is a store or
load above a loop and a redundant load of that value within the loop, as
long as no potentially-aliasing stores happen within the loop.

show more ...

Cranelift: fix fuzzbug in critical-edge splitting. (#4044)

regalloc2 is a bit pickier about critical edges than regalloc.rs was,
because of how it inserts moves. In particular, if a branch has any

Cranelift: fix fuzzbug in critical-edge splitting. (#4044)

regalloc2 is a bit pickier about critical edges than regalloc.rs was,
because of how it inserts moves. In particular, if a branch has any
arguments (e.g., a conditional branch or br_table), its successors must
all have only one predecessor, so we can do edge moves at the top of
successor blocks rather than at the end of this block. Otherwise, moves
that semantically must come after the block's last uses (the branch's
args) would be placed before it.

This is almost always the case, because crit-edge splitting ensures that
if we have more than one succ, all our succs will have only one pred.
This is because branch kinds that take arguments (fixed args, not the
blockparam args) tend to have more than one successor: conditionals and
br_tables.

However, a fuzzbug recently illuminated one corner case I had missed: a
br_table can have *one* successor only, if it has a default target and
an empty table. In this case, crit-edge splitting will happily skip a
split and assume that we can insert edge moves at the end of the block
with the br_table. But this will fail.

regalloc2 explicitly checks this and bails with a panic, rather than
continue, so no miscompilation is possible; but without this fix, we
will get these panics on br_tables with empty tables.

show more ...