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