Package soot.toolkits.graph

Class MHGDominatorsFinder<N>

  • All Implemented Interfaces:
    DominatorsFinder<N>
    Direct Known Subclasses:
    MHGPostDominatorsFinder
    public class MHGDominatorsFinder<N>
extends Object
implements DominatorsFinder<N>
    Calculate dominators for basic blocks.

    Uses the algorithm contained in Dragon book, pg. 670-1. 

           D(n0) := { n0 }
       for n in N - { n0 } do D(n) := N;
       while changes to any D(n) occur do
         for n in N - {n0} do
             D(n) := {n} U (intersect of D(p) over all predecessors p of n)
    2007/07/03 - updated to use BitSets instead of HashSets, as the most expensive operation in this algorithm used to be cloning of the fullSet, which is very cheap for BitSets.
    Author:
    Navindra Umanee, Eric Bodden

    • Field Detail

      • heads

        protected final Set<N> heads

      • nodeToFlowSet

        protected final Map<N,​BitSet> nodeToFlowSet

      • nodeToIndex

        protected final Map<N,​Integer> nodeToIndex

      • indexToNode

        protected final Map<Integer,​N> indexToNode

      • lastIndex

        protected int lastIndex

    • Constructor Detail

      • MHGDominatorsFinder

        public MHGDominatorsFinder​(DirectedGraph<N> graph)