# Module type Dominator.S

`module type S = `sig` .. `end``

`type t `
type of graphs
`type vertex `
type of vertices
`module S: `Set.S``  with type elt = vertex``
`type idom = `vertex -> vertex` `
function from `n` to `n`'s immediate dominator
`type idoms = `vertex -> vertex -> bool` `
`idoms x y` is true when `x` is `y`'s immediate dominator
`type dom_tree = `vertex -> vertex list` `
function from `x` to a list of nodes immediately dominated by `x`
`type dominators = `vertex -> vertex list` `
function from node to a list of nodes that dominate it.
`type dom = `vertex -> vertex -> bool` `
`dom x y` returns true iff `x` dominates `y`
`type sdom = `vertex -> vertex -> bool` `
`sdom x y` returns true iff `x` strictly dominates `y`.
`type dom_frontier = `vertex -> vertex list` `
function from `x` to a list of nodes not dominated by `x`, but with predecessors which are dominated by `x`
`val compute_idom : `t ->       vertex -> vertex -> vertex``
Computes the dominator tree, using the Lengauer-Tarjan algorithm. `compute_idom cfg s0` returns a function `idom : V.t -> V.t` s.t. `idom x` returns the immediate dominator of `x`.
`val dominators_to_dom : `('a -> S.t) -> vertex -> 'a -> bool``
Given a function from a node to it's dominators, returns a function `dom : V.t -> V.t -> bool` s.t. `dom x y` returns true when `x` dominates `y`.
`val dominators_to_sdom : `(vertex -> S.t) ->       vertex -> vertex -> bool``
Given a function from a node to it's dominators, returns a function `sdom : V.t -> V.t -> bool` s.t. `sdom x y` returns true when `x` strictly dominates `y`.
`val dom_to_sdom : `(vertex -> vertex -> bool) ->       vertex -> vertex -> bool``
`val dominators_to_sdominators : `(vertex -> S.t) ->       vertex -> S.t``
Given a a function from a node to it's dominators, returns a function from a node to it's strict dominators.
`val dominators_to_idoms : `(vertex -> S.t) ->       vertex -> vertex -> bool``
Given a function from a node to it's dominators, returns a function `idoms : vertex -> vertex -> bool` s.t. `idoms x y` returns true when `x` is the immediate dominator of `y`.
`val dominators_to_dom_tree : `t ->       ?pred:(t -> vertex -> vertex list) ->       (vertex -> S.t) ->       vertex -> S.t``
Computes a dominator tree (function from x to a list of nodes immediately dominated by x) for the given CFG and dominator function. Note: The dominator tree is also called `IDom` by Muchnick. Note: If you are computing a post-dominator tree, then the optional argument pred should be G.succ.
`val idom_to_dom_tree : `t ->       (vertex -> vertex) ->       vertex -> vertex list``
Computes a dominator tree (function from x to a list of nodes immediately dominated by x) for the given CFG and idom function.
`val idom_to_idoms : `idom -> vertex -> vertex -> bool``
`val compute_dom_frontier : `t ->       dom_tree ->       idom -> vertex -> vertex list``
Computes the dominance frontier. As specified in section 19.1 of Modern Compiler Implementation in ML by Andrew Appel.
`val idom_to_dominators : `('a -> 'a) -> 'a -> 'a list``
`val idom_to_dom : `(vertex -> vertex) ->       vertex -> vertex -> bool``