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