Module type Graph__Dominator.S
type dom_frontier
= vertex -> vertex list
function from
x
to a list of nodes not dominated byx
, but with predecessors which are dominated byx
val compute_idom : t -> vertex -> vertex -> vertex
Computes the dominator tree, using the Lengauer-Tarjan algorithm.
compute_idom cfg s0
returns a functionidom : V.t -> V.t
s.t.idom x
returns the immediate dominator ofx
.
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 whenx
dominatesy
.
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 whenx
strictly dominatesy
.
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 whenx
is the immediate dominator ofy
.
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.