wasmtime
wasmtime copied to clipboard
Use a linear time dominators algorithm
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