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 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 dominatorsIterator<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'Graph<T>
getGraph()
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)
String
toString()
-
-
-
Constructor Detail
-
Dominators
public Dominators(Graph<T> G, T root) throws IllegalArgumentException
- Parameters:
G
- The graphroot
- The root from which to compute dominators- Throws:
IllegalArgumentException
- if G is null
-
-
Method Detail
-
make
public static <T> Dominators<T> make(Graph<T> G, T root)
-
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.DominatorInfo getInfo(T node)
-
-