Module type `Dominator.S`

type t: type of graphs

type vertex: type of vertices

module S : Stdlib.Set.S with type S.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