001/*
002 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 *  This file is licensed to You under the Eclipse Public License (EPL);
005 *  You may not use this file except in compliance with the License. You
006 *  may obtain a copy of the License at
007 *
008 *      http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 *  See the COPYRIGHT.txt file distributed with this work for information
011 *  regarding copyright ownership.
012 */
013package org.jikesrvm.compilers.baseline;
014
015import static org.jikesrvm.classloader.BytecodeConstants.*;
016
017import org.jikesrvm.VM;
018import org.jikesrvm.classloader.BytecodeStream;
019import org.jikesrvm.classloader.ExceptionHandlerMap;
020import org.jikesrvm.classloader.MethodReference;
021import org.jikesrvm.classloader.NormalMethod;
022
023/**
024 * Analyze the byte codes and determine the boundaries of the
025 * basic blocks. Used for building the reference maps for a
026 * method.
027 */
028final class BuildBB {
029
030  // ---------------- Static Class Fields --------------------
031
032  /** Types of Instructions */
033  private enum InstructionType {
034    NONBRANCH, CONDITIONAL_BRANCH, BRANCH
035  };
036
037  //***************************************************************************//
038  //                                                                           //
039  //  Once the method determineTheBasicBlocks is complete, these 4 items       //
040  //  basicBlocks, byteToBlockMap, numJsrs and gcPointCount will be            //
041  //  appropriately filled in. They will be accessed by BuildReferenceMaps  //
042  //  BuildLiveRefMaps, so that the reference maps can be built.            //
043  //                                                                           //
044  //***************************************************************************//
045
046  /**
047   * basic blocks of the byte code
048   */
049  final BasicBlockFactory bbf;
050  BasicBlock[] basicBlocks;
051
052  /**
053   * identify which block a byte is part of
054   */
055  short[] byteToBlockMap;
056
057  /**
058   * Number of unique jsr targets processed
059   */
060  int numJsrs;
061
062  /**
063   * Number of GC points found
064   */
065  int gcPointCount;
066
067  // This variable is used in multiple methods of this class, make it accessible
068  int bytelength;
069
070  /**
071   * Analyzes the bytecodes and builds the basic blocks with their predecessors.
072   * The results will be used by BuildReferenceMaps
073   *
074   * @param method the method whose bytecodes will be analyzed
075   */
076  BuildBB(NormalMethod method) {
077    ExceptionHandlerMap exceptions;   // Used to get a hold of the try Start, End and Handler lists
078    int[] retList;    // List of basic block numbers that end with a "ret" instruction.
079    BytecodeStream bcodes;        // The bytecodes being analyzed.
080    BasicBlock currentBB;         // current basic block being processed
081    InstructionType lastInstrType;// type of the last instruction
082    int lastInstrStart;// byte index where last instruction started
083    boolean hasMagic = false; // are there magic operations in this method (VM.VerifyAssertions only)
084    //
085    //  Initialization
086    //
087    int nextRetList = 0;
088    numJsrs = 0;
089    gcPointCount = 1;  // All methods have the possible thread switch in prologue
090
091    bcodes = method.getBytecodes();
092    bytelength = bcodes.length();
093
094    byteToBlockMap = new short[bytelength];
095    basicBlocks = new BasicBlock[2];  // many methods only have one block (+1 for EXIT)
096
097    bbf = new BasicBlockFactory();
098
099    exceptions = method.getExceptionHandlerMap();
100
101    retList = null;
102
103    //
104    //  Set up the EXIT basic block
105    //
106    basicBlocks[BasicBlock.EXITBLOCK] = new BasicBlock(bytelength, bytelength, BasicBlock.EXITBLOCK);
107
108    //
109    // Get the first basic block
110    //
111    currentBB = bbf.newBlock(0);
112    addBasicBlock(currentBB);
113    currentBB.setState(BasicBlock.METHODENTRY);
114    lastInstrType = InstructionType.NONBRANCH;
115    lastInstrStart = 0;
116
117    if (exceptions != null) {
118      // Get blocks for any handlers, which tend to not be a clear block boundaries
119      //
120      setupHandlerBBs(exceptions);
121
122      // Set up blocks for start of try block, which tend not be to at clear
123      // block boundaries
124      //
125      setupTryStartBBs(exceptions);
126    }
127
128    //
129    // Scan the bytecodes for this method
130    //
131    while (bcodes.hasMoreBytecodes()) {
132      // Determine if we are at a block boundary
133      // We are at a block boundary if:
134      //   1) non-branch instruction followed by a known block
135      //   2) last instruction was a conditional branch
136      //   3) last instruction was a branch
137      // Note that forward branches mean that the byteToBlockMap will have
138      // a basic block value prior to us examining that destination byte code
139      //
140      if (lastInstrType == InstructionType.NONBRANCH) {
141        if (byteToBlockMap[bcodes.index()] == BasicBlock.NOTBLOCK) {
142          // Not a new block
143          // Make note of current block
144          byteToBlockMap[bcodes.index()] = (short) currentBB.getBlockNumber();
145        } else {
146          // Earlier forward branch must have started this block
147          currentBB.setEnd(lastInstrStart);
148          basicBlocks[byteToBlockMap[bcodes.index()]].addPredecessor(currentBB);
149          currentBB = basicBlocks[byteToBlockMap[bcodes.index()]];
150        }
151      } else { // we are at a block boundary, last instr was some type of branch
152        if (lastInstrType == InstructionType.CONDITIONAL_BRANCH) {
153          currentBB.setEnd(lastInstrStart);
154          // See if we need a new block
155          if (byteToBlockMap[bcodes.index()] == BasicBlock.NOTBLOCK) {
156            BasicBlock newBB = bbf.newBlock(bcodes.index());
157            addBasicBlock(newBB);
158            newBB.addPredecessor(currentBB);
159            currentBB = newBB;
160            // Make note of current block
161            byteToBlockMap[bcodes.index()] = (short) currentBB.getBlockNumber();
162          } else {
163            // From an earlier forward branch
164            basicBlocks[byteToBlockMap[bcodes.index()]].addPredecessor(currentBB);
165            currentBB = basicBlocks[byteToBlockMap[bcodes.index()]];
166          }
167        } else {
168          if (lastInstrType == InstructionType.BRANCH) {
169            currentBB.setEnd(lastInstrStart);
170            // See if we need a new block
171            if (byteToBlockMap[bcodes.index()] == BasicBlock.NOTBLOCK) {
172              BasicBlock newBB = bbf.newBlock(bcodes.index());
173              addBasicBlock(newBB);
174              currentBB = newBB;
175              // Make note of current block
176              byteToBlockMap[bcodes.index()] = (short) currentBB.getBlockNumber();
177            } else {
178              // From an earlier forward branch
179              currentBB = basicBlocks[byteToBlockMap[bcodes.index()]];
180            }
181          }
182        }
183      }
184      // end of determining if at block boundary
185
186      // Now examine this instruction
187      lastInstrStart = bcodes.index();  // Instruction starts here
188      lastInstrType = InstructionType.NONBRANCH; // assume it will be a non-branch
189      switch (bcodes.nextInstruction()) {
190        case JBC_ifeq:
191        case JBC_ifne:
192        case JBC_iflt:
193        case JBC_ifge:
194        case JBC_ifgt:
195        case JBC_ifle:
196        case JBC_if_icmpeq:
197        case JBC_if_icmpne:
198        case JBC_if_icmplt:
199        case JBC_if_icmpge:
200        case JBC_if_icmpgt:
201        case JBC_if_icmple:
202        case JBC_if_acmpeq:
203        case JBC_if_acmpne:
204        case JBC_ifnull:
205        case JBC_ifnonnull: {
206          lastInstrType = InstructionType.CONDITIONAL_BRANCH;
207          int offset = bcodes.getBranchOffset();
208          if (offset <= 0) gcPointCount++; // gc map required if backward edge
209          int branchtarget = lastInstrStart + offset;
210          processBranchTarget(lastInstrStart, branchtarget);
211          break;
212        }
213
214        case JBC_jsr: {
215          lastInstrType = InstructionType.BRANCH;
216          int offset = bcodes.getBranchOffset();
217          int branchtarget = lastInstrStart + offset;
218          processBranchTarget(lastInstrStart, branchtarget);
219          int jsrentryBBNum = byteToBlockMap[branchtarget];
220          BasicBlock bb = basicBlocks[jsrentryBBNum];
221          if ((bb.getState() & BasicBlock.JSRENTRY) == 0) numJsrs++;
222          bb.setState(BasicBlock.JSRENTRY);
223          gcPointCount = gcPointCount + 1;
224          break;
225        }
226
227        case JBC_jsr_w: {
228          lastInstrType = InstructionType.BRANCH;
229          int offset = bcodes.getWideBranchOffset();
230          int branchtarget = lastInstrStart + offset;
231          processBranchTarget(lastInstrStart, branchtarget);
232          int jsrentryBBNum = byteToBlockMap[branchtarget];
233          BasicBlock bb = basicBlocks[jsrentryBBNum];
234          if ((bb.getState() & BasicBlock.JSRENTRY) == 0) numJsrs++;
235          bb.setState(BasicBlock.JSRENTRY);
236          gcPointCount = gcPointCount + 1;
237          break;
238        }
239
240        case JBC_goto: {
241          lastInstrType = InstructionType.BRANCH;
242          int offset = bcodes.getBranchOffset();
243          if (offset <= 0) gcPointCount++; // gc map required if backward edge
244          int branchtarget = lastInstrStart + offset;
245          processBranchTarget(lastInstrStart, branchtarget);
246          break;
247        }
248
249        case JBC_goto_w: {
250          lastInstrType = InstructionType.BRANCH;
251          int offset = bcodes.getWideBranchOffset();
252          if (offset <= 0) gcPointCount++; // gc map required if backward edge
253          int branchtarget = lastInstrStart + offset;
254          processBranchTarget(lastInstrStart, branchtarget);
255          break;
256        }
257
258        case JBC_tableswitch: {
259          lastInstrType = InstructionType.BRANCH;
260          bcodes.alignSwitch();
261          int def = bcodes.getDefaultSwitchOffset();
262          processBranchTarget(lastInstrStart, lastInstrStart + def);
263          int low = bcodes.getLowSwitchValue();
264          int high = bcodes.getHighSwitchValue();
265          int n = high - low + 1;                        // n = number of normal cases (0..n-1)
266
267          // generate labels for offsets
268          for (int i = 0; i < n; i++) {
269            int offset = bcodes.getTableSwitchOffset(i);
270            processBranchTarget(lastInstrStart, lastInstrStart + offset);
271          }
272          bcodes.skipTableSwitchOffsets(n);
273          break;
274        }
275
276        case JBC_lookupswitch: {
277          lastInstrType = InstructionType.BRANCH;
278          bcodes.alignSwitch();
279          int def = bcodes.getDefaultSwitchOffset();
280          int npairs = bcodes.getSwitchLength();
281          processBranchTarget(lastInstrStart, lastInstrStart + def);
282
283          // generate label for each offset in table
284          for (int i = 0; i < npairs; i++) {
285            int offset = bcodes.getLookupSwitchOffset(i);
286            processBranchTarget(lastInstrStart, lastInstrStart + offset);
287          }
288          bcodes.skipLookupSwitchPairs(npairs);
289          break;
290        }
291
292        case JBC_ireturn:
293        case JBC_lreturn:
294        case JBC_freturn:
295        case JBC_dreturn:
296        case JBC_areturn:
297        case JBC_return: {
298          lastInstrType = InstructionType.BRANCH;
299          basicBlocks[BasicBlock.EXITBLOCK].addPredecessor(currentBB);
300          if (method.isSynchronized() || VM.UseEpilogueYieldPoints) {
301            gcPointCount++;
302          }
303          break;
304        }
305
306        case JBC_ret: {
307          lastInstrType = InstructionType.BRANCH;
308          bcodes.getLocalNumber(); // index
309          int blocknum = currentBB.getBlockNumber();
310          basicBlocks[blocknum].setState(BasicBlock.JSREXIT);
311
312          // Worry about growing retListarray
313          if (retList == null) retList = new int[10];
314          if (nextRetList >= retList.length) {
315            int[] biggerRetList = new int[nextRetList + 10];
316            for (int i = 0; i < nextRetList; i++) {
317              biggerRetList[i] = retList[i];
318            }
319            retList = biggerRetList;
320            biggerRetList = null;
321          }
322          retList[nextRetList++] = blocknum;
323          break;
324        }
325
326        case JBC_wide: {
327          int widecode = bcodes.getWideOpcode();
328          bcodes.getWideLocalNumber(); // index
329          if (widecode == JBC_ret) {
330            lastInstrType = InstructionType.BRANCH;
331            int blocknum = currentBB.getBlockNumber();
332            basicBlocks[blocknum].setState(BasicBlock.JSREXIT);
333
334            // Worry about growing retListarray
335            if (retList == null) retList = new int[10];
336            if (nextRetList >= retList.length) {
337              int[] biggerRetList = new int[nextRetList + 10];
338              for (int i = 0; i < nextRetList; i++) {
339                biggerRetList[i] = retList[i];
340              }
341              retList = biggerRetList;
342              biggerRetList = null;
343            }
344            retList[nextRetList++] = blocknum;
345          } else if (widecode == JBC_iinc) {
346            bcodes.getWideIncrement();
347          } else {
348            // nothing more to do
349          }
350          break;
351        }
352
353        case JBC_athrow: {
354          lastInstrType = InstructionType.BRANCH;
355          processAthrow(exceptions, lastInstrStart);
356          gcPointCount++;
357          break;
358        }
359
360        case JBC_invokestatic:
361        case JBC_invokevirtual: {
362          if (VM.VerifyAssertions && !hasMagic) {
363            MethodReference methodRef = bcodes.getMethodReference();
364            hasMagic = methodRef.getType().isMagicType();
365            byteToBlockMap[lastInstrStart] = (short) currentBB.getBlockNumber();
366            gcPointCount = gcPointCount + 1;
367            break;
368          }
369        }
370
371        case JBC_aaload:
372        case JBC_iaload:
373        case JBC_faload:
374        case JBC_baload:
375        case JBC_caload:
376        case JBC_saload:
377        case JBC_laload:
378        case JBC_daload:
379        case JBC_lastore:
380        case JBC_dastore:
381        case JBC_iastore:
382        case JBC_fastore:
383        case JBC_aastore:
384        case JBC_bastore:
385        case JBC_castore:
386        case JBC_sastore:
387        case JBC_putfield:
388        case JBC_getfield:
389        case JBC_getstatic:
390        case JBC_putstatic:
391        case JBC_irem:
392        case JBC_idiv:
393        case JBC_lrem:
394        case JBC_ldiv:
395        case JBC_invokespecial:
396        case JBC_invokeinterface:
397        case JBC_instanceof:
398        case JBC_checkcast:
399        case JBC_monitorenter:
400        case JBC_monitorexit:
401        case JBC_new:
402        case JBC_newarray:
403        case JBC_anewarray:
404        case JBC_multianewarray: {
405          bcodes.skipInstruction();
406          byteToBlockMap[lastInstrStart] = (short) currentBB.getBlockNumber();
407          gcPointCount = gcPointCount + 1;
408          break;
409        }
410
411        default: {
412          bcodes.skipInstruction();
413          byteToBlockMap[lastInstrStart] = (short) currentBB.getBlockNumber();
414          break;
415        }
416      } // switch (opcode)
417    } // while (bcodes.hasMoreBytecodes)
418
419    currentBB.setEnd(lastInstrStart);   // close off last block
420
421    // process try and catch blocks
422    if (exceptions != null) {
423      // process catch blocks
424      processExceptionHandlers(exceptions);
425      // mark all blocks in try sections as being part of a try
426      markTryBlocks(exceptions);
427    }
428
429    // process ret instructions as last step
430    if (retList != null) {
431      processRetList(retList, nextRetList);
432    }
433
434    // can not support jsrs with unboxed types at the moment
435    if (VM.VerifyAssertions && !VM.BuildForHarmony) VM._assert(VM.runningVM || numJsrs == 0 || !hasMagic);
436  }
437
438  /********************************/
439  /*                              */
440  /*   Routines for Branches      */
441  /*                              */
442  /********************************/
443
444  /**
445   * Processing a branch that appears at location index in the byte code and has a
446   * target index of branchtarget in the byte code. The target of a branch must
447   * start a basic block. So if the byteToBlockMap doesn't already show a basic
448   * block at the target, make one start there. If a basic block is already set
449   * up and this is a branch forward then only need to adjust predecessor list
450   * (we know it is not a branch into the middle of a block as only starts are
451   * marked in byte code beyond "index"). If the basic block is already set up and
452   * this is a backward branch then we must check if the block needs splitting,
453   * branching to the middle of a block is not allowed.
454   *
455   * @param index the byte index of the branch instruction
456   * @param branchtarget the target byte index
457   */
458  private void processBranchTarget(int index, int branchtarget) {
459
460    BasicBlock newBB, currentBB;
461    if (byteToBlockMap[branchtarget] == BasicBlock.NOTBLOCK) {
462      newBB = bbf.newBlock(branchtarget);
463      addBasicBlock(newBB);
464      byteToBlockMap[branchtarget] = (short) newBB.getBlockNumber();
465      currentBB = basicBlocks[byteToBlockMap[index]];
466      newBB.addPredecessor(currentBB);
467    } else if (index > branchtarget) {
468      // This is a backwards branch
469      processBackwardBranch(index, branchtarget);
470    } else {
471      // This is a forward branch to an existing block, need to register
472      // the predecessor
473      currentBB = basicBlocks[byteToBlockMap[index]];
474      basicBlocks[byteToBlockMap[branchtarget]].addPredecessor(currentBB);
475    }
476  }
477
478  /**
479   * A backwards branch has been found from the byte code at location "index"
480   * to a target location of "branchtarget". Need to make sure that the
481   * branchtarget location is the start of a block (and if not, then split the
482   * existing block into two) Need to register the block that ends at "index"
483   * as a predecessor of the block that starts at branchtarget.
484   *
485   * @param index the byte index of the branch instruction
486   * @param branchtarget the target byte index
487   */
488  private void processBackwardBranch(int index, int branchtarget) {
489    BasicBlock existingBB, currentBB, newBB;
490    int newBlockNum, i, newBlockEnd;
491
492    existingBB = basicBlocks[byteToBlockMap[branchtarget]];
493    if (existingBB.getStart() != branchtarget) {
494      // Need to split the existing block in two, by ending the existing block
495      // at the previous instruction and starting a new block at the branchtarget.
496      // Need to split the existing block in two. It is best to set up the new
497      // block to end at the instruction before the target and the existing
498      // block to start at the target. That way the tail stays the same.
499
500      newBB = bbf.newBlock(existingBB.getStart());
501      addBasicBlock(newBB);
502      newBlockNum = newBB.getBlockNumber();
503      existingBB.setStart(branchtarget);
504
505      // Find the last instruction prior to the branch target;
506      //  that's the end of the new block
507      //
508      for (i = branchtarget - 1; byteToBlockMap[i] == BasicBlock.NOTBLOCK; i--) {
509        // count as described in the comment above the loop header
510      }
511
512      newBlockEnd = i;
513      newBB.setEnd(i);
514
515      // Going forwards, mark the start of each instruction with the new block
516      // number
517      //
518      for (i = newBB.getStart(); i <= newBlockEnd; i++) {
519        if (byteToBlockMap[i] != BasicBlock.NOTBLOCK) {
520          byteToBlockMap[i] = (short) newBlockNum;
521        }
522      }
523
524      BasicBlock.transferPredecessors(existingBB, newBB);
525
526      // The new block is a predecessor of the existing block
527      existingBB.addPredecessor(newBB);
528    } else {
529      // Nice coincidence, the existing block starts at "branchtarget"
530    }
531
532    // Now mark the "current" block (the one that ends at "index") as a predecessor
533    // of the target block (which is either the existing block or a newly made
534    // block)
535    //
536    currentBB = basicBlocks[byteToBlockMap[index]];
537    existingBB.addPredecessor(currentBB);
538  }
539
540  /********************************/
541  /*                              */
542  /*   Routines for JSR/Ret       */
543  /*                              */
544  /********************************/
545
546  /**
547   * process the effect of the ret instructions on the precedance table
548   *
549   * @param retList a list of basic blocks with return instructions. Each block
550   *  is represented by its basic block number.
551   * @param nextRetList maximum index in the list
552   */
553  private void processRetList(int[] retList, int nextRetList) {
554    // block 0 not used
555    int otherRetCount;
556    for (int i = 0; i < nextRetList; i++) {
557      int retBlockNum = retList[i];
558      BasicBlock retBB = basicBlocks[retBlockNum];
559      boolean[] seenAlready = new boolean[bbf.getNumberofBlocks() + 1];
560      otherRetCount = 0;
561      findAndSetJSRCallSite(retBlockNum, retBB, otherRetCount, seenAlready);
562    }
563  }
564
565  /**
566   * Scans back from ret instruction to jsr call sites.
567   *
568   * @param pred the basic block number of the predecessor block
569   * @param retBB the basic block that contains the return
570   * @param otherRetCount the number of other returns (i.e. non-matching)
571   *  returns that were found on the path
572   * @param seenAlready list of blocks that have already been seen
573   */
574  private void findAndSetJSRCallSite(int pred, BasicBlock retBB, int otherRetCount, boolean[] seenAlready) {
575    seenAlready[pred] = true;
576    BasicBlock jsrBB = basicBlocks[pred];
577    jsrBB.setState(BasicBlock.INJSR);
578
579    if (basicBlocks[pred].isJSRExit() && pred != retBB.getBlockNumber()) {
580      otherRetCount++;
581    }
582
583    if (basicBlocks[pred].isJSREntry()) {
584      if (otherRetCount == 0) {
585        // setup call site
586        setupJSRCallSite(basicBlocks[pred], retBB);
587        return;
588      } else {
589        otherRetCount--;
590      }
591    }
592    int[] predecessors = basicBlocks[pred].getPredecessors();
593    for (int predecessor : predecessors) {
594      if (!seenAlready[predecessor]) {
595        findAndSetJSRCallSite(predecessor, retBB, otherRetCount, seenAlready);
596      }
597    }
598  }
599
600  /**
601   * Does the setup for a jsr call site.
602   *
603   * @param entryBB a basic block with a jsr entry
604   * @param retBB a basic block with a matching return
605   */
606  private void setupJSRCallSite(BasicBlock entryBB, BasicBlock retBB) {
607    int newBB;
608    int[] callsites = entryBB.getPredecessors();
609    int callLength = callsites.length;
610    for (int i = 0; i < callLength; i++) {
611      int callsite = callsites[i];
612      int blockend = basicBlocks[callsite].getEnd();
613      for (newBB = blockend + 1; byteToBlockMap[newBB] == BasicBlock.NOTBLOCK; newBB++) ;
614      int nextBlock = byteToBlockMap[newBB];
615      basicBlocks[nextBlock].addPredecessor(retBB);
616    }
617  }
618
619  /********************************/
620  /*                              */
621  /*   Routines for Try/catch     */
622  /*                              */
623  /********************************/
624
625  /**
626   * For every handler, make a block that starts with the handler PC
627   * Only called when exceptions is not null.
628   *
629   * @param exceptions exception handler information
630   */
631  private void setupHandlerBBs(ExceptionHandlerMap exceptions) {
632    int[] tryHandlerPC = exceptions.getHandlerPC();
633    int tryLength = tryHandlerPC.length;
634    for (int i = 0; i < tryLength; i++) {
635      if (byteToBlockMap[tryHandlerPC[i]] == BasicBlock.NOTBLOCK) {
636        BasicBlock handlerBB = bbf.newBlock(tryHandlerPC[i]);
637        handlerBB.setState(BasicBlock.TRYHANDLERSTART);
638        addBasicBlock(handlerBB);
639        byteToBlockMap[tryHandlerPC[i]] = (short) handlerBB.getBlockNumber();
640      }
641    }
642  }
643
644  /**
645   * For every try start, make a block that starts with the Try start,
646   * mark it as a try start. Only called when exceptions is not null.
647   *
648   * @param exceptions exception handler information
649   */
650  private void setupTryStartBBs(ExceptionHandlerMap exceptions) {
651    int[] tryStartPC = exceptions.getStartPC();
652    int tryLength = tryStartPC.length;
653    for (int i = 0; i < tryLength; i++) {
654      if (byteToBlockMap[tryStartPC[i]] == BasicBlock.NOTBLOCK) {
655        BasicBlock tryStartBB = bbf.newBlock(tryStartPC[i]);
656        addBasicBlock(tryStartBB);
657        byteToBlockMap[tryStartPC[i]] = (short) tryStartBB.getBlockNumber();
658        tryStartBB.setState(BasicBlock.TRYSTART);
659      }
660    }
661  }
662
663  /**
664   * For every handler, mark the blocks in its try block as its predecessors.
665   * Only called when exceptions is not null.
666   *
667   * @param exceptions exception handler information
668   */
669  private void processExceptionHandlers(ExceptionHandlerMap exceptions) {
670    int[] tryStartPC = exceptions.getStartPC();
671    int[] tryEndPC = exceptions.getEndPC();
672    int[] tryHandlerPC = exceptions.getHandlerPC();
673    int tryLength = tryHandlerPC.length;
674    for (int i = 0; i < tryLength; i++) {
675      int handlerBBNum = byteToBlockMap[tryHandlerPC[i]];
676      BasicBlock tryHandlerBB = basicBlocks[handlerBBNum];
677      int throwBBNum = 0;
678      for (int k = tryStartPC[i]; k < tryEndPC[i]; k++) {
679        if (byteToBlockMap[k] == BasicBlock.NOTBLOCK) continue;
680
681        if (byteToBlockMap[k] != throwBBNum) {
682          throwBBNum = byteToBlockMap[k];
683          BasicBlock throwBB = basicBlocks[throwBBNum];
684          tryHandlerBB.addUniquePredecessor(throwBB);
685        }
686      }
687    }
688  }
689
690  /**
691   * Mark all the blocks within try range as being Try blocks
692   * used for determining the stack maps for Handler blocks
693   * Only called when exceptions is not null.
694   *
695   * @param exceptions exception handler information
696   */
697  private void markTryBlocks(ExceptionHandlerMap exceptions) {
698    int[] tryStartPC = exceptions.getStartPC();
699    int[] tryEndPC = exceptions.getEndPC();
700    int tryLength = tryStartPC.length;
701    int tryBlockNum = 0;
702    for (int i = 0; i < tryLength; i++) {
703      for (int j = tryStartPC[i]; j < tryEndPC[i]; j++) {
704        if (byteToBlockMap[j] != BasicBlock.NOTBLOCK) {
705          if (tryBlockNum != byteToBlockMap[j]) {
706            tryBlockNum = byteToBlockMap[j];
707            basicBlocks[tryBlockNum].setState(BasicBlock.TRYBLOCK);
708          }
709        }
710      }
711    }
712  }
713
714  /**
715   * Check if an athrow is within a try block, if it is, then handlers have this
716   * block as their predecessor; which is registered in "processExceptionHandlers"
717   * Otherwise, the athrow acts as a branch to the exit and that should be marked
718   * here. Note exceptions may be null.
719   *
720   * @param exceptions exception handler information
721   * @param athrowIndex byte index of the athrow
722   */
723  private void processAthrow(ExceptionHandlerMap exceptions, int athrowIndex) {
724    if (exceptions != null) {
725      int[] tryStartPC = exceptions.getStartPC();
726      int[] tryEndPC = exceptions.getEndPC();
727      int tryLength = tryStartPC.length;
728      // Check if this athrow index is within any of the try blocks
729      for (int i = 0; i < tryLength; i++) {
730        if (tryStartPC[i] <= athrowIndex && athrowIndex < tryEndPC[i]) {
731          return; // found it
732        }
733      }
734    }
735
736    BasicBlock athrowBB = basicBlocks[byteToBlockMap[athrowIndex]];
737    basicBlocks[BasicBlock.EXITBLOCK].addPredecessor(athrowBB);
738  }
739
740  /********************************/
741  /*                              */
742  /*   Misc routines              */
743  /*                              */
744  /********************************/
745
746  /**
747   * Adds a basic block.
748   *
749   * @param newBB the block to add
750   */
751  private void addBasicBlock(BasicBlock newBB) {
752    // Check whether basicBlock array must be grown.
753    //
754    int blocknum = newBB.getBlockNumber();
755    if (blocknum >= basicBlocks.length) {
756      int currentSize = basicBlocks.length;
757      int newSize = 15;
758      if (currentSize != 2) {
759        if (currentSize == 15) {
760          newSize = bytelength >> 4; // assume 16 bytecodes per basic block
761        } else {
762          newSize = currentSize + currentSize >> 3;  // increase by 12.5%
763        }
764        if (newSize <= blocknum) {
765          newSize = blocknum + 20;
766        }
767      }
768      BasicBlock[] biggerBlocks = new BasicBlock[newSize];
769      for (int i = 0; i < currentSize; i++) {
770        biggerBlocks[i] = basicBlocks[i];
771      }
772      basicBlocks = biggerBlocks;
773    }
774
775    // Go ahead and add block
776    basicBlocks[blocknum] = newBB;
777  }
778}