/*
* 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.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 {
/** non-null; method being converted */
private final ConcreteMethod method;
/** non-null; work set; bits indicate offsets in need of examination */
private final int[] workSet;
/**
* 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;
/**
* 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;
/**
* non-null, sparse; for each instruction offset to a branch of
* some sort, the list of targets for that instruction
*/
private final IntList[] targetLists;
/**
* 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 non-null; method to convert
* @return 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 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)) {
/*
* 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 non-null; the list of basic blocks
*/
private ByteBlockList getBlockList() {
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;
}
/**
* 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</code> 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</code> 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</code> 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;
}
}
|
