## Parameters

`module G : G`

## Signature

`type t = G.t`

type of graphs

`type vertex = G.V.t`

type of vertices

`module S : Stdlib.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`
`val dom_tree_to_nontrivial_dom : vertex -> dom_tree -> vertex list`

Returns a list of the non-trivial dominators of a flowgraph G(v) given the start vertex `v` and the corresponding dominator tree. E.g., `dom_tree_to_nontrivial_dom v (idom_to_dom_tree g (compute_idom g v))`. A vertex u is a non-trivial dominator of G(v) if it dominates some vertex w other than v and u.

`val dom_tree_to_snontrivial_dom : vertex -> dom_tree -> S.t`

As for `dom_tree_to_nontrivial_dom` but returns a set.