dex/code/RopTranslator.java

/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dexgen.dex.code;

import com.android.dexgen.rop.code.BasicBlock;
import com.android.dexgen.rop.code.BasicBlockList;
import com.android.dexgen.rop.code.FillArrayDataInsn;
import com.android.dexgen.rop.code.Insn;
import com.android.dexgen.rop.code.LocalVariableInfo;
import com.android.dexgen.rop.code.PlainCstInsn;
import com.android.dexgen.rop.code.PlainInsn;
import com.android.dexgen.rop.code.RegOps;
import com.android.dexgen.rop.code.RegisterSpec;
import com.android.dexgen.rop.code.RegisterSpecList;
import com.android.dexgen.rop.code.RegisterSpecSet;
import com.android.dexgen.rop.code.Rop;
import com.android.dexgen.rop.code.RopMethod;
import com.android.dexgen.rop.code.SourcePosition;
import com.android.dexgen.rop.code.SwitchInsn;
import com.android.dexgen.rop.code.ThrowingCstInsn;
import com.android.dexgen.rop.code.ThrowingInsn;
import com.android.dexgen.rop.cst.Constant;
import com.android.dexgen.rop.cst.CstInteger;
import com.android.dexgen.rop.type.Type;
import com.android.dexgen.util.Bits;
import com.android.dexgen.util.IntList;

import java.util.ArrayList;

/**
 * Translator from {@link RopMethod} to {@link DalvCode}. The {@link
 * #translate} method is the thing to call on this class.
 */
public final class RopTranslator {
    /** {@code non-null;} method to translate */
    private final RopMethod method;

    /**
     * how much position info to preserve; one of the static
     * constants in {@link PositionList}
     */
    private final int positionInfo;

    /** {@code null-ok;} local variable info to use */
    private final LocalVariableInfo locals;

    /** {@code non-null;} container for all the address objects for the method */
    private final BlockAddresses addresses;

    /** {@code non-null;} list of output instructions in-progress */
    private final OutputCollector output;

    /** {@code non-null;} visitor to use during translation */
    private final TranslationVisitor translationVisitor;

    /** {@code >= 0;} register count for the method */
    private final int regCount;

    /** {@code null-ok;} block output order; becomes non-null in {@link #pickOrder} */
    private int[] order;

    /** size, in register units, of all the parameters to this method */
    private final int paramSize;

    /**
     * true if the parameters to this method happen to be in proper order
     * at the end of the frame (as the optimizer emits them)
     */
    private boolean paramsAreInOrder;

    /**
     * Translates a {@link RopMethod}. This may modify the given
     * input.
     *
     * @param method {@code non-null;} the original method
     * @param positionInfo how much position info to preserve; one of the
     * static constants in {@link PositionList}
     * @param locals {@code null-ok;} local variable information to use
     * @param paramSize size, in register units, of all the parameters to
     * this method
     * @return {@code non-null;} the translated version
     */
    public static DalvCode translate(RopMethod method, int positionInfo,
                                     LocalVariableInfo locals, int paramSize) {
        RopTranslator translator =
            new RopTranslator(method, positionInfo, locals,
                    paramSize);
        return translator.translateAndGetResult();
    }

    /**
     * Constructs an instance. This method is private. Use {@link #translate}.
     *
     * @param method {@code non-null;} the original method
     * @param positionInfo how much position info to preserve; one of the
     * static constants in {@link PositionList}
     * @param locals {@code null-ok;} local variable information to use
     * @param paramSize size, in register units, of all the parameters to
     * this method
     */
    private RopTranslator(RopMethod method, int positionInfo,
                          LocalVariableInfo locals, int paramSize) {
        this.method = method;
        this.positionInfo = positionInfo;
        this.locals = locals;
        this.addresses = new BlockAddresses(method);
        this.paramSize = paramSize;
        this.order = null;
        this.paramsAreInOrder = calculateParamsAreInOrder(method, paramSize);

        BasicBlockList blocks = method.getBlocks();
        int bsz = blocks.size();

        /*
         * Max possible instructions includes three code address
         * objects per basic block (to the first and last instruction,
         * and just past the end of the block), and the possibility of
         * an extra goto at the end of each basic block.
         */
        int maxInsns = (bsz * 3) + blocks.getInstructionCount();

        if (locals != null) {
            /*
             * If we're tracking locals, then there's could be another
             * extra instruction per block (for the locals state at the
             * start of the block) as well as one for each interblock
             * local introduction.
             */
            maxInsns += bsz + locals.getAssignmentCount();
        }

        /*
         * If params are not in order, we will need register space
         * for them before this is all over...
         */
        this.regCount = blocks.getRegCount()
                + (paramsAreInOrder ? 0 : this.paramSize);

        this.output = new OutputCollector(maxInsns, bsz * 3, regCount);

        if (locals != null) {
            this.translationVisitor =
                new LocalVariableAwareTranslationVisitor(output, locals);
        } else {
            this.translationVisitor = new TranslationVisitor(output);
        }
    }

    /**
     * Checks to see if the move-param instructions that occur in this
     * method happen to slot the params in an order at the top of the
     * stack frame that matches dalvik's calling conventions. This will
     * alway result in "true" for methods that have run through the
     * SSA optimizer.
     *
     * @param paramSize size, in register units, of all the parameters
     * to this method
     */
    private static boolean calculateParamsAreInOrder(RopMethod method,
            final int paramSize) {
        final boolean[] paramsAreInOrder = { true };
        final int initialRegCount = method.getBlocks().getRegCount();

        /*
         * We almost could just check the first block here, but the
         * {@code cf} layer will put in a second move-param in a
         * subsequent block in the case of synchronized methods.
         */
        method.getBlocks().forEachInsn(new Insn.BaseVisitor() {
            public void visitPlainCstInsn(PlainCstInsn insn) {
                if (insn.getOpcode().getOpcode()== RegOps.MOVE_PARAM) {
                    int param =
                        ((CstInteger) insn.getConstant()).getValue();

                    paramsAreInOrder[0] = paramsAreInOrder[0]
                            && ((initialRegCount - paramSize + param)
                                == insn.getResult().getReg());
                }
            }
        });

        return paramsAreInOrder[0];
    }

    /**
     * Does the translation and returns the result.
     *
     * @return {@code non-null;} the result
     */
    private DalvCode translateAndGetResult() {
        pickOrder();
        outputInstructions();

        StdCatchBuilder catches =
            new StdCatchBuilder(method, order, addresses);

        return new DalvCode(positionInfo, output.getFinisher(), catches);
    }

    /**
     * Performs initial creation of output instructions based on the
     * original blocks.
     */
    private void outputInstructions() {
        BasicBlockList blocks = method.getBlocks();
        int[] order = this.order;
        int len = order.length;

        // Process the blocks in output order.
        for (int i = 0; i < len; i++) {
            int nextI = i + 1;
            int nextLabel = (nextI == order.length) ? -1 : order[nextI];
            outputBlock(blocks.labelToBlock(order[i]), nextLabel);
        }
    }

    /**
     * Helper for {@link #outputInstructions}, which does the processing
     * and output of one block.
     *
     * @param block {@code non-null;} the block to process and output
     * @param nextLabel {@code >= -1;} the next block that will be processed, or
     * {@code -1} if there is no next block
     */
    private void outputBlock(BasicBlock block, int nextLabel) {
        // Append the code address for this block.
        CodeAddress startAddress = addresses.getStart(block);
        output.add(startAddress);

        // Append the local variable state for the block.
        if (locals != null) {
            RegisterSpecSet starts = locals.getStarts(block);
            output.add(new LocalSnapshot(startAddress.getPosition(),
                                         starts));
        }

        /*
         * Choose and append an output instruction for each original
         * instruction.
         */
        translationVisitor.setBlock(block, addresses.getLast(block));
        block.getInsns().forEach(translationVisitor);

        // Insert the block end code address.
        output.add(addresses.getEnd(block));

        // Set up for end-of-block activities.

        int succ = block.getPrimarySuccessor();
        Insn lastInsn = block.getLastInsn();

        /*
         * Check for (and possibly correct for) a non-optimal choice of
         * which block will get output next.
         */

        if ((succ >= 0) && (succ != nextLabel)) {
            /*
             * The block has a "primary successor" and that primary
             * successor isn't the next block to be output.
             */
            Rop lastRop = lastInsn.getOpcode();
            if ((lastRop.getBranchingness() == Rop.BRANCH_IF) &&
                    (block.getSecondarySuccessor() == nextLabel)) {
                /*
                 * The block ends with an "if" of some sort, and its
                 * secondary successor (the "then") is in fact the
                 * next block to output. So, reverse the sense of
                 * the test, so that we can just emit the next block
                 * without an interstitial goto.
                 */
                output.reverseBranch(1, addresses.getStart(succ));
            } else {
                /*
                 * Our only recourse is to add a goto here to get the
                 * flow to be correct.
                 */
                TargetInsn insn =
                    new TargetInsn(Dops.GOTO, lastInsn.getPosition(),
                            RegisterSpecList.EMPTY,
                            addresses.getStart(succ));
                output.add(insn);
            }
        }
    }

    /**
     * Picks an order for the blocks by doing "trace" analysis.
     */
    private void pickOrder() {
        BasicBlockList blocks = method.getBlocks();
        int sz = blocks.size();
        int maxLabel = blocks.getMaxLabel();
        int[] workSet = Bits.makeBitSet(maxLabel);
        int[] tracebackSet = Bits.makeBitSet(maxLabel);

        for (int i = 0; i < sz; i++) {
            BasicBlock one = blocks.get(i);
            Bits.set(workSet, one.getLabel());
        }

        int[] order = new int[sz];
        int at = 0;

        /*
         * Starting with the designated "first label" (that is, the
         * first block of the method), add that label to the order,
         * and then pick its first as-yet unordered successor to
         * immediately follow it, giving top priority to the primary
         * (aka default) successor (if any). Keep following successors
         * until the trace runs out of possibilities. Then, continue
         * by finding an unordered chain containing the first as-yet
         * unordered block, and adding it to the order, and so on.
         */
        for (int label = method.getFirstLabel();
             label != -1;
             label = Bits.findFirst(workSet, 0)) {

            /*
             * Attempt to trace backward from the chosen block to an
             * as-yet unordered predecessor which lists the chosen
             * block as its primary successor, and so on, until we
             * fail to find such an unordered predecessor. Start the
             * trace with that block. Note that the first block in the
             * method has no predecessors, so in that case this loop
             * will simply terminate with zero iterations and without
             * picking a new starter block.
             */
            traceBack:
            for (;;) {
                IntList preds = method.labelToPredecessors(label);
                int psz = preds.size();

                for (int i = 0; i < psz; i++) {
                    int predLabel = preds.get(i);

                    if (Bits.get(tracebackSet, predLabel)) {
                        /*
                         * We found a predecessor loop; stop tracing back
                         * from here.
                         */
                        break;
                    }

                    if (!Bits.get(workSet, predLabel)) {
                        // This one's already ordered.
                        continue;
                    }

                    BasicBlock pred = blocks.labelToBlock(predLabel);
                    if (pred.getPrimarySuccessor() == label) {
                        // Found one!
                        label = predLabel;
                        Bits.set(tracebackSet, label);
                        continue traceBack;
                    }
                }

                // Failed to find a better block to start the trace.
                break;
            }

            /*
             * Trace a path from the chosen block to one of its
             * unordered successors (hopefully the primary), and so
             * on, until we run out of unordered successors.
             */
            while (label != -1) {
                Bits.clear(workSet, label);
                Bits.clear(tracebackSet, label);
                order[at] = label;
                at++;

                BasicBlock one = blocks.labelToBlock(label);
                BasicBlock preferredBlock = blocks.preferredSuccessorOf(one);

                if (preferredBlock == null) {
                    break;
                }

                int preferred = preferredBlock.getLabel();
                int primary = one.getPrimarySuccessor();

                if (Bits.get(workSet, preferred)) {
                    /*
                     * Order the current block's preferred successor
                     * next, as it has yet to be scheduled.
                     */
                    label = preferred;
                } else if ((primary != preferred) && (primary >= 0)
                        && Bits.get(workSet, primary)) {
                    /*
                     * The primary is available, so use that.
                     */
                    label = primary;
                } else {
                    /*
                     * There's no obvious candidate, so pick the first
                     * one that's available, if any.
                     */
                    IntList successors = one.getSuccessors();
                    int ssz = successors.size();
                    label = -1;
                    for (int i = 0; i < ssz; i++) {
                        int candidate = successors.get(i);
                        if (Bits.get(workSet, candidate)) {
                            label = candidate;
                            break;
                        }
                    }
                }
            }
        }

        if (at != sz) {
            // There was a duplicate block label.
            throw new RuntimeException("shouldn't happen");
        }

        this.order = order;
    }

    /**
     * Gets the complete register list (result and sources) out of a
     * given rop instruction. For insns that are commutative, have
     * two register sources, and have a source equal to the result,
     * place that source first.
     *
     * @param insn {@code non-null;} instruction in question
     * @return {@code non-null;} the instruction's complete register list
     */
    private static RegisterSpecList getRegs(Insn insn) {
        return getRegs(insn, insn.getResult());
    }

    /**
     * Gets the complete register list (result and sources) out of a
     * given rop instruction. For insns that are commutative, have
     * two register sources, and have a source equal to the result,
     * place that source first.
     *
     * @param insn {@code non-null;} instruction in question
     * @param resultReg {@code null-ok;} the real result to use (ignore the insn's)
     * @return {@code non-null;} the instruction's complete register list
     */
    private static RegisterSpecList getRegs(Insn insn,
            RegisterSpec resultReg) {
        RegisterSpecList regs = insn.getSources();

        if (insn.getOpcode().isCommutative()
                && (regs.size() == 2)
                && (resultReg.getReg() == regs.get(1).getReg())) {

            /*
             * For commutative ops which have two register sources,
             * if the second source is the same register as the result,
             * swap the sources so that an opcode of form 12x can be selected
             * instead of one of form 23x
             */

            regs = RegisterSpecList.make(regs.get(1), regs.get(0));
        }

        if (resultReg == null) {
            return regs;
        }

        return regs.withFirst(resultReg);
    }

    /**
     * Instruction visitor class for doing the instruction translation per se.
     */
    private class TranslationVisitor implements Insn.Visitor {
        /** {@code non-null;} list of output instructions in-progress */
        private final OutputCollector output;

        /** {@code non-null;} basic block being worked on */
        private BasicBlock block;

        /**
         * {@code null-ok;} code address for the salient last instruction of the
         * block (used before switches and throwing instructions)
         */
        private CodeAddress lastAddress;

        /**
         * Constructs an instance.
         *
         * @param output {@code non-null;} destination for instruction output
         */
        public TranslationVisitor(OutputCollector output) {
            this.output = output;
        }

        /**
         * Sets the block currently being worked on.
         *
         * @param block {@code non-null;} the block
         * @param lastAddress {@code non-null;} code address for the salient
         * last instruction of the block
         */
        public void setBlock(BasicBlock block, CodeAddress lastAddress) {
            this.block = block;
            this.lastAddress = lastAddress;
        }

        /** {@inheritDoc} */
        public void visitPlainInsn(PlainInsn insn) {
            Rop rop = insn.getOpcode();
            if (rop.getOpcode() == RegOps.MARK_LOCAL) {
                /*
                 * Ignore these. They're dealt with by
                 * the LocalVariableAwareTranslationVisitor
                 */
                return;
            }
            if (rop.getOpcode() == RegOps.MOVE_RESULT_PSEUDO) {
                // These get skipped
                return;
            }

            SourcePosition pos = insn.getPosition();
            Dop opcode = RopToDop.dopFor(insn);
            DalvInsn di;

            switch (rop.getBranchingness()) {
                case Rop.BRANCH_NONE:
                case Rop.BRANCH_RETURN:
                case Rop.BRANCH_THROW: {
                    di = new SimpleInsn(opcode, pos, getRegs(insn));
                    break;
                }
                case Rop.BRANCH_GOTO: {
                    /*
                     * Code in the main translation loop will emit a
                     * goto if necessary (if the branch isn't to the
                     * immediately subsequent block).
                     */
                    return;
                }
                case Rop.BRANCH_IF: {
                    int target = block.getSuccessors().get(1);
                    di = new TargetInsn(opcode, pos, getRegs(insn),
                                        addresses.getStart(target));
                    break;
                }
                default: {
                    throw new RuntimeException("shouldn't happen");
                }
            }

            addOutput(di);
        }

        /** {@inheritDoc} */
        public void visitPlainCstInsn(PlainCstInsn insn) {
            SourcePosition pos = insn.getPosition();
            Dop opcode = RopToDop.dopFor(insn);
            Rop rop = insn.getOpcode();
            int ropOpcode = rop.getOpcode();
            DalvInsn di;

            if (rop.getBranchingness() != Rop.BRANCH_NONE) {
                throw new RuntimeException("shouldn't happen");
            }

            if (ropOpcode == RegOps.MOVE_PARAM) {
                if (!paramsAreInOrder) {
                    /*
                     * Parameters are not in order at the top of the reg space.
                     * We need to add moves.
                     */

                    RegisterSpec dest = insn.getResult();
                    int param =
                        ((CstInteger) insn.getConstant()).getValue();
                    RegisterSpec source =
                        RegisterSpec.make(regCount - paramSize + param,
                                dest.getType());
                    di = new SimpleInsn(opcode, pos,
                                        RegisterSpecList.make(dest, source));
                    addOutput(di);
                }
            } else {
                // No moves required for the parameters
                RegisterSpecList regs = getRegs(insn);
                di = new CstInsn(opcode, pos, regs, insn.getConstant());
                addOutput(di);
            }
        }

        /** {@inheritDoc} */
        public void visitSwitchInsn(SwitchInsn insn) {
            SourcePosition pos = insn.getPosition();
            IntList cases = insn.getCases();
            IntList successors = block.getSuccessors();
            int casesSz = cases.size();
            int succSz = successors.size();
            int primarySuccessor = block.getPrimarySuccessor();

            /*
             * Check the assumptions that the number of cases is one
             * less than the number of successors and that the last
             * successor in the list is the primary (in this case, the
             * default). This test is here to guard against forgetting
             * to change this code if the way switch instructions are
             * constructed also gets changed.
             */
            if ((casesSz != (succSz - 1)) ||
                (primarySuccessor != successors.get(casesSz))) {
                throw new RuntimeException("shouldn't happen");
            }

            CodeAddress[] switchTargets = new CodeAddress[casesSz];

            for (int i = 0; i < casesSz; i++) {
                int label = successors.get(i);
                switchTargets[i] = addresses.getStart(label);
            }

            CodeAddress dataAddress = new CodeAddress(pos);
            SwitchData dataInsn =
                new SwitchData(pos, lastAddress, cases, switchTargets);
            Dop opcode = dataInsn.isPacked() ?
                Dops.PACKED_SWITCH : Dops.SPARSE_SWITCH;
            TargetInsn switchInsn =
                new TargetInsn(opcode, pos, getRegs(insn), dataAddress);

            addOutput(lastAddress);
            addOutput(switchInsn);

            addOutputSuffix(new OddSpacer(pos));
            addOutputSuffix(dataAddress);
            addOutputSuffix(dataInsn);
        }

        /**
         * Looks forward to the current block's primary successor, returning
         * the RegisterSpec of the result of the move-result-pseudo at the
         * top of that block or null if none.
         *
         * @return {@code null-ok;} result of move-result-pseudo at the beginning of
         * primary successor
         */
        private RegisterSpec getNextMoveResultPseudo()
        {
            int label = block.getPrimarySuccessor();

            if (label < 0) {
                return null;
            }

            Insn insn
                    = method.getBlocks().labelToBlock(label).getInsns().get(0);

            if (insn.getOpcode().getOpcode() != RegOps.MOVE_RESULT_PSEUDO) {
                return null;
            } else {
                return insn.getResult();
            }
        }

        /** {@inheritDoc} */
        public void visitThrowingCstInsn(ThrowingCstInsn insn) {
            SourcePosition pos = insn.getPosition();
            Dop opcode = RopToDop.dopFor(insn);
            Rop rop = insn.getOpcode();
            Constant cst = insn.getConstant();

            if (rop.getBranchingness() != Rop.BRANCH_THROW) {
                throw new RuntimeException("shouldn't happen");
            }

            addOutput(lastAddress);

            if (rop.isCallLike()) {
                RegisterSpecList regs = insn.getSources();
                DalvInsn di = new CstInsn(opcode, pos, regs, cst);

                addOutput(di);
            } else {
                RegisterSpec realResult = getNextMoveResultPseudo();

                RegisterSpecList regs = getRegs(insn, realResult);
                DalvInsn di;

                boolean hasResult = opcode.hasResult()
                        || (rop.getOpcode() == RegOps.CHECK_CAST);

                if (hasResult != (realResult != null)) {
                    throw new RuntimeException(
                            "Insn with result/move-result-pseudo mismatch " +
                            insn);
                }

                if ((rop.getOpcode() == RegOps.NEW_ARRAY) &&
                    (opcode.getOpcode() != DalvOps.NEW_ARRAY)) {
                    /*
                     * It's a type-specific new-array-<primitive>, and
                     * so it should be turned into a SimpleInsn (no
                     * constant ref as it's implicit).
                     */
                    di = new SimpleInsn(opcode, pos, regs);
                } else {
                    /*
                     * This is the general case for constant-bearing
                     * instructions.
                     */
                    di = new CstInsn(opcode, pos, regs, cst);
                }

                addOutput(di);
            }
        }

        /** {@inheritDoc} */
        public void visitThrowingInsn(ThrowingInsn insn) {
            SourcePosition pos = insn.getPosition();
            Dop opcode = RopToDop.dopFor(insn);
            Rop rop = insn.getOpcode();
            RegisterSpec realResult;

            if (rop.getBranchingness() != Rop.BRANCH_THROW) {
                throw new RuntimeException("shouldn't happen");
            }

            realResult = getNextMoveResultPseudo();

            if (opcode.hasResult() != (realResult != null)) {
                throw new RuntimeException(
                        "Insn with result/move-result-pseudo mismatch" + insn);
            }

            addOutput(lastAddress);

            DalvInsn di = new SimpleInsn(opcode, pos,
                    getRegs(insn, realResult));

            addOutput(di);
        }

        /** {@inheritDoc} */
        public void visitFillArrayDataInsn(FillArrayDataInsn insn) {
            SourcePosition pos = insn.getPosition();
            Constant cst = insn.getConstant();
            ArrayList<Constant> values = insn.getInitValues();
            Rop rop = insn.getOpcode();

            if (rop.getBranchingness() != Rop.BRANCH_NONE) {
                throw new RuntimeException("shouldn't happen");
            }
            CodeAddress dataAddress = new CodeAddress(pos);
            ArrayData dataInsn =
                new ArrayData(pos, lastAddress, values, cst);

            TargetInsn fillArrayDataInsn =
                new TargetInsn(Dops.FILL_ARRAY_DATA, pos, getRegs(insn),
                        dataAddress);

            addOutput(lastAddress);
            addOutput(fillArrayDataInsn);

            addOutputSuffix(new OddSpacer(pos));
            addOutputSuffix(dataAddress);
            addOutputSuffix(dataInsn);
        }

        /**
         * Adds to the output.
         *
         * @param insn {@code non-null;} instruction to add
         */
        protected void addOutput(DalvInsn insn) {
            output.add(insn);
        }

        /**
         * Adds to the output suffix.
         *
         * @param insn {@code non-null;} instruction to add
         */
        protected void addOutputSuffix(DalvInsn insn) {
            output.addSuffix(insn);
        }
    }

    /**
     * Instruction visitor class for doing instruction translation with
     * local variable tracking
     */
    private class LocalVariableAwareTranslationVisitor
            extends TranslationVisitor {
        /** {@code non-null;} local variable info */
        private LocalVariableInfo locals;

        /**
         * Constructs an instance.
         *
         * @param output {@code non-null;} destination for instruction output
         * @param locals {@code non-null;} the local variable info
         */
        public LocalVariableAwareTranslationVisitor(OutputCollector output,
                                                    LocalVariableInfo locals) {
            super(output);
            this.locals = locals;
        }

        /** {@inheritDoc} */
        @Override
        public void visitPlainInsn(PlainInsn insn) {
            super.visitPlainInsn(insn);
            addIntroductionIfNecessary(insn);
        }

        /** {@inheritDoc} */
        @Override
        public void visitPlainCstInsn(PlainCstInsn insn) {
            super.visitPlainCstInsn(insn);
            addIntroductionIfNecessary(insn);
        }

        /** {@inheritDoc} */
        @Override
        public void visitSwitchInsn(SwitchInsn insn) {
            super.visitSwitchInsn(insn);
            addIntroductionIfNecessary(insn);
        }

        /** {@inheritDoc} */
        @Override
        public void visitThrowingCstInsn(ThrowingCstInsn insn) {
            super.visitThrowingCstInsn(insn);
            addIntroductionIfNecessary(insn);
        }

        /** {@inheritDoc} */
        @Override
        public void visitThrowingInsn(ThrowingInsn insn) {
            super.visitThrowingInsn(insn);
            addIntroductionIfNecessary(insn);
        }

        /**
         * Adds a {@link LocalStart} to the output if the given
         * instruction in fact introduces a local variable.
         *
         * @param insn {@code non-null;} instruction in question
         */
        public void addIntroductionIfNecessary(Insn insn) {
            RegisterSpec spec = locals.getAssignment(insn);

            if (spec != null) {
                addOutput(new LocalStart(insn.getPosition(), spec));
            }
        }
    }
}