Dominator.S
function from x
to a list of nodes not dominated by x
, but with predecessors which are dominated by x
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
.
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
.
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
.
Given a a function from a node to it's dominators, returns a function from a node to it's strict dominators.
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.
Computes a dominator tree (function from x to a list of nodes immediately dominated by x) for the given CFG and idom function.
Computes the dominance frontier. As specified in section 19.1 of Modern Compiler Implementation in ML by Andrew Appel.