Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /* Soot - a J*va Optimization Framework
   * Copyright (C) 2003 Navindra Umanee <navindra@cs.mcgill.ca>
   *
   * 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
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  * 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.

Author(s):
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>>();
         bottomUpDispatch(dt.getHead());
     }
 
     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.
         
         if(isFrontierKnown(node))
             return;
 
         Iterator children = .getChildrenOf(node).iterator();
 
         while(children.hasNext()){
             DominatorNode child = (DominatorNodechildren.next();
 
             if(!isFrontierKnown(child))
                 bottomUpDispatch(child);
         }
 
         processNode(node);
     }
    
    
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
      end
      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
        end
      end
 
    protected void processNode(DominatorNode node)
    {
        List<DominatorNodedominanceFrontier = new ArrayList<DominatorNode>();
        
        // local
        {
            Iterator<DominatorNodesuccsIt = .getSuccsOf(node).iterator();
            
            while(succsIt.hasNext()){
                DominatorNode succ = succsIt.next();
                
                if(!.isImmediateDominatorOf(nodesucc))
                    dominanceFrontier.add(succ);
            }
        }
        // up
        {
            Iterator childIt = .getChildrenOf(node).iterator();
            
            while(childIt.hasNext()){
                DominatorNode child = (DominatorNodechildIt.next();
                
                Iterator childFrontIt = getDominanceFrontierOf(child).iterator();
                while(childFrontIt.hasNext()){
                    DominatorNode childFront = (DominatorNodechildFrontIt.next();
                    
                    if(!.isImmediateDominatorOf(nodechildFront))
                        dominanceFrontier.add(childFront);
                }
            }
        }
        
        .put(nodedominanceFrontier);
    }
New to GrepCode? Check out our FAQ X