KickJava   Java API By Example, From Geeks To Geeks.

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


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 import java.util.*;
30
31 import soot.*;
32 import soot.util.Chain;
33
34
35     /**
36      * <p>
37      * Represents the control flow graph of a {@link Body} at the basic
38      * block level. Each node of the graph is a {@link Block} while the
39      * edges represent the flow of control from one basic block to
40      * the next.</p>
41      *
42      * <p> This is an abstract base class for different variants of
43      * {@link BlockGraph}, where the variants differ in how they
44      * analyze the control flow between individual units (represented
45      * by passing different variants of {@link UnitGraph} to the
46      * <code>BlockGraph</code> constructor) and in how they identify
47      * block leaders (represented by overriding <code>BlockGraph</code>'s
48      * definition of {@link computeLeaders()}.
49      */

50 public abstract class BlockGraph implements DirectedGraph
51 {
52     Body mBody;
53     Chain mUnits;
54     List mBlocks;
55     List mHeads = new ArrayList();
56     List mTails = new ArrayList();
57
58    
59     /**
60      * Create a <code>BlockGraph</code> representing at the basic block
61      * level the control flow specified, at the <code>Unit</code> level,
62      * by a given {@link UnitGraph}.
63      *
64      * @param unitGraph A representation of the control flow at
65      * the level of individual {@link Unit}s.
66      */

67     protected BlockGraph(UnitGraph unitGraph)
68     {
69         mBody = unitGraph.getBody();
70         mUnits = mBody.getUnits();
71     Set leaders = computeLeaders(unitGraph);
72     buildBlocks(leaders, unitGraph);
73     }
74
75
76     /**
77      * <p>Utility method for computing the basic block leaders for a
78      * {@link Body}, given its {@link UnitGraph} (i.e., the
79      * instructions which begin new basic blocks).</p>
80      *
81      * <p> This implementation designates as basic block leaders :
82      *
83      * <ul>
84      *
85      * <li>Any <code>Unit</code> which has zero predecessors (e.g. the
86      * <code>Unit</code> following a return or unconditional branch) or
87      * more than one predecessor (e.g. a merge point).</li>
88      *
89      * <li><code>Unit</code>s which are the target of any branch (even if
90      * they have no other predecessors and the branch has no other
91      * successors, which is possible for the targets of unconditional
92      * branches or degenerate conditional branches which both branch
93      * and fall through to the same <code>Unit</code>).</li>
94      *
95      * <li>All successors of any <code>Unit</code> which has more than one
96      * successor (this includes the successors of <code>Unit</code>s which
97      * may throw an exception that gets caught within the
98      * <code>Body</code>, as well the successors of conditional
99      * branches).</li>
100      *
101      * <li>The first <code>Unit</code> in any <code>Trap</code> handler.
102      * (Strictly speaking, if <code>unitGraph</code> were a
103      * <code>ExceptionalUnitGraph</code> that included only a single
104      * unexceptional predecessor for some handler&mdash;because no trapped
105      * unit could possibly throw the exception that the handler
106      * catches, while the code preceding the handler fell through to
107      * the handler's code&mdash;then you could merge the handler into the
108      * predecessor's basic block; but such situations occur only in
109      * carefully contrived bytecode.)
110      *
111      * </ul></p>
112      *
113      * @param unitGraph is the <code>Unit</code>-level CFG which is to be split
114      * into basic blocks.
115      *
116      * @return the {@link Set} of {@link Unit}s in <code>unitGraph</code> which
117      * are block leaders.
118      */

119     protected Set computeLeaders(UnitGraph unitGraph) {
120     Body body = unitGraph.getBody();
121     if (body != mBody) {
122         throw new RuntimeException JavaDoc("BlockGraph.computeLeaders() called with a UnitGraph that doesn't match its mBody.");
123     }
124         Set leaders = new HashSet();
125
126     // Trap handlers start new basic blocks, no matter how many
127
// predecessors they have.
128
Chain traps = body.getTraps();
129     for (Iterator trapIt = traps.iterator(); trapIt.hasNext(); ) {
130         Trap trap = (Trap) trapIt.next();
131         leaders.add(trap.getHandlerUnit());
132     }
133
134     for (Iterator unitIt = body.getUnits().iterator(); unitIt.hasNext(); ) {
135         Unit u = (Unit) unitIt.next();
136         List predecessors = unitGraph.getPredsOf(u);
137         int predCount = predecessors.size();
138         List successors = unitGraph.getSuccsOf(u);
139         int succCount = successors.size();
140
141         if (predCount != 1) { // If predCount == 1 but the predecessor
142
leaders.add(u); // is a branch, u will get added by that
143
} // branch's successor test.
144
if ((succCount > 1) || (u.branches())) {
145         for (Iterator it = successors.iterator(); it.hasNext(); ) {
146             leaders.add((Unit) it.next()); // The cast is an
147
} // assertion check.
148
}
149     }
150     return leaders;
151     }
152
153
154     /**
155      * <p>A utility method that does most of the work of constructing
156      * basic blocks, once the set of block leaders has been
157      * determined, and which designates the heads and tails of the graph.</p>
158      *
159      * <p><code>BlockGraph</code> provides an implementation of
160      * <code>buildBlocks()</code> which splits the {@link Unit}s in
161      * <code>unitGraph</code> so that each <code>Unit</code> in the
162      * passed set of block leaders is the first unit in a block. It
163      * defines as heads the blocks which begin with
164      * <code>Unit</code>s which are heads in <code>unitGraph</code>,
165      * and defines as tails the blocks which end with
166      * <code>Unit</code>s which are tails in <code>unitGraph</code>.
167      * Subclasses might override this behavior.
168      *
169      * @param leaders Contains <code>Unit</code>s which are
170      * to be block leaders.
171      *
172      * @param unitGraph Provides information about the predecessors and
173      * successors of each <code>Unit</code> in the <code>Body</code>,
174      * for determining the predecessors and successors of
175      * each created {@link Block}.
176      *
177      * @return a {@link Map} from {@link Unit}s which begin or end a block
178      * to the block which contains them.
179      */

180     protected Map buildBlocks(Set leaders, UnitGraph unitGraph) {
181     List blockList = new ArrayList(leaders.size());
182     Map unitToBlock = new HashMap(); // Maps head and tail units to
183
// their blocks, for building
184
// predecessor and successor lists.
185
Unit blockHead = null;
186     int blockLength = 0;
187     Iterator unitIt = mUnits.iterator();
188     if (unitIt.hasNext()) {
189         blockHead = (Unit) unitIt.next();
190         if (! leaders.contains(blockHead)) {
191         throw new RuntimeException JavaDoc("BlockGraph: first unit not a leader!");
192         }
193         blockLength++;
194     }
195     Unit blockTail = blockHead;
196     int indexInMethod = 0;
197
198     while (unitIt.hasNext()) {
199         Unit u = (Unit) unitIt.next();
200         if (leaders.contains(u)) {
201         addBlock(blockHead, blockTail, indexInMethod, blockLength,
202              blockList, unitToBlock);
203         indexInMethod++;
204         blockHead = u;
205         blockLength = 0;
206         }
207         blockTail = u;
208         blockLength++;
209     }
210     if (blockLength > 0) {
211         // Add final block.
212
addBlock(blockHead, blockTail, indexInMethod, blockLength,
213              blockList, unitToBlock);
214     }
215
216     // The underlying UnitGraph defines heads and tails.
217
for (Iterator it = unitGraph.getHeads().iterator(); it.hasNext(); ) {
218         Unit headUnit = (Unit) it.next();
219         Block headBlock = (Block) unitToBlock.get(headUnit);
220         if (headBlock.getHead() == headUnit) {
221         mHeads.add(headBlock);
222         } else {
223         throw new RuntimeException JavaDoc("BlockGraph(): head Unit is not the first unit in the corresponding Block!");
224         }
225     }
226     for (Iterator it = unitGraph.getTails().iterator(); it.hasNext(); ) {
227         Unit tailUnit = (Unit) it.next();
228         Block tailBlock = (Block) unitToBlock.get(tailUnit);
229         if (tailBlock.getTail() == tailUnit) {
230         mTails.add(tailBlock);
231         } else {
232         throw new RuntimeException JavaDoc("BlockGraph(): tail Unit is not the last unit in the corresponding Block!");
233         }
234     }
235     
236     for (Iterator blockIt = blockList.iterator(); blockIt.hasNext(); ) {
237         Block block = (Block) blockIt.next();
238
239         List predUnits = unitGraph.getPredsOf(block.getHead());
240         List predBlocks = new ArrayList(predUnits.size());
241         for (Iterator predIt = predUnits.iterator(); predIt.hasNext(); ) {
242         Unit predUnit = (Unit) predIt.next();
243         Block predBlock = (Block) unitToBlock.get(predUnit);
244         if (predBlock == null) {
245             throw new RuntimeException JavaDoc("BlockGraph(): block head mapped to null block!");
246         }
247         predBlocks.add(predBlock);
248         }
249
250         if (predBlocks.size() == 0) {
251         block.setPreds(Collections.EMPTY_LIST);
252
253         // If the UnreachableCodeEliminator is not eliminating
254
// unreachable handlers, then they will have no
255
// predecessors, yet not be heads.
256
/* if (! mHeads.contains(block)) {
257             throw new RuntimeException("Block with no predecessors is not a head!");
258
259             // Note that a block can be a head even if it has
260             // predecessors: a handler that might catch an exception
261             // thrown by the first Unit in the method.
262         }
263         */

264         } else {
265         block.setPreds(Collections.unmodifiableList(predBlocks));
266         if (block.getHead() == mUnits.getFirst()) {
267             mHeads.add(block); // Make the first block a head
268
// even if the Body is one huge loop.
269
}
270         }
271
272         List succUnits = unitGraph.getSuccsOf(block.getTail());
273         List succBlocks = new ArrayList(succUnits.size());
274         for (Iterator succIt = succUnits.iterator(); succIt.hasNext(); ) {
275         Unit succUnit = (Unit) succIt.next();
276         Block succBlock = (Block) unitToBlock.get(succUnit);
277         if (succBlock == null) {
278             throw new RuntimeException JavaDoc("BlockGraph(): block tail mapped to null block!");
279         }
280         succBlocks.add(succBlock);
281         }
282         if (succBlocks.size() == 0) {
283         block.setSuccs(Collections.EMPTY_LIST);
284         if (! mTails.contains(block)) {
285             throw new RuntimeException JavaDoc("Block with no successors is not a tail!: " + block.toString());
286             // Note that a block can be a tail even if it has
287
// successors: a return that throws a caught exception.
288
}
289         } else {
290         block.setSuccs(Collections.unmodifiableList(succBlocks));
291         }
292     }
293     mBlocks = Collections.unmodifiableList(blockList);
294     mHeads = Collections.unmodifiableList(mHeads);
295     if (mTails.size() == 0) {
296         mTails = Collections.EMPTY_LIST;
297     } else {
298         mTails = Collections.unmodifiableList(mTails);
299     }
300     return unitToBlock;
301     }
302
303     /**
304      * A utility method which creates a new block and adds information about
305      * it to data structures used to build the graph.
306      *
307      * @param head The first unit in the block.
308      * @param tail The last unit in the block.
309      * @param index The index of this block this {@link Body}.
310      * @param length The number of units in this block.
311      * @param blockList The list of blocks for this method. <code>addBlock()</code>
312      * will add the newly created block to this list.
313      * @param unitToBlock A map from units to blocks. <code>addBlock()</code> will
314      * add mappings from <code>head</code> and <code>tail</code>
315      * to the new block
316      */

317     private void addBlock(Unit head, Unit tail, int index, int length,
318               List blockList, Map unitToBlock) {
319     Block block = new Block(head, tail, mBody, index, length, this);
320     blockList.add(block);
321     unitToBlock.put(tail, block);
322     unitToBlock.put(head, block);
323     }
324      
325     /**
326      * Returns the {@link Body} this {@link BlockGraph} is derived from.
327      * @return The {@link Body} this {@link BlockGraph} is derived from.
328      */

329     public Body getBody()
330     {
331         return mBody;
332     }
333
334     /**
335      * Returns a list of the Blocks composing this graph.
336      * @return A list of the blocks composing this graph
337      * in the same order as they partition underlying Body instance's
338      * unit chain.
339      * @see Block
340      */

341     public List getBlocks()
342     {
343         return mBlocks;
344     }
345
346                
347     public String JavaDoc toString() {
348        
349         Iterator it = mBlocks.iterator();
350         StringBuffer JavaDoc buf = new StringBuffer JavaDoc();
351         while(it.hasNext()) {
352             Block someBlock = (Block) it.next();
353             
354             buf.append(someBlock.toString() + '\n');
355         }
356         
357         return buf.toString();
358     }
359
360     /* DirectedGraph implementation */
361     public List getHeads()
362     {
363         return mHeads;
364     }
365
366     public List getTails()
367     {
368     return mTails;
369     }
370
371     public List getPredsOf(Object JavaDoc o)
372     {
373         Block b = (Block) o;
374         return b.getPreds();
375     }
376
377     public List getSuccsOf(Object JavaDoc o)
378     {
379         Block b = (Block) o;
380         return b.getSuccs();
381     }
382
383     public int size()
384     {
385         return mBlocks.size();
386     }
387
388     public Iterator iterator()
389     {
390         return mBlocks.iterator();
391     }
392 }
393
Popular Tags