jsrinlineradapter.java

asm的源码包 并且包含英文的文档

/***
 * ASM: a very small and fast Java bytecode manipulation framework
 * Copyright (c) 2000-2005 INRIA, France Telecom
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the copyright holders nor the names of its
 *    contributors may be used to endorse or promote products derived from
 *    this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
 * THE POSSIBILITY OF SUCH DAMAGE.
 */
package org.objectweb.asm.commons;

import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.objectweb.asm.Label;
import org.objectweb.asm.MethodVisitor;
import org.objectweb.asm.Opcodes;
import org.objectweb.asm.Type;
import org.objectweb.asm.tree.AbstractInsnNode;
import org.objectweb.asm.tree.InsnList;
import org.objectweb.asm.tree.InsnNode;
import org.objectweb.asm.tree.JumpInsnNode;
import org.objectweb.asm.tree.LabelNode;
import org.objectweb.asm.tree.LookupSwitchInsnNode;
import org.objectweb.asm.tree.MethodNode;
import org.objectweb.asm.tree.TableSwitchInsnNode;
import org.objectweb.asm.tree.TryCatchBlockNode;
import org.objectweb.asm.tree.LocalVariableNode;

/**
 * A {@link org.objectweb.asm.MethodAdapter} that removes JSR instructions and
 * inlines the referenced subroutines.
 * 
 * <b>Explanation of how it works</b> TODO
 * 
 * @author Niko Matsakis
 */
public class JSRInlinerAdapter extends MethodNode implements Opcodes {

    private final static boolean LOGGING = false;

    /**
     * The visitor to which we will emit a translation of this method without
     * internal subroutines.
     */
    private MethodVisitor mv;

    /**
     * For each label that is jumped to by a JSR, we create a Subroutine
     * instance. Map<LabelNode,Subroutine> is the generic type.
     */
    private final Map subroutineHeads = new HashMap();

    /**
     * This subroutine instance denotes the line of execution that is not
     * contained within any subroutine; i.e., the "subroutine" that is executing
     * when a method first begins.
     */
    private final Subroutine mainSubroutine = new Subroutine();

    /**
     * This BitSet contains the index of every instruction that belongs to more
     * than one subroutine. This should not happen often.
     */
    private final BitSet dualCitizens = new BitSet();

    /**
     * Creates a new JSRInliner.
     * 
     * @param mv the <code>MethodVisitor</code> to send the resulting inlined
     *        method code to (use <code>null</code> for none).
     * @param access the method's access flags (see {@link Opcodes}). This
     *        parameter also indicates if the method is synthetic and/or
     *        deprecated.
     * @param name the method's name.
     * @param desc the method's descriptor (see {@link Type}).
     * @param signature the method's signature. May be <tt>null</tt>.
     * @param exceptions the internal names of the method's exception classes
     *        (see {@link Type#getInternalName() getInternalName}). May be
     *        <tt>null</tt>.
     */
    public JSRInlinerAdapter(
        final MethodVisitor mv,
        final int access,
        final String name,
        final String desc,
        final String signature,
        final String[] exceptions)
    {
        super(access, name, desc, signature, exceptions);
        this.mv = mv;
    }

    /**
     * Detects a JSR instruction and sets a flag to indicate we will need to do
     * inlining.
     */
    public void visitJumpInsn(final int opcode, final Label lbl) {
        super.visitJumpInsn(opcode, lbl);
        LabelNode ln = ((JumpInsnNode) instructions.getLast()).label;
        if (opcode == JSR && !subroutineHeads.containsKey(ln)) {
            subroutineHeads.put(ln, new Subroutine());
        }
    }

    /**
     * If any JSRs were seen, triggers the inlining process. Otherwise, forwards
     * the byte codes untouched.
     */
    public void visitEnd() {
        if (!subroutineHeads.isEmpty()) {
            markSubroutines();
            if (LOGGING) {
                log(mainSubroutine.toString());
                Iterator it = subroutineHeads.values().iterator();
                while (it.hasNext()) {
                    Subroutine sub = (Subroutine) it.next();
                    log(sub.toString());
                }
            }
            emitCode();
        }

        // Forward the translate opcodes on if appropriate:
        if (mv != null) {
            accept(mv);
        }
    }

    /**
     * Walks the method and determines which internal subroutine(s), if any,
     * each instruction is a method of.
     */
    private void markSubroutines() {
        BitSet anyvisited = new BitSet();

        // First walk the main subroutine and find all those instructions which
        // can be reached without invoking any JSR at all
        markSubroutineWalk(mainSubroutine, 0, anyvisited);

        // Go through the head of each subroutine and find any nodes reachable
        // to that subroutine without following any JSR links.
        for (Iterator it = subroutineHeads.entrySet().iterator(); it.hasNext();)
        {
            Map.Entry entry = (Map.Entry) it.next();
            LabelNode lab = (LabelNode) entry.getKey();
            Subroutine sub = (Subroutine) entry.getValue();
            int index = instructions.indexOf(lab);
            markSubroutineWalk(sub, index, anyvisited);
        }
    }

    /**
     * Performs a depth first search walking the normal byte code path starting
     * at <code>index</code>, and adding each instruction encountered into
     * the subroutine <code>sub</code>. After this walk is complete, iterates
     * over the exception handlers to ensure that we also include those byte
     * codes which are reachable through an exception that may be thrown during
     * the execution of the subroutine. Invoked from
     * <code>markSubroutines()</code>.
     * 
     * @param sub TODO.
     * @param index TODO.
     * @param anyvisited TODO.
     */
    private void markSubroutineWalk(
        final Subroutine sub,
        final int index,
        final BitSet anyvisited)
    {
        if (LOGGING) {
            log("markSubroutineWalk: sub=" + sub + " index=" + index);
        }

        // First find those instructions reachable via normal execution
        markSubroutineWalkDFS(sub, index, anyvisited);

        // Now, make sure we also include any applicable exception handlers
        boolean loop = true;
        while (loop) {
            loop = false;
            for (Iterator it = tryCatchBlocks.iterator(); it.hasNext();) {
                TryCatchBlockNode trycatch = (TryCatchBlockNode) it.next();

                if (LOGGING) {
                    log("Scanning try/catch " + trycatch);
                }

                // If the handler has already been processed, skip it.
                int handlerindex = instructions.indexOf(trycatch.handler);
                if (sub.instructions.get(handlerindex)) {
                    continue;
                }

                int startindex = instructions.indexOf(trycatch.start);
                int endindex = instructions.indexOf(trycatch.end);
                int nextbit = sub.instructions.nextSetBit(startindex);
                if (nextbit != -1 && nextbit < endindex) {
                    if (LOGGING) {
                        log("Adding exception handler: " + startindex + "-"
                                + endindex + " due to " + nextbit + " handler "
                                + handlerindex);
                    }
                    markSubroutineWalkDFS(sub, handlerindex, anyvisited);
                    loop = true;
                }
            }
        }
    }

    /**
     * Performs a simple DFS of the instructions, assigning each to the
     * subroutine <code>sub</code>. Starts from <code>index</code>.
     * Invoked only by <code>markSubroutineWalk()</code>.
     * 
     * @param sub TODO.
     * @param index TODO.
     * @param anyvisited TODO.
     */
    private void markSubroutineWalkDFS(
        final Subroutine sub,
        int index,
        final BitSet anyvisited)
    {
        while (true) {
            AbstractInsnNode node = instructions.get(index);

            // don't visit a node twice
            if (sub.instructions.get(index)) {
                return;
            }
            sub.instructions.set(index);

            // check for those nodes already visited by another subroutine
            if (anyvisited.get(index)) {
                dualCitizens.set(index);
                if (LOGGING) {
                    log("Instruction #" + index + " is dual citizen.");
                }
            }
            anyvisited.set(index);

            if (node.getType() == AbstractInsnNode.JUMP_INSN
                    && node.getOpcode() != JSR)
            {
                // we do not follow recursively called subroutines here; but any
                // other sort of branch we do follow
                JumpInsnNode jnode = (JumpInsnNode) node;
                int destidx = instructions.indexOf(jnode.label);
                markSubroutineWalkDFS(sub, destidx, anyvisited);
            }
            if (node.getType() == AbstractInsnNode.TABLESWITCH_INSN) {
                TableSwitchInsnNode tsnode = (TableSwitchInsnNode) node;
                int destidx = instructions.indexOf(tsnode.dflt);
                markSubroutineWalkDFS(sub, destidx, anyvisited);
                for (int i = tsnode.labels.size() - 1; i >= 0; --i) {
                    LabelNode l = (LabelNode) tsnode.labels.get(i);
                    destidx = instructions.indexOf(l);
                    markSubroutineWalkDFS(sub, destidx, anyvisited);
                }
            }
            if (node.getType() == AbstractInsnNode.LOOKUPSWITCH_INSN) {
                LookupSwitchInsnNode lsnode = (LookupSwitchInsnNode) node;
                int destidx = instructions.indexOf(lsnode.dflt);
                markSubroutineWalkDFS(sub, destidx, anyvisited);
                for (int i = lsnode.labels.size() - 1; i >= 0; --i) {
                    LabelNode l = (LabelNode) lsnode.labels.get(i);
                    destidx = instructions.indexOf(l);
                    markSubroutineWalkDFS(sub, destidx, anyvisited);
                }
            }

            // check to see if this opcode falls through to the next instruction
            // or not; if not, return.
            switch (instructions.get(index).getOpcode()) {
                case GOTO:
                case RET:
                case TABLESWITCH:
                case LOOKUPSWITCH:
                case IRETURN:
                case LRETURN:
                case FRETURN:
                case DRETURN:
                case ARETURN:
                case RETURN:
                case ATHROW:
                    /*
                     * note: this either returns from this subroutine, or a
                     * parent subroutine which invoked it
                     */
                    return;
            }

            // Use tail recursion here in the form of an outer while loop to
            // avoid our stack growing needlessly:
            index++;
        }
    }

    /**
     * Creates the new instructions, inlining each instantiation of each
     * subroutine until the code is fully elaborated.
     */
    private void emitCode() {
        LinkedList worklist = new LinkedList();
        // Create an instantiation of the "root" subroutine, which is just the
        // main routine
        worklist.add(new Instantiation(null, mainSubroutine));

        // Emit instantiations of each subroutine we encounter, including the
        // main subroutine
        InsnList newInstructions = new InsnList();
        List newTryCatchBlocks = new ArrayList();
        List newLocalVariables = new ArrayList();
        while (!worklist.isEmpty()) {
            Instantiation inst = (Instantiation) worklist.removeFirst();
            emitSubroutine(inst,
                    worklist,
                    newInstructions,
                    newTryCatchBlocks,
                    newLocalVariables);
        }
        instructions = newInstructions;
        tryCatchBlocks = newTryCatchBlocks;
        localVariables = newLocalVariables;
    }

    /**
     * Emits one instantiation of one subroutine, specified by
     * <code>instant</code>. May add new instantiations that are invoked by
     * this one to the <code>worklist</code> parameter, and new try/catch
     * blocks to <code>newTryCatchBlocks</code>.
     *