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: topo sort when computing best costs during elaboration (#12177)

* Cranelift: topo sort when computing best costs during elaboration

This lets us avoid a fixpoint loop. In practice, the f

Cranelift: topo sort when computing best costs during elaboration (#12177)

* Cranelift: topo sort when computing best costs during elaboration

This lets us avoid a fixpoint loop. In practice, the fixpoint loop almost always
converged after only one or two iterations (plus one more iteration to learn
that we did in fact converge) but we do see as high as fourteen iterations in
Sightglass's `pulldown-cmark` and 12 in `spidermonkey.wasm`.

A topo sort is effectively one pass over the IR, after which we know that we
converge after a single iteration of the loop that used to be inside the
fixpoint. The fixpoint loop did two iterations at best (one to converge, and one
to learn that it converged) so this is basically no worse in the best case for
the fixpoint loop. However, the new approach's worst case is the same as its
best case, which is definitely not true for the fixpoint loop (becomes quadratic
at worse).

This does not affect the best costs we compute for each value at all, and
therefore does not affect our generated code at all (e.g. note that the
filetests and disas tests are unmodified in this commit).

Despite improving worst-case algorithmic complexity, it does not seem to have
any statistically significant affect on compilation time for Sightglass's
default benchmark suite either:

```
compilation :: instructions-retired :: benchmarks/pulldown-cmark/benchmark.wasm

No difference in performance.

[14272577 14343801.70 14428315] main.so (-Cparallel-compilation=n)
[14332259 14376054.10 14452731] topo-sort.so (-Cparallel-compilation=n)

compilation :: instructions-retired :: benchmarks/spidermonkey/benchmark.wasm

No difference in performance.

[494880425 497004543.50 497423796] main.so (-Cparallel-compilation=n)
[496100425 496346205.40 496691007] topo-sort.so (-Cparallel-compilation=n)

compilation :: instructions-retired :: benchmarks/bz2/benchmark.wasm

No difference in performance.

[3499081 3517541.70 3552882] main.so (-Cparallel-compilation=n)
[3498186 3514863.90 3531898] topo-sort.so (-Cparallel-compilation=n)
```

* Update some comments and add some debug assertions

show more ...

refactor(cranelift): merge DominatorTreePreorder into DominatorTree (#11596)

* refactor(cranelift): merge DominatorTreePreorder into DominatorTree

Integrate preorder functionality directly into Dom

refactor(cranelift): merge DominatorTreePreorder into DominatorTree (#11596)

* refactor(cranelift): merge DominatorTreePreorder into DominatorTree

Integrate preorder functionality directly into DominatorTree to
eliminate duplicate computation and improve performance.

This eliminates the need for a separate DominatorTreePreorder data
structure, reducing memory usage and providing O(1) block dominance
checks by default. Block dominance checks throughout the compiler now
benefit from constant-time performance instead of O(depth) tree
traversal.

* refactor(cranelift): implement the new unified DominatorTree

Remove separate DominatorTreePreorder computation and use unified API:

- Context: Remove domtree_preorder field, simplify compute_domtree()
- AliasAnalysis: Switch from DominatorTreePreorder to DominatorTree
- Update dominance checks to use general dominates() method

All dominance checks in alias analysis now automatically benefit from
O(1) block dominance performance when instructions are in different
blocks.

* refactor(cranelift): update optimization passes for DominatorTree

* refactor(cranelift): update verifier and tests for new DominatorTree

SSA dominance validation in the verifier now benefits from O(1)
block-to-block dominance checks, improving compilation performance
during debug builds with verification enabled.

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

Simplify aegraphs by removing union-find and canonical eclass IDs. (#10471)

I was recently re-thinking through some of the core data structure
design in our aegraph implementation, and wondered: do

Simplify aegraphs by removing union-find and canonical eclass IDs. (#10471)

I was recently re-thinking through some of the core data structure
design in our aegraph implementation, and wondered: do we really need
the union-find data structure, the notion of "canonical" ID for an
eclass separate from its latest ID (root of union-node tree), and the
hashcons-key canonicalization using all of this? It's an awful lot of
complexity and has led to some fairly subtle bugs (e.g., #6126), and is
generally unsatisfying.

I had the realization: the only case where the distinction between
canonical and latest ID matters is when we expand an eclass after its
initial (eager) rewriting, which happens before we see its uses. If we
hypothesize that this happens rarely, then it should be fine to
canonicalize based only on latest ID -- we shouldn't lose much (and we
can measure this loss empirically).

The chief case where this kind of "late eclass expansion" still happens
is: if we have some expression E1 that eventually rewrites to E2 via
some simplification, and E2 already exists earlier in the program, then
E1 will join the eclass. If we then have some `E3 := E1 + 1`, and later
`E4 := E2 + 1`, we need the union-find canonicalization for E4 to GVN to
E3. Otherwise, the latest ID for the eclass that eventually contains E1
and E2 is different at the time that E3 uses it (and is GVN'd and
rewritten) and when E4 does. Put another way: E3 captures a snapshot of
its operand's eclass before a new node joins it, and is never
reprocessed when that happens, so E3 remains distinct.

But if the `E2 -> E1` rewrite is truly "directional" toward a better
representation that we will always want to choose -- say, `x + 0 -> x`,
or any constant-propagation in general -- then if the eager rewriting
for E2 produces E1's eclass ID directly *without* adding E2 to its
nodes, then all users will still canonicalize as before. This "only
return the rewrite target, don't union with it" before is exactly our
`subsume` operator.

Put another way: subsumption prevents growing eclasses later, so
snapshots in time remain the latest, and everyone canonicalizes with the
same ID. We move to a true immutable data structure, with simple
hashconsing with no magic.

The rewrite semantics are then much simpler too: if any value is
marked "subsume", we pick it (pick an arbitrary one if multiple) as our
rewrite result; otherwise, create an eclass with the original rewrite
input and all rewrite outputs (by creating union-nodes in the DFG). No
auto-subsume or factoring in availability -- that's it. "Subsume" means:
always pick the rewritten value, don't keep the original, and we use it
whenever that's unambiguously true for better canonicalization.

Given that, it turns out that we can remove the union-find mechanism
entirely. It also turns out that we can unify the scoped-hashmap for
"effectful/idempotent ops" with the ordinary hashmap for pure ops;
everything can be scoped. To get working LICM we do need to retain our
"available block" mechanism, but only to insert values at a higher scope
level in the scoped hashmap -- it is now heuristic, not load-bearing for
correctness.

I suspect that the fixpoint loop computing analysis results can go away
too, now that we truly don't update arguments -- we have a simple
immutable data structure with everything snapshotted at creation -- but
I haven't made that change yet.

This change appears to be "in the noise" in both runtime and compile
time -- a Sightglass run on the default suite shows only

```
compilation :: cycles :: benchmarks/pulldown-cmark/benchmark.wasm

Δ = 551234.50 ± 514580.62 (confidence = 99%)

new.so is 1.00x to 1.01x faster than old.so!

[61669181 72513567.85 98139932] new.so
[60991071 73064802.35 120044089] old.so

execution :: cycles :: benchmarks/bz2/benchmark.wasm

Δ = 232827.80 ± 204621.12 (confidence = 99%)

old.so is 1.00x to 1.01x faster than new.so!

[67208140 72812782.32 89996076] new.so
[69531172 72579954.52 80530142] old.so
```

which seem like suitably small swings that are fine. Spot-checking the
aegraph stats on the same function before-and-after shows the same
optimizations happening in all functions I examined, and we see the
compile-tests showing no movement except for a value renumbering in one
case. So: no effect objectively, but deletes code and significantly
simplifies the core algorithm.

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

egraph: Resolve all aliases at once (#8240)

* egraph: Resolve all aliases at once

This way we can use the linear-time alias rewriting pass, and then avoid
having to think about value aliases ever a

egraph: Resolve all aliases at once (#8240)

* egraph: Resolve all aliases at once

This way we can use the linear-time alias rewriting pass, and then avoid
having to think about value aliases ever again.

* Resolve aliases in facts and values_labels

When resolving aliases in values_labels, this discards debug info on
values which are replaced by aliases. However, that is equivalent to the
existing behavior in `Lower::get_value_labels`, which resolves value
aliases first and only then looks for attached debug info.

show more ...

cranelift: Enable "chaos mode" in egraph pass (#7968)

First of all, thread a "chaos mode" control-plane into Context::optimize
and from there into EgraphPass, OptimizeCtx, and Elaborator.

In this c

cranelift: Enable "chaos mode" in egraph pass (#7968)

First of all, thread a "chaos mode" control-plane into Context::optimize
and from there into EgraphPass, OptimizeCtx, and Elaborator.

In this commit we use the control-plane to change the following
behaviors in ways which shouldn't cause incorrect results:

- Dominator-tree block traversal order for both the rule application and
elaboration passes
- Order of evaluating optimization alternatives from `simplify`
- Choose worst values instead of best in each eclass

Co-authored-by: L. Pereira <[email protected]>

show more ...

cranelift: Remove redundant dominator-tree structure (#7948)

* Don't keep extra copies of root block ID

We already know the entry block everywhere we use this.

* Replace DomTreeWithChildren with D

cranelift: Remove redundant dominator-tree structure (#7948)

* Don't keep extra copies of root block ID

We already know the entry block everywhere we use this.

* Replace DomTreeWithChildren with DominatorTreePreorder

These two types had nearly identical interfaces except that the latter
also supports constant-time dominance checks.

* Use dom-tree preorder for O(1) dominance checks

It turns out this was the only thing the egraph pass used the original
dominator tree for, so we can stop passing that around.

We could also require that the caller of EgraphPass::new construct the
DominatorTreePreorder and avoid passing the original tree into the
egraph pass at all, but I've chosen to stop refactoring here.

We should review all uses of DominatorTree::dominates to see if it makes
sense to pass a DominatorTreePreorder around more places.

* review comments: Rename/document away from "domtree with children"

show more ...

Remove the use of the union-find structure during elaboration (#7922)

* Remove the use of the union-find structure during elaboration

Remove the UnionFind argument to `Elaborator::new`, and from th

Remove the use of the union-find structure during elaboration (#7922)

* Remove the use of the union-find structure during elaboration

Remove the UnionFind argument to `Elaborator::new`, and from the
`Elaborator` structure, relying instead on the `value_to_best_value`
table when computing canonical values.

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

* Document the eclass union subtree invariant

---------

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

show more ...

Cranelift: Use a fixpoint loop to compute the best value for each eclass (#7859)

* Cranelift: Use a fixpoint loop to compute the best value for each eclass

Fixes #7857

* Remove fixpoint loop early

Cranelift: Use a fixpoint loop to compute the best value for each eclass (#7859)

* Cranelift: Use a fixpoint loop to compute the best value for each eclass

Fixes #7857

* Remove fixpoint loop early-continue optimization

* Add document describing optimization rule invariants

* Make select optimizations use subsume

* Remove invalid debug assert

* Remove now-unused methods

* Add commutative adds to cost tests

show more ...

Cranelift: Break op cost ties with expression depth in egraphs (#7456)

* Cranelift: Switch egraph `Cost` to a struct with named fields

Mechanical change.

* Cranelift: Break op cost ties with expre

Cranelift: Break op cost ties with expression depth in egraphs (#7456)

* Cranelift: Switch egraph `Cost` to a struct with named fields

Mechanical change.

* Cranelift: Break op cost ties with expression depth in egraphs

This means that, when the opcode cost is the same, we prefer shallow and wide
expressions to narrow and deep. For example, `(a + b) + (c + d)` is preferred to
`((a + b) + c) + d`. This is beneficial because it exposes more
instruction-level parallelism and shortens live ranges.

Co-Authored-By: Trevor Elliott <[email protected]>

* Cranelift: Bitpack the egraph `Cost` structure

Co-Authored-By: Chris Fallin <[email protected]>
Co-Authored-By: Trevor Elliott <[email protected]>

* Make it so you can't construct `Cost::inifinity()` by accident

* Use fold to code golf

---------

Co-authored-by: Trevor Elliott <[email protected]>
Co-authored-by: Chris Fallin <[email protected]>

show more ...

Cranelift: Fix union node bitpacking (#7465)

* Cranelift: Fix union node bitpacking

It turns out we have just been taking the newest rewrite's value for a eclass
union and never actually comparing

Cranelift: Fix union node bitpacking (#7465)

* Cranelift: Fix union node bitpacking

It turns out we have just been taking the newest rewrite's value for a eclass
union and never actually comparing costs and taking the value with the minimum
cost. Whoops!

Fixing this made some test expectations fail, which we resolved by tweaking the
cost function to give materializing constants nonzero cost. This way we prefer
`-x` to `0 - x`.

We also made elaboration function break ties between values with the same cost
with the value index. It prefers larger value indices, since the original
value's index will be lower than all of its rewritten values' indices. This
heuristically prefers rewritten values because we hope our rewrites are all
improvements even when the cost function can't show that.

Co-Authored-By: Chris Fallin <[email protected]>
Co-Authored-By: Trevor Elliott <[email protected]>

* Add more information to assertion message

* Fix off-by-one bug in assertion

* Limit number of matches consumed from ISLE

We generally want to clamp down and avoid runaway behavior here.

But there also seems to be some sort of rustc/llvm bug on Rust 1.71 that is
causing iteration to wild here. This commit avoids that bug.

* Update test expectation

* prtest:full

---------

Co-authored-by: Chris Fallin <[email protected]>
Co-authored-by: Trevor Elliott <[email protected]>

show more ...

egraphs: don't let rematerialization override LICM. (#7306)

This reworks the way that remat and LICM interact during aegraph
elaboration. In principle, both happen during the same single-pass "code

egraphs: don't let rematerialization override LICM. (#7306)

This reworks the way that remat and LICM interact during aegraph
elaboration. In principle, both happen during the same single-pass "code
placement" algorithm: we decide where to place pure instructions (those
that are eligible for movement), and remat pushes them one way while
LICM pushes them the other.

The interaction is a little more subtle than simple heuristic priority,
though -- it's really a decision ordering issue. A remat'd value wants to sink
as deep into the loop nest as it can (to the use's block), but we don't
know *where* the uses go until we process them (and make LICM-related
choices), and we process uses after defs during elaboration. Or more
precisely, we have some work at the use before recursively processing
the def, and some work after the recursion returns; and the LICM
decision happens after recursion returns, because LICM wants to know
where the defs are to know how high we can hoist. (The recursion is
itself unrolled into a state machine on an explicit stack so that's a
little hard to see but that's what is happening in principle.)

The solution here is to make remat a separate just-in-time thing, once
we have arg values. Just before we plug the final arg values into the
elaborated instruction, we ask: is this a remat'd value, and if so, do
we have a copy of the computation in this block yet. If not, we make
one. This has to happen in two places (the main elab loop and the
toplevel driver from the skeleton).

The one downside of this solution is that it doesn't handle *recursive*
rematerialization by default. This means that if we, for example, decide
to remat single-constant-arg adds (as we actually do in our current
rules), we won't then also recursively remat the constant arg to those
adds. This can be seen in the `licm.clif` test case. This doesn't seem
to be a dealbreaker to me because most such cases will be able to fold
the constants anyway (they happen mostly because of pointer
pre-computations: a loop over structs in Wasm computes heap_base + p +
offset, and naive LICM pulls a `heap_base + offset` out of the loop for
every struct field accessed in the loop, with horrible register pressure
resulting; that's why we have that remat rule. Most such offsets are
pretty small.).

Fixes #7283.

show more ...

A couple of small refactorings to the egraph elaboration pass (#7304)

@jameysharp and I noticed a couple of refactoring opportunities while
reading through the elaboration pass:

* The elaboration l

A couple of small refactorings to the egraph elaboration pass (#7304)

@jameysharp and I noticed a couple of refactoring opportunities while
reading through the elaboration pass:

* The elaboration loop doesn't need to match on the top of the stack as
a reference, because each case pops it immediately. Instead we can pop
and match on the popped value.
* Computing the cost of a `Result` value that's not in the DFG was using
the block that contains the instruction to determine the level, but
since the instruction is already known to not be in the DFG, this
would default to `LoopLevel::root()` unconditionally. This also meant
that the `Cost::at_level` function turned into an identity function on
the cost given, making it unnecessary.

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

show more ...

Fix the original block for block params in egraphs (#5960)

This fixes an issue where block params were always listed as being
members of the current block in egraphs, even when the block param was
a

Fix the original block for block params in egraphs (#5960)

This fixes an issue where block params were always listed as being
members of the current block in egraphs, even when the block param was
actually defined in a separate block. This then enables instructions
which depend on these parameters to get hoisted up out of inner loops at
least to the block that defined the argument.

Closes #5957

show more ...

Allow hoisting `vconst` instructions out of loops (#5909)

* Allow hoisting `vconst` instructions out of loops

Staring at some SIMD code and what LLVM and v8 both generate it appears
that a common t

Allow hoisting `vconst` instructions out of loops (#5909)

* Allow hoisting `vconst` instructions out of loops

Staring at some SIMD code and what LLVM and v8 both generate it appears
that a common technique for SIMD-loops is to hoist constants outside of
loops since they're nontrivial to rematerialize unlike integer
constants. This commit updates the `loop_hoist_level` calculation with
egraphs to have a nonzero default for instructions that have no
arguments (e.g. consts) which enables hoisting these instructions out of
loops.

Note, though, that for now I've listed the maximum as hoisting outside
of one loop, but not all of them. While theoretically vconsts could move
up to the top of the function I'd be worried about their impact on
register pressure and having to save/restore around calls or similar, so
hopefully if the hot part of a program is a single loop then hoisting
out of one loop is a reasonable-enough heuristic for now.

Locally on x64 with a benchmark that just encodes binary to hex this saw
a 15% performance improvement taking hex encoding from ~6G/s to ~6.7G/s.

* Test vconst is only hoisted one loop out

show more ...

egraphs: fix accidental remat of call. (#5726)

In the provided test case in #5716, the result of a call was then
added to 0. We have a rewrite rule that sets the remat-bit on any add
of a value an

egraphs: fix accidental remat of call. (#5726)

In the provided test case in #5716, the result of a call was then
added to 0. We have a rewrite rule that sets the remat-bit on any add
of a value and a constant, because these frequently appear (e.g. from
address offset calculations) and this can frequently reduce register
pressure (one long-lived base vs. many long-lived base+offset values).
Separately, we have an algebraic rule that `x+0` rewrites to `x`.

The result of this was that we had an eclass with the remat bit set on
the add, but the add was also union'd into the call. We pick the
latter during extraction, because it's cheaper not to do the add at
all; but we still get the remat bit, and try to remat a call (!),
which blows up later.

This PR fixes the logic to look up the "best value" for a value (i.e.,
whatever extraction determined), and look up the remat bit on *that*
node, not the canonical node.

(Why did the canonical node become the iadd and not the call? Because
the former had a lower value-number, as an accident of IR
construction; we don't impose any requirements on the input CLIF's
value-number ordering, and I don't think this breaks any of the
important acyclic properties, even though there is technically a
dependence from a lower-numbered to a higher-numbered node. In essence
one can think of them as having "virtual numbers" in any true
topologically-sorted order, and the only place the actual integer
indices matter should be in choosing the "canonical ID", which is just
used for dedup'ing, modulo this bug.)

Fixes #5716.

show more ...

cranelift: Remove brz and brnz (#5630)

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

cranelift: Rework block instructions to use BlockCall (#5464)

Add a new type BlockCall that represents the pair of a block name with arguments to be passed to it. (The mnemonic here is that it looks

cranelift: Rework block instructions to use BlockCall (#5464)

Add a new type BlockCall that represents the pair of a block name with arguments to be passed to it. (The mnemonic here is that it looks a bit like a function call.) Rework the implementation of jump, brz, and brnz to use BlockCall instead of storing the block arguments as varargs in the instruction's ValueList.

To ensure that we're processing block arguments from BlockCall values in instructions, three new functions have been introduced on DataFlowGraph that both sets of arguments:

inst_values - returns an iterator that traverses values in the instruction and block arguments
map_inst_values - applies a function to each value in the instruction and block arguments
overwrite_inst_values - overwrite all values in an instruction and block arguments with values from the iterator

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

show more ...

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

Optimizations to egraph framework (#5391)

* Optimizations to egraph framework:

- Save elaborated results by canonical value, not latest value (union
value). Previously we were artificially ski

Optimizations to egraph framework (#5391)

* Optimizations to egraph framework:

- Save elaborated results by canonical value, not latest value (union
value). Previously we were artificially skipping and re-elaborating
some values we already had because we were not finding them in the
map.

- Make some changes to handling of icmp results: when icmp became
I8-typed (when bools went away), many uses became `(uextend $I32 (icmp
$I8 ...))`, and so patterns in lowering backends were no longer
matching.

This PR includes an x64-specific change to match `(brz (uextend (icmp
...)))` and similarly for `brnz`, but it also takes advantage of the
ability to write rules easily in the egraph mid-end to rewrite selects
with icmp inputs appropriately.

- Extend constprop to understand selects in the egraph mid-end.

With these changes, bz2.wasm sees a ~1% speedup, and spidermonkey.wasm
with a fib.js input sees a 16.8% speedup:

```
$ time taskset 1 target/release/wasmtime run --allow-precompiled --dir=. ./spidermonkey.base.cwasm ./fib.js
1346269
taskset 1 target/release/wasmtime run --allow-precompiled --dir=. ./fib.js 2.14s user 0.01s system 99% cpu 2.148 total
$ time taskset 1 target/release/wasmtime run --allow-precompiled --dir=. ./spidermonkey.egraphs.cwasm ./fib.js
1346269
taskset 1 target/release/wasmtime run --allow-precompiled --dir=. ./fib.js 1.78s user 0.01s system 99% cpu 1.788 total
```

* Review feedback.

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

egraphs: a few miscellaneous compile-time optimizations. (#5072)

* egraphs: a few miscellaneous compile-time optimizations.

These optimizations together are worth about a 2% compile-time
reducti

egraphs: a few miscellaneous compile-time optimizations. (#5072)

* egraphs: a few miscellaneous compile-time optimizations.

These optimizations together are worth about a 2% compile-time
reduction, as measured on one core with spidermonkey.wasm as an input,
using `hyperfine` on `wasmtime compile`.

The changes included are:
- Some better pre-allocation (blockparams and side-effects concatenated
list vecs);
- Avoiding the indirection of storing list-of-types for every Pure and
Inst node, when almost all nodes produce only a single result;
instead, store arity and single type if it exists, and allow result
projection nodes to fill in types otherwise;
- Pack the `MemoryState` enum into one `u32` (this together with the
above removal of the type slice allows `Node` to
shrink from 48 bytes to 32 bytes);
- always-inline an accessor (`entry` on `CtxHash`) that wasn't
(`always(inline)` appears to be load-bearing, rather than just
`inline`);
- Split the update-analysis path into two hotpaths, one for the union
case and one for the new-node case (and the former can avoid
recomputing for the contained node when replacing a node with
node-and-child eclass entry).

* Review feedback.

* Fix test build.

* Fix to lowering when unused output with invalid type is present.

show more ...