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.opt.ir;
014
015import static org.jikesrvm.compilers.opt.driver.OptConstants.NO;
016import static org.jikesrvm.compilers.opt.driver.OptConstants.UNKNOWN_BCI;
017import static org.jikesrvm.compilers.opt.ir.Operators.ATHROW_opcode;
018import static org.jikesrvm.compilers.opt.ir.Operators.BBEND;
019import static org.jikesrvm.compilers.opt.ir.Operators.BOUNDS_CHECK_opcode;
020import static org.jikesrvm.compilers.opt.ir.Operators.CHECKCAST_NOTNULL_opcode;
021import static org.jikesrvm.compilers.opt.ir.Operators.CHECKCAST_UNRESOLVED_opcode;
022import static org.jikesrvm.compilers.opt.ir.Operators.CHECKCAST_opcode;
023import static org.jikesrvm.compilers.opt.ir.Operators.GOTO;
024import static org.jikesrvm.compilers.opt.ir.Operators.INT_ZERO_CHECK_opcode;
025import static org.jikesrvm.compilers.opt.ir.Operators.IR_PROLOGUE_opcode;
026import static org.jikesrvm.compilers.opt.ir.Operators.LABEL;
027import static org.jikesrvm.compilers.opt.ir.Operators.LONG_ZERO_CHECK_opcode;
028import static org.jikesrvm.compilers.opt.ir.Operators.NULL_CHECK_opcode;
029import static org.jikesrvm.compilers.opt.ir.Operators.OBJARRAY_STORE_CHECK_opcode;
030
031import java.util.Enumeration;
032import java.util.HashSet;
033
034import org.jikesrvm.VM;
035import org.jikesrvm.classloader.TypeReference;
036import org.jikesrvm.compilers.opt.inlining.InlineSequence;
037import org.jikesrvm.compilers.opt.ir.operand.BasicBlockOperand;
038import org.jikesrvm.compilers.opt.ir.operand.BranchOperand;
039import org.jikesrvm.compilers.opt.ir.operand.MethodOperand;
040import org.jikesrvm.compilers.opt.util.SortedGraphNode;
041import org.jikesrvm.compilers.opt.util.SpaceEffGraphEdge;
042import org.jikesrvm.compilers.opt.util.SpaceEffGraphNode;
043import org.jikesrvm.runtime.Entrypoints;
044import org.jikesrvm.util.EmptyEnumeration;
045import org.vmmagic.pragma.NoInline;
046
047/**
048 * A basic block in the
049 * {@link ControlFlowGraph Factored Control Flow Graph (FCFG)}.
050 * <p>
051 * Just like in a standard control flow graph (CFG), a FCFG basic block
052 * contains a linear sequence of instructions. However, in the FCFG,
053 * a Potentially Excepting Instruction (PEI) does not necessarily end its
054 * basic block.  Therefore, although instructions within a FCFG basic block
055 * have the expected dominance relationships, they do <em>not</em> have the
056 * same post-dominance relationships as they would under the traditional
057 * basic block formulation used in a CFG.
058 * We chose to use an FCFG because doing so significantly reduces the
059 * number of basic blocks and control flow graph edges, thus reducing
060 * the time and space costs of representing the FCFG and also
061 * increasing the effectiveness of local (within a single basic block)
062 * analysis.  However, using an FCFG does complicate flow-sensitive
063 * global analaysis.  Many analyses can be easily extended to
064 * work on the FCFG.  For those analyses that cannot, we provide utilities
065 * ({@link IR#unfactor()}, {@link #unfactor(IR)})
066 * to effectively convert the FCFG into a CFG.
067 * For a more detailed description of the FCFG and its implications for
068 * program analysis see the PASTE'99 paper by Choi et al.
069 *   <a href="http://www.research.ibm.com/jalapeno/publication.html#paste99">
070 *   Efficient and Precise Modeling of Exceptions for the Analysis of Java Programs </a>
071 * <p>
072 * The instructions in a basic block have the following structure
073 * <ul>
074 * <li> The block begins with a <code>LABEL</code>.
075 * <li> Next come zero or more non-branch instructions.
076 * <li> Next come zero or more conditional branches
077 * <li> Next comes zero or one unconditional branch
078 * <li> Finally the block ends with a <code>BBEND</code>
079 * </ul>
080 * <code>CALL</code> instructions do not end their basic block.
081 * <code>ATHROW</code> instructions do end their basic block.
082 * Conventionally, we refer to the <em>real</em> instructions of
083 * the block as those that are between the LABEL and the BBEND.
084 * We say that the block is empty if it contains no real instructions.
085 *
086 * @see IR
087 * @see Instruction
088 * @see ControlFlowGraph
089 */
090
091public class BasicBlock extends SortedGraphNode {
092
093  /** Bitfield used in flag encoding */
094  static final short CAN_THROW_EXCEPTIONS = 0x01;
095  /** Bitfield used in flag encoding */
096  static final short IMPLICIT_EXIT_EDGE = 0x02;
097  /** Bitfield used in flag encoding */
098  static final short EXCEPTION_HANDLER = 0x04;
099  /** Bitfield used in flag encoding */
100  static final short REACHABLE_FROM_EXCEPTION_HANDLER = 0x08;
101
102  // the flag for 0x10 was removed and is now free
103
104  /** Bitfield used in flag encoding */
105  static final short INFREQUENT = 0x20;
106  /** Bitfield used in flag encoding */
107  static final short SCRATCH = 0x40;
108  /** Bitfield used in flag encoding */
109  static final short LANDING_PAD = 0x80;
110  /** Bitfield used in flag encoding */
111  static final short EXCEPTION_HANDLER_WITH_NORMAL_IN = 0x100;
112
113  /**
114   * Used to encode various properties of the block.
115   */
116  protected short flags;
117
118  /**
119   * Encodes exception handler info for this block.
120   * May be shared if multiple blocks have exactly the same chain
121   * of exception handlers.
122   */
123  public ExceptionHandlerBasicBlockBag exceptionHandlers;
124
125  /**
126   * First instruction of the basic block (LABEL).
127   */
128  final Instruction start;
129
130  /**
131   * Last instruction of the basic block (BBEND).
132   */
133  final Instruction end;
134
135  /**
136   * Relative execution frequency of this basic block.
137   * The entry block to a CFG has weight 1.0;
138   */
139  protected float freq;
140
141  /**
142   * Creates a new basic block at the specified location.
143   * It initially contains a single label instruction pointed to
144   * by start and a BBEND instruction pointed to by end.
145   *
146   * @param i         bytecode index to create basic block at
147   * @param position  the inline context for this basic block
148   * @param cfg       the FCFG that will contain the basic block
149   */
150  public BasicBlock(int i, InlineSequence position, ControlFlowGraph cfg) {
151    this(i, position, cfg.allocateNodeNumber());
152  }
153
154  /**
155   * Creates a new basic block at the specified location with
156   * the given basic block number.
157   * It initially contains a single label instruction pointed to
158   * by start and a BBEND instruction pointed to by end.
159   * WARNING: Don't call this constructor directly if the created basic
160   * block is going to be in some control flow graph, since it
161   * may not get assigned a unique number.
162   *
163   * @param i         bytecode index to create basic block at
164   * @param position  the inline context for this basic block
165   * @param num       the number to assign the basic block
166   */
167  protected BasicBlock(int i, InlineSequence position, int num) {
168    setNumber(num);
169    start = Label.create(LABEL, new BasicBlockOperand(this));
170    start.bcIndex = i;
171
172    start.position = position;
173    end = BBend.create(BBEND, new BasicBlockOperand(this));
174    // NOTE: we have no idea where this block will end so it
175    // makes no sense to set its bcIndex or position.
176    // In fact, the block may end in a different method entirely,
177    // so setting its position to the same as start may silently
178    // get us into all kinds of trouble. --dave.
179    end.bcIndex = UNKNOWN_BCI;
180    start.linkWithNext(end);
181    initInOutSets();
182  }
183
184  /**
185   * This constructor is only used for creating an EXIT node
186   */
187  private BasicBlock() {
188    start = end = null;
189    setNumber(1);
190  }
191
192  final void initInOutSets() {
193      }
194
195  static BasicBlock makeExit() {
196    return new BasicBlock();
197  }
198
199  /**
200   * Returns the string representation of this basic block.
201   * @return a String that is the name of the block.
202   */
203  @Override
204  public String toString() {
205    int number = getNumber();
206    if (isExit()) return "EXIT" + number;
207    if (number == 0) return "BB0 (ENTRY)";
208    return "BB" + number;
209  }
210
211  /**
212   * Print a detailed dump of the block to the sysWrite stream
213   */
214  @Override
215  public final void printExtended() {
216    VM.sysWrite("Basic block " + toString() + "\n");
217
218    // print in set.
219    BasicBlock bb2;
220    Enumeration<BasicBlock> e2 = getIn();
221    VM.sysWrite("\tin: ");
222    if (!e2.hasMoreElements()) {
223      VM.sysWrite("<none>\n");
224    } else {
225      bb2 = e2.nextElement();
226      VM.sysWrite(bb2.toString());
227      while (e2.hasMoreElements()) {
228        bb2 = e2.nextElement();
229        VM.sysWrite(", " + bb2.toString());
230      }
231      VM.sysWrite("\n");
232    }
233
234    // print out set.
235    e2 = getNormalOut();
236    VM.sysWrite("\tnormal out: ");
237    if (!e2.hasMoreElements()) {
238      VM.sysWrite("<none>\n");
239    } else {
240      bb2 = e2.nextElement();
241      VM.sysWrite(bb2.toString());
242      while (e2.hasMoreElements()) {
243        bb2 = e2.nextElement();
244        VM.sysWrite(", " + bb2.toString());
245      }
246      VM.sysWrite("\n");
247    }
248
249    e2 = getExceptionalOut();
250    VM.sysWrite("\texceptional out: ");
251    if (!e2.hasMoreElements()) {
252      VM.sysWrite("<none>\n");
253    } else {
254      bb2 = e2.nextElement();
255      VM.sysWrite(bb2.toString());
256      while (e2.hasMoreElements()) {
257        bb2 = e2.nextElement();
258        VM.sysWrite(", " + bb2.toString());
259      }
260      VM.sysWrite("\n");
261    }
262
263    if (mayThrowUncaughtException()) {
264      VM.sysWrite("\tMay throw uncaught exceptions, implicit edge to EXIT\n");
265    }
266
267    if (hasExceptionHandlers()) {
268      VM.sysWrite("\tIn scope exception handlers: ");
269      e2 = getExceptionHandlers();
270      if (e2.hasMoreElements()) {
271        bb2 = e2.nextElement();
272        VM.sysWrite(bb2.toString());
273        while (e2.hasMoreElements()) {
274          bb2 = e2.nextElement();
275          VM.sysWrite(", " + bb2.toString());
276        }
277      } else {
278        VM.sysWrite("<none>");
279      }
280      VM.sysWrite("\n");
281    }
282
283    if (getNext() != null) {
284      VM.sysWrite("\tNext in code order: " + getNext().toString() + "\n");
285    }
286
287    if (start != null) {
288      VM.sysWrite("\tInstructions:\n");
289      Instruction inst = start;
290      while (inst != end) {
291        VM.sysWrite(inst.bcIndex + ":\t" + inst + "\n");
292        inst = inst.getNext();
293      }
294      VM.sysWrite(inst.bcIndex + ":\t" + inst + "\n");
295    }
296    VM.sysWrite("\n");
297  }
298
299  /**
300   * Can this block possibly throw an exception?
301   * May conservatively return true even if the block
302   * does not contain a PEI.
303   *
304   * @return <code>true</code> if the block might raise an
305   *         exception or <code>false</code> if it cannot
306   */
307  public final boolean canThrowExceptions() {
308    return (flags & CAN_THROW_EXCEPTIONS) != 0;
309  }
310
311  /**
312   * Can a PEI in this block possibly raise an uncaught exception?
313   * May conservatively return true even if the block
314   * does not contain a PEI. When this is true it implies
315   * that there is an implicit edge from this node to the
316   * exit node in the FCFG.
317   * <p>
318   * NOTE: This method says nothing about the presence/absence
319   * of an explicit throw of an uncaught exception, and thus does
320   * not rule out the block having an <em>explicit</em>
321   * edge to the exit node caused by a throw of an uncaught exception.
322   *
323   * @return <code>true</code> if the block might raise an
324   *         exception uncaught or <code>false</code> if it cannot
325   */
326  public final boolean mayThrowUncaughtException() {
327    return (flags & IMPLICIT_EXIT_EDGE) != 0;
328  }
329
330  /**
331   * Is this block the first basic block in an exception handler?
332   * NOTE: This doesn't seem particularly useful to me anymore,
333   * since it is the same as asking if the block is an instanceof
334   * and ExceptionHandlerBasicBlock. Perhaps we should phase this out?
335   *
336   * @return <code>true</code> if the block is the first block in
337   *         an exception hander or <code>false</code> if it is not
338   */
339  public final boolean isExceptionHandlerBasicBlock() {
340    return (flags & EXCEPTION_HANDLER) != 0;
341  }
342
343  /**
344   * Has the block been marked as being reachable from an
345   * exception handler?
346   *
347   * @return <code>true</code> if the block is reachable from
348   *         an exception hander or <code>false</code> if it is not
349   */
350  public final boolean isReachableFromExceptionHandler() {
351    return (flags & REACHABLE_FROM_EXCEPTION_HANDLER) != 0;
352  }
353
354  /**
355   * Compare the in scope exception handlers of two blocks.
356   *
357   * @param other block to be compared to this.
358   * @return <code>true</code> if this and other have equivalent in
359   * scope exception handlers.
360   */
361  public final boolean isExceptionHandlerEquivalent(BasicBlock other) {
362    // We might be able to do something,
363    // by considering the (subset) of reachable exception handlers,
364    // but it would be awfully tricky to get it right,
365    // so just give up if they aren't equivalent.
366    if (exceptionHandlers != other.exceptionHandlers) {
367      // Even if not pointer ==, they still may be equivalent
368      Enumeration<BasicBlock> e1 = getExceptionHandlers();
369      Enumeration<BasicBlock> e2 = other.getExceptionHandlers();
370      while (e1.hasMoreElements()) {
371        if (!e2.hasMoreElements()) return false;
372        if (e1.nextElement() != e2.nextElement()) return false;
373      }
374      if (e2.hasMoreElements()) return false;
375    }
376    return true;
377  }
378
379  /**
380   * Has the block been marked as being infrequently executed?
381   * NOTE: Only blocks that are truly icy cold should be marked
382   * as infrequent.
383   *
384   * @return <code>true</code> if the block is marked as infrequently
385   *         executed or <code>false</code> if it is not
386   */
387  public final boolean getInfrequent() {
388    return (flags & INFREQUENT) != 0;
389  }
390
391  /**
392   * Is the scratch flag set on the block?
393   *
394   * @return <code>true</code> if the block scratch flag is set
395   *         or <code>false</code> if it is not
396   */
397  public final boolean getScratchFlag() {
398    return (flags & SCRATCH) != 0;
399  }
400
401  /**
402   * Has the block been marked as landing pad?
403   *
404   * @return <code>true</code> if the block is marked as landing pad
405   *         or <code>false</code> if it is not
406   */
407  public final boolean getLandingPad() {
408    return (flags & LANDING_PAD) != 0;
409  }
410
411  /**
412   * Mark the block as possibly raising an exception.
413   */
414  public final void setCanThrowExceptions() {
415    flags |= CAN_THROW_EXCEPTIONS;
416  }
417
418  /**
419   * Mark the block as possibly raising an uncaught exception.
420   */
421  public final void setMayThrowUncaughtException() {
422    flags |= IMPLICIT_EXIT_EDGE;
423  }
424
425  /**
426   * Mark the block as the first block in an exception handler.
427   */
428  public final void setExceptionHandlerBasicBlock() {
429    flags |= EXCEPTION_HANDLER;
430  }
431
432  /**
433   * Mark the block as being reachable from an exception handler.
434   */
435  public final void setReachableFromExceptionHandler() {
436    flags |= REACHABLE_FROM_EXCEPTION_HANDLER;
437  }
438
439  /**
440   * Mark the block as being infrequently executed.
441   */
442  public final void setInfrequent() {
443    flags |= INFREQUENT;
444  }
445
446  /**
447   * Set the scratch flag
448   */
449  public final void setScratchFlag() {
450    flags |= SCRATCH;
451  }
452
453  /**
454   * Mark the block as a landing pad for loop invariant code motion.
455   */
456  public final void setLandingPad() {
457    flags |= LANDING_PAD;
458  }
459
460  /**
461   * Clear the may raise an exception property of the block
462   */
463  public final void clearCanThrowExceptions() {
464    flags &= ~CAN_THROW_EXCEPTIONS;
465  }
466
467  /**
468   * Clear the may raise uncaught exception property of the block
469   */
470  public final void clearMayThrowUncaughtException() {
471    flags &= ~IMPLICIT_EXIT_EDGE;
472  }
473
474  /**
475   * Clear the block is the first one in an exception handler
476   * property of the block.
477   */
478  public final void clearExceptionHandlerBasicBlock() {
479    flags &= ~EXCEPTION_HANDLER;
480  }
481
482  /**
483   * Clear the block is reachable from an exception handler
484   * property of the block.
485   */
486  public final void clearReachableFromExceptionHandler() {
487    flags &= ~REACHABLE_FROM_EXCEPTION_HANDLER;
488  }
489
490  /**
491   * Clear the infrequently executed property of the block
492   */
493  public final void clearInfrequent() {
494    flags &= ~INFREQUENT;
495  }
496
497  /**
498   * Clear the scratch flag.
499   */
500  public final void clearScratchFlag() {
501    flags &= ~SCRATCH;
502  }
503
504  /**
505   * Clear the landing pad property of the block
506   */
507  public final void clearLandingPad() {
508    flags &= ~LANDING_PAD;
509  }
510
511  private void setCanThrowExceptions(boolean v) {
512    if (v) {
513      setCanThrowExceptions();
514    } else {
515      clearCanThrowExceptions();
516    }
517  }
518
519  private void setMayThrowUncaughtException(boolean v) {
520    if (v) {
521      setMayThrowUncaughtException();
522    } else {
523      clearMayThrowUncaughtException();
524    }
525  }
526
527  final void setInfrequent(boolean v) {
528    if (v) {
529      setInfrequent();
530    } else {
531      clearInfrequent();
532    }
533  }
534
535  public final void setExceptionHandlerWithNormalIn() {
536    flags |= EXCEPTION_HANDLER_WITH_NORMAL_IN;
537  }
538
539  public final boolean isExceptionHandlerWithNormalIn() {
540    return (flags & EXCEPTION_HANDLER_WITH_NORMAL_IN) != 0;
541  }
542
543  /**
544   * Make a branch operand with the label instruction
545   * of this block.
546   *
547   * @return an BranchOperand holding this blocks label
548   */
549  public final BranchOperand makeJumpTarget() {
550    return new BranchOperand(firstInstruction());
551  }
552
553  /**
554   * Make a GOTO instruction, branching to the first instruction of
555   * this basic block.
556   *
557   * @return a GOTO instruction that jumps to this block
558   */
559  public final Instruction makeGOTO() {
560    return Goto.create(GOTO, makeJumpTarget());
561  }
562
563  /**
564   * @return the first instruciton of the basic block (the label)
565   */
566  public final Instruction firstInstruction() {
567    return start;
568  }
569
570  /**
571   * @return the first 'real' instruction of the basic block;
572   *         null if the block is empty
573   */
574  public final Instruction firstRealInstruction() {
575    if (isEmpty()) {
576      return null;
577    } else {
578      return start.getNext();
579    }
580  }
581
582  /**
583   * @return the last instruction of the basic block (the BBEND)
584   */
585  public final Instruction lastInstruction() {
586    return end;
587  }
588
589  /**
590   * @return the last 'real' instruction of the basic block;
591   *         null if the block is empty
592   */
593  public final Instruction lastRealInstruction() {
594    if (isEmpty()) {
595      return null;
596    } else {
597      return end.getPrev();
598    }
599  }
600
601  /**
602   * @return the estimated relative execution frequency of the block
603   */
604  public final float getExecutionFrequency() {
605    return freq;
606  }
607
608  public final void setExecutionFrequency(float f) {
609    freq = f;
610  }
611
612  /**
613   * Scales the estimated relative execution frequency of this block.
614   *
615   * @param f scale factor
616   */
617  public final void scaleExecutionFrequency(float f) {
618    freq *= f;
619  }
620
621  /**
622   * Augments the estimated relative execution frequency of this block.
623   *
624   * @param f value to add
625   */
626  public final void augmentExecutionFrequency(float f) {
627    freq += f;
628  }
629
630  /**
631   * Is this block the exit basic block?
632   *
633   * @return <code>true</code> if this block is the EXIT or
634   *         <code>false</code> if it is not
635   */
636  public final boolean isExit() {
637    return start == null;
638  }
639
640  /**
641   * Forward enumeration of all the instruction in the block.
642   * @return a forward enumeration of the block's instructons.
643   */
644  public final Enumeration<Instruction> forwardInstrEnumerator() {
645    return IREnumeration.forwardIntraBlockIE(firstInstruction(), lastInstruction());
646  }
647
648  /**
649   * Reverse enumeration of all the instruction in the block.
650   * @return a reverse enumeration of the block's instructons.
651   */
652  public final Enumeration<Instruction> reverseInstrEnumerator() {
653    return IREnumeration.reverseIntraBlockIE(lastInstruction(), firstInstruction());
654  }
655
656  /**
657   * Forward enumeration of all the real instruction in the block.
658   * @return a forward enumeration of the block's real instructons.
659   */
660  public final Enumeration<Instruction> forwardRealInstrEnumerator() {
661    return IREnumeration.forwardIntraBlockIE(firstRealInstruction(), lastRealInstruction());
662  }
663
664  /**
665   * Reverse enumeration of all the real instruction in the block.
666   * @return a reverse enumeration of the block's real instructons.
667   */
668  public final Enumeration<Instruction> reverseRealInstrEnumerator() {
669    return IREnumeration.reverseIntraBlockIE(lastRealInstruction(), firstRealInstruction());
670  }
671
672  /**
673   * How many real instructions does the block contain?
674   * WARNING: This method actually counts the instructions,
675   * thus it has a linear time complexity!
676   *
677   * @return the number of "real" instructions in this basic block.
678   */
679  public int getNumberOfRealInstructions() {
680    int count = 0;
681    for (Enumeration<Instruction> e = forwardRealInstrEnumerator(); e.hasMoreElements(); e.nextElement()) {
682      count++;
683    }
684
685    return count;
686  }
687
688  /**
689   * Does this basic block end in a GOTO instruction?
690   *
691   * @return <code>true</code> if the block ends in a GOTO
692   *         or <code>false</code> if it does not
693   */
694  public final boolean hasGoto() {
695    if (isEmpty()) return false;
696    if (Goto.conforms(lastRealInstruction())) return true;
697    if (VM.BuildForIA32) {
698      return org.jikesrvm.compilers.opt.ir.ia32.MIR_Branch.conforms(lastRealInstruction());
699    } else {
700      if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
701      return org.jikesrvm.compilers.opt.ir.ppc.MIR_Branch.conforms(lastRealInstruction());
702    }
703  }
704
705  /**
706   * Does this basic block end in a RETURN instruction?
707   *
708   * @return <code>true</code> if the block ends in a RETURN
709   *         or <code>false</code> if it does not
710   */
711  public final boolean hasReturn() {
712    if (isEmpty()) return false;
713    if (Return.conforms(lastRealInstruction())) return true;
714    if (VM.BuildForIA32) {
715      return org.jikesrvm.compilers.opt.ir.ia32.MIR_Return.conforms(lastRealInstruction());
716    } else {
717      if (VM.VerifyAssertions) VM._assert(VM.BuildForPowerPC);
718      return org.jikesrvm.compilers.opt.ir.ppc.MIR_Return.conforms(lastRealInstruction());
719    }
720  }
721
722  /**
723   * Does this basic block end in a SWITCH instruction?
724   *
725   * @return <code>true</code> if the block ends in a SWITCH
726   *         or <code>false</code> if it does not
727   */
728  public final boolean hasSwitch() {
729    if (isEmpty()) return false;
730    Instruction s = lastRealInstruction();
731    return TableSwitch.conforms(s) || LowTableSwitch.conforms(s) || LookupSwitch.conforms(s);
732  }
733
734  /**
735   * Does this basic block contain an explicit athrow instruction?
736   *
737   * @return <code>true</code> if the block ends in an explicit Athrow
738   *         instruction or <code>false</code> if it does not
739   */
740  public final boolean hasAthrowInst() {
741    if (isEmpty()) return false;
742    Instruction s = lastRealInstruction();
743
744    if (VM.BuildForIA32 && s.operator().isAdviseESP()) {
745      s = s.getPrev();
746    }
747
748    if (Athrow.conforms(s)) {
749      return true;
750    }
751    MethodOperand mop = null;
752    if (VM.BuildForIA32 &&
753        org.jikesrvm.compilers.opt.ir.ia32.MIR_Call.conforms(s)) {
754      mop = org.jikesrvm.compilers.opt.ir.ia32.MIR_Call.getMethod(s);
755    } else if (VM.BuildForPowerPC &&
756        org.jikesrvm.compilers.opt.ir.ppc.MIR_Call.conforms(s)) {
757      mop = org.jikesrvm.compilers.opt.ir.ppc.MIR_Call.getMethod(s);
758    } else if (Call.conforms(s)) {
759      mop = Call.getMethod(s);
760    }
761    return mop != null && mop.getTarget() == Entrypoints.athrowMethod;
762  }
763
764  /**
765   * Does this basic block end in an explicit trap?
766   *
767   * @return <code>true</code> if the block ends in a an explicit trap
768   *         or <code>false</code> if it does not
769   */
770  public final boolean hasTrap() {
771    if (isEmpty()) return false;
772    Instruction s = lastRealInstruction();
773
774    return Trap.conforms(s);
775  }
776
777  /**
778   * Does this basic block end in a call that never returns?
779   * (For example, a call to athrow())
780   *
781   * @return <code>true</code> if the block ends in a call that never
782   *         returns or <code>false</code> if it does not
783   */
784  public final boolean hasNonReturningCall() {
785    if (isEmpty()) return false;
786    Instruction s = lastRealInstruction();
787
788    if (Call.conforms(s)) {
789      MethodOperand methodOp = Call.getMethod(s);
790      if (methodOp != null && methodOp.isNonReturningCall()) {
791        return true;
792      }
793    }
794
795    return false;
796  }
797
798  public final boolean hasNonReturningOsr() {
799    if (isEmpty()) return false;
800    Instruction s = lastRealInstruction();
801    return OsrPoint.conforms(s);
802  }
803
804  /**
805   * If there is a fallthrough FCFG successor of this node
806   * return it.
807   *
808   * @return the fall-through successor of this node or
809   *         <code>null</code> if none exists
810   */
811  public final BasicBlock getFallThroughBlock() {
812    if (hasGoto()) return null;
813    if (hasSwitch()) return null;
814    if (hasReturn()) return null;
815    if (hasAthrowInst()) return null;
816    if (hasTrap()) return null;
817    if (hasNonReturningCall()) return null;
818    if (hasNonReturningOsr()) return null;
819
820    return nextBasicBlockInCodeOrder();
821  }
822
823  /**
824   * @return the FCFG successor if all conditional branches in this are
825   * <em> not </em> taken
826   */
827  public final BasicBlock getNotTakenNextBlock() {
828    Instruction last = lastRealInstruction();
829    if (Goto.conforms(last)) {
830      return last.getBranchTarget();
831    } else if (VM.BuildForIA32 && org.jikesrvm.compilers.opt.ir.ia32.MIR_Branch.conforms(last)) {
832      return last.getBranchTarget();
833    } else if (VM.BuildForPowerPC && org.jikesrvm.compilers.opt.ir.ppc.MIR_Branch.conforms(last)) {
834      return last.getBranchTarget();
835    } else {
836      return nextBasicBlockInCodeOrder();
837    }
838  }
839
840  /**
841   * Replace fall through in this block by an explicit goto
842   */
843  public void killFallThrough() {
844    BasicBlock fallThrough = getFallThroughBlock();
845    if (fallThrough != null) {
846      lastInstruction().insertBefore(Goto.create(GOTO, fallThrough.makeJumpTarget()));
847    }
848  }
849
850  /**
851   * Prepend instruction to this basic block by inserting it right after
852   * the LABEL instruction in the instruction list.
853   *
854   * @param i instruction to append
855   */
856  public final void prependInstruction(Instruction i) {
857    start.insertAfter(i);
858  }
859
860  /**
861   * Prepend instruction to this basic block but respect the prologue
862   * instruction, which must come first.
863   *
864   * @param i instruction to append
865   */
866  public final void prependInstructionRespectingPrologue(Instruction i) {
867    Instruction first = firstRealInstruction();
868    if ((first != null) && (first.getOpcode() == IR_PROLOGUE_opcode)) {
869      first.insertAfter(i);
870    } else {
871      start.insertAfter(i);
872    }
873  }
874
875  /**
876   * Append instruction to this basic block by inserting it right before
877   * the BBEND instruction in the instruction list.
878   *
879   * @param i instruction to append
880   */
881  public final void appendInstruction(Instruction i) {
882    end.insertBefore(i);
883  }
884
885  /**
886   * Append instruction to this basic block by inserting it right before
887   * the BBEND instruction in the instruction list. However, if
888   * the basic block ends in a sequence of branch instructions, insert
889   * the instruction before the first branch instruction.
890   *
891   * @param i instruction to append
892   */
893  public final void appendInstructionRespectingTerminalBranch(Instruction i) {
894    Instruction s = end;
895    while (s.getPrev().operator().isBranch()) s = s.getPrev();
896    s.insertBefore(i);
897  }
898
899  /**
900   * Append instruction to this basic block by inserting it right before
901   * the BBEND instruction in the instruction list. However, if
902   * the basic block ends in a sequence of branch instructions, insert
903   * the instruction before the first branch instruction. If the block
904   * ends in a PEI, insert the instruction before the PEI.
905   * This function is meant to be used when the block has
906   * been {@link #unfactor(IR) unfactored} and thus is in CFG form.
907   *
908   * @param i instruction to append
909   */
910  public final void appendInstructionRespectingTerminalBranchOrPEI(Instruction i) {
911    Instruction s = end;
912    while (s.getPrev().operator().isBranch() ||
913           s.getPrev().operator().isThrow() ||
914           (s.getPrev().isPEI() && getApplicableExceptionalOut(s.getPrev()).hasMoreElements())) {
915      s = s.getPrev();
916    }
917    s.insertBefore(i);
918  }
919
920  /**
921   * Return an enumeration of the branch instructions in this
922   * basic block.
923   * @return an forward enumeration of this blocks branch instruction
924   */
925  public final Enumeration<Instruction> enumerateBranchInstructions() {
926    Instruction start = firstBranchInstruction();
927    Instruction end = (start == null) ? null : lastRealInstruction();
928    return IREnumeration.forwardIntraBlockIE(start, end);
929  }
930
931  /**
932   * Return the first branch instruction in the block.
933   *
934   * @return the first branch instruction in the block
935   *         or <code>null</code> if there are none.
936   */
937  public final Instruction firstBranchInstruction() {
938    Instruction s = lastRealInstruction();
939    if (s == null) return null;
940    if (!s.operator().isBranch()) return null;
941    while (s.getPrev().isBranch()) {
942      s = s.getPrev();
943    }
944    return s;
945  }
946
947  /**
948   * Return the next basic block in with respect to the current
949   * code linearization order.
950   *
951   * @return the next basic block in the code order or
952   *         <code>null</code> if no such block exists
953   */
954  public final BasicBlock nextBasicBlockInCodeOrder() {
955    return (BasicBlock) getNext();
956  }
957
958  /**
959   * Return the previous basic block in with respect to the current
960   * code linearization order.
961   *
962   * @return the previous basic block in the code order or
963   *         <code>null</code> if no such block exists
964   */
965  public final BasicBlock prevBasicBlockInCodeOrder() {
966    return (BasicBlock) getPrev();
967  }
968
969  /**
970   * Returns true if the block contains no real instructions
971   *
972   * @return <code>true</code> if the block contains no real instructions
973   *         or <code>false</code> if it does.
974   */
975  public final boolean isEmpty() {
976    return start.getNext() == end;
977  }
978
979  /**
980   * Are there any exceptional out edges that are applicable
981   * to the given instruction (assumed to be in instruction in 'this')
982   *
983   * @param instr the instruction in question
984   * @return true or false;
985   */
986  public final boolean hasApplicableExceptionalOut(Instruction instr) {
987    return getApplicableExceptionalOut(instr).hasMoreElements();
988  }
989
990  /**
991   * An enumeration of the subset of exceptional out edges that are applicable
992   * to the given instruction (assumed to be in instruction in 'this')
993   *
994   * @param instr the instruction in question
995   * @return an enumeration of the exceptional out edges applicable to instr
996   */
997  public final Enumeration<BasicBlock> getApplicableExceptionalOut(Instruction instr) {
998    if (instr.isPEI()) {
999      int numPossible = getNumberOfExceptionalOut();
1000      if (numPossible == 0) return EmptyEnumeration.<BasicBlock>emptyEnumeration();
1001      ComputedBBEnum e = new ComputedBBEnum(numPossible);
1002      switch (instr.getOpcode()) {
1003        case ATHROW_opcode:
1004          TypeReference type = Athrow.getValue(instr).getType();
1005          addTargets(e, type);
1006          break;
1007        case CHECKCAST_opcode:
1008        case CHECKCAST_NOTNULL_opcode:
1009        case CHECKCAST_UNRESOLVED_opcode:
1010          addTargets(e, TypeReference.JavaLangClassCastException);
1011          break;
1012        case NULL_CHECK_opcode:
1013          addTargets(e, TypeReference.JavaLangNullPointerException);
1014          break;
1015        case BOUNDS_CHECK_opcode:
1016          addTargets(e, TypeReference.JavaLangArrayIndexOutOfBoundsException);
1017          break;
1018        case INT_ZERO_CHECK_opcode:
1019        case LONG_ZERO_CHECK_opcode:
1020          addTargets(e, TypeReference.JavaLangArithmeticException);
1021          break;
1022        case OBJARRAY_STORE_CHECK_opcode:
1023          addTargets(e, TypeReference.JavaLangArrayStoreException);
1024          break;
1025        default:
1026          // Not an operator for which we have a more refined notion of
1027          // its exception semantics, so assume that any reachable exception
1028          // handler might be a potential target of this PEI
1029          return getExceptionalOut();
1030      }
1031      return e;
1032    } else {
1033      return EmptyEnumeration.<BasicBlock>emptyEnumeration();
1034    }
1035  }
1036
1037  // add all handler blocks in this's out set that might possibly catch
1038  // an exception of static type throwException
1039  // (may dynamically be any subtype of thrownException)
1040  private void addTargets(ComputedBBEnum e, TypeReference thrownException) {
1041    for (SpaceEffGraphEdge ed = _outEdgeStart; ed != null; ed = ed.getNextOut()) {
1042      BasicBlock bb = (BasicBlock) ed.toNode();
1043      if (bb.isExceptionHandlerBasicBlock()) {
1044        ExceptionHandlerBasicBlock eblock = (ExceptionHandlerBasicBlock) bb;
1045        if (eblock.mayCatchException(thrownException) != NO) {
1046          e.addPossiblyDuplicateElement(eblock);
1047        }
1048      }
1049    }
1050  }
1051
1052  /**
1053   * An enumeration of the in scope exception handlers for this basic block.
1054   * Note that this may be a superset of the exception handlers
1055   * actually included in the out set of this basic block.
1056   *
1057   * @return an enumeration of all inscope exception handlers
1058   */
1059  public final Enumeration<BasicBlock> getExceptionHandlers() {
1060    if (exceptionHandlers == null) {
1061      return EmptyEnumeration.<BasicBlock>emptyEnumeration();
1062    } else {
1063      return exceptionHandlers.enumerator();
1064    }
1065  }
1066
1067  /**
1068   * Is this block in the scope of at least exception handler?
1069   *
1070   * @return <code>true</code> if there is at least one in scope
1071   *         exception handler, <code>false</code> otherwise
1072   */
1073  public final boolean hasExceptionHandlers() {
1074    return exceptionHandlers != null;
1075  }
1076
1077  /**
1078   * Returns an Enumeration of the in scope exception handlers that are
1079   * actually reachable from this basic block in the order that they are
1080   * applicable (which is semantically meaningful).
1081   * IE, this is those blocks in getExceptionalOut ordered as
1082   * in getExceptionHandlers.
1083   *
1084   * @return an enumeration of the reachable exception handlers
1085   */
1086  public final Enumeration<BasicBlock> getReachableExceptionHandlers() {
1087    if (hasExceptionHandlers()) {
1088      int count = 0;
1089      for (Enumeration<BasicBlock> inScope = getExceptionHandlers(); inScope.hasMoreElements(); inScope.nextElement()) {
1090        count++;
1091      }
1092
1093      ComputedBBEnum ans = new ComputedBBEnum(count);
1094
1095      for (Enumeration<BasicBlock> inScope = getExceptionHandlers(); inScope.hasMoreElements();) {
1096        BasicBlock cand = inScope.nextElement();
1097        if (pointsOut(cand)) ans.addPossiblyDuplicateElement(cand);
1098      }
1099      return ans;
1100    } else {
1101      return EmptyEnumeration.<BasicBlock>emptyEnumeration();
1102    }
1103  }
1104
1105  /**
1106   * Delete all the non-exceptional out edges.
1107   * A useful primitive routine for some CFG manipulations.
1108   */
1109  public final void deleteNormalOut() {
1110    for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.getNextOut()) {
1111      BasicBlock out = (BasicBlock) e.toNode();
1112      if (!out.isExceptionHandlerBasicBlock()) {
1113        deleteOut(e);
1114      }
1115    }
1116  }
1117
1118  /**
1119   * Recompute the normal out edges of 'this' based on the
1120   * semantics of the branch instructions in the block.<p>
1121   *
1122   * WARNING: Use this method with caution.  It does not update the
1123   * CFG edges correctly if the method contains certain instructions
1124   * such as throws and returns.  Incorrect liveness info and GC maps
1125   * result, causing crashes during GC.<p>
1126   *
1127   * TODO check if warning is still current and if there's info on
1128   *  CMVC Defect 171189 anywhere
1129   *
1130   * @param ir the containing IR
1131   */
1132  public final void recomputeNormalOut(IR ir) {
1133    deleteNormalOut();
1134    for (Enumeration<Instruction> e = enumerateBranchInstructions(); e.hasMoreElements();) {
1135      Instruction branch = e.nextElement();
1136      Enumeration<BasicBlock> targets = branch.getBranchTargets();
1137      while (targets.hasMoreElements()) {
1138        BasicBlock targetBlock = targets.nextElement();
1139        if (targetBlock.isExceptionHandlerBasicBlock()) {
1140          targetBlock.setExceptionHandlerWithNormalIn();
1141        }
1142        insertOut(targetBlock);
1143      }
1144    }
1145    // Check for fallthrough edge
1146    BasicBlock fallThrough = getFallThroughBlock();
1147    if (fallThrough != null) {
1148      if (fallThrough.isExceptionHandlerBasicBlock()) {
1149        fallThrough.setExceptionHandlerWithNormalIn();
1150      }
1151      insertOut(fallThrough);
1152    }
1153
1154    // Check special cases that require edge to exit
1155    if (hasReturn()) {
1156      insertOut(ir.cfg.exit());
1157    } else if (hasAthrowInst() || hasNonReturningCall()) {
1158      if (mayThrowUncaughtException()) {
1159        insertOut(ir.cfg.exit());
1160      }
1161    } else if (hasNonReturningOsr()) {
1162      insertOut(ir.cfg.exit());
1163    }
1164  }
1165
1166  /**
1167   * Ensure that the target instruction is the only real instruction
1168   * in its basic block and that it has exactly one successor and
1169   * one predecessor basic blocks that are linked to it by fall through edges.
1170   *
1171   * @param target the Instruction that must be placed in its own BB
1172   * @param ir the containing IR object
1173   * @return the BasicBlock containing target
1174   */
1175  public final BasicBlock segregateInstruction(Instruction target, IR ir) {
1176    if (IR.PARANOID) VM._assert(this == target.getBasicBlock());
1177
1178    BasicBlock BB1 = splitNodeAt(target.getPrev(), ir);
1179    this.insertOut(BB1);
1180    ir.cfg.linkInCodeOrder(this, BB1);
1181    BasicBlock BB2 = BB1.splitNodeAt(target, ir);
1182    BB1.insertOut(BB2);
1183    ir.cfg.linkInCodeOrder(BB1, BB2);
1184    return BB1;
1185  }
1186
1187  /**
1188   * Splits a node at an instruction point.  All the instructions up to and
1189   * including the argument instruction remain in the original basic block.
1190   * All instructions in this basic block but after s in the instruction list
1191   * are moved to the new basic block.
1192   * <ul>
1193   * <li> does not establish control flow edge out of B1 -- caller responsibility
1194   * <li> does not establish control flow edge into B2 -- caller responsibility
1195   * <li> Leaves a break in the code order -- caller responsibility
1196   *      to patch back together. If the original code order was
1197   *      BB_before -&gt; BB1 -&gt; BB_after
1198   *      then the new code order is
1199   *      BB_before -&gt; BB1 &lt;break&gt; BB2 -&gt; BB_after.
1200   *      Note that if BB_after == null, splitNodeAt does handle
1201   *      updating ir.cfg._lastNode to point to BB2.
1202   * </ul>
1203   *
1204   * @param last_instr_BB1 the instr that is to become the last instruction
1205   *                       in this basic block
1206   * @param ir             the containing IR object
1207   * @return the newly created basic block which is the successor to this
1208   */
1209  public final BasicBlock splitNodeAt(Instruction last_instr_BB1, IR ir) {
1210    if (IR.PARANOID) VM._assert(this == last_instr_BB1.getBasicBlock());
1211
1212    BasicBlock BB1 = this;
1213    BasicBlock BB2 = new BasicBlock(last_instr_BB1.bcIndex, last_instr_BB1.position, ir.cfg);
1214    BasicBlock BB3 = (BasicBlock) BB1.next;
1215
1216    // move last_instr_BB1 ... BB1.end.prev into BB2
1217    if (last_instr_BB1 == BB1.end || last_instr_BB1.getNext() == BB1.end) {
1218      // there are no such instructions; nothing to do
1219    } else {
1220      Instruction first_instr_BB2 = last_instr_BB1.getNext();
1221      Instruction last_instr_BB2 = BB1.end.getPrev();
1222      last_instr_BB1.linkWithNext(BB1.end);
1223      BB2.start.linkWithNext(first_instr_BB2);
1224      last_instr_BB2.linkWithNext(BB2.end);
1225    }
1226
1227    // Update code ordering (see header comment above)
1228    if (BB3 == null) {
1229      ir.cfg.addLastInCodeOrder(BB2);
1230      if (IR.PARANOID) VM._assert(BB1.next == BB2 && BB2.prev == BB1);
1231      ir.cfg.breakCodeOrder(BB1, BB2);
1232    } else {
1233      ir.cfg.breakCodeOrder(BB1, BB3);
1234      ir.cfg.linkInCodeOrder(BB2, BB3);
1235    }
1236
1237    // Update control flow graph to transfer BB1's out edges to BB2.
1238    // But it's not as simple as that.  Any edge that is present to represent
1239    // potential exception behavior (out.isExceptionHandlerBasicBlock == true)
1240    // needs to be both left in BB1's out set and transfered to BB2's out set
1241    // Note this may be overly conservative, but will be correct.
1242    for (Enumeration<BasicBlock> e = getOut(); e.hasMoreElements();) {
1243      BasicBlock out = e.nextElement();
1244      BB2.insertOut(out);
1245    }
1246
1247    // Initialize the rest of BB2's exception related state to match BB1
1248    BB2.exceptionHandlers = BB1.exceptionHandlers;
1249    BB2.setCanThrowExceptions(BB1.canThrowExceptions());
1250    BB2.setMayThrowUncaughtException(BB1.mayThrowUncaughtException());
1251    BB2.setExecutionFrequency(BB1.getExecutionFrequency());
1252
1253    BB1.deleteNormalOut();
1254
1255    return BB2;
1256  }
1257
1258  /**
1259   * Splits a node at an instruction point. All the instructions up to and
1260   * including the argument instruction remain in the original basic block
1261   * all instructions in this basic block but after s in the instruction list
1262   * are moved to the new basic block. The blocks are linked together in
1263   * the FCFG and the code order.
1264   * The key difference between this function and
1265   * {@link #splitNodeAt(Instruction,IR)} is that it does
1266   * establish the FCFG edges and code order such that B1 falls into B2.
1267   *
1268   * @param last_instr_BB1 the instr that is to become
1269   *                       the last instruction in this basic block
1270   * @param ir             the containing IR object
1271   * @return the newly created basic block which is the successor to this
1272   */
1273  public final BasicBlock splitNodeWithLinksAt(Instruction last_instr_BB1, IR ir) {
1274
1275    if (IR.PARANOID) VM._assert(this == last_instr_BB1.getBasicBlock());
1276
1277    BasicBlock BB2 = splitNodeAt(last_instr_BB1, ir);
1278    this.insertOut(BB2);
1279    ir.cfg.linkInCodeOrder(this, BB2);
1280    return BB2;
1281  }
1282
1283  /**
1284   * Copies a basic block. The copy differs from the original as follows:
1285   * <ul>
1286   * <li> the copy's number and labels are new, and will be unique in the
1287   *      containing IR
1288   * <li> the copy is NOT linked into the IR's bblist
1289   * <li> the copy does NOT appear in the IR's cfg.
1290   * </ul>
1291   * The copy
1292   * <ul>
1293   * <li> inherits the original block's exception handlers
1294   * <li> inherits the original block's bytecode index
1295   * <li> has NEW copies of each instruction.
1296   * </ul>
1297   *
1298   * @param ir the containing IR
1299   * @return the copy
1300   */
1301  public final BasicBlock copyWithoutLinks(IR ir) {
1302    // create a new block with the same bytecode index and exception handlers
1303    int bytecodeIndex = -1;
1304
1305    // Make the label instruction of the new block have the same
1306    // bc info as the label of the original block.
1307    if (firstInstruction() != null) {
1308      bytecodeIndex = firstInstruction().bcIndex;
1309    }
1310
1311    BasicBlock newBlock = createSubBlock(bytecodeIndex, ir, 1f);
1312
1313    // copy each instruction from the original block.
1314    for (Instruction s = firstInstruction().getNext(); s != lastInstruction(); s = s.getNext()) {
1315      newBlock.appendInstruction(s.copyWithoutLinks());
1316    }
1317
1318    // copy other properties of the block.
1319    newBlock.flags = flags;
1320
1321    return newBlock;
1322  }
1323
1324  /**
1325   * For each basic block b which is a "normal" successor of this,
1326   * make a copy of b, and set up the CFG so that this block has
1327   * normal out edges to the copies.<p>
1328   *
1329   * WARNING: Use this method with caution.  See comment on
1330   * BasicBlock.recomputeNormalOut()
1331   *
1332   * @param ir the containing IR
1333   */
1334  public final void replicateNormalOut(IR ir) {
1335    // for each normal out successor (b) of 'this' ....
1336    for (Enumeration<BasicBlock> e = getNormalOut(); e.hasMoreElements();) {
1337      BasicBlock b = e.nextElement();
1338      replicateThisOut(ir, b);
1339    }
1340  }
1341
1342  /**
1343   * For basic block b which has to be a "normal" successor of this,
1344   * make a copy of b, and set up the CFG so that this block has
1345   * normal out edges to the copy.<p>
1346   *
1347   * WARNING: Use this method with caution.  See comment on
1348   * BasicBlock.recomputeNormalOut()
1349   *
1350   * @param ir the governing IR
1351   * @param b the block to replicate
1352   * @return the replicated basic block
1353   */
1354  public final BasicBlock replicateThisOut(IR ir, BasicBlock b) {
1355    return replicateThisOut(ir, b, this);
1356  }
1357
1358  /**
1359   * For basic block b which has to be a "normal" successor of this,
1360   * make a copy of b, and set up the CFG so that this block has
1361   * normal out edges to the copy.<p>
1362   *
1363   * WARNING: Use this method with caution.  See comment on
1364   * BasicBlock.recomputeNormalOut()
1365   *
1366   * @param ir the governing IR
1367   * @param b the block to replicate
1368   * @param pred code order predecessor for new block
1369   * @return the replicated basic block
1370   */
1371  public final BasicBlock replicateThisOut(IR ir, BasicBlock b, BasicBlock pred) {
1372    // don't replicate the exit node
1373    if (b.isExit()) return null;
1374
1375    // 1. create the replicated block (bCopy)
1376    BasicBlock bCopy = b.copyWithoutLinks(ir);
1377
1378    // 2. If b has a fall-through edge, insert the appropriate GOTO at
1379    // the end of bCopy
1380    BasicBlock bFallThrough = b.getFallThroughBlock();
1381    if (bFallThrough != null) {
1382      Instruction g = Goto.create(GOTO, bFallThrough.makeJumpTarget());
1383      bCopy.appendInstruction(g);
1384    }
1385    bCopy.recomputeNormalOut(ir);
1386
1387    // 3. update the branch instructions in 'this' to point to bCopy
1388    redirectOuts(b, bCopy, ir);
1389
1390    // 4. link the new basic into the code order, immediately following pred
1391    pred.killFallThrough();
1392    BasicBlock next = pred.nextBasicBlockInCodeOrder();
1393    if (next != null) {
1394      ir.cfg.breakCodeOrder(pred, next);
1395      ir.cfg.linkInCodeOrder(bCopy, next);
1396    }
1397    ir.cfg.linkInCodeOrder(pred, bCopy);
1398
1399    return bCopy;
1400  }
1401
1402  /**
1403   * Move me behind `pred'.
1404   *
1405   * @param pred my desired code order predecessor
1406   * @param ir the governing IR
1407   */
1408  public void moveBehind(BasicBlock pred, IR ir) {
1409    killFallThrough();
1410    pred.killFallThrough();
1411    BasicBlock thisPred = prevBasicBlockInCodeOrder();
1412    BasicBlock thisSucc = nextBasicBlockInCodeOrder();
1413    if (thisPred != null) {
1414      thisPred.killFallThrough();
1415      ir.cfg.breakCodeOrder(thisPred, this);
1416    }
1417    if (thisSucc != null) ir.cfg.breakCodeOrder(this, thisSucc);
1418
1419    if (thisPred != null && thisSucc != null) {
1420      ir.cfg.linkInCodeOrder(thisPred, thisSucc);
1421    }
1422
1423    thisPred = pred;
1424    thisSucc = pred.nextBasicBlockInCodeOrder();
1425
1426    if (thisSucc != null) {
1427      ir.cfg.breakCodeOrder(thisPred, thisSucc);
1428      ir.cfg.linkInCodeOrder(this, thisSucc);
1429    }
1430    ir.cfg.linkInCodeOrder(thisPred, this);
1431  }
1432
1433  /**
1434   * Change all branches from this to b to branches that go to bCopy instead.
1435   * This method also handles this.fallThrough, so `this' should still be in
1436   * the code order when this method is called.<p>
1437   *
1438   * WARNING: Use this method with caution.  See comment on
1439   * BasicBlock.recomputeNormalOut()
1440   *
1441   * @param b     the original target
1442   * @param bCopy the future target
1443   * @param ir the IR that contains this basic block
1444   */
1445  public final void redirectOuts(BasicBlock b, BasicBlock bCopy, IR ir) {
1446    BranchOperand copyTarget = bCopy.makeJumpTarget();
1447    BranchOperand bTarget = b.makeJumpTarget();
1448    // 1. update the branch instructions in 'this' to point to bCopy
1449    for (Enumeration<Instruction> ie = enumerateBranchInstructions(); ie.hasMoreElements();) {
1450      Instruction s = ie.nextElement();
1451      s.replaceSimilarOperands(bTarget, copyTarget);
1452    }
1453
1454    // 2. if this falls through to b, make it jump to bCopy
1455    if (getFallThroughBlock() == b) {
1456      Instruction g = Goto.create(GOTO, copyTarget); //no copy needed.
1457      appendInstruction(g);
1458    }
1459
1460    // 3. recompute normal control flow edges.
1461    recomputeNormalOut(ir);
1462  }
1463
1464  /*
1465   * TODO: work on eliminating this method by converting callers to
1466   *       three argument form
1467   */
1468  public final BasicBlock createSubBlock(int bc, IR ir) {
1469    return createSubBlock(bc, ir, 1f);
1470  }
1471
1472  /**
1473   * Creates a new basic block that inherits its exception handling,
1474   * etc from 'this'. This method is intended to be used in conjunction
1475   * with splitNodeAt when splitting instructions in one original block
1476   * into a sequence of sublocks
1477   *
1478   * @param bc the bytecode index to start the block
1479   * @param ir the containing IR
1480   * @param wf the fraction of this's execution frequency that should be
1481   *           inherited by the new block. In the range [0.0, 1.0]
1482   * @return the new empty BBlock
1483   */
1484  public final BasicBlock createSubBlock(int bc, IR ir, float wf) {
1485    // For now, give the basic block the same inline context as the
1486    // original block.
1487    // TODO: This won't always work. (In fact, in the presence of inlining
1488    //       it will be wrong quite often). --dave
1489    //       We really have to pass the position in if we except this to work.
1490    BasicBlock temp = new BasicBlock(bc, firstInstruction().position, ir.cfg);
1491
1492    // Conservatively transfer all exception handling behavior of the
1493    // parent block  (this) to the new child block (temp)
1494    temp.exceptionHandlers = exceptionHandlers;
1495    temp.setCanThrowExceptions(canThrowExceptions());
1496    temp.setMayThrowUncaughtException(mayThrowUncaughtException());
1497    temp.setExecutionFrequency(getExecutionFrequency() * wf);
1498    for (Enumeration<BasicBlock> e = getOut(); e.hasMoreElements();) {
1499      BasicBlock out = e.nextElement();
1500      if (out.isExceptionHandlerBasicBlock()) {
1501        temp.insertOut(out);
1502      }
1503    }
1504
1505    return temp;
1506  }
1507
1508  /**
1509   * If this block has a single non-Exception successor in the CFG
1510   * then we may be able to merge the two blocks together.
1511   * In order for this to be legal, it must be the case that:
1512   * <ol>
1513   *  <li>The successor block has no other in edges than the one from this.
1514   *  <li>Both blocks have the same exception handlers.
1515   * </ol>
1516   * Merging the blocks is always desirable when
1517   * <ol>
1518   *  <li>the successor block is the next block in code order
1519   *  <li>the successor block is not the next block in the code order,
1520   *      but ends in an unconditional branch (ie it doesn't have a
1521   *      fallthrough successor in the code order that we could be screwing up).
1522   * </ol>
1523   *
1524   * @param ir the IR object containing the basic block to be merged
1525   * @return <code>true</code> if  the block was merged or
1526   *         <code>false</code> otherwise
1527   */
1528  public final boolean mergeFallThrough(IR ir) {
1529    if (getNumberOfNormalOut() != 1) return false; // this has other out edges.
1530    BasicBlock succBB = (BasicBlock) next;
1531    if (succBB == null || !pointsOut(succBB)) {
1532      // get the successor from the CFG rather than the code order (case (b))
1533      succBB = getNormalOut().nextElement();
1534      if (succBB.isExit()) return false;
1535      if (succBB.lastRealInstruction() == null || !succBB.lastRealInstruction().isUnconditionalBranch()) {
1536        return false;
1537      }
1538    }
1539
1540    if (succBB.isExceptionHandlerBasicBlock()) return false; // must preserve special exception info!
1541    if (succBB.getNumberOfIn() != 1) return false; // succBB has other in edges
1542
1543    // Different in scope Exception handlers?
1544    if (!isExceptionHandlerEquivalent(succBB)) return false;
1545
1546    // There may be a redundant goto at the end of this -- remove it.
1547    // There may also be redundant conditional branches (also to succBB).
1548    // Remove them as well.
1549    // Branch instructions to blocks other than succBB are errors.
1550    if (VM.VerifyAssertions) {
1551      for (Enumeration<Instruction> e = enumerateBranchInstructions(); e.hasMoreElements();) {
1552        Enumeration<BasicBlock> targets = e.nextElement().getBranchTargets();
1553        while (targets.hasMoreElements()) {
1554          BasicBlock target = targets.nextElement();
1555          VM._assert(target == succBB);
1556        }
1557      }
1558    }
1559    Instruction s = this.end.getPrev();
1560    while (s.isBranch()) {
1561      s = s.remove();
1562    }
1563
1564    // splice together the instruction lists of the two basic blocks into
1565    // a single list and update this's BBEND info
1566    this.end.getPrev().linkWithNext(succBB.start.getNext());
1567    succBB.end.getPrev().linkWithNext(this.end);
1568
1569    // Add succBB's CFG sucessors to this's CFG out edges
1570    for (OutEdgeEnum e = succBB.getOut(); e.hasMoreElements();) {
1571      BasicBlock out = e.nextElement();
1572      this.insertOut(out);
1573    }
1574
1575    // Blow away sucBB.
1576    ir.cfg.removeFromCFGAndCodeOrder(succBB);
1577
1578    // Merge misc BB state
1579    setCanThrowExceptions(canThrowExceptions() || succBB.canThrowExceptions());
1580    setMayThrowUncaughtException(mayThrowUncaughtException() || succBB.mayThrowUncaughtException());
1581    if (succBB.getInfrequent()) setInfrequent();
1582
1583    return true;
1584  }
1585
1586  /**
1587   * Convert a block in the FCFG into the equivalent set of
1588   * CFG blocks by splitting the original block into sub-blocks
1589   * at each PEI that reaches at least one exception handelr.
1590   * NOTE: This is sufficient for intraprocedural analysis, since the
1591   * only program point at which the "wrong" answers will
1592   * be computed is the exit node, but is not good enough for
1593   * interprocedural analyses.  To do an interprocedural analysis,
1594   * either the analysis needs to deal with the FCFG or all nodes
1595   * that modify globally visible state must be unfactored.
1596   * @see IR#unfactor
1597   * @param ir the containing IR object
1598   */
1599  final void unfactor(IR ir) {
1600    for (Enumeration<Instruction> e = forwardRealInstrEnumerator(); e.hasMoreElements();) {
1601      Instruction s = e.nextElement();
1602      Enumeration<BasicBlock> expOuts = getApplicableExceptionalOut(s);
1603      if (expOuts.hasMoreElements() && e.hasMoreElements()) {
1604        BasicBlock next = splitNodeWithLinksAt(s, ir);
1605        next.unfactor(ir);
1606        pruneExceptionalOut(ir);
1607        return;
1608      }
1609    }
1610  }
1611
1612  /**
1613   * Prune away exceptional out edges that are not reachable given this
1614   * block's instructions.
1615   *
1616   * @param ir the IR that contains this block
1617   */
1618  final void pruneExceptionalOut(IR ir) {
1619    int n = getNumberOfExceptionalOut();
1620    if (n > 0) {
1621      ComputedBBEnum handlers = new ComputedBBEnum(n);
1622      Enumeration<Instruction> e = forwardRealInstrEnumerator();
1623      while (e.hasMoreElements()) {
1624        Instruction x = e.nextElement();
1625        Enumeration<BasicBlock> bbs = getApplicableExceptionalOut(x);
1626        while (bbs.hasMoreElements()) {
1627          BasicBlock bb = bbs.nextElement();
1628          handlers.addPossiblyDuplicateElement(bb);
1629        }
1630      }
1631
1632      deleteExceptionalOut();
1633
1634      for (int i = 0; handlers.hasMoreElements(); i++) {
1635        ExceptionHandlerBasicBlock b = (ExceptionHandlerBasicBlock) handlers.nextElement();
1636        insertOut(b);
1637      }
1638    }
1639
1640    // Since any edge to an exception handler is an "exceptional" edge,
1641    // the previous procedure has thrown away any "normal" CFG edges to
1642    // exception handlers.  So, recompute normal edges to recover them.
1643    recomputeNormalOut(ir);
1644
1645  }
1646
1647  // helper function for unfactor
1648  private void deleteExceptionalOut() {
1649    for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.getNextOut()) {
1650      BasicBlock out = (BasicBlock) e.toNode();
1651      if (out.isExceptionHandlerBasicBlock()) {
1652        deleteOut(e);
1653      }
1654    }
1655  }
1656
1657  /**
1658   * An enumeration of the FCFG in nodes.
1659   *
1660   * @return an enumeration of the in nodes
1661   */
1662  public final Enumeration<BasicBlock> getIn() {
1663    return new InEdgeEnum(this);
1664  }
1665
1666  /**
1667   * An enumeration of the FCFG in nodes.
1668   *
1669   * @return an enumeration of the in nodes
1670   */
1671  @Override
1672  public final Enumeration<BasicBlock> getInNodes() {
1673    return new InEdgeEnum(this);
1674  }
1675
1676  /**
1677   * Is there an in edge from the given basic block?
1678   *
1679   * @param bb basic block in question
1680   * @return <code>true</code> if an in edge exists from bb
1681   *         <code>false</code> otherwise
1682   */
1683  public final boolean isIn(BasicBlock bb) {
1684    InEdgeEnum iee = new InEdgeEnum(this);
1685    while (iee.hasMoreElements()) {
1686      if (iee.nextElement() == bb) {
1687        return true;
1688      }
1689    }
1690    return false;
1691  }
1692
1693  /**
1694   * An enumeration of the FCFG out nodes.
1695   *
1696   * @return an enumeration of the out nodes
1697   */
1698  public final OutEdgeEnum getOut() {
1699    return new OutEdgeEnum(this);
1700  }
1701
1702  /**
1703   * An enumeration of the FCFG out nodes.
1704   *
1705   * @return an enumeration of the out nodes
1706   */
1707  @Override
1708  public final OutEdgeEnum getOutNodes() {
1709    return new OutEdgeEnum(this);
1710  }
1711
1712  /**
1713   * Is there an out edge to the given basic block?
1714   *
1715   * @param bb basic block in question
1716   * @return <code>true</code> if an out edge exists to bb
1717   *         <code>false</code> otherwise
1718   */
1719  public final boolean isOut(BasicBlock bb) {
1720    OutEdgeEnum oee = new OutEdgeEnum(this);
1721    while (oee.hasMoreElements()) {
1722      if (oee.nextElement() == bb) {
1723        return true;
1724      }
1725    }
1726    return false;
1727  }
1728
1729  /**
1730   * An enumeration of the 'normal' (not reached via exceptional control flow)
1731   * out nodes of the block.
1732   *
1733   * @return an enumeration of the out nodes that are not
1734   *         reachable via as a result of exceptional control flow
1735   */
1736  public final Enumeration<BasicBlock> getNormalOut() {
1737    return new NormalOutEdgeEnum(this);
1738  }
1739
1740  /**
1741   * Is there a 'normal' out edge to the given basic block?
1742   *
1743   * @param bb basic block in question
1744   * @return <code>true</code> if a normal out edge exists to bb
1745   *         <code>false</code> otherwise
1746   */
1747  public final boolean isNormalOut(BasicBlock bb) {
1748    NormalOutEdgeEnum noee = new NormalOutEdgeEnum(this);
1749    while (noee.hasMoreElements()) {
1750      if (noee.nextElement() == bb) {
1751        return true;
1752      }
1753    }
1754    return false;
1755  }
1756
1757  /**
1758   * An enumeration of the 'exceptional' (reached via exceptional control flow)
1759   * out nodes of the block.
1760   *
1761   * @return an enumeration of the out nodes that are
1762   *         reachable via as a result of exceptional control flow
1763   */
1764  public final Enumeration<BasicBlock> getExceptionalOut() {
1765    if (canThrowExceptions()) {
1766      return new ExceptionOutEdgeEnum(this);
1767    } else {
1768      return EmptyEnumeration.<BasicBlock>emptyEnumeration();
1769    }
1770  }
1771
1772  /**
1773   * Is there an 'exceptional' out edge to the given basic block?
1774   *
1775   * @param bb basic block in question
1776   * @return <code>true</code> if an exceptional out edge exists to bb
1777   *         <code>false</code> otherwise
1778   */
1779  public final boolean isExceptionalOut(BasicBlock bb) {
1780    if (!canThrowExceptions()) return false;
1781    ExceptionOutEdgeEnum eoee = new ExceptionOutEdgeEnum(this);
1782    while (eoee.hasMoreElements()) {
1783      if (eoee.nextElement() == bb) {
1784        return true;
1785      }
1786    }
1787    return false;
1788  }
1789
1790  /**
1791   * Get the number of out nodes that are to "normal" basic blocks
1792   *
1793   * @return the number of out nodes that are not the start of
1794   *         exception handlers
1795   */
1796  public final int getNumberOfNormalOut() {
1797    int count = 0;
1798    boolean countValid = true;
1799    for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.getNextOut()) {
1800      BasicBlock bb = (BasicBlock) e.toNode();
1801      if (!bb.isExceptionHandlerBasicBlock()) {
1802        count++;
1803      } else if (bb.isExceptionHandlerWithNormalIn()) {
1804        countValid = false;
1805        break;
1806      }
1807    }
1808    if (countValid) {
1809      return count;
1810    } else {
1811      HashSet<BasicBlock> setOfTargets = new HashSet<BasicBlock>();
1812      for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.getNextOut()) {
1813        BasicBlock bb = (BasicBlock) e.toNode();
1814        if (!bb.isExceptionHandlerBasicBlock()) {
1815          setOfTargets.add(bb);
1816        }
1817      }
1818      for (Enumeration<Instruction> e = enumerateBranchInstructions(); e.hasMoreElements();) {
1819        Enumeration<BasicBlock> targets = e.nextElement().getBranchTargets();
1820        while (targets.hasMoreElements()) {
1821          setOfTargets.add(targets.nextElement());
1822        }
1823      }
1824      return setOfTargets.size();
1825    }
1826  }
1827
1828  /**
1829   * Get the number of out nodes that are to exception handler basic blocks
1830   *
1831   * @return the number of out nodes that are exception handlers
1832   */
1833  public final int getNumberOfExceptionalOut() {
1834    int count = 0;
1835    if (canThrowExceptions()) {
1836      for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.getNextOut()) {
1837        BasicBlock bb = (BasicBlock) e.toNode();
1838        if (bb.isExceptionHandlerBasicBlock()) {
1839          count++;
1840        }
1841      }
1842    }
1843    return count;
1844  }
1845
1846  /**
1847   * Are there exceptinal handlers that are reachable via
1848   * exceptional control flow from this basic block?
1849   *
1850   * @return <code>true</code> if an exceptional handler
1851   *          is reachable from this block or
1852   *          <code>false</code> otherwise.
1853   */
1854  public final boolean hasReachableExceptionHandlers() {
1855    if (canThrowExceptions()) {
1856      for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.getNextOut()) {
1857        BasicBlock bb = (BasicBlock) e.toNode();
1858        if (bb.isExceptionHandlerBasicBlock()) {
1859          return true;
1860        }
1861      }
1862    }
1863    return false;
1864  }
1865
1866  /*
1867  * Primitive BasicBlock enumerators.
1868  * We don't really intend clients to directly instantiate these, but rather to
1869  * call the appropriate utility function that creates/initializes one of these
1870  */
1871  abstract static class BBEnum implements Enumeration<BasicBlock> {
1872    protected BasicBlock current;
1873
1874    @Override
1875    public final boolean hasMoreElements() {
1876      return current != null;
1877    }
1878
1879    @Override
1880    public final BasicBlock nextElement() {
1881      if (current == null) fail();
1882      BasicBlock value = current;
1883      current = advance();
1884      return value;
1885    }
1886
1887    protected abstract BasicBlock advance();
1888
1889    @NoInline
1890    protected static void fail() throws java.util.NoSuchElementException {
1891      throw new java.util.NoSuchElementException("Basic Block Enumeration");
1892    }
1893  }
1894
1895  // Arbitrary constructed enumeration of some set of basic blocks
1896  static final class ComputedBBEnum implements Enumeration<BasicBlock> {
1897    private final BasicBlock[] blocks;
1898    private int numBlocks;
1899    private int current;
1900
1901    ComputedBBEnum(int maxBlocks) {
1902      blocks = new BasicBlock[maxBlocks];
1903    }
1904
1905    void addElement(BasicBlock b) {
1906      blocks[numBlocks++] = b;
1907    }
1908
1909    void addPossiblyDuplicateElement(BasicBlock b) {
1910      for (int i = 0; i < numBlocks; i++) {
1911        if (blocks[i] == b) return;
1912      }
1913      addElement(b);
1914    }
1915
1916    public int totalCount() {
1917      return numBlocks;
1918    }
1919
1920    @Override
1921    public boolean hasMoreElements() {
1922      return current < numBlocks;
1923    }
1924
1925    @Override
1926    public BasicBlock nextElement() {
1927      if (current >= numBlocks) fail();
1928      return blocks[current++];
1929    }
1930
1931    @NoInline
1932    static void fail() throws java.util.NoSuchElementException {
1933      throw new java.util.NoSuchElementException("Basic Block Enumeration");
1934    }
1935  }
1936
1937  // this class needs to be implemented efficiently, as it is used heavily.
1938  static final class InEdgeEnum implements Enumeration<BasicBlock> {
1939    private SpaceEffGraphEdge _edge;
1940
1941    InEdgeEnum(SpaceEffGraphNode n) {
1942      _edge = n.firstInEdge();
1943    }
1944
1945    @Override
1946    public boolean hasMoreElements() {
1947      return _edge != null;
1948    }
1949
1950    @Override
1951    public BasicBlock nextElement() {
1952      SpaceEffGraphEdge e = _edge;
1953      _edge = e.getNextIn();
1954      return (BasicBlock) e.fromNode();
1955    }
1956  }
1957
1958  // this class needs to be implemented efficiently, as it is used heavily.
1959  static final class OutEdgeEnum implements Enumeration<BasicBlock> {
1960    private SpaceEffGraphEdge _edge;
1961
1962    OutEdgeEnum(SpaceEffGraphNode n) {
1963      _edge = n.firstOutEdge();
1964    }
1965
1966    @Override
1967    public boolean hasMoreElements() {
1968      return _edge != null;
1969    }
1970
1971    @Override
1972    public BasicBlock nextElement() {
1973      SpaceEffGraphEdge e = _edge;
1974      _edge = e.getNextOut();
1975      return (BasicBlock) e.toNode();
1976    }
1977  }
1978
1979  // Enumerate the non-handler blocks in the edge set
1980  final class NormalOutEdgeEnum extends BBEnum {
1981    private SpaceEffGraphEdge _edge;
1982
1983    NormalOutEdgeEnum(SpaceEffGraphNode n) {
1984      _edge = n.firstOutEdge();
1985      current = advance();
1986    }
1987
1988    @Override
1989    protected BasicBlock advance() {
1990      while (_edge != null) {
1991        BasicBlock cand = (BasicBlock) _edge.toNode();
1992        _edge = _edge.getNextOut();
1993        if (!cand.isExceptionHandlerBasicBlock()) {
1994          return cand;
1995        } else if (cand.isExceptionHandlerWithNormalIn()) {
1996          for (Enumeration<Instruction> e = enumerateBranchInstructions(); e.hasMoreElements();) {
1997            Enumeration<BasicBlock> targets = e.nextElement().getBranchTargets();
1998            while (targets.hasMoreElements()) {
1999              if (cand == targets.nextElement()) {
2000                return cand;
2001              }
2002            }
2003          }
2004        }
2005      }
2006      return null;
2007    }
2008  }
2009
2010  // Enumerate the non-handler blocks in the edge set
2011  static final class ExceptionOutEdgeEnum extends BBEnum {
2012    private SpaceEffGraphEdge _edge;
2013
2014    ExceptionOutEdgeEnum(SpaceEffGraphNode n) {
2015      _edge = n.firstOutEdge();
2016      current = advance();
2017    }
2018
2019    @Override
2020    protected BasicBlock advance() {
2021      while (_edge != null) {
2022        BasicBlock cand = (BasicBlock) _edge.toNode();
2023        _edge = _edge.getNextOut();
2024        if (cand.isExceptionHandlerBasicBlock()) {
2025          return cand;
2026        }
2027      }
2028      return null;
2029    }
2030  }
2031
2032  public void discardInstructions() {
2033    start.getNext().setPrev(null);
2034    end.getPrev().setNext(null);
2035    start.linkWithNext(end);
2036  }
2037}