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 Graphs for Procedures in Static Single Information Form are Interval Graphs, 2007.

• Strictness

Unless stated otherwise all exposed functions might fully evaluate their input but are not guaranteed to do so.

Documentation

type Node = Int

type Path = [Node]

type Edge = (Node, Node)

type Graph = IntMap IntSet

type Rooted = (Node, Graph)

idom :: 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.

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

Immediate post-dominators. Complexity as for idom.

domTree :: Rooted -> Tree Node

Dominator tree. Complexity as for idom.

pdomTree :: Rooted -> Tree Node

Post-dominator tree. Complexity as for idom.

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

Dominators. Complexity as for idom

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

Post-dominators. Complexity as for idom.

pddfs :: Rooted -> [Node]

Post-dominated depth-first search.

rpddfs :: Rooted -> [Node]

Reverse post-dominated depth-first search.

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

fromEdges :: [Edge] -> Graph

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

toEdges :: Graph -> [Edge]

asTree :: Rooted -> Tree Node

asGraph :: Tree Node -> Rooted

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

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