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

      • isDominatedBy

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

        public Graph<T> getGraph()
      • getIdom

        public T getIdom​(T node)
        return the immediate dominator of node
      • 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