KickJava   Java API By Example, From Geeks To Geeks.

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


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 soot.options.*;
27 import java.util.*;
28 import soot.util.*;
29
30 /**
31  * Constructs a dominator tree structure from the given
32  * DominatorsFinder. The nodes in DominatorTree are of type
33  * DominatorNode.
34  *
35  * <p>
36  *
37  * Note: DominatorTree does not currently implement DirectedGraph
38  * since it provides 4 methods of navigating the nodes where the
39  * meaning of getPredsOf and getSuccsOf diverge from the usual meaning
40  * in a DirectedGraph implementation.
41  *
42  * <p>
43  *
44  * If you need a DirectedGraph implementation, see DominatorTreeAdapter.
45  *
46  * @author Navindra Umanee
47  **/

48 public class DominatorTree
49 {
50     protected DominatorsFinder dominators;
51     protected DirectedGraph graph;
52     protected DominatorNode head;
53     protected ArrayList tails;
54
55     /**
56      * "gode" is a node in the original graph, "dode" is a node in the
57      * dominator tree.
58      **/

59     protected HashMap godeToDode;
60     
61     public DominatorTree(DominatorsFinder dominators)
62     {
63         // if(Options.v().verbose())
64
// G.v().out.println("[" + graph.getBody().getMethod().getName() +
65
// "] Constructing DominatorTree...");
66

67         this.dominators = dominators;
68         this.graph = dominators.getGraph();
69         
70         head = null;
71         tails = new ArrayList();
72         godeToDode = new HashMap();
73         
74         buildTree();
75     }
76
77     /**
78      * Returns the original graph to which the Dominator tree
79      * pertains.
80      **/

81     public DirectedGraph getGraph()
82     {
83         return dominators.getGraph();
84     }
85     
86     /**
87      * Returns the root of the dominator tree.
88      **/

89     public DominatorNode getHead()
90     {
91         return head;
92     }
93
94     /**
95      * Returns a list of the tails of the dominator tree.
96      **/

97     public List getTails()
98     {
99         return (List) tails.clone();
100     }
101
102     /**
103      * Returns the parent of node in the tree, null if the node is at
104      * the root.
105      **/

106     public DominatorNode getParentOf(DominatorNode node)
107     {
108         return node.getParent();
109     }
110
111     /**
112      * Returns the children of node in the tree.
113      **/

114     public List getChildrenOf(DominatorNode node)
115     {
116         return (List)((ArrayList)node.getChildren()).clone();
117     }
118
119     /**
120      * Finds all the predecessors of node in the original
121      * DirectedGraph and returns a list of the corresponding
122      * DominatorNodes.
123      **/

124     public List getPredsOf(DominatorNode node)
125     {
126         List preds = graph.getPredsOf(node.getGode());
127
128         List predNodes = new ArrayList();
129         
130         for(Iterator predsIt = preds.iterator(); predsIt.hasNext();){
131             Object JavaDoc pred = predsIt.next();
132             predNodes.add(getDode(pred));
133         }
134
135         return predNodes;
136     }
137
138     /**
139      * Finds all the successors of node in the original DirectedGraph
140      * and returns a list of the corresponding DominatorNodes.
141      **/

142     public List getSuccsOf(DominatorNode node)
143     {
144         List succs = graph.getSuccsOf(node.getGode());
145
146         List succNodes = new ArrayList();
147         
148         for(Iterator succsIt = succs.iterator(); succsIt.hasNext();){
149             Object JavaDoc succ = succsIt.next();
150             succNodes.add(getDode(succ));
151         }
152
153         return succNodes;
154     }
155
156     /**
157      * Returns true if idom immediately dominates node.
158      **/

159     public boolean isImmediateDominatorOf(DominatorNode idom, DominatorNode node)
160     {
161         // node.getParent() could be null
162
return (node.getParent() == idom);
163     }
164
165     /**
166      * Returns true if dom dominates node.
167      **/

168     public boolean isDominatorOf(DominatorNode dom, DominatorNode node)
169     {
170         return dominators.isDominatedBy(node.getGode(), dom.getGode());
171     }
172
173     /**
174      * Returns the DominatorNode for a given node in the original
175      * DirectedGraph.
176      **/

177     public DominatorNode getDode(Object JavaDoc gode)
178     {
179         DominatorNode dode = (DominatorNode) godeToDode.get(gode);
180
181         if(dode == null)
182             throw new RuntimeException JavaDoc("Assertion failed: Dominator tree does not have a corresponding dode for gode (" + gode + ")");
183
184         return dode;
185     }
186
187     /**
188      * Returns an iterator over the nodes in the tree. No ordering is
189      * implied.
190      **/

191     public Iterator iterator()
192     {
193         return godeToDode.values().iterator();
194     }
195
196     /**
197      * Returns the number of nodes in the tree.
198      **/

199     public int size()
200     {
201         return godeToDode.size();
202     }
203
204     /**
205      * Add all the necessary links between nodes to form a meaningful
206      * tree structure.
207      **/

208     protected void buildTree()
209     {
210         // hook up children with parents and vice-versa
211
{
212             for(Iterator godesIt = graph.iterator(); godesIt.hasNext();){
213                 Object JavaDoc gode = godesIt.next();
214
215                 DominatorNode dode = fetchDode(gode);
216                 DominatorNode parent = fetchParent(gode);
217
218                 if(parent == null){
219                     if(head != null)
220                         throw new RuntimeException JavaDoc("Assertion failed.");
221                     
222                     head = dode;
223                 }
224                 else{
225                     parent.addChild(dode);
226                     dode.setParent(parent);
227                 }
228             }
229         }
230         
231         // identify the tail nodes
232
{
233             for(Iterator dodesIt = this.iterator(); dodesIt.hasNext();){
234                 DominatorNode dode = (DominatorNode) dodesIt.next();
235
236                 if(dode.isTail())
237                     tails.add(dode);
238             }
239         }
240     }
241
242     /**
243      * Convenience method, ensures we don't create more than one
244      * DominatorNode for a given block.
245      **/

246     protected DominatorNode fetchDode(Object JavaDoc gode)
247     {
248         DominatorNode dode;
249         
250         if(godeToDode.containsKey(gode)){
251             dode = (DominatorNode) godeToDode.get(gode);
252         }
253         else{
254             dode = new DominatorNode(gode);
255             godeToDode.put(gode, dode);
256         }
257
258         return dode;
259     }
260
261     protected DominatorNode fetchParent(Object JavaDoc gode)
262     {
263         Object JavaDoc immediateDominator = dominators.getImmediateDominator(gode);
264
265         if(immediateDominator == null)
266             return null;
267         
268         return fetchDode(immediateDominator);
269     }
270 }
271
Popular Tags