Copyright | (c) Matt Morrow 2009 |
---|---|

License | BSD3 |

Maintainer | <klebinger.andreas@gmx.at> |

Stability | stable |

Portability | portable |

Safe Haskell | Safe-Inferred |

Language | Haskell2010 |

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.

## Synopsis

- type Node = Int
- type Path = [Node]
- type Edge = (Node, Node)
- type Graph = IntMap IntSet
- type Rooted = (Node, Graph)
- idom :: Rooted -> [(Node, Node)]
- ipdom :: Rooted -> [(Node, Node)]
- domTree :: Rooted -> Tree Node
- pdomTree :: Rooted -> Tree Node
- dom :: Rooted -> [(Node, Path)]
- pdom :: Rooted -> [(Node, Path)]
- pddfs :: Rooted -> [Node]
- rpddfs :: Rooted -> [Node]
- 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])]