wasmtime icon indicating copy to clipboard operation
wasmtime copied to clipboard

Use a linear time dominators algorithm

Open fitzgen opened this issue 1 year ago • 0 comments

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

fitzgen avatar Oct 17 '24 15:10 fitzgen