Class Dominators<T>
java.lang.Object
com.ibm.wala.util.graph.dominators.Dominators<T>
- Direct Known Subclasses:
GenericDominators
,NumberedDominators
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
Modifier and TypeClassDescriptionprotected final class
LOOK-ASIDE TABLE FOR PER-NODE STATE AND ITS ACCESSORS -
Field Summary
-
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptionprotected void
analyze()
analyze dominatorsdominators
(T node) return an Iterator over all nodes that dominate nodereturn the dominator tree, which has an edge from n to n' if n dominates n'@Nullable T
return the immediate dominator of nodeprotected abstract Dominators<T>.DominatorInfo
boolean
isDominatedBy
(T node, T master) is node dominated by master?static <T> Dominators
<T> toString()
-
Field Details
-
G
-
root
the root node from which to build dominators -
reachableNodeCount
protected int reachableNodeCountthe number of nodes reachable from the root
-
-
Constructor Details
-
Dominators
- Parameters:
G
- The graphroot
- The root from which to compute dominators- Throws:
IllegalArgumentException
- if G is null
-
-
Method Details
-
make
-
isDominatedBy
-
getIdom
-
dominators
-
dominatorTree
-
analyze
protected void analyze()analyze dominators -
getInfo
-
toString
-