## Parameters

`module G : I`

## Signature

`include S with type t = G.t and type vertex = G.V.t`
`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.

`type dom_graph = unit -> t`
`type dom_functions = {`

1. `idom : idom;`
2. `idoms : idoms;`
3. `dom_tree : dom_tree;`
4. `dominators : dominators;`
5. `dom : dom;`
6. `sdom : sdom;`
7. `dom_frontier : dom_frontier;`
8. `dom_graph : dom_graph;`

`}`
`val compute_dom_graph : G.t -> dom_tree -> G.t`
`val compute_all : G.t -> vertex -> dom_functions`

Computes all dominance functions.

This function computes some things eagerly and some lazily, so don't worry about it doing extra work to compute functions you don't need, but also don't call it if you aren't going to use anything it returns.

- returns

  a record containing all dominance functions for the given graph and entry node.