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 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
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected class
Dominators.DominatorInfo
LOOK-ASIDE TABLE FOR PER-NODE STATE AND ITS ACCESSORS
-
Constructor Summary
Constructors Constructor Description Dominators(Graph<T> G, T root)
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description protected void
analyze()
analyze dominatorsjava.util.Iterator<T>
dominators(T node)
return an Iterator over all nodes that dominate nodeGraph<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 nodeprotected abstract Dominators.DominatorInfo
getInfo(T node)
boolean
isDominatedBy(T node, T master)
is node dominated by master?static <T> Dominators<T>
make(Graph<T> G, T root)
java.lang.String
toString()
-
-
-
Method Detail
-
make
public static <T> Dominators<T> make(Graph<T> G, T root)
-
dominators
public java.util.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.DominatorInfo getInfo(T node)
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-