Changes in elaborate.rs

76911c29 - Partial support for no_std in cranelift_codegen (#12222)

Wed, 07 Jan 2026 16:41:32 +0000

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 List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

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

Sat, 03 Jan 2026 00:54:48 +0000

cranelift-codegen: rename most uses of std to core and alloc (#12237)* rename most std uses to core and alloc* cargo fmt List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

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

Wed, 17 Dec 2025 21:31:38 +0000

Cranelift: topo sort when computing best costs during elaboration (#12177)* Cranelift: topo sort when computing best costs during elaborationThis lets us avoid a fixpoint loop. In practice, the fixpoint loop almost alwaysconverged after only one or two iterations (plus one more iteration to learnthat we did in fact converge) but we do see as high as fourteen iterations inSightglass's `pulldown-cmark` and 12 in `spidermonkey.wasm`.A topo sort is effectively one pass over the IR, after which we know that weconverge after a single iteration of the loop that used to be inside thefixpoint. The fixpoint loop did two iterations at best (one to converge, and oneto learn that it converged) so this is basically no worse in the best case forthe fixpoint loop. However, the new approach's worst case is the same as itsbest case, which is definitely not true for the fixpoint loop (becomes quadraticat worse).This does not affect the best costs we compute for each value at all, andtherefore does not affect our generated code at all (e.g. note that thefiletests and disas tests are unmodified in this commit).Despite improving worst-case algorithmic complexity, it does not seem to haveany statistically significant affect on compilation time for Sightglass'sdefault 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 List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

3a14fa39 - refactor(cranelift): merge DominatorTreePreorder into DominatorTree (#11596)

Wed, 03 Sep 2025 18:56:07 +0000

refactor(cranelift): merge DominatorTreePreorder into DominatorTree (#11596)* refactor(cranelift): merge DominatorTreePreorder into DominatorTreeIntegrate preorder functionality directly into DominatorTree toeliminate duplicate computation and improve performance.This eliminates the need for a separate DominatorTreePreorder datastructure, reducing memory usage and providing O(1) block dominancechecks by default. Block dominance checks throughout the compiler nowbenefit from constant-time performance instead of O(depth) treetraversal.* refactor(cranelift): implement the new unified DominatorTreeRemove 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() methodAll dominance checks in alias analysis now automatically benefit fromO(1) block dominance performance when instructions are in differentblocks.* refactor(cranelift): update optimization passes for DominatorTree* refactor(cranelift): update verifier and tests for new DominatorTreeSSA dominance validation in the verifier now benefits from O(1)block-to-block dominance checks, improving compilation performanceduring debug builds with verification enabled. List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

90ac295e - Update Wasmtime to the 2024 Rust Edition (#10806)

Mon, 19 May 2025 16:40:55 +0000

Update Wasmtime to the 2024 Rust Edition (#10806)* Update Wasmtime to the 2024 Rust EditionNow that our MSRV supports the 2024 edition it's possible to make thisswitch. This commit moves Wasmtime to the 2024 Edition to keepup-to-date with Rust idioms and access many of the edition featuresexclusive to the 2024 edition.prtest:full* Reformat with the 2024 edition List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

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

Wed, 26 Mar 2025 17:18:18 +0000

Simplify aegraphs by removing union-find and canonical eclass IDs. (#10471)I was recently re-thinking through some of the core data structuredesign in our aegraph implementation, and wondered: do we really needthe union-find data structure, the notion of "canonical" ID for aneclass separate from its latest ID (root of union-node tree), and thehashcons-key canonicalization using all of this? It's an awful lot ofcomplexity and has led to some fairly subtle bugs (e.g., #6126), and isgenerally unsatisfying.I had the realization: the only case where the distinction betweencanonical and latest ID matters is when we expand an eclass after itsinitial (eager) rewriting, which happens before we see its uses. If wehypothesize that this happens rarely, then it should be fine tocanonicalize based only on latest ID -- we shouldn't lose much (and wecan measure this loss empirically).The chief case where this kind of "late eclass expansion" still happensis: if we have some expression E1 that eventually rewrites to E2 viasome simplification, and E2 already exists earlier in the program, thenE1 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 toE3. Otherwise, the latest ID for the eclass that eventually contains E1and E2 is different at the time that E3 uses it (and is GVN'd andrewritten) and when E4 does. Put another way: E3 captures a snapshot ofits operand's eclass before a new node joins it, and is neverreprocessed when that happens, so E3 remains distinct.But if the `E2 -> E1` rewrite is truly "directional" toward a betterrepresentation that we will always want to choose -- say, `x + 0 -> x`,or any constant-propagation in general -- then if the eager rewritingfor E2 produces E1's eclass ID directly *without* adding E2 to itsnodes, then all users will still canonicalize as before. This "onlyreturn the rewrite target, don't union with it" before is exactly our`subsume` operator.Put another way: subsumption prevents growing eclasses later, sosnapshots in time remain the latest, and everyone canonicalizes with thesame ID. We move to a true immutable data structure, with simplehashconsing with no magic.The rewrite semantics are then much simpler too: if any value ismarked "subsume", we pick it (pick an arbitrary one if multiple) as ourrewrite result; otherwise, create an eclass with the original rewriteinput and all rewrite outputs (by creating union-nodes in the DFG). Noauto-subsume or factoring in availability -- that's it. "Subsume" means:always pick the rewritten value, don't keep the original, and we use itwhenever that's unambiguously true for better canonicalization.Given that, it turns out that we can remove the union-find mechanismentirely. 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 scopelevel in the scoped hashmap -- it is now heuristic, not load-bearing forcorrectness.I suspect that the fixpoint loop computing analysis results can go awaytoo, now that we truly don't update arguments -- we have a simpleimmutable data structure with everything snapshotted at creation -- butI haven't made that change yet.This change appears to be "in the noise" in both runtime and compiletime -- 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.soexecution :: 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 theaegraph stats on the same function before-and-after shows the sameoptimizations happening in all functions I examined, and we see thecompile-tests showing no movement except for a value renumbering in onecase. So: no effect objectively, but deletes code and significantlysimplifies the core algorithm. List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

132ef1e4 - Fxhash to rustchash (#8498)

Mon, 29 Apr 2024 15:25:41 +0000

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 List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

b338f921 - egraph: Resolve all aliases at once (#8240)

Thu, 28 Mar 2024 22:04:04 +0000

egraph: Resolve all aliases at once (#8240)* egraph: Resolve all aliases at onceThis way we can use the linear-time alias rewriting pass, and then avoidhaving to think about value aliases ever again.* Resolve aliases in facts and values_labelsWhen resolving aliases in values_labels, this discards debug info onvalues which are replaced by aliases. However, that is equivalent to theexisting behavior in `Lower::get_value_labels`, which resolves valuealiases first and only then looks for attached debug info. List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

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

Tue, 20 Feb 2024 22:26:21 +0000

cranelift: Enable "chaos mode" in egraph pass (#7968)First of all, thread a "chaos mode" control-plane into Context::optimizeand from there into EgraphPass, OptimizeCtx, and Elaborator.In this commit we use the control-plane to change the followingbehaviors 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 eclassCo-authored-by: L. Pereira List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

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

Fri, 16 Feb 2024 22:01:09 +0000

cranelift: Remove redundant dominator-tree structure (#7948)* Don't keep extra copies of root block IDWe already know the entry block everywhere we use this.* Replace DomTreeWithChildren with DominatorTreePreorderThese two types had nearly identical interfaces except that the latteralso supports constant-time dominance checks.* Use dom-tree preorder for O(1) dominance checksIt turns out this was the only thing the egraph pass used the originaldominator tree for, so we can stop passing that around.We could also require that the caller of EgraphPass::new construct theDominatorTreePreorder and avoid passing the original tree into theegraph pass at all, but I've chosen to stop refactoring here.We should review all uses of DominatorTree::dominates to see if it makessense to pass a DominatorTreePreorder around more places.* review comments: Rename/document away from "domtree with children" List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

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

Tue, 13 Feb 2024 19:30:37 +0000

Remove the use of the union-find structure during elaboration (#7922)* Remove the use of the union-find structure during elaborationRemove 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 Co-authored-by: L. Pereira * Document the eclass union subtree invariant---------Co-authored-by: Jamey Sharp Co-authored-by: L. Pereira List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

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

Mon, 05 Feb 2024 22:42:32 +0000

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 eclassFixes #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 List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

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

Tue, 07 Nov 2023 22:29:20 +0000

Cranelift: Break op cost ties with expression depth in egraphs (#7456)* Cranelift: Switch egraph `Cost` to a struct with named fieldsMechanical change.* Cranelift: Break op cost ties with expression depth in egraphsThis means that, when the opcode cost is the same, we prefer shallow and wideexpressions to narrow and deep. For example, `(a + b) + (c + d)` is preferred to`((a + b) + c) + d`. This is beneficial because it exposes moreinstruction-level parallelism and shortens live ranges.Co-Authored-By: Trevor Elliott * Cranelift: Bitpack the egraph `Cost` structureCo-Authored-By: Chris Fallin Co-Authored-By: Trevor Elliott * Make it so you can't construct `Cost::inifinity()` by accident* Use fold to code golf---------Co-authored-by: Trevor Elliott Co-authored-by: Chris Fallin List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

e39c6b76 - Cranelift: Fix union node bitpacking (#7465)

Tue, 07 Nov 2023 18:47:16 +0000

Cranelift: Fix union node bitpacking (#7465)* Cranelift: Fix union node bitpackingIt turns out we have just been taking the newest rewrite's value for a eclassunion and never actually comparing costs and taking the value with the minimumcost. Whoops!Fixing this made some test expectations fail, which we resolved by tweaking thecost 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 costwith the value index. It prefers larger value indices, since the originalvalue's index will be lower than all of its rewritten values' indices. Thisheuristically prefers rewritten values because we hope our rewrites are allimprovements even when the cost function can't show that.Co-Authored-By: Chris Fallin Co-Authored-By: Trevor Elliott * Add more information to assertion message* Fix off-by-one bug in assertion* Limit number of matches consumed from ISLEWe 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 iscausing iteration to wild here. This commit avoids that bug.* Update test expectation* prtest:full---------Co-authored-by: Chris Fallin Co-authored-by: Trevor Elliott List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

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

Fri, 20 Oct 2023 20:00:12 +0000

egraphs: don't let rematerialization override LICM. (#7306)This reworks the way that remat and LICM interact during aegraphelaboration. In principle, both happen during the same single-pass "codeplacement" algorithm: we decide where to place pure instructions (thosethat are eligible for movement), and remat pushes them one way whileLICM 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 sinkas deep into the loop nest as it can (to the use's block), but we don'tknow *where* the uses go until we process them (and make LICM-relatedchoices), and we process uses after defs during elaboration. Or moreprecisely, we have some work at the use before recursively processingthe def, and some work after the recursion returns; and the LICMdecision happens after recursion returns, because LICM wants to knowwhere the defs are to know how high we can hoist. (The recursion isitself unrolled into a state machine on an explicit stack so that's alittle hard to see but that's what is happening in principle.)The solution here is to make remat a separate just-in-time thing, oncewe have arg values. Just before we plug the final arg values into theelaborated instruction, we ask: is this a remat'd value, and if so, dowe have a copy of the computation in this block yet. If not, we makeone. This has to happen in two places (the main elab loop and thetoplevel 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, decideto remat single-constant-arg adds (as we actually do in our currentrules), we won't then also recursively remat the constant arg to thoseadds. This can be seen in the `licm.clif` test case. This doesn't seemto be a dealbreaker to me because most such cases will be able to foldthe constants anyway (they happen mostly because of pointerpre-computations: a loop over structs in Wasm computes heap_base + p +offset, and naive LICM pulls a `heap_base + offset` out of the loop forevery struct field accessed in the loop, with horrible register pressureresulting; that's why we have that remat rule. Most such offsets arepretty small.).Fixes #7283. List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

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

Thu, 19 Oct 2023 23:52:25 +0000

A couple of small refactorings to the egraph elaboration pass (#7304)@jameysharp and I noticed a couple of refactoring opportunities whilereading 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 List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

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

Tue, 07 Mar 2023 23:58:03 +0000

Fix the original block for block params in egraphs (#5960)This fixes an issue where block params were always listed as beingmembers of the current block in egraphs, even when the block param wasactually defined in a separate block. This then enables instructionswhich depend on these parameters to get hoisted up out of inner loops atleast to the block that defined the argument.Closes #5957 List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

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

Mon, 06 Mar 2023 15:29:43 +0000

Allow hoisting `vconst` instructions out of loops (#5909)* Allow hoisting `vconst` instructions out of loopsStaring at some SIMD code and what LLVM and v8 both generate it appearsthat a common technique for SIMD-loops is to hoist constants outside ofloops since they're nontrivial to rematerialize unlike integerconstants. This commit updates the `loop_hoist_level` calculation withegraphs to have a nonzero default for instructions that have noarguments (e.g. consts) which enables hoisting these instructions out ofloops.Note, though, that for now I've listed the maximum as hoisting outsideof one loop, but not all of them. While theoretically vconsts could moveup to the top of the function I'd be worried about their impact onregister pressure and having to save/restore around calls or similar, sohopefully if the hot part of a program is a single loop then hoistingout of one loop is a reasonable-enough heuristic for now.Locally on x64 with a benchmark that just encodes binary to hex this sawa 15% performance improvement taking hex encoding from ~6G/s to ~6.7G/s.* Test vconst is only hoisted one loop out List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

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

Mon, 06 Feb 2023 23:36:16 +0000

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. List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs

a5698ced - cranelift: Remove brz and brnz (#5630)

Mon, 30 Jan 2023 20:34:56 +0000

cranelift: Remove brz and brnz (#5630)Remove the brz and brnz instructions, as their behavior is now redundant with brif. List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/elaborate.rs