FileDocCategorySizeDatePackage
Ropper.javaAPI DocAndroid 1.5 API58689Wed May 06 22:41:02 BST 2009com.android.dx.cf.code

Ropper

public final class Ropper extends Object
Utility that converts a basic block list into a list of register-oriented blocks.

Fields Summary
private static final int
PARAM_ASSIGNMENT
label offset for the parameter assignment block
private static final int
RETURN
label offset for the return block
private static final int
SYNCH_RETURN
label offset for the synchronized method final return block
private static final int
SYNCH_SETUP_1
label offset for the first synchronized method setup block
private static final int
SYNCH_SETUP_2
label offset for the second synchronized method setup block
private static final int
SYNCH_CATCH_1
label offset for the first synchronized method exception handler block
private static final int
SYNCH_CATCH_2
label offset for the second synchronized method exception handler block
private static final int
SPECIAL_LABEL_COUNT
number of special label offsets
private final ConcreteMethod
method
non-null; method being converted
private final ByteBlockList
blocks
non-null; original block list
private final int
maxLocals
max locals of the method
private final int
maxLabel
max label (exclusive) of any original bytecode block
private final RopperMachine
machine
non-null; simulation machine to use
private final Simulator
sim
non-null; simulator to use
private final Frame[]
startFrames
non-null; sparse array mapping block labels to initial frame contents, if known
private final ArrayList
result
non-null; output block list in-progress
private final ArrayList
resultSubroutines
non-null; list of subroutine-nest labels (See {@link Frame#getSubroutines} associated with each result block. Parallel to {@link Ropper#result}.
private final com.android.dx.rop.type.Type[]
catchTypes
non-null; for each block (by label) that is used as an exception handler, the type of exception it catches
private boolean
synchNeedsExceptionHandler
whether an exception-handler block for a synchronized method was ever required
private final Subroutine[]
subroutines
non-null; list of subroutines indexed by label of start address
private boolean
hasSubroutines
true if subroutines is non-empty
Constructors Summary
private Ropper(ConcreteMethod method, TranslationAdvice advice)
Constructs an instance. This class is not publicly instantiable; use {@link #convert}.

param
method non-null; method to convert
param
advice non-null; translation advice to use

        if (method == null) {
            throw new NullPointerException("method == null");
        }

        if (advice == null) {
            throw new NullPointerException("advice == null");
        }

        this.method = method;
        this.blocks = BasicBlocker.identifyBlocks(method);
        this.maxLabel = blocks.getMaxLabel();
        this.maxLocals = method.getMaxLocals();
        this.machine = new RopperMachine(this, method, advice);
        this.sim = new Simulator(machine, method);
        this.startFrames = new Frame[maxLabel];
        this.subroutines = new Subroutine[maxLabel];

        /*
         * The "* 2 + 10" below is to conservatively believe that every
         * block is an exception handler target and should also
         * take care of enough other possible extra overhead such that
         * the underlying array is unlikely to need resizing.
         */
        this.result = new ArrayList<BasicBlock>(blocks.size() * 2 + 10);
        this.resultSubroutines = new ArrayList<IntList>(blocks.size() * 2 + 10);

        this.catchTypes = new Type[maxLabel];
        this.synchNeedsExceptionHandler = false;

        /*
         * Set up the first stack frame with the right limits, but leave it
         * empty here (to be filled in outside of the constructor).
         */
        startFrames[0] = new Frame(maxLocals, method.getMaxStack());
Methods Summary
private voidaddBlock(BasicBlock block, com.android.dx.util.IntList subroutines)
Adds a block to the output result.

param
block non-null; the block to add
param
subroutines non-null; subroutine label list as described in {@link Frame#getSubroutines}

        if (block == null) {
            throw new NullPointerException("block == null");
        }

        result.add(block);
        subroutines.throwIfMutable();
        resultSubroutines.add(subroutines);
private voidaddExceptionSetupBlocks()
Creates the exception handler setup blocks. "maxLocals" below is because that's the register number corresponding to the sole element on a one-deep stack (which is the situation at the start of an exception handler block).


        int len = catchTypes.length;
        for (int i = 0; i < len; i++) {
            Type one = catchTypes[i];
            if (one != null) {
                Insn proto = labelToBlock(i).getFirstInsn();
                SourcePosition pos = proto.getPosition();
                InsnList il = new InsnList(2);

                Insn insn = new PlainInsn(Rops.opMoveException(one),
                                          pos,
                                          RegisterSpec.make(maxLocals, one),
                                          RegisterSpecList.EMPTY);
                il.set(0, insn);

                insn = new PlainInsn(Rops.GOTO, pos, null,
                                     RegisterSpecList.EMPTY);
                il.set(1, insn);
                il.setImmutable();

                BasicBlock bb = new BasicBlock(getExceptionSetupLabel(i),
                                               il,
                                               IntList.makeImmutable(i),
                                               i);
                addBlock(bb, startFrames[i].getSubroutines());
            }
        }
private booleanaddOrReplaceBlock(BasicBlock block, com.android.dx.util.IntList subroutines)
Adds or replace a block in the output result. If this is a replacement, then any extra blocks that got added with the original get removed as a result of calling this method.

param
block non-null; the block to add or replace
param
subroutines non-null; subroutine label list as described in {@link Frame#getSubroutines}
return
true if the block was replaced or false if it was added for the first time

        if (block == null) {
            throw new NullPointerException("block == null");
        }

        int idx = labelToResultIndex(block.getLabel());
        boolean ret;

        if (idx < 0) {
            ret = false;
        } else {
            /*
             * We are replacing a pre-existing block, so find any
             * blocks that got added as part of the original and
             * remove those too. Such blocks are (possibly indirect)
             * successors of this block which are out of the range of
             * normally-translated blocks.
             */
            removeBlockAndSpecialSuccessors(idx);
            ret = true;
        }

        result.add(block);
        subroutines.throwIfMutable();
        resultSubroutines.add(subroutines);
        return ret;
private booleanaddOrReplaceBlockNoDelete(BasicBlock block, com.android.dx.util.IntList subroutines)
Adds or replaces a block in the output result. Do not delete any successors.

param
block non-null; the block to add or replace
param
subroutines non-null; subroutine label list as described in {@link Frame#getSubroutines}
return
true if the block was replaced or false if it was added for the first time

        if (block == null) {
            throw new NullPointerException("block == null");
        }

        int idx = labelToResultIndex(block.getLabel());
        boolean ret;

        if (idx < 0) {
            ret = false;
        } else {
            result.remove(idx);
            resultSubroutines.remove(idx);
            ret = true;
        }

        result.add(block);
        subroutines.throwIfMutable();
        resultSubroutines.add(subroutines);
        return ret;
private voidaddReturnBlock()
Constructs and adds the return block, if necessary. The return block merely contains an appropriate return instruction.

        Rop returnOp = machine.getReturnOp();

        if (returnOp == null) {
            /*
             * The method being converted never returns normally, so there's
             * no need for a return block.
             */
            return;
        }

        SourcePosition returnPos = machine.getReturnPosition();
        int label = getSpecialLabel(RETURN);

        if (isSynchronized()) {
            InsnList insns = new InsnList(1);
            Insn insn = new ThrowingInsn(Rops.MONITOR_EXIT, returnPos,
                                         RegisterSpecList.make(getSynchReg()),
                                         StdTypeList.EMPTY);
            insns.set(0, insn);
            insns.setImmutable();

            int nextLabel = getSpecialLabel(SYNCH_RETURN);
            BasicBlock bb =
                new BasicBlock(label, insns,
                               IntList.makeImmutable(nextLabel), nextLabel);
            addBlock(bb, IntList.EMPTY);

            label = nextLabel;
        }

        InsnList insns = new InsnList(1);
        TypeList sourceTypes = returnOp.getSources();
        RegisterSpecList sources;

        if (sourceTypes.size() == 0) {
            sources = RegisterSpecList.EMPTY;
        } else {
            RegisterSpec source = RegisterSpec.make(0, sourceTypes.getType(0));
            sources = RegisterSpecList.make(source);
        }

        Insn insn = new PlainInsn(returnOp, returnPos, null, sources);
        insns.set(0, insn);
        insns.setImmutable();

        BasicBlock bb = new BasicBlock(label, insns, IntList.EMPTY, -1);
        addBlock(bb, IntList.EMPTY);
private voidaddSetupBlocks()
Constructs and adds the blocks that perform setup for the rest of the method. This includes a first block which merely contains assignments from parameters to the same-numbered registers and a possible second block which deals with synchronization.

        LocalVariableList localVariables = method.getLocalVariables();
        SourcePosition pos = method.makeSourcePosistion(0);
        Prototype desc = method.getEffectiveDescriptor();
        StdTypeList params = desc.getParameterTypes();
        int sz = params.size();
        InsnList insns = new InsnList(sz + 1);
        int at = 0;

        for (int i = 0; i < sz; i++) {
            Type one = params.get(i);
            LocalVariableList.Item local = localVariables.pcAndIndexToLocal(0, at);
            RegisterSpec result = (local == null) ?
                RegisterSpec.make(at, one) :
                RegisterSpec.makeLocalOptional(at, one, local.getLocalItem());

            Insn insn = new PlainCstInsn(Rops.opMoveParam(one), pos, result,
                                         RegisterSpecList.EMPTY,
                                         CstInteger.make(at));
            insns.set(i, insn);
            at += one.getCategory();
        }

        insns.set(sz, new PlainInsn(Rops.GOTO, pos, null, 
                                    RegisterSpecList.EMPTY));
        insns.setImmutable();

        boolean synch = isSynchronized();
        int label = synch ? getSpecialLabel(SYNCH_SETUP_1) : 0;
        BasicBlock bb =
            new BasicBlock(getSpecialLabel(PARAM_ASSIGNMENT), insns,
                           IntList.makeImmutable(label), label);
        addBlock(bb, IntList.EMPTY);

        if (synch) {
            RegisterSpec synchReg = getSynchReg();
            Insn insn;
            if (isStatic()) {
                insn = new ThrowingCstInsn(Rops.CONST_OBJECT, pos,
                                           RegisterSpecList.EMPTY,
                                           StdTypeList.EMPTY,
                                           method.getDefiningClass());
                insns = new InsnList(1);
                insns.set(0, insn);
            } else {
                insns = new InsnList(2);
                insn = new PlainCstInsn(Rops.MOVE_PARAM_OBJECT, pos,
                                        synchReg, RegisterSpecList.EMPTY,
                                        CstInteger.VALUE_0);
                insns.set(0, insn);
                insns.set(1, new PlainInsn(Rops.GOTO, pos, null,
                                           RegisterSpecList.EMPTY));
            }

            int label2 = getSpecialLabel(SYNCH_SETUP_2);
            insns.setImmutable();
            bb = new BasicBlock(label, insns,
                                IntList.makeImmutable(label2), label2);
            addBlock(bb, IntList.EMPTY);

            insns = new InsnList(isStatic() ? 2 : 1);

            if (isStatic()) {
                insns.set(0, new PlainInsn(Rops.opMoveResultPseudo(synchReg),
                        pos, synchReg, RegisterSpecList.EMPTY));
            }

            insn = new ThrowingInsn(Rops.MONITOR_ENTER, pos,
                                    RegisterSpecList.make(synchReg),
                                    StdTypeList.EMPTY);
            insns.set(isStatic() ? 1 :0, insn);
            insns.setImmutable();
            bb = new BasicBlock(label2, insns, IntList.makeImmutable(0), 0);
            addBlock(bb, IntList.EMPTY);
        }
private voidaddSynchExceptionHandlerBlock()
Constructs and adds, if necessary, the catch-all exception handler block to deal with unwinding the lock taken on entry to a synchronized method.

        if (!synchNeedsExceptionHandler) {
            /*
             * The method being converted either isn't synchronized or
             * can't possibly throw exceptions in its main body, so
             * there's no need for a synchronized method exception
             * handler.
             */
            return;
        }

        SourcePosition pos = method.makeSourcePosistion(0);
        RegisterSpec exReg = RegisterSpec.make(0, Type.THROWABLE);
        BasicBlock bb;
        Insn insn;

        InsnList insns = new InsnList(2);
        insn = new PlainInsn(Rops.opMoveException(Type.THROWABLE), pos,
                             exReg, RegisterSpecList.EMPTY);
        insns.set(0, insn);
        insn = new ThrowingInsn(Rops.MONITOR_EXIT, pos,
                                RegisterSpecList.make(getSynchReg()),
                                StdTypeList.EMPTY);
        insns.set(1, insn);
        insns.setImmutable();

        int label2 = getSpecialLabel(SYNCH_CATCH_2);
        bb = new BasicBlock(getSpecialLabel(SYNCH_CATCH_1), insns,
                            IntList.makeImmutable(label2), label2);
        addBlock(bb, IntList.EMPTY);

        insns = new InsnList(1);
        insn = new ThrowingInsn(Rops.THROW, pos,
                                RegisterSpecList.make(exReg),
                                StdTypeList.EMPTY);
        insns.set(0, insn);
        insns.setImmutable();

        bb = new BasicBlock(label2, insns, IntList.EMPTY, -1);
        addBlock(bb, IntList.EMPTY);
public static RopMethodconvert(ConcreteMethod method, TranslationAdvice advice)
Converts a {@link ConcreteMethod} to a {@link RopMethod}.

param
method non-null; method to convert
param
advice non-null; translation advice to use
return
non-null; the converted instance

        try {
            Ropper r = new Ropper(method, advice);
            r.doit();
            return r.getRopMethod();
        } catch (SimException ex) {
            ex.addContext("...while working on method " +
                          method.getNat().toHuman());
            throw ex;
        }
private voiddeleteUnreachableBlocks()
Deletes all blocks that cannot be reached. This is run to delete original subroutine blocks after subroutine inlining.

        final IntList reachableLabels = new IntList(result.size());

        // subroutine inlining is done now and we won't update this list here
        resultSubroutines.clear();

        forEachNonSubBlockDepthFirst(getSpecialLabel(PARAM_ASSIGNMENT),
                new BasicBlock.Visitor() {

            public void visitBlock(BasicBlock b) {
                reachableLabels.add(b.getLabel());
            }
        });

        reachableLabels.sort();

        for (int i = result.size() - 1 ; i >= 0 ; i--) {
            if (reachableLabels.indexOf(result.get(i).getLabel()) < 0) {
                result.remove(i);
                // unnecessary here really, since subroutine inlining is done
                //resultSubroutines.remove(i);
            }
        }
private voiddoit()
Does the conversion.

        int[] workSet = Bits.makeBitSet(maxLabel);

        Bits.set(workSet, 0);
        addSetupBlocks();
        setFirstFrame();

        for (;;) {
            int offset = Bits.findFirst(workSet, 0);
            if (offset < 0) {
                break;
            }
            Bits.clear(workSet, offset);
            ByteBlock block = blocks.labelToBlock(offset);
            Frame frame = startFrames[offset];
            try {
                processBlock(block, frame, workSet);
            } catch (SimException ex) {
                ex.addContext("...while working on block " + Hex.u2(offset));
                throw ex;
            }
        }

        addReturnBlock();
        addSynchExceptionHandlerBlock();
        addExceptionSetupBlocks();

        if (hasSubroutines) {
            // Subroutines are very rare, so skip this step if it's n/a
            inlineSubroutines();
        }
private InsnListfilterMoveReturnAddressInsns(InsnList insns)
Removes all move-return-address instructions, returning a new InsnList if necessary. The move-return-address insns are dead code after subroutines have been inlined.

param
insns InsnList that may contain move-return-address insns
return
InsnList with move-return-address removed.

        int sz;
        int newSz = 0;

        // First see if we need to filter, and if so what the new size will be
        sz = insns.size();
        for (int i = 0; i < sz; i++) {
            if (insns.get(i).getOpcode() != Rops.MOVE_RETURN_ADDRESS) {
                newSz++;
            }
        }

        if (newSz == sz) {
            return insns;
        }

        // Make a new list without the MOVE_RETURN_ADDRESS insns
        InsnList newInsns = new InsnList(newSz);

        int newIndex = 0;
        for (int i = 0; i < sz; i++) {
            Insn insn = insns.get(i);
            if (insn.getOpcode() != Rops.MOVE_RETURN_ADDRESS) {
                newInsns.set(newIndex++, insn);
            }
        }

        newInsns.setImmutable();
        return newInsns;
private voidforEachNonSubBlockDepthFirst(int firstLabel, BasicBlock.Visitor v)
Visits each non-subroutine block once in depth-first successor order.

param
firstLabel label of start block
param
v callback interface


        forEachNonSubBlockDepthFirst0(labelToBlock(firstLabel),
                v, new BitSet(maxLabel));
private voidforEachNonSubBlockDepthFirst0(BasicBlock next, BasicBlock.Visitor v, java.util.BitSet visited)
Visits each block once in depth-first successor order, ignoring jsr targets. Worker for forEachNonSubBlockDepthFirst().

param
next next block to visit
param
v callback interface
param
visited set of blocks already visited


        v.visitBlock(next);
        visited.set(next.getLabel());

        IntList successors = next.getSuccessors();

        int sz = successors.size();

        for (int i = 0 ; i < sz ; i++) {
            int succ = successors.get(i);

            if (visited.get(succ)) {
                continue;
            }

            if (isSubroutineCaller(next) && i > 0) {
                // ignore jsr targets
                continue;
            }

            /*
             * Ignore missing labels: they're successors of
             * subroutines that never invoke a ret.
             */
            int idx = labelToResultIndex(succ);
            if (idx >= 0) {
                forEachNonSubBlockDepthFirst0(result.get(idx), v, visited);
            }
        }
private intgetAvailableLabel()
Gets an arbitrary unreserved and available label.

return
>= 0; the label

        int candidate = getMinimumUnreservedLabel();

        for (BasicBlock bb : result) {
            int label = bb.getLabel();
            if (label >= candidate) {
                candidate = label + 1;
            }
        }

        return candidate;
private intgetExceptionSetupLabel(int label)
Gets the label for the exception handler setup block corresponding to the given label.

param
label >= 0; the original label
return
>= 0; the corresponding exception handler setup label

        return maxLabel + label;
intgetFirstTempStackReg()
Gets the first (lowest) register number to use as the temporary area when unwinding stack manipulation ops.

return
>= 0; the first register to use

        /*
         * We use the register that is just past the deepest possible
         * stack element, plus one if the method is synchronized to
         * avoid overlapping with the synch register. We don't need to
         * do anything else special at this level, since later passes
         * will merely notice the highest register used by explicit
         * inspection.
         */
        int regCount = getNormalRegCount();
        return isSynchronized() ? regCount + 1 : regCount;
private intgetMinimumUnreservedLabel()
Gets the minimum label for unreserved use.

return
>= 0; the minimum label

        /*
         * The labels below ((maxLabel * 2) + SPECIAL_LABEL_COUNT) are
         * reserved for particular uses.
         */

        return (maxLabel * 2) + SPECIAL_LABEL_COUNT;
private intgetNormalRegCount()
Gets the total number of registers used for "normal" purposes (i.e., for the straightforward translation from the original Java).

return
>= 0; the total number of registers used

        return maxLocals + method.getMaxStack();
private RopMethodgetRopMethod()
Extracts the resulting {@link RopMethod} from the instance.

return
non-null; the method object


        // Construct the final list of blocks.

        int sz = result.size();
        BasicBlockList bbl = new BasicBlockList(sz);
        for (int i = 0; i < sz; i++) {
            bbl.set(i, result.get(i));
        }
        bbl.setImmutable();

        // Construct the method object to wrap it all up.

        /*
         * Note: The parameter assignment block is always the first
         * that should be executed, hence the second argument to the
         * constructor.
         */
        return new RopMethod(bbl, getSpecialLabel(PARAM_ASSIGNMENT));
private intgetSpecialLabel(int label)
Gets the label for the given special-purpose block. The given label should be one of the static constants defined by this class.

param
label < 0; the special label constant
return
>= 0; the actual label value to use

        /*
         * The label is bitwise-complemented so that mistakes where
         * LABEL is used instead of getSpecialLabel(LABEL) cause a
         * failure at block construction time, since negative labels
         * are illegal. We multiply maxLabel by 2 since 0..maxLabel
         * (exclusive) are the original blocks and
         * maxLabel..(maxLabel*2) are reserved for exception handler
         * setup blocks (see getExceptionSetupLabel(), above).
         */
        return (maxLabel * 2) + ~label;
private RegisterSpecgetSynchReg()
Gets the register spec to use to hold the object to synchronize on, for a synchronized method.

return
non-null; the register spec

        /*
         * We use the register that is just past the deepest possible
         * stack element. We don't need to do anything else special at
         * this level, since later passes will merely notice the
         * highest register used by explicit inspection.
         */
        return RegisterSpec.make(getNormalRegCount(), Type.OBJECT);
private voidinlineSubroutines()
Inlines any subroutine calls

        final IntList reachableSubroutineCallerLabels = new IntList(4);

        /*
         * Compile a list of all subroutine calls reachable
         * through the normal (non-subroutine) flow.  We do this first, since
         * we'll be affecting the call flow as we go.
         * 
         * Start at label 0 --  the param assignment block has nothing for us
         */
        forEachNonSubBlockDepthFirst(0, new BasicBlock.Visitor() {
            public void visitBlock(BasicBlock b) {
                if (isSubroutineCaller(b)) {
                    reachableSubroutineCallerLabels.add(b.getLabel());
                }
            }
        });

        /*
         * Convert the resultSubroutines list, indexed by block index,
         * to a label-to-subroutines mapping used by the inliner.
         */
        int largestAllocedLabel = getAvailableLabel();
        ArrayList<IntList> labelToSubroutines
                = new ArrayList<IntList>(largestAllocedLabel);
        for (int i = 0; i < largestAllocedLabel; i++) {
            labelToSubroutines.add(null);
        }

        for (int i = 0; i < result.size(); i++) {
            BasicBlock b = result.get(i);
            if (b == null) {
                continue;
            }
            IntList subroutineList = resultSubroutines.get(i);
            labelToSubroutines.set(b.getLabel(), subroutineList);
        }

        /*
        * Inline all reachable subroutines.
        * Inner subroutines will be inlined as they are encountered.
        */
        int sz = reachableSubroutineCallerLabels.size();
        for (int i = 0 ; i < sz ; i++) {
            int label = reachableSubroutineCallerLabels.get(i);
            new SubroutineInliner(
                    new LabelAllocator(getAvailableLabel()), labelToSubroutines)
                    .inlineSubroutineCalledFrom(labelToBlock(label));
        }

        // Now find the blocks that aren't reachable and remove them
        deleteUnreachableBlocks();
private booleanisStatic()
Gets whether the method being translated is static.

return
whether the method being translated is static

        int accessFlags = method.getAccessFlags();
        return (accessFlags & AccessFlags.ACC_STATIC) != 0;
private booleanisSubroutineCaller(BasicBlock bb)
Checks to see if the basic block is a subroutine caller block.

param
bb non-null; the basic block in question
return
true if this block calls a subroutine

        IntList successors = bb.getSuccessors();
        if (successors.size() < 2) return false;

        int subLabel = successors.get(1);

        return (subLabel < subroutines.length)
                && (subroutines[subLabel] != null);
private booleanisSynchronized()
Gets whether the method being translated is synchronized.

return
whether the method being translated is synchronized

        int accessFlags = method.getAccessFlags();
        return (accessFlags & AccessFlags.ACC_SYNCHRONIZED) != 0;
private BasicBlocklabelToBlock(int label)
Searches {@link #result} for a block with the given label. Return it if found, or throw an exception if there is no such block.

param
label the label to look for
return
non-null; the block with the given label

        int idx = labelToResultIndex(label);

        if (idx < 0) {
            throw new IllegalArgumentException("no such label " +
                    Hex.u2(label));
        }

        return result.get(idx);
private intlabelToResultIndex(int label)
Searches {@link #result} for a block with the given label. Return its index if found, or return -1 if there is no such block.

param
label the label to look for
return
>= -1; the index for the block with the given label or -1 if there is no such block

        int sz = result.size();
        for (int i = 0; i < sz; i++) {
            BasicBlock one = result.get(i);
            if (one.getLabel() == label) {
                return i;
            }
        }

        return -1;
private voidmergeAndWorkAsNecessary(int label, int pred, com.android.dx.cf.code.Ropper$Subroutine calledSubroutine, Frame frame, int[] workSet)
Helper for {@link #processBlock}, which merges frames and adds to the work set, as necessary.

param
label >= 0; label to work on
param
pred predecessor label. Must be >= 0 when label is a subroutine start block and calledSubroutine is non-null. Otherwise, may be -1.
param
calledSubroutine null-ok; a Subroutine instance if label is the first block in a subroutine.
param
frame non-null; new frame for the labelled block
param
workSet non-null; bits representing work to do, which this method may add to

        Frame existing = startFrames[label];
        Frame merged;

        if (existing != null) {
            /*
             * Some other block also continues at this label. Merge
             * the frames, and re-set the bit in the work set if there
             * was a change.
             */
            if (calledSubroutine != null) {
                merged = existing.mergeWithSubroutineCaller(frame,
                        calledSubroutine.getStartBlock(), pred);
            } else {
                merged = existing.mergeWith(frame);
            }
            if (merged != existing) {
                startFrames[label] = merged;
                Bits.set(workSet, label);
            }
        } else {
            // This is the first time this label has been encountered.
            if (calledSubroutine != null) {
                startFrames[label]
                        = frame.makeNewSubroutineStartFrame(label, pred);
            } else {
                startFrames[label] = frame;
            }
            Bits.set(workSet, label);
        }
private voidprocessBlock(ByteBlock block, Frame frame, int[] workSet)
Processes the given block.

param
block non-null; block to process
param
frame non-null; start frame for the block
param
workSet non-null; bits representing work to do, which this method may add to

        // Prepare the list of caught exceptions for this block.
        ByteCatchList catches = block.getCatches();
        machine.startBlock(catches.toRopCatchList());

        /*
         * Using a copy of the given frame, simulate each instruction,
         * calling into machine for each.
         */
        frame = frame.copy();
        sim.simulate(block, frame);
        frame.setImmutable();

        int extraBlockCount = machine.getExtraBlockCount();
        ArrayList<Insn> insns = machine.getInsns();
        int insnSz = insns.size();

        /*
         * Merge the frame into each possible non-exceptional
         * successor.
         */

        int catchSz = catches.size();
        IntList successors = block.getSuccessors();

        int startSuccessorIndex;

        Subroutine calledSubroutine = null;
        if (machine.hasJsr()) {
            /*
             * If this frame ends in a JSR, only merge our frame with
             * the subroutine start, not the subroutine's return target.
             */
            startSuccessorIndex = 1;

            int subroutineLabel = successors.get(1);

            if (subroutines[subroutineLabel] == null) {
                subroutines[subroutineLabel] = new Subroutine (subroutineLabel);
            }
            
            subroutines[subroutineLabel].addCallerBlock(block.getLabel());

            calledSubroutine = subroutines[subroutineLabel];
        } else if (machine.hasRet()) {
            /*
             * This block ends in a ret, which means it's the final block
             * in some subroutine. Ultimately, this block will be copied
             * and inlined for each call and then disposed of.
             */

            ReturnAddress ra = machine.getReturnAddress();
            int subroutineLabel = ra.getSubroutineAddress();

            if (subroutines[subroutineLabel] == null) {
                subroutines[subroutineLabel]
                        = new Subroutine (subroutineLabel, block.getLabel());
            } else {
                subroutines[subroutineLabel].addRetBlock(block.getLabel());
            }

            successors = subroutines[subroutineLabel].getSuccessors();
            subroutines[subroutineLabel]
                    .mergeToSuccessors(frame, workSet);
            // Skip processing below since we just did it.
            startSuccessorIndex = successors.size();
        } else if (machine.wereCatchesUsed()) {
            /*
             * If there are catches, then the first successors
             * (which will either be all of them or all but the last one)
             * are catch targets.
             */
            startSuccessorIndex = catchSz;
        } else {
            startSuccessorIndex = 0;
        }

        int succSz = successors.size();
        for (int i = startSuccessorIndex; i < succSz;
             i++) {
            int succ = successors.get(i);
            try {
                mergeAndWorkAsNecessary(succ, block.getLabel(),
                        calledSubroutine, frame, workSet);
            } catch (SimException ex) {
                ex.addContext("...while merging to block " + Hex.u2(succ));
                throw ex;
            }
        }

        if ((succSz == 0) && machine.returns()) {
            /*
             * The block originally contained a return, but it has
             * been made to instead end with a goto, and we need to
             * tell it at this point that its sole successor is the
             * return block. This has to happen after the merge loop
             * above, since, at this point, the return block doesn't
             * actually exist; it gets synthesized at the end of
             * processing the original blocks.
             */
            successors = IntList.makeImmutable(getSpecialLabel(RETURN));
            succSz = 1;
        }

        int primarySucc;

        if (succSz == 0) {
            primarySucc = -1;
        } else {
            primarySucc = machine.getPrimarySuccessorIndex();
            if (primarySucc >= 0) {
                primarySucc = successors.get(primarySucc);
            }
        }

        /*
         * This variable is true only when the method is synchronized and
         * the block being processed can possibly throw an exception.
         */
        boolean synch = isSynchronized() && machine.canThrow();

        if (synch || (catchSz != 0)) {
            /*
             * Deal with exception handlers: Merge an exception-catch
             * frame into each possible exception handler, and
             * construct a new set of successors to point at the
             * exception handler setup blocks (which get synthesized
             * at the very end of processing).
             */
            boolean catchesAny = false;
            IntList newSucc = new IntList(succSz);
            for (int i = 0; i < catchSz; i++) {
                ByteCatchList.Item one = catches.get(i);
                CstType exceptionClass = one.getExceptionClass();
                int targ = one.getHandlerPc();

                catchesAny |= (exceptionClass == CstType.OBJECT);

                Frame f = frame.makeExceptionHandlerStartFrame(exceptionClass);

                try {
                    mergeAndWorkAsNecessary(targ, block.getLabel(),
                            null, f, workSet);
                } catch (SimException ex) {
                    ex.addContext("...while merging exception to block " +
                                  Hex.u2(targ));
                    throw ex;
                }

                /*
                 * Set up the exception handler type, by setting it if
                 * the given handler has yet to be encountered, or by
                 * conservatively unioning if it has.
                 */
                Type already = catchTypes[targ];
                if (already == null) {
                    catchTypes[targ] = exceptionClass.getClassType();
                } else if (already != exceptionClass.getClassType()) {
                    catchTypes[targ] = Type.OBJECT;
                }

                /*
                 * The synthesized exception setup block will have the
                 * label getExceptionSetupLabel(targ).
                 */
                newSucc.add(getExceptionSetupLabel(targ));
            }

            if (synch && !catchesAny) {
                /*
                 * The method is synchronized and this block doesn't
                 * already have a catch-all handler, so add one to the
                 * end, both in the successors and in the throwing
                 * instruction(s) at the end of the block (which is where
                 * the caught classes live).
                 */
                newSucc.add(getSpecialLabel(SYNCH_CATCH_1));
                synchNeedsExceptionHandler = true;

                for (int i = insnSz - extraBlockCount - 1; i < insnSz; i++) {
                    Insn insn = insns.get(i);
                    if (insn.canThrow()) {
                        insn = insn.withAddedCatch(Type.OBJECT);
                        insns.set(i, insn);
                    }
                }
            }

            if (primarySucc >= 0) {
                newSucc.add(primarySucc);
            }

            newSucc.setImmutable();
            successors = newSucc;
        }

        // Construct the final resulting block(s), and store it (them).

        int primarySuccListIndex = successors.indexOf(primarySucc);

        /*
         * If there are any extra blocks, work backwards through the
         * list of instructions, adding single-instruction blocks, and
         * resetting the successors variables as appropriate.
         */
        for (/*extraBlockCount*/; extraBlockCount > 0; extraBlockCount--) {
            /*
             * Some of the blocks that the RopperMachine wants added
             * are for move-result insns, and these need goto insns as well.
             */
            Insn extraInsn = insns.get(--insnSz);
            boolean needsGoto
                    = extraInsn.getOpcode().getBranchingness()
                        == Rop.BRANCH_NONE;
            InsnList il = new InsnList(needsGoto ? 2 : 1);
            IntList extraBlockSuccessors = successors;

            il.set(0, extraInsn);

            if (needsGoto) {
                il.set(1, new PlainInsn(Rops.GOTO,
                        extraInsn.getPosition(), null,
                        RegisterSpecList.EMPTY));
                /*
                 * Obviously, this block won't be throwing an exception
                 * so it should only have one successor.
                 */
                extraBlockSuccessors = IntList.makeImmutable(primarySucc);
            }
            il.setImmutable();

            int label = getAvailableLabel();
            BasicBlock bb = new BasicBlock(label, il, extraBlockSuccessors,
                    primarySucc);
            // All of these extra blocks will be in the same subroutine
            addBlock(bb, frame.getSubroutines());

            successors = successors.mutableCopy();
            successors.set(primarySuccListIndex, label);
            successors.setImmutable();
            primarySucc = label;
        }
        
        Insn lastInsn = (insnSz == 0) ? null : insns.get(insnSz - 1);

        /*
         * Add a goto to the end of the block if it doesn't already
         * end with a branch, to maintain the invariant that all
         * blocks end with a branch of some sort or other. Note that
         * it is possible for there to be blocks for which no
         * instructions were ever output (e.g., only consist of pop*
         * in the original Java bytecode).
         */
        if ((lastInsn == null) ||
            (lastInsn.getOpcode().getBranchingness() == Rop.BRANCH_NONE)) {
            SourcePosition pos = (lastInsn == null) ? SourcePosition.NO_INFO :
                lastInsn.getPosition();
            insns.add(new PlainInsn(Rops.GOTO, pos, null,
                                    RegisterSpecList.EMPTY));
            insnSz++;
        }
        
        /*
         * Construct a block for the remaining instructions (which in
         * the usual case is all of them).
         */

        InsnList il = new InsnList(insnSz);
        for (int i = 0; i < insnSz; i++) {
            il.set(i, insns.get(i));
        }
        il.setImmutable();

        BasicBlock bb =
            new BasicBlock(block.getLabel(), il, successors, primarySucc);
        addOrReplaceBlock(bb, frame.getSubroutines());
private voidremoveBlockAndSpecialSuccessors(int idx)
Helper for {@link #addOrReplaceBlock} which recursively removes the given block and all blocks that are (direct and indirect) successors of it whose labels indicate that they are not in the normally-translated range.

param
idx non-null; block to remove (etc.)

        int minLabel = getMinimumUnreservedLabel();
        BasicBlock block = result.get(idx);
        IntList successors = block.getSuccessors();
        int sz = successors.size();

        result.remove(idx);
        resultSubroutines.remove(idx);

        for (int i = 0; i < sz; i++) {
            int label = successors.get(i);
            if (label >= minLabel) {
                idx = labelToResultIndex(label);
                if (idx < 0) {
                    throw new RuntimeException("Invalid label "
                            + Hex.u2(label));
                }
                removeBlockAndSpecialSuccessors(idx);
            }
        }
private voidsetFirstFrame()
Sets up the first frame to contain all the incoming parameters in locals.

        Prototype desc = method.getEffectiveDescriptor();
        startFrames[0].initializeWithParameters(desc.getParameterTypes());
        startFrames[0].setImmutable();
private com.android.dx.cf.code.Ropper$SubroutinesubroutineFromRetBlock(int label)
Finds a Subroutine that is returned from by a ret in a given block.

param
label A block that originally contained a ret instruction
return
null-ok; Subroutine or null if none was found.

        for (int i = subroutines.length - 1 ; i >= 0 ; i--) {
            if (subroutines[i] != null) {
                Subroutine subroutine = subroutines[i];

                if (subroutine.retBlocks.get(label)) {
                    return subroutine;
                }
            }
        }

        return null;