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

  • Field Details

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

  • Method Details

    • make

      public static <T> Dominators<T> make(Graph<T> G, T root)
    • isDominatedBy

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

      public @Nullable T getIdom(@Nullable 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
    • getInfo

      protected abstract Dominators<T>.DominatorInfo getInfo(@Nullable T node)
    • toString

      public String toString()
      Overrides:
      toString in class Object