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