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 */
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 public final 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 BasicBlock targetBlock = targets.next();
1195 if (targetBlock.isExceptionHandlerBasicBlock()) {
1196 targetBlock.setExceptionHandlerWithNormalIn();
1197 }
1198 insertOut(targetBlock);
1199 }
1200 }
1201 // Check for fallthrough edge
1202 BasicBlock fallThrough = getFallThroughBlock();
1203 if (fallThrough != null) {
1204 if (fallThrough.isExceptionHandlerBasicBlock()) {
1205 fallThrough.setExceptionHandlerWithNormalIn();
1206 }
1207 insertOut(fallThrough);
1208 }
1209
1210 // Check special cases that require edge to exit
1211 if (hasReturn()) {
1212 insertOut(ir.cfg.exit());
1213 } else if (hasAthrowInst() || hasNonReturningCall()) {
1214 if (mayThrowUncaughtException()) {
1215 insertOut(ir.cfg.exit());
1216 }
1217 } else if (hasNonReturningOsr()) {
1218 insertOut(ir.cfg.exit());
1219 }
1220 }
1221
1222 /**
1223 * Ensure that the target instruction is the only real instruction
1224 * in its basic block and that it has exactly one successor and
1225 * one predecessor basic blocks that are linked to it by fall through edges.
1226 *
1227 * @param target the Instruction that must be placed in its own BB
1228 * @param ir the containing IR object
1229 * @return the BasicBlock containing target
1230 */
1231 public final BasicBlock segregateInstruction(Instruction target, IR ir) {
1232 if (IR.PARANOID) VM._assert(this == target.getBasicBlock());
1233
1234 BasicBlock BB1 = splitNodeAt(target.getPrev(), ir);
1235 this.insertOut(BB1);
1236 ir.cfg.linkInCodeOrder(this, BB1);
1237 BasicBlock BB2 = BB1.splitNodeAt(target, ir);
1238 BB1.insertOut(BB2);
1239 ir.cfg.linkInCodeOrder(BB1, BB2);
1240 return BB1;
1241 }
1242
1243 /**
1244 * Splits a node at an instruction point. All the instructions up to and
1245 * including the argument instruction remain in the original basic block.
1246 * All instructions in this basic block but after s in the instruction list
1247 * are moved to the new basic block.
1248 * <ul>
1249 * <li> does not establish control flow edge out of B1 -- caller responsibility
1250 * <li> does not establish control flow edge into B2 -- caller responsibility
1251 * <li> Leaves a break in the code order -- caller responsibility
1252 * to patch back together. If the original code order was
1253 * BB_before -> BB1 -> BB_after
1254 * then the new code order is
1255 * BB_before -> BB1 <break> BB2 -> BB_after.
1256 * Note that if BB_after == null, splitNodeAt does handle
1257 * updating ir.cfg._lastNode to point to BB2.
1258 * </ul>
1259 *
1260 * @param last_instr_BB1 the instr that is to become the last instruction
1261 * in this basic block
1262 * @param ir the containing IR object
1263 * @return the newly created basic block which is the successor to this
1264 */
1265 public final BasicBlock splitNodeAt(Instruction last_instr_BB1, IR ir) {
1266 if (IR.PARANOID) VM._assert(this == last_instr_BB1.getBasicBlock());
1267
1268 BasicBlock BB1 = this;
1269 BasicBlock BB2 = new BasicBlock(last_instr_BB1.bcIndex, last_instr_BB1.position, ir.cfg);
1270 BasicBlock BB3 = (BasicBlock) BB1.next;
1271
1272 // move last_instr_BB1 ... BB1.end.prev into BB2
1273 if (last_instr_BB1 == BB1.end || last_instr_BB1.getNext() == BB1.end) {
1274 // there are no such instructions; nothing to do
1275 } else {
1276 Instruction first_instr_BB2 = last_instr_BB1.getNext();
1277 Instruction last_instr_BB2 = BB1.end.getPrev();
1278 last_instr_BB1.linkWithNext(BB1.end);
1279 BB2.start.linkWithNext(first_instr_BB2);
1280 last_instr_BB2.linkWithNext(BB2.end);
1281 }
1282
1283 // Update code ordering (see header comment above)
1284 if (BB3 == null) {
1285 ir.cfg.addLastInCodeOrder(BB2);
1286 if (IR.PARANOID) VM._assert(BB1.next == BB2 && BB2.prev == BB1);
1287 ir.cfg.breakCodeOrder(BB1, BB2);
1288 } else {
1289 ir.cfg.breakCodeOrder(BB1, BB3);
1290 ir.cfg.linkInCodeOrder(BB2, BB3);
1291 }
1292
1293 // Update control flow graph to transfer BB1's out edges to BB2.
1294 // But it's not as simple as that. Any edge that is present to represent
1295 // potential exception behavior (out.isExceptionHandlerBasicBlock == true)
1296 // needs to be both left in BB1's out set and transfered to BB2's out set
1297 // Note this may be overly conservative, but will be correct.
1298 for (BasicBlockEnumeration e = getOut(); e.hasMoreElements();) {
1299 BasicBlock out = e.next();
1300 BB2.insertOut(out);
1301 }
1302
1303 // Initialize the rest of BB2's exception related state to match BB1
1304 BB2.exceptionHandlers = BB1.exceptionHandlers;
1305 BB2.setCanThrowExceptions(BB1.canThrowExceptions());
1306 BB2.setMayThrowUncaughtException(BB1.mayThrowUncaughtException());
1307 BB2.setUnsafeToSchedule(BB1.isUnsafeToSchedule());
1308 BB2.setExecutionFrequency(BB1.getExecutionFrequency());
1309
1310 BB1.deleteNormalOut();
1311
1312 return BB2;
1313 }
1314
1315 /**
1316 * Splits a node at an instruction point. All the instructions up to and
1317 * including the argument instruction remain in the original basic block
1318 * all instructions in this basic block but after s in the instruction list
1319 * are moved to the new basic block. The blocks are linked together in
1320 * the FCFG and the code order.
1321 * The key difference between this function and
1322 * {@link #splitNodeAt(Instruction,IR)} is that it does
1323 * establish the FCFG edges and code order such that B1 falls into B2.
1324 *
1325 * @param last_instr_BB1 the instr that is to become
1326 * the last instruction in this basic block
1327 * @param ir the containing IR object
1328 * @return the newly created basic block which is the successor to this
1329 */
1330 public final BasicBlock splitNodeWithLinksAt(Instruction last_instr_BB1, IR ir) {
1331
1332 if (IR.PARANOID) VM._assert(this == last_instr_BB1.getBasicBlock());
1333
1334 BasicBlock BB2 = splitNodeAt(last_instr_BB1, ir);
1335 this.insertOut(BB2);
1336 ir.cfg.linkInCodeOrder(this, BB2);
1337 return BB2;
1338 }
1339
1340 /**
1341 * Copies a basic block. The copy differs from the original as follows:
1342 * <ul>
1343 * <li> the copy's number and labels are new, and will be unique in the
1344 * containing IR
1345 * <li> the copy is NOT linked into the IR's bblist
1346 * <li> the copy does NOT appear in the IR's cfg.
1347 * </ul>
1348 * The copy
1349 * <ul>
1350 * <li> inherits the original block's exception handlers
1351 * <li> inherits the original block's bytecode index
1352 * <li> has NEW copies of each instruction.
1353 *
1354 * @param ir the containing IR
1355 * @return the copy
1356 */
1357 public final BasicBlock copyWithoutLinks(IR ir) {
1358 // create a new block with the same bytecode index and exception handlers
1359 int bytecodeIndex = -1;
1360
1361 // Make the label instruction of the new block have the same
1362 // bc info as the label of the original block.
1363 if (firstInstruction() != null) {
1364 bytecodeIndex = firstInstruction().bcIndex;
1365 }
1366
1367 BasicBlock newBlock = createSubBlock(bytecodeIndex, ir, 1f);
1368
1369 // copy each instruction from the original block.
1370 for (Instruction s = firstInstruction().getNext(); s != lastInstruction(); s = s.getNext()) {
1371 newBlock.appendInstruction(s.copyWithoutLinks());
1372 }
1373
1374 // copy other properties of the block.
1375 newBlock.flags = flags;
1376
1377 return newBlock;
1378 }
1379
1380 /**
1381 * For each basic block b which is a "normal" successor of this,
1382 * make a copy of b, and set up the CFG so that this block has
1383 * normal out edges to the copies.
1384 *
1385 * WARNING: Use this method with caution. See comment on
1386 * BasicBlock.recomputeNormalOut()
1387 *
1388 * @param ir the containing IR
1389 */
1390 public final void replicateNormalOut(IR ir) {
1391 // for each normal out successor (b) of 'this' ....
1392 for (BasicBlockEnumeration e = getNormalOut(); e.hasMoreElements();) {
1393 BasicBlock b = e.next();
1394 replicateThisOut(ir, b);
1395 }
1396 }
1397
1398 /**
1399 * For basic block b which has to be a "normal" successor of this,
1400 * make a copy of b, and set up the CFG so that this block has
1401 * normal out edges to the copy.
1402 *
1403 * WARNING: Use this method with caution. See comment on
1404 * BasicBlock.recomputeNormalOut()
1405 *
1406 * @param ir the governing IR
1407 * @param b the block to replicate
1408 */
1409 public final BasicBlock replicateThisOut(IR ir, BasicBlock b) {
1410 return replicateThisOut(ir, b, this);
1411 }
1412
1413 /**
1414 * For basic block b which has to be a "normal" successor of this,
1415 * make a copy of b, and set up the CFG so that this block has
1416 * normal out edges to the copy.
1417 *
1418 * WARNING: Use this method with caution. See comment on
1419 * BasicBlock.recomputeNormalOut()
1420 *
1421 * @param ir the governing IR
1422 * @param b the block to replicate
1423 * @param pred code order predecessor for new block
1424 */
1425 public final BasicBlock replicateThisOut(IR ir, BasicBlock b, BasicBlock pred) {
1426 // don't replicate the exit node
1427 if (b.isExit()) return null;
1428
1429 // 1. create the replicated block (bCopy)
1430 BasicBlock bCopy = b.copyWithoutLinks(ir);
1431
1432 // 2. If b has a fall-through edge, insert the appropriate GOTO at
1433 // the end of bCopy
1434 BasicBlock bFallThrough = b.getFallThroughBlock();
1435 if (bFallThrough != null) {
1436 Instruction g = Goto.create(GOTO, bFallThrough.makeJumpTarget());
1437 bCopy.appendInstruction(g);
1438 }
1439 bCopy.recomputeNormalOut(ir);
1440
1441 // 3. update the branch instructions in 'this' to point to bCopy
1442 redirectOuts(b, bCopy, ir);
1443
1444 // 4. link the new basic into the code order, immediately following pred
1445 pred.killFallThrough();
1446 BasicBlock next = pred.nextBasicBlockInCodeOrder();
1447 if (next != null) {
1448 ir.cfg.breakCodeOrder(pred, next);
1449 ir.cfg.linkInCodeOrder(bCopy, next);
1450 }
1451 ir.cfg.linkInCodeOrder(pred, bCopy);
1452
1453 return bCopy;
1454 }
1455
1456 /**
1457 * Move me behind `pred'.
1458 *
1459 * @param pred my desired code order predecessor
1460 * @param ir the governing IR
1461 */
1462 public void moveBehind(BasicBlock pred, IR ir) {
1463 killFallThrough();
1464 pred.killFallThrough();
1465 BasicBlock thisPred = prevBasicBlockInCodeOrder();
1466 BasicBlock thisSucc = nextBasicBlockInCodeOrder();
1467 if (thisPred != null) {
1468 thisPred.killFallThrough();
1469 ir.cfg.breakCodeOrder(thisPred, this);
1470 }
1471 if (thisSucc != null) ir.cfg.breakCodeOrder(this, thisSucc);
1472
1473 if (thisPred != null && thisSucc != null) {
1474 ir.cfg.linkInCodeOrder(thisPred, thisSucc);
1475 }
1476
1477 thisPred = pred;
1478 thisSucc = pred.nextBasicBlockInCodeOrder();
1479
1480 if (thisSucc != null) {
1481 ir.cfg.breakCodeOrder(thisPred, thisSucc);
1482 ir.cfg.linkInCodeOrder(this, thisSucc);
1483 }
1484 ir.cfg.linkInCodeOrder(thisPred, this);
1485 }
1486
1487 /**
1488 * Change all branches from this to b to branches that go to bCopy instead.
1489 * This method also handles this.fallThrough, so `this' should still be in
1490 * the code order when this method is called.
1491 *
1492 * WARNING: Use this method with caution. See comment on
1493 * BasicBlock.recomputeNormalOut()
1494 *
1495 * @param b the original target
1496 * @param bCopy the future target
1497 */
1498 public final void redirectOuts(BasicBlock b, BasicBlock bCopy, IR ir) {
1499 BranchOperand copyTarget = bCopy.makeJumpTarget();
1500 BranchOperand bTarget = b.makeJumpTarget();
1501 // 1. update the branch instructions in 'this' to point to bCopy
1502 for (InstructionEnumeration ie = enumerateBranchInstructions(); ie.hasMoreElements();) {
1503 Instruction s = ie.next();
1504 s.replaceSimilarOperands(bTarget, copyTarget);
1505 }
1506
1507 // 2. if this falls through to b, make it jump to bCopy
1508 if (getFallThroughBlock() == b) {
1509 Instruction g = Goto.create(GOTO, copyTarget); //no copy needed.
1510 appendInstruction(g);
1511 }
1512
1513 // 3. recompute normal control flow edges.
1514 recomputeNormalOut(ir);
1515 }
1516
1517 /*
1518 * TODO: work on eliminating this method by converting callers to
1519 * three argument form
1520 */
1521 public final BasicBlock createSubBlock(int bc, IR ir) {
1522 return createSubBlock(bc, ir, 1f);
1523 }
1524
1525 /**
1526 * Creates a new basic block that inherits its exception handling,
1527 * etc from 'this'. This method is intended to be used in conjunction
1528 * with splitNodeAt when splitting instructions in one original block
1529 * into a sequence of sublocks
1530 *
1531 * @param bc the bytecode index to start the block
1532 * @param ir the containing IR
1533 * @param wf the fraction of this's execution frequency that should be
1534 * inherited by the new block. In the range [0.0, 1.0]
1535 * @return the new empty BBlock
1536 */
1537 public final BasicBlock createSubBlock(int bc, IR ir, float wf) {
1538 // For now, give the basic block the same inline context as the
1539 // original block.
1540 // TODO: This won't always work. (In fact, in the presence of inlining
1541 // it will be wrong quite often). --dave
1542 // We really have to pass the position in if we except this to work.
1543 BasicBlock temp = new BasicBlock(bc, firstInstruction().position, ir.cfg);
1544
1545 // Conservatively transfer all exception handling behavior of the
1546 // parent block (this) to the new child block (temp)
1547 temp.exceptionHandlers = exceptionHandlers;
1548 temp.setCanThrowExceptions(canThrowExceptions());
1549 temp.setMayThrowUncaughtException(mayThrowUncaughtException());
1550 temp.setUnsafeToSchedule(isUnsafeToSchedule());
1551 temp.setExecutionFrequency(getExecutionFrequency() * wf);
1552 for (BasicBlockEnumeration e = getOut(); e.hasMoreElements();) {
1553 BasicBlock out = e.next();
1554 if (out.isExceptionHandlerBasicBlock()) {
1555 temp.insertOut(out);
1556 }
1557 }
1558
1559 return temp;
1560 }
1561
1562 /**
1563 * If this block has a single non-Exception successor in the CFG
1564 * then we may be able to merge the two blocks together.
1565 * In order for this to be legal, it must be the case that:
1566 * (1) The successor block has no other in edges than the one from this.
1567 * (2) Both blocks have the same exception handlers.
1568 * Merging the blocks is always desirable when
1569 * (a) the successor block is the next block in code order
1570 * (b) the successor block is not the next block in the code order,
1571 * but ends in an unconditional branch (ie it doesn't have a
1572 * fallthrough successor in the code order that we could be screwing up).
1573 *
1574 * @param ir the IR object containing the basic block to be merged
1575 * @return <code>true</code> if the block was merged or
1576 * <code>false</code> otherwise
1577 */
1578 public final boolean mergeFallThrough(IR ir) {
1579 if (getNumberOfNormalOut() != 1) return false; // this has other out edges.
1580 BasicBlock succBB = (BasicBlock) next;
1581 if (succBB == null || !pointsOut(succBB)) {
1582 // get the successor from the CFG rather than the code order (case (b))
1583 succBB = getNormalOut().next();
1584 if (succBB.isExit()) return false;
1585 if (succBB.lastRealInstruction() == null || !succBB.lastRealInstruction().isUnconditionalBranch()) {
1586 return false;
1587 }
1588 }
1589
1590 if (succBB.isExceptionHandlerBasicBlock()) return false; // must preserve special exception info!
1591 if (succBB.getNumberOfIn() != 1) return false; // succBB has other in edges
1592
1593 // Different in scope Exception handlers?
1594 if (!isExceptionHandlerEquivalent(succBB)) return false;
1595
1596 // There may be a redundant goto at the end of this -- remove it.
1597 // There may also be redundant conditional branches (also to succBB).
1598 // Remove them as well.
1599 // Branch instructions to blocks other than succBB are errors.
1600 if (VM.VerifyAssertions) {
1601 for (InstructionEnumeration e = enumerateBranchInstructions(); e.hasMoreElements();) {
1602 BasicBlockEnumeration targets = e.next().getBranchTargets();
1603 while (targets.hasMoreElements()) {
1604 BasicBlock target = targets.next();
1605 VM._assert(target == succBB);
1606 }
1607 }
1608 }
1609 Instruction s = this.end.getPrev();
1610 while (s.isBranch()) {
1611 s = s.remove();
1612 }
1613
1614 // splice together the instruction lists of the two basic blocks into
1615 // a single list and update this's BBEND info
1616 this.end.getPrev().linkWithNext(succBB.start.getNext());
1617 succBB.end.getPrev().linkWithNext(this.end);
1618
1619 // Add succBB's CFG sucessors to this's CFG out edges
1620 for (OutEdgeEnum e = succBB.getOut(); e.hasMoreElements();) {
1621 BasicBlock out = e.next();
1622 this.insertOut(out);
1623 }
1624
1625 // Blow away sucBB.
1626 ir.cfg.removeFromCFGAndCodeOrder(succBB);
1627
1628 // Merge misc BB state
1629 setCanThrowExceptions(canThrowExceptions() || succBB.canThrowExceptions());
1630 setMayThrowUncaughtException(mayThrowUncaughtException() || succBB.mayThrowUncaughtException());
1631 setUnsafeToSchedule(isUnsafeToSchedule() || succBB.isUnsafeToSchedule());
1632 if (succBB.getInfrequent()) setInfrequent();
1633
1634 return true;
1635 }
1636
1637 /**
1638 * Convert a block in the FCFG into the equivalent set of
1639 * CFG blocks by splitting the original block into sub-blocks
1640 * at each PEI that reaches at least one exception handelr.
1641 * NOTE: This is sufficient for intraprocedural analysis, since the
1642 * only program point at which the "wrong" answers will
1643 * be computed is the exit node, but is not good enough for
1644 * interprocedural analyses. To do an interprocedural analysis,
1645 * either the analysis needs to deal with the FCFG or all nodes
1646 * that modify globally visible state must be unfactored.
1647 * @see IR#unfactor
1648 * @param ir the containing IR object
1649 */
1650 final void unfactor(IR ir) {
1651 for (InstructionEnumeration e = forwardRealInstrEnumerator(); e.hasMoreElements();) {
1652 Instruction s = e.next();
1653 BasicBlockEnumeration expOuts = getApplicableExceptionalOut(s);
1654 if (expOuts.hasMoreElements() && e.hasMoreElements()) {
1655 BasicBlock next = splitNodeWithLinksAt(s, ir);
1656 next.unfactor(ir);
1657 pruneExceptionalOut(ir);
1658 return;
1659 }
1660 }
1661 }
1662
1663 /**
1664 * Prune away exceptional out edges that are not reachable given this
1665 * block's instructions.
1666 */
1667 final void pruneExceptionalOut(IR ir) {
1668 int n = getNumberOfExceptionalOut();
1669 if (n > 0) {
1670 ComputedBBEnum handlers = new ComputedBBEnum(n);
1671 InstructionEnumeration e = forwardRealInstrEnumerator();
1672 while (e.hasMoreElements()) {
1673 Instruction x = e.next();
1674 BasicBlockEnumeration bbs = getApplicableExceptionalOut(x);
1675 while (bbs.hasMoreElements()) {
1676 BasicBlock bb = bbs.next();
1677 handlers.addPossiblyDuplicateElement(bb);
1678 }
1679 }
1680
1681 deleteExceptionalOut();
1682
1683 for (int i = 0; handlers.hasMoreElements(); i++) {
1684 ExceptionHandlerBasicBlock b = (ExceptionHandlerBasicBlock) handlers.next();
1685 insertOut(b);
1686 }
1687 }
1688
1689 // Since any edge to an exception handler is an "exceptional" edge,
1690 // the previous procedure has thrown away any "normal" CFG edges to
1691 // exception handlers. So, recompute normal edges to recover them.
1692 recomputeNormalOut(ir);
1693
1694 }
1695
1696 // helper function for unfactor
1697 private void deleteExceptionalOut() {
1698 for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.getNextOut()) {
1699 BasicBlock out = (BasicBlock) e.toNode();
1700 if (out.isExceptionHandlerBasicBlock()) {
1701 deleteOut(e);
1702 }
1703 }
1704 }
1705
1706 /**
1707 * An enumeration of the FCFG in nodes.
1708 *
1709 * @return an enumeration of the in nodes
1710 */
1711 public final BasicBlockEnumeration getIn() {
1712 return new InEdgeEnum(this);
1713 }
1714
1715 /**
1716 * An enumeration of the FCFG in nodes.
1717 *
1718 * @return an enumeration of the in nodes
1719 */
1720 public final BasicBlockEnumeration getInNodes() {
1721 return new InEdgeEnum(this);
1722 }
1723
1724 /**
1725 * Is there an in edge from the given basic block?
1726 *
1727 * @param bb basic block in question
1728 * @return <code>true</code> if an in edge exists from bb
1729 * <code>false</code> otherwise
1730 */
1731 public final boolean isIn(BasicBlock bb) {
1732 InEdgeEnum iee = new InEdgeEnum(this);
1733 while (iee.hasMoreElements()) {
1734 if (iee.next() == bb) {
1735 return true;
1736 }
1737 }
1738 return false;
1739 }
1740
1741 /**
1742 * An enumeration of the FCFG out nodes.
1743 *
1744 * @return an enumeration of the out nodes
1745 */
1746 public final OutEdgeEnum getOut() {
1747 return new OutEdgeEnum(this);
1748 }
1749
1750 /**
1751 * An enumeration of the FCFG out nodes.
1752 *
1753 * @return an enumeration of the out nodes
1754 */
1755 public final OutEdgeEnum getOutNodes() {
1756 return new OutEdgeEnum(this);
1757 }
1758
1759 /**
1760 * Is there an out edge to the given basic block?
1761 *
1762 * @param bb basic block in question
1763 * @return <code>true</code> if an out edge exists to bb
1764 * <code>false</code> otherwise
1765 */
1766 public final boolean isOut(BasicBlock bb) {
1767 OutEdgeEnum oee = new OutEdgeEnum(this);
1768 while (oee.hasMoreElements()) {
1769 if (oee.next() == bb) {
1770 return true;
1771 }
1772 }
1773 return false;
1774 }
1775
1776 /**
1777 * An enumeration of the 'normal' (not reached via exceptional control flow)
1778 * out nodes of the block.
1779 *
1780 * @return an enumeration of the out nodes that are not
1781 * reachable via as a result of exceptional control flow
1782 */
1783 public final BasicBlockEnumeration getNormalOut() {
1784 return new NormalOutEdgeEnum(this);
1785 }
1786
1787 /**
1788 * Is there a 'normal' out edge to the given basic block?
1789 *
1790 * @param bb basic block in question
1791 * @return <code>true</code> if a normal out edge exists to bb
1792 * <code>false</code> otherwise
1793 */
1794 public final boolean isNormalOut(BasicBlock bb) {
1795 NormalOutEdgeEnum noee = new NormalOutEdgeEnum(this);
1796 while (noee.hasMoreElements()) {
1797 if (noee.next() == bb) {
1798 return true;
1799 }
1800 }
1801 return false;
1802 }
1803
1804 /**
1805 * An enumeration of the 'exceptional' (reached via exceptional control flow)
1806 * out nodes of the block.
1807 *
1808 * @return an enumeration of the out nodes that are
1809 * reachable via as a result of exceptional control flow
1810 */
1811 public final BasicBlockEnumeration getExceptionalOut() {
1812 if (canThrowExceptions()) {
1813 return new ExceptionOutEdgeEnum(this);
1814 } else {
1815 return BasicBlockEnumeration.Empty;
1816 }
1817 }
1818
1819 /**
1820 * Is there an 'exceptional' out edge to the given basic block?
1821 *
1822 * @param bb basic block in question
1823 * @return <code>true</code> if an exceptional out edge exists to bb
1824 * <code>false</code> otherwise
1825 */
1826 public final boolean isExceptionalOut(BasicBlock bb) {
1827 if (!canThrowExceptions()) return false;
1828 ExceptionOutEdgeEnum eoee = new ExceptionOutEdgeEnum(this);
1829 while (eoee.hasMoreElements()) {
1830 if (eoee.next() == bb) {
1831 return true;
1832 }
1833 }
1834 return false;
1835 }
1836
1837 /**
1838 * Get the number of out nodes that are to "normal" basic blocks
1839 *
1840 * @return the number of out nodes that are not the start of
1841 * exception handlers
1842 */
1843 public final int getNumberOfNormalOut() {
1844 int count = 0;
1845 boolean countValid = true;
1846 for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.getNextOut()) {
1847 BasicBlock bb = (BasicBlock) e.toNode();
1848 if (!bb.isExceptionHandlerBasicBlock()) {
1849 count++;
1850 } else if (bb.isExceptionHandlerWithNormalIn()) {
1851 countValid = false;
1852 break;
1853 }
1854 }
1855 if (countValid) {
1856 return count;
1857 } else {
1858 HashSet<BasicBlock> setOfTargets = new HashSet<BasicBlock>();
1859 for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.getNextOut()) {
1860 BasicBlock bb = (BasicBlock) e.toNode();
1861 if (!bb.isExceptionHandlerBasicBlock()) {
1862 setOfTargets.add(bb);
1863 }
1864 }
1865 for (InstructionEnumeration e = enumerateBranchInstructions(); e.hasMoreElements();) {
1866 BasicBlockEnumeration targets = e.next().getBranchTargets();
1867 while (targets.hasMoreElements()) {
1868 setOfTargets.add(targets.nextElement());
1869 }
1870 }
1871 return setOfTargets.size();
1872 }
1873 }
1874
1875 /**
1876 * Get the number of out nodes that are to exception handler basic blocks
1877 *
1878 * @return the number of out nodes that are exception handlers
1879 */
1880 public final int getNumberOfExceptionalOut() {
1881 int count = 0;
1882 if (canThrowExceptions()) {
1883 for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.getNextOut()) {
1884 BasicBlock bb = (BasicBlock) e.toNode();
1885 if (bb.isExceptionHandlerBasicBlock()) {
1886 count++;
1887 }
1888 }
1889 }
1890 return count;
1891 }
1892
1893 /**
1894 * Are there exceptinal handlers that are reachable via
1895 * exceptional control flow from this basic block?
1896 *
1897 * @return <code>true</code> if an exceptional handler
1898 * is reachable from this block or
1899 * <code>false</code> otherwise.
1900 */
1901 public final boolean hasReachableExceptionHandlers() {
1902 if (canThrowExceptions()) {
1903 for (SpaceEffGraphEdge e = _outEdgeStart; e != null; e = e.getNextOut()) {
1904 BasicBlock bb = (BasicBlock) e.toNode();
1905 if (bb.isExceptionHandlerBasicBlock()) {
1906 return true;
1907 }
1908 }
1909 }
1910 return false;
1911 }
1912
1913 /*
1914 * Primitive BasicBlock enumerators.
1915 * We don't really intend clients to directly instantiate these, but rather to
1916 * call the appropriate utility function that creates/initializes one of these
1917 */
1918 abstract static class BBEnum implements BasicBlockEnumeration {
1919 protected BasicBlock current;
1920
1921 public final boolean hasMoreElements() { return current != null; }
1922
1923 public final BasicBlock nextElement() { return next(); }
1924
1925 public final BasicBlock next() {
1926 if (current == null) fail();
1927 BasicBlock value = current;
1928 current = advance();
1929 return value;
1930 }
1931
1932 protected abstract BasicBlock advance();
1933
1934 @NoInline
1935 protected static void fail() throws java.util.NoSuchElementException {
1936 throw new java.util.NoSuchElementException("Basic Block Enumeration");
1937 }
1938 }
1939
1940 // Arbitrary constructed enumeration of some set of basic blocks
1941 static final class ComputedBBEnum implements BasicBlockEnumeration {
1942 private BasicBlock[] blocks;
1943 private int numBlocks;
1944 private int current;
1945
1946 ComputedBBEnum(int maxBlocks) {
1947 blocks = new BasicBlock[maxBlocks];
1948 }
1949
1950 void addElement(BasicBlock b) {
1951 blocks[numBlocks++] = b;
1952 }
1953
1954 void addPossiblyDuplicateElement(BasicBlock b) {
1955 for (int i = 0; i < numBlocks; i++) {
1956 if (blocks[i] == b) return;
1957 }
1958 addElement(b);
1959 }
1960
1961 public int totalCount() { return numBlocks; }
1962
1963 public boolean hasMoreElements() { return current < numBlocks; }
1964
1965 public BasicBlock nextElement() { return next(); }
1966
1967 public BasicBlock next() {
1968 if (current >= numBlocks) fail();
1969 return blocks[current++];
1970 }
1971
1972 @NoInline
1973 static void fail() throws java.util.NoSuchElementException {
1974 throw new java.util.NoSuchElementException("Basic Block Enumeration");
1975 }
1976 }
1977
1978 // this class needs to be implemented efficiently, as it is used heavily.
1979 static final class InEdgeEnum implements BasicBlockEnumeration {
1980 private SpaceEffGraphEdge _edge;
1981
1982 public InEdgeEnum(SpaceEffGraphNode n) { _edge = n.firstInEdge(); }
1983
1984 public boolean hasMoreElements() { return _edge != null; }
1985
1986 public BasicBlock nextElement() { return next(); }
1987
1988 public BasicBlock next() {
1989 SpaceEffGraphEdge e = _edge;
1990 _edge = e.getNextIn();
1991 return (BasicBlock) e.fromNode();
1992 }
1993 }
1994
1995 // this class needs to be implemented efficiently, as it is used heavily.
1996 static final class OutEdgeEnum implements BasicBlockEnumeration {
1997 private SpaceEffGraphEdge _edge;
1998
1999 public OutEdgeEnum(SpaceEffGraphNode n) { _edge = n.firstOutEdge(); }
2000
2001 public boolean hasMoreElements() { return _edge != null; }
2002
2003 public BasicBlock nextElement() { return next(); }
2004
2005 public BasicBlock next() {
2006 SpaceEffGraphEdge e = _edge;
2007 _edge = e.getNextOut();
2008 return (BasicBlock) e.toNode();
2009 }
2010 }
2011
2012 // Enumerate the non-handler blocks in the edge set
2013 final class NormalOutEdgeEnum extends BBEnum {
2014 private SpaceEffGraphEdge _edge;
2015
2016 NormalOutEdgeEnum(SpaceEffGraphNode n) {
2017 _edge = n.firstOutEdge();
2018 current = advance();
2019 }
2020
2021 protected BasicBlock advance() {
2022 while (_edge != null) {
2023 BasicBlock cand = (BasicBlock) _edge.toNode();
2024 _edge = _edge.getNextOut();
2025 if (!cand.isExceptionHandlerBasicBlock()) {
2026 return cand;
2027 } else if (cand.isExceptionHandlerWithNormalIn()) {
2028 for (InstructionEnumeration e = enumerateBranchInstructions(); e.hasMoreElements();) {
2029 BasicBlockEnumeration targets = e.next().getBranchTargets();
2030 while (targets.hasMoreElements()) {
2031 if (cand == targets.nextElement()) {
2032 return cand;
2033 }
2034 }
2035 }
2036 }
2037 }
2038 return null;
2039 }
2040 }
2041
2042 // Enumerate the non-handler blocks in the edge set
2043 static final class ExceptionOutEdgeEnum extends BBEnum {
2044 private SpaceEffGraphEdge _edge;
2045
2046 ExceptionOutEdgeEnum(SpaceEffGraphNode n) {
2047 _edge = n.firstOutEdge();
2048 current = advance();
2049 }
2050
2051 protected BasicBlock advance() {
2052 while (_edge != null) {
2053 BasicBlock cand = (BasicBlock) _edge.toNode();
2054 _edge = _edge.getNextOut();
2055 if (cand.isExceptionHandlerBasicBlock()) {
2056 return cand;
2057 }
2058 }
2059 return null;
2060 }
2061 }
2062
2063 public void discardInstructions() {
2064 start.getNext().setPrev(null);
2065 end.getPrev().setNext(null);
2066 start.linkWithNext(end);
2067 }
2068 }