path: root/dx/src/com/android/dx/cf/code/BasicBlocker.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.dx.cf.code;

import com.android.dx.rop.cst.Constant;
import com.android.dx.rop.cst.CstCallSiteRef;
import com.android.dx.rop.cst.CstMemberRef;
import com.android.dx.rop.cst.CstString;
import com.android.dx.rop.cst.CstType;
import com.android.dx.rop.type.Type;
import com.android.dx.util.Bits;
import com.android.dx.util.IntList;
import java.util.ArrayList;

/**
 * Utility that identifies basic blocks in bytecode.
 */
public final class BasicBlocker implements BytecodeArray.Visitor {
    /** {@code non-null;} method being converted */
    private final ConcreteMethod method;

    /**
     * {@code non-null;} work set; bits indicate offsets in need of
     * examination
     */
    private final int[] workSet;

    /**
     * {@code 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[] liveSet;

    /**
     * {@code non-null;} block start set; bits indicate the starts of
     * basic blocks, including the opcodes that start blocks of
     * definitely-dead code
     */
    private final int[] blockSet;

    /**
     * {@code non-null, sparse;} for each instruction offset to a branch of
     * some sort, the list of targets for that instruction
     */
    private final IntList[] targetLists;

    /**
     * {@code non-null, sparse;} for each instruction offset to a throwing
     * instruction, the list of exception handlers for that instruction
     */
    private final ByteCatchList[] catchLists;

    /** offset of the previously parsed bytecode */
    private int previousOffset;

    /**
     * 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 {@code non-null;} method to convert
     * @return {@code non-null;} list of basic blocks
     */
    public static ByteBlockList identifyBlocks(ConcreteMethod method) {
        BasicBlocker bb = new BasicBlocker(method);

        bb.doit();
        return bb.getBlockList();
    }

    /**
     * Constructs an instance. This class is not publicly instantiable; use
     * {@link #identifyBlocks}.
     *
     * @param method {@code non-null;} method to convert
     */
    private BasicBlocker(ConcreteMethod method) {
        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;
    }

    /*
     * Note: These methods are defined implementation of the interface
     * BytecodeArray.Visitor; since the class isn't publicly
     * instantiable, no external code ever gets a chance to actually
     * call these methods.
     */

    /** {@inheritDoc} */
    public void visitInvalid(int opcode, int offset, int length) {
        visitCommon(offset, length, true);
    }

    /** {@inheritDoc} */
    public void visitNoArgs(int opcode, int offset, int length, Type type) {
        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;
            }
        }
    }

    /** {@inheritDoc} */
    public void visitLocal(int opcode, int offset, int length,
            int idx, Type type, int value) {
        if (opcode == ByteOps.RET) {
            visitCommon(offset, length, false);
            targetLists[offset] = IntList.EMPTY;
        } else {
            visitCommon(offset, length, true);
        }
    }

    /** {@inheritDoc} */
    public void visitConstant(int opcode, int offset, int length,
            Constant cst, int value) {
        visitCommon(offset, length, true);

        if ((cst instanceof CstMemberRef) || (cst instanceof CstType) ||
            (cst instanceof CstString) || (cst instanceof CstCallSiteRef)) {
            /*
             * 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);
        }
    }

    /** {@inheritDoc} */
    public void visitBranch(int opcode, int offset, int length,
            int target) {
        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);
    }

    /** {@inheritDoc} */
    public void visitSwitch(int opcode, int offset, int length,
            SwitchList cases, int padding) {
        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();
    }

    /** {@inheritDoc} */
    public void visitNewarray(int offset, int length, CstType type,
            ArrayList<Constant> intVals) {
        visitCommon(offset, length, true);
        visitThrowing(offset, length, true);
    }

    /**
     * Extracts the list of basic blocks from the bit sets.
     *
     * @return {@code non-null;} the list of basic blocks
     */
    private ByteBlockList getBlockList() {
        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;
    }

    /**
     * Does basic block identification.
     */
    private void doit() {
        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);
                }
            }
        }
    }

    /**
     * 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 {@code true} iff this instruction starts a
     * basic block
     */
    private void addWorkIfNecessary(int offset, boolean blockStart) {
        if (!Bits.get(liveSet, offset)) {
            Bits.set(workSet, offset);
        }

        if (blockStart) {
            Bits.set(blockSet, offset);
        }
    }

    /**
     * Helper method used by all the visitor methods.
     *
     * @param offset offset to the instruction
     * @param length length of the instruction, in bytes
     * @param nextIsLive {@code true} iff the instruction after
     * the indicated one is possibly-live (because this one isn't an
     * unconditional branch, a return, or a switch)
     */
    private void visitCommon(int offset, int length, boolean nextIsLive) {
        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);
        }
    }

    /**
     * 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 {@code true} iff the instruction after
     * the indicated one is possibly-live (because this one isn't an
     * unconditional throw)
     */
    private void visitThrowing(int offset, int length, boolean nextIsLive) {
        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);
    }

    /**
     * {@inheritDoc}
     */
    public void setPreviousOffset(int offset) {
        previousOffset = offset;
    }

    /**
     * {@inheritDoc}
     */
    public int getPreviousOffset() {
        return previousOffset;
    }
}