Module Dominator.Make_graph
Parameters
Signature
include S with type t = G.t and type vertex = G.V.t
type t
= G.t
type of graphs
type vertex
= G.V.t
type of vertices
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.
type dom_graph
= unit -> t
type dom_functions
=
{
idom : idom;
idoms : idoms;
dom_tree : dom_tree;
dominators : dominators;
dom : dom;
sdom : sdom;
dom_frontier : dom_frontier;
dom_graph : dom_graph;
}
val compute_dom_graph : G.t -> dom_tree -> G.t
val compute_all : G.t -> vertex -> dom_functions
Computes all dominance functions.
This function computes some things eagerly and some lazily, so don't worry about it doing extra work to compute functions you don't need, but also don't call it if you aren't going to use anything it returns.
- returns
a record containing all dominance functions for the given graph and entry node.