Package com.ibm.wala.util.graph.dominators

Class Dominators<T>

java.lang.Object

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

Direct Known Subclasses:

GenericDominators, NumberedDominators

public abstract class Dominators<T>
extends 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

Nested Class Summary

Nested Classes

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

Field Summary

Fields

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
Dominators(Graph<T> G, T root)

Method Summary

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'
@Nullable T	getIdom(@Nullable T node)	return the immediate dominator of node
protected abstract Dominators<T>.DominatorInfo	getInfo(@Nullable T 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 java.lang.Object

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

Field Details

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 Details

Dominators

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

Parameters:

G - The graph

root - The root from which to compute dominators

Throws:

IllegalArgumentException - if G is null

Method Details

make

public static <T> Dominators<T> make(Graph<T> G,
 T root)

isDominatedBy

public boolean isDominatedBy(T node,
 T master)

is node dominated by master?

getIdom

public @Nullable T getIdom(@Nullable T node)

return the immediate dominator of node

dominators

public Iterator<T> dominators(T node)

return an Iterator over all nodes that dominate node

dominatorTree

public Graph<T> dominatorTree()

return the dominator tree, which has an edge from n to n' if n dominates n'

analyze

protected void analyze()

analyze dominators

getInfo

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

toString

public String toString()

Overrides:

toString in class Object