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

Class 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

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected 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 T root
      the root node from which to build dominators

    • Constructor Summary

      Constructors 
      Constructor Description
      Dominators​(Graph<T> G, T root)  

    • Field Detail

      • 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 Detail

      • Dominators

        public Dominators​(Graph<T> G,
                  T root)
           throws java.lang.IllegalArgumentException
        Parameters:
        G - The graph
        root - The root from which to compute dominators
        Throws:
        java.lang.IllegalArgumentException - if G is null

    • Method Detail

      • isDominatedBy

        public boolean isDominatedBy​(T node,
                             T master)
        is node dominated by master?

      • getIdom

        public T getIdom​(T node)
        return the immediate dominator of node

      • 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

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object