Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /* Soot - a J*va Optimization Framework
   * Copyright (C) 2003 Navindra Umanee <>
   * 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.*;

Class to compute the DominanceFrontier using Cytron's celebrated efficient algorithm.

Navindra Umanee
See also:
Efficiently Computing Static Single Assignment Form and the Control Dependence Graph
 public class CytronDominanceFrontier implements DominanceFrontier
     protected DominatorTree dt;
         this. = dt;
          = new HashMap<DominatorNodeList<DominatorNode>>();
     public List getDominanceFrontierOf(DominatorNode node)
         ArrayList frontier = (ArrayList.get(node);
         if(frontier == null)
             throw new RuntimeException("Frontier not defined for node: " + node);
         return (Listfrontier.clone();
     protected boolean isFrontierKnown(DominatorNode node)
         return .containsKey(node);
Make sure we visit children first. This is reverse topological order.
     protected void bottomUpDispatch(DominatorNode node)
         // *** FIXME: It's annoying that this algorithm is so
         // *** inefficient in that in traverses the tree from the head
         // *** to the tail before it does anything.
         Iterator children = .getChildrenOf(node).iterator();
             DominatorNode child = (;
Calculate dominance frontier for a set of basic blocks.

Uses the algorithm of Cytron et al., TOPLAS Oct. 91:

 for each X in a bottom-up traversal of the dominator tree do

      DF(X) < - null
      for each Y in Succ(X) do
        if (idom(Y)!=X) then DF(X) <- DF(X) U Y
      for each Z in {idom(z) = X} do
        for each Y in DF(Z) do
              if (idom(Y)!=X) then DF(X) <- DF(X) U Y
    protected void processNode(DominatorNode node)
        List<DominatorNodedominanceFrontier = new ArrayList<DominatorNode>();
        // local
            Iterator<DominatorNodesuccsIt = .getSuccsOf(node).iterator();
                DominatorNode succ =;
        // up
            Iterator childIt = .getChildrenOf(node).iterator();
                DominatorNode child = (;
                Iterator childFrontIt = getDominanceFrontierOf(child).iterator();
                    DominatorNode childFront = (;
New to GrepCode? Check out our FAQ X