com.ibm.wala.util.graph
Class Dominators<T>

java.lang.Object
  com.ibm.wala.util.graph.Dominators<T>

Direct Known Subclasses:

DominanceFrontiers

public class Dominators<T>
extends java.lang.Object

Calculate dominators using Langauer and Tarjan's fastest algorithm. TOPLAS 1(1), July 1979. This implementation uses path compression and results in a O(e * alpha(e,n)) complexity, where e is the number of edges in the CFG and n is the number of nodes. Sources: TOPLAS article, Muchnick book

Field Summary

protected Graph<T>	G a convenient place to locate the graph to avoid passing it internally
protected int	reachableNodeCount the number of nodes reachable from the root
protected T	root the root node from which to build dominators

Constructor Summary

Dominators(Graph<T> G, T root)

Method Summary

java.util.Iterator<T>	dominators(T node)
Graph<T>	dominatorTree()
T	getIdom(T node)
boolean	isDominatedBy(T node, T master)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

G

protected final Graph<T> G

a convenient place to locate the graph to avoid passing it internally

root

protected final T root

the root node from which to build dominators

reachableNodeCount

protected int reachableNodeCount

the number of nodes reachable from the root

Constructor Detail

Dominators

public Dominators(Graph<T> G,
                  T root)
           throws java.lang.IllegalArgumentException

Parameters:

G - The graph

root - The root from which to compute dominators

Throws:

java.lang.IllegalArgumentException - if G is null

Method Detail

isDominatedBy

public boolean isDominatedBy(T node,
                             T master)

getIdom

public T getIdom(T node)

dominators

public java.util.Iterator<T> dominators(T node)

dominatorTree

public Graph<T> dominatorTree()