KickJava   Java API By Example, From Geeks To Geeks.

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


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 1999 Patrice Pominville, Raja Vallee-Rai
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 /*
21  * Modified by the Sable Research Group and others 1997-2003.
22  * See the 'credits' file distributed with Soot for the complete list of
23  * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
24  */
25
26
27 package soot.toolkits.graph;
28
29
30
31 import soot.*;
32 import soot.util.*;
33 import java.util.*;
34
35 import soot.options.Options;
36
37
38 /**
39  * <p>
40  * Represents a CFG where the nodes are {@link Unit} instances and
41  * edges represent unexceptional and (possibly) exceptional control
42  * flow between <tt>Unit</tt>s.</p>
43  *
44  * <p>
45  * This is an abstract class, providing the facilities used to build
46  * CFGs for specific purposes.</p>
47  */
48
49 public abstract class UnitGraph implements DirectedGraph
50 {
51     List heads;
52     List tails;
53
54     protected Map unitToSuccs;
55     protected Map unitToPreds;
56     protected SootMethod method;
57     protected Body body;
58     protected Chain unitChain;
59
60     /**
61      * Performs the work that is required to construct any sort of
62      * <tt>UnitGraph</tt>.
63      *
64      * @param body The body of the method for which to construct a
65      * control flow graph.
66      */
67     protected UnitGraph( Body body) {
68     this.body = body;
69     unitChain = body.getUnits();
70         method = body.getMethod();
71         if(Options.v().verbose())
72         G.v().out.println("[" + method.getName() + "] Constructing " +
73                   this.getClass().getName() + "...");
74       
75     }
76     
77
78     /**
79      * Utility method for <tt>UnitGraph</tt> constructors. It computes
80      * the edges corresponding to unexceptional control flow.
81      *
82      * @param unitToSuccs A {@link Map} from {@link Unit}s to
83      * {@link List}s of {@link Unit}s. This is
84      * an ``out parameter''; callers must pass an empty
85      * {@link Map}. <tt>buildUnexceptionalEdges</tt> will
86      * add a mapping for every <tt>Unit</tt> in the
87      * body to a list of its unexceptional successors.
88      *
89      * @param unitToPreds A {@link Map} from {@link Unit}s to
90      * {@link List}s of {@link Unit}s. This is an
91      * ``out parameter''; callers must pass an empty
92      * {@link Map}. <tt>buildUnexceptionalEdges</tt> will
93      * add a mapping for every <tt>Unit</tt> in the body
94      * to a list of its unexceptional predecessors.
95      */
96     protected void buildUnexceptionalEdges(Map unitToSuccs, Map unitToPreds) {
97
98     // Initialize the predecessor sets to empty
99 for (Iterator unitIt = unitChain.iterator(); unitIt.hasNext(); ) {
100         unitToPreds.put(unitIt.next(), new ArrayList());
101     }
102     
103     Iterator unitIt = unitChain.iterator();
104     Unit currentUnit, nextUnit;
105                 
106     nextUnit = unitIt.hasNext() ? (Unit) unitIt.next(): null;
107                 
108     while(nextUnit != null) {
109         currentUnit = nextUnit;
110         nextUnit = unitIt.hasNext() ? (Unit) unitIt.next(): null;
111                     
112         List successors = new ArrayList();
113                     
114         if( currentUnit.fallsThrough() ) {
115         // Add the next unit as the successor
116 if(nextUnit != null) {
117             successors.add(nextUnit);
118             ((List) unitToPreds.get(nextUnit)).add(currentUnit);
119         }
120         }
121                         
122         if( currentUnit.branches() ) {
123         for (Iterator targetIt = currentUnit.getUnitBoxes().iterator();
124              targetIt.hasNext(); ) {
125             Unit target = ((UnitBox) targetIt.next()).getUnit();
126             // Arbitrary bytecode can branch to the same
127 // target it falls through to, so we screen for duplicates:
128 if (! successors.contains(target)) {
129             successors.add(target);
130             ((List) unitToPreds.get(target)).add(currentUnit);
131             }
132         }
133         }
134
135         // Store away successors
136 unitToSuccs.put(currentUnit, successors);
137     }
138     }
139
140
141     /**
142      * <p>Utility method used in the construction of {@link UnitGraph}s, to be
143      * called only after the unitToPreds and unitToSuccs maps have
144      * been built.</p>
145      *
146      * <p><code>UnitGraph</code> provides an implementation of
147      * <code>buildHeadsAndTails()</code> which defines the graph's set
148      * of heads to include the first {@link Unit} in the graph's body,
149      * together with any other <tt>Unit</tt> which has no predecessors.
150      * It defines the graph's set of tails to include all
151      * <tt>Unit</tt>s with no successors. Subclasses of
152      * <code>UnitGraph</code> may override this method to change the
153      * criteria for classifying a node as a head or tail.</p>
154      */
155     protected void buildHeadsAndTails() {
156     List tailList = new ArrayList();
157     List headList = new ArrayList();
158
159     for (Iterator unitIt = unitChain.iterator(); unitIt.hasNext(); ) {
160         Unit s = (Unit) unitIt.next();
161         List succs = (List) unitToSuccs.get(s);
162         if(succs.size() == 0) {
163         tailList.add(s);
164         }
165         List preds = (List) unitToPreds.get(s);
166         if(preds.size() == 0) {
167         headList.add(s);
168         }
169     }
170
171     // Add the first Unit, even if it is the target of
172 // a branch.
173 Unit entryPoint = (Unit) unitChain.getFirst();
174     if (! headList.contains(entryPoint)) {
175         headList.add(entryPoint);
176     }
177
178     tails = Collections.unmodifiableList(tailList);
179     heads = Collections.unmodifiableList(headList);
180     }
181
182
183     /**
184      * Utility method that replaces the values of a {@link Map},
185      * which must be instances of {@link List}, with unmodifiable
186      * equivalents.
187      *
188      * @param map The map whose values are to be made unmodifiable.
189      */
190     protected static void makeMappedListsUnmodifiable(Map map) {
191     for (Iterator it = map.entrySet().iterator(); it.hasNext(); ) {
192         Map.Entry entry = (Map.Entry) it.next();
193         List value = (List) entry.getValue();
194         if (value.size() == 0) {
195         entry.setValue(Collections.EMPTY_LIST);
196         } else {
197         entry.setValue(Collections.unmodifiableList(value));
198         }
199     }
200     }
201
202
203     /**
204      * Utility method that produces a new map from the {@link Unit}s
205      * of this graph's body to the union of the values stored in the
206      * two argument {@link Map}s, used to combine the maps of
207      * exceptional and unexceptional predecessors and successors into
208      * maps of all predecessors and successors. The values stored in
209      * both argument maps must be {@link List}s of {@link Unit}s,
210      * which are assumed not to contain any duplicate <tt>Unit</tt>s.
211      *
212      * @param mapA The first map to be combined.
213      *
214      * @param mapB The second map to be combined.
215      */
216     protected Map combineMapValues(Map mapA, Map mapB) {
217     // The duplicate screen
218 Map result = new HashMap(mapA.size() * 2 + 1, 0.7f);
219     for (Iterator chainIt = unitChain.iterator(); chainIt.hasNext(); ) {
220         Unit unit = (Unit) chainIt.next();
221         List listA = (List) mapA.get(unit);
222         if (listA == null) {
223         listA = Collections.EMPTY_LIST;
224         }
225         List listB = (List) mapB.get(unit);
226         if (listB == null) {
227         listB = Collections.EMPTY_LIST;
228         }
229
230         int resultSize = listA.size() + listB.size();
231         if (resultSize == 0) {
232         result.put(unit, Collections.EMPTY_LIST);
233         } else {
234         List resultList = new ArrayList(resultSize);
235         Iterator listIt = null;
236         // As a minor optimization of the duplicate screening,
237 // copy the longer list first.
238 if (listA.size() >= listB.size()) {
239             resultList.addAll(listA);
240             listIt = listB.iterator();
241         } else {
242             resultList.addAll(listB);
243             listIt = listA.iterator();
244         }
245         while (listIt.hasNext()) {
246             Object JavaDoc element = listIt.next();
247             // It is possible for there to be both an exceptional
248 // and an unexceptional edge connecting two Units
249 // (though probably not in a class generated by
250 // javac), so we need to screen for duplicates. On the
251 // other hand, we expect most of these lists to have
252 // only one or two elements, so it doesn't seem worth
253 // the cost to build a Set to do the screening.
254 if (! resultList.contains(element)) {
255             resultList.add(element);
256             }
257         }
258         result.put(unit, Collections.unmodifiableList(resultList));
259         }
260     }
261     return result;
262     }
263
264
265     /**
266      * Utility method for adding an edge to maps representing the CFG.
267      *
268      * @param unitToSuccs The {@link Map} from {@link Unit}s to {@link List}s
269      * of their successors.
270      *
271      * @param unitToPreds The {@link Map} from {@link Unit}s to {@link List}s
272      * of their successors.
273      *
274      * @param head The {@link Unit} from which the edge starts.
275      *
276      * @param tail The {@link Unit} to which the edge flows.
277      */
278     protected void addEdge(Map unitToSuccs, Map unitToPreds,
279                Unit head, Unit tail) {
280     List headsSuccs = (List) unitToSuccs.get(head);
281     if (headsSuccs == null) {
282         headsSuccs = new ArrayList(3); // We expect this list to
283 // remain short.
284 unitToSuccs.put(head, headsSuccs);
285     }
286     if (! headsSuccs.contains(tail)) {
287         headsSuccs.add(tail);
288         List tailsPreds = (List) unitToPreds.get(tail);
289         if (tailsPreds == null) {
290         tailsPreds = new ArrayList();
291         unitToPreds.put(tail, tailsPreds);
292         }
293         tailsPreds.add(head);
294     }
295     }
296
297
298     /**
299      * @return The body from which this UnitGraph was built.
300      *
301      * @see Body
302      */
303     public Body getBody()
304     {
305         return body;
306     }
307
308
309
310   /**
311    * Look for a path in graph, from def to use.
312    * This path has to lie inside an extended basic block
313    * (and this property implies uniqueness.). The path returned
314    * includes from and to.
315    *
316    * @param from start point for the path.
317    * @param to end point for the path.
318    * @return null if there is no such path.
319    */
320   public List getExtendedBasicBlockPathBetween(Unit from, Unit to)
321     {
322         UnitGraph g = this;
323         
324       // if this holds, we're doomed to failure!!!
325 if (g.getPredsOf(to).size() > 1)
326         return null;
327
328       // pathStack := list of succs lists
329 // pathStackIndex := last visited index in pathStack
330 LinkedList pathStack = new LinkedList();
331       LinkedList pathStackIndex = new LinkedList();
332
333       pathStack.add(from);
334       pathStackIndex.add(new Integer JavaDoc(0));
335
336       int psiMax = (g.getSuccsOf((Unit)pathStack.get(0))).size();
337       int level = 0;
338       while (((Integer JavaDoc)pathStackIndex.get(0)).intValue() != psiMax)
339         {
340           int p = ((Integer JavaDoc)(pathStackIndex.get(level))).intValue();
341
342           List succs = g.getSuccsOf((Unit)(pathStack.get(level)));
343           if (p >= succs.size())
344             {
345               // no more succs - backtrack to previous level.
346
347               pathStack.remove(level);
348               pathStackIndex.remove(level);
349
350               level--;
351               int q = ((Integer JavaDoc)pathStackIndex.get(level)).intValue();
352               pathStackIndex.set(level, new Integer JavaDoc(q+1));
353               continue;
354             }
355
356           Unit betweenUnit = (Unit)(succs.get(p));
357
358           // we win!
359 if (betweenUnit == to)
360             {
361               pathStack.add(to);
362               return pathStack;
363             }
364
365           // check preds of betweenUnit to see if we should visit its kids.
366 if (g.getPredsOf(betweenUnit).size() > 1)
367             {
368               pathStackIndex.set(level, new Integer JavaDoc(p+1));
369               continue;
370             }
371
372           // visit kids of betweenUnit.
373 level++;
374           pathStackIndex.add(new Integer JavaDoc(0));
375           pathStack.add(betweenUnit);
376         }
377       return null;
378     }
379
380
381     /* DirectedGraph implementation */
382     public List getHeads()
383     {
384         return heads;
385     }
386
387     public List getTails()
388     {
389         return tails;
390     }
391
392     public List getPredsOf(Object JavaDoc u)
393     {
394         if(!unitToPreds.containsKey(u))
395         throw new NoSuchElementException("Invalid unit " + u);
396
397         return (List) unitToPreds.get(u);
398     }
399
400     public List getSuccsOf(Object JavaDoc u)
401     {
402         if(!unitToSuccs.containsKey(u))
403         throw new NoSuchElementException("Invalid unit " + u);
404
405         return (List) unitToSuccs.get(u);
406     }
407
408     public int size()
409     {
410         return unitChain.size();
411     }
412
413     public Iterator iterator()
414     {
415         return unitChain.iterator();
416     }
417
418     public String JavaDoc toString()
419     {
420         Iterator it = unitChain.iterator();
421         StringBuffer JavaDoc buf = new StringBuffer JavaDoc();
422         while(it.hasNext()) {
423             Unit u = (Unit) it.next();
424             buf.append("// preds: "+getPredsOf(u)+"\n");
425             buf.append(u.toString() + '\n');
426             buf.append("// succs "+getSuccsOf(u)+"\n");
427         }
428         return buf.toString();
429     }
430 }
431
Popular Tags