SsaBasicBlock.java revision 99409883d9c4c0ffb49b070ce307bb33a9dfe9f1
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 137 * predecessor set will be 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 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 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 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 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 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 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 254 int sz = insns.size(); 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 * @return count of phi insns 284 */ 285 private int getCountPhiInsns() { 286 int countPhiInsns; 287 288 int sz = insns.size(); 289 for (countPhiInsns = 0; countPhiInsns < sz; countPhiInsns++) { 290 SsaInsn insn = insns.get(countPhiInsns); 291 if (!(insn instanceof PhiInsn)) { 292 break; 293 } 294 } 295 296 return countPhiInsns; 297 } 298 299 /** 300 * @return {@code non-null;} the (mutable) instruction list for this block, 301 * with phi insns at the beginning. 302 */ 303 public ArrayList<SsaInsn> getInsns() { 304 return insns; 305 } 306 307 /** 308 * @return {@code non-null;} the (mutable) list of phi insns for this block 309 */ 310 public List<SsaInsn> getPhiInsns() { 311 return insns.subList(0, getCountPhiInsns()); 312 } 313 314 /** 315 * @return the block index of this block 316 */ 317 public int getIndex() { 318 return index; 319 } 320 321 /** 322 * @return the label of this block in rop form 323 */ 324 public int getRopLabel() { 325 return ropLabel; 326 } 327 328 /** 329 * @return the label of this block in rop form as a hex string 330 */ 331 public String getRopLabelString() { 332 return Hex.u2(ropLabel); 333 } 334 335 /** 336 * @return {@code non-null;} predecessors set, indexed by block index 337 */ 338 public BitSet getPredecessors() { 339 return predecessors; 340 } 341 342 /** 343 * @return {@code non-null;} successors set, indexed by block index 344 */ 345 public BitSet getSuccessors() { 346 return successors; 347 } 348 349 /** 350 * @return {@code non-null;} ordered successor list, containing block 351 * indicies 352 */ 353 public IntList getSuccessorList() { 354 return successorList; 355 } 356 357 /** 358 * @return {@code >= -1;} block index of primary successor or 359 * {@code -1} if no primary successor. 360 */ 361 public int getPrimarySuccessorIndex() { 362 return primarySuccessor; 363 } 364 365 /** 366 * @return rop label of primary successor 367 */ 368 public int getPrimarySuccessorRopLabel() { 369 return parent.blockIndexToRopLabel(primarySuccessor); 370 } 371 372 /** 373 * @return {@code null-ok;} the primary successor block or {@code null} 374 * if there is none 375 */ 376 public SsaBasicBlock getPrimarySuccessor() { 377 if (primarySuccessor < 0) { 378 return null; 379 } else { 380 return parent.getBlocks().get(primarySuccessor); 381 } 382 } 383 384 /** 385 * @return successor list of rop labels 386 */ 387 public IntList getRopLabelSuccessorList() { 388 IntList result = new IntList(successorList.size()); 389 390 int sz = successorList.size(); 391 392 for (int i = 0; i < sz; i++) { 393 result.add(parent.blockIndexToRopLabel(successorList.get(i))); 394 } 395 return result; 396 } 397 398 /** 399 * @return {@code non-null;} method that contains this block 400 */ 401 public SsaMethod getParent() { 402 return parent; 403 } 404 405 /** 406 * Inserts a new empty GOTO block as a predecessor to this block. 407 * All previous predecessors will be predecessors to the new block. 408 * 409 * @return {@code non-null;} an appropriately-constructed instance 410 */ 411 public SsaBasicBlock insertNewPredecessor() { 412 SsaBasicBlock newPred = parent.makeNewGotoBlock(); 413 414 // Update the new block 415 newPred.predecessors = predecessors; 416 newPred.successors.set(index) ; 417 newPred.successorList.add(index); 418 newPred.primarySuccessor = index; 419 420 421 // Update us 422 predecessors = new BitSet(parent.getBlocks().size()); 423 predecessors.set(newPred.index); 424 425 // Update our (soon-to-be) old predecessors 426 for (int i = newPred.predecessors.nextSetBit(0); i >= 0; 427 i = newPred.predecessors.nextSetBit(i + 1)) { 428 429 SsaBasicBlock predBlock = parent.getBlocks().get(i); 430 431 predBlock.replaceSuccessor(index, newPred.index); 432 } 433 434 return newPred; 435 } 436 437 /** 438 * Constructs and inserts a new empty GOTO block {@code Z} between 439 * this block ({@code A}) and a current successor block 440 * ({@code B}). The new block will replace B as A's successor and 441 * A as B's predecessor. A and B will no longer be directly connected. 442 * If B is listed as a successor multiple times, all references 443 * are replaced. 444 * 445 * @param other current successor (B) 446 * @return {@code non-null;} an appropriately-constructed instance 447 */ 448 public SsaBasicBlock insertNewSuccessor(SsaBasicBlock other) { 449 SsaBasicBlock newSucc = parent.makeNewGotoBlock(); 450 451 if (!successors.get(other.index)) { 452 throw new RuntimeException("Block " + other.getRopLabelString() 453 + " not successor of " + getRopLabelString()); 454 } 455 456 // Update the new block 457 newSucc.predecessors.set(this.index); 458 newSucc.successors.set(other.index) ; 459 newSucc.successorList.add(other.index); 460 newSucc.primarySuccessor = other.index; 461 462 // Update us 463 for (int i = successorList.size() - 1 ; i >= 0; i--) { 464 if(successorList.get(i) == other.index) { 465 successorList.set(i, newSucc.index); 466 } 467 } 468 469 if (primarySuccessor == other.index) { 470 primarySuccessor = newSucc.index; 471 } 472 successors.clear(other.index); 473 successors.set(newSucc.index); 474 475 // Update "other" 476 other.predecessors.set(newSucc.index); 477 other.predecessors.set(index, successors.get(other.index)); 478 479 return newSucc; 480 } 481 482 /** 483 * Replaces an old successor with a new successor. This will throw 484 * RuntimeException if {@code oldIndex} was not a successor. 485 * 486 * @param oldIndex index of old successor block 487 * @param newIndex index of new successor block. 488 */ 489 public void replaceSuccessor(int oldIndex, int newIndex) { 490 if (oldIndex == newIndex) { 491 return; 492 } 493 494 // Update us. 495 successors.set(newIndex); 496 497 if (primarySuccessor == oldIndex) { 498 primarySuccessor = newIndex; 499 } 500 501 for (int i = successorList.size() - 1 ; i >= 0; i--) { 502 if(successorList.get(i) == oldIndex) { 503 successorList.set(i, newIndex); 504 } 505 } 506 507 successors.clear(oldIndex); 508 509 // Update new successor. 510 parent.getBlocks().get(newIndex).predecessors.set(index); 511 512 // Update old successor. 513 parent.getBlocks().get(oldIndex).predecessors.clear(index); 514 } 515 516 517 /** 518 * Attaches block to an exit block if necessary. If this block 519 * is not an exit predecessor or is the exit block, this block does 520 * nothing. For use by {@link com.android.dx.ssa.SsaMethod#makeExitBlock} 521 * 522 * @param exitBlock {@code non-null;} exit block 523 */ 524 public void exitBlockFixup(SsaBasicBlock exitBlock) { 525 if (this == exitBlock) { 526 return; 527 } 528 529 if (successorList.size() == 0) { 530 /* 531 * This is an exit predecessor. 532 * Set the successor to the exit block 533 */ 534 successors.set(exitBlock.index); 535 successorList.add(exitBlock.index); 536 primarySuccessor = exitBlock.index; 537 exitBlock.predecessors.set(this.index); 538 } 539 } 540 541 /** 542 * Adds a move instruction to the end of this basic block, just 543 * before the last instruction. If the result of the final instruction 544 * is the source in question, then the move is placed at the beginning of 545 * the primary successor block. This is for unversioned registers. 546 * 547 * @param result move destination 548 * @param source move source 549 */ 550 public void addMoveToEnd(RegisterSpec result, RegisterSpec source) { 551 552 if (result.getReg() == source.getReg()) { 553 // Sometimes we end up with no-op moves. Ignore them here. 554 return; 555 } 556 557 /* 558 * The last Insn has to be a normal SSA insn: a phi can't branch 559 * or return or cause an exception, etc. 560 */ 561 NormalSsaInsn lastInsn; 562 lastInsn = (NormalSsaInsn)insns.get(insns.size()-1); 563 564 if (lastInsn.getResult() != null || lastInsn.getSources().size() > 0) { 565 /* 566 * The final insn in this block has a source or result register, 567 * and the moves we may need to place and schedule may interfere. 568 * We need to insert this instruction at the 569 * beginning of the primary successor block instead. We know 570 * this is safe, because when we edge-split earlier, we ensured 571 * that each successor has only us as a predecessor. 572 */ 573 574 for (int i = successors.nextSetBit(0) 575 ; i >= 0 576 ; i = successors.nextSetBit(i + 1)) { 577 578 SsaBasicBlock succ; 579 580 succ = parent.getBlocks().get(i); 581 succ.addMoveToBeginning(result, source); 582 } 583 } else { 584 /* 585 * We can safely add a move to the end of the block 586 * just before the last instruction because 587 * the final insn does not assign to anything. 588 */ 589 590 RegisterSpecList sources; 591 sources = RegisterSpecList.make(source); 592 593 NormalSsaInsn toAdd; 594 595 toAdd = new NormalSsaInsn( 596 new PlainInsn(Rops.opMove(result.getType()), 597 SourcePosition.NO_INFO, result, sources), this); 598 599 insns.add(insns.size() - 1, toAdd); 600 601 movesFromPhisAtEnd++; 602 } 603 } 604 605 /** 606 * Adds a move instruction after the phi insn block. 607 * 608 * @param result move destination 609 * @param source move source 610 */ 611 public void addMoveToBeginning (RegisterSpec result, RegisterSpec source) { 612 if (result.getReg() == source.getReg()) { 613 // Sometimes we end up with no-op moves. Ignore them here. 614 return; 615 } 616 617 RegisterSpecList sources; 618 sources = RegisterSpecList.make(source); 619 620 NormalSsaInsn toAdd; 621 622 toAdd = new NormalSsaInsn( 623 new PlainInsn(Rops.opMove(result.getType()), 624 SourcePosition.NO_INFO, result, sources), this); 625 626 insns.add(getCountPhiInsns(), toAdd); 627 movesFromPhisAtBeginning++; 628 } 629 630 /** 631 * Sets the register as used in a bitset, taking into account its 632 * category/width. 633 * 634 * @param regsUsed set, indexed by register number 635 * @param rs register to mark as used 636 */ 637 private static void setRegsUsed (BitSet regsUsed, RegisterSpec rs) { 638 regsUsed.set(rs.getReg()); 639 if (rs.getCategory() > 1) { 640 regsUsed.set(rs.getReg() + 1); 641 } 642 } 643 644 /** 645 * Checks to see if the register is used in a bitset, taking 646 * into account its category/width. 647 * 648 * @param regsUsed set, indexed by register number 649 * @param rs register to mark as used 650 * @return true if register is fully or partially (for the case of wide 651 * registers) used. 652 */ 653 private static boolean checkRegUsed (BitSet regsUsed, RegisterSpec rs) { 654 int reg = rs.getReg(); 655 int category = rs.getCategory(); 656 657 return regsUsed.get(reg) 658 || (category == 2 ? regsUsed.get(reg + 1) : false); 659 } 660 661 /** 662 * Ensures that all move operations in this block occur such that 663 * reads of any register happen before writes to that register. 664 * NOTE: caller is expected to returnSpareRegisters()! 665 * 666 * TODO: See Briggs, et al "Practical Improvements to the Construction and 667 * Destruction of Static Single Assignment Form" section 5. a) This can 668 * be done in three passes. 669 * 670 * @param toSchedule List of instructions. Must consist only of moves. 671 */ 672 private void scheduleUseBeforeAssigned(List<SsaInsn> toSchedule) { 673 BitSet regsUsedAsSources = new BitSet(parent.getRegCount()); 674 // TODO get rid of this 675 BitSet regsUsedAsResults = new BitSet(parent.getRegCount()); 676 677 int sz = toSchedule.size(); 678 679 int insertPlace = 0; 680 681 while (insertPlace < sz) { 682 int oldInsertPlace = insertPlace; 683 684 // Record all registers used as sources in this block. 685 for (int i = insertPlace; i < sz; i++) { 686 setRegsUsed(regsUsedAsSources, 687 toSchedule.get(i).getSources().get(0)); 688 689 setRegsUsed(regsUsedAsResults, 690 toSchedule.get(i).getResult()); 691 } 692 693 /* 694 * If there are no circular dependencies, then there exists 695 * n instructions where n > 1 whose result is not used as a source. 696 */ 697 for (int i = insertPlace; i <sz; i++) { 698 SsaInsn insn = toSchedule.get(i); 699 700 /* 701 * Move these n registers to the front, since they overwrite 702 * nothing. 703 */ 704 if (!checkRegUsed(regsUsedAsSources, insn.getResult())) { 705 Collections.swap(toSchedule, i, insertPlace++); 706 } 707 } 708 709 // If we've made no progress in this iteration, there's a 710 // circular dependency. Split it using the temp reg. 711 if (oldInsertPlace == insertPlace) { 712 713 SsaInsn insnToSplit = null; 714 715 // Find an insn whose result is used as a source. 716 for (int i = insertPlace; i < sz; i++) { 717 SsaInsn insn = toSchedule.get(i); 718 if (checkRegUsed(regsUsedAsSources, insn.getResult()) 719 && checkRegUsed(regsUsedAsResults, 720 insn.getSources().get(0))) { 721 722 insnToSplit = insn; 723 // We're going to split this insn--move it to the 724 // front 725 Collections.swap(toSchedule, insertPlace, i); 726 break; 727 } 728 } 729 730 // At least one insn will be set above 731 732 RegisterSpec result = insnToSplit.getResult(); 733 RegisterSpec tempSpec = result.withReg( 734 parent.borrowSpareRegister(result.getCategory())); 735 736 NormalSsaInsn toAdd; 737 738 toAdd = new NormalSsaInsn( 739 new PlainInsn(Rops.opMove(result.getType()), 740 SourcePosition.NO_INFO, 741 tempSpec, 742 insnToSplit.getSources()), this); 743 744 toSchedule.add(insertPlace++, toAdd); 745 746 NormalSsaInsn toReplace; 747 RegisterSpecList newSources; 748 749 newSources = RegisterSpecList.make(tempSpec); 750 751 toReplace = new NormalSsaInsn( 752 new PlainInsn(Rops.opMove(result.getType()), 753 SourcePosition.NO_INFO, 754 result, 755 newSources), this); 756 757 toSchedule.set(insertPlace, toReplace); 758 759 // size has changed 760 sz = toSchedule.size(); 761 } 762 763 regsUsedAsSources.clear(); 764 regsUsedAsResults.clear(); 765 } 766 } 767 768 /** 769 * Adds {@code regV} to the live-out list for this block. This is called 770 * by the liveness analyzer. 771 * 772 * @param regV register that is live-out for this block. 773 */ 774 public void addLiveOut (int regV) { 775 if (liveOut == null) { 776 liveOut = SetFactory.makeLivenessSet(parent.getRegCount()); 777 } 778 779 liveOut.add(regV); 780 } 781 782 /** 783 * Adds {@code regV} to the live-in list for this block. This is 784 * called by the liveness analyzer. 785 * 786 * @param regV register that is live-in for this block. 787 */ 788 public void addLiveIn (int regV) { 789 if (liveIn == null) { 790 liveIn = SetFactory.makeLivenessSet(parent.getRegCount()); 791 } 792 793 liveIn.add(regV); 794 } 795 796 /** 797 * Returns the set of live-in registers. Valid after register 798 * interference graph has been generated, otherwise empty. 799 * 800 * @return {@code non-null;} live-in register set. 801 */ 802 public IntSet getLiveInRegs() { 803 if (liveIn == null) { 804 liveIn = SetFactory.makeLivenessSet(parent.getRegCount()); 805 } 806 return liveIn; 807 } 808 809 /** 810 * Returns the set of live-out registers. Valid after register 811 * interference graph has been generated, otherwise empty. 812 * 813 * @return {@code non-null;} live-out register set. 814 */ 815 public IntSet getLiveOutRegs() { 816 if (liveOut == null) { 817 liveOut = SetFactory.makeLivenessSet(parent.getRegCount()); 818 } 819 return liveOut; 820 } 821 822 /** 823 * @return true if this is the one-and-only exit block for this method 824 */ 825 public boolean isExitBlock() { 826 return index == parent.getExitBlockIndex(); 827 } 828 829 /** 830 * Returns true if this block is reachable (that is, it hasn't been 831 * unlinked from the control flow of this method). This currently tests 832 * that it's either the start block or it has predecessors, which suffices 833 * for all current control flow transformations. 834 * 835 * @return true if reachable 836 */ 837 public boolean isReachable() { 838 return index == parent.getEntryBlockIndex() 839 || predecessors.cardinality() > 0; 840 } 841 842 /** 843 * Sorts move instructions added via {@code addMoveToEnd} during 844 * phi removal so that results don't overwrite sources that are used. 845 * For use after all phis have been removed and all calls to 846 * addMoveToEnd() have been made.<p> 847 * 848 * This is necessary because copy-propogation may have left us in a state 849 * where the same basic block has the same register as a phi operand 850 * and a result. In this case, the register in the phi operand always 851 * refers value before any other phis have executed. 852 */ 853 public void scheduleMovesFromPhis() { 854 if (movesFromPhisAtBeginning > 1) { 855 List<SsaInsn> toSchedule; 856 857 toSchedule = insns.subList(0, movesFromPhisAtBeginning); 858 859 scheduleUseBeforeAssigned(toSchedule); 860 861 SsaInsn firstNonPhiMoveInsn = insns.get(movesFromPhisAtBeginning); 862 863 //TODO it's actually possible that this case never happens, 864 //because a move-exception block, having only one predecessor 865 //in SSA form, perhaps is never on a dominance frontier. 866 if (firstNonPhiMoveInsn.isMoveException()) { 867 if (true) { 868 /* 869 * We've yet to observe this case, and if it can 870 * occur the code written to handle it probably 871 * does not work. 872 */ 873 throw new RuntimeException( 874 "Unexpected: moves from " 875 +"phis before move-exception"); 876 } else { 877 878 // A move-exception insn must be placed first in this block 879 // We need to move it there, and deal with possible 880 // interference. 881 boolean moveExceptionInterferes = false; 882 883 int moveExceptionResult 884 = firstNonPhiMoveInsn.getResult().getReg(); 885 886 // Does the move-exception result reg interfere with the 887 // phi moves? 888 for(SsaInsn insn: toSchedule) { 889 if (insn.isResultReg(moveExceptionResult) 890 || insn.isRegASource(moveExceptionResult)) { 891 moveExceptionInterferes = true; 892 break; 893 } 894 } 895 896 if (!moveExceptionInterferes) { 897 // This is the easy case. 898 insns.remove(movesFromPhisAtBeginning); 899 insns.add(0, firstNonPhiMoveInsn); 900 } else { 901 // We need to move the result to a spare reg 902 // and move it back. 903 904 int spareRegister; 905 RegisterSpec originalResultSpec; 906 907 originalResultSpec = firstNonPhiMoveInsn.getResult(); 908 spareRegister = parent.borrowSpareRegister( 909 originalResultSpec.getCategory()); 910 911 // We now move it to a spare register. 912 firstNonPhiMoveInsn.changeResultReg(spareRegister); 913 RegisterSpec tempSpec = 914 firstNonPhiMoveInsn.getResult(); 915 916 insns.add(0, firstNonPhiMoveInsn); 917 918 // And here we move it back 919 920 NormalSsaInsn toAdd; 921 922 toAdd = new NormalSsaInsn( 923 new PlainInsn(Rops.opMove( 924 tempSpec.getType()), 925 SourcePosition.NO_INFO, 926 originalResultSpec, 927 RegisterSpecList.make(tempSpec)), 928 this); 929 930 931 // Place it immediately after the phi-moves, 932 // overwriting the move-exception that was there. 933 insns.set(movesFromPhisAtBeginning + 1, toAdd); 934 } 935 } 936 } 937 } 938 if (movesFromPhisAtEnd > 1) { 939 scheduleUseBeforeAssigned( 940 insns.subList(insns.size() - movesFromPhisAtEnd - 1, 941 insns.size() - 1)); 942 } 943 944 // Return registers borrowed here and in scheduleUseBeforeAssigned(). 945 parent.returnSpareRegisters(); 946 947 } 948 949 /** 950 * Visit all insns in this block. 951 * 952 * @param visitor {@code non-null;} callback interface 953 */ 954 public void forEachInsn(SsaInsn.Visitor visitor) { 955 for (SsaInsn insn: insns) { 956 insn.accept(visitor); 957 } 958 } 959 960 /** {@inheritDoc} */ 961 public String toString() { 962 return "{" + index + ":" + Hex.u2(ropLabel) + '}'; 963 } 964 965 /** 966 * Visitor interface for basic blocks. 967 */ 968 public interface Visitor { 969 /** 970 * Indicates a block has been visited by an iterator method. 971 * 972 * @param v {@code non-null;} block visited 973 * @param parent {@code null-ok;} parent node if applicable 974 */ 975 void visitBlock (SsaBasicBlock v, SsaBasicBlock parent); 976 } 977 978 /** 979 * Label comparator. 980 */ 981 public static final class LabelComparator 982 implements Comparator<SsaBasicBlock> { 983 /** {@inheritDoc} */ 984 public int compare(SsaBasicBlock b1, SsaBasicBlock b2) { 985 int label1 = b1.ropLabel; 986 int label2 = b2.ropLabel; 987 988 if (label1 < label2) { 989 return -1; 990 } else if (label1 > label2) { 991 return 1; 992 } else { 993 return 0; 994 } 995 } 996 } 997} 998