# 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