Moduleghc-9.10.3GHC2021

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.

5 types
16 values

Packageghc-9.10.3
Exports21
LanguageGHC2021
LicenceBSD-3-Clause
SourceDominators.hs

typetype Node = Word64

typetype Path = [Node]

typetype Edge = (Node, Node)

typetype Graph = Word64Map Word64Set

typetype Rooted = (Node, Graph)

valueidom :: Rooted -> [(Node, Node)]

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.

valueipdom :: Rooted -> [(Node, Node)]

Immediate post-dominators. Complexity as for idom.

valuedomTree :: Rooted -> Tree Node

Dominator tree. Complexity as for idom.

valuepdomTree :: Rooted -> Tree Node

Post-dominator tree. Complexity as for idom.

valuedom :: Rooted -> [(Node, Path)]

Dominators. Complexity as for idom

valuepdom :: Rooted -> [(Node, Path)]

Post-dominators. Complexity as for idom.

valuepddfs :: Rooted -> [Node]

Post-dominated depth-first search.

valuerpddfs :: Rooted -> [Node]

Reverse post-dominated depth-first search.

valuefromAdj :: [(Node, [Node])] -> Graph

valuefromEdges :: [Edge] -> Graph

valuetoAdj :: Graph -> [(Node, [Node])]

valuetoEdges :: Graph -> [Edge]

valueasTree :: Rooted -> Tree Node

valueasCGraph :: Tree Node -> Rooted

valueparents :: Tree a -> [(a, a)]

valueancestors :: Tree a -> [(a, [a])]