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

Class GenericDominators<T>

java.lang.Object

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

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

public class GenericDominators<T>
extends Dominators<T>

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/interfaces inherited from class com.ibm.wala.util.graph.dominators.Dominators

Dominators.DominatorInfo

Field Summary

Fields inherited from class com.ibm.wala.util.graph.dominators.Dominators

G, reachableNodeCount, root

Constructor Summary

Constructors

Constructor	Description
GenericDominators(Graph<T> G, T root)

Method Summary

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

Methods inherited from class com.ibm.wala.util.graph.dominators.Dominators

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

Methods inherited from class java.lang.Object

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

Constructor Details

GenericDominators

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

Throws:

IllegalArgumentException

Method Details

getInfo

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

Specified by:

getInfo in class Dominators<T>