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).