Class NumberedDominators<T>

java.lang.Object

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

com.ibm.wala.util.graph.dominators.NumberedDominators<T>

public class NumberedDominators<T>
extends Dominators<T>

Calculate dominators using Lengauer 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

Nested Class Summary

Nested classes/interfaces inherited from class Dominators

Dominators.DominatorInfo

Modifier and Type	Class	Description
protected final class	Dominators.DominatorInfo	LOOK-ASIDE TABLE FOR PER-NODE STATE AND ITS ACCESSORS

Field Summary

Fields inherited from class Dominators

G, reachableNodeCount, root

Modifier and Type	Field	Description
protected final 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 final T	root	the root node from which to build dominators

Constructor Summary

Constructors

Constructor	Description
NumberedDominators(NumberedGraph<T> G, T root)

Method Summary

Modifier and Type	Method	Description
protected final Dominators<T>.DominatorInfo	getInfo(@Nullable T node)

Methods inherited from class Dominators

analyze, dominators, dominatorTree, getIdom, isDominatedBy, make, toString

Modifier and Type	Method	Description
protected void	analyze()	analyze dominators
Iterator<T>	dominators(T node)	return an Iterator over all nodes that dominate node
Graph<T>	dominatorTree()	return the dominator tree, which has an edge from n to n' if n dominates n'
T	getIdom(T node)	return the immediate dominator of node
boolean	isDominatedBy(T node, T master)	is node dominated by master?
static <T> Dominators<T>	make(Graph<T> G, T root)
String	toString()

Methods inherited from class Object

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

Constructor Details

NumberedDominators

public NumberedDominators(NumberedGraph<T> G,
 T root)
                   throws IllegalArgumentException

Throws:

IllegalArgumentException

Method Details

getInfo

protected final Dominators<T>.DominatorInfo getInfo(@Nullable T node)

Specified by:

getInfo in class Dominators<T>