BasicBlockIdentifyer


1   /*
2    * Created on Aug 13, 2004
3    * @author Matthias Kempka
4    */
5   package de.uka.ipd.coverage.recording;
6   
7   import java.util.ArrayList  ;
8   import java.util.Iterator  ;
9   import java.util.List  ;
10  
11  import org.apache.bcel.generic.*;
12  
13  /**
14   * @author Matthias Kempka
15   *
16   */
17  /*
18   * Bytecode looks basically like:
19   * ------
20   * 0 instruction 0
21   * 1 branch to 3
22   * 2 instruction 2
23   * 3 instruction 3
24   * 4 instruction 4
25   * 5 branch to 2
26   * 6 return
27   * ------
28   * basic blocks are for this example (from, to):
29   *  (0,1), (2,2), (3,5), (6,6)
30   * 
31   * BlockDelimiters are woven to signal starts and ends of the blocks.
32   * The end of a block is usually a branch, return or throw instruction. Because
33   * those instructions disrupt the instruction flow, the end delimiters must be
34   * inserted before the last instruction of a block. This is called an excluding
35   * end.
36   * In special cases, where a block separated by a branch _target_ (i.e. 
37   * Block (2,2)) the last instruction is no cut in the instruction flow. It is not
38   * right to weave an excluding end here because, for example, the excluded
39   * instruction could be a method call that throws an exception. Thus, the end
40   * delimiter is inserted _after_ the last instruction of a block. This is called
41   * an including end.
42   * 
43   */
44  public class BasicBlockIdentifyer {
45      
46      public static BasicBlock[] getBasicBlocks(RegisteredMethod registeredMethod) {
47          ClassGen classGen = new ClassGen(registeredMethod.getJavaClass());
48          MethodGen method = new MethodGen(registeredMethod.getMethod(), 
49                  classGen.getClassName(), classGen.getConstantPool());
50          
51          InstructionList il = insertBlockDelimiters(method);
52          
53          BasicBlock[] blocks = createBlocksFromInstructionList(registeredMethod, il);
54          
55          setBlockBranches(il, blocks); 
56          
57          return blocks;
58      }
59  
60      /**
61       * Iterates through the InstructionList and creates a BasicBlock array
62       * from the BlockDelimiters in the InstructionList.  
63       * @param registeredMethod
64       * @param il
65       */
66      private static BasicBlock[] createBlocksFromInstructionList(
67              RegisteredMethod registeredMethod, 
68              InstructionList il) {
69          List   blockList = new ArrayList  (il.size());
70          BasicBlockBuilder builder = new BasicBlockBuilder();
71          for (Iterator   iter = il.iterator(); iter.hasNext();) {
72              Instruction element = 
73                  ((InstructionHandle) iter.next()).getInstruction();
74              if (element instanceof BlockDelimiter) {
75                  BlockDelimiter delim = (BlockDelimiter) element;
76                  if (delim.isStartBlock()) {
77                      builder.createBasicBlock();
78                      builder.setRegisteredMethod(registeredMethod);
79                      builder.setStartLine(delim.getPosition());
80                  } else if (delim.isEndBlock()) { 
81                      builder.setEndLine(delim.getPosition());
82                      blockList.add(builder.getBasicBlock());
83                  }
84              }
85          }
86          BasicBlock[] blocks = (BasicBlock[]) blockList.toArray(
87                  new BasicBlock[blockList.size()]);
88          return blocks;
89      }
90  
91      /**
92       * Iterates through the instructionList and sets the block successors 
93       * as needed in the blocks array.
94       * @param il
95       * @param blocks
96       */
97      private static void setBlockBranches(InstructionList il, BasicBlock[] blocks) {
98          for (Iterator   iter = il.iterator(); iter.hasNext();) {
99              Instruction element = ((InstructionHandle) iter.next()).getInstruction();
100             if (element instanceof BlockDelimiter) {
101                 BlockDelimiter delim = (BlockDelimiter) element;
102                 if (delim.isEndBlock()) {
103                     BasicBlock currentBlock = 
104                         searchBlockWithEnd(blocks, delim.getPosition());
105                     int[] targets = delim.getTargets();
106                     for (int i = 0; i < targets.length; i++) {
107                         BasicBlock targetBlock = 
108                             searchBlockWithStart(blocks, targets[i]);
109                         currentBlock.addSuccessor(targetBlock);
110                     }
111                 }
112             }
113         }
114     }
115 
116     /**
117      * @return returns the block of the array that starts with the given startPC
118      */
119     private static BasicBlock searchBlockWithStart(BasicBlock[] blocks, int startPC) {
120         for (int i = 0; i < blocks.length; i++) {
121             if (blocks[i].getStartLine() == startPC) {
122                 return blocks[i];
123             }
124         }
125         throw new AssertionError  ("Block with startline " + startPC + " not found"); //$NON-NLS-1$ //$NON-NLS-2$
126     }
127 
128     /**
129      * @return returns the block of the array that ends with the given endPC
130      */
131     private static BasicBlock searchBlockWithEnd(BasicBlock[] blocks, int endPC) {
132         for (int i = 0; i < blocks.length; i++) {
133             if (blocks[i].getEndLine() == endPC) {
134                 return blocks[i];
135             }
136         }
137         throw new AssertionError  ("Block with endline " + endPC + " not found"); //$NON-NLS-1$ //$NON-NLS-2$
138     }
139 
140     /**
141      * Modify the InstructionList of the given method such that basic blocks
142      * are identified. This is done by weaving in BlockDelimiter instructions
143      * at the appropriate locations.<br>
144      * Branch targets and exception handlers 
145      * are redirected to the appropriate block start. The given
146      * MethodGen is modified. The returned InstructionList is the same as can
147      * be accessed via method.getInstructionList().
148      * @return returns the InstructionList of method with inserted BlockDelimiter
149      * instructions at appropriate locations. There is one BlockDelimiter Instruction
150      * for each block start and end.
151      * @param method
152      */
153     protected static InstructionList insertBlockDelimiters(MethodGen method) {
154         InstructionList il = method.getInstructionList();
155         // no iterator because we insert something in the instruction list
156         // and iterators behaviours is undefined there.
157         InstructionHandle runningHandle = il.getStart();
158         
159         assert !(runningHandle.getInstruction() instanceof BlockDelimiter) :
160                 "InstructionList was already instrumented with block delimiters!"; //$NON-NLS-1$
161         
162         // at the beginning of a method, there is *always* a block start
163         insertStartDelimiter(il, runningHandle, runningHandle.getPosition());
164         
165         while (true) {
166             // make sure we are right after a start block now
167             assert runningHandle.getPrev().getInstruction() 
168                 instanceof BlockDelimiter && 
169                 ((BlockDelimiter) runningHandle.getPrev().getInstruction()).isStartBlock()
170                     : "No start block at begin of iteration!"; //$NON-NLS-1$
171                 
172             // skip until an instruction is found that is a delimiter
173             // those instructions are return, branch and throw instructions,
174             // and BlockDelimiters, of course.
175             while (!isBlockDelimiter(runningHandle.getInstruction())) {
176                 runningHandle = runningHandle.getNext();
177             }
178             if (runningHandle.getInstruction() instanceof BlockDelimiter) {
179                 runningHandle = skipExistingBlockDelimiters(method, 
180                         il, runningHandle);
181                 // we are now right after a block start
182                 continue;
183             }
184             
185             // for branch instruction targets, set block beginnings, if necessary.
186             // before a beginning there is always an ending.
187                 
188             if (runningHandle.getInstruction() instanceof BranchInstruction) {
189                 BranchHandle branchHandle = (BranchHandle) runningHandle;
190                 if (runningHandle.getInstruction() instanceof Select) {
191                     insertSelectTargetDelimiters(il, branchHandle);
192                 }
193                 insertBranchTargetDelimiters(il, branchHandle);
194             }
195 
196             // the only case of an including end is a jump to somewhere where
197             // no jumping instruction leads. This is handled above,
198             // Thus, here is always an excluding end.
199             if (!isEndDelimiter(runningHandle.getPrev().getInstruction())) {
200                 insertEndDelimiter(il, runningHandle, runningHandle.getPosition());
201             }
202             
203             if (runningHandle.getNext() == null) {
204                 break;
205             }
206             
207             // start the next block.
208             runningHandle = runningHandle.getNext();
209 
210             if (!isStartDelimiter(runningHandle.getInstruction())) {
211                 // in special cases there are already end delimiters at this
212                 // position. Therefor we must get the real position from the
213                 // next real instruction.
214                 int nextPosition = getNextPosition(runningHandle);
215                 insertStartDelimiter(il, runningHandle, nextPosition);
216             } else {
217                 runningHandle = runningHandle.getNext();
218             }
219         }
220 
221         redirectExceptionHandlers(method);
222 
223         // check some constraints
224         assert checkConsistency(il); 
225         assert checkBranchTargets(il);
226         assert checkExceptionHandlers(method);
227         
228         
229         return il;
230     }
231 
232     /**
233      * check that every exceptionHandler points to a block start.
234      * @param method
235      */
236     private static boolean checkExceptionHandlers(MethodGen method) {
237         CodeExceptionGen[] eHandlers = method.getExceptionHandlers();
238         for (int i = 0; i < eHandlers.length; i++) {
239             assert isStartDelimiter(eHandlers[i].getHandlerPC().getInstruction()); 
240         }
241         return true;
242     }
243 
244     /**
245      * @param method
246      */
247     private static void redirectExceptionHandlers(MethodGen method) {
248         // the modification of the exceptionHandlers seems to affect 
249         // the method directly, thus no set at the end of this method
250         CodeExceptionGen[] exceptionHandlers = method.getExceptionHandlers();
251         for (int i = 0; i < exceptionHandlers.length; i++) {
252             InstructionHandle excHandler = exceptionHandlers[i].getHandlerPC();
253 
254             assert isStartDelimiter(excHandler.getPrev().getInstruction()) 
255                     : "Expected a start delimiter at the begin of the catch block," //$NON-NLS-1$
256                         + " but there is none at method " + method.getName()  //$NON-NLS-1$
257                         + " for catch block with exception "  //$NON-NLS-1$
258                         + exceptionHandlers[i].getCatchType().getClassName();
259             
260             exceptionHandlers[i].setHandlerPC(excHandler.getPrev());
261         }
262     }
263 
264     /**
265      * @param instruction
266      * @return returns true if the given instruction is a BlockDelimiter
267      * and stands for a block start.
268      */
269     private static boolean isStartDelimiter(Instruction instruction) {
270         if (instruction instanceof BlockDelimiter) {
271             BlockDelimiter delim = (BlockDelimiter) instruction;
272             if (delim.isStartBlock()) {
273                 return true;
274             }
275         }
276         return false;
277     }
278 
279     /**
280      * @param instruction
281      * @return returns true if the given instruction is a BlockDelimiter
282      * and stands for a block end.
283      */
284     private static boolean isEndDelimiter(Instruction instruction) {
285         if (instruction instanceof BlockDelimiter) {
286             BlockDelimiter delim = (BlockDelimiter) instruction;
287             if (delim.isEndBlock()) {
288                 return true;
289             }
290         }
291         return false;
292     }
293 
294     /**
295      * @param il
296      * @param selectHandle
297      */
298     private static void insertSelectTargetDelimiters(
299             InstructionList il, 
300             BranchHandle selectHandle) {
301         Select selectInstruction = (Select) selectHandle.getInstruction();
302         InstructionHandle[] targets = selectInstruction.getTargets();
303 
304         for (int i = 0; i < targets.length; i++) {
305             
306             // insert the delimiters
307             insertStartAndEndDelimiterForBranchTargets(il, targets[i]);
308             
309             // redirect branch targets to the start of the block.
310             if (targets[i].getPrev().getInstruction() instanceof BlockDelimiter) {
311                 // if there is already a block start right before the branchtarget
312                 // set the branchtarget to that block start.
313                 BlockDelimiter delim = 
314                         (BlockDelimiter) targets[i].getPrev().getInstruction();
315                 if (delim.isStartBlock()) {
316                     selectInstruction.setTarget(i, targets[i].getPrev());
317                 }
318                 assert delim.isStartBlock() : "Branch target cannot be redirected. Missing start block"; //$NON-NLS-1$
319                 assert (!delim.isEndBlock()) : 
320                     "Block end right before a branch target _after_ weaving in the branch delimiters"; //$NON-NLS-1$
321             }
322             
323         }
324     }
325 
326     /*
327      * checks if every start is followed by an end and that 
328      * positions are monotone
329      */
330     private static boolean checkConsistency(InstructionList il) {
331         InstructionHandle runnerHandle = il.getStart();
332         int pc = runnerHandle.getPosition();
333         while (runnerHandle.getNext() != null) {
334             while (!(runnerHandle.getInstruction() instanceof BlockDelimiter)) {
335                 assert runnerHandle.getNext() != null : "Instructionlist ends in block"; //$NON-NLS-1$
336 
337                 assert runnerHandle.getPosition() > pc : "Positions not monotone! " +  //$NON-NLS-1$
338                     "Expected PC > " + pc + " but was " + runnerHandle.getPosition(); //$NON-NLS-1$ //$NON-NLS-2$
339                 pc = runnerHandle.getPosition();
340 
341                 runnerHandle = runnerHandle.getNext();
342                 
343             }
344             
345             assert ((BlockDelimiter) runnerHandle.getInstruction()).isStartBlock() :
346                 "Expected start block, but is not!"; //$NON-NLS-1$
347             
348             runnerHandle = runnerHandle.getNext();
349             while (!(runnerHandle.getInstruction() instanceof BlockDelimiter)) {
350                 assert runnerHandle.getNext() != null : 
351                     "InstructionList ends with an end delimiter, " + //$NON-NLS-1$
352                     "but there should be a return or throw."; //$NON-NLS-1$
353                 
354                 assert runnerHandle.getPosition() > pc : "Positions not monoton! " +  //$NON-NLS-1$
355                     "Expected PC > " + pc + " but was " + runnerHandle.getPosition(); //$NON-NLS-1$ //$NON-NLS-2$
356                 pc = runnerHandle.getPosition();
357                 
358                 runnerHandle = runnerHandle.getNext();
359             }
360             
361             assert ((BlockDelimiter) runnerHandle.getInstruction()).isEndBlock() :
362                 "Expected end block, but is not!"; //$NON-NLS-1$
363             
364             runnerHandle = runnerHandle.getNext();
365         }
366         return true;
367     }
368 
369     /*
370      * checks that every branch target is a block start which is a must.
371      */
372     private static boolean checkBranchTargets(InstructionList il) {
373         InstructionHandle runnerHandle = il.getStart();
374         while (runnerHandle != null) {
375             if (runnerHandle instanceof BranchHandle) {
376                 if (runnerHandle.getInstruction() instanceof Select) {
377                     InstructionHandle[] targets = 
378                         ((Select) runnerHandle.getInstruction()).getTargets();
379                     for (int i = 0; i < targets.length; i++) {
380                         assert targets[i].getInstruction() instanceof
381                             BlockDelimiter : " Select target is no block start at " //$NON-NLS-1$
382                                 + "position " + targets[i].getPosition(); //$NON-NLS-1$
383                     }
384                 }
385                 BranchHandle branchHandle = (BranchHandle) runnerHandle;
386                 assert branchHandle.getTarget().getInstruction() instanceof
387                     BlockDelimiter : "Branch target is no block start at position "  //$NON-NLS-1$
388                         + branchHandle.getPosition() ;
389             }
390             runnerHandle = runnerHandle.getNext();
391         }
392         return true;
393     }
394 
395     /**
396      * @param runningHandle
397      */
398     private static int getNextPosition(InstructionHandle runningHandle) {
399         while (runningHandle.getInstruction() instanceof BlockDelimiter) {
400             runningHandle = runningHandle.getNext();
401         }
402         return runningHandle.getPosition();
403     }
404 
405     /**
406      * @param method
407      * @param runningHandle
408      */
409     private static InstructionHandle skipExistingBlockDelimiters(
410             MethodGen method, 
411             InstructionList il,
412             InstructionHandle runningHandle) {
413         assert ((BlockDelimiter) runningHandle.getInstruction()).isEndBlock() :
414                     "BasicBlockIdentifyer, Class: " + method.getClassName()  //$NON-NLS-1$
415                     + ", Method " + method.getName() //$NON-NLS-1$
416                     + " Start block found where an end block was expected!"  //$NON-NLS-1$
417                     + " Blocks won't be right, there is no point in continuing"; //$NON-NLS-1$
418             // runningHandle points to a block end instruction here.
419             // the only case where we find a block end instruction
420             // is if there was a branch target (see method 
421             // insertBranchTargetDelimiters ), and there is always a start
422             // afterwards.
423             // we now skip to the next BlockDelimiter which is this start 
424         do {
425             runningHandle = runningHandle.getNext();
426             if (runningHandle instanceof BranchHandle) {
427                 BranchHandle branchHandle = (BranchHandle) runningHandle;
428                 insertBranchTargetDelimiters(il, branchHandle);
429             }
430         } while (!(runningHandle.getInstruction() 
431                 instanceof BlockDelimiter));
432         // and just once more to the next instruction
433         runningHandle = runningHandle.getNext();
434         return runningHandle;
435     }
436 
437     /**
438      * inserts an end and a start block delimiter before the target of the 
439      * BranchHandle regarding excluding and including ends.
440      * @param il
441      * @param branchHandle
442      */
443     private static void insertBranchTargetDelimiters(
444             InstructionList il, 
445             BranchHandle branchHandle) {
446 
447         InstructionHandle branchTarget = branchHandle.getTarget();
448             
449         if (branchTarget.getInstruction() instanceof BlockDelimiter) {
450             return;
451         }
452         
453         insertStartAndEndDelimiterForBranchTargets(il, branchTarget);
454         
455         redirectBranchTargets(branchHandle);
456     }
457 
458     /**
459      * @param il
460      * @param branchTarget
461      */
462     private static void insertStartAndEndDelimiterForBranchTargets(
463             InstructionList il, 
464             InstructionHandle branchTarget) {
465         // insert the block delimiter if necessary
466         if (!(branchTarget.getPrev().getInstruction() instanceof BlockDelimiter)) {
467             
468             // target is somewhere in the middle of a block
469             // insert the end of the previous block first
470             if (branchTarget.getPrev() != null
471                     && requiresExcludingEnd(branchTarget.getPrev().getInstruction())
472                     //  no null check here, if getPrev is excludeEnd, 
473                     // there is at least a start block instruction here.
474                     && !(branchTarget.getPrev().getPrev().getInstruction()  
475                             instanceof BlockDelimiter) ) {
476                 
477                 // in case of an excluding end that is not already there.
478                 insertEndDelimiter(il, branchTarget.getPrev(), 
479                         branchTarget.getPrev().getPosition());
480             } else {
481                 // in case of an including end
482                 insertEndDelimiter(il, branchTarget, 
483                         branchTarget.getPrev().getPosition());
484             }
485             insertStartDelimiter(il, branchTarget, branchTarget.getPosition());
486         }
487     }
488 
489     private static void redirectBranchTargets(BranchHandle branchHandle) {
490         InstructionHandle branchTarget = branchHandle.getTarget();
491         
492         if (branchTarget.getInstruction() instanceof BlockDelimiter) {
493             return;
494         }
495 
496         // redirect branch targets to the start of the block.
497         if (branchTarget.getPrev().getInstruction() instanceof BlockDelimiter) {
498             // if there is already a block start right before the branchtarget
499             // set the branchtarget to that block start.
500             BlockDelimiter delim = 
501                     (BlockDelimiter) branchTarget.getPrev().getInstruction();
502 
503             assert delim.isStartBlock() : "Branch target cannot be " + //$NON-NLS-1$
504                 "redirected. Missing start block"; //$NON-NLS-1$
505             assert (!delim.isEndBlock()) : 
506                 "Block end right before a branch target _after_ weaving " + //$NON-NLS-1$
507                 "in the branch delimiters"; //$NON-NLS-1$
508             
509             branchHandle.setTarget(branchTarget.getPrev());
510         }
511     }
512 
513     private static void insertStartDelimiter(InstructionList il,
514             InstructionHandle target, int position) {
515 
516         assert position >= 0 : "Start position is " +  //$NON-NLS-1$
517                 position + " but must be >= 0"; //$NON-NLS-1$
518         
519         il.insert(target, new BlockDelimiter(
520                 BlockDelimiter.BLOCK_START,
521                 position));
522     }
523 
524     private static void insertEndDelimiter(InstructionList il,
525             InstructionHandle target, int position) {
526         BlockDelimiter blockDelimiter = new BlockDelimiter(
527                 BlockDelimiter.BLOCK_END,
528                 position);
529         if (target instanceof BranchHandle) { // excluding end before branch target
530             BranchHandle branchHandle = (BranchHandle) target;
531             blockDelimiter.addTarget(getNextPosition(branchHandle.getTarget()));
532             if (target.getInstruction() instanceof Select) {
533                 Select select = (Select) target.getInstruction();
534                 InstructionHandle[] targets = select.getTargets();
535                 for (int i = 0; i < targets.length; i++) {
536                     blockDelimiter.addTarget(getNextPosition(targets[i]));
537                 }
538             }
539             if (!(target.getInstruction() instanceof UnconditionalBranch)) {
540                 blockDelimiter.addTarget(getNextPosition(target.getNext()));
541             }
542         } else if (!requiresExcludingEnd(target.getInstruction())) {
543             blockDelimiter.addTarget(getNextPosition(target));
544         }
545         il.insert(target, blockDelimiter);
546     }
547     
548     /**
549      * @param instruction
550      */
551     private static boolean requiresExcludingEnd(Instruction instruction) {
552         boolean result = false;
553         if (instruction instanceof BranchInstruction 
554                 || instruction instanceof ReturnInstruction
555                 || instruction instanceof ATHROW) {
556             result = true;      
557         }
558         return result;
559     }
560 
561     /**
562      * an instruction is a delimiter if it already is a delimiter or if 
563      * it is an instruction that makes an excluding end necessary.
564      * @param instruction
565      */
566     private static boolean isBlockDelimiter(Instruction instruction) {
567         boolean result = false;
568         if (instruction instanceof BlockDelimiter // may be there 
569                                                   // from branch targets 
570                 || requiresExcludingEnd(instruction)) {
571             result = true;      
572         }
573         return result;
574     }
575 }
576
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags