Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /* Soot - a J*va Optimization Framework
   * Copyright (C) 2005 Navindra Umanee <>
   * Copyright (C) 2007 Eric Bodden
   * This library is free software; you can redistribute it and/or
   * modify it under the terms of the GNU Lesser General Public
   * License as published by the Free Software Foundation; either
   * version 2.1 of the License, or (at your option) any later version.
  * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * Lesser General Public License for more details.
  * You should have received a copy of the GNU Lesser General Public
  * License along with this library; if not, write to the
  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  * Boston, MA 02111-1307, USA.
 package soot.toolkits.graph;
 import java.util.List;
 import java.util.Map;

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 java.util.BitSets instead of java.util.HashSets, as the most expensive operation in this algorithm used to be cloning of the fullSet, which is very cheap for java.util.BitSets.

Navindra Umanee
Eric Bodden
 public class MHGDominatorsFinder<N> implements DominatorsFinder<N>
     protected DirectedGraph<N> graph;
     protected BitSet fullSet;
     protected List<N> heads;
     protected Map<N,BitSetnodeToFlowSet;
     protected Map<N,IntegernodeToIndex;
     protected Map<Integer,N> indexToNode;
     protected int lastIndex = 0;
     public MHGDominatorsFinder(DirectedGraph<N> graph)
         this. = graph;
     protected void doAnalysis()
          = .getHeads();
          = new HashMap<N, BitSet>();
          = new HashMap<N, Integer>();
          = new HashMap<Integer,N>();
         //build full set
          = new BitSet(.size());
         .flip(0, .size());//set all to true
         //set up domain for intersection: head nodes are only dominated by themselves,
         //other nodes are dominated by everything else
         for(Iterator<N> i = .iterator(); i.hasNext();){
             N o =;
                 BitSet self = new BitSet();
         boolean changed = true;
             changed = false;
             for(Iterator<N> i = .iterator(); i.hasNext();){
                 N o =;
                 if(.contains(o)) continue;
                 //initialize to the "neutral element" for the intersection
                 //this clone() is fast on BitSets (opposed to on HashSets)
 				BitSet predsIntersect = (BitSet.clone();
                //intersect over all predecessors
                for(Iterator<N> j = .getPredsOf(o).iterator(); j.hasNext();){
                    BitSet predSet = .get(;
                BitSet oldSet = .get(o);
                //each node dominates itself
                    changed = true;
        } while(changed);
    protected int indexOf(N o) {
        Integer index = .get(o);
        if(index==null) {
            index = ;
        return index;
    public DirectedGraph<N> getGraph()
        return ;
    public List<N> getDominators(Object node)
        //reconstruct list of dominators from bitset
        List<N> result = new ArrayList<N>();
        BitSet bitSet = .get(node);
        for(int i=0;i<bitSet.length();i++) {
            if(bitSet.get(i)) {
        return result;
    public N getImmediateDominator(Object node)
        // root node
            return null;
	// could be memoised, I guess
        List<N> dominatorsList = getDominators(node);
        Iterator<N> dominatorsIt = dominatorsList.iterator();
        N immediateDominator = null;
        while((immediateDominator == null) && dominatorsIt.hasNext()){
            N dominator =;
                immediateDominator = dominator;
        assert immediateDominator!=null;
        return immediateDominator;
    public boolean isDominatedBy(N node, N dominator)
        return getDominators(node).contains(dominator);
    public boolean isDominatedByAll(N nodeCollection<N> dominators)
        return getDominators(node).containsAll(dominators);
New to GrepCode? Check out our FAQ X