Ropper.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.cf.code; 18 19import com.android.dx.rop.code.*; 20import com.android.dx.rop.cst.CstInteger; 21import com.android.dx.rop.cst.CstType; 22import com.android.dx.rop.type.Prototype; 23import com.android.dx.rop.type.StdTypeList; 24import com.android.dx.rop.type.Type; 25import com.android.dx.rop.type.TypeList; 26import com.android.dx.util.Bits; 27import com.android.dx.util.Hex; 28import com.android.dx.util.IntList; 29 30import java.util.ArrayList; 31import java.util.BitSet; 32import java.util.HashMap; 33 34/** 35 * Utility that converts a basic block list into a list of register-oriented 36 * blocks. 37 */ 38public final class Ropper { 39 /** label offset for the parameter assignment block */ 40 private static final int PARAM_ASSIGNMENT = -1; 41 42 /** label offset for the return block */ 43 private static final int RETURN = -2; 44 45 /** label offset for the synchronized method final return block */ 46 private static final int SYNCH_RETURN = -3; 47 48 /** label offset for the first synchronized method setup block */ 49 private static final int SYNCH_SETUP_1 = -4; 50 51 /** label offset for the second synchronized method setup block */ 52 private static final int SYNCH_SETUP_2 = -5; 53 54 /** 55 * label offset for the first synchronized method exception 56 * handler block 57 */ 58 private static final int SYNCH_CATCH_1 = -6; 59 60 /** 61 * label offset for the second synchronized method exception 62 * handler block 63 */ 64 private static final int SYNCH_CATCH_2 = -7; 65 66 /** number of special label offsets */ 67 private static final int SPECIAL_LABEL_COUNT = 7; 68 69 /** non-null; method being converted */ 70 private final ConcreteMethod method; 71 72 /** non-null; original block list */ 73 private final ByteBlockList blocks; 74 75 /** max locals of the method */ 76 private final int maxLocals; 77 78 /** max label (exclusive) of any original bytecode block */ 79 private final int maxLabel; 80 81 /** non-null; simulation machine to use */ 82 private final RopperMachine machine; 83 84 /** non-null; simulator to use */ 85 private final Simulator sim; 86 87 /** 88 * non-null; sparse array mapping block labels to initial frame contents, 89 * if known 90 */ 91 private final Frame[] startFrames; 92 93 /** non-null; output block list in-progress */ 94 private final ArrayList<BasicBlock> result; 95 96 /** 97 * non-null; list of subroutine-nest labels 98 * (See {@link Frame#getSubroutines} associated with each result block. 99 * Parallel to {@link Ropper#result}. 100 */ 101 private final ArrayList<IntList> resultSubroutines; 102 103 /** 104 * non-null; for each block (by label) that is used as an exception 105 * handler, the type of exception it catches 106 */ 107 private final Type[] catchTypes; 108 109 /** 110 * whether an exception-handler block for a synchronized method was 111 * ever required 112 */ 113 private boolean synchNeedsExceptionHandler; 114 115 /** non-null; list of subroutines indexed by label of start address */ 116 private final Subroutine subroutines[]; 117 118 /** true if <code>subroutines</code> is non-empty */ 119 private boolean hasSubroutines; 120 121 /** 122 * Keeps track of subroutines that exist in java form and are inlined in 123 * Rop form. 124 */ 125 private class Subroutine { 126 /** list of all blocks that jsr to this subroutine */ 127 private BitSet callerBlocks; 128 /** List of all blocks that return from this subroutine */ 129 private BitSet retBlocks; 130 /** first block in this subroutine */ 131 private int startBlock; 132 133 /** 134 * Constructs instance. 135 * 136 * @param startBlock First block of the subroutine. 137 */ 138 Subroutine(int startBlock) { 139 this.startBlock = startBlock; 140 retBlocks = new BitSet(maxLabel); 141 callerBlocks = new BitSet(maxLabel); 142 hasSubroutines = true; 143 } 144 145 /** 146 * Constructs instance. 147 * 148 * @param startBlock First block of the subroutine. 149 * @param retBlock one of the ret blocks (final blocks) of this 150 * subroutine. 151 */ 152 Subroutine(int startBlock, int retBlock) { 153 this(startBlock); 154 addRetBlock(retBlock); 155 } 156 157 /** 158 * @return >= 0; the label of the subroutine's start block. 159 */ 160 int getStartBlock() { 161 return startBlock; 162 } 163 164 /** 165 * Adds a label to the list of ret blocks (final blocks) for this 166 * subroutine. 167 * 168 * @param retBlock ret block label 169 */ 170 void addRetBlock(int retBlock) { 171 retBlocks.set(retBlock); 172 } 173 174 /** 175 * Adds a label to the list of caller blocks for this subroutine. 176 * 177 * @param label a block that invokes this subroutine. 178 */ 179 void addCallerBlock(int label) { 180 callerBlocks.set(label); 181 } 182 183 /** 184 * Generates a list of subroutine successors. Note: successor blocks 185 * could be listed more than once. This is ok, because this successor 186 * list (and the block it's associated with) will be copied and inlined 187 * before we leave the ropper. Redundent successors will result in 188 * redundent (no-op) merges. 189 * 190 * @return all currently known successors 191 * (return destinations) for that subroutine 192 */ 193 IntList getSuccessors() { 194 IntList successors = new IntList(callerBlocks.size()); 195 196 /* 197 * For each subroutine caller, get it's target. If the target is us, 198 * add the ret target (subroutine successor) to our list 199 */ 200 201 for(int label = callerBlocks.nextSetBit(0); label >= 0 202 ; label = callerBlocks.nextSetBit(label+1)) { 203 204 BasicBlock subCaller = labelToBlock(label); 205 successors.add(subCaller.getSuccessors().get(0)); 206 } 207 208 successors.setImmutable(); 209 210 return successors; 211 } 212 213 /** 214 * Merges the specified frame into this subroutine's successors, 215 * setting <code>workSet</code> as appropriate. To be called with 216 * the frame of a subroutine ret block. 217 * 218 * @param frame non-null; frame from ret block to merge 219 * @param workSet non-null; workset to update 220 */ 221 void mergeToSuccessors(Frame frame, int[] workSet) { 222 int sz = callerBlocks.size(); 223 224 for(int label = callerBlocks.nextSetBit(0); label >= 0 225 ; label = callerBlocks.nextSetBit(label+1)) { 226 227 BasicBlock subCaller = labelToBlock(label); 228 int succLabel = subCaller.getSuccessors().get(0); 229 230 Frame subFrame = frame.subFrameForLabel(startBlock, label); 231 232 if (subFrame != null) { 233 mergeAndWorkAsNecessary(succLabel, -1, null, 234 subFrame, workSet); 235 } else { 236 Bits.set(workSet, label); 237 } 238 } 239 } 240 } 241 242 /** 243 * Converts a {@link ConcreteMethod} to a {@link RopMethod}. 244 * 245 * @param method non-null; method to convert 246 * @param advice non-null; translation advice to use 247 * @return non-null; the converted instance 248 */ 249 public static RopMethod convert(ConcreteMethod method, 250 TranslationAdvice advice) { 251 try { 252 Ropper r = new Ropper(method, advice); 253 r.doit(); 254 return r.getRopMethod(); 255 } catch (SimException ex) { 256 ex.addContext("...while working on method " + 257 method.getNat().toHuman()); 258 throw ex; 259 } 260 } 261 262 /** 263 * Constructs an instance. This class is not publicly instantiable; use 264 * {@link #convert}. 265 * 266 * @param method non-null; method to convert 267 * @param advice non-null; translation advice to use 268 */ 269 private Ropper(ConcreteMethod method, TranslationAdvice advice) { 270 if (method == null) { 271 throw new NullPointerException("method == null"); 272 } 273 274 if (advice == null) { 275 throw new NullPointerException("advice == null"); 276 } 277 278 this.method = method; 279 this.blocks = BasicBlocker.identifyBlocks(method); 280 this.maxLabel = blocks.getMaxLabel(); 281 this.maxLocals = method.getMaxLocals(); 282 this.machine = new RopperMachine(this, method, advice); 283 this.sim = new Simulator(machine, method); 284 this.startFrames = new Frame[maxLabel]; 285 this.subroutines = new Subroutine[maxLabel]; 286 287 /* 288 * The "* 2 + 10" below is to conservatively believe that every 289 * block is an exception handler target and should also 290 * take care of enough other possible extra overhead such that 291 * the underlying array is unlikely to need resizing. 292 */ 293 this.result = new ArrayList<BasicBlock>(blocks.size() * 2 + 10); 294 this.resultSubroutines = new ArrayList<IntList>(blocks.size() * 2 + 10); 295 296 this.catchTypes = new Type[maxLabel]; 297 this.synchNeedsExceptionHandler = false; 298 299 /* 300 * Set up the first stack frame with the right limits, but leave it 301 * empty here (to be filled in outside of the constructor). 302 */ 303 startFrames[0] = new Frame(maxLocals, method.getMaxStack()); 304 } 305 306 /** 307 * Gets the first (lowest) register number to use as the temporary 308 * area when unwinding stack manipulation ops. 309 * 310 * @return >= 0; the first register to use 311 */ 312 /*package*/ int getFirstTempStackReg() { 313 /* 314 * We use the register that is just past the deepest possible 315 * stack element, plus one if the method is synchronized to 316 * avoid overlapping with the synch register. We don't need to 317 * do anything else special at this level, since later passes 318 * will merely notice the highest register used by explicit 319 * inspection. 320 */ 321 int regCount = getNormalRegCount(); 322 return isSynchronized() ? regCount + 1 : regCount; 323 } 324 325 /** 326 * Gets the label for the exception handler setup block corresponding 327 * to the given label. 328 * 329 * @param label >= 0; the original label 330 * @return >= 0; the corresponding exception handler setup label 331 */ 332 private int getExceptionSetupLabel(int label) { 333 return maxLabel + label; 334 } 335 336 /** 337 * Gets the label for the given special-purpose block. The given label 338 * should be one of the static constants defined by this class. 339 * 340 * @param label < 0; the special label constant 341 * @return >= 0; the actual label value to use 342 */ 343 private int getSpecialLabel(int label) { 344 /* 345 * The label is bitwise-complemented so that mistakes where 346 * LABEL is used instead of getSpecialLabel(LABEL) cause a 347 * failure at block construction time, since negative labels 348 * are illegal. We multiply maxLabel by 2 since 0..maxLabel 349 * (exclusive) are the original blocks and 350 * maxLabel..(maxLabel*2) are reserved for exception handler 351 * setup blocks (see getExceptionSetupLabel(), above). 352 */ 353 return (maxLabel * 2) + ~label; 354 } 355 356 /** 357 * Gets the minimum label for unreserved use. 358 * 359 * @return >= 0; the minimum label 360 */ 361 private int getMinimumUnreservedLabel() { 362 /* 363 * The labels below ((maxLabel * 2) + SPECIAL_LABEL_COUNT) are 364 * reserved for particular uses. 365 */ 366 367 return (maxLabel * 2) + SPECIAL_LABEL_COUNT; 368 } 369 370 /** 371 * Gets an arbitrary unreserved and available label. 372 * 373 * @return >= 0; the label 374 */ 375 private int getAvailableLabel() { 376 int candidate = getMinimumUnreservedLabel(); 377 378 for (BasicBlock bb : result) { 379 int label = bb.getLabel(); 380 if (label >= candidate) { 381 candidate = label + 1; 382 } 383 } 384 385 return candidate; 386 } 387 388 /** 389 * Gets whether the method being translated is synchronized. 390 * 391 * @return whether the method being translated is synchronized 392 */ 393 private boolean isSynchronized() { 394 int accessFlags = method.getAccessFlags(); 395 return (accessFlags & AccessFlags.ACC_SYNCHRONIZED) != 0; 396 } 397 398 /** 399 * Gets whether the method being translated is static. 400 * 401 * @return whether the method being translated is static 402 */ 403 private boolean isStatic() { 404 int accessFlags = method.getAccessFlags(); 405 return (accessFlags & AccessFlags.ACC_STATIC) != 0; 406 } 407 408 /** 409 * Gets the total number of registers used for "normal" purposes (i.e., 410 * for the straightforward translation from the original Java). 411 * 412 * @return >= 0; the total number of registers used 413 */ 414 private int getNormalRegCount() { 415 return maxLocals + method.getMaxStack(); 416 } 417 418 /** 419 * Gets the register spec to use to hold the object to synchronize on, 420 * for a synchronized method. 421 * 422 * @return non-null; the register spec 423 */ 424 private RegisterSpec getSynchReg() { 425 /* 426 * We use the register that is just past the deepest possible 427 * stack element. We don't need to do anything else special at 428 * this level, since later passes will merely notice the 429 * highest register used by explicit inspection. 430 */ 431 return RegisterSpec.make(getNormalRegCount(), Type.OBJECT); 432 } 433 434 /** 435 * Searches {@link #result} for a block with the given label. Return its 436 * index if found, or return <code>-1</code> if there is no such block. 437 * 438 * @param label the label to look for 439 * @return >= -1; the index for the block with the given label or 440 * <code>-1</code> if there is no such block 441 */ 442 private int labelToResultIndex(int label) { 443 int sz = result.size(); 444 for (int i = 0; i < sz; i++) { 445 BasicBlock one = result.get(i); 446 if (one.getLabel() == label) { 447 return i; 448 } 449 } 450 451 return -1; 452 } 453 454 /** 455 * Searches {@link #result} for a block with the given label. Return it if 456 * found, or throw an exception if there is no such block. 457 * 458 * @param label the label to look for 459 * @return non-null; the block with the given label 460 */ 461 private BasicBlock labelToBlock(int label) { 462 int idx = labelToResultIndex(label); 463 464 if (idx < 0) { 465 throw new IllegalArgumentException("no such label " + 466 Hex.u2(label)); 467 } 468 469 return result.get(idx); 470 } 471 472 /** 473 * Adds a block to the output result. 474 * 475 * @param block non-null; the block to add 476 * @param subroutines non-null; subroutine label list as described in 477 * {@link Frame#getSubroutines} 478 */ 479 private void addBlock(BasicBlock block, IntList subroutines) { 480 if (block == null) { 481 throw new NullPointerException("block == null"); 482 } 483 484 result.add(block); 485 subroutines.throwIfMutable(); 486 resultSubroutines.add(subroutines); 487 } 488 489 /** 490 * Adds or replace a block in the output result. If this is a 491 * replacement, then any extra blocks that got added with the 492 * original get removed as a result of calling this method. 493 * 494 * @param block non-null; the block to add or replace 495 * @param subroutines non-null; subroutine label list as described in 496 * {@link Frame#getSubroutines} 497 * @return <code>true</code> if the block was replaced or 498 * <code>false</code> if it was added for the first time 499 */ 500 private boolean addOrReplaceBlock(BasicBlock block, IntList subroutines) { 501 if (block == null) { 502 throw new NullPointerException("block == null"); 503 } 504 505 int idx = labelToResultIndex(block.getLabel()); 506 boolean ret; 507 508 if (idx < 0) { 509 ret = false; 510 } else { 511 /* 512 * We are replacing a pre-existing block, so find any 513 * blocks that got added as part of the original and 514 * remove those too. Such blocks are (possibly indirect) 515 * successors of this block which are out of the range of 516 * normally-translated blocks. 517 */ 518 removeBlockAndSpecialSuccessors(idx); 519 ret = true; 520 } 521 522 result.add(block); 523 subroutines.throwIfMutable(); 524 resultSubroutines.add(subroutines); 525 return ret; 526 } 527 528 /** 529 * Adds or replaces a block in the output result. Do not delete 530 * any successors. 531 * 532 * @param block non-null; the block to add or replace 533 * @param subroutines non-null; subroutine label list as described in 534 * {@link Frame#getSubroutines} 535 * @return <code>true</code> if the block was replaced or 536 * <code>false</code> if it was added for the first time 537 */ 538 private boolean addOrReplaceBlockNoDelete(BasicBlock block, 539 IntList subroutines) { 540 if (block == null) { 541 throw new NullPointerException("block == null"); 542 } 543 544 int idx = labelToResultIndex(block.getLabel()); 545 boolean ret; 546 547 if (idx < 0) { 548 ret = false; 549 } else { 550 result.remove(idx); 551 resultSubroutines.remove(idx); 552 ret = true; 553 } 554 555 result.add(block); 556 subroutines.throwIfMutable(); 557 resultSubroutines.add(subroutines); 558 return ret; 559 } 560 561 /** 562 * Helper for {@link #addOrReplaceBlock} which recursively removes 563 * the given block and all blocks that are (direct and indirect) 564 * successors of it whose labels indicate that they are not in the 565 * normally-translated range. 566 * 567 * @param idx non-null; block to remove (etc.) 568 */ 569 private void removeBlockAndSpecialSuccessors(int idx) { 570 int minLabel = getMinimumUnreservedLabel(); 571 BasicBlock block = result.get(idx); 572 IntList successors = block.getSuccessors(); 573 int sz = successors.size(); 574 575 result.remove(idx); 576 resultSubroutines.remove(idx); 577 578 for (int i = 0; i < sz; i++) { 579 int label = successors.get(i); 580 if (label >= minLabel) { 581 idx = labelToResultIndex(label); 582 if (idx < 0) { 583 throw new RuntimeException("Invalid label " 584 + Hex.u2(label)); 585 } 586 removeBlockAndSpecialSuccessors(idx); 587 } 588 } 589 } 590 591 /** 592 * Extracts the resulting {@link RopMethod} from the instance. 593 * 594 * @return non-null; the method object 595 */ 596 private RopMethod getRopMethod() { 597 598 // Construct the final list of blocks. 599 600 int sz = result.size(); 601 BasicBlockList bbl = new BasicBlockList(sz); 602 for (int i = 0; i < sz; i++) { 603 bbl.set(i, result.get(i)); 604 } 605 bbl.setImmutable(); 606 607 // Construct the method object to wrap it all up. 608 609 /* 610 * Note: The parameter assignment block is always the first 611 * that should be executed, hence the second argument to the 612 * constructor. 613 */ 614 return new RopMethod(bbl, getSpecialLabel(PARAM_ASSIGNMENT)); 615 } 616 617 /** 618 * Does the conversion. 619 */ 620 private void doit() { 621 int[] workSet = Bits.makeBitSet(maxLabel); 622 623 Bits.set(workSet, 0); 624 addSetupBlocks(); 625 setFirstFrame(); 626 627 for (;;) { 628 int offset = Bits.findFirst(workSet, 0); 629 if (offset < 0) { 630 break; 631 } 632 Bits.clear(workSet, offset); 633 ByteBlock block = blocks.labelToBlock(offset); 634 Frame frame = startFrames[offset]; 635 try { 636 processBlock(block, frame, workSet); 637 } catch (SimException ex) { 638 ex.addContext("...while working on block " + Hex.u2(offset)); 639 throw ex; 640 } 641 } 642 643 addReturnBlock(); 644 addSynchExceptionHandlerBlock(); 645 addExceptionSetupBlocks(); 646 647 if (hasSubroutines) { 648 // Subroutines are very rare, so skip this step if it's n/a 649 inlineSubroutines(); 650 } 651 } 652 653 /** 654 * Sets up the first frame to contain all the incoming parameters in 655 * locals. 656 */ 657 private void setFirstFrame() { 658 Prototype desc = method.getEffectiveDescriptor(); 659 startFrames[0].initializeWithParameters(desc.getParameterTypes()); 660 startFrames[0].setImmutable(); 661 } 662 663 /** 664 * Processes the given block. 665 * 666 * @param block non-null; block to process 667 * @param frame non-null; start frame for the block 668 * @param workSet non-null; bits representing work to do, which this 669 * method may add to 670 */ 671 private void processBlock(ByteBlock block, Frame frame, int[] workSet) { 672 // Prepare the list of caught exceptions for this block. 673 ByteCatchList catches = block.getCatches(); 674 machine.startBlock(catches.toRopCatchList()); 675 676 /* 677 * Using a copy of the given frame, simulate each instruction, 678 * calling into machine for each. 679 */ 680 frame = frame.copy(); 681 sim.simulate(block, frame); 682 frame.setImmutable(); 683 684 int extraBlockCount = machine.getExtraBlockCount(); 685 ArrayList<Insn> insns = machine.getInsns(); 686 int insnSz = insns.size(); 687 688 /* 689 * Merge the frame into each possible non-exceptional 690 * successor. 691 */ 692 693 int catchSz = catches.size(); 694 IntList successors = block.getSuccessors(); 695 696 int startSuccessorIndex; 697 698 Subroutine calledSubroutine = null; 699 if (machine.hasJsr()) { 700 /* 701 * If this frame ends in a JSR, only merge our frame with 702 * the subroutine start, not the subroutine's return target. 703 */ 704 startSuccessorIndex = 1; 705 706 int subroutineLabel = successors.get(1); 707 708 if (subroutines[subroutineLabel] == null) { 709 subroutines[subroutineLabel] = new Subroutine (subroutineLabel); 710 } 711 712 subroutines[subroutineLabel].addCallerBlock(block.getLabel()); 713 714 calledSubroutine = subroutines[subroutineLabel]; 715 } else if (machine.hasRet()) { 716 /* 717 * This block ends in a ret, which means it's the final block 718 * in some subroutine. Ultimately, this block will be copied 719 * and inlined for each call and then disposed of. 720 */ 721 722 ReturnAddress ra = machine.getReturnAddress(); 723 int subroutineLabel = ra.getSubroutineAddress(); 724 725 if (subroutines[subroutineLabel] == null) { 726 subroutines[subroutineLabel] 727 = new Subroutine (subroutineLabel, block.getLabel()); 728 } else { 729 subroutines[subroutineLabel].addRetBlock(block.getLabel()); 730 } 731 732 successors = subroutines[subroutineLabel].getSuccessors(); 733 subroutines[subroutineLabel] 734 .mergeToSuccessors(frame, workSet); 735 // Skip processing below since we just did it. 736 startSuccessorIndex = successors.size(); 737 } else if (machine.wereCatchesUsed()) { 738 /* 739 * If there are catches, then the first successors 740 * (which will either be all of them or all but the last one) 741 * are catch targets. 742 */ 743 startSuccessorIndex = catchSz; 744 } else { 745 startSuccessorIndex = 0; 746 } 747 748 int succSz = successors.size(); 749 for (int i = startSuccessorIndex; i < succSz; 750 i++) { 751 int succ = successors.get(i); 752 try { 753 mergeAndWorkAsNecessary(succ, block.getLabel(), 754 calledSubroutine, frame, workSet); 755 } catch (SimException ex) { 756 ex.addContext("...while merging to block " + Hex.u2(succ)); 757 throw ex; 758 } 759 } 760 761 if ((succSz == 0) && machine.returns()) { 762 /* 763 * The block originally contained a return, but it has 764 * been made to instead end with a goto, and we need to 765 * tell it at this point that its sole successor is the 766 * return block. This has to happen after the merge loop 767 * above, since, at this point, the return block doesn't 768 * actually exist; it gets synthesized at the end of 769 * processing the original blocks. 770 */ 771 successors = IntList.makeImmutable(getSpecialLabel(RETURN)); 772 succSz = 1; 773 } 774 775 int primarySucc; 776 777 if (succSz == 0) { 778 primarySucc = -1; 779 } else { 780 primarySucc = machine.getPrimarySuccessorIndex(); 781 if (primarySucc >= 0) { 782 primarySucc = successors.get(primarySucc); 783 } 784 } 785 786 /* 787 * This variable is true only when the method is synchronized and 788 * the block being processed can possibly throw an exception. 789 */ 790 boolean synch = isSynchronized() && machine.canThrow(); 791 792 if (synch || (catchSz != 0)) { 793 /* 794 * Deal with exception handlers: Merge an exception-catch 795 * frame into each possible exception handler, and 796 * construct a new set of successors to point at the 797 * exception handler setup blocks (which get synthesized 798 * at the very end of processing). 799 */ 800 boolean catchesAny = false; 801 IntList newSucc = new IntList(succSz); 802 for (int i = 0; i < catchSz; i++) { 803 ByteCatchList.Item one = catches.get(i); 804 CstType exceptionClass = one.getExceptionClass(); 805 int targ = one.getHandlerPc(); 806 807 catchesAny |= (exceptionClass == CstType.OBJECT); 808 809 Frame f = frame.makeExceptionHandlerStartFrame(exceptionClass); 810 811 try { 812 mergeAndWorkAsNecessary(targ, block.getLabel(), 813 null, f, workSet); 814 } catch (SimException ex) { 815 ex.addContext("...while merging exception to block " + 816 Hex.u2(targ)); 817 throw ex; 818 } 819 820 /* 821 * Set up the exception handler type, by setting it if 822 * the given handler has yet to be encountered, or by 823 * conservatively unioning if it has. 824 */ 825 Type already = catchTypes[targ]; 826 if (already == null) { 827 catchTypes[targ] = exceptionClass.getClassType(); 828 } else if (already != exceptionClass.getClassType()) { 829 catchTypes[targ] = Type.OBJECT; 830 } 831 832 /* 833 * The synthesized exception setup block will have the 834 * label getExceptionSetupLabel(targ). 835 */ 836 newSucc.add(getExceptionSetupLabel(targ)); 837 } 838 839 if (synch && !catchesAny) { 840 /* 841 * The method is synchronized and this block doesn't 842 * already have a catch-all handler, so add one to the 843 * end, both in the successors and in the throwing 844 * instruction(s) at the end of the block (which is where 845 * the caught classes live). 846 */ 847 newSucc.add(getSpecialLabel(SYNCH_CATCH_1)); 848 synchNeedsExceptionHandler = true; 849 850 for (int i = insnSz - extraBlockCount - 1; i < insnSz; i++) { 851 Insn insn = insns.get(i); 852 if (insn.canThrow()) { 853 insn = insn.withAddedCatch(Type.OBJECT); 854 insns.set(i, insn); 855 } 856 } 857 } 858 859 if (primarySucc >= 0) { 860 newSucc.add(primarySucc); 861 } 862 863 newSucc.setImmutable(); 864 successors = newSucc; 865 } 866 867 // Construct the final resulting block(s), and store it (them). 868 869 int primarySuccListIndex = successors.indexOf(primarySucc); 870 871 /* 872 * If there are any extra blocks, work backwards through the 873 * list of instructions, adding single-instruction blocks, and 874 * resetting the successors variables as appropriate. 875 */ 876 for (/*extraBlockCount*/; extraBlockCount > 0; extraBlockCount--) { 877 /* 878 * Some of the blocks that the RopperMachine wants added 879 * are for move-result insns, and these need goto insns as well. 880 */ 881 Insn extraInsn = insns.get(--insnSz); 882 boolean needsGoto 883 = extraInsn.getOpcode().getBranchingness() 884 == Rop.BRANCH_NONE; 885 InsnList il = new InsnList(needsGoto ? 2 : 1); 886 IntList extraBlockSuccessors = successors; 887 888 il.set(0, extraInsn); 889 890 if (needsGoto) { 891 il.set(1, new PlainInsn(Rops.GOTO, 892 extraInsn.getPosition(), null, 893 RegisterSpecList.EMPTY)); 894 /* 895 * Obviously, this block won't be throwing an exception 896 * so it should only have one successor. 897 */ 898 extraBlockSuccessors = IntList.makeImmutable(primarySucc); 899 } 900 il.setImmutable(); 901 902 int label = getAvailableLabel(); 903 BasicBlock bb = new BasicBlock(label, il, extraBlockSuccessors, 904 primarySucc); 905 // All of these extra blocks will be in the same subroutine 906 addBlock(bb, frame.getSubroutines()); 907 908 successors = successors.mutableCopy(); 909 successors.set(primarySuccListIndex, label); 910 successors.setImmutable(); 911 primarySucc = label; 912 } 913 914 Insn lastInsn = (insnSz == 0) ? null : insns.get(insnSz - 1); 915 916 /* 917 * Add a goto to the end of the block if it doesn't already 918 * end with a branch, to maintain the invariant that all 919 * blocks end with a branch of some sort or other. Note that 920 * it is possible for there to be blocks for which no 921 * instructions were ever output (e.g., only consist of pop* 922 * in the original Java bytecode). 923 */ 924 if ((lastInsn == null) || 925 (lastInsn.getOpcode().getBranchingness() == Rop.BRANCH_NONE)) { 926 SourcePosition pos = (lastInsn == null) ? SourcePosition.NO_INFO : 927 lastInsn.getPosition(); 928 insns.add(new PlainInsn(Rops.GOTO, pos, null, 929 RegisterSpecList.EMPTY)); 930 insnSz++; 931 } 932 933 /* 934 * Construct a block for the remaining instructions (which in 935 * the usual case is all of them). 936 */ 937 938 InsnList il = new InsnList(insnSz); 939 for (int i = 0; i < insnSz; i++) { 940 il.set(i, insns.get(i)); 941 } 942 il.setImmutable(); 943 944 BasicBlock bb = 945 new BasicBlock(block.getLabel(), il, successors, primarySucc); 946 addOrReplaceBlock(bb, frame.getSubroutines()); 947 } 948 949 /** 950 * Helper for {@link #processBlock}, which merges frames and 951 * adds to the work set, as necessary. 952 * 953 * @param label >= 0; label to work on 954 * @param pred predecessor label. Must be >= 0 when 955 * <code>label</code> is a subroutine start block and calledSubroutine 956 * is non-null. Otherwise, may be -1. 957 * @param calledSubroutine null-ok; a Subroutine instance if 958 * <code>label</code> is the first block in a subroutine. 959 * @param frame non-null; new frame for the labelled block 960 * @param workSet non-null; bits representing work to do, which this 961 * method may add to 962 */ 963 private void mergeAndWorkAsNecessary(int label, int pred, 964 Subroutine calledSubroutine, Frame frame, int[] workSet) { 965 Frame existing = startFrames[label]; 966 Frame merged; 967 968 if (existing != null) { 969 /* 970 * Some other block also continues at this label. Merge 971 * the frames, and re-set the bit in the work set if there 972 * was a change. 973 */ 974 if (calledSubroutine != null) { 975 merged = existing.mergeWithSubroutineCaller(frame, 976 calledSubroutine.getStartBlock(), pred); 977 } else { 978 merged = existing.mergeWith(frame); 979 } 980 if (merged != existing) { 981 startFrames[label] = merged; 982 Bits.set(workSet, label); 983 } 984 } else { 985 // This is the first time this label has been encountered. 986 if (calledSubroutine != null) { 987 startFrames[label] 988 = frame.makeNewSubroutineStartFrame(label, pred); 989 } else { 990 startFrames[label] = frame; 991 } 992 Bits.set(workSet, label); 993 } 994 } 995 996 /** 997 * Constructs and adds the blocks that perform setup for the rest of 998 * the method. This includes a first block which merely contains 999 * assignments from parameters to the same-numbered registers and 1000 * a possible second block which deals with synchronization. 1001 */ 1002 private void addSetupBlocks() { 1003 LocalVariableList localVariables = method.getLocalVariables(); 1004 SourcePosition pos = method.makeSourcePosistion(0); 1005 Prototype desc = method.getEffectiveDescriptor(); 1006 StdTypeList params = desc.getParameterTypes(); 1007 int sz = params.size(); 1008 InsnList insns = new InsnList(sz + 1); 1009 int at = 0; 1010 1011 for (int i = 0; i < sz; i++) { 1012 Type one = params.get(i); 1013 LocalVariableList.Item local = localVariables.pcAndIndexToLocal(0, at); 1014 RegisterSpec result = (local == null) ? 1015 RegisterSpec.make(at, one) : 1016 RegisterSpec.makeLocalOptional(at, one, local.getLocalItem()); 1017 1018 Insn insn = new PlainCstInsn(Rops.opMoveParam(one), pos, result, 1019 RegisterSpecList.EMPTY, 1020 CstInteger.make(at)); 1021 insns.set(i, insn); 1022 at += one.getCategory(); 1023 } 1024 1025 insns.set(sz, new PlainInsn(Rops.GOTO, pos, null, 1026 RegisterSpecList.EMPTY)); 1027 insns.setImmutable(); 1028 1029 boolean synch = isSynchronized(); 1030 int label = synch ? getSpecialLabel(SYNCH_SETUP_1) : 0; 1031 BasicBlock bb = 1032 new BasicBlock(getSpecialLabel(PARAM_ASSIGNMENT), insns, 1033 IntList.makeImmutable(label), label); 1034 addBlock(bb, IntList.EMPTY); 1035 1036 if (synch) { 1037 RegisterSpec synchReg = getSynchReg(); 1038 Insn insn; 1039 if (isStatic()) { 1040 insn = new ThrowingCstInsn(Rops.CONST_OBJECT, pos, 1041 RegisterSpecList.EMPTY, 1042 StdTypeList.EMPTY, 1043 method.getDefiningClass()); 1044 insns = new InsnList(1); 1045 insns.set(0, insn); 1046 } else { 1047 insns = new InsnList(2); 1048 insn = new PlainCstInsn(Rops.MOVE_PARAM_OBJECT, pos, 1049 synchReg, RegisterSpecList.EMPTY, 1050 CstInteger.VALUE_0); 1051 insns.set(0, insn); 1052 insns.set(1, new PlainInsn(Rops.GOTO, pos, null, 1053 RegisterSpecList.EMPTY)); 1054 } 1055 1056 int label2 = getSpecialLabel(SYNCH_SETUP_2); 1057 insns.setImmutable(); 1058 bb = new BasicBlock(label, insns, 1059 IntList.makeImmutable(label2), label2); 1060 addBlock(bb, IntList.EMPTY); 1061 1062 insns = new InsnList(isStatic() ? 2 : 1); 1063 1064 if (isStatic()) { 1065 insns.set(0, new PlainInsn(Rops.opMoveResultPseudo(synchReg), 1066 pos, synchReg, RegisterSpecList.EMPTY)); 1067 } 1068 1069 insn = new ThrowingInsn(Rops.MONITOR_ENTER, pos, 1070 RegisterSpecList.make(synchReg), 1071 StdTypeList.EMPTY); 1072 insns.set(isStatic() ? 1 :0, insn); 1073 insns.setImmutable(); 1074 bb = new BasicBlock(label2, insns, IntList.makeImmutable(0), 0); 1075 addBlock(bb, IntList.EMPTY); 1076 } 1077 } 1078 1079 /** 1080 * Constructs and adds the return block, if necessary. The return 1081 * block merely contains an appropriate <code>return</code> 1082 * instruction. 1083 */ 1084 private void addReturnBlock() { 1085 Rop returnOp = machine.getReturnOp(); 1086 1087 if (returnOp == null) { 1088 /* 1089 * The method being converted never returns normally, so there's 1090 * no need for a return block. 1091 */ 1092 return; 1093 } 1094 1095 SourcePosition returnPos = machine.getReturnPosition(); 1096 int label = getSpecialLabel(RETURN); 1097 1098 if (isSynchronized()) { 1099 InsnList insns = new InsnList(1); 1100 Insn insn = new ThrowingInsn(Rops.MONITOR_EXIT, returnPos, 1101 RegisterSpecList.make(getSynchReg()), 1102 StdTypeList.EMPTY); 1103 insns.set(0, insn); 1104 insns.setImmutable(); 1105 1106 int nextLabel = getSpecialLabel(SYNCH_RETURN); 1107 BasicBlock bb = 1108 new BasicBlock(label, insns, 1109 IntList.makeImmutable(nextLabel), nextLabel); 1110 addBlock(bb, IntList.EMPTY); 1111 1112 label = nextLabel; 1113 } 1114 1115 InsnList insns = new InsnList(1); 1116 TypeList sourceTypes = returnOp.getSources(); 1117 RegisterSpecList sources; 1118 1119 if (sourceTypes.size() == 0) { 1120 sources = RegisterSpecList.EMPTY; 1121 } else { 1122 RegisterSpec source = RegisterSpec.make(0, sourceTypes.getType(0)); 1123 sources = RegisterSpecList.make(source); 1124 } 1125 1126 Insn insn = new PlainInsn(returnOp, returnPos, null, sources); 1127 insns.set(0, insn); 1128 insns.setImmutable(); 1129 1130 BasicBlock bb = new BasicBlock(label, insns, IntList.EMPTY, -1); 1131 addBlock(bb, IntList.EMPTY); 1132 } 1133 1134 /** 1135 * Constructs and adds, if necessary, the catch-all exception handler 1136 * block to deal with unwinding the lock taken on entry to a synchronized 1137 * method. 1138 */ 1139 private void addSynchExceptionHandlerBlock() { 1140 if (!synchNeedsExceptionHandler) { 1141 /* 1142 * The method being converted either isn't synchronized or 1143 * can't possibly throw exceptions in its main body, so 1144 * there's no need for a synchronized method exception 1145 * handler. 1146 */ 1147 return; 1148 } 1149 1150 SourcePosition pos = method.makeSourcePosistion(0); 1151 RegisterSpec exReg = RegisterSpec.make(0, Type.THROWABLE); 1152 BasicBlock bb; 1153 Insn insn; 1154 1155 InsnList insns = new InsnList(2); 1156 insn = new PlainInsn(Rops.opMoveException(Type.THROWABLE), pos, 1157 exReg, RegisterSpecList.EMPTY); 1158 insns.set(0, insn); 1159 insn = new ThrowingInsn(Rops.MONITOR_EXIT, pos, 1160 RegisterSpecList.make(getSynchReg()), 1161 StdTypeList.EMPTY); 1162 insns.set(1, insn); 1163 insns.setImmutable(); 1164 1165 int label2 = getSpecialLabel(SYNCH_CATCH_2); 1166 bb = new BasicBlock(getSpecialLabel(SYNCH_CATCH_1), insns, 1167 IntList.makeImmutable(label2), label2); 1168 addBlock(bb, IntList.EMPTY); 1169 1170 insns = new InsnList(1); 1171 insn = new ThrowingInsn(Rops.THROW, pos, 1172 RegisterSpecList.make(exReg), 1173 StdTypeList.EMPTY); 1174 insns.set(0, insn); 1175 insns.setImmutable(); 1176 1177 bb = new BasicBlock(label2, insns, IntList.EMPTY, -1); 1178 addBlock(bb, IntList.EMPTY); 1179 } 1180 1181 /** 1182 * Creates the exception handler setup blocks. "maxLocals" 1183 * below is because that's the register number corresponding 1184 * to the sole element on a one-deep stack (which is the 1185 * situation at the start of an exception handler block). 1186 */ 1187 private void addExceptionSetupBlocks() { 1188 1189 int len = catchTypes.length; 1190 for (int i = 0; i < len; i++) { 1191 Type one = catchTypes[i]; 1192 if (one != null) { 1193 Insn proto = labelToBlock(i).getFirstInsn(); 1194 SourcePosition pos = proto.getPosition(); 1195 InsnList il = new InsnList(2); 1196 1197 Insn insn = new PlainInsn(Rops.opMoveException(one), 1198 pos, 1199 RegisterSpec.make(maxLocals, one), 1200 RegisterSpecList.EMPTY); 1201 il.set(0, insn); 1202 1203 insn = new PlainInsn(Rops.GOTO, pos, null, 1204 RegisterSpecList.EMPTY); 1205 il.set(1, insn); 1206 il.setImmutable(); 1207 1208 BasicBlock bb = new BasicBlock(getExceptionSetupLabel(i), 1209 il, 1210 IntList.makeImmutable(i), 1211 i); 1212 addBlock(bb, startFrames[i].getSubroutines()); 1213 } 1214 } 1215 } 1216 1217 /** 1218 * Checks to see if the basic block is a subroutine caller block. 1219 * 1220 * @param bb non-null; the basic block in question 1221 * @return true if this block calls a subroutine 1222 */ 1223 private boolean isSubroutineCaller(BasicBlock bb) { 1224 IntList successors = bb.getSuccessors(); 1225 if (successors.size() < 2) return false; 1226 1227 int subLabel = successors.get(1); 1228 1229 return (subLabel < subroutines.length) 1230 && (subroutines[subLabel] != null); 1231 } 1232 1233 /** 1234 * Inlines any subroutine calls 1235 */ 1236 private void inlineSubroutines() { 1237 final IntList reachableSubroutineCallerLabels = new IntList(4); 1238 1239 /* 1240 * Compile a list of all subroutine calls reachable 1241 * through the normal (non-subroutine) flow. We do this first, since 1242 * we'll be affecting the call flow as we go. 1243 * 1244 * Start at label 0 -- the param assignment block has nothing for us 1245 */ 1246 forEachNonSubBlockDepthFirst(0, new BasicBlock.Visitor() { 1247 public void visitBlock(BasicBlock b) { 1248 if (isSubroutineCaller(b)) { 1249 reachableSubroutineCallerLabels.add(b.getLabel()); 1250 } 1251 } 1252 }); 1253 1254 /* 1255 * Convert the resultSubroutines list, indexed by block index, 1256 * to a label-to-subroutines mapping used by the inliner. 1257 */ 1258 int largestAllocedLabel = getAvailableLabel(); 1259 ArrayList<IntList> labelToSubroutines 1260 = new ArrayList<IntList>(largestAllocedLabel); 1261 for (int i = 0; i < largestAllocedLabel; i++) { 1262 labelToSubroutines.add(null); 1263 } 1264 1265 for (int i = 0; i < result.size(); i++) { 1266 BasicBlock b = result.get(i); 1267 if (b == null) { 1268 continue; 1269 } 1270 IntList subroutineList = resultSubroutines.get(i); 1271 labelToSubroutines.set(b.getLabel(), subroutineList); 1272 } 1273 1274 /* 1275 * Inline all reachable subroutines. 1276 * Inner subroutines will be inlined as they are encountered. 1277 */ 1278 int sz = reachableSubroutineCallerLabels.size(); 1279 for (int i = 0 ; i < sz ; i++) { 1280 int label = reachableSubroutineCallerLabels.get(i); 1281 new SubroutineInliner( 1282 new LabelAllocator(getAvailableLabel()), labelToSubroutines) 1283 .inlineSubroutineCalledFrom(labelToBlock(label)); 1284 } 1285 1286 // Now find the blocks that aren't reachable and remove them 1287 deleteUnreachableBlocks(); 1288 } 1289 1290 /** 1291 * Deletes all blocks that cannot be reached. This is run to delete 1292 * original subroutine blocks after subroutine inlining. 1293 */ 1294 private void deleteUnreachableBlocks() { 1295 final IntList reachableLabels = new IntList(result.size()); 1296 1297 // subroutine inlining is done now and we won't update this list here 1298 resultSubroutines.clear(); 1299 1300 forEachNonSubBlockDepthFirst(getSpecialLabel(PARAM_ASSIGNMENT), 1301 new BasicBlock.Visitor() { 1302 1303 public void visitBlock(BasicBlock b) { 1304 reachableLabels.add(b.getLabel()); 1305 } 1306 }); 1307 1308 reachableLabels.sort(); 1309 1310 for (int i = result.size() - 1 ; i >= 0 ; i--) { 1311 if (reachableLabels.indexOf(result.get(i).getLabel()) < 0) { 1312 result.remove(i); 1313 // unnecessary here really, since subroutine inlining is done 1314 //resultSubroutines.remove(i); 1315 } 1316 } 1317 } 1318 1319 /** 1320 * Allocates labels, without requiring previously allocated labels 1321 * to have been added to the blocks list. 1322 */ 1323 private static class LabelAllocator { 1324 int nextAvailableLabel; 1325 1326 /** 1327 * @param startLabel available label to start allocating from 1328 */ 1329 LabelAllocator(int startLabel) { 1330 nextAvailableLabel = startLabel; 1331 } 1332 1333 /** 1334 * @return next available label 1335 */ 1336 int getNextLabel() { 1337 return nextAvailableLabel++; 1338 } 1339 } 1340 1341 /** 1342 * Inlines a subroutine. Start by calling 1343 * <code>inlineSubroutineCalledFrom</code>. 1344 */ 1345 private class SubroutineInliner { 1346 /** 1347 * maps original label to the label 1348 * that will be used by the inlined version 1349 */ 1350 private final HashMap<Integer, Integer> origLabelToCopiedLabel; 1351 1352 /** Set of original labels that need to be copied. */ 1353 private final BitSet workList; 1354 1355 /** The label of the original start block for this subroutine. */ 1356 private int subroutineStart; 1357 1358 /** The label of the ultimate return block. */ 1359 private int subroutineSuccessor; 1360 1361 /** Used for generating new labels for copied blocks. */ 1362 private final LabelAllocator labelAllocator; 1363 1364 /** 1365 * A mapping, indexed by label, to subroutine nesting list. 1366 * The subroutine nest list is as returned by 1367 * {@link Frame#getSubroutines}. 1368 */ 1369 private final ArrayList<IntList> labelToSubroutines; 1370 1371 SubroutineInliner(final LabelAllocator labelAllocator, 1372 ArrayList<IntList> labelToSubroutines) { 1373 origLabelToCopiedLabel = new HashMap<Integer, Integer>(); 1374 1375 workList = new BitSet(maxLabel); 1376 1377 this.labelAllocator = labelAllocator; 1378 this.labelToSubroutines = labelToSubroutines; 1379 } 1380 1381 /** 1382 * Inlines a subroutine. 1383 * 1384 * @param b block where jsr occurred in the original bytecode 1385 */ 1386 void inlineSubroutineCalledFrom(final BasicBlock b) { 1387 1388 /* 1389 * The 0th successor of a subroutine caller block is where 1390 * the subroutine should return to. The 1st successor is 1391 * the start block of the subroutine. 1392 */ 1393 subroutineSuccessor = b.getSuccessors().get(0); 1394 subroutineStart = b.getSuccessors().get(1); 1395 1396 /* 1397 * This allocates an initial label and adds the first 1398 * block to the worklist. 1399 */ 1400 int newSubStartLabel = mapOrAllocateLabel(subroutineStart); 1401 1402 for(int label = workList.nextSetBit(0); label >= 0 1403 ; label = workList.nextSetBit(0)) { 1404 1405 workList.clear(label); 1406 int newLabel = origLabelToCopiedLabel.get(label); 1407 1408 copyBlock(label, newLabel); 1409 1410 if (isSubroutineCaller(labelToBlock(label))) { 1411 new SubroutineInliner(labelAllocator, labelToSubroutines) 1412 .inlineSubroutineCalledFrom(labelToBlock(newLabel)); 1413 } 1414 } 1415 1416 /* 1417 * Replace the original caller block, since we now have a 1418 * new successor 1419 */ 1420 1421 addOrReplaceBlockNoDelete( 1422 new BasicBlock(b.getLabel(), b.getInsns(), 1423 IntList.makeImmutable (newSubStartLabel), 1424 newSubStartLabel), labelToSubroutines.get(b.getLabel())); 1425 } 1426 1427 /** 1428 * Copies a basic block, mapping its successors along the way. 1429 * @param origLabel original block label 1430 * @param newLabel label that the new block should have 1431 */ 1432 private void copyBlock(int origLabel, int newLabel) { 1433 1434 BasicBlock origBlock = labelToBlock(origLabel); 1435 1436 final IntList origSuccessors = origBlock.getSuccessors(); 1437 IntList successors; 1438 int primarySuccessor = -1; 1439 Subroutine subroutine; 1440 1441 if (isSubroutineCaller(origBlock)) { 1442 /* 1443 * A subroutine call inside a subroutine call. 1444 * Set up so we can recurse. The caller block should have 1445 * it's first successor be a copied block that will be 1446 * the subroutine's return point. It's second successor will 1447 * be copied when we recurse, and remains as the original 1448 * label of the start of the inner subroutine. 1449 */ 1450 1451 successors = IntList.makeImmutable( 1452 mapOrAllocateLabel(origSuccessors.get(0)), 1453 origSuccessors.get(1)); 1454 // primary successor will be set when this block is replaced 1455 } else if (null 1456 != (subroutine = subroutineFromRetBlock(origLabel))) { 1457 /* 1458 * this is a ret block -- its successor 1459 * should be subroutineSuccessor 1460 */ 1461 1462 // Sanity check 1463 if (subroutine.startBlock != subroutineStart) { 1464 throw new RuntimeException ( 1465 "ret instruction returns to label " 1466 + Hex.u2 (subroutine.startBlock) 1467 + " expected: " + Hex.u2(subroutineStart)); 1468 } 1469 1470 successors = IntList.makeImmutable(subroutineSuccessor); 1471 primarySuccessor = subroutineSuccessor; 1472 } else { 1473 // Map all the successor labels 1474 1475 int origPrimary = origBlock.getPrimarySuccessor(); 1476 int sz = origSuccessors.size(); 1477 1478 successors = new IntList(sz); 1479 1480 for (int i = 0 ; i < sz ; i++) { 1481 int origSuccLabel = origSuccessors.get(i); 1482 int newSuccLabel = mapOrAllocateLabel(origSuccLabel); 1483 1484 successors.add(newSuccLabel); 1485 1486 if (origPrimary == origSuccLabel) { 1487 primarySuccessor = newSuccLabel; 1488 } 1489 } 1490 1491 successors.setImmutable(); 1492 } 1493 1494 addBlock ( 1495 new BasicBlock(newLabel, 1496 filterMoveReturnAddressInsns(origBlock.getInsns()), 1497 successors, primarySuccessor), 1498 labelToSubroutines.get(newLabel)); 1499 } 1500 1501 /** 1502 * Checks to see if a specified label is involved in a specified 1503 * subroutine. 1504 * 1505 * @param label >=0 a basic block label 1506 * @param subroutineStart >=0 a subroutine as identified by the 1507 * label of its start block. 1508 * @return true if the block is dominated by the subroutine call. 1509 */ 1510 private boolean involvedInSubroutine(int label, int subroutineStart) { 1511 IntList subroutinesList = labelToSubroutines.get(label); 1512 return (subroutinesList.size() > 0 1513 && subroutinesList.top() == subroutineStart); 1514 } 1515 1516 /** 1517 * Maps the label of a pre-copied block to the label of the inlined 1518 * block, allocating a new label and adding it to the worklist 1519 * if necessary. If the origLabel is a "special" label, it 1520 * is returned exactly and not scheduled for duplication: copying 1521 * never proceeds past a special label, which likely is the function 1522 * return block or an immediate predecessor. 1523 * 1524 * @param origLabel label of original, pre-copied block 1525 * @return label for new, inlined block 1526 */ 1527 private int mapOrAllocateLabel(int origLabel) { 1528 int resultLabel; 1529 Integer mappedLabel = origLabelToCopiedLabel.get(origLabel); 1530 1531 if (mappedLabel != null) { 1532 resultLabel = mappedLabel; 1533 } else if (!involvedInSubroutine(origLabel,subroutineStart)) { 1534 /* 1535 * A subroutine has ended by some means other than a "ret" 1536 * (which really means a throw caught later). 1537 */ 1538 resultLabel = origLabel; 1539 } else { 1540 resultLabel = labelAllocator.getNextLabel(); 1541 workList.set(origLabel); 1542 origLabelToCopiedLabel.put(origLabel, resultLabel); 1543 1544 // The new label has the same frame as the original label 1545 while (labelToSubroutines.size() <= resultLabel) { 1546 labelToSubroutines.add(null); 1547 } 1548 labelToSubroutines.set(resultLabel, 1549 labelToSubroutines.get(origLabel)); 1550 } 1551 1552 return resultLabel; 1553 } 1554 } 1555 1556 /** 1557 * Finds a <code>Subroutine<code> that is returned from by a ret in 1558 * a given block. 1559 * @param label A block that originally contained a ret instruction 1560 * @return null-ok; Subroutine or null if none was found. 1561 */ 1562 private Subroutine subroutineFromRetBlock(int label) { 1563 for (int i = subroutines.length - 1 ; i >= 0 ; i--) { 1564 if (subroutines[i] != null) { 1565 Subroutine subroutine = subroutines[i]; 1566 1567 if (subroutine.retBlocks.get(label)) { 1568 return subroutine; 1569 } 1570 } 1571 } 1572 1573 return null; 1574 } 1575 1576 1577 /** 1578 * Removes all move-return-address instructions, returning a new InsnList 1579 * if necessary. The move-return-address insns are dead code after 1580 * subroutines have been inlined. 1581 * 1582 * @param insns InsnList that may contain move-return-address insns 1583 * @return InsnList with move-return-address removed. 1584 */ 1585 private InsnList filterMoveReturnAddressInsns(InsnList insns) { 1586 int sz; 1587 int newSz = 0; 1588 1589 // First see if we need to filter, and if so what the new size will be 1590 sz = insns.size(); 1591 for (int i = 0; i < sz; i++) { 1592 if (insns.get(i).getOpcode() != Rops.MOVE_RETURN_ADDRESS) { 1593 newSz++; 1594 } 1595 } 1596 1597 if (newSz == sz) { 1598 return insns; 1599 } 1600 1601 // Make a new list without the MOVE_RETURN_ADDRESS insns 1602 InsnList newInsns = new InsnList(newSz); 1603 1604 int newIndex = 0; 1605 for (int i = 0; i < sz; i++) { 1606 Insn insn = insns.get(i); 1607 if (insn.getOpcode() != Rops.MOVE_RETURN_ADDRESS) { 1608 newInsns.set(newIndex++, insn); 1609 } 1610 } 1611 1612 newInsns.setImmutable(); 1613 return newInsns; 1614 } 1615 1616 /** 1617 * Visits each non-subroutine block once in depth-first successor order. 1618 * @param firstLabel label of start block 1619 * @param v callback interface 1620 */ 1621 private void forEachNonSubBlockDepthFirst( 1622 int firstLabel, BasicBlock.Visitor v) { 1623 1624 forEachNonSubBlockDepthFirst0(labelToBlock(firstLabel), 1625 v, new BitSet(maxLabel)); 1626 } 1627 1628 /** 1629 * Visits each block once in depth-first successor order, ignoring jsr 1630 * targets. Worker for forEachNonSubBlockDepthFirst(). 1631 * @param next next block to visit 1632 * @param v callback interface 1633 * @param visited set of blocks already visited 1634 */ 1635 private void forEachNonSubBlockDepthFirst0( 1636 BasicBlock next, BasicBlock.Visitor v, BitSet visited) { 1637 1638 v.visitBlock(next); 1639 visited.set(next.getLabel()); 1640 1641 IntList successors = next.getSuccessors(); 1642 1643 int sz = successors.size(); 1644 1645 for (int i = 0 ; i < sz ; i++) { 1646 int succ = successors.get(i); 1647 1648 if (visited.get(succ)) { 1649 continue; 1650 } 1651 1652 if (isSubroutineCaller(next) && i > 0) { 1653 // ignore jsr targets 1654 continue; 1655 } 1656 1657 /* 1658 * Ignore missing labels: they're successors of 1659 * subroutines that never invoke a ret. 1660 */ 1661 int idx = labelToResultIndex(succ); 1662 if (idx >= 0) { 1663 forEachNonSubBlockDepthFirst0(result.get(idx), v, visited); 1664 } 1665 } 1666 } 1667} 1668