Module Dominator.Make

Parameters

module G : G

Signature

type t = G.t

type of graphs

type vertex = G.V.t

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