Progress on liveness analysis.
Compute basic blocks and their predecessors, necessary for backward flow
analysis. This is a work in progress and isn't yet enabled.
(When enabled, verification takes 20% longer, so there's some room for
improvement on performance.)
Also, this changes the "generate register maps" setting to be enabled
by default, and allows a "no" prefix on -Xgenregmap to disable it.
Bug 2534655
Change-Id: Id2e8512f53fc454ce2184879ab663ed7121274b6
diff --git a/vm/Dvm.mk b/vm/Dvm.mk
index 140372d..43cdc41 100644
--- a/vm/Dvm.mk
+++ b/vm/Dvm.mk
@@ -141,6 +141,7 @@
analysis/Optimize.c \
analysis/RegisterMap.c \
analysis/VerifySubs.c \
+ analysis/VfyBasicBlock.c \
hprof/Hprof.c \
hprof/HprofClass.c \
hprof/HprofHeap.c \
diff --git a/vm/Globals.h b/vm/Globals.h
index c2639cb..bea7c2c 100644
--- a/vm/Globals.h
+++ b/vm/Globals.h
@@ -62,6 +62,22 @@
} ExecutionMode;
/*
+ * Register map generation mode. Only applicable when generateRegisterMaps
+ * is enabled. (The "disabled" state is not folded into this because
+ * there are callers like dexopt that want to enable/disable without
+ * specifying the configuration details.)
+ *
+ * "TypePrecise" is slower and requires additional storage for the register
+ * maps, but allows type-precise GC. "LivePrecise" is even slower and
+ * requires additional heap during processing, but allows live-precise GC.
+ */
+typedef enum {
+ kRegisterMapModeUnknown = 0,
+ kRegisterMapModeTypePrecise,
+ kRegisterMapModeLivePrecise
+} RegisterMapMode;
+
+/*
* All fields are initialized to zero.
*
* Storage allocated here must be freed by a subsystem shutdown function or
@@ -118,6 +134,9 @@
DexOptimizerMode dexOptMode;
DexClassVerifyMode classVerifyMode;
+ bool generateRegisterMaps;
+ RegisterMapMode registerMapMode;
+
bool monitorVerification;
bool dexOptForSmp;
@@ -128,7 +147,6 @@
bool preciseGc;
bool preVerify;
bool postVerify;
- bool generateRegisterMaps;
bool concurrentMarkSweep;
bool verifyCardTable;
diff --git a/vm/Init.c b/vm/Init.c
index e1e7711..741799d 100644
--- a/vm/Init.c
+++ b/vm/Init.c
@@ -119,7 +119,7 @@
dvmFprintf(stderr, " -Xgc:[no]postverify\n");
dvmFprintf(stderr, " -Xgc:[no]concurrent\n");
dvmFprintf(stderr, " -Xgc:[no]verifycardtable\n");
- dvmFprintf(stderr, " -Xgenregmap\n");
+ dvmFprintf(stderr, " -X[no]genregmap\n");
dvmFprintf(stderr, " -Xverifyopt:[no]checkmon\n");
dvmFprintf(stderr, " -Xcheckdexsum\n");
#if defined(WITH_JIT)
@@ -983,7 +983,8 @@
} else if (strcmp(argv[i], "-Xgenregmap") == 0) {
gDvm.generateRegisterMaps = true;
- LOGV("Register maps will be generated during verification\n");
+ } else if (strcmp(argv[i], "-Xnogenregmap") == 0) {
+ gDvm.generateRegisterMaps = false;
} else if (strcmp(argv[i], "Xverifyopt:checkmon") == 0) {
gDvm.monitorVerification = true;
@@ -1083,6 +1084,8 @@
gDvm.classVerifyMode = VERIFY_MODE_ALL;
gDvm.dexOptMode = OPTIMIZE_MODE_VERIFIED;
gDvm.monitorVerification = false;
+ gDvm.generateRegisterMaps = true;
+ gDvm.registerMapMode = kRegisterMapModeTypePrecise;
/*
* Default execution mode.
diff --git a/vm/PointerSet.c b/vm/PointerSet.c
index 862f733..ca7b537 100644
--- a/vm/PointerSet.c
+++ b/vm/PointerSet.c
@@ -267,7 +267,8 @@
*/
void dvmPointerSetDump(const PointerSet* pSet)
{
+ LOGI("PointerSet %p\n", pSet);
int i;
for (i = 0; i < pSet->count; i++)
- printf(" %p", pSet->list[i]);
+ LOGI(" %2d: %p", i, pSet->list[i]);
}
diff --git a/vm/analysis/CodeVerify.c b/vm/analysis/CodeVerify.c
index 3d9d270..aa41d82 100644
--- a/vm/analysis/CodeVerify.c
+++ b/vm/analysis/CodeVerify.c
@@ -3445,6 +3445,14 @@
vdata->registerLines = NULL; /* don't set this until we need it */
/*
+ * Compute basic blocks if we want to do liveness analysis.
+ */
+ if (gDvm.registerMapMode == kRegisterMapModeLivePrecise) {
+ if (!dvmComputeVfyBasicBlocks(vdata))
+ goto bail;
+ }
+
+ /*
* Initialize the types of the registers that correspond to the
* method arguments. We can determine this from the method signature.
*/
@@ -3763,7 +3771,7 @@
RegisterLine* workLine = ®Table->workLine;
const DexFile* pDexFile = meth->clazz->pDvmDex->pDexFile;
ClassObject* resClass;
- int branchTarget = 0;
+ s4 branchTarget = 0;
const int insnRegCount = meth->registersSize;
RegType tmpType;
DecodedInstruction decInsn;
@@ -5754,7 +5762,7 @@
if ((nextFlags & kInstrCanBranch) != 0) {
bool isConditional;
- if (!dvmGetBranchTarget(meth, insnFlags, insnIdx, &branchTarget,
+ if (!dvmGetBranchOffset(meth, insnFlags, insnIdx, &branchTarget,
&isConditional))
{
/* should never happen after static verification */
diff --git a/vm/analysis/CodeVerify.h b/vm/analysis/CodeVerify.h
index 85b2e5e..b9147ef 100644
--- a/vm/analysis/CodeVerify.h
+++ b/vm/analysis/CodeVerify.h
@@ -21,6 +21,7 @@
#define _DALVIK_CODEVERIFY
#include "analysis/VerifySubs.h"
+#include "analysis/VfyBasicBlock.h"
/*
@@ -187,6 +188,12 @@
*/
size_t newInstanceCount;
size_t monitorEnterCount;
+
+ /*
+ * Array of pointers to basic blocks, one entry per code unit. Used
+ * for liveness analysis.
+ */
+ VfyBasicBlock** basicBlocks;
} VerifierData;
diff --git a/vm/analysis/DexVerify.c b/vm/analysis/DexVerify.c
index 2e2d267..1a931ad 100644
--- a/vm/analysis/DexVerify.c
+++ b/vm/analysis/DexVerify.c
@@ -111,7 +111,7 @@
i += width;
insns += width;
}
- if (i != (int) dvmGetMethodInsnsSize(meth)) {
+ if (i != (int) vdata->insnsSize) {
LOG_VFY_METH(meth, "VFY: code did not end where expected (%d vs. %d)\n",
i, dvmGetMethodInsnsSize(meth));
goto bail;
@@ -140,19 +140,16 @@
const DexCode* pCode = dvmGetMethodCode(meth);
u4 triesSize = pCode->triesSize;
const DexTry* pTries;
- u4 handlersSize;
- u4 offset;
- u4 i;
+ u4 idx;
if (triesSize == 0) {
return true;
}
pTries = dexGetTries(pCode);
- handlersSize = dexGetHandlersSize(pCode);
- for (i = 0; i < triesSize; i++) {
- const DexTry* pTry = &pTries[i];
+ for (idx = 0; idx < triesSize; idx++) {
+ const DexTry* pTry = &pTries[idx];
u4 start = pTry->startAddr;
u4 end = start + pTry->insnCount;
u4 addr;
@@ -180,8 +177,9 @@
}
/* Iterate over each of the handlers to verify target addresses. */
- offset = dexGetFirstHandlerOffset(pCode);
- for (i = 0; i < handlersSize; i++) {
+ u4 handlersSize = dexGetHandlersSize(pCode);
+ u4 offset = dexGetFirstHandlerOffset(pCode);
+ for (idx = 0; idx < handlersSize; idx++) {
DexCatchIterator iterator;
dexCatchIteratorInit(&iterator, pCode, offset);
@@ -252,6 +250,7 @@
vdata.insnRegCount = meth->registersSize;
vdata.insnFlags = NULL;
vdata.uninitMap = NULL;
+ vdata.basicBlocks = NULL;
/*
* If there aren't any instructions, make sure that's expected, then
@@ -285,8 +284,7 @@
* TODO: Consider keeping a reusable pre-allocated array sitting
* around for smaller methods.
*/
- vdata.insnFlags = (InsnFlags*)
- calloc(dvmGetMethodInsnsSize(meth), sizeof(InsnFlags));
+ vdata.insnFlags = (InsnFlags*) calloc(vdata.insnsSize, sizeof(InsnFlags));
if (vdata.insnFlags == NULL)
goto bail;
@@ -307,12 +305,14 @@
/*
* Set the "in try" flags for all instructions guarded by a "try" block.
+ * Also sets the "branch target" flag on exception handlers.
*/
if (!scanTryCatchBlocks(meth, vdata.insnFlags))
goto bail;
/*
- * Perform static instruction verification.
+ * Perform static instruction verification. Also sets the "branch
+ * target" flags.
*/
if (!verifyInstructions(&vdata))
goto bail;
@@ -332,6 +332,7 @@
result = true;
bail:
+ dvmFreeVfyBasicBlocks(&vdata);
dvmFreeUninitInstanceMap(vdata.uninitMap);
free(vdata.insnFlags);
return result;
@@ -717,10 +718,10 @@
int curOffset, bool selfOkay)
{
const int insnCount = dvmGetMethodInsnsSize(meth);
- int offset, absOffset;
+ s4 offset, absOffset;
bool isConditional;
- if (!dvmGetBranchTarget(meth, insnFlags, curOffset, &offset,
+ if (!dvmGetBranchOffset(meth, insnFlags, curOffset, &offset,
&isConditional))
return false;
@@ -1208,8 +1209,12 @@
* This instruction is probably a GC point. Branch instructions
* only qualify if they go backward, so for those we need to
* check the offset.
+ *
+ * TODO: we could also scan the targets of a "switch" statement,
+ * and if none of them branch backward we could ignore that
+ * instruction as well.
*/
- int offset;
+ s4 offset;
bool unused;
if ((opFlags & kInstrCanBranch) != 0) {
/*
@@ -1217,7 +1222,7 @@
* component was tagged with kVfyBranch, but it's easier
* to just grab it again than cart the state around.
*/
- if (!dvmGetBranchTarget(meth, insnFlags, codeOffset, &offset,
+ if (!dvmGetBranchOffset(meth, insnFlags, codeOffset, &offset,
&unused))
{
/* should never happen */
diff --git a/vm/analysis/VerifySubs.c b/vm/analysis/VerifySubs.c
index df1dcaf..cbe8af7 100644
--- a/vm/analysis/VerifySubs.c
+++ b/vm/analysis/VerifySubs.c
@@ -79,8 +79,8 @@
*
* Returns "false" on failure (e.g. this isn't a branch instruction).
*/
-bool dvmGetBranchTarget(const Method* meth, InsnFlags* insnFlags,
- int curOffset, int* pOffset, bool* pConditional)
+bool dvmGetBranchOffset(const Method* meth, const InsnFlags* insnFlags,
+ int curOffset, s4* pOffset, bool* pConditional)
{
const u2* insns = meth->insns + curOffset;
diff --git a/vm/analysis/VerifySubs.h b/vm/analysis/VerifySubs.h
index f145fff..9449e64 100644
--- a/vm/analysis/VerifySubs.h
+++ b/vm/analysis/VerifySubs.h
@@ -61,9 +61,9 @@
void dvmLogUnableToResolveClass(const char* missingClassDescr,
const Method* meth);
-/* extract the relative branch target from a branch instruction */
-bool dvmGetBranchTarget(const Method* meth, InsnFlags* insnFlags,
- int curOffset, int* pOffset, bool* pConditional);
+/* extract the relative branch offset from a branch instruction */
+bool dvmGetBranchOffset(const Method* meth, const InsnFlags* insnFlags,
+ int curOffset, s4* pOffset, bool* pConditional);
/* return a RegType enumeration value that "value" just fits into */
char dvmDetermineCat1Const(s4 value);
diff --git a/vm/analysis/VfyBasicBlock.c b/vm/analysis/VfyBasicBlock.c
new file mode 100644
index 0000000..59d395e
--- /dev/null
+++ b/vm/analysis/VfyBasicBlock.c
@@ -0,0 +1,530 @@
+/*
+ * Copyright (C) 2010 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.
+ */
+
+/*
+ * Verifier basic block functions.
+ */
+#include "Dalvik.h"
+#include "analysis/VfyBasicBlock.h"
+#include "analysis/CodeVerify.h"
+#include "analysis/VerifySubs.h"
+#include "libdex/DexCatch.h"
+#include "libdex/InstrUtils.h"
+
+
+/*
+ * Extract the list of catch handlers from "pTry" into "addrBuf".
+ *
+ * Returns the size of the catch handler list. If the return value
+ * exceeds "addrBufSize", the items at the end of the list will not be
+ * represented in the output array, and this function should be called
+ * again with a larger buffer.
+ */
+static u4 extractCatchHandlers(const DexCode* pCode, const DexTry* pTry,
+ u4* addrBuf, size_t addrBufSize)
+{
+ DexCatchIterator iterator;
+ unsigned int idx = 0;
+
+ dexCatchIteratorInit(&iterator, pCode, pTry->handlerOff);
+ while (true) {
+ DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
+ if (handler == NULL)
+ break;
+
+ if (idx < addrBufSize) {
+ addrBuf[idx] = handler->address;
+ }
+ idx++;
+ }
+
+ return idx;
+}
+
+/*
+ * Returns "true" if the instruction represents a data chunk, such as a
+ * switch statement block.
+ */
+static bool isDataChunk(u2 insn)
+{
+ return (insn == kPackedSwitchSignature ||
+ insn == kSparseSwitchSignature ||
+ insn == kArrayDataSignature);
+}
+
+/*
+ * Alloc a basic block in the specified slot. The storage will be
+ * initialized.
+ */
+static VfyBasicBlock* allocVfyBasicBlock(VerifierData* vdata, u4 idx)
+{
+ VfyBasicBlock* newBlock = (VfyBasicBlock*) calloc(1, sizeof(VfyBasicBlock));
+ if (newBlock == NULL)
+ return NULL;
+
+ newBlock->predecessors = dvmPointerSetAlloc(8);
+ if (newBlock->predecessors == NULL) {
+ free(newBlock);
+ return NULL;
+ }
+
+ newBlock->firstAddr = (u4) -1; // DEBUG
+
+ return newBlock;
+}
+
+/*
+ * Add "curBlock" to the predecessor list in "targetIdx".
+ */
+static bool addToPredecessor(VerifierData* vdata, VfyBasicBlock* curBlock,
+ u4 targetIdx)
+{
+ assert(targetIdx < vdata->insnsSize);
+
+ /*
+ * Allocate the target basic block if necessary. This will happen
+ * on e.g. forward branches.
+ *
+ * We can't fill in all the fields, but that will happen automatically
+ * when we get to that part of the code.
+ */
+ VfyBasicBlock* targetBlock = vdata->basicBlocks[targetIdx];
+ if (targetBlock == NULL) {
+ targetBlock = allocVfyBasicBlock(vdata, targetIdx);
+ if (targetBlock == NULL)
+ return false;
+ vdata->basicBlocks[targetIdx] = targetBlock;
+ }
+
+ PointerSet* preds = targetBlock->predecessors;
+ bool added = dvmPointerSetAddEntry(preds, curBlock);
+ if (!added) {
+ /*
+ * This happens sometimes for packed-switch instructions, where
+ * the same target address appears more than once. Also, a
+ * (pointless) conditional branch to the next instruction will
+ * trip over this.
+ */
+ LOGV("ODD: point set for targ=0x%04x (%p) already had block "
+ "fir=0x%04x (%p)\n",
+ targetIdx, targetBlock, curBlock->firstAddr, curBlock);
+ }
+
+ return true;
+}
+
+/*
+ * Add ourselves to the predecessor list in all blocks we might transfer
+ * control to.
+ *
+ * There are four ways to proceed to a new instruction:
+ * (1) continue to the following instruction
+ * (2) [un]conditionally branch to a specific location
+ * (3) conditionally branch through a "switch" statement
+ * (4) throw an exception
+ *
+ * Returning from the method (via a return statement or an uncaught
+ * exception) are not interesting for liveness analysis.
+ */
+static bool setPredecessors(VerifierData* vdata, VfyBasicBlock* curBlock,
+ u4 curIdx, OpcodeFlags opFlags, u4 nextIdx, u4* handlerList,
+ size_t numHandlers)
+{
+ const InsnFlags* insnFlags = vdata->insnFlags;
+ const Method* meth = vdata->method;
+
+ unsigned int handlerIdx;
+ for (handlerIdx = 0; handlerIdx < numHandlers; handlerIdx++) {
+ if (!addToPredecessor(vdata, curBlock, handlerList[handlerIdx]))
+ return false;
+ }
+
+ if ((opFlags & kInstrCanContinue) != 0) {
+ if (!addToPredecessor(vdata, curBlock, nextIdx))
+ return false;
+ }
+ if ((opFlags & kInstrCanBranch) != 0) {
+ bool unused, gotBranch;
+ s4 branchOffset, absOffset;
+
+ gotBranch = dvmGetBranchOffset(meth, insnFlags, curIdx,
+ &branchOffset, &unused);
+ assert(gotBranch);
+ absOffset = curIdx + branchOffset;
+ assert(absOffset >= 0 && (u4) absOffset < vdata->insnsSize);
+
+ if (!addToPredecessor(vdata, curBlock, absOffset))
+ return false;
+ }
+
+ if ((opFlags & kInstrCanSwitch) != 0) {
+ const u2* curInsn = &meth->insns[curIdx];
+ const u2* dataPtr;
+
+ /* these values have already been verified, so we can trust them */
+ s4 offsetToData = curInsn[1] | ((s4) curInsn[2]) << 16;
+ dataPtr = curInsn + offsetToData;
+
+ /*
+ * dataPtr points to the start of the switch data. The first
+ * item is the NOP+magic, the second is the number of entries in
+ * the switch table.
+ */
+ u2 switchCount = dataPtr[1];
+
+ /*
+ * Skip past the ident field, size field, and the first_key field
+ * (for packed) or the key list (for sparse).
+ */
+ if (dexOpcodeFromCodeUnit(meth->insns[curIdx]) == OP_PACKED_SWITCH) {
+ dataPtr += 4;
+ } else {
+ assert(dexOpcodeFromCodeUnit(meth->insns[curIdx]) ==
+ OP_SPARSE_SWITCH);
+ dataPtr += 2 + 2 * switchCount;
+ }
+
+ u4 switchIdx;
+ for (switchIdx = 0; switchIdx < switchCount; switchIdx++) {
+ s4 offset, absOffset;
+
+ offset = (s4) dataPtr[switchIdx*2] |
+ (s4) (dataPtr[switchIdx*2 +1] << 16);
+ absOffset = curIdx + offset;
+ assert(absOffset >= 0 && (u4) absOffset < vdata->insnsSize);
+
+ if (!addToPredecessor(vdata, curBlock, absOffset))
+ return false;
+ }
+ }
+
+ return true;
+}
+
+/*
+ * Dump the contents of the basic blocks.
+ */
+static void dumpBasicBlocks(const VerifierData* vdata)
+{
+ char printBuf[256];
+ unsigned int idx;
+ int count;
+
+ LOGI("Basic blocks for %s.%s:%s\n", vdata->method->clazz->descriptor,
+ vdata->method->name, vdata->method->shorty);
+ for (idx = 0; idx < vdata->insnsSize; idx++) {
+ VfyBasicBlock* block = vdata->basicBlocks[idx];
+ if (block == NULL)
+ continue;
+
+ assert(block->firstAddr == idx);
+ count = snprintf(printBuf, sizeof(printBuf), " %04x-%04x ",
+ block->firstAddr, block->lastAddr);
+
+ PointerSet* preds = block->predecessors;
+ size_t numDeps = dvmPointerSetGetCount(preds);
+
+ if (numDeps > 0) {
+ count += snprintf(printBuf + count, sizeof(printBuf) - count,
+ "preds:");
+
+ unsigned int predIdx;
+ for (predIdx = 0; predIdx < numDeps; predIdx++) {
+ if (count >= (int) sizeof(printBuf))
+ break;
+ const VfyBasicBlock* pred =
+ (const VfyBasicBlock*) dvmPointerSetGetEntry(preds, predIdx);
+ count += snprintf(printBuf + count, sizeof(printBuf) - count,
+ "%04x(%p),", pred->firstAddr, pred);
+ }
+ } else {
+ count += snprintf(printBuf + count, sizeof(printBuf) - count,
+ "(no preds)");
+ }
+
+ LOGI("%s", printBuf);
+ }
+}
+
+
+/*
+ * Generate a list of basic blocks and related information.
+ *
+ * On success, returns "true" with vdata->basicBlocks initialized.
+ */
+bool dvmComputeVfyBasicBlocks(VerifierData* vdata)
+{
+ const InsnFlags* insnFlags = vdata->insnFlags;
+ const Method* meth = vdata->method;
+ const u4 insnsSize = vdata->insnsSize;
+ const DexCode* pCode = dvmGetMethodCode(meth);
+ const DexTry* pTries = NULL;
+ const size_t kHandlerStackAllocSize = 16; /* max seen so far is 7 */
+ u4 handlerAddrs[kHandlerStackAllocSize];
+ u4* handlerListAlloc = NULL;
+ u4* handlerList = NULL;
+ size_t numHandlers = 0;
+ u4 idx, blockStartAddr;
+ bool result = false;
+
+ bool verbose = false;
+ if (false) {
+ if (strcmp(meth->clazz->descriptor, "Ljava/security/Provider;") == 0 &&
+ strcmp(meth->name, "entrySet") == 0)
+ {
+ verbose = true;
+ }
+ }
+
+ if (verbose) {
+ LOGI("Basic blocks for %s.%s:%s\n",
+ meth->clazz->descriptor, meth->name, meth->shorty);
+ }
+
+ /*
+ * Allocate a data structure that allows us to map from an address to
+ * the corresponding basic block. Initially all pointers are NULL.
+ * They are populated on demand as we proceed (either when we reach a
+ * new BB, or when we need to add an item to the predecessor list in
+ * a not-yet-reached BB).
+ *
+ * Only the first instruction in the block points to the BB structure;
+ * the rest remain NULL.
+ */
+ vdata->basicBlocks =
+ (VfyBasicBlock**) calloc(insnsSize, sizeof(VfyBasicBlock*));
+ if (vdata->basicBlocks == NULL)
+ goto bail;
+
+ /*
+ * The "tries" list is a series of non-overlapping regions with a list
+ * of "catch" handlers. Rather than do the "find a matching try block"
+ * computation at each step, we just walk the "try" list in parallel.
+ *
+ * Not all methods have "try" blocks. If this one does, we init tryEnd
+ * to zero, so that the (exclusive bound) range check trips immediately.
+ */
+ u4 tryIndex = 0, tryStart = 0, tryEnd = 0;
+ if (pCode->triesSize != 0) {
+ pTries = dexGetTries(pCode);
+ }
+
+ u4 debugBBIndex = 0;
+
+ /*
+ * The address associated with a basic block is the start address.
+ */
+ blockStartAddr = 0;
+
+ for (idx = 0; idx < insnsSize; ) {
+ /*
+ * Make sure we're pointing at the right "try" block. It should
+ * not be possible to "jump over" a block, so if we're no longer
+ * in the correct one we can just advance to the next.
+ */
+ if (pTries != NULL && idx >= tryEnd) {
+ if (tryIndex == pCode->triesSize) {
+ /* no more try blocks in this method */
+ pTries = NULL;
+ numHandlers = 0;
+ } else {
+ /*
+ * Extract the set of handlers. We want to avoid doing
+ * this for each block, so we copy them to local storage.
+ * If it doesn't fit in the small stack area, we'll use
+ * the heap instead.
+ *
+ * It's rare to encounter a method with more than half a
+ * dozen possible handlers.
+ */
+ tryStart = pTries[tryIndex].startAddr;
+ tryEnd = tryStart + pTries[tryIndex].insnCount;
+
+ if (handlerListAlloc != NULL) {
+ free(handlerListAlloc);
+ handlerListAlloc = NULL;
+ }
+ numHandlers = extractCatchHandlers(pCode, &pTries[tryIndex],
+ handlerAddrs, kHandlerStackAllocSize);
+ assert(numHandlers > 0); // TODO make sure this is verified
+ if (numHandlers <= kHandlerStackAllocSize) {
+ handlerList = handlerAddrs;
+ } else {
+ LOGD("overflow, numHandlers=%d\n", numHandlers);
+ handlerListAlloc = (u4*) malloc(sizeof(u4) * numHandlers);
+ if (handlerListAlloc == NULL)
+ return false;
+ extractCatchHandlers(pCode, &pTries[tryIndex],
+ handlerListAlloc, numHandlers);
+ handlerList = handlerListAlloc;
+ }
+
+ LOGV("+++ start=%x end=%x numHan=%d\n",
+ tryStart, tryEnd, numHandlers);
+
+ tryIndex++;
+ }
+ }
+
+ /*
+ * Check the current instruction, and possibly aspects of the
+ * next instruction, to see if this instruction ends the current
+ * basic block.
+ *
+ * Instructions that can throw only end the block if there is the
+ * possibility of a local handler catching the exception.
+ */
+ Opcode opcode = dexOpcodeFromCodeUnit(meth->insns[idx]);
+ OpcodeFlags opFlags = dexGetFlagsFromOpcode(opcode);
+ size_t nextIdx = idx + dexGetWidthFromInstruction(&meth->insns[idx]);
+ bool endBB = false;
+ bool ignoreInstr = false;
+
+ if ((opFlags & kInstrCanContinue) == 0) {
+ /* does not continue */
+ endBB = true;
+ } else if ((opFlags & (kInstrCanBranch | kInstrCanSwitch)) != 0) {
+ /* conditionally branches elsewhere */
+ endBB = true;
+ } else if ((opFlags & kInstrCanThrow) != 0 &&
+ dvmInsnIsInTry(insnFlags, idx))
+ {
+ /* throws an exception that might be caught locally */
+ endBB = true;
+ } else if (isDataChunk(meth->insns[idx])) {
+ /*
+ * If this is a data chunk (e.g. switch data) we want to skip
+ * over it entirely. Set endBB so we don't carry this along as
+ * the start of a block, and ignoreInstr so we don't try to
+ * open a basic block for this instruction.
+ */
+ endBB = ignoreInstr = true;
+ } else if (dvmInsnIsBranchTarget(insnFlags, nextIdx)) {
+ /*
+ * We also need to end it if the next instruction is a branch
+ * target. Note we've tagged exception catch blocks as such.
+ *
+ * If we're this far along in the "else" chain, we know that
+ * this isn't a data-chunk NOP, and control can continue to
+ * the next instruction, so we're okay examining "nextIdx".
+ */
+ assert(nextIdx < insnsSize);
+ endBB = true;
+ } else if (opcode == OP_NOP && isDataChunk(meth->insns[nextIdx])) {
+ /*
+ * Handle an odd special case: if this is NOP padding before a
+ * data chunk, also treat it as "ignore". Otherwise it'll look
+ * like a block that starts and doesn't end.
+ */
+ endBB = ignoreInstr = true;
+ } else {
+ /* check: return ops should be caught by absence of can-continue */
+ assert((opFlags & kInstrCanReturn) == 0);
+ }
+
+ if (verbose) {
+ char btc = dvmInsnIsBranchTarget(insnFlags, idx) ? '>' : ' ';
+ char tryc =
+ (pTries != NULL && idx >= tryStart && idx < tryEnd) ? 't' : ' ';
+ bool startBB = (idx == blockStartAddr);
+ const char* startEnd;
+
+
+ if (ignoreInstr)
+ startEnd = "IGNORE";
+ else if (startBB && endBB)
+ startEnd = "START/END";
+ else if (startBB)
+ startEnd = "START";
+ else if (endBB)
+ startEnd = "END";
+ else
+ startEnd = "-";
+
+ LOGI("%04x: %c%c%s #%d\n", idx, tryc, btc, startEnd, debugBBIndex);
+
+ if (pTries != NULL && idx == tryStart) {
+ assert(numHandlers > 0);
+ LOGI(" EXC block: [%04x, %04x) %d:(%04x...)\n",
+ tryStart, tryEnd, numHandlers, handlerList[0]);
+ }
+ }
+
+ if (idx != blockStartAddr) {
+ /* should not be a basic block struct associated with this addr */
+ assert(vdata->basicBlocks[idx] == NULL);
+ }
+ if (endBB) {
+ if (!ignoreInstr) {
+ /*
+ * Create a new BB if one doesn't already exist.
+ */
+ VfyBasicBlock* curBlock = vdata->basicBlocks[blockStartAddr];
+ if (curBlock == NULL) {
+ curBlock = allocVfyBasicBlock(vdata, blockStartAddr);
+ if (curBlock == NULL)
+ return false;
+ vdata->basicBlocks[blockStartAddr] = curBlock;
+ }
+
+ curBlock->firstAddr = blockStartAddr;
+ curBlock->lastAddr = idx;
+
+ if (!setPredecessors(vdata, curBlock, idx, opFlags, nextIdx,
+ handlerList, numHandlers))
+ {
+ goto bail;
+ }
+ }
+
+ blockStartAddr = nextIdx;
+ debugBBIndex++;
+ }
+
+ idx = nextIdx;
+ }
+
+ assert(idx == insnsSize);
+
+ result = true;
+
+ if (verbose)
+ dumpBasicBlocks(vdata);
+
+bail:
+ free(handlerListAlloc);
+ return result;
+}
+
+/*
+ * Free the storage used by basic blocks.
+ */
+void dvmFreeVfyBasicBlocks(VerifierData* vdata)
+{
+ unsigned int idx;
+
+ if (vdata->basicBlocks == NULL)
+ return;
+
+ for (idx = 0; idx < vdata->insnsSize; idx++) {
+ VfyBasicBlock* block = vdata->basicBlocks[idx];
+ if (block == NULL)
+ continue;
+
+ dvmPointerSetFree(block->predecessors);
+ free(block);
+ }
+}
diff --git a/vm/analysis/VfyBasicBlock.h b/vm/analysis/VfyBasicBlock.h
new file mode 100644
index 0000000..c2d6618
--- /dev/null
+++ b/vm/analysis/VfyBasicBlock.h
@@ -0,0 +1,52 @@
+/*
+ * Copyright (C) 2010 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.
+ */
+
+/*
+ * Basic block functions, as used by the verifier. (The names were chosen
+ * to avoid conflicts with similar structures used by the compiler.)
+ */
+#ifndef _DALVIK_VFYBASICBLOCK
+#define _DALVIK_VFYBASICBLOCK
+
+#include "libdex/InstrUtils.h"
+#include "PointerSet.h"
+
+struct VerifierData;
+
+
+/*
+ * Structure representing a basic block.
+ *
+ * This is used for liveness analysis, which is a reverse-flow algorithm,
+ * so we need to mantain a list of predecessors for each block.
+ */
+typedef struct {
+ u4 firstAddr; /* address of first instruction */
+ u4 lastAddr; /* address of last instruction */
+ PointerSet* predecessors; /* set of basic blocks that can flow here */
+} VfyBasicBlock;
+
+/*
+ * Generate a list of basic blocks.
+ */
+bool dvmComputeVfyBasicBlocks(struct VerifierData* vdata);
+
+/*
+ * Free storage allocated by dvmComputeVfyBasicBlocks.
+ */
+void dvmFreeVfyBasicBlocks(struct VerifierData* vdata);
+
+#endif /*_DALVIK_VFYBASICBLOCK*/
