Cranelift: Rewrite conditional branches to unconditional traps into conditional traps during legalization (#10988)

* Cranelift: Legalize via a backwards walk, rather than forwards

Note: the test ex

Cranelift: Rewrite conditional branches to unconditional traps into conditional traps during legalization (#10988)

* Cranelift: Legalize via a backwards walk, rather than forwards

Note: the test expectation change in `filetests/egraph/misc.clif` is simply
because we happen to change the order in which we created the legalized
`stack_addr` instructions that get GVN'd together, and therefore also changed
their relative value numbering. We dedupe to the value that occurs first in the
function, which is the one inserted into the DFG *after* the other now because
of the backwards traversal, and it therefore has a different value number from
before. The resulting program is identical, modulo value numbering.

* Cranelift: Rewrite conditional branches to unconditional traps into conditional traps during legalization

Given this instruction:

```clif
brif v0, block1, block2
```

If we know that `block1` does nothing but immediately trap then we can rewrite
that `brif` into the following:

```clif
trapz v0, <trapcode>
jump block2
```

(And we can do the equivalent with `trapz` if `block2` immediately traps).

This transformation allows for the conditional trap instructions to be GVN'd and
for our egraphs mid-end to generally better optimize the program. We
additionally have better codegen in our backends for `trapz` than branches to
unconditional traps.

Fixes https://github.com/bytecodealliance/wasmtime/issues/10941

* Update CLIF filetests and Wasmtime disas tests

show more ...

Update nightly used in CI (#10957)

A new lint was added to rustc so this updates the nightly used in CI and
then additionally fixes the lints that are firing.

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 ...

Implement most `array.*` instructions for the GC proposal (#9326)

* Implement most `array.*` instructions for the GC proposal

This does not implement `array.copy` and `array.init_elem` yet, but imp

Implement most `array.*` instructions for the GC proposal (#9326)

* Implement most `array.*` instructions for the GC proposal

This does not implement `array.copy` and `array.init_elem` yet, but implements
all other `array.*` instructions:

* `array.new`
* `array.new_fixed`
* `array.new_default`
* `array.new_data`
* `array.new_elem`
* `array.fill`
* `array.init_data`
* `array.len`
* `array.get`
* `array.get_s`
* `array.get_u`
* `array.set`

Note that the initial plumbing for `array.{copy,init_elem}` is in place, but the
instructions themselves are not implemented yet.

* Fix no-gc builds

* Fix some clippy warnings

* cargo fmt

* Fix another clippy error

* Fix more clippy errors

* Remove debug logging

* Add array.fill helper

* exit scope even on panic

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 ...

Minir typo/Grammar fixes (#6187)

* fix typo

* add test to check that Option<EntityRef> is twice as large as EntityRef

* grammar

* grammar

* reverse snakecase -- Not sure if folks want this type

Minir typo/Grammar fixes (#6187)

* fix typo

* add test to check that Option<EntityRef> is twice as large as EntityRef

* grammar

* grammar

* reverse snakecase -- Not sure if folks want this type of change

show more ...

Ensure the sequence number doesn't leak out of Layout (#6061)

Previously it could affect the PartialEq and Hash impls. Ignoring the
sequence number in PartialEq and Hash allows us to not renumber al

Ensure the sequence number doesn't leak out of Layout (#6061)

Previously it could affect the PartialEq and Hash impls. Ignoring the
sequence number in PartialEq and Hash allows us to not renumber all
blocks in the incremental cache.

show more ...

Make sequence numbers local to instructions (#6043)

* Only allow pp_cmp within a single block

Block order shouldn't matter for codegen and restricting pp_cmp to a
single block will allow making ins

Make sequence numbers local to instructions (#6043)

* Only allow pp_cmp within a single block

Block order shouldn't matter for codegen and restricting pp_cmp to a
single block will allow making instruction sequence numbers local to a
block.

* Make sequence numbers local to instructions

This allows renumbering to be localized to a single block where previously it
could affect the entire function. Also saves 32bit of overhead per block.

show more ...

Various cleanups to Layout (#6042)

* Use inst_block instead of pp_block where possible

* Remove unused is_block_gap method

* Remove ProgramOrder trait

It only has a single implementation

* Renam

Various cleanups to Layout (#6042)

* Use inst_block instead of pp_block where possible

* Remove unused is_block_gap method

* Remove ProgramOrder trait

It only has a single implementation

* Rename Layout::cmp to pp_cmp to distinguish it from Ord::cmp

* Make pp_block non-generic

* Use rpo_cmp_block instead of rpo_cmp in the verifier

* Remove ProgramPoint

* Rename ExpandedProgramPoint to ProgramPoint

* Remove From<ValueDef> for ProgramPoint impl

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 ...

egraph support: rewrite to work in terms of CLIF data structures. (#5382)

* egraph support: rewrite to work in terms of CLIF data structures.

This work rewrites the "egraph"-based optimization f

egraph support: rewrite to work in terms of CLIF data structures. (#5382)

* egraph support: rewrite to work in terms of CLIF data structures.

This work rewrites the "egraph"-based optimization framework in
Cranelift to operate on aegraphs (acyclic egraphs) represented in the
CLIF itself rather than as a separate data structure to which and from
which we translate the CLIF.

The basic idea is to add a new kind of value, a "union", that is like an
alias but refers to two other values rather than one. This allows us to
represent an eclass of enodes (values) as a tree. The union node allows
for a value to have *multiple representations*: either constituent value
could be used, and (in well-formed CLIF produced by correct
optimization rules) they must be equivalent.

Like the old egraph infrastructure, we take advantage of acyclicity and
eager rule application to do optimization in a single pass. Like before,
we integrate GVN (during the optimization pass) and LICM (during
elaboration).

Unlike the old egraph infrastructure, everything stays in the
DataFlowGraph. "Pure" enodes are represented as instructions that have
values attached, but that are not placed into the function layout. When
entering "egraph" form, we remove them from the layout while optimizing.
When leaving "egraph" form, during elaboration, we can place an
instruction back into the layout the first time we elaborate the enode;
if we elaborate it more than once, we clone the instruction.

The implementation performs two passes overall:

- One, a forward pass in RPO (to see defs before uses), that (i) removes
"pure" instructions from the layout and (ii) optimizes as it goes. As
before, we eagerly optimize, so we form the entire union of optimized
forms of a value before we see any uses of that value. This lets us
rewrite uses to use the most "up-to-date" form of the value and
canonicalize and optimize that form.

The eager rewriting and acyclic representation make each other work
(we could not eagerly rewrite if there were cycles; and acyclicity
does not miss optimization opportunities only because the first time
we introduce a value, we immediately produce its "best" form). This
design choice is also what allows us to avoid the "parent pointers"
and fixpoint loop of traditional egraphs.

This forward optimization pass keeps a scoped hashmap to "intern"
nodes (thus performing GVN), and also interleaves on a per-instruction
level with alias analysis. The interleaving with alias analysis allows
alias analysis to see the most optimized form of each address (so it
can see equivalences), and allows the next value to see any
equivalences (reuses of loads or stored values) that alias analysis
uncovers.

- Two, a forward pass in domtree preorder, that "elaborates" pure enodes
back into the layout, possibly in multiple places if needed. This
tracks the loop nest and hoists nodes as needed, performing LICM as it
goes. Note that by doing this in forward order, we avoid the
"fixpoint" that traditional LICM needs: we hoist a def before its
uses, so when we place a node, we place it in the right place the
first time rather than moving later.

This PR replaces the old (a)egraph implementation. It removes both the
cranelift-egraph crate and the logic in cranelift-codegen that uses it.

On `spidermonkey.wasm` running a simple recursive Fibonacci
microbenchmark, this work shows 5.5% compile-time reduction and 7.7%
runtime improvement (speedup).

Most of this implementation was done in (very productive) pair
programming sessions with Jamey Sharp, thus:

Co-authored-by: Jamey Sharp <[email protected]>

* Review feedback.

* Review feedback.

* Review feedback.

* Bugfix: cprop rule: `(x + k1) - k2` becomes `x - (k2 - k1)`, not `x - (k1 - k2)`.

Co-authored-by: Jamey Sharp <[email protected]>

show more ...

egraph-based midend: draw the rest of the owl (productionized). (#4953)

* egraph-based midend: draw the rest of the owl.

* Rename `egg` submodule of cranelift-codegen to `egraph`.

* Apply some

egraph-based midend: draw the rest of the owl (productionized). (#4953)

* egraph-based midend: draw the rest of the owl.

* Rename `egg` submodule of cranelift-codegen to `egraph`.

* Apply some feedback from @jsharp during code walkthrough.

* Remove recursion from find_best_node by doing a single pass.

Rather than recursively computing the lowest-cost node for a given
eclass and memoizing the answer at each eclass node, we can do a single
forward pass; because every eclass node refers only to earlier nodes,
this is sufficient. The behavior may slightly differ from the earlier
behavior because we cannot short-circuit costs to zero once a node is
elaborated; but in practice this should not matter.

* Make elaboration non-recursive.

Use an explicit stack instead (with `ElabStackEntry` entries,
alongside a result stack).

* Make elaboration traversal of the domtree non-recursive/stack-safe.

* Work analysis logic in Cranelift-side egraph glue into a general analysis framework in cranelift-egraph.

* Apply static recursion limit to rule application.

* Fix aarch64 wrt dynamic-vector support -- broken rebase.

* Topo-sort cranelift-egraph before cranelift-codegen in publish script, like the comment instructs me to!

* Fix multi-result call testcase.

* Include `cranelift-egraph` in `PUBLISHED_CRATES`.

* Fix atomic_rmw: not really a load.

* Remove now-unnecessary PartialOrd/Ord derivations.

* Address some code-review comments.

* Review feedback.

* Review feedback.

* No overlap in mid-end rules, because we are defining a multi-constructor.

* rustfmt

* Review feedback.

* Review feedback.

* Review feedback.

* Review feedback.

* Remove redundant `mut`.

* Add comment noting what rules can do.

* Review feedback.

* Clarify comment wording.

* Update `has_memory_fence_semantics`.

* Apply @jameysharp's improved loop-level computation.

Co-authored-by: Jamey Sharp <[email protected]>

* Fix suggestion commit.

* Fix off-by-one in new loop-nest analysis.

* Review feedback.

* Review feedback.

* Review feedback.

* Use `Default`, not `std::default::Default`, as per @fitzgen

Co-authored-by: Nick Fitzgerald <[email protected]>

* Apply @fitzgen's comment elaboration to a doc-comment.

Co-authored-by: Nick Fitzgerald <[email protected]>

* Add stat for hitting the rewrite-depth limit.

* Some code motion in split prelude to make the diff a little clearer wrt `main`.

* Take @jameysharp's suggested `try_into()` usage for blockparam indices.

Co-authored-by: Jamey Sharp <[email protected]>

* Take @jameysharp's suggestion to avoid double-match on load op.

Co-authored-by: Jamey Sharp <[email protected]>

* Fix suggestion (add import).

* Review feedback.

* Fix stack_load handling.

* Remove redundant can_store case.

* Take @jameysharp's suggested improvement to FuncEGraph::build() logic

Co-authored-by: Jamey Sharp <[email protected]>

* Tweaks to FuncEGraph::build() on top of suggestion.

* Take @jameysharp's suggested clarified condition

Co-authored-by: Jamey Sharp <[email protected]>

* Clean up after suggestion (unused variable).

* Fix loop analysis.

* loop level asserts

* Revert constant-space loop analysis -- edge cases were incorrect, so let's go with the simple thing for now.

* Take @jameysharp's suggestion re: result_tys

Co-authored-by: Jamey Sharp <[email protected]>

* Fix up after suggestion

* Take @jameysharp's suggestion to use fold rather than reduce

Co-authored-by: Jamey Sharp <[email protected]>

* Fixup after suggestion

* Take @jameysharp's suggestion to remove elaborate_eclass_use's return value.

* Clarifying comment in terminator insts.

Co-authored-by: Jamey Sharp <[email protected]>
Co-authored-by: Nick Fitzgerald <[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: 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

Serialize `BlockNode`'s cold field too when serializing a `Layout` (#4265)

This fixes a bug when the `cold` field would not be serialized, since
we're using a custom (de)serializer for `Layout`. Th

Serialize `BlockNode`'s cold field too when serializing a `Layout` (#4265)

This fixes a bug when the `cold` field would not be serialized, since
we're using a custom (de)serializer for `Layout`. This is now properly
handled by adding a boolean in the serialized stream.

This was caught during the work on #4155, as this would result in cache
mismatches between a function and itself.

show more ...

Cranelift: add support for cold blocks.

This PR adds a flag to each block that can be set via the frontend/builder
interface that indicates that the block will not be frequently
executed. As such, t

Cranelift: add support for cold blocks.

This PR adds a flag to each block that can be set via the frontend/builder
interface that indicates that the block will not be frequently
executed. As such, the compiler backend should place the block "out of
line" in the final machine code, so that the ordinary, more frequent
execution path that excludes the block does not have to jump around it.

This is useful for adding handlers for exceptional conditions
(slow-paths, guard violations) in a way that minimizes performance cost.

Fixes #2747.

show more ...

Add a doclink.

cranelift: Move most debug-level logs to the trace level

Cranelift crates have historically been much more verbose with debug-level
logging than most other crates in the Rust ecosystem. We log thing

cranelift: Move most debug-level logs to the trace level

Cranelift crates have historically been much more verbose with debug-level
logging than most other crates in the Rust ecosystem. We log things like how
many parameters a basic block has, the color of virtual registers during
regalloc, etc. Even for Cranelift hackers, these things are largely only useful
when hacking specifically on Cranelift and looking at a particular test case,
not even when using some Cranelift embedding (such as Wasmtime).

Most of the time, when people want logging for their Rust programs, they do
something like:

RUST_LOG=debug cargo run

This means that they get all that mostly not useful debug logging out of
Cranelift. So they might want to disable logging for Cranelift, or change it to
a higher log level:

RUST_LOG=debug,cranelift=info cargo run

The problem is that this is already more annoying to type that `RUST_LOG=debug`,
and that Cranelift isn't one single crate, so you actually have to play
whack-a-mole with naming all the Cranelift crates off the top of your head,
something more like this:

RUST_LOG=debug,cranelift=info,cranelift_codegen=info,cranelift_wasm=info,...

Therefore, we're changing most of the `debug!` logs into `trace!` logs: anything
that is very Cranelift-internal, unlikely to be useful/meaningful to the
"average" Cranelift embedder, or prints a message for each instruction visited
during a pass. On the other hand, things that just report a one line statistic
for a whole pass, for example, are left as `debug!`. The more verbose the log
messages are, the higher the bar they must clear to be `debug!` rather than
`trace!`.

show more ...

Describe serialization format

Add serde serialization support for the full clif ir

Skip non-branching blocks now that we're using basic blocks

This is a rebase of [1]. In the long term, we'll want to simplify these
analysis passes. For now, this is simple and will reduce the numbe

Skip non-branching blocks now that we're using basic blocks

This is a rebase of [1]. In the long term, we'll want to simplify these
analysis passes. For now, this is simple and will reduce the number of
instructions processed in certain cases.

[1] https://github.com/bytecodealliance/cranelift/pull/866

show more ...

Rename 'an block' to 'a block'

Missed this in the automatic rename of 'Ebb' to 'Block'.

Mass rename Ebb and relatives to Block (#1365)

* Manually rename BasicBlock to BlockPredecessor

BasicBlock is a pair of (Ebb, Inst) that is used to represent the
basic block subcomponent of an E

Mass rename Ebb and relatives to Block (#1365)

* Manually rename BasicBlock to BlockPredecessor

BasicBlock is a pair of (Ebb, Inst) that is used to represent the
basic block subcomponent of an Ebb that is a predecessor to an Ebb.

Eventually we will be able to remove this struct, but for now it
makes sense to give it a non-conflicting name so that we can start
to transition Ebb to represent a basic block.

I have not updated any comments that refer to BasicBlock, as
eventually we will remove BlockPredecessor and replace with Block,
which is a basic block, so the comments will become correct.

* Manually rename SSABuilder block types to avoid conflict

SSABuilder has its own Block and BlockData types. These along with
associated identifier will cause conflicts in a later commit, so
they are renamed to be more verbose here.

* Automatically rename 'Ebb' to 'Block' in *.rs

* Automatically rename 'EBB' to 'block' in *.rs

* Automatically rename 'ebb' to 'block' in *.rs

* Automatically rename 'extended basic block' to 'basic block' in *.rs

* Automatically rename 'an basic block' to 'a basic block' in *.rs

* Manually update comment for `Block`

`Block`'s wikipedia article required an update.

* Automatically rename 'an `Block`' to 'a `Block`' in *.rs

* Automatically rename 'extended_basic_block' to 'basic_block' in *.rs

* Automatically rename 'ebb' to 'block' in *.clif

* Manually rename clif constant that contains 'ebb' as substring to avoid conflict

* Automatically rename filecheck uses of 'EBB' to 'BB'

'regex: EBB' -> 'regex: BB'
'$EBB' -> '$BB'

* Automatically rename 'EBB' 'Ebb' to 'block' in *.clif

* Automatically rename 'an block' to 'a block' in *.clif

* Fix broken testcase when function name length increases

Test function names are limited to 16 characters. This causes
the new longer name to be truncated and fail a filecheck test. An
outdated comment was also fixed.

show more ...

When splitting a const, insert prior to the terminal branch group. (#1325)

* When splitting a const, insert prior to the terminal branch group. Closes #1159

Given code like the following, on x86_

When splitting a const, insert prior to the terminal branch group. (#1325)

* When splitting a const, insert prior to the terminal branch group. Closes #1159

Given code like the following, on x86_64, which does not have i128 registers:

ebb0(v0: i64):
v1 = iconst.i128 0
v2 = icmp_imm eq v0, 1
brnz v2, ebb1
jump ebb2(v1)

It would be split to:

ebb0(v0: i64):
v1 = iconst.i128 0
v2 = icmp_imm eq v0, 1
brnz v2, ebb1
v3, v4 = isplit.i128 v1
jump ebb2(v3, v4)

But that fails basic-block invariants. This patch changes that to:

ebb0(v0: i64):
v1 = iconst.i128 0
v2 = icmp_imm eq v0, 1
v3, v4 = isplit.i128 v1
brnz v2, ebb1
jump ebb2(v3, v4)

* Add isplit-bb.clif testcase

show more ...