Functor Dominator.Make

module Make: 
functor (G : G) -> S with type t = G.t and type vertex = G.V.t
Parameters:
G : G

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