Changes in cost.rs

50431b45 - Cranelift: Do not track expression depth in egraph cost function (#12248)

Tue, 06 Jan 2026 18:53:48 +0000

Cranelift: Do not track expression depth in egraph cost function (#12248)We don't have any rules that try to rebalance trees to make them shallower inthe mid-end (we determined it was the wrong place to do that kind of thing,since we don't know register pressure at that point) so there is no need totrack expression depth in the cost function. List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/cost.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/cost.rs

d5ef5285 - Cranelift: Tweak cost function to make `imul` more expensive (#12006)

Fri, 07 Nov 2025 19:23:05 +0000

Cranelift: Tweak cost function to make `imul` more expensive (#12006)* Cranelift: Tweak cost function to pessimize `select` opcodes`select`s cannot be speculated through on some of our targets (e.g. x64) sostrongly prefer not choosing them.Using a target-specific cost function, so that we only pessimize `select` whenit makes sense, is left for follow up work and is tracked in #12005.* Don't pessimize `select`s that heavily List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/cost.rs

7bf31723 - Cranelift: simplify some side-effectful instructions in ISLE (#10524)

Tue, 08 Apr 2025 17:57:03 +0000

Cranelift: simplify some side-effectful instructions in ISLE (#10524)* Cranelift: simplify some side-effectful instructions in ISLEThis commit adds a new top-level ISLE entrypoint specifically for instructionsin the side-effectful skeleton: `simplify_skeleton`. While these rewrites areprocessed during the egraph pass, values from skeleton instructions still do notget inserted into the egraph. Indeed, `simplify_skeleton` operateson *instructions* rather than *values* because we do not represent side effectsas values; values do not have side effects in CLIF, instructions do. Therefore,rather than doing a whole dynamic-programming style extraction of the bestcandidate simplification like we do with the egraph, we take an eager and greedyapproach.Furthermore, `simplify_skeleton` is limited only to skeleton instructions thatdo not involve control-flow or terminators right now. This is because changingthe control-flow graph can change whether a use is dominated by a def or not,and we do not currently have the machinery to track and fix up invalidateduses. Addressing this is left for future commits.* fix `MIN / -1` cprop and add negative tests for things simplify_skeleton cannot handle yet List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/cost.rs

1104a838 - Cranelift: avoid integer-shift optimization with invalid reduces on vector types. (#10413)

Mon, 17 Mar 2025 19:45:41 +0000

Cranelift: avoid integer-shift optimization with invalid reduces on vector types. (#10413)An optimization rule in our mid-end implemented the followingequivalence:``` (x << N) >> N == x as T1 as T2```where `T1` is a smaller integer type and `T2` is a larger integertype, and `N` is the difference in bitwidths between them. In otherwords, when a left-then-right-shift clears the upper bits (orsign-extends them), we can implement that by reducing to a smallertype then extending back to the original type.Unfortunately, `ireduce` is not valid on vector-of-integer types. Afuzzbug reported in #10409 shows that this pattern results in invalidCLIF when optimizing this pattern with an `i64x2` as input.This PR tightens the rule's LHS to only apply to integer types.Note that there is another optimization rule that can also implementthis behavior with a bitwise AND with a mask. Previously the tworesulting expressions had the same cost in the egraph, and whateverperturbation occurred in the ISLE compilation of the rule (which is amulti-constructor because this is the mid-end, so is returningmultiple results) caused that rule's result to be picked insteadduring extraction. I've also tweaked the costs to make reduces/extendscheaper than ordinary arithmetic as a result, to keep the sameoptimizer outputs after extraction. One x64 test in particular showedwhy this is correct: the mask-with-AND resulted in twoinstructions (move, AND-with-immediate) while a uextend can be donewith one (zero-extending move, `movzbl`), and aarch64 has similarbuiltin extends in many cases. List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/cost.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/cost.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/cost.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/cost.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/cost.rs

de0e0bea - Legalize `b{and,or,xor}_not` into component instructions (#5709)

Mon, 06 Feb 2023 19:53:40 +0000

Legalize `b{and,or,xor}_not` into component instructions (#5709)* Remove trailing whitespace in `lower.isle` files * Legalize the `band_not` instruction into simpler form This commit legalizes the `band_not` instruction into `band`-of-`bnot`, or two instructions. This is intended to assist with egraph-based optimizations where the `band_not` instruction doesn't have to be specifically included in other bit-operation-patterns. Lowerings of the `band_not` instruction have been moved to a specialization of the `band` instruction. * Legalize `bor_not` into components Same as prior commit, but for the `bor_not` instruction. * Legalize bxor_not into bxor-of-bnot Same as prior commits. I think this also ended up fixing a bug in the s390x backend where `bxor_not x y` was actually translated as `bnot (bxor x y)` by accident given the test update changes. * Simplify not-fused operands for riscv64 Looks like some delegated-to rules have special-cases for "if this feature is enabled use the fused instruction" so move the clause for testing the feature up to the lowering phase to help trigger other rules if the feature isn't enabled. This should make the riscv64 backend more consistent with how other backends are implemented. * Remove B{and,or,xor}Not from cost of egraph metrics These shouldn't ever reach egraphs now that they're legalized away. * Add an egraph optimization for `x^-1 => ~x` This adds a simplification node to translate xor-against-minus-1 to a `bnot` instruction. This helps trigger various other optimizations in the egraph implementation and also various backend lowering rules for instructions. This is chiefly useful as wasm doesn't have a `bnot` equivalent, so it's encoded as `x^-1`. * Add a wasm test for end-to-end bitwise lowerings Test that end-to-end various optimizations are being applied for input wasm modules. * Specifically don't self-update rustup on CI I forget why this was here originally, but this is failing on Windows CI. In general there's no need to update rustup, so leave it as-is. * Cleanup some aarch64 lowering rules Previously a 32/64 split was necessary due to the `ALUOp` being different but that's been refactored away no so there's no longer any need for duplicate rules. * Narrow a x64 lowering rule This previously made more sense when it was `band_not` and rarely used, but be more specific in the type-filter on this rule that it's only applicable to SIMD types with lanes. * Simplify xor-against-minus-1 rule No need to have the commutative version since constants are already shuffled right for egraphs * Optimize band-of-bnot when bnot is on the left Use some more rules in the egraph algebraic optimizations to canonicalize band/bor/bxor with a `bnot` operand to put the operand on the right. That way the lowerings in the backends only have to list the rule once, with the operand on the right, to optimize both styles of input. * Add commutative lowering rules * Update cranelift/codegen/src/isa/x64/lower.isle Co-authored-by: Jamey Sharp --------- Co-authored-by: Jamey Sharp List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/cost.rs

ffbcc67e - Cranelift: Consider shifts as "simple" arithmetic in egraph cost model (#5646)

Sat, 28 Jan 2023 00:30:42 +0000

Cranelift: Consider shifts as "simple" arithmetic in egraph cost model (#5646) List of files: /wasmtime-44.0.1/cranelift/codegen/src/egraph/cost.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/egraph/cost.rs