Changes in ctxhash.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/ctxhash.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/ctxhash.rs

f2fb00dd - chore: update `hashbrown` to 0.15 (#9974)

Fri, 10 Jan 2025 15:35:27 +0000

chore: update `hashbrown` to 0.15 (#9974)* chore: update `hashbrown` to 0.15* fmt List of files: /wasmtime-44.0.1/cranelift/codegen/src/ctxhash.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/ctxhash.rs

9ce3ffe1 - Update some CI dependencies (#7983)

Thu, 22 Feb 2024 23:54:03 +0000

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

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

Tue, 06 Dec 2022 22:58:57 +0000

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