Stream: git-wasmtime

Topic: wasmtime / issue #9481 Use a linear time dominators algor...

view this post on Zulip Wasmtime GitHub notifications bot (Oct 17 2024 at 15:27):

fitzgen opened issue #9481:

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

view this post on Zulip Wasmtime GitHub notifications bot (Oct 21 2024 at 18:43):

amartosch commented on issue #9481:

I'd like to have a try at it. The plan would be to implement the Semi-NCA algorithm, because LLVM also seems to use it.

Last updated: Dec 23 2024 at 12:05 UTC