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  ("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  ("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  ("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  ("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  ("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  ("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  ("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   toString() {
348        
349         Iterator it = mBlocks.iterator();
350         StringBuffer   buf = new StringBuffer  ();
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   o)
372     {
373         Block b = (Block) o;
374         return b.getPreds();
375     }
376 
377     public List getSuccsOf(Object   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
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags