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

BasicBlocker

public final class BasicBlocker extends Object implements BytecodeArray.Visitor
Utility that identifies basic blocks in bytecode.

Fields Summary
private final ConcreteMethod
method
non-null; method being converted
private final int[]
workSet
non-null; work set; bits indicate offsets in need of examination
private final int[]
liveSet
non-null; live set; bits indicate potentially-live opcodes; contrawise, a bit that isn't on is either in the middle of an instruction or is a definitely-dead opcode
private final int[]
blockSet
non-null; block start set; bits indicate the starts of basic blocks, including the opcodes that start blocks of definitely-dead code
private final com.android.dx.util.IntList[]
targetLists
non-null, sparse; for each instruction offset to a branch of some sort, the list of targets for that instruction
private final ByteCatchList[]
catchLists
non-null, sparse; for each instruction offset to a throwing instruction, the list of exception handlers for that instruction
private int
previousOffset
offset of the previously parsed bytecode
Constructors Summary
private BasicBlocker(ConcreteMethod method)
Constructs an instance. This class is not publicly instantiable; use {@link #identifyBlocks}.

param
method non-null; method to convert

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

        this.method = method;

        /*
         * The "+1" below is so the idx-past-end is also valid,
         * avoiding a special case, but without preventing
         * flow-of-control falling past the end of the method from
         * getting properly reported.
         */
        int sz = method.getCode().size() + 1;

        workSet = Bits.makeBitSet(sz);
        liveSet = Bits.makeBitSet(sz);
        blockSet = Bits.makeBitSet(sz);
        targetLists = new IntList[sz];
        catchLists = new ByteCatchList[sz];
        previousOffset = -1;
Methods Summary
private voidaddWorkIfNecessary(int offset, boolean blockStart)
Sets a bit in the work set, but only if the instruction in question isn't yet known to be possibly-live.

param
offset offset to the instruction in question
param
blockStart true iff this instruction starts a basic block

        if (!Bits.get(liveSet, offset)) {
            Bits.set(workSet, offset);
        }

        if (blockStart) {
            Bits.set(blockSet, offset);
        }
private voiddoit()
Does basic block identification.

        BytecodeArray bytes = method.getCode();
        ByteCatchList catches = method.getCatches();
        int catchSz = catches.size();

        /*
         * Start by setting offset 0 as the start of a block and in need
         * of work...
         */
        Bits.set(workSet, 0);
        Bits.set(blockSet, 0);

        /*
         * And then process the work set, add new work based on
         * exception ranges that are active, and iterate until there's
         * nothing left to work on.
         */
        while (!Bits.isEmpty(workSet)) {
            try {
                bytes.processWorkSet(workSet, this);
            } catch (IllegalArgumentException ex) {
                // Translate the exception.
                throw new SimException("flow of control falls off " +
                                       "end of method",
                                       ex);
            }

            for (int i = 0; i < catchSz; i++) {
                ByteCatchList.Item item = catches.get(i);
                int start = item.getStartPc();
                int end = item.getEndPc();
                if (Bits.anyInRange(liveSet, start, end)) {
                    Bits.set(blockSet, start);
                    Bits.set(blockSet, end);
                    addWorkIfNecessary(item.getHandlerPc(), true);
                }
            }
        }
private ByteBlockListgetBlockList()
Extracts the list of basic blocks from the bit sets.

return
non-null; the list of basic blocks

        ByteCatchList catches = method.getCatches();
        BytecodeArray bytes = method.getCode();
        ByteBlock[] bbs = new ByteBlock[bytes.size()];
        int count = 0;

        for (int at = 0, next; /*at*/; at = next) {
            next = Bits.findFirst(blockSet, at + 1);
            if (next < 0) {
                break;
            }

            if (Bits.get(liveSet, at)) {
                /*
                 * Search backward for the branch or throwing
                 * instruction at the end of this block, if any. If
                 * there isn't any, then "next" is the sole target.
                 */
                IntList targets = null;
                int targetsAt = -1;
                ByteCatchList blockCatches;

                for (int i = next - 1; i >= at; i--) {
                    targets = targetLists[i];
                    if (targets != null) {
                        targetsAt = i;
                        break;
                    }
                }

                if (targets == null) {
                    targets = IntList.makeImmutable(next);
                    blockCatches = ByteCatchList.EMPTY;
                } else {
                    blockCatches = catchLists[targetsAt];
                    if (blockCatches == null) {
                        blockCatches = ByteCatchList.EMPTY;
                    }
                }

                bbs[count] =
                    new ByteBlock(at, at, next, targets, blockCatches);
                count++;
            }
        }

        ByteBlockList result = new ByteBlockList(count);
        for (int i = 0; i < count; i++) {
            result.set(i, bbs[i]);
        }

        return result;
public intgetPreviousOffset()
{@inheritDoc}

        return previousOffset;
public static ByteBlockListidentifyBlocks(ConcreteMethod method)
Identifies and enumerates the basic blocks in the given method, returning a list of them. The returned list notably omits any definitely-dead code that is identified in the process.

param
method non-null; method to convert
return
non-null; list of basic blocks

        BasicBlocker bb = new BasicBlocker(method);

        bb.doit();
        return bb.getBlockList();
public voidsetPreviousOffset(int offset)
{@inheritDoc}

        previousOffset = offset;
public voidvisitBranch(int opcode, int offset, int length, int target)
{@inheritDoc}

        switch (opcode) {
            case ByteOps.GOTO: {
                visitCommon(offset, length, false);
                targetLists[offset] = IntList.makeImmutable(target);
                break;
            }
            case ByteOps.JSR: {
                /*
                 * Each jsr is quarantined into a separate block (containing
                 * only the jsr instruction) but is otherwise treated
                 * as a conditional branch. (That is to say, both its
                 * target and next instruction begin new blocks.)
                 */
                addWorkIfNecessary(offset, true);
                // Fall through to next case...
            }
            default: {
                int next = offset + length;
                visitCommon(offset, length, true);
                addWorkIfNecessary(next, true);
                targetLists[offset] = IntList.makeImmutable(next, target);
                break;
            }
        }

        addWorkIfNecessary(target, true);
private voidvisitCommon(int offset, int length, boolean nextIsLive)
Helper method used by all the visitor methods.

param
offset offset to the instruction
param
length length of the instruction, in bytes
param
nextIsLive true iff the instruction after the indicated one is possibly-live (because this one isn't an unconditional branch, a return, or a switch)

        Bits.set(liveSet, offset);

        if (nextIsLive) {
            /*
             * If the next instruction is flowed to by this one, just
             * add it to the work set, and then a subsequent visit*()
             * will deal with it as appropriate.
             */
            addWorkIfNecessary(offset + length, false);
        } else {
            /*
             * If the next instruction isn't flowed to by this one,
             * then mark it as a start of a block but *don't* add it
             * to the work set, so that in the final phase we can know
             * dead code blocks as those marked as blocks but not also marked
             * live.
             */
            Bits.set(blockSet, offset + length);
        }
public voidvisitConstant(int opcode, int offset, int length, com.android.dx.rop.cst.Constant cst, int value)
{@inheritDoc}

        visitCommon(offset, length, true);

        if ((cst instanceof CstMemberRef) || (cst instanceof CstType) ||
            (cst instanceof CstString)) {
            /*
             * Instructions with these sorts of constants have the
             * possibility of throwing, so this instruction needs to
             * end its block (since it can throw, and possible-throws
             * are branch points).
             */
            visitThrowing(offset, length, true);
        }
public voidvisitInvalid(int opcode, int offset, int length)
{@inheritDoc}

        visitCommon(offset, length, true);
public voidvisitLocal(int opcode, int offset, int length, int idx, com.android.dx.rop.type.Type type, int value)
{@inheritDoc}

        if (opcode == ByteOps.RET) {
            visitCommon(offset, length, false);
            targetLists[offset] = IntList.EMPTY;
        } else {
            visitCommon(offset, length, true);
        }
public voidvisitNewarray(int offset, int length, com.android.dx.rop.cst.CstType type, java.util.ArrayList intVals)
{@inheritDoc}

        visitCommon(offset, length, true);
        visitThrowing(offset, length, true);
public voidvisitNoArgs(int opcode, int offset, int length, com.android.dx.rop.type.Type type)
{@inheritDoc}

        switch (opcode) {
            case ByteOps.IRETURN:
            case ByteOps.RETURN: {
                visitCommon(offset, length, false);
                targetLists[offset] = IntList.EMPTY;
                break;
            }
            case ByteOps.ATHROW: {
                visitCommon(offset, length, false);
                visitThrowing(offset, length, false);
                break;
            }
            case ByteOps.IALOAD:
            case ByteOps.LALOAD:
            case ByteOps.FALOAD:
            case ByteOps.DALOAD:
            case ByteOps.AALOAD:
            case ByteOps.BALOAD:
            case ByteOps.CALOAD:
            case ByteOps.SALOAD:
            case ByteOps.IASTORE:
            case ByteOps.LASTORE:
            case ByteOps.FASTORE:
            case ByteOps.DASTORE:
            case ByteOps.AASTORE:
            case ByteOps.BASTORE:
            case ByteOps.CASTORE:
            case ByteOps.SASTORE:
            case ByteOps.ARRAYLENGTH:
            case ByteOps.MONITORENTER:
            case ByteOps.MONITOREXIT: {
                /*
                 * These instructions can all throw, so they have to end
                 * the block they appear in (since throws are branches).
                 */
                visitCommon(offset, length, true);
                visitThrowing(offset, length, true);
                break;
            }
            case ByteOps.IDIV:
            case ByteOps.IREM: {
                /*
                 * The int and long versions of division and remainder may
                 * throw, but not the other types.
                 */
                visitCommon(offset, length, true);
                if ((type == Type.INT) || (type == Type.LONG)) {
                    visitThrowing(offset, length, true);
                }
                break;                
            }
            default: {
                visitCommon(offset, length, true);
                break;
            }
        }
public voidvisitSwitch(int opcode, int offset, int length, SwitchList cases, int padding)
{@inheritDoc}

        visitCommon(offset, length, false);
        addWorkIfNecessary(cases.getDefaultTarget(), true);

        int sz = cases.size();
        for (int i = 0; i < sz; i++) {
            addWorkIfNecessary(cases.getTarget(i), true);
        }

        targetLists[offset] = cases.getTargets();
private voidvisitThrowing(int offset, int length, boolean nextIsLive)
Helper method used by all the visitor methods that deal with opcodes that possibly throw. This method should be called after calling {@link #visitCommon}.

param
offset offset to the instruction
param
length length of the instruction, in bytes
param
nextIsLive true iff the instruction after the indicated one is possibly-live (because this one isn't an unconditional throw)

        int next = offset + length;

        if (nextIsLive) {
            addWorkIfNecessary(next, true);
        }

        ByteCatchList catches = method.getCatches().listFor(offset);
        catchLists[offset] = catches;
        targetLists[offset] = catches.toTargetList(nextIsLive ? next : -1);