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