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