Skip to content

Evaluate using the `A Simple, Fast Dominance Algorithm` algorithm for dominator analysis.

Currently we use the Lengauer-Tarjan algorithm (based on the dom-lt package). Based on the paper in the title in practice we should be able to do better.

Currently dominator analysis is implemented in GHC.CmmToAsm.CFG.Dominators. fgl seems to already have an implementation of A Simple, Fast Dominance Algorithm that hopefully would be easy to adapt.

The thing to do here would be to:

Implement A Simple, Fast Dominance Algorithm providing a drop-in replacement for GHC.CmmToAsm.CFG.Dominators. Make sure the implementation is correct (as best we can).

Benchmark compile times in regards to both allocations and time. (I can help with benchmarking if needed).

To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information