package ocamlgraph

  1. Overview
  2. Docs
package ocamlgraph
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module Dominator.Make_graphSource

Parameters

module G : I

Signature

include S with type t = G.t and type vertex = G.V.t
Sourcetype t = G.t

type of graphs

Sourcetype vertex = G.V.t

type of vertices

Sourcemodule S : Set.S with type elt = vertex
Sourcetype idom = vertex -> vertex

function from n to n's immediate dominator

Sourcetype idoms = vertex -> vertex -> bool

idoms x y is true when x is y's immediate dominator

Sourcetype dom_tree = vertex -> vertex list

function from x to a list of nodes immediately dominated by x

Sourcetype dominators = vertex -> vertex list

function from node to a list of nodes that dominate it.

Sourcetype dom = vertex -> vertex -> bool

dom x y returns true iff x dominates y

Sourcetype sdom = vertex -> vertex -> bool

sdom x y returns true iff x strictly dominates y.

Sourcetype 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

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval dom_to_sdom : (vertex -> vertex -> bool) -> vertex -> vertex -> bool
Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval 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.

Sourceval idom_to_idoms : idom -> vertex -> vertex -> bool
Sourceval 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.

Sourceval idom_to_dominators : ('a -> 'a) -> 'a -> 'a list
Sourceval idom_to_dom : (vertex -> vertex) -> vertex -> vertex -> bool
Sourceval dom_tree_to_nontrivial_dom : vertex -> dom_tree -> vertex list

Returns a list of the non-trivial dominators of a flowgraph G(v) given the start vertex v and the corresponding dominator tree. E.g., dom_tree_to_nontrivial_dom v (idom_to_dom_tree g (compute_idom g v)). A vertex u is a non-trivial dominator of G(v) if it dominates some vertex w other than v and u.

Sourceval dom_tree_to_snontrivial_dom : vertex -> dom_tree -> S.t

As for dom_tree_to_nontrivial_dom but returns a set.

Sourcetype dom_graph = unit -> t
Sourcetype dom_functions = {
  1. idom : idom;
  2. idoms : idoms;
  3. dom_tree : dom_tree;
  4. dominators : dominators;
  5. dom : dom;
  6. sdom : sdom;
  7. dom_frontier : dom_frontier;
  8. dom_graph : dom_graph;
}
Sourceval compute_dom_graph : G.t -> dom_tree -> G.t
Sourceval 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.