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 }