1 /* 2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 3 * 4 * This code is free software; you can redistribute it and/or modify it 5 * under the terms of the GNU General Public License version 2 only, as 6 * published by the Free Software Foundation. Oracle designates this 7 * particular file as subject to the "Classpath" exception as provided 8 * by Oracle in the LICENSE file that accompanied this code. 9 * 10 * This code is distributed in the hope that it will be useful, but WITHOUT 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 13 * version 2 for more details (a copy is included in the LICENSE file that 14 * accompanied this code). 15 * 16 * You should have received a copy of the GNU General Public License version 17 * 2 along with this work; if not, write to the Free Software Foundation, 18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 19 * 20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 21 * or visit www.oracle.com if you need additional information or have any 22 * questions. 23 */ 24 25 /* 26 * This file is available under and governed by the GNU General Public 27 * License version 2 only, as published by the Free Software Foundation. 28 * However, the following notice accompanied the original version of this 29 * file: 30 * 31 * ASM: a very small and fast Java bytecode manipulation framework 32 * Copyright (c) 2000-2011 INRIA, France Telecom 33 * All rights reserved. 34 * 35 * Redistribution and use in source and binary forms, with or without 36 * modification, are permitted provided that the following conditions 37 * are met: 38 * 1. Redistributions of source code must retain the above copyright 39 * notice, this list of conditions and the following disclaimer. 40 * 2. Redistributions in binary form must reproduce the above copyright 41 * notice, this list of conditions and the following disclaimer in the 42 * documentation and/or other materials provided with the distribution. 43 * 3. Neither the name of the copyright holders nor the names of its 44 * contributors may be used to endorse or promote products derived from 45 * this software without specific prior written permission. 46 * 47 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 48 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 49 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 50 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 51 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 52 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 53 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 54 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 55 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 56 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF 57 * THE POSSIBILITY OF SUCH DAMAGE. 58 */ 59 package jdk.internal.org.objectweb.asm.commons; 60 61 import java.util.AbstractMap; 62 import java.util.ArrayList; 63 import java.util.BitSet; 64 import java.util.HashMap; 65 import java.util.Iterator; 66 import java.util.LinkedList; 67 import java.util.List; 68 import java.util.Map; 69 import java.util.Set; 70 71 import jdk.internal.org.objectweb.asm.Label; 72 import jdk.internal.org.objectweb.asm.MethodVisitor; 73 import jdk.internal.org.objectweb.asm.Opcodes; 74 import jdk.internal.org.objectweb.asm.Type; 75 import jdk.internal.org.objectweb.asm.tree.AbstractInsnNode; 76 import jdk.internal.org.objectweb.asm.tree.InsnList; 77 import jdk.internal.org.objectweb.asm.tree.InsnNode; 78 import jdk.internal.org.objectweb.asm.tree.JumpInsnNode; 79 import jdk.internal.org.objectweb.asm.tree.LabelNode; 80 import jdk.internal.org.objectweb.asm.tree.LocalVariableNode; 81 import jdk.internal.org.objectweb.asm.tree.LookupSwitchInsnNode; 82 import jdk.internal.org.objectweb.asm.tree.MethodNode; 83 import jdk.internal.org.objectweb.asm.tree.TableSwitchInsnNode; 84 import jdk.internal.org.objectweb.asm.tree.TryCatchBlockNode; 85 86 /** 87 * A {@link jdk.internal.org.objectweb.asm.MethodVisitor} that removes JSR instructions and 88 * inlines the referenced subroutines. 89 * 90 * <b>Explanation of how it works</b> TODO 91 * 92 * @author Niko Matsakis 93 */ 94 public class JSRInlinerAdapter extends MethodNode implements Opcodes { 95 96 private static final boolean LOGGING = false; 97 98 /** 99 * For each label that is jumped to by a JSR, we create a BitSet instance. 100 */ 101 private final Map<LabelNode, BitSet> subroutineHeads = new HashMap<LabelNode, BitSet>(); 102 103 /** 104 * This subroutine instance denotes the line of execution that is not 105 * contained within any subroutine; i.e., the "subroutine" that is executing 106 * when a method first begins. 107 */ 108 private final BitSet mainSubroutine = new BitSet(); 109 110 /** 111 * This BitSet contains the index of every instruction that belongs to more 112 * than one subroutine. This should not happen often. 113 */ 114 final BitSet dualCitizens = new BitSet(); 115 116 /** 117 * Creates a new JSRInliner. <i>Subclasses must not use this 118 * constructor</i>. Instead, they must use the 119 * {@link #JSRInlinerAdapter(int, MethodVisitor, int, String, String, String, String[])} 120 * version. 121 * 122 * @param mv 123 * the <code>MethodVisitor</code> to send the resulting inlined 124 * method code to (use <code>null</code> for none). 125 * @param access 126 * the method's access flags (see {@link Opcodes}). This 127 * parameter also indicates if the method is synthetic and/or 128 * deprecated. 129 * @param name 130 * the method's name. 131 * @param desc 132 * the method's descriptor (see {@link Type}). 133 * @param signature 134 * the method's signature. May be <tt>null</tt>. 135 * @param exceptions 136 * the internal names of the method's exception classes (see 137 * {@link Type#getInternalName() getInternalName}). May be 138 * <tt>null</tt>. 139 * @throws IllegalStateException 140 * If a subclass calls this constructor. 141 */ 142 public JSRInlinerAdapter(final MethodVisitor mv, final int access, 143 final String name, final String desc, final String signature, 144 final String[] exceptions) { 145 this(Opcodes.ASM5, mv, access, name, desc, signature, exceptions); 146 if (getClass() != JSRInlinerAdapter.class) { 147 throw new IllegalStateException(); 148 } 149 } 150 151 /** 152 * Creates a new JSRInliner. 153 * 154 * @param api 155 * the ASM API version implemented by this visitor. Must be one 156 * of {@link Opcodes#ASM4} or {@link Opcodes#ASM5}. 157 * @param mv 158 * the <code>MethodVisitor</code> to send the resulting inlined 159 * method code to (use <code>null</code> for none). 160 * @param access 161 * the method's access flags (see {@link Opcodes}). This 162 * parameter also indicates if the method is synthetic and/or 163 * deprecated. 164 * @param name 165 * the method's name. 166 * @param desc 167 * the method's descriptor (see {@link Type}). 168 * @param signature 169 * the method's signature. May be <tt>null</tt>. 170 * @param exceptions 171 * the internal names of the method's exception classes (see 172 * {@link Type#getInternalName() getInternalName}). May be 173 * <tt>null</tt>. 174 */ 175 protected JSRInlinerAdapter(final int api, final MethodVisitor mv, 176 final int access, final String name, final String desc, 177 final String signature, final String[] exceptions) { 178 super(api, access, name, desc, signature, exceptions); 179 this.mv = mv; 180 } 181 182 /** 183 * Detects a JSR instruction and sets a flag to indicate we will need to do 184 * inlining. 185 */ 186 @Override 187 public void visitJumpInsn(final int opcode, final Label lbl) { 188 super.visitJumpInsn(opcode, lbl); 189 LabelNode ln = ((JumpInsnNode) instructions.getLast()).label; 190 if (opcode == JSR && !subroutineHeads.containsKey(ln)) { 191 subroutineHeads.put(ln, new BitSet()); 192 } 193 } 194 195 /** 196 * If any JSRs were seen, triggers the inlining process. Otherwise, forwards 197 * the byte codes untouched. 198 */ 199 @Override 200 public void visitEnd() { 201 if (!subroutineHeads.isEmpty()) { 202 markSubroutines(); 203 if (LOGGING) { 204 log(mainSubroutine.toString()); 205 Iterator<BitSet> it = subroutineHeads.values().iterator(); 206 while (it.hasNext()) { 207 BitSet sub = it.next(); 208 log(sub.toString()); 209 } 210 } 211 emitCode(); 212 } 213 214 // Forward the translate opcodes on if appropriate: 215 if (mv != null) { 216 accept(mv); 217 } 218 } 219 220 /** 221 * Walks the method and determines which internal subroutine(s), if any, 222 * each instruction is a method of. 223 */ 224 private void markSubroutines() { 225 BitSet anyvisited = new BitSet(); 226 227 // First walk the main subroutine and find all those instructions which 228 // can be reached without invoking any JSR at all 229 markSubroutineWalk(mainSubroutine, 0, anyvisited); 230 231 // Go through the head of each subroutine and find any nodes reachable 232 // to that subroutine without following any JSR links. 233 for (Iterator<Map.Entry<LabelNode, BitSet>> it = subroutineHeads 234 .entrySet().iterator(); it.hasNext();) { 235 Map.Entry<LabelNode, BitSet> entry = it.next(); 236 LabelNode lab = entry.getKey(); 237 BitSet sub = entry.getValue(); 238 int index = instructions.indexOf(lab); 239 markSubroutineWalk(sub, index, anyvisited); 240 } 241 } 242 243 /** 244 * Performs a depth first search walking the normal byte code path starting 245 * at <code>index</code>, and adding each instruction encountered into the 246 * subroutine <code>sub</code>. After this walk is complete, iterates over 247 * the exception handlers to ensure that we also include those byte codes 248 * which are reachable through an exception that may be thrown during the 249 * execution of the subroutine. Invoked from <code>markSubroutines()</code>. 250 * 251 * @param sub 252 * the subroutine whose instructions must be computed. 253 * @param index 254 * an instruction of this subroutine. 255 * @param anyvisited 256 * indexes of the already visited instructions, i.e. marked as 257 * part of this subroutine or any previously computed subroutine. 258 */ 259 private void markSubroutineWalk(final BitSet sub, final int index, 260 final BitSet anyvisited) { 261 if (LOGGING) { 262 log("markSubroutineWalk: sub=" + sub + " index=" + index); 263 } 264 265 // First find those instructions reachable via normal execution 266 markSubroutineWalkDFS(sub, index, anyvisited); 267 268 // Now, make sure we also include any applicable exception handlers 269 boolean loop = true; 270 while (loop) { 271 loop = false; 272 for (Iterator<TryCatchBlockNode> it = tryCatchBlocks.iterator(); it 273 .hasNext();) { 274 TryCatchBlockNode trycatch = it.next(); 275 276 if (LOGGING) { 277 // TODO use of default toString(). 278 log("Scanning try/catch " + trycatch); 279 } 280 281 // If the handler has already been processed, skip it. 282 int handlerindex = instructions.indexOf(trycatch.handler); 283 if (sub.get(handlerindex)) { 284 continue; 285 } 286 287 int startindex = instructions.indexOf(trycatch.start); 288 int endindex = instructions.indexOf(trycatch.end); 289 int nextbit = sub.nextSetBit(startindex); 290 if (nextbit != -1 && nextbit < endindex) { 291 if (LOGGING) { 292 log("Adding exception handler: " + startindex + '-' 293 + endindex + " due to " + nextbit + " handler " 294 + handlerindex); 295 } 296 markSubroutineWalkDFS(sub, handlerindex, anyvisited); 297 loop = true; 298 } 299 } 300 } 301 } 302 303 /** 304 * Performs a simple DFS of the instructions, assigning each to the 305 * subroutine <code>sub</code>. Starts from <code>index</code>. Invoked only 306 * by <code>markSubroutineWalk()</code>. 307 * 308 * @param sub 309 * the subroutine whose instructions must be computed. 310 * @param index 311 * an instruction of this subroutine. 312 * @param anyvisited 313 * indexes of the already visited instructions, i.e. marked as 314 * part of this subroutine or any previously computed subroutine. 315 */ 316 private void markSubroutineWalkDFS(final BitSet sub, int index, 317 final BitSet anyvisited) { 318 while (true) { 319 AbstractInsnNode node = instructions.get(index); 320 321 // don't visit a node twice 322 if (sub.get(index)) { 323 return; 324 } 325 sub.set(index); 326 327 // check for those nodes already visited by another subroutine 328 if (anyvisited.get(index)) { 329 dualCitizens.set(index); 330 if (LOGGING) { 331 log("Instruction #" + index + " is dual citizen."); 332 } 333 } 334 anyvisited.set(index); 335 336 if (node.getType() == AbstractInsnNode.JUMP_INSN 337 && node.getOpcode() != JSR) { 338 // we do not follow recursively called subroutines here; but any 339 // other sort of branch we do follow 340 JumpInsnNode jnode = (JumpInsnNode) node; 341 int destidx = instructions.indexOf(jnode.label); 342 markSubroutineWalkDFS(sub, destidx, anyvisited); 343 } 344 if (node.getType() == AbstractInsnNode.TABLESWITCH_INSN) { 345 TableSwitchInsnNode tsnode = (TableSwitchInsnNode) node; 346 int destidx = instructions.indexOf(tsnode.dflt); 347 markSubroutineWalkDFS(sub, destidx, anyvisited); 348 for (int i = tsnode.labels.size() - 1; i >= 0; --i) { 349 LabelNode l = tsnode.labels.get(i); 350 destidx = instructions.indexOf(l); 351 markSubroutineWalkDFS(sub, destidx, anyvisited); 352 } 353 } 354 if (node.getType() == AbstractInsnNode.LOOKUPSWITCH_INSN) { 355 LookupSwitchInsnNode lsnode = (LookupSwitchInsnNode) node; 356 int destidx = instructions.indexOf(lsnode.dflt); 357 markSubroutineWalkDFS(sub, destidx, anyvisited); 358 for (int i = lsnode.labels.size() - 1; i >= 0; --i) { 359 LabelNode l = lsnode.labels.get(i); 360 destidx = instructions.indexOf(l); 361 markSubroutineWalkDFS(sub, destidx, anyvisited); 362 } 363 } 364 365 // check to see if this opcode falls through to the next instruction 366 // or not; if not, return. 367 switch (instructions.get(index).getOpcode()) { 368 case GOTO: 369 case RET: 370 case TABLESWITCH: 371 case LOOKUPSWITCH: 372 case IRETURN: 373 case LRETURN: 374 case FRETURN: 375 case DRETURN: 376 case ARETURN: 377 case RETURN: 378 case ATHROW: 379 /* 380 * note: this either returns from this subroutine, or a parent 381 * subroutine which invoked it 382 */ 383 return; 384 } 385 386 // Use tail recursion here in the form of an outer while loop to 387 // avoid our stack growing needlessly: 388 index++; 389 390 // We implicitly assumed above that execution can always fall 391 // through to the next instruction after a JSR. But a subroutine may 392 // never return, in which case the code after the JSR is unreachable 393 // and can be anything. In particular, it can seem to fall off the 394 // end of the method, so we must handle this case here (we could 395 // instead detect whether execution can return or not from a JSR, 396 // but this is more complicated). 397 if (index >= instructions.size()) { 398 return; 399 } 400 } 401 } 402 403 /** 404 * Creates the new instructions, inlining each instantiation of each 405 * subroutine until the code is fully elaborated. 406 */ 407 private void emitCode() { 408 LinkedList<Instantiation> worklist = new LinkedList<Instantiation>(); 409 // Create an instantiation of the "root" subroutine, which is just the 410 // main routine 411 worklist.add(new Instantiation(null, mainSubroutine)); 412 413 // Emit instantiations of each subroutine we encounter, including the 414 // main subroutine 415 InsnList newInstructions = new InsnList(); 416 List<TryCatchBlockNode> newTryCatchBlocks = new ArrayList<TryCatchBlockNode>(); 417 List<LocalVariableNode> newLocalVariables = new ArrayList<LocalVariableNode>(); 418 while (!worklist.isEmpty()) { 419 Instantiation inst = worklist.removeFirst(); 420 emitSubroutine(inst, worklist, newInstructions, newTryCatchBlocks, 421 newLocalVariables); 422 } 423 instructions = newInstructions; 424 tryCatchBlocks = newTryCatchBlocks; 425 localVariables = newLocalVariables; 426 } 427 428 /** 429 * Emits one instantiation of one subroutine, specified by 430 * <code>instant</code>. May add new instantiations that are invoked by this 431 * one to the <code>worklist</code> parameter, and new try/catch blocks to 432 * <code>newTryCatchBlocks</code>. 433 * 434 * @param instant 435 * the instantiation that must be performed. 436 * @param worklist 437 * list of the instantiations that remain to be done. 438 * @param newInstructions 439 * the instruction list to which the instantiated code must be 440 * appended. 441 * @param newTryCatchBlocks 442 * the exception handler list to which the instantiated handlers 443 * must be appended. 444 */ 445 private void emitSubroutine(final Instantiation instant, 446 final List<Instantiation> worklist, final InsnList newInstructions, 447 final List<TryCatchBlockNode> newTryCatchBlocks, 448 final List<LocalVariableNode> newLocalVariables) { 449 LabelNode duplbl = null; 450 451 if (LOGGING) { 452 log("--------------------------------------------------------"); 453 log("Emitting instantiation of subroutine " + instant.subroutine); 454 } 455 456 // Emit the relevant instructions for this instantiation, translating 457 // labels and jump targets as we go: 458 for (int i = 0, c = instructions.size(); i < c; i++) { 459 AbstractInsnNode insn = instructions.get(i); 460 Instantiation owner = instant.findOwner(i); 461 462 // Always remap labels: 463 if (insn.getType() == AbstractInsnNode.LABEL) { 464 // Translate labels into their renamed equivalents. 465 // Avoid adding the same label more than once. Note 466 // that because we own this instruction the gotoTable 467 // and the rangeTable will always agree. 468 LabelNode ilbl = (LabelNode) insn; 469 LabelNode remap = instant.rangeLabel(ilbl); 470 if (LOGGING) { 471 // TODO use of default toString(). 472 log("Translating lbl #" + i + ':' + ilbl + " to " + remap); 473 } 474 if (remap != duplbl) { 475 newInstructions.add(remap); 476 duplbl = remap; 477 } 478 continue; 479 } 480 481 // We don't want to emit instructions that were already 482 // emitted by a subroutine higher on the stack. Note that 483 // it is still possible for a given instruction to be 484 // emitted twice because it may belong to two subroutines 485 // that do not invoke each other. 486 if (owner != instant) { 487 continue; 488 } 489 490 if (LOGGING) { 491 log("Emitting inst #" + i); 492 } 493 494 if (insn.getOpcode() == RET) { 495 // Translate RET instruction(s) to a jump to the return label 496 // for the appropriate instantiation. The problem is that the 497 // subroutine may "fall through" to the ret of a parent 498 // subroutine; therefore, to find the appropriate ret label we 499 // find the lowest subroutine on the stack that claims to own 500 // this instruction. See the class javadoc comment for an 501 // explanation on why this technique is safe (note: it is only 502 // safe if the input is verifiable). 503 LabelNode retlabel = null; 504 for (Instantiation p = instant; p != null; p = p.previous) { 505 if (p.subroutine.get(i)) { 506 retlabel = p.returnLabel; 507 } 508 } 509 if (retlabel == null) { 510 // This is only possible if the mainSubroutine owns a RET 511 // instruction, which should never happen for verifiable 512 // code. 513 throw new RuntimeException("Instruction #" + i 514 + " is a RET not owned by any subroutine"); 515 } 516 newInstructions.add(new JumpInsnNode(GOTO, retlabel)); 517 } else if (insn.getOpcode() == JSR) { 518 LabelNode lbl = ((JumpInsnNode) insn).label; 519 BitSet sub = subroutineHeads.get(lbl); 520 Instantiation newinst = new Instantiation(instant, sub); 521 LabelNode startlbl = newinst.gotoLabel(lbl); 522 523 if (LOGGING) { 524 log(" Creating instantiation of subr " + sub); 525 } 526 527 // Rather than JSRing, we will jump to the inline version and 528 // push NULL for what was once the return value. This hack 529 // allows us to avoid doing any sort of data flow analysis to 530 // figure out which instructions manipulate the old return value 531 // pointer which is now known to be unneeded. 532 newInstructions.add(new InsnNode(ACONST_NULL)); 533 newInstructions.add(new JumpInsnNode(GOTO, startlbl)); 534 newInstructions.add(newinst.returnLabel); 535 536 // Insert this new instantiation into the queue to be emitted 537 // later. 538 worklist.add(newinst); 539 } else { 540 newInstructions.add(insn.clone(instant)); 541 } 542 } 543 544 // Emit try/catch blocks that are relevant to this method. 545 for (Iterator<TryCatchBlockNode> it = tryCatchBlocks.iterator(); it 546 .hasNext();) { 547 TryCatchBlockNode trycatch = it.next(); 548 549 if (LOGGING) { 550 // TODO use of default toString(). 551 log("try catch block original labels=" + trycatch.start + '-' 552 + trycatch.end + "->" + trycatch.handler); 553 } 554 555 final LabelNode start = instant.rangeLabel(trycatch.start); 556 final LabelNode end = instant.rangeLabel(trycatch.end); 557 558 // Ignore empty try/catch regions 559 if (start == end) { 560 if (LOGGING) { 561 log(" try catch block empty in this subroutine"); 562 } 563 continue; 564 } 565 566 final LabelNode handler = instant.gotoLabel(trycatch.handler); 567 568 if (LOGGING) { 569 // TODO use of default toString(). 570 log(" try catch block new labels=" + start + '-' + end + "->" 571 + handler); 572 } 573 574 if (start == null || end == null || handler == null) { 575 throw new RuntimeException("Internal error!"); 576 } 577 578 newTryCatchBlocks.add(new TryCatchBlockNode(start, end, handler, 579 trycatch.type)); 580 } 581 582 for (Iterator<LocalVariableNode> it = localVariables.iterator(); it 583 .hasNext();) { 584 LocalVariableNode lvnode = it.next(); 585 if (LOGGING) { 586 log("local var " + lvnode.name); 587 } 588 final LabelNode start = instant.rangeLabel(lvnode.start); 589 final LabelNode end = instant.rangeLabel(lvnode.end); 590 if (start == end) { 591 if (LOGGING) { 592 log(" local variable empty in this sub"); 593 } 594 continue; 595 } 596 newLocalVariables.add(new LocalVariableNode(lvnode.name, 597 lvnode.desc, lvnode.signature, start, end, lvnode.index)); 598 } 599 } 600 601 private static void log(final String str) { 602 System.err.println(str); 603 } 604 605 /** 606 * A class that represents an instantiation of a subroutine. Each 607 * instantiation has an associate "stack" --- which is a listing of those 608 * instantiations that were active when this particular instance of this 609 * subroutine was invoked. Each instantiation also has a map from the 610 * original labels of the program to the labels appropriate for this 611 * instantiation, and finally a label to return to. 612 */ 613 private class Instantiation extends AbstractMap<LabelNode, LabelNode> { 614 615 /** 616 * Previous instantiations; the stack must be statically predictable to 617 * be inlinable. 618 */ 619 final Instantiation previous; 620 621 /** 622 * The subroutine this is an instantiation of. 623 */ 624 public final BitSet subroutine; 625 626 /** 627 * This table maps Labels from the original source to Labels pointing at 628 * code specific to this instantiation, for use in remapping try/catch 629 * blocks,as well as gotos. 630 * 631 * Note that in the presence of dual citizens instructions, that is, 632 * instructions which belong to more than one subroutine due to the 633 * merging of control flow without a RET instruction, we will map the 634 * target label of a GOTO to the label used by the instantiation lowest 635 * on the stack. This avoids code duplication during inlining in most 636 * cases. 637 * 638 * @see #findOwner(int) 639 */ 640 public final Map<LabelNode, LabelNode> rangeTable = new HashMap<LabelNode, LabelNode>(); 641 642 /** 643 * All returns for this instantiation will be mapped to this label 644 */ 645 public final LabelNode returnLabel; 646 647 Instantiation(final Instantiation prev, final BitSet sub) { 648 previous = prev; 649 subroutine = sub; 650 for (Instantiation p = prev; p != null; p = p.previous) { 651 if (p.subroutine == sub) { 652 throw new RuntimeException("Recursive invocation of " + sub); 653 } 654 } 655 656 // Determine the label to return to when this subroutine terminates 657 // via RET: note that the main subroutine never terminates via RET. 658 if (prev != null) { 659 returnLabel = new LabelNode(); 660 } else { 661 returnLabel = null; 662 } 663 664 // Each instantiation will remap the labels from the code above to 665 // refer to its particular copy of its own instructions. Note that 666 // we collapse labels which point at the same instruction into one: 667 // this is fairly common as we are often ignoring large chunks of 668 // instructions, so what were previously distinct labels become 669 // duplicates. 670 LabelNode duplbl = null; 671 for (int i = 0, c = instructions.size(); i < c; i++) { 672 AbstractInsnNode insn = instructions.get(i); 673 674 if (insn.getType() == AbstractInsnNode.LABEL) { 675 LabelNode ilbl = (LabelNode) insn; 676 677 if (duplbl == null) { 678 // if we already have a label pointing at this spot, 679 // don't recreate it. 680 duplbl = new LabelNode(); 681 } 682 683 // Add an entry in the rangeTable for every label 684 // in the original code which points at the next 685 // instruction of our own to be emitted. 686 rangeTable.put(ilbl, duplbl); 687 } else if (findOwner(i) == this) { 688 // We will emit this instruction, so clear the 'duplbl' flag 689 // since the next Label will refer to a distinct 690 // instruction. 691 duplbl = null; 692 } 693 } 694 } 695 696 /** 697 * Returns the "owner" of a particular instruction relative to this 698 * instantiation: the owner referes to the Instantiation which will emit 699 * the version of this instruction that we will execute. 700 * 701 * Typically, the return value is either <code>this</code> or 702 * <code>null</code>. <code>this</code> indicates that this 703 * instantiation will generate the version of this instruction that we 704 * will execute, and <code>null</code> indicates that this instantiation 705 * never executes the given instruction. 706 * 707 * Sometimes, however, an instruction can belong to multiple 708 * subroutines; this is called a "dual citizen" instruction (though it 709 * may belong to more than 2 subroutines), and occurs when multiple 710 * subroutines branch to common points of control. In this case, the 711 * owner is the subroutine that appears lowest on the stack, and which 712 * also owns the instruction in question. 713 * 714 * @param i 715 * the index of the instruction in the original code 716 * @return the "owner" of a particular instruction relative to this 717 * instantiation. 718 */ 719 public Instantiation findOwner(final int i) { 720 if (!subroutine.get(i)) { 721 return null; 722 } 723 if (!dualCitizens.get(i)) { 724 return this; 725 } 726 Instantiation own = this; 727 for (Instantiation p = previous; p != null; p = p.previous) { 728 if (p.subroutine.get(i)) { 729 own = p; 730 } 731 } 732 return own; 733 } 734 735 /** 736 * Looks up the label <code>l</code> in the <code>gotoTable</code>, thus 737 * translating it from a Label in the original code, to a Label in the 738 * inlined code that is appropriate for use by an instruction that 739 * branched to the original label. 740 * 741 * @param l 742 * The label we will be translating 743 * @return a label for use by a branch instruction in the inlined code 744 * @see #rangeLabel 745 */ 746 public LabelNode gotoLabel(final LabelNode l) { 747 // owner should never be null, because owner is only null 748 // if an instruction cannot be reached from this subroutine 749 Instantiation owner = findOwner(instructions.indexOf(l)); 750 return owner.rangeTable.get(l); 751 } 752 753 /** 754 * Looks up the label <code>l</code> in the <code>rangeTable</code>, 755 * thus translating it from a Label in the original code, to a Label in 756 * the inlined code that is appropriate for use by an try/catch or 757 * variable use annotation. 758 * 759 * @param l 760 * The label we will be translating 761 * @return a label for use by a try/catch or variable annotation in the 762 * original code 763 * @see #rangeTable 764 */ 765 public LabelNode rangeLabel(final LabelNode l) { 766 return rangeTable.get(l); 767 } 768 769 // AbstractMap implementation 770 771 @Override 772 public Set<Map.Entry<LabelNode, LabelNode>> entrySet() { 773 return null; 774 } 775 776 @Override 777 public LabelNode get(final Object o) { 778 return gotoLabel((LabelNode) o); 779 } 780 } 781 }