summaryrefslogtreecommitdiff
path: root/dx/src/com/android/dx/cf/code/BasicBlocker.java
diff options
context:
space:
mode:
Diffstat (limited to 'dx/src/com/android/dx/cf/code/BasicBlocker.java')
-rw-r--r--dx/src/com/android/dx/cf/code/BasicBlocker.java452
1 files changed, 452 insertions, 0 deletions
diff --git a/dx/src/com/android/dx/cf/code/BasicBlocker.java b/dx/src/com/android/dx/cf/code/BasicBlocker.java
new file mode 100644
index 0000000..8fb9560
--- /dev/null
+++ b/dx/src/com/android/dx/cf/code/BasicBlocker.java
@@ -0,0 +1,452 @@
+/*
+ * 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 {
+ /** {@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)) {
+ /*
+ * 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;
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-28 06:28:11 +0000