001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Common Public License (CPL);
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/cpl1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.jikesrvm.compilers.opt.ir;
014
015 import static org.jikesrvm.compilers.opt.driver.OptConstants.NO;
016 import static org.jikesrvm.compilers.opt.ir.Operators.ATHROW_opcode;
017 import static org.jikesrvm.compilers.opt.ir.Operators.BBEND;
018 import static org.jikesrvm.compilers.opt.ir.Operators.BOUNDS_CHECK_opcode;
019 import static org.jikesrvm.compilers.opt.ir.Operators.CHECKCAST_NOTNULL_opcode;
020 import static org.jikesrvm.compilers.opt.ir.Operators.CHECKCAST_UNRESOLVED_opcode;
021 import static org.jikesrvm.compilers.opt.ir.Operators.CHECKCAST_opcode;
022 import static org.jikesrvm.compilers.opt.ir.Operators.GOTO;
023 import static org.jikesrvm.compilers.opt.ir.Operators.INT_ZERO_CHECK_opcode;
024 import static org.jikesrvm.compilers.opt.ir.Operators.IR_PROLOGUE_opcode;
025 import static org.jikesrvm.compilers.opt.ir.Operators.LABEL;
026 import static org.jikesrvm.compilers.opt.ir.Operators.LONG_ZERO_CHECK_opcode;
027 import static org.jikesrvm.compilers.opt.ir.Operators.NULL_CHECK_opcode;
028 import static org.jikesrvm.compilers.opt.ir.Operators.OBJARRAY_STORE_CHECK_opcode;
029
030 import java.util.HashSet;
031
032 import org.jikesrvm.VM;
033 import org.jikesrvm.classloader.TypeReference;
034 import org.jikesrvm.compilers.opt.driver.OptConstants;
035 import org.jikesrvm.compilers.opt.inlining.InlineSequence;
036 import org.jikesrvm.compilers.opt.ir.operand.BasicBlockOperand;
037 import org.jikesrvm.compilers.opt.ir.operand.BranchOperand;
038 import org.jikesrvm.compilers.opt.ir.operand.MethodOperand;
039 import org.jikesrvm.compilers.opt.liveness.LiveIntervalEnumeration;
040 import org.jikesrvm.compilers.opt.regalloc.LiveIntervalElement;
041 import org.jikesrvm.compilers.opt.util.SortedGraphNode;
042 import org.jikesrvm.compilers.opt.util.SpaceEffGraphEdge;
043 import org.jikesrvm.compilers.opt.util.SpaceEffGraphNode;
044 import org.jikesrvm.runtime.Entrypoints;
045 import 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 * <p>
086 *
087 * @see IR
088 * @see Instruction
089 * @see ControlFlowGraph
090 */
091
092 public class BasicBlock extends SortedGraphNode {
093
094 /** Bitfield used in flag encoding */
095 static final short CAN_THROW_EXCEPTIONS = 0x01;
096 /** Bitfield used in flag encoding */
097 static final short IMPLICIT_EXIT_EDGE = 0x02;
098 /** Bitfield used in flag encoding */
099 static final short EXCEPTION_HANDLER = 0x04;
100 /** Bitfield used in flag encoding */
101 static final short REACHABLE_FROM_EXCEPTION_HANDLER = 0x08;
102 /** Bitfield used in flag encoding */
103 static final short UNSAFE_TO_SCHEDULE = 0x10;
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 = OptConstants.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 * Make an EXIT node.
196 */
197 static BasicBlock makeExit() {
198 return new BasicBlock();
199 }
200
201 /**
202 * Returns the string representation of this basic block.
203 * @return a String that is the name of the block.
204 */
205 public String toString() {
206 int number = getNumber();
207 if (isExit()) return "EXIT" + number;
208 if (number == 0) return "BB0 (ENTRY)";
209 return "BB" + number;
210 }
211
212 /**
213 * Print a detailed dump of the block to the sysWrite stream
214 */
215 public final void printExtended() {
216 VM.sysWrite("Basic block " + toString() + "\n");
217
218 // print in set.
219 BasicBlock bb2;
220 BasicBlockEnumeration e2 = getIn();
221 VM.sysWrite("\tin: ");
222 if (!e2.hasMoreElements()) {
223 VM.sysWrite("<none>\n");
224 } else {
225 bb2 = e2.next();
226 VM.sysWrite(bb2.toString());
227 while (e2.hasMoreElements()) {
228 bb2 = e2.next();
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.next();
241 VM.sysWrite(bb2.toString());
242 while (e2.hasMoreElements()) {
243 bb2 = e2.next();
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.next();
255 VM.sysWrite(bb2.toString());
256 while (e2.hasMoreElements()) {
257 bb2 = e2.next();
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.next();
272 VM.sysWrite(bb2.toString());
273 while (e2.hasMoreElements()) {
274 bb2 = e2.next();
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 * Clear the scratch object from previous uses
301 * (rename scratchObject manipulations for GCMaps/RegAlloc).
302 */
303 public final void initializeLiveRange() {
304 scratchObject = null;
305 }
306
307 /**
308 * @return an enumeration of the live interval elements for this basic
309 * block.
310 */
311 public final LiveIntervalEnumeration enumerateLiveIntervals() {
312 return new LiveIntervalEnumeration((LiveIntervalElement) scratchObject);
313 }
314
315 /**
316 * Returns NULL or an LiveIntervalElement (GCMaps/RegAlloc).
317 * @return scratchObject cast as an LiveIntevalElement
318 */
319 public final LiveIntervalElement getFirstLiveIntervalElement() {
320 if (scratchObject != null) {
321 return (LiveIntervalElement) scratchObject;
322 } else {
323 return null;
324 }
325 }
326
327 /**
328 * Prepend a live interval element to the list being maintained
329 * in scratchObject (GCMaps/RegAlloc).
330 *
331 * @param li the live interval element to add
332 */
333 public final void prependLiveIntervalElement(LiveIntervalElement li) {
334 li.setNext((LiveIntervalElement) scratchObject);
335 scratchObject = li;
336 }
337
338 /**
339 * Can this block possibly throw an exception?
340 * May conservatively return true even if the block
341 * does not contain a PEI.
342 *
343 * @return <code>true</code> if the block might raise an
344 * exception or <code>false</code> if it cannot
345 */
346 public final boolean canThrowExceptions() {
347 return (flags & CAN_THROW_EXCEPTIONS) != 0;
348 }
349
350 /**
351 * Can a PEI in this block possibly raise an uncaught exception?
352 * May conservatively return true even if the block
353 * does not contain a PEI. When this is true it implies
354 * that there is an implicit edge from this node to the
355 * exit node in the FCFG.
356 * <p>
357 * NOTE: This method says nothing about the presence/absence
358 * of an explicit throw of an uncaught exception, and thus does
359 * not rule out the block having an <em>explicit</em>
360 * edge to the exit node caused by a throw of an uncaught exception.
361 *
362 * @return <code>true</code> if the block might raise an
363 * exception uncaught or <code>false</code> if it cannot
364 */
365 public final boolean mayThrowUncaughtException() {
366 return (flags & IMPLICIT_EXIT_EDGE) != 0;
367 }
368
369 /**
370 * Is this block the first basic block in an exception handler?
371 * NOTE: This doesn't seem particularly useful to me anymore,
372 * since it is the same as asking if the block is an instanceof
373 * and ExceptionHandlerBasicBlock. Perhaps we should phase this out?
374 *
375 * @return <code>true</code> if the block is the first block in
376 * an exception hander or <code>false</code> if it is not
377 */
378 public final boolean isExceptionHandlerBasicBlock() {
379 return (flags & EXCEPTION_HANDLER) != 0;
380 }
381
382 /**
383 * Has the block been marked as being reachable from an
384 * exception handler?
385 *
386 * @return <code>true</code> if the block is reachable from
387 * an exception hander or <code>false</code> if it is not
388 */
389 public final boolean isReachableFromExceptionHandler() {
390 return (flags & REACHABLE_FROM_EXCEPTION_HANDLER) != 0;
391 }
392
393 /**
394 * Compare the in scope exception handlers of two blocks.
395 *
396 * @param other block to be compared to this.
397 * @return <code>true</code> if this and other have equivalent in
398 * scope exception handlers.
399 */
400 public final boolean isExceptionHandlerEquivalent(BasicBlock other) {
401 // We might be able to do something,
402 // by considering the (subset) of reachable exception handlers,
403 // but it would be awfully tricky to get it right,
404 // so just give up if they aren't equivalent.
405 if (exceptionHandlers != other.exceptionHandlers) {
406 // Even if not pointer ==, they still may be equivalent
407 BasicBlockEnumeration e1 = getExceptionHandlers();
408 BasicBlockEnumeration e2 = other.getExceptionHandlers();
409 while (e1.hasMoreElements()) {
410 if (!e2.hasMoreElements()) return false;
411 if (e1.next() != e2.next()) return false;
412 }
413 if (e2.hasMoreElements()) return false;
414 }
415 return true;
416 }
417
418 /**
419 * Has the block been marked as being unsafe to schedule
420 * (due to the presence of Magic)?
421 *
422 * @return <code>true</code> if the block is marked as unsafe
423 * to schedule or <code>false</code> if it is not
424 */
425 public final boolean isUnsafeToSchedule() {
426 return (flags & UNSAFE_TO_SCHEDULE) != 0;
427 }
428
429 /**
430 * Has the block been marked as being infrequently executed?
431 * NOTE: Only blocks that are truly icy cold should be marked
432 * as infrequent.
433 *
434 * @return <code>true</code> if the block is marked as infrequently
435 * executed or <code>false</code> if it is not
436 */
437 public final boolean getInfrequent() {
438 return (flags & INFREQUENT) != 0;
439 }
440
441 /**
442 * Is the scratch flag set on the block?
443 *
444 * @return <code>true</code> if the block scratch flag is set
445 * or <code>false</code> if it is not
446 */
447 public final boolean getScratchFlag() {
448 return (flags & SCRATCH) != 0;
449 }
450
451 /**
452 * Has the block been marked as landing pad?
453 *
454 * @return <code>true</code> if the block is marked as landing pad
455 * or <code>false</code> if it is not
456 */
457 public final boolean getLandingPad() {
458 return (flags & LANDING_PAD) != 0;
459 }
460
461 /**
462 * Mark the block as possibly raising an exception.
463 */
464 public final void setCanThrowExceptions() {
465 flags |= CAN_THROW_EXCEPTIONS;
466 }
467
468 /**
469 * Mark the block as possibly raising an uncaught exception.
470 */
471 public final void setMayThrowUncaughtException() {
472 flags |= IMPLICIT_EXIT_EDGE;
473 }
474
475 /**
476 * Mark the block as the first block in an exception handler.
477 */
478 public final void setExceptionHandlerBasicBlock() {
479 flags |= EXCEPTION_HANDLER;
480 }
481
482 /**
483 * Mark the block as being reachable from an exception handler.
484 */
485 public final void setReachableFromExceptionHandler() {
486 flags |= REACHABLE_FROM_EXCEPTION_HANDLER;
487 }
488
489 /**
490 * Mark the block as being unsafe to schedule.
491 */
492 public final void setUnsafeToSchedule() {
493 flags |= UNSAFE_TO_SCHEDULE;
494 }
495
496 /**
497 * Mark the block as being infrequently executed.
498 */
499 public final void setInfrequent() {
500 flags |= INFREQUENT;
501 }
502
503 /**
504 * Set the scratch flag
505 */
506 public final void setScratchFlag() {
507 flags |= SCRATCH;
508 }
509
510 /**
511 * Mark the block as a landing pad for loop invariant code motion.
512 */
513 public final void setLandingPad() {
514 flags |= LANDING_PAD;
515 }
516
517 /**
518 * Clear the may raise an exception property of the block
519 */
520 public final void clearCanThrowExceptions() {
521 flags &= ~CAN_THROW_EXCEPTIONS;
522 }
523
524 /**
525 * Clear the may raise uncaught exception property of the block
526 */
527 public final void clearMayThrowUncaughtException() {
528 flags &= ~IMPLICIT_EXIT_EDGE;
529 }
530
531 /**
532 * Clear the block is the first one in an exception handler
533 * property of the block.
534 */
535 public final void clearExceptionHandlerBasicBlock() {
536 flags &= ~EXCEPTION_HANDLER;
537 }
538
539 /**
540 * Clear the block is reachable from an exception handler
541 * property of the block.
542 */
543 public final void clearReachableFromExceptionHandler() {
544 flags &= ~REACHABLE_FROM_EXCEPTION_HANDLER;
545 }
546
547 /**
548 * Clear the unsafe to schedule property of the block
549 */
550 public final void clearUnsafeToSchedule() {
551 flags &= ~UNSAFE_TO_SCHEDULE;
552 }
553
554 /**
555 * Clear the infrequently executed property of the block
556 */
557 public final void clearInfrequent() {
558 flags &= ~INFREQUENT;
559 }
560
561 /**
562 * Clear the scratch flag.
563 */
564 public final void clearScratchFlag() {
565 flags &= ~SCRATCH;
566 }
567
568 /**
569 * Clear the landing pad property of the block
570 */
571 public final void clearLandingPad() {
572 flags &= ~LANDING_PAD;
573 }
574
575 private void setCanThrowExceptions(boolean v) {
576 if (v) {
577 setCanThrowExceptions();
578 } else {
579 clearCanThrowExceptions();
580 }
581 }
582
583 private void setMayThrowUncaughtException(boolean v) {
584 if (v) {
585 setMayThrowUncaughtException();
586 } else {
587 clearMayThrowUncaughtException();
588 }
589 }
590
591 @SuppressWarnings("unused")
592 // FIXME can this be deleted ??
593 private void setIsExceptionHandlerBasicBlock(boolean v) {
594 if (v) {
595 setExceptionHandlerBasicBlock();
596 } else {
597 clearExceptionHandlerBasicBlock();
598 }
599 }
600
601 private void setUnsafeToSchedule(boolean v) {
602 if (v) {
603 setUnsafeToSchedule();
604 } else {
605 clearUnsafeToSchedule();
606 }
607 }
608
609 final void setInfrequent(boolean v) {
610 if (v) {
611 setInfrequent();
612 } else {
613 clearInfrequent();
614 }
615 }
616
617 public final void setExceptionHandlerWithNormalIn() {
618 flags |= EXCEPTION_HANDLER_WITH_NORMAL_IN;
619 }
620
621 private boolean isExceptionHandlerWithNormalIn() {
622 return (flags & EXCEPTION_HANDLER_WITH_NORMAL_IN) != 0;
623 }
624
625 /**
626 * Make a branch operand with the label instruction
627 * of this block.
628 *
629 * @return an BranchOperand holding this blocks label
630 */
631 public final BranchOperand makeJumpTarget() {
632 return new BranchOperand(firstInstruction());
633 }
634
635 /**
636 * Make a GOTO instruction, branching to the first instruction of
637 * this basic block.
638 *
639 * @return a GOTO instruction that jumps to this block
640 */
641 public final Instruction makeGOTO() {
642 return Goto.create(GOTO, makeJumpTarget());
643 }
644
645 /**
646 * @return the first instruciton of the basic block (the label)
647 */
648 public final Instruction firstInstruction() {
649 return start;
650 }
651
652 /**
653 * @return the first 'real' instruction of the basic block;
654 * null if the block is empty
655 */
656 public final Instruction firstRealInstruction() {
657 if (isEmpty()) {
658 return null;
659 } else {
660 return start.getNext();
661 }
662 }
663
664 /**
665 * @return the last instruction of the basic block (the BBEND)
666 */
667 public final Instruction lastInstruction() {
668 return end;
669 }
670
671 /**
672 * @return the last 'real' instruction of the basic block;
673 * null if the block is empty
674 */
675 public final Instruction lastRealInstruction() {
676 if (isEmpty()) {
677 return null;
678 } else {
679 return end.getPrev();
680 }
681 }
682
683 /**
684 * Return the estimated relative execution frequency of the block
685 */
686 public final float getExecutionFrequency() {
687 return freq;
688 }
689
690 /**
691 * Set the estimated relative execution frequency of this block.
692 */
693 public final void setExecutionFrequency(float f) {
694 freq = f;
695 }
696
697 /**
698 * Scale the estimated relative execution frequency of this block.
699 */
700 public final void scaleExecutionFrequency(float f) {
701 freq *= f;
702 }
703
704 /**
705 * Augment the estimated relative execution frequency of this block.
706 */
707 public final void augmentExecutionFrequency(float f) {
708 freq += f;
709 }
710
711 /**
712 * Is this block the exit basic block?
713 *
714 * @return <code>true</code> if this block is the EXIT or
715 * <code>false</code> if it is not
716 */
717 public final boolean isExit() {
718 return start == null;
719 }
720
721 /**
722 * Forward enumeration of all the instruction in the block.
723 * @return a forward enumeration of the block's instructons.
724 */
725 public final InstructionEnumeration forwardInstrEnumerator() {
726 return IREnumeration.forwardIntraBlockIE(firstInstruction(), lastInstruction());
727 }
728
729 /**
730 * Reverse enumeration of all the instruction in the block.
731 * @return a reverse enumeration of the block's instructons.
732 */
733 public final InstructionEnumeration reverseInstrEnumerator() {
734 return IREnumeration.reverseIntraBlockIE(lastInstruction(), firstInstruction());
735 }
736
737 /**
738 * Forward enumeration of all the real instruction in the block.
739 * @return a forward enumeration of the block's real instructons.
740 */
741 public final InstructionEnumeration forwardRealInstrEnumerator() {
742 return IREnumeration.forwardIntraBlockIE(firstRealInstruction(), lastRealInstruction());
743 }
744
745 /**
746 * Reverse enumeration of all the real instruction in the block.
747 * @return a reverse enumeration of the block's real instructons.
748 */
749 public final InstructionEnumeration reverseRealInstrEnumerator() {
750 return IREnumeration.reverseIntraBlockIE(lastRealInstruction(), firstRealInstruction());
751 }
752
753 /**
754 * How many real instructions does the block contain?
755 * WARNING: This method actually counts the instructions,
756 * thus it has a linear time complexity!
757 *
758 * @return the number of "real" instructions in this basic block.
759 */
760 public int getNumberOfRealInstructions() {
761 int count = 0;
762 for (InstructionEnumeration e = forwardRealInstrEnumerator(); e.hasMoreElements(); e.next()) {
763 count++;
764 }
765
766 return count;
767 }
768
769 /**
770 * Does this basic block end in a GOTO instruction?
771 *
772 * @return <code>true</code> if the block ends in a GOTO
773 * or <code>false</code> if it does not
774 */
775 public final boolean hasGoto() {
776 if (isEmpty()) return false;
777 return Goto.conforms(lastRealInstruction()) || MIR_Branch.conforms(lastRealInstruction());
778 }
779
780 /**
781 * Does this basic block end in a RETURN instruction?
782 *
783 * @return <code>true</code> if the block ends in a RETURN
784 * or <code>false</code> if it does not
785 */
786 public final boolean hasReturn() {
787 if (isEmpty()) return false;
788 return Return.conforms(lastRealInstruction()) || MIR_Return.conforms(lastRealInstruction());
789 }
790
791 /**
792 * Does this basic block end in a SWITCH instruction?
793 *
794 * @return <code>true</code> if the block ends in a SWITCH
795 * or <code>false</code> if it does not
796 */
797 public final boolean hasSwitch() {
798 if (isEmpty()) return false;
799 Instruction s = lastRealInstruction();
800 return TableSwitch.conforms(s) || LowTableSwitch.conforms(s) || LookupSwitch.conforms(s);
801 }
802
803 /**
804 * Does this basic block contain an explicit athrow instruction?
805 *
806 * @return <code>true</code> if the block ends in an explicit Athrow
807 * instruction or <code>false</code> if it does not
808 */
809 public final boolean hasAthrowInst() {
810 if (isEmpty()) return false;
811 Instruction s = lastRealInstruction();
812
813 if (VM.BuildForIA32 && Operators.helper.isAdviseESP(s.operator)) {
814 s = s.getPrev();
815 }
816
817 if (Athrow.conforms(s)) {
818 return true;
819 }
820 MethodOperand mop = null;
821 if (MIR_Call.conforms(s)) {
822 mop = MIR_Call.getMethod(s);
823 } else if (Call.conforms(s)) {
824 mop = Call.getMethod(s);
825 }
826 return mop != null && mop.getTarget() == Entrypoints.athrowMethod;
827 }
828
829 /**
830 * Does this basic block end in an explicit trap?
831 *
832 * @return <code>true</code> if the block ends in a an explicit trap
833 * or <code>false</code> if it does not
834 */
835 public final boolean hasTrap() {
836 if (isEmpty()) return false;
837 Instruction s = lastRealInstruction();
838
839 return Trap.conforms(s);
840 }
841
842 /**
843 * Does this basic block end in a call that never returns?
844 * (For example, a call to athrow())
845 *
846 * @return <code>true</code> if the block ends in a call that never
847 * returns or <code>false</code> if it does not
848 */
849 public final boolean hasNonReturningCall() {
850 if (isEmpty()) return false;
851 Instruction s = lastRealInstruction();
852
853 if (Call.conforms(s)) {
854 MethodOperand methodOp = Call.getMethod(s);
855 if (methodOp != null && methodOp.isNonReturningCall()) {
856 return true;
857 }
858 }
859
860 return false;
861 }
862
863 public final boolean hasNonReturningOsr() {
864 if (isEmpty()) return false;
865 Instruction s = lastRealInstruction();
866 return OsrPoint.conforms(s);
867 }
868
869 /**
870 * If there is a fallthrough FCFG successor of this node
871 * return it.
872 *
873 * @return the fall-through successor of this node or
874 * <code>null</code> if none exists
875 */
876 public final BasicBlock getFallThroughBlock() {
877 if (hasGoto()) return null;
878 if (hasSwitch()) return null;
879 if (hasReturn()) return null;
880 if (hasAthrowInst()) return null;
881 if (hasTrap()) return null;
882 if (hasNonReturningCall()) return null;
883 if (hasNonReturningOsr()) return null;
884
885 return nextBasicBlockInCodeOrder();
886 }
887
888 /**
889 * @return the FCFG successor if all conditional branches in this are
890 * <em> not </em> taken
891 */
892 public final BasicBlock getNotTakenNextBlock() {
893 Instruction last = lastRealInstruction();
894 if (Goto.conforms(last) || MIR_Branch.conforms(last)) {
895 return last.getBranchTarget();
896 } else {
897 return nextBasicBlockInCodeOrder();
898 }
899 }
900
901 /**
902 * Replace fall through in this block by an explicit goto
903 */
904 public void killFallThrough() {
905 BasicBlock fallThrough = getFallThroughBlock();
906 if (fallThrough != null) {
907 lastInstruction().insertBefore(Goto.create(GOTO, fallThrough.makeJumpTarget()));
908 }
909 }
910
911 /**
912 * Prepend instruction to this basic block by inserting it right after
913 * the LABEL instruction in the instruction list.
914 *
915 * @param i instruction to append
916 */
917 public final void prependInstruction(Instruction i) {
918 start.insertAfter(i);
919 }
920
921 /**
922 * Prepend instruction to this basic block but respect the prologue
923 * instruction, which must come first.
924 *
925 * @param i instruction to append
926 */
927 public final void prependInstructionRespectingPrologue(Instruction i) {
928 Instruction first = firstRealInstruction();
929 if ((first != null) && (first.getOpcode() == IR_PROLOGUE_opcode)) {
930 first.insertAfter(i);
931 } else {
932 start.insertAfter(i);
933 }
934 }
935
936 /**
937 * Append instruction to this basic block by inserting it right before
938 * the BBEND instruction in the instruction list.
939 *
940 * @param i instruction to append
941 */
942 public final void appendInstruction(Instruction i) {
943 end.insertBefore(i);
944 }
945
946 /**
947 * Append instruction to this basic block by inserting it right before
948 * the BBEND instruction in the instruction list. However, if
949 * the basic block ends in a sequence of branch instructions, insert
950 * the instruction before the first branch instruction.
951 *
952 * @param i instruction to append
953 */
954 public final void appendInstructionRespectingTerminalBranch(Instruction i) {
955 Instruction s = end;
956 while (s.getPrev().operator().isBranch()) s = s.getPrev();
957 s.insertBefore(i);
958 }
959
960 /**
961 * Append instruction to this basic block by inserting it right before
962 * the BBEND instruction in the instruction list. However, if
963 * the basic block ends in a sequence of branch instructions, insert
964 * the instruction before the first branch instruction. If the block
965 * ends in a PEI, insert the instruction before the PEI.
966 * This function is meant to be used when the block has
967 * been {@link #unfactor(IR) unfactored} and thus is in CFG form.
968 *
969 * @param i instruction to append
970 */
971 public final void appendInstructionRespectingTerminalBranchOrPEI(Instruction i) {
972 Instruction s = end;
973 while (s.getPrev().operator().isBranch() ||
974 s.getPrev().operator().isThrow() ||
975 (s.getPrev().isPEI() && getApplicableExceptionalOut(s.getPrev()).hasMoreElements())) {
976 s = s.getPrev();
977 }
978 s.insertBefore(i);
979 }
980
981 /**
982 * Return an enumeration of the branch instructions in this
983 * basic block.
984 * @return an forward enumeration of this blocks branch instruction
985 */
986 public final InstructionEnumeration enumerateBranchInstructions() {
987 Instruction start = firstBranchInstruction();
988 Instruction end = (start == null) ? null : lastRealInstruction();
989 return IREnumeration.forwardIntraBlockIE(start, end);
990 }
991
992 /**
993 * Return the first branch instruction in the block.
994 *
995 * @return the first branch instruction in the block
996 * or <code>null</code> if there are none.
997 */
998 public final Instruction firstBranchInstruction() {
999 Instruction s = lastRealInstruction();
1000 if (s == null) return null;
1001 if (!s.operator().isBranch()) return null;
1002 while (s.getPrev().isBranch()) {
1003 s = s.getPrev();
1004 }
1005 return s;
1006 }
1007
1008 /**
1009 * Return the next basic block in with respect to the current
1010 * code linearization order.
1011 *
1012 * @return the next basic block in the code order or
1013 * <code>null</code> if no such block exists
1014 */
1015 public final BasicBlock nextBasicBlockInCodeOrder() {
1016 return (BasicBlock) getNext();
1017 }
1018
1019 /**
1020 * Return the previous basic block in with respect to the current
1021 * code linearization order.
1022 *
1023 * @return the previous basic block in the code order or
1024 * <code>null</code> if no such block exists
1025 */
1026 public final BasicBlock prevBasicBlockInCodeOrder() {
1027 return (BasicBlock) getPrev();
1028 }
1029
1030 /**
1031 * Returns true if the block contains no real instructions
1032 *
1033 * @return <code>true</code> if the block contains no real instructions
1034 * or <code>false</code> if it does.
1035 */
1036 public final boolean isEmpty() {
1037 return start.getNext() == end;
1038 }
1039
1040 /**
1041 * Are there any exceptional out edges that are applicable
1042 * to the given instruction (assumed to be in instruction in 'this')
1043 *
1044 * @param instr the instruction in question
1045 * @return true or false;
1046 */
1047 public final boolean hasApplicableExceptionalOut(Instruction instr) {
1048 return getApplicableExceptionalOut(instr).hasMoreElements();
1049 }
1050
1051 /**
1052 * An enumeration of the subset of exceptional out edges that are applicable
1053 * to the given instruction (assumed to be in instruction in 'this')
1054 *
1055 * @param instr the instruction in question
1056 * @return an enumeration of the exceptional out edges applicable to instr
1057 */
1058 public final BasicBlockEnumeration getApplicableExceptionalOut(Instruction instr) {
1059 if (instr.isPEI()) {
1060 int numPossible = getNumberOfExceptionalOut();
1061 if (numPossible == 0) return BasicBlockEnumeration.Empty;
1062 ComputedBBEnum e = new ComputedBBEnum(numPossible);
1063 switch (instr.getOpcode()) {
1064 case ATHROW_opcode:
1065 TypeReference type = Athrow.getValue(instr).getType();
1066 addTargets(e, type);
1067 break;
1068 case CHECKCAST_opcode:
1069 case CHECKCAST_NOTNULL_opcode:
1070 case CHECKCAST_UNRESOLVED_opcode:
1071 addTargets(e, TypeReference.JavaLangClassCastException);
1072 break;
1073 case NULL_CHECK_opcode:
1074 addTargets(e, TypeReference.JavaLangNullPointerException);
1075 break;
1076 case BOUNDS_CHECK_opcode:
1077 addTargets(e, TypeReference.JavaLangArrayIndexOutOfBoundsException);
1078 break;
1079 case INT_ZERO_CHECK_opcode:
1080 case LONG_ZERO_CHECK_opcode:
1081 addTargets(e, TypeReference.JavaLangArithmeticException);
1082 break;
1083 case OBJARRAY_STORE_CHECK_opcode:
1084 addTargets(e, TypeReference.JavaLangArrayStoreException);
1085 break;
1086 default:
1087 // Not an operator for which we have a more refined notion of
1088 // its exception semantics, so assume that any reachable exception
1089 // handler might be a potential target of this PEI
1090 return getExceptionalOut();
1091 }
1092 return e;
1093 } else {
1094 return BasicBlockEnumeration.Empty;
1095 }
1096 }
1097
1098 // add all handler blocks in this's out set that might possibly catch
1099 // an exception of static type throwException
1100 // (may dynamically be any subtype of thrownException)
1101 private void addTargets(ComputedBBEnum e, TypeReference thrownException) {
1102 for (SpaceEffGraphEdge ed = _outEdgeStart; ed != null; ed = ed.getNextOut()) {
1103 BasicBlock bb = (BasicBlock) ed.toNode();
1104 if (bb.isExceptionHandlerBasicBlock()) {
1105 ExceptionHandlerBasicBlock eblock = (ExceptionHandlerBasicBlock) bb;
1106 if (eblock.mayCatchException(thrownException) != NO) {
1107 e.addPossiblyDuplicateElement(eblock);
1108 }
1109 }
1110 }
1111 }
1112
1113 /**
1114 * An enumeration of the in scope exception handlers for this basic block.
1115 * Note that this may be a superset of the exception handlers
1116 * actually included in the out set of this basic block.
1117 *
1118 * @return an enumeration of all inscope exception handlers
1119 */
1120 public final BasicBlockEnumeration getExceptionHandlers() {
1121 if (exceptionHandlers == null) {
1122 return BasicBlockEnumeration.Empty;
1123 } else {
1124 return exceptionHandlers.enumerator();
1125 }
1126 }
1127
1128 /**
1129 * Is this block in the scope of at least exception handler?
1130 *
1131 * @return <code>true</code> if there is at least one in scope
1132 * exception handler, <code>false</code> otherwise
1133 */
1134 public final boolean hasExceptionHandlers() {
1135 return exceptionHandlers != null;
1136 }
1137
1138 /**
1139 * Returns an Enumeration of the in scope exception handlers that are
1140 * actually reachable from this basic block in the order that they are
1141 * applicable (which is semantically meaningful).
1142 * IE, this is those blocks in getExceptionalOut ordered as
1143 * in getExceptionHandlers.
1144 *
1145 * @return an enumeration of the reachable exception handlers
1146 */
1147 public final BasicBlockEnumeration getReachableExceptionHandlers() {
1148 if (hasExceptionHandlers()) {
1149 int count = 0;
1150 for (BasicBlockEnumeration inScope = getExceptionHandlers(); inScope.hasMoreElements(); inScope.next()) {
1151 count++;
1152 }
1153
1154 ComputedBBEnum ans = new ComputedBBEnum(count);
1155
1156 for (BasicBlockEnumeration inScope = getExceptionHandlers(); inScope.hasMoreElements();) {
1157 BasicBlock cand = inScope.next();
1158 if (pointsOut(cand)) ans.addPossiblyDuplicateElement(cand);
1159 }
1160 return ans;
1161 } else {
1162 return BasicBlockEnumeration.Empty;
1163 }
1164 }
1165
1166 /**
1167 * Delete all the non-exceptional out edges.
1168 * A useful primitive routine for some CFG manipulations.
1169 */
1170 public final void deleteNormalOut() {
1171 for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.getNextOut()) {
1172 BasicBlock out = (BasicBlock) e.toNode();
1173 if (!out.isExceptionHandlerBasicBlock()) {
1174 deleteOut(e);
1175 }
1176 }
1177 }
1178
1179 /**
1180 * Recompute the normal out edges of 'this' based on the
1181 * semantics of the branch instructions in the block.
1182 *
1183 * WARNING: Use this method with caution. It does not update the
1184 * CFG edges correctly if the method contains certain instructions
1185 * such as throws and returns. Incorrect liveness info and GC maps
1186 * result, causing crashes during GC. CMVC Defect 171189
1187 */
1188 public final void recomputeNormalOut(IR ir) {
1189 deleteNormalOut();
1190 for (InstructionEnumeration e = enumerateBranchInstructions(); e.hasMoreElements();) {
1191 Instruction branch = e.next();
1192 BasicBlockEnumeration targets = branch.getBranchTargets();
1193 while (targets.hasMoreElements()) {
1194 insertOut(targets.next());
1195 }
1196 }
1197 // Check for fallthrough edge
1198 BasicBlock fallThrough = getFallThroughBlock();
1199 if (fallThrough != null) {
1200 insertOut(fallThrough);
1201 }
1202
1203 // Check special cases that require edge to exit
1204 if (hasReturn()) {
1205 insertOut(ir.cfg.exit());
1206 } else if (hasAthrowInst() || hasNonReturningCall()) {
1207 if (mayThrowUncaughtException()) {
1208 insertOut(ir.cfg.exit());
1209 }
1210 } else if (hasNonReturningOsr()) {
1211 insertOut(ir.cfg.exit());
1212 }
1213 }
1214
1215 /**
1216 * Ensure that the target instruction is the only real instruction
1217 * in its basic block and that it has exactly one successor and
1218 * one predecessor basic blocks that are linked to it by fall through edges.
1219 *
1220 * @param target the Instruction that must be placed in its own BB
1221 * @param ir the containing IR object
1222 * @return the BasicBlock containing target
1223 */
1224 public final BasicBlock segregateInstruction(Instruction target, IR ir) {
1225 if (IR.PARANOID) VM._assert(this == target.getBasicBlock());
1226
1227 BasicBlock BB1 = splitNodeAt(target.getPrev(), ir);
1228 this.insertOut(BB1);
1229 ir.cfg.linkInCodeOrder(this, BB1);
1230 BasicBlock BB2 = BB1.splitNodeAt(target, ir);
1231 BB1.insertOut(BB2);
1232 ir.cfg.linkInCodeOrder(BB1, BB2);
1233 return BB1;
1234 }
1235
1236 /**
1237 * Splits a node at an instruction point. All the instructions up to and
1238 * including the argument instruction remain in the original basic block.
1239 * All instructions in this basic block but after s in the instruction list
1240 * are moved to the new basic block.
1241 * <ul>
1242 * <li> does not establish control flow edge out of B1 -- caller responsibility
1243 * <li> does not establish control flow edge into B2 -- caller responsibility
1244 * <li> Leaves a break in the code order -- caller responsibility
1245 * to patch back together. If the original code order was
1246 * BB_before -> BB1 -> BB_after
1247 * then the new code order is
1248 * BB_before -> BB1 <break> BB2 -> BB_after.
1249 * Note that if BB_after == null, splitNodeAt does handle
1250 * updating ir.cfg._lastNode to point to BB2.
1251 * </ul>
1252 *
1253 * @param last_instr_BB1 the instr that is to become the last instruction
1254 * in this basic block
1255 * @param ir the containing IR object
1256 * @return the newly created basic block which is the successor to this
1257 */
1258 public final BasicBlock splitNodeAt(Instruction last_instr_BB1, IR ir) {
1259 if (IR.PARANOID) VM._assert(this == last_instr_BB1.getBasicBlock());
1260
1261 BasicBlock BB1 = this;
1262 BasicBlock BB2 = new BasicBlock(last_instr_BB1.bcIndex, last_instr_BB1.position, ir.cfg);
1263 BasicBlock BB3 = (BasicBlock) BB1.next;
1264
1265 // move last_instr_BB1 ... BB1.end.prev into BB2
1266 if (last_instr_BB1 == BB1.end || last_instr_BB1.getNext() == BB1.end) {
1267 // there are no such instructions; nothing to do
1268 } else {
1269 Instruction first_instr_BB2 = last_instr_BB1.getNext();
1270 Instruction last_instr_BB2 = BB1.end.getPrev();
1271 last_instr_BB1.linkWithNext(BB1.end);
1272 BB2.start.linkWithNext(first_instr_BB2);
1273 last_instr_BB2.linkWithNext(BB2.end);
1274 }
1275
1276 // Update code ordering (see header comment above)
1277 if (BB3 == null) {
1278 ir.cfg.addLastInCodeOrder(BB2);
1279 if (IR.PARANOID) VM._assert(BB1.next == BB2 && BB2.prev == BB1);
1280 ir.cfg.breakCodeOrder(BB1, BB2);
1281 } else {
1282 ir.cfg.breakCodeOrder(BB1, BB3);
1283 ir.cfg.linkInCodeOrder(BB2, BB3);
1284 }
1285
1286 // Update control flow graph to transfer BB1's out edges to BB2.
1287 // But it's not as simple as that. Any edge that is present to represent
1288 // potential exception behavior (out.isExceptionHandlerBasicBlock == true)
1289 // needs to be both left in BB1's out set and transfered to BB2's out set
1290 // Note this may be overly conservative, but will be correct.
1291 for (BasicBlockEnumeration e = getOut(); e.hasMoreElements();) {
1292 BasicBlock out = e.next();
1293 BB2.insertOut(out);
1294 }
1295
1296 // Initialize the rest of BB2's exception related state to match BB1
1297 BB2.exceptionHandlers = BB1.exceptionHandlers;
1298 BB2.setCanThrowExceptions(BB1.canThrowExceptions());
1299 BB2.setMayThrowUncaughtException(BB1.mayThrowUncaughtException());
1300 BB2.setUnsafeToSchedule(BB1.isUnsafeToSchedule());
1301 BB2.setExecutionFrequency(BB1.getExecutionFrequency());
1302
1303 BB1.deleteNormalOut();
1304
1305 return BB2;
1306 }
1307
1308 /**
1309 * Splits a node at an instruction point. All the instructions up to and
1310 * including the argument instruction remain in the original basic block
1311 * all instructions in this basic block but after s in the instruction list
1312 * are moved to the new basic block. The blocks are linked together in
1313 * the FCFG and the code order.
1314 * The key difference between this function and
1315 * {@link #splitNodeAt(Instruction,IR)} is that it does
1316 * establish the FCFG edges and code order such that B1 falls into B2.
1317 *
1318 * @param last_instr_BB1 the instr that is to become
1319 * the last instruction in this basic block
1320 * @param ir the containing IR object
1321 * @return the newly created basic block which is the successor to this
1322 */
1323 public final BasicBlock splitNodeWithLinksAt(Instruction last_instr_BB1, IR ir) {
1324
1325 if (IR.PARANOID) VM._assert(this == last_instr_BB1.getBasicBlock());
1326
1327 BasicBlock BB2 = splitNodeAt(last_instr_BB1, ir);
1328 this.insertOut(BB2);
1329 ir.cfg.linkInCodeOrder(this, BB2);
1330 return BB2;
1331 }
1332
1333 /**
1334 * Copies a basic block. The copy differs from the original as follows:
1335 * <ul>
1336 * <li> the copy's number and labels are new, and will be unique in the
1337 * containing IR
1338 * <li> the copy is NOT linked into the IR's bblist
1339 * <li> the copy does NOT appear in the IR's cfg.
1340 * </ul>
1341 * The copy
1342 * <ul>
1343 * <li> inherits the original block's exception handlers
1344 * <li> inherits the original block's bytecode index
1345 * <li> has NEW copies of each instruction.
1346 *
1347 * @param ir the containing IR
1348 * @return the copy
1349 */
1350 public final BasicBlock copyWithoutLinks(IR ir) {
1351 // create a new block with the same bytecode index and exception handlers
1352 int bytecodeIndex = -1;
1353
1354 // Make the label instruction of the new block have the same
1355 // bc info as the label of the original block.
1356 if (firstInstruction() != null) {
1357 bytecodeIndex = firstInstruction().bcIndex;
1358 }
1359
1360 BasicBlock newBlock = createSubBlock(bytecodeIndex, ir, 1f);
1361
1362 // copy each instruction from the original block.
1363 for (Instruction s = firstInstruction().getNext(); s != lastInstruction(); s = s.getNext()) {
1364 newBlock.appendInstruction(s.copyWithoutLinks());
1365 }
1366
1367 // copy other properties of the block.
1368 newBlock.flags = flags;
1369
1370 return newBlock;
1371 }
1372
1373 /**
1374 * For each basic block b which is a "normal" successor of this,
1375 * make a copy of b, and set up the CFG so that this block has
1376 * normal out edges to the copies.
1377 *
1378 * WARNING: Use this method with caution. See comment on
1379 * BasicBlock.recomputeNormalOut()
1380 *
1381 * @param ir the containing IR
1382 */
1383 public final void replicateNormalOut(IR ir) {
1384 // for each normal out successor (b) of 'this' ....
1385 for (BasicBlockEnumeration e = getNormalOut(); e.hasMoreElements();) {
1386 BasicBlock b = e.next();
1387 replicateThisOut(ir, b);
1388 }
1389 }
1390
1391 /**
1392 * For basic block b which has to be a "normal" successor of this,
1393 * make a copy of b, and set up the CFG so that this block has
1394 * normal out edges to the copy.
1395 *
1396 * WARNING: Use this method with caution. See comment on
1397 * BasicBlock.recomputeNormalOut()
1398 *
1399 * @param ir the governing IR
1400 * @param b the block to replicate
1401 */
1402 public final BasicBlock replicateThisOut(IR ir, BasicBlock b) {
1403 return replicateThisOut(ir, b, this);
1404 }
1405
1406 /**
1407 * For basic block b which has to be a "normal" successor of this,
1408 * make a copy of b, and set up the CFG so that this block has
1409 * normal out edges to the copy.
1410 *
1411 * WARNING: Use this method with caution. See comment on
1412 * BasicBlock.recomputeNormalOut()
1413 *
1414 * @param ir the governing IR
1415 * @param b the block to replicate
1416 * @param pred code order predecessor for new block
1417 */
1418 public final BasicBlock replicateThisOut(IR ir, BasicBlock b, BasicBlock pred) {
1419 // don't replicate the exit node
1420 if (b.isExit()) return null;
1421
1422 // 1. create the replicated block (bCopy)
1423 BasicBlock bCopy = b.copyWithoutLinks(ir);
1424
1425 // 2. If b has a fall-through edge, insert the appropriate GOTO at
1426 // the end of bCopy
1427 BasicBlock bFallThrough = b.getFallThroughBlock();
1428 if (bFallThrough != null) {
1429 Instruction g = Goto.create(GOTO, bFallThrough.makeJumpTarget());
1430 bCopy.appendInstruction(g);
1431 }
1432 bCopy.recomputeNormalOut(ir);
1433
1434 // 3. update the branch instructions in 'this' to point to bCopy
1435 redirectOuts(b, bCopy, ir);
1436
1437 // 4. link the new basic into the code order, immediately following pred
1438 pred.killFallThrough();
1439 BasicBlock next = pred.nextBasicBlockInCodeOrder();
1440 if (next != null) {
1441 ir.cfg.breakCodeOrder(pred, next);
1442 ir.cfg.linkInCodeOrder(bCopy, next);
1443 }
1444 ir.cfg.linkInCodeOrder(pred, bCopy);
1445
1446 return bCopy;
1447 }
1448
1449 /**
1450 * Move