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   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   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   gode)
178     {
179         DominatorNode dode = (DominatorNode) godeToDode.get(gode);
180 
181         if(dode == null)
182             throw new RuntimeException  ("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   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  ("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   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   gode)
262     {
263         Object   immediateDominator = dominators.getImmediateDominator(gode);
264 
265         if(immediateDominator == null)
266             return null;
267         
268         return fetchDode(immediateDominator);
269     }
270 }
271
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags