Stream: git-wasmtime

Topic: wasmtime / PR #12177 Cranelift: topo sort when computing ...

Wasmtime GitHub notifications bot (Dec 17 2025 at 21:09):

fitzgen requested cfallin for a review on PR #12177.

Wasmtime GitHub notifications bot (Dec 17 2025 at 21:09):

fitzgen requested wasmtime-compiler-reviewers for a review on PR #12177.

Wasmtime GitHub notifications bot (Dec 17 2025 at 21:09):

fitzgen opened PR #12177 from fitzgen:egraph-cost-function-topo-sort to bytecodealliance:main:

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)

cc https://github.com/bytecodealliance/wasmtime/issues/12156

<!--
Please make sure you include the following information:

• If this work has been discussed elsewhere, please include a link to that
  conversation. If it was discussed in an issue, just mention "issue #...".

• Explain why this change is needed. If the details are in an issue already,
  this can be brief.

Our development process is documented in the Wasmtime book:
https://docs.wasmtime.dev/contributing-development-process.html

Please ensure all communication follows the code of conduct:
https://github.com/bytecodealliance/wasmtime/blob/main/CODE_OF_CONDUCT.md
-->

Wasmtime GitHub notifications bot (Dec 17 2025 at 21:18):

fitzgen updated PR #12177.

Wasmtime GitHub notifications bot (Dec 17 2025 at 21:24):

cfallin submitted PR review:

Nice -- thanks for this improvement!

Wasmtime GitHub notifications bot (Dec 17 2025 at 21:25):

cfallin has enabled auto merge for PR #12177.

Wasmtime GitHub notifications bot (Dec 17 2025 at 21:54):

cfallin merged PR #12177.

Last updated: Jan 09 2026 at 13:15 UTC