SsaBasicBlock.java revision 2ad60cfc28e14ee8f0bb038720836a4696c478ad
1/* 2 * Copyright (C) 2007 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.android.dx.ssa; 18 19import com.android.dx.rop.code.BasicBlock; 20import com.android.dx.rop.code.BasicBlockList; 21import com.android.dx.rop.code.InsnList; 22import com.android.dx.rop.code.PlainInsn; 23import com.android.dx.rop.code.RegisterSpec; 24import com.android.dx.rop.code.RegisterSpecList; 25import com.android.dx.rop.code.RopMethod; 26import com.android.dx.rop.code.Rops; 27import com.android.dx.rop.code.SourcePosition; 28import com.android.dx.rop.code.Insn; 29import com.android.dx.rop.code.Rop; 30import com.android.dx.util.IntList; 31import com.android.dx.util.Hex; 32import com.android.dx.util.IntSet; 33import com.android.dx.util.BitIntSet; 34import com.android.dx.util.ListIntSet; 35 36import java.util.ArrayList; 37import java.util.BitSet; 38import java.util.Collections; 39import java.util.List; 40 41/** 42 * An SSA representation of a basic block. 43 */ 44public final class SsaBasicBlock { 45 46 /** non-null; insn list associated with this instance */ 47 private ArrayList<SsaInsn> insns; 48 /** non-null; predecessor set (by block list index) */ 49 private BitSet predecessors; 50 /** non-null; successor set (by block list index) */ 51 private BitSet successors; 52 /** 53 * non-null; ordered successor list 54 * (same block may be listed more than once) 55 */ 56 private IntList successorList; 57 /** block list index of primary successor, or -1 for no primary successor */ 58 private int primarySuccessor = -1; 59 /** label of block in rop form */ 60 private int ropLabel; 61 /** non-null; method we belong to */ 62 private SsaMethod parent; 63 /** our index into parent.getBlock() */ 64 private int index; 65 /** list of dom children */ 66 private final ArrayList<SsaBasicBlock> domChildren; 67 68 /** 69 * The number of moves added to the end of the block during the 70 * phi-removal process. Retained for subsequent move scheduling. 71 */ 72 private int movesFromPhisAtEnd = 0; 73 /** 74 * The number of moves added to the beginning of the block during the 75 * phi-removal process. Retained for subsequent move scheduling. 76 */ 77 private int movesFromPhisAtBeginning = 0; 78 79 /** null-ok; indexed by reg: the regs that are live-in at this block */ 80 private IntSet liveIn; 81 /** null-ok; indexed by reg: the regs that are live-out at this block */ 82 private IntSet liveOut; 83 84 /** 85 * Create a new empty basic block 86 * @param basicBlockIndex index this block will have 87 * @param ropLabel original rop-form label 88 * @param parent method of this block 89 */ 90 public SsaBasicBlock(final int basicBlockIndex, final int ropLabel, 91 final SsaMethod parent) { 92 this.parent = parent; 93 this.index = basicBlockIndex; 94 this.insns = new ArrayList<SsaInsn>(); 95 this.ropLabel = ropLabel; 96 97 this.predecessors = new BitSet(parent.getBlocks().size()); 98 this.successors = new BitSet(parent.getBlocks().size()); 99 this.successorList = new IntList(); 100 101 domChildren = new ArrayList<SsaBasicBlock>(); 102 } 103 104 /** 105 * Creates a new SSA basic block from a ROP form basic block. 106 * 107 * @param rmeth original method 108 * @param basicBlockIndex index this block will have 109 * @param parent method of this block 110 * predecessor set will be updated. 111 * @return new instance 112 */ 113 public static SsaBasicBlock newFromRop(RopMethod rmeth, 114 int basicBlockIndex, final SsaMethod parent) { 115 116 BasicBlockList ropBlocks; 117 SsaBasicBlock result; 118 InsnList ropInsns; 119 BasicBlock bb; 120 121 ropBlocks = rmeth.getBlocks(); 122 bb = ropBlocks.get(basicBlockIndex); 123 124 result = new SsaBasicBlock(basicBlockIndex, bb.getLabel(), parent); 125 126 ropInsns = bb.getInsns(); 127 128 result.insns.ensureCapacity(ropInsns.size()); 129 for (int i = 0, sz = ropInsns.size() ; i < sz ; i++) { 130 result.insns.add(new NormalSsaInsn (ropInsns.get(i), result)); 131 } 132 133 result.predecessors = SsaMethod.bitSetFromLabelList( 134 ropBlocks, 135 rmeth.labelToPredecessors(bb.getLabel())); 136 137 result.successors 138 = SsaMethod.bitSetFromLabelList(ropBlocks, bb.getSuccessors()); 139 140 result.successorList 141 = SsaMethod.indexListFromLabelList(ropBlocks, 142 bb.getSuccessors()); 143 144 145 if (result.successorList.size() != 0) { 146 int primarySuccessor = bb.getPrimarySuccessor(); 147 148 result.primarySuccessor = (primarySuccessor < 0) 149 ? -1 : ropBlocks.indexOfLabel(primarySuccessor); 150 } 151 152 return result; 153 } 154 155 /** 156 * Adds a basic block as a dom child for this block. Used when constructing 157 * the dom tree. 158 * 159 * @param child non-null; new dom child 160 */ 161 void addDomChild(SsaBasicBlock child) { 162 domChildren.add(child); 163 } 164 165 /** 166 * Gets the dom children for this node. Don't modify this list. 167 * 168 * @return non-null; list of dom children 169 */ 170 ArrayList<SsaBasicBlock> getDomChildren() { 171 return domChildren; 172 } 173 174 /** 175 * Adds a phi insn to the beginning of this block. The result type of 176 * the phi will be set to void, to indicate that it's currently unknown. 177 * 178 * @param reg >=0 result reg 179 */ 180 void addPhiInsnForReg(int reg) { 181 insns.add(0, new PhiInsn(reg, this)); 182 } 183 184 /** 185 * Adds a phi insn to the beginning of this block. This is to be used 186 * when the result type or local-association can be determined at phi 187 * insert time. 188 * 189 * @param resultSpec non-null; reg 190 */ 191 void addPhiInsnForReg(RegisterSpec resultSpec) { 192 insns.add(0, new PhiInsn(resultSpec, this)); 193 } 194 195 /** 196 * Adds an insn to the head of this basic block, just after any phi 197 * insns. 198 * 199 * @param insn non-null; rop-form insn to add 200 */ 201 void addInsnToHead(Insn insn) { 202 SsaInsn newInsn = SsaInsn.makeFromRop(insn, this); 203 insns.add(getCountPhiInsns(), newInsn); 204 parent.onInsnAdded(newInsn); 205 } 206 207 /** 208 * Replaces the last insn in this block. The provided insn must have 209 * some branchingness. 210 * 211 * @param insn non-null; rop-form insn to add, which must branch. 212 */ 213 void replaceLastInsn(Insn insn) { 214 if (insn.getOpcode().getBranchingness() == Rop.BRANCH_NONE) { 215 throw new IllegalArgumentException("last insn must branch"); 216 } 217 218 SsaInsn oldInsn = insns.get(insns.size() - 1); 219 SsaInsn newInsn = SsaInsn.makeFromRop(insn, this); 220 221 insns.set(insns.size() - 1, newInsn); 222 223 parent.onInsnRemoved(oldInsn); 224 parent.onInsnAdded(newInsn); 225 } 226 227 /** 228 * Visits each phi insn 229 * @param v callback 230 */ 231 public void forEachPhiInsn(PhiInsn.Visitor v) { 232 233 int sz = insns.size(); 234 for (int i = 0; i < sz; i++) { 235 SsaInsn insn = insns.get(i); 236 if (insn instanceof PhiInsn) { 237 v.visitPhiInsn((PhiInsn) insn); 238 } else { 239 /* 240 * Presently we assume PhiInsn's are in a continuous 241 * block at the top of the list 242 */ 243 break; 244 } 245 } 246 } 247 248 /** 249 * Deletes all phi insns. Do this after adding appropriate move insns. 250 */ 251 public void removeAllPhiInsns() { 252 /* 253 * Presently we assume PhiInsn's are in a continuous 254 * block at the top of the list 255 */ 256 257 insns.subList(0, getCountPhiInsns()).clear(); 258 } 259 260 /** 261 * Gets the number of phi insns at the top of this basic block. 262 * @return count of phi insns 263 */ 264 private int getCountPhiInsns() { 265 int countPhiInsns; 266 267 int sz = insns.size(); 268 for (countPhiInsns = 0; countPhiInsns < sz; countPhiInsns++) { 269 SsaInsn insn = insns.get(countPhiInsns); 270 if (!(insn instanceof PhiInsn)) { 271 break; 272 } 273 } 274 275 return countPhiInsns; 276 } 277 278 /** 279 * @return non-null;the (mutable) instruction list for this block, 280 * with phi insns at the beginning. 281 */ 282 public ArrayList<SsaInsn> getInsns() { 283 return insns; 284 } 285 286 /** 287 * @return non-null; the (mutable) list of phi insns for this block 288 */ 289 public List<SsaInsn> getPhiInsns() { 290 return insns.subList(0, getCountPhiInsns()); 291 } 292 293 /** 294 * @return the block index of this block 295 */ 296 public int getIndex() { 297 return index; 298 } 299 300 /** 301 * @return the label of this block in rop form 302 */ 303 public int getRopLabel() { 304 return ropLabel; 305 } 306 307 /** 308 * @return the label of this block in rop form as a hex string 309 */ 310 public String getRopLabelString() { 311 return Hex.u2(ropLabel); 312 } 313 314 /** 315 * @return non-null;predecessors set, indexed by block index 316 */ 317 public BitSet getPredecessors() { 318 return predecessors; 319 } 320 321 /** 322 * @return non-null;successors set, indexed by block index 323 */ 324 public BitSet getSuccessors() { 325 return successors; 326 } 327 328 /** 329 * @return non-null;ordered successor list, containing block indicies 330 */ 331 public IntList getSuccessorList() { 332 return successorList; 333 } 334 335 /** 336 * @return >= -1; block index of primary successor or -1 if no 337 * primary successor. 338 */ 339 public int getPrimarySuccessorIndex() { 340 return primarySuccessor; 341 } 342 343 /** 344 * @return rop label of primary successor 345 */ 346 public int getPrimarySuccessorRopLabel() { 347 return parent.blockIndexToRopLabel(primarySuccessor); 348 } 349 350 /** 351 * @return null-ok; the primary successor block or null if there is none. 352 */ 353 public SsaBasicBlock getPrimarySuccessor() { 354 if (primarySuccessor < 0) { 355 return null; 356 } else { 357 return parent.getBlocks().get(primarySuccessor); 358 } 359 } 360 361 /** 362 * @return successor list of rop labels 363 */ 364 public IntList getRopLabelSuccessorList() { 365 IntList result = new IntList(successorList.size()); 366 367 int sz = successorList.size(); 368 369 for (int i = 0; i < sz; i++) { 370 result.add(parent.blockIndexToRopLabel(successorList.get(i))); 371 } 372 return result; 373 } 374 375 /** 376 * @return non-null; method that contains this block 377 */ 378 public SsaMethod getParent() { 379 return parent; 380 } 381 382 /** 383 * Inserts a new empty GOTO block as a predecessor to this block. 384 * All previous predecessors will be predecessors to the new block. 385 * 386 * @return non-null; an appropriately-constructed instance 387 */ 388 public SsaBasicBlock insertNewPredecessor() { 389 SsaBasicBlock newPred = parent.makeNewGotoBlock(); 390 391 // Update the new block 392 newPred.predecessors = predecessors; 393 newPred.successors.set(index) ; 394 newPred.successorList.add(index); 395 newPred.primarySuccessor = index; 396 397 398 // Update us 399 predecessors = new BitSet(parent.getBlocks().size()); 400 predecessors.set(newPred.index); 401 402 // Update our (soon-to-be) old predecessors 403 for (int i = newPred.predecessors.nextSetBit(0); i >= 0; 404 i = newPred.predecessors.nextSetBit(i + 1)) { 405 406 SsaBasicBlock predBlock = parent.getBlocks().get(i); 407 408 predBlock.replaceSuccessor(index, newPred.index); 409 } 410 411 return newPred; 412 } 413 414 /** 415 * Constructs and inserts a new empty GOTO block <code>Z</code> between 416 * this block (<code>A</code>) and a current successor block 417 * (<code>B</code>). The new block will replace B as A's successor and 418 * A as B's predecessor. A and B will no longer be directly connected. 419 * If B is listed as a successor multiple times, all references 420 * are replaced. 421 * 422 * @param other current successor (B) 423 * @return non-null; an appropriately-constructed instance 424 */ 425 public SsaBasicBlock insertNewSuccessor(SsaBasicBlock other) { 426 SsaBasicBlock newSucc = parent.makeNewGotoBlock(); 427 428 if (!successors.get(other.index)) { 429 throw new RuntimeException("Block " + other.getRopLabelString() 430 + " not successor of " + getRopLabelString()); 431 } 432 433 // Update the new block 434 newSucc.predecessors.set(this.index); 435 newSucc.successors.set(other.index) ; 436 newSucc.successorList.add(other.index); 437 newSucc.primarySuccessor = other.index; 438 439 // Update us 440 for (int i = successorList.size() - 1 ; i >= 0; i--) { 441 if(successorList.get(i) == other.index) { 442 successorList.set(i, newSucc.index); 443 } 444 } 445 446 if (primarySuccessor == other.index) { 447 primarySuccessor = newSucc.index; 448 } 449 successors.clear(other.index); 450 successors.set(newSucc.index); 451 452 // Update "other" 453 other.predecessors.set(newSucc.index); 454 other.predecessors.set(index, successors.get(other.index)); 455 456 return newSucc; 457 } 458 459 /** 460 * Replace an old successor with a new successor. 461 * Throws RuntimeException if oldIndex was not a successor. 462 * @param oldIndex index of old successor block 463 * @param newIndex index of new successor block. 464 */ 465 public void replaceSuccessor(int oldIndex, int newIndex) { 466 if (oldIndex == newIndex) { 467 return; 468 } 469 470 // Update us 471 successors.set(newIndex); 472 473 if (primarySuccessor == oldIndex) { 474 primarySuccessor = newIndex; 475 } 476 477 for (int i = successorList.size() - 1 ; i >= 0; i--) { 478 if(successorList.get(i) == oldIndex) { 479 successorList.set(i, newIndex); 480 } 481 } 482 483 successors.clear(oldIndex); 484 485 // Update new successor 486 parent.getBlocks().get(newIndex).predecessors.set(index); 487 488 // Update old successor 489 parent.getBlocks().get(oldIndex).predecessors.clear(index); 490 } 491 492 493 /** 494 * Attaches block to an exit block if necessary. If this block 495 * is not an exit predecessor or is the exit block, this block does 496 * nothing. For use by {@link com.android.dx.ssa.SsaMethod#makeExitBlock} 497 * 498 * @param exitBlock non-null; exit block 499 */ 500 public void exitBlockFixup(SsaBasicBlock exitBlock) { 501 if (this == exitBlock) { 502 return; 503 } 504 505 if (successorList.size() == 0) { 506 /* 507 * This is an exit predecessor. 508 * Set the successor to the exit block 509 */ 510 successors.set(exitBlock.index); 511 successorList.add(exitBlock.index); 512 primarySuccessor = exitBlock.index; 513 exitBlock.predecessors.set(this.index); 514 } 515 } 516 517 /** 518 * Adds a move instruction to the end of this basic block, just 519 * before the last instruction. If the result of the final instruction 520 * is the source in question, then the move is placed at the beginning of 521 * the primary successor block. This is for unversioned registers. 522 * @param result move destination 523 * @param source move source 524 */ 525 public void addMoveToEnd(RegisterSpec result, RegisterSpec source) { 526 527 if (result.getReg() == source.getReg()) { 528 // Sometimes we end up with no-op moves. Ignore them here. 529 return; 530 } 531 532 /* 533 * The last Insn has to be a normal SSA insn: a phi can't branch 534 * or return or cause an exception, etc. 535 */ 536 NormalSsaInsn lastInsn; 537 lastInsn = (NormalSsaInsn)insns.get(insns.size()-1); 538 539 if (lastInsn.getResult() != null || lastInsn.getSources().size() > 0) { 540 /* 541 * The final insn in this block has a source or result register, 542 * and the moves we may need to place and schedule may interfere. 543 * We need to insert this instruction at the 544 * beginning of the primary successor block instead. We know 545 * this is safe, because when we edge-split earlier, we ensured 546 * that each successor has only us as a predecessor. 547 */ 548 549 for (int i = successors.nextSetBit(0) 550 ; i >= 0 551 ; i = successors.nextSetBit(i + 1)) { 552 553 SsaBasicBlock succ; 554 555 succ = parent.getBlocks().get(i); 556 succ.addMoveToBeginning(result, source); 557 } 558 } else { 559 /* 560 * We can safely add a move to the end of the block 561 * just before the last instruction because 562 * the final insn does not assign to anything. 563 */ 564 565 RegisterSpecList sources; 566 sources = RegisterSpecList.make(source); 567 568 NormalSsaInsn toAdd; 569 570 toAdd = new NormalSsaInsn( 571 new PlainInsn(Rops.opMove(result.getType()), 572 SourcePosition.NO_INFO, result, sources), this); 573 574 insns.add(insns.size() - 1, toAdd); 575 576 movesFromPhisAtEnd++; 577 } 578 } 579 580 /** 581 * Add a move instruction after the phi insn block. 582 * @param result move destination 583 * @param source move source 584 */ 585 public void addMoveToBeginning (RegisterSpec result, RegisterSpec source) { 586 587 if (result.getReg() == source.getReg()) { 588 // Sometimes we end up with no-op moves. Ignore them here. 589 return; 590 } 591 592 RegisterSpecList sources; 593 sources = RegisterSpecList.make(source); 594 595 NormalSsaInsn toAdd; 596 597 toAdd = new NormalSsaInsn( 598 new PlainInsn(Rops.opMove(result.getType()), 599 SourcePosition.NO_INFO, result, sources), this); 600 601 insns.add(getCountPhiInsns(), toAdd); 602 movesFromPhisAtBeginning++; 603 } 604 605 /** 606 * Sets the register as used in a bitset, taking into account its 607 * category/width. 608 * 609 * @param regsUsed set, indexed by register number 610 * @param rs register to mark as used 611 */ 612 private static void setRegsUsed (BitSet regsUsed, RegisterSpec rs) { 613 regsUsed.set(rs.getReg()); 614 if (rs.getCategory() > 1) { 615 regsUsed.set(rs.getReg() + 1); 616 } 617 } 618 619 /** 620 * Checks to see if the register is used in a bitset, taking 621 * into account its category/width. 622 * 623 * @param regsUsed set, indexed by register number 624 * @param rs register to mark as used 625 * @return true if register is fully or partially (for the case of wide 626 * registers) used. 627 */ 628 private static boolean checkRegUsed (BitSet regsUsed, RegisterSpec rs) { 629 int reg = rs.getReg(); 630 int category = rs.getCategory(); 631 632 return regsUsed.get(reg) 633 || (category == 2 ? regsUsed.get(reg + 1) : false); 634 } 635 636 /** 637 * Ensures that all move operations in this block occur such that 638 * reads of any register happen before writes to that register. 639 * NOTE: caller is expected to returnSpareRegisters()! 640 * 641 * TODO See Briggs, et al "Practical Improvements to the Construction and 642 * Destruction of Static Single Assignment Form" section 5. a) This can 643 * be done in three passes. 644 * @param toSchedule List of instructions. Must consist only of moves. 645 */ 646 private void scheduleUseBeforeAssigned(List<SsaInsn> toSchedule) { 647 BitSet regsUsedAsSources = new BitSet(parent.getRegCount()); 648 // TODO get rid of this 649 BitSet regsUsedAsResults = new BitSet(parent.getRegCount()); 650 651 int sz = toSchedule.size(); 652 653 int insertPlace = 0; 654 655 while (insertPlace < sz) { 656 int oldInsertPlace = insertPlace; 657 658 // Record all registers used as sources in this block. 659 for (int i = insertPlace; i < sz; i++) { 660 setRegsUsed(regsUsedAsSources, 661 toSchedule.get(i).getSources().get(0)); 662 663 setRegsUsed(regsUsedAsResults, 664 toSchedule.get(i).getResult()); 665 } 666 667 /* 668 * If there are no circular dependencies, then there exists 669 * n instructions where n > 1 whose result is not used as a source. 670 */ 671 for (int i = insertPlace; i <sz; i++) { 672 SsaInsn insn = toSchedule.get(i); 673 674 /* 675 * Move these n registers to the front, since they overwrite 676 * nothing. 677 */ 678 if (!checkRegUsed(regsUsedAsSources, insn.getResult())) { 679 Collections.swap(toSchedule, i, insertPlace++); 680 } 681 } 682 683 // If we've made no progress in this iteration, there's a 684 // circular dependency. Split it using the temp reg. 685 if (oldInsertPlace == insertPlace) { 686 687 SsaInsn insnToSplit = null; 688 689 // Find an insn whose result is used as a source. 690 for (int i = insertPlace; i < sz; i++) { 691 SsaInsn insn = toSchedule.get(i); 692 if (checkRegUsed(regsUsedAsSources, insn.getResult()) 693 && checkRegUsed(regsUsedAsResults, 694 insn.getSources().get(0))) { 695 696 insnToSplit = insn; 697 // We're going to split this insn--move it to the 698 // front 699 Collections.swap(toSchedule, insertPlace, i); 700 break; 701 } 702 } 703 704 // At least one insn will be set above 705 706 RegisterSpec result = insnToSplit.getResult(); 707 RegisterSpec tempSpec = result.withReg( 708 parent.borrowSpareRegister(result.getCategory())); 709 710 NormalSsaInsn toAdd; 711 712 toAdd = new NormalSsaInsn( 713 new PlainInsn(Rops.opMove(result.getType()), 714 SourcePosition.NO_INFO, 715 tempSpec, 716 insnToSplit.getSources()), this); 717 718 toSchedule.add(insertPlace++, toAdd); 719 720 NormalSsaInsn toReplace; 721 RegisterSpecList newSources; 722 723 newSources = RegisterSpecList.make(tempSpec); 724 725 toReplace = new NormalSsaInsn( 726 new PlainInsn(Rops.opMove(result.getType()), 727 SourcePosition.NO_INFO, 728 result, 729 newSources), this); 730 731 toSchedule.set(insertPlace, toReplace); 732 733 // size has changed 734 sz = toSchedule.size(); 735 } 736 737 regsUsedAsSources.clear(); 738 regsUsedAsResults.clear(); 739 } 740 } 741 742 /** 743 * Adds regV to the live-out list for this block. 744 * Called by the liveness analyzer. 745 * @param regV register that is live-out for this block. 746 */ 747 public void 748 addLiveOut (int regV) { 749 if (liveOut == null) { 750 liveOut = SetFactory.makeLivenessSet(parent.getRegCount()); 751 } 752 753 liveOut.add(regV); 754 } 755 756 /** 757 * Adds regV to the live-in list for this block. 758 * Called by the liveness analyzer. 759 * @param regV register that is live-in for this block. 760 */ 761 public void 762 addLiveIn (int regV) { 763 if (liveIn == null) { 764 liveIn = SetFactory.makeLivenessSet(parent.getRegCount()); 765 } 766 767 liveIn.add(regV); 768 } 769 770 /** 771 * Returns the set of live-in registers. Valid after register 772 * interference graph has been generated, otherwise empty. 773 * 774 * @return non-null; live-in register set. 775 */ 776 public IntSet getLiveInRegs() { 777 if (liveIn == null) { 778 liveIn = SetFactory.makeLivenessSet(parent.getRegCount()); 779 } 780 return liveIn; 781 } 782 783 /** 784 * Returns the set of live-out registers. Valid after register 785 * interference graph has been generated, otherwise empty. 786 * 787 * @return non-null; live-out register set. 788 */ 789 public IntSet getLiveOutRegs() { 790 if (liveOut == null) { 791 liveOut = SetFactory.makeLivenessSet(parent.getRegCount()); 792 } 793 return liveOut; 794 } 795 796 /** 797 * @return true if this is the one-and-only exit block for this method 798 */ 799 public boolean isExitBlock() { 800 return index == parent.getExitBlockIndex(); 801 } 802 803 /** 804 * Returns true if this block is reachable (that is, it hasn't been 805 * unlinked from the control flow of this method). This currently tests 806 * that it's either the start block or it has predecessors, which suffices 807 * for all current control flow transformations. 808 * 809 * @return true if reachable 810 */ 811 public boolean isReachable() { 812 return index == parent.getEntryBlockIndex() 813 || predecessors.cardinality() > 0; 814 } 815 816 /** 817 * Sorts move instructions added via <code>addMoveToEnd</code> during 818 * phi removal so that results don't overwrite sources that are used. 819 * For use after all phis have been removed and all calls to 820 * addMoveToEnd() have been made.<p> 821 * 822 * This is necessary because copy-propogation may have left us in a state 823 * where the same basic block has the same register as a phi operand 824 * and a result. In this case, the register in the phi operand always 825 * refers value before any other phis have executed. 826 */ 827 public void scheduleMovesFromPhis() { 828 829 if (movesFromPhisAtBeginning > 1) { 830 List<SsaInsn> toSchedule; 831 832 toSchedule = insns.subList(0, movesFromPhisAtBeginning); 833 834 scheduleUseBeforeAssigned(toSchedule); 835 836 SsaInsn firstNonPhiMoveInsn = insns.get(movesFromPhisAtBeginning); 837 838 //TODO it's actually possible that this case never happens, 839 //because a move-exception block, having only one predecessor 840 //in SSA form, perhaps is never on a dominance frontier. 841 if (firstNonPhiMoveInsn.isMoveException()) { 842 if (true) { 843 /* 844 * We've yet to observe this case, and if it can 845 * occur the code written to handle it probably 846 * does not work. 847 */ 848 throw new RuntimeException( 849 "Unexpected: moves from " 850 +"phis before move-exception"); 851 } else { 852 853 // A move-exception insn must be placed first in this block 854 // We need to move it there, and deal with possible 855 // interference. 856 boolean moveExceptionInterferes = false; 857 858 int moveExceptionResult 859 = firstNonPhiMoveInsn.getResult().getReg(); 860 861 // Does the move-exception result reg interfere with the 862 // phi moves? 863 for(SsaInsn insn: toSchedule) { 864 if (insn.isResultReg(moveExceptionResult) 865 || insn.isRegASource(moveExceptionResult)) { 866 moveExceptionInterferes = true; 867 break; 868 } 869 } 870 871 if (!moveExceptionInterferes) { 872 // The easy case 873 insns.remove(movesFromPhisAtBeginning); 874 insns.add(0, firstNonPhiMoveInsn); 875 } else { 876 // We need to move the result to a spare reg and move it 877 // back. 878 879 int spareRegister; 880 RegisterSpec originalResultSpec; 881 882 originalResultSpec = firstNonPhiMoveInsn.getResult(); 883 spareRegister = parent.borrowSpareRegister( 884 originalResultSpec.getCategory()); 885 886 // We now move it to a spare register 887 firstNonPhiMoveInsn.changeResultReg(spareRegister); 888 RegisterSpec tempSpec = firstNonPhiMoveInsn.getResult(); 889 890 insns.add(0, firstNonPhiMoveInsn); 891 892 // And here we move it back 893 894 NormalSsaInsn toAdd; 895 896 toAdd = new NormalSsaInsn( 897 new PlainInsn(Rops.opMove( 898 tempSpec.getType()), 899 SourcePosition.NO_INFO, 900 originalResultSpec, 901 RegisterSpecList.make(tempSpec)), 902 this); 903 904 905 // Place it immediately after the phi-moves, 906 // overwriting the move-exception that was there. 907 insns.set(movesFromPhisAtBeginning + 1, toAdd); 908 } 909 } 910 } 911 } 912 if (movesFromPhisAtEnd > 1) { 913 scheduleUseBeforeAssigned( 914 insns.subList(insns.size() - movesFromPhisAtEnd - 1, 915 insns.size() - 1)); 916 } 917 918 // Return registers borrowed here and in scheduleUseBeforeAssigned() 919 parent.returnSpareRegisters(); 920 921 } 922 923 /** 924 * Visit all insns in this block 925 * @param visitor callback interface 926 */ 927 public void forEachInsn(SsaInsn.Visitor visitor) { 928 for (SsaInsn insn: insns) { 929 insn.accept(visitor); 930 } 931 } 932 933 public String toString() { 934 return "{" + index + ":" + Hex.u2(ropLabel) + '}'; 935 } 936 937 /** 938 * Visitor interface for basic blocks 939 */ 940 public interface Visitor { 941 942 /** 943 * Indicates a block has been visited by an iterator method. 944 * @param v non-null; block visited 945 * @param parent null-ok; parent node if applicable. 946 */ 947 void visitBlock (SsaBasicBlock v, SsaBasicBlock parent); 948 } 949} 950