Moduleghc-10.0.0.20260917GHC2024
GHC.CmmToAsm.CFG.Dominators
The Lengauer-Tarjan graph dominators algorithm.
1 Lengauer, Tarjan,
A Fast Algorithm for Finding Dominators in a Flowgraph, 1979.
2 Muchnick,
Advanced Compiler Design and Implementation, 1997.
3 Brisk, Sarrafzadeh,
Interference CGraphs for Procedures in Static Single
Information Form are Interval CGraphs, 2007.
Strictness
Unless stated otherwise all exposed functions might fully evaluate their input but are not guaranteed to do so.
- Packageghc-10.0.0.20260917
- Exports21
- LanguageGHC2024
- LicenceBSD-3-Clause
- SourceDominators.hs
Immediate dominators. O(|E|*alpha(|E|,|V|)), where alpha(m,n) is "a functional inverse of Ackermann's function".
This Complexity bound assumes O(1) indexing. Since we're
using IntMap, it has an additional lg |V| factor
somewhere in there. I'm not sure where.
Immediate post-dominators.
Complexity as for idom.
Dominator tree.
Complexity as for idom.
Post-dominator tree.
Complexity as for idom.
Dominators.
Complexity as for idom
Post-dominators.
Complexity as for idom.
Post-dominated depth-first search.
Reverse post-dominated depth-first search.