KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > toolkits > graph > CytronDominanceFrontier


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2003 Navindra Umanee <navindra@cs.mcgill.ca>
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */
19
20 package soot.toolkits.graph;
21
22 import soot.*;
23 import soot.toolkits.scalar.*;
24 import soot.toolkits.graph.*;
25 import soot.jimple.*;
26 import java.util.*;
27 import soot.util.*;
28
29 /**
30  * Class to compute the DominanceFrontier using Cytron's celebrated efficient
31  * algorithm.
32  *
33  * @author Navindra Umanee
34  * @see <a
35  * HREF="http://citeseer.nj.nec.com/cytron91efficiently.html">Efficiently
36  * Computing Static Single Assignment Form and the Control Dependence
37  * Graph</a>
38  **/
39 public class CytronDominanceFrontier implements DominanceFrontier
40 {
41     protected DominatorTree dt;
42     protected Map nodeToFrontier;
43     
44     public CytronDominanceFrontier(DominatorTree dt)
45     {
46         this.dt = dt;
47         nodeToFrontier = new HashMap();
48         bottomUpDispatch(dt.getHead());
49     }
50
51     public List getDominanceFrontierOf(DominatorNode node)
52     {
53         ArrayList frontier = (ArrayList) nodeToFrontier.get(node);
54
55         if(frontier == null)
56             throw new RuntimeException JavaDoc("Frontier not defined for node: " + node);
57
58         return (List) frontier.clone();
59     }
60
61     protected boolean isFrontierKnown(DominatorNode node)
62     {
63         return nodeToFrontier.containsKey(node);
64     }
65     
66     /**
67      * Make sure we visit children first. This is reverse topological
68      * order.
69      **/
70     protected void bottomUpDispatch(DominatorNode node)
71     {
72         // *** FIXME: It's annoying that this algorithm is so
73 // *** inefficient in that in traverses the tree from the head
74 // *** to the tail before it does anything.
75
76         if(isFrontierKnown(node))
77             return;
78
79         Iterator children = dt.getChildrenOf(node).iterator();
80
81         while(children.hasNext()){
82             DominatorNode child = (DominatorNode) children.next();
83
84             if(!isFrontierKnown(child))
85                 bottomUpDispatch(child);
86         }
87
88         processNode(node);
89     }
90     
91     /**
92      * Calculate dominance frontier for a set of basic blocks.
93      *
94      * <p> Uses the algorithm of Cytron et al., TOPLAS Oct. 91:
95      *
96      * <pre>
97      * for each X in a bottom-up traversal of the dominator tree do
98      *
99      * DF(X) < - null
100      * for each Y in Succ(X) do
101      * if (idom(Y)!=X) then DF(X) <- DF(X) U Y
102      * end
103      * for each Z in {idom(z) = X} do
104      * for each Y in DF(Z) do
105      * if (idom(Y)!=X) then DF(X) <- DF(X) U Y
106      * end
107      * end
108      * </pre>
109      **/
110     protected void processNode(DominatorNode node)
111     {
112         List dominanceFrontier = new ArrayList();
113         
114         // local
115 {
116             Iterator succsIt = dt.getSuccsOf(node).iterator();
117             
118             while(succsIt.hasNext()){
119                 DominatorNode succ = (DominatorNode) succsIt.next();
120                 
121                 if(!dt.isImmediateDominatorOf(node, succ))
122                     dominanceFrontier.add(succ);
123             }
124         }
125
126         // up
127 {
128             Iterator childIt = dt.getChildrenOf(node).iterator();
129             
130             while(childIt.hasNext()){
131                 DominatorNode child = (DominatorNode) childIt.next();
132                 
133                 Iterator childFrontIt = getDominanceFrontierOf(child).iterator();
134
135                 while(childFrontIt.hasNext()){
136                     DominatorNode childFront = (DominatorNode) childFrontIt.next();
137                     
138                     if(!dt.isImmediateDominatorOf(node, childFront))
139                         dominanceFrontier.add(childFront);
140                 }
141             }
142         }
143         
144         nodeToFrontier.put(node, dominanceFrontier);
145     }
146 }
147
148
Popular Tags