001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 1999 Patrice Pominville, Raja Vallee-Rai
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019:
020: /*
021: * Modified by the Sable Research Group and others 1997-2003.
022: * See the 'credits' file distributed with Soot for the complete list of
023: * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
024: */
025:
026: package soot.toolkits.graph;
027:
028: import java.util.*;
029:
030: import soot.*;
031: import soot.util.Chain;
032:
033: /**
034: * <p>
035: * Represents the control flow graph of a {@link Body} at the basic
036: * block level. Each node of the graph is a {@link Block} while the
037: * edges represent the flow of control from one basic block to
038: * the next.</p>
039: *
040: * <p> This is an abstract base class for different variants of
041: * {@link BlockGraph}, where the variants differ in how they
042: * analyze the control flow between individual units (represented
043: * by passing different variants of {@link UnitGraph} to the
044: * <code>BlockGraph</code> constructor) and in how they identify
045: * block leaders (represented by overriding <code>BlockGraph</code>'s
046: * definition of {@link computeLeaders()}.
047: */
048: public abstract class BlockGraph implements DirectedGraph {
049: Body mBody;
050: Chain mUnits;
051: List mBlocks;
052: List mHeads = new ArrayList();
053: List mTails = new ArrayList();
054:
055: /**
056: * Create a <code>BlockGraph</code> representing at the basic block
057: * level the control flow specified, at the <code>Unit</code> level,
058: * by a given {@link UnitGraph}.
059: *
060: * @param unitGraph A representation of the control flow at
061: * the level of individual {@link Unit}s.
062: */
063: protected BlockGraph(UnitGraph unitGraph) {
064: mBody = unitGraph.getBody();
065: mUnits = mBody.getUnits();
066: Set<Unit> leaders = computeLeaders(unitGraph);
067: buildBlocks(leaders, unitGraph);
068: }
069:
070: /**
071: * <p>Utility method for computing the basic block leaders for a
072: * {@link Body}, given its {@link UnitGraph} (i.e., the
073: * instructions which begin new basic blocks).</p>
074: *
075: * <p> This implementation designates as basic block leaders :
076: *
077: * <ul>
078: *
079: * <li>Any <code>Unit</code> which has zero predecessors (e.g. the
080: * <code>Unit</code> following a return or unconditional branch) or
081: * more than one predecessor (e.g. a merge point).</li>
082: *
083: * <li><code>Unit</code>s which are the target of any branch (even if
084: * they have no other predecessors and the branch has no other
085: * successors, which is possible for the targets of unconditional
086: * branches or degenerate conditional branches which both branch
087: * and fall through to the same <code>Unit</code>).</li>
088: *
089: * <li>All successors of any <code>Unit</code> which has more than one
090: * successor (this includes the successors of <code>Unit</code>s which
091: * may throw an exception that gets caught within the
092: * <code>Body</code>, as well the successors of conditional
093: * branches).</li>
094: *
095: * <li>The first <code>Unit</code> in any <code>Trap</code> handler.
096: * (Strictly speaking, if <code>unitGraph</code> were a
097: * <code>ExceptionalUnitGraph</code> that included only a single
098: * unexceptional predecessor for some handler—because no trapped
099: * unit could possibly throw the exception that the handler
100: * catches, while the code preceding the handler fell through to
101: * the handler's code—then you could merge the handler into the
102: * predecessor's basic block; but such situations occur only in
103: * carefully contrived bytecode.)
104: *
105: * </ul></p>
106: *
107: * @param unitGraph is the <code>Unit</code>-level CFG which is to be split
108: * into basic blocks.
109: *
110: * @return the {@link Set} of {@link Unit}s in <code>unitGraph</code> which
111: * are block leaders.
112: */
113: protected Set<Unit> computeLeaders(UnitGraph unitGraph) {
114: Body body = unitGraph.getBody();
115: if (body != mBody) {
116: throw new RuntimeException(
117: "BlockGraph.computeLeaders() called with a UnitGraph that doesn't match its mBody.");
118: }
119: Set<Unit> leaders = new HashSet<Unit>();
120:
121: // Trap handlers start new basic blocks, no matter how many
122: // predecessors they have.
123: Chain traps = body.getTraps();
124: for (Iterator trapIt = traps.iterator(); trapIt.hasNext();) {
125: Trap trap = (Trap) trapIt.next();
126: leaders.add(trap.getHandlerUnit());
127: }
128:
129: for (Iterator unitIt = body.getUnits().iterator(); unitIt
130: .hasNext();) {
131: Unit u = (Unit) unitIt.next();
132: List predecessors = unitGraph.getPredsOf(u);
133: int predCount = predecessors.size();
134: List successors = unitGraph.getSuccsOf(u);
135: int succCount = successors.size();
136:
137: if (predCount != 1) { // If predCount == 1 but the predecessor
138: leaders.add(u); // is a branch, u will get added by that
139: } // branch's successor test.
140: if ((succCount > 1) || (u.branches())) {
141: for (Iterator it = successors.iterator(); it.hasNext();) {
142: leaders.add((Unit) it.next()); // The cast is an
143: } // assertion check.
144: }
145: }
146: return leaders;
147: }
148:
149: /**
150: * <p>A utility method that does most of the work of constructing
151: * basic blocks, once the set of block leaders has been
152: * determined, and which designates the heads and tails of the graph.</p>
153: *
154: * <p><code>BlockGraph</code> provides an implementation of
155: * <code>buildBlocks()</code> which splits the {@link Unit}s in
156: * <code>unitGraph</code> so that each <code>Unit</code> in the
157: * passed set of block leaders is the first unit in a block. It
158: * defines as heads the blocks which begin with
159: * <code>Unit</code>s which are heads in <code>unitGraph</code>,
160: * and defines as tails the blocks which end with
161: * <code>Unit</code>s which are tails in <code>unitGraph</code>.
162: * Subclasses might override this behavior.
163: *
164: * @param leaders Contains <code>Unit</code>s which are
165: * to be block leaders.
166: *
167: * @param unitGraph Provides information about the predecessors and
168: * successors of each <code>Unit</code> in the <code>Body</code>,
169: * for determining the predecessors and successors of
170: * each created {@link Block}.
171: *
172: * @return a {@link Map} from {@link Unit}s which begin or end a block
173: * to the block which contains them.
174: */
175: protected Map buildBlocks(Set<Unit> leaders, UnitGraph unitGraph) {
176: List blockList = new ArrayList(leaders.size());
177: Map unitToBlock = new HashMap(); // Maps head and tail units to
178: // their blocks, for building
179: // predecessor and successor lists.
180: Unit blockHead = null;
181: int blockLength = 0;
182: Iterator unitIt = mUnits.iterator();
183: if (unitIt.hasNext()) {
184: blockHead = (Unit) unitIt.next();
185: if (!leaders.contains(blockHead)) {
186: throw new RuntimeException(
187: "BlockGraph: first unit not a leader!");
188: }
189: blockLength++;
190: }
191: Unit blockTail = blockHead;
192: int indexInMethod = 0;
193:
194: while (unitIt.hasNext()) {
195: Unit u = (Unit) unitIt.next();
196: if (leaders.contains(u)) {
197: addBlock(blockHead, blockTail, indexInMethod,
198: blockLength, blockList, unitToBlock);
199: indexInMethod++;
200: blockHead = u;
201: blockLength = 0;
202: }
203: blockTail = u;
204: blockLength++;
205: }
206: if (blockLength > 0) {
207: // Add final block.
208: addBlock(blockHead, blockTail, indexInMethod, blockLength,
209: blockList, unitToBlock);
210: }
211:
212: // The underlying UnitGraph defines heads and tails.
213: for (Iterator it = unitGraph.getHeads().iterator(); it
214: .hasNext();) {
215: Unit headUnit = (Unit) it.next();
216: Block headBlock = (Block) unitToBlock.get(headUnit);
217: if (headBlock.getHead() == headUnit) {
218: mHeads.add(headBlock);
219: } else {
220: throw new RuntimeException(
221: "BlockGraph(): head Unit is not the first unit in the corresponding Block!");
222: }
223: }
224: for (Iterator it = unitGraph.getTails().iterator(); it
225: .hasNext();) {
226: Unit tailUnit = (Unit) it.next();
227: Block tailBlock = (Block) unitToBlock.get(tailUnit);
228: if (tailBlock.getTail() == tailUnit) {
229: mTails.add(tailBlock);
230: } else {
231: throw new RuntimeException(
232: "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
242: .hasNext();) {
243: Unit predUnit = (Unit) predIt.next();
244: Block predBlock = (Block) unitToBlock.get(predUnit);
245: if (predBlock == null) {
246: throw new RuntimeException(
247: "BlockGraph(): block head mapped to null block!");
248: }
249: predBlocks.add(predBlock);
250: }
251:
252: if (predBlocks.size() == 0) {
253: block.setPreds(Collections.EMPTY_LIST);
254:
255: // If the UnreachableCodeEliminator is not eliminating
256: // unreachable handlers, then they will have no
257: // predecessors, yet not be heads.
258: /* if (! mHeads.contains(block)) {
259: throw new RuntimeException("Block with no predecessors is not a head!");
260:
261: // Note that a block can be a head even if it has
262: // predecessors: a handler that might catch an exception
263: // thrown by the first Unit in the method.
264: }
265: */
266: } else {
267: block
268: .setPreds(Collections
269: .unmodifiableList(predBlocks));
270: if (block.getHead() == mUnits.getFirst()) {
271: mHeads.add(block); // Make the first block a head
272: // even if the Body is one huge loop.
273: }
274: }
275:
276: List succUnits = unitGraph.getSuccsOf(block.getTail());
277: List succBlocks = new ArrayList(succUnits.size());
278: for (Iterator succIt = succUnits.iterator(); succIt
279: .hasNext();) {
280: Unit succUnit = (Unit) succIt.next();
281: Block succBlock = (Block) unitToBlock.get(succUnit);
282: if (succBlock == null) {
283: throw new RuntimeException(
284: "BlockGraph(): block tail mapped to null block!");
285: }
286: succBlocks.add(succBlock);
287: }
288: if (succBlocks.size() == 0) {
289: block.setSuccs(Collections.EMPTY_LIST);
290: if (!mTails.contains(block)) {
291: throw new RuntimeException(
292: "Block with no successors is not a tail!: "
293: + block.toString());
294: // Note that a block can be a tail even if it has
295: // successors: a return that throws a caught exception.
296: }
297: } else {
298: block
299: .setSuccs(Collections
300: .unmodifiableList(succBlocks));
301: }
302: }
303: mBlocks = Collections.unmodifiableList(blockList);
304: mHeads = Collections.unmodifiableList(mHeads);
305: if (mTails.size() == 0) {
306: mTails = Collections.EMPTY_LIST;
307: } else {
308: mTails = Collections.unmodifiableList(mTails);
309: }
310: return unitToBlock;
311: }
312:
313: /**
314: * A utility method which creates a new block and adds information about
315: * it to data structures used to build the graph.
316: *
317: * @param head The first unit in the block.
318: * @param tail The last unit in the block.
319: * @param index The index of this block this {@link Body}.
320: * @param length The number of units in this block.
321: * @param blockList The list of blocks for this method. <code>addBlock()</code>
322: * will add the newly created block to this list.
323: * @param unitToBlock A map from units to blocks. <code>addBlock()</code> will
324: * add mappings from <code>head</code> and <code>tail</code>
325: * to the new block
326: */
327: private void addBlock(Unit head, Unit tail, int index, int length,
328: List blockList, Map unitToBlock) {
329: Block block = new Block(head, tail, mBody, index, length, this );
330: blockList.add(block);
331: unitToBlock.put(tail, block);
332: unitToBlock.put(head, block);
333: }
334:
335: /**
336: * Returns the {@link Body} this {@link BlockGraph} is derived from.
337: * @return The {@link Body} this {@link BlockGraph} is derived from.
338: */
339: public Body getBody() {
340: return mBody;
341: }
342:
343: /**
344: * Returns a list of the Blocks composing this graph.
345: * @return A list of the blocks composing this graph
346: * in the same order as they partition underlying Body instance's
347: * unit chain.
348: * @see Block
349: */
350: public List getBlocks() {
351: return mBlocks;
352: }
353:
354: public String toString() {
355:
356: Iterator it = mBlocks.iterator();
357: StringBuffer buf = new StringBuffer();
358: while (it.hasNext()) {
359: Block someBlock = (Block) it.next();
360:
361: buf.append(someBlock.toString() + '\n');
362: }
363:
364: return buf.toString();
365: }
366:
367: /* DirectedGraph implementation */
368: public List getHeads() {
369: return mHeads;
370: }
371:
372: public List getTails() {
373: return mTails;
374: }
375:
376: public List getPredsOf(Object o) {
377: Block b = (Block) o;
378: return b.getPreds();
379: }
380:
381: public List getSuccsOf(Object o) {
382: Block b = (Block) o;
383: return b.getSuccs();
384: }
385:
386: public int size() {
387: return mBlocks.size();
388: }
389:
390: public Iterator iterator() {
391: return mBlocks.iterator();
392: }
393: }
|