FileDocCategorySizeDatePackage
RopTranslator.javaAPI DocAndroid 1.5 API31488Wed May 06 22:41:02 BST 2009com.android.dx.dex.code

RopTranslator

public final class RopTranslator extends Object
Translator from {@link RopMethod} to {@link DalvCode}. The {@link #translate} method is the thing to call on this class.

Fields Summary
private final com.android.dx.rop.code.RopMethod
method
non-null; method to translate
private final int
positionInfo
how much position info to preserve; one of the static constants in {@link PositionList}
private final com.android.dx.rop.code.LocalVariableInfo
locals
null-ok; local variable info to use
private final BlockAddresses
addresses
non-null; container for all the address objects for the method
private final OutputCollector
output
non-null; list of output instructions in-progress
private final TranslationVisitor
translationVisitor
non-null; visitor to use during translation
private final int
regCount
>= 0; register count for the method
private int[]
order
null-ok; block output order; becomes non-null in {@link #pickOrder}
private final int
paramSize
size, in register units, of all the parameters to this method
private boolean
paramsAreInOrder
true if the parameters to this method happen to be in proper order at the end of the frame (as the optimizer emits them)
Constructors Summary
private RopTranslator(com.android.dx.rop.code.RopMethod method, int positionInfo, com.android.dx.rop.code.LocalVariableInfo locals, int paramSize)
Constructs an instance. This method is private. Use {@link #translate}.

param
method non-null; the original method
param
positionInfo how much position info to preserve; one of the static constants in {@link PositionList}
param
locals null-ok; local variable information to use
param
paramSize size, in register units, of all the parameters to this method

        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);
        }
Methods Summary
private static booleancalculateParamsAreInOrder(com.android.dx.rop.code.RopMethod method, int paramSize)
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

        final boolean[] paramsAreInOrder = { true };
        final int initialRegCount = method.getBlocks().getRegCount();

        /*
         * We almost could just check the first block here, but the
         * <code>cf</code> 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];
private static com.android.dx.rop.code.RegisterSpecListgetRegs(com.android.dx.rop.code.Insn insn)
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 non-null; instruction in question
return
non-null; the instruction's complete register list

        return getRegs(insn, insn.getResult());
private static com.android.dx.rop.code.RegisterSpecListgetRegs(com.android.dx.rop.code.Insn insn, com.android.dx.rop.code.RegisterSpec resultReg)
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 non-null; instruction in question
param
resultReg null-ok; the real result to use (ignore the insn's)
return
non-null; the instruction's complete register list

        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);
private voidoutputBlock(com.android.dx.rop.code.BasicBlock block, int nextLabel)
Helper for {@link #outputInstructions}, which does the processing and output of one block.

param
block non-null; the block to process and output
param
nextLabel >= -1; the next block that will be processed, or -1 if there is no next block

        // 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);
            }
        }
private voidoutputInstructions()
Performs initial creation of output instructions based on the original blocks.

        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);
        }
private voidpickOrder()
Picks an order for the blocks by doing "trace" analysis.

        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;
public static DalvCodetranslate(com.android.dx.rop.code.RopMethod method, int positionInfo, com.android.dx.rop.code.LocalVariableInfo locals, int paramSize)
Translates a {@link RopMethod}. This may modify the given input.

param
method non-null; the original method
param
positionInfo how much position info to preserve; one of the static constants in {@link PositionList}
param
locals null-ok; local variable information to use
param
paramSize size, in register units, of all the parameters to this method
return
non-null; the translated version

        RopTranslator translator =
            new RopTranslator(method, positionInfo, locals,
                    paramSize);
        return translator.translateAndGetResult();
private DalvCodetranslateAndGetResult()
Does the translation and returns the result.

return
non-null; the result

        pickOrder();
        outputInstructions();

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

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