bytecodealliance / bytecodealliance/wasmtime

Use a linear time dominators algorithm

Open
#9,481 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
18.6k
Forks
1.8k
Avg merge
1d 18h
Merged PRs (30d)
126

Description

Right now we use the classic simple-fast algorithm (*A Simple, Fast Dominance Algorithm* by Cooper et al) and while this works well most of the time in practice, it has quadratic worst case time.

Linear-time alternatives exist: https://dl.acm.org/doi/10.5555/1123869

We should consider using them instead.

SpiderMonkey found the Semi-NCA algorithm to be a big speed up: https://spidermonkey.dev/blog/2024/10/16/75x-faster-optimizing-the-ion-compiler-backend.html

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.