Extend a trace with a backward branch into a loop.
When seeing a trace that ends with a backward branch, exhaust all code
blocks reachable from that trace and try to identify if there exists a
non-nested loop. If the derived loop is found to be too complex or only
acyclic code is seen, revert to the original compilation mechanism to
translate a simple trace.
This CL uses the whole-method parser/dataflow analysis framework to
identify such loops. No optimization/codegen are performed yet.
Bug: 4086718
Change-Id: I19ed3ee53ea1cbda33940c533de8e9220e647156
diff --git a/CleanSpec.mk b/CleanSpec.mk
index 1149aff..3fbdc64 100644
--- a/CleanSpec.mk
+++ b/CleanSpec.mk
@@ -50,6 +50,7 @@
$(call add-clean-step, rm -rf $(OUT)/obj/SHARED_LIBRARIES/libdvm*)
$(call add-clean-step, rm -rf $(OUT)/obj/SHARED_LIBRARIES/libdvm*)
$(call add-clean-step, rm -rf $(OUT)/obj/SHARED_LIBRARIES/libdvm*)
+$(call add-clean-step, rm -rf $(OUT)/obj/SHARED_LIBRARIES/libdvm*)
# ************************************************
# NEWER CLEAN STEPS MUST BE AT THE END OF THE LIST
# ************************************************
diff --git a/vm/Dvm.mk b/vm/Dvm.mk
index aea0b53..c9a776b 100644
--- a/vm/Dvm.mk
+++ b/vm/Dvm.mk
@@ -218,7 +218,7 @@
compiler/InlineTransformation.c \
compiler/IntermediateRep.c \
compiler/Dataflow.c \
- compiler/MethodSSATransformation.c \
+ compiler/SSATransformation.c \
compiler/Loop.c \
compiler/Ralloc.c \
interp/Jit.c
diff --git a/vm/Globals.h b/vm/Globals.h
index ad28e14..df10e36 100644
--- a/vm/Globals.h
+++ b/vm/Globals.h
@@ -878,6 +878,9 @@
/* Flag to dump all compiled code */
bool printMe;
+ /* Per-process debug flag toggled when receiving a SIGUSR2 */
+ bool receivedSIGUSR2;
+
/* Trace profiling mode */
TraceProfilingModes profileMode;
diff --git a/vm/SignalCatcher.c b/vm/SignalCatcher.c
index 9381312..5a5e037 100644
--- a/vm/SignalCatcher.c
+++ b/vm/SignalCatcher.c
@@ -230,6 +230,7 @@
static void handleSigUsr2(void)
{
static int codeCacheResetCount = 0;
+ gDvmJit.receivedSIGUSR2 ^= true;
if ((--codeCacheResetCount & 7) == 0) {
/* Dump all class pointers in the traces */
dvmJitScanAllClassPointers(printAllClass);
diff --git a/vm/compiler/Compiler.h b/vm/compiler/Compiler.h
index 2a0eef4..5d5036f 100644
--- a/vm/compiler/Compiler.h
+++ b/vm/compiler/Compiler.h
@@ -232,6 +232,7 @@
DataFlowAnalysisMode dfaMode,
bool isIterative);
void dvmCompilerMethodSSATransformation(struct CompilationUnit *cUnit);
+bool dvmCompilerBuildLoop(struct CompilationUnit *cUnit);
void dvmCompilerStateRefresh(void);
JitTraceDescription *dvmCopyTraceDescriptor(const u2 *pc,
const struct JitEntry *desc);
diff --git a/vm/compiler/CompilerIR.h b/vm/compiler/CompilerIR.h
index c807877..7b9987b 100644
--- a/vm/compiler/CompilerIR.h
+++ b/vm/compiler/CompilerIR.h
@@ -64,6 +64,12 @@
kCatchEntry,
} BBType;
+typedef enum JitMode {
+ kJitTrace = 0, // Acyclic - all instructions come from the trace descriptor
+ kJitLoop, // Cycle - trace descriptor is used as a hint
+ kJitMethod, // Whole method
+} JitMode;
+
typedef struct ChainCellCounts {
union {
u1 count[kChainingCellLast]; /* include one more space for the gap # */
@@ -148,6 +154,7 @@
typedef struct BasicBlock {
int id;
bool visited;
+ bool hidden;
unsigned int startOffset;
const Method *containingMethod; // For blocks from the callee
BBType blockType;
@@ -249,7 +256,7 @@
const u2 *switchOverflowPad;
/* New fields only for method-based compilation */
- bool methodJitMode;
+ JitMode jitMode;
int numReachableBlocks;
int numDalvikRegisters; // method->registersSize + inlined
BasicBlock *entryBlock;
diff --git a/vm/compiler/Dataflow.c b/vm/compiler/Dataflow.c
index 76744bd..26068a1 100644
--- a/vm/compiler/Dataflow.c
+++ b/vm/compiler/Dataflow.c
@@ -1694,7 +1694,6 @@
const DecodedInstruction *insn = &mir->dalvikInsn;
int opcode = insn->opcode;
int dfAttributes = dvmCompilerDataFlowAttributes[opcode];
- int flags = dexGetFlagsFromOpcode(insn->opcode);
char *ret;
int length;
@@ -1719,6 +1718,7 @@
strcpy(buffer, dexGetOpcodeName(opcode));
}
+ int flags = dexGetFlagsFromOpcode(opcode);
/* For branches, decode the instructions to print out the branch targets */
if (flags & kInstrCanBranch) {
InstructionFormat dalvikFormat = dexGetFormatFromOpcode(insn->opcode);
@@ -2393,6 +2393,7 @@
while (true) {
BasicBlock *bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator);
if (bb == NULL) break;
+ if (bb->hidden == true) continue;
if (bb->blockType == kDalvikByteCode ||
bb->blockType == kTraceEntryBlock ||
bb->blockType == kMethodEntryBlock ||
@@ -2430,6 +2431,7 @@
BasicBlock *bb =
(BasicBlock *) dvmGrowableListIteratorNext(&iterator);
if (bb == NULL) break;
+ if (bb->hidden == true) continue;
change |= (*func)(cUnit, bb);
}
}
diff --git a/vm/compiler/Frontend.c b/vm/compiler/Frontend.c
index 8663c5c..8272fb6 100644
--- a/vm/compiler/Frontend.c
+++ b/vm/compiler/Frontend.c
@@ -416,6 +416,1072 @@
}
/*
+ * Since we are including instructions from possibly a cold method into the
+ * current trace, we need to make sure that all the associated information
+ * with the callee is properly initialized. If not, we punt on this inline
+ * target.
+ *
+ * TODO: volatile instructions will be handled later.
+ */
+bool dvmCompilerCanIncludeThisInstruction(const Method *method,
+ const DecodedInstruction *insn)
+{
+ switch (insn->opcode) {
+ case OP_NEW_INSTANCE:
+ case OP_NEW_INSTANCE_JUMBO:
+ case OP_CHECK_CAST:
+ case OP_CHECK_CAST_JUMBO: {
+ ClassObject *classPtr = (ClassObject *)(void*)
+ (method->clazz->pDvmDex->pResClasses[insn->vB]);
+
+ /* Class hasn't been initialized yet */
+ if (classPtr == NULL) {
+ return false;
+ }
+ return true;
+ }
+ case OP_SGET:
+ case OP_SGET_JUMBO:
+ case OP_SGET_WIDE:
+ case OP_SGET_WIDE_JUMBO:
+ case OP_SGET_OBJECT:
+ case OP_SGET_OBJECT_JUMBO:
+ case OP_SGET_BOOLEAN:
+ case OP_SGET_BOOLEAN_JUMBO:
+ case OP_SGET_BYTE:
+ case OP_SGET_BYTE_JUMBO:
+ case OP_SGET_CHAR:
+ case OP_SGET_CHAR_JUMBO:
+ case OP_SGET_SHORT:
+ case OP_SGET_SHORT_JUMBO:
+ case OP_SPUT:
+ case OP_SPUT_JUMBO:
+ case OP_SPUT_WIDE:
+ case OP_SPUT_WIDE_JUMBO:
+ case OP_SPUT_OBJECT:
+ case OP_SPUT_OBJECT_JUMBO:
+ case OP_SPUT_BOOLEAN:
+ case OP_SPUT_BOOLEAN_JUMBO:
+ case OP_SPUT_BYTE:
+ case OP_SPUT_BYTE_JUMBO:
+ case OP_SPUT_CHAR:
+ case OP_SPUT_CHAR_JUMBO:
+ case OP_SPUT_SHORT:
+ case OP_SPUT_SHORT_JUMBO: {
+ void *fieldPtr = (void*)
+ (method->clazz->pDvmDex->pResFields[insn->vB]);
+
+ if (fieldPtr == NULL) {
+ return false;
+ }
+ return true;
+ }
+ case OP_INVOKE_SUPER:
+ case OP_INVOKE_SUPER_RANGE:
+ case OP_INVOKE_SUPER_JUMBO: {
+ int mIndex = method->clazz->pDvmDex->
+ pResMethods[insn->vB]->methodIndex;
+ const Method *calleeMethod = method->clazz->super->vtable[mIndex];
+ if (calleeMethod == NULL) {
+ return false;
+ }
+ return true;
+ }
+ case OP_INVOKE_SUPER_QUICK:
+ case OP_INVOKE_SUPER_QUICK_RANGE: {
+ const Method *calleeMethod = method->clazz->super->vtable[insn->vB];
+ if (calleeMethod == NULL) {
+ return false;
+ }
+ return true;
+ }
+ case OP_INVOKE_STATIC:
+ case OP_INVOKE_STATIC_RANGE:
+ case OP_INVOKE_STATIC_JUMBO:
+ case OP_INVOKE_DIRECT:
+ case OP_INVOKE_DIRECT_RANGE:
+ case OP_INVOKE_DIRECT_JUMBO: {
+ const Method *calleeMethod =
+ method->clazz->pDvmDex->pResMethods[insn->vB];
+ if (calleeMethod == NULL) {
+ return false;
+ }
+ return true;
+ }
+ case OP_CONST_CLASS:
+ case OP_CONST_CLASS_JUMBO: {
+ void *classPtr = (void*)
+ (method->clazz->pDvmDex->pResClasses[insn->vB]);
+
+ if (classPtr == NULL) {
+ return false;
+ }
+ return true;
+ }
+ case OP_CONST_STRING_JUMBO:
+ case OP_CONST_STRING: {
+ void *strPtr = (void*)
+ (method->clazz->pDvmDex->pResStrings[insn->vB]);
+
+ if (strPtr == NULL) {
+ return false;
+ }
+ return true;
+ }
+ default:
+ return true;
+ }
+}
+
+/* Split an existing block from the specified code offset into two */
+static BasicBlock *splitBlock(CompilationUnit *cUnit,
+ unsigned int codeOffset,
+ BasicBlock *origBlock)
+{
+ MIR *insn = origBlock->firstMIRInsn;
+ while (insn) {
+ if (insn->offset == codeOffset) break;
+ insn = insn->next;
+ }
+ if (insn == NULL) {
+ LOGE("Break split failed");
+ dvmAbort();
+ }
+ BasicBlock *bottomBlock = dvmCompilerNewBB(kDalvikByteCode,
+ cUnit->numBlocks++);
+ dvmInsertGrowableList(&cUnit->blockList, (intptr_t) bottomBlock);
+
+ bottomBlock->startOffset = codeOffset;
+ bottomBlock->firstMIRInsn = insn;
+ bottomBlock->lastMIRInsn = origBlock->lastMIRInsn;
+
+ /* Handle the taken path */
+ bottomBlock->taken = origBlock->taken;
+ if (bottomBlock->taken) {
+ origBlock->taken = NULL;
+ dvmCompilerClearBit(bottomBlock->taken->predecessors, origBlock->id);
+ dvmCompilerSetBit(bottomBlock->taken->predecessors, bottomBlock->id);
+ }
+
+ /* Handle the fallthrough path */
+ bottomBlock->fallThrough = origBlock->fallThrough;
+ origBlock->fallThrough = bottomBlock;
+ dvmCompilerSetBit(bottomBlock->predecessors, origBlock->id);
+ if (bottomBlock->fallThrough) {
+ dvmCompilerClearBit(bottomBlock->fallThrough->predecessors,
+ origBlock->id);
+ dvmCompilerSetBit(bottomBlock->fallThrough->predecessors,
+ bottomBlock->id);
+ }
+
+ /* Handle the successor list */
+ if (origBlock->successorBlockList.blockListType != kNotUsed) {
+ bottomBlock->successorBlockList = origBlock->successorBlockList;
+ origBlock->successorBlockList.blockListType = kNotUsed;
+ GrowableListIterator iterator;
+
+ dvmGrowableListIteratorInit(&bottomBlock->successorBlockList.blocks,
+ &iterator);
+ while (true) {
+ SuccessorBlockInfo *successorBlockInfo =
+ (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator);
+ if (successorBlockInfo == NULL) break;
+ BasicBlock *bb = successorBlockInfo->block;
+ dvmCompilerClearBit(bb->predecessors, origBlock->id);
+ dvmCompilerSetBit(bb->predecessors, bottomBlock->id);
+ }
+ }
+
+ origBlock->lastMIRInsn = insn->prev;
+
+ insn->prev->next = NULL;
+ insn->prev = NULL;
+ return bottomBlock;
+}
+
+/*
+ * Given a code offset, find out the block that starts with it. If the offset
+ * is in the middle of an existing block, split it into two.
+ */
+static BasicBlock *findBlock(CompilationUnit *cUnit,
+ unsigned int codeOffset,
+ bool split, bool create)
+{
+ GrowableList *blockList = &cUnit->blockList;
+ BasicBlock *bb;
+ unsigned int i;
+
+ for (i = 0; i < blockList->numUsed; i++) {
+ bb = (BasicBlock *) blockList->elemList[i];
+ if (bb->blockType != kDalvikByteCode) continue;
+ if (bb->startOffset == codeOffset) return bb;
+ /* Check if a branch jumps into the middle of an existing block */
+ if ((split == true) && (codeOffset > bb->startOffset) &&
+ (bb->lastMIRInsn != NULL) &&
+ (codeOffset <= bb->lastMIRInsn->offset)) {
+ BasicBlock *newBB = splitBlock(cUnit, codeOffset, bb);
+ return newBB;
+ }
+ }
+ if (create) {
+ bb = dvmCompilerNewBB(kDalvikByteCode, cUnit->numBlocks++);
+ dvmInsertGrowableList(&cUnit->blockList, (intptr_t) bb);
+ bb->startOffset = codeOffset;
+ return bb;
+ }
+ return NULL;
+}
+
+/* Dump the CFG into a DOT graph */
+void dumpCFG(CompilationUnit *cUnit, const char *dirPrefix)
+{
+ const Method *method = cUnit->method;
+ FILE *file;
+ char *signature = dexProtoCopyMethodDescriptor(&method->prototype);
+ char startOffset[80];
+ sprintf(startOffset, "_%x", cUnit->entryBlock->fallThrough->startOffset);
+ char *fileName = (char *) dvmCompilerNew(
+ strlen(dirPrefix) +
+ strlen(method->clazz->descriptor) +
+ strlen(method->name) +
+ strlen(signature) +
+ strlen(startOffset) +
+ strlen(".dot") + 1, true);
+ sprintf(fileName, "%s%s%s%s%s.dot", dirPrefix,
+ method->clazz->descriptor, method->name, signature, startOffset);
+ free(signature);
+
+ /*
+ * Convert the special characters into a filesystem- and shell-friendly
+ * format.
+ */
+ int i;
+ for (i = strlen(dirPrefix); fileName[i]; i++) {
+ if (fileName[i] == '/') {
+ fileName[i] = '_';
+ } else if (fileName[i] == ';') {
+ fileName[i] = '#';
+ } else if (fileName[i] == '$') {
+ fileName[i] = '+';
+ } else if (fileName[i] == '(' || fileName[i] == ')') {
+ fileName[i] = '@';
+ } else if (fileName[i] == '<' || fileName[i] == '>') {
+ fileName[i] = '=';
+ }
+ }
+ file = fopen(fileName, "w");
+ if (file == NULL) {
+ return;
+ }
+ fprintf(file, "digraph G {\n");
+
+ fprintf(file, " rankdir=TB\n");
+
+ int numReachableBlocks = cUnit->numReachableBlocks;
+ int idx;
+ const GrowableList *blockList = &cUnit->blockList;
+
+ for (idx = 0; idx < numReachableBlocks; idx++) {
+ int blockIdx = cUnit->dfsOrder.elemList[idx];
+ BasicBlock *bb = (BasicBlock *) dvmGrowableListGetElement(blockList,
+ blockIdx);
+ if (bb == NULL) break;
+ if (bb->blockType == kMethodEntryBlock) {
+ fprintf(file, " entry [shape=Mdiamond];\n");
+ } else if (bb->blockType == kMethodExitBlock) {
+ fprintf(file, " exit [shape=Mdiamond];\n");
+ } else if (bb->blockType == kDalvikByteCode) {
+ fprintf(file, " block%04x [shape=record,label = \"{ \\\n",
+ bb->startOffset);
+ const MIR *mir;
+ for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
+ fprintf(file, " {%04x %s\\l}%s\\\n", mir->offset,
+ mir->ssaRep ?
+ dvmCompilerFullDisassembler(cUnit, mir) :
+ dexGetOpcodeName(mir->dalvikInsn.opcode),
+ mir->next ? " | " : " ");
+ }
+ fprintf(file, " }\"];\n\n");
+ } else if (bb->blockType == kExceptionHandling) {
+ char blockName[BLOCK_NAME_LEN];
+
+ dvmGetBlockName(bb, blockName);
+ fprintf(file, " %s [shape=invhouse];\n", blockName);
+ }
+
+ char blockName1[BLOCK_NAME_LEN], blockName2[BLOCK_NAME_LEN];
+
+ if (bb->taken) {
+ dvmGetBlockName(bb, blockName1);
+ dvmGetBlockName(bb->taken, blockName2);
+ fprintf(file, " %s:s -> %s:n [style=dotted]\n",
+ blockName1, blockName2);
+ }
+ if (bb->fallThrough) {
+ dvmGetBlockName(bb, blockName1);
+ dvmGetBlockName(bb->fallThrough, blockName2);
+ fprintf(file, " %s:s -> %s:n\n", blockName1, blockName2);
+ }
+
+ if (bb->successorBlockList.blockListType != kNotUsed) {
+ fprintf(file, " succ%04x [shape=%s,label = \"{ \\\n",
+ bb->startOffset,
+ (bb->successorBlockList.blockListType == kCatch) ?
+ "Mrecord" : "record");
+ GrowableListIterator iterator;
+ dvmGrowableListIteratorInit(&bb->successorBlockList.blocks,
+ &iterator);
+ SuccessorBlockInfo *successorBlockInfo =
+ (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator);
+
+ int succId = 0;
+ while (true) {
+ if (successorBlockInfo == NULL) break;
+
+ BasicBlock *destBlock = successorBlockInfo->block;
+ SuccessorBlockInfo *nextSuccessorBlockInfo =
+ (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator);
+
+ fprintf(file, " {<f%d> %04x: %04x\\l}%s\\\n",
+ succId++,
+ successorBlockInfo->key,
+ destBlock->startOffset,
+ (nextSuccessorBlockInfo != NULL) ? " | " : " ");
+
+ successorBlockInfo = nextSuccessorBlockInfo;
+ }
+ fprintf(file, " }\"];\n\n");
+
+ dvmGetBlockName(bb, blockName1);
+ fprintf(file, " %s:s -> succ%04x:n [style=dashed]\n",
+ blockName1, bb->startOffset);
+
+ if (bb->successorBlockList.blockListType == kPackedSwitch ||
+ bb->successorBlockList.blockListType == kSparseSwitch) {
+
+ dvmGrowableListIteratorInit(&bb->successorBlockList.blocks,
+ &iterator);
+
+ succId = 0;
+ while (true) {
+ SuccessorBlockInfo *successorBlockInfo =
+ (SuccessorBlockInfo *)
+ dvmGrowableListIteratorNext(&iterator);
+ if (successorBlockInfo == NULL) break;
+
+ BasicBlock *destBlock = successorBlockInfo->block;
+
+ dvmGetBlockName(destBlock, blockName2);
+ fprintf(file, " succ%04x:f%d:e -> %s:n\n",
+ bb->startOffset, succId++,
+ blockName2);
+ }
+ }
+ }
+ fprintf(file, "\n");
+
+ /*
+ * If we need to debug the dominator tree, uncomment the following code
+ */
+#if 1
+ dvmGetBlockName(bb, blockName1);
+ fprintf(file, " cfg%s [label=\"%s\", shape=none];\n",
+ blockName1, blockName1);
+ if (bb->iDom) {
+ dvmGetBlockName(bb->iDom, blockName2);
+ fprintf(file, " cfg%s:s -> cfg%s:n\n\n",
+ blockName2, blockName1);
+ }
+#endif
+ }
+ fprintf(file, "}\n");
+ fclose(file);
+}
+
+/* Verify if all the successor is connected with all the claimed predecessors */
+static bool verifyPredInfo(CompilationUnit *cUnit, BasicBlock *bb)
+{
+ BitVectorIterator bvIterator;
+
+ dvmBitVectorIteratorInit(bb->predecessors, &bvIterator);
+ while (true) {
+ int blockIdx = dvmBitVectorIteratorNext(&bvIterator);
+ if (blockIdx == -1) break;
+ BasicBlock *predBB = (BasicBlock *)
+ dvmGrowableListGetElement(&cUnit->blockList, blockIdx);
+ bool found = false;
+ if (predBB->taken == bb) {
+ found = true;
+ } else if (predBB->fallThrough == bb) {
+ found = true;
+ } else if (predBB->successorBlockList.blockListType != kNotUsed) {
+ GrowableListIterator iterator;
+ dvmGrowableListIteratorInit(&predBB->successorBlockList.blocks,
+ &iterator);
+ while (true) {
+ SuccessorBlockInfo *successorBlockInfo =
+ (SuccessorBlockInfo *)
+ dvmGrowableListIteratorNext(&iterator);
+ if (successorBlockInfo == NULL) break;
+ BasicBlock *succBB = successorBlockInfo->block;
+ if (succBB == bb) {
+ found = true;
+ break;
+ }
+ }
+ }
+ if (found == false) {
+ char blockName1[BLOCK_NAME_LEN], blockName2[BLOCK_NAME_LEN];
+ dvmGetBlockName(bb, blockName1);
+ dvmGetBlockName(predBB, blockName2);
+ dumpCFG(cUnit, "/sdcard/cfg/");
+ LOGE("Successor %s not found from %s",
+ blockName1, blockName2);
+ dvmAbort();
+ }
+ }
+ return true;
+}
+
+/* Identify code range in try blocks and set up the empty catch blocks */
+static void processTryCatchBlocks(CompilationUnit *cUnit)
+{
+ const Method *meth = cUnit->method;
+ const DexCode *pCode = dvmGetMethodCode(meth);
+ int triesSize = pCode->triesSize;
+ int i;
+ int offset;
+
+ if (triesSize == 0) {
+ return;
+ }
+
+ const DexTry *pTries = dexGetTries(pCode);
+ BitVector *tryBlockAddr = cUnit->tryBlockAddr;
+
+ /* Mark all the insn offsets in Try blocks */
+ for (i = 0; i < triesSize; i++) {
+ const DexTry* pTry = &pTries[i];
+ /* all in 16-bit units */
+ int startOffset = pTry->startAddr;
+ int endOffset = startOffset + pTry->insnCount;
+
+ for (offset = startOffset; offset < endOffset; offset++) {
+ dvmCompilerSetBit(tryBlockAddr, offset);
+ }
+ }
+
+ /* Iterate over each of the handlers to enqueue the empty Catch blocks */
+ offset = dexGetFirstHandlerOffset(pCode);
+ int handlersSize = dexGetHandlersSize(pCode);
+
+ for (i = 0; i < handlersSize; i++) {
+ DexCatchIterator iterator;
+ dexCatchIteratorInit(&iterator, pCode, offset);
+
+ for (;;) {
+ DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
+
+ if (handler == NULL) {
+ break;
+ }
+
+ /*
+ * Create dummy catch blocks first. Since these are created before
+ * other blocks are processed, "split" is specified as false.
+ */
+ findBlock(cUnit, handler->address,
+ /* split */
+ false,
+ /* create */
+ true);
+ }
+
+ offset = dexCatchIteratorGetEndOffset(&iterator, pCode);
+ }
+}
+
+/* Process instructions with the kInstrCanBranch flag */
+static void processCanBranch(CompilationUnit *cUnit, BasicBlock *curBlock,
+ MIR *insn, int curOffset, int width, int flags,
+ const u2* codePtr, const u2* codeEnd)
+{
+ int target = curOffset;
+ switch (insn->dalvikInsn.opcode) {
+ case OP_GOTO:
+ case OP_GOTO_16:
+ case OP_GOTO_32:
+ target += (int) insn->dalvikInsn.vA;
+ break;
+ case OP_IF_EQ:
+ case OP_IF_NE:
+ case OP_IF_LT:
+ case OP_IF_GE:
+ case OP_IF_GT:
+ case OP_IF_LE:
+ target += (int) insn->dalvikInsn.vC;
+ break;
+ case OP_IF_EQZ:
+ case OP_IF_NEZ:
+ case OP_IF_LTZ:
+ case OP_IF_GEZ:
+ case OP_IF_GTZ:
+ case OP_IF_LEZ:
+ target += (int) insn->dalvikInsn.vB;
+ break;
+ default:
+ LOGE("Unexpected opcode(%d) with kInstrCanBranch set",
+ insn->dalvikInsn.opcode);
+ dvmAbort();
+ }
+ BasicBlock *takenBlock = findBlock(cUnit, target,
+ /* split */
+ true,
+ /* create */
+ true);
+ curBlock->taken = takenBlock;
+ dvmCompilerSetBit(takenBlock->predecessors, curBlock->id);
+
+ /* Always terminate the current block for conditional branches */
+ if (flags & kInstrCanContinue) {
+ BasicBlock *fallthroughBlock = findBlock(cUnit,
+ curOffset + width,
+ /*
+ * If the method is processed
+ * in sequential order from the
+ * beginning, we don't need to
+ * specify split for continue
+ * blocks. However, this
+ * routine can be called by
+ * compileLoop, which starts
+ * parsing the method from an
+ * arbitrary address in the
+ * method body.
+ */
+ true,
+ /* create */
+ true);
+ curBlock->fallThrough = fallthroughBlock;
+ dvmCompilerSetBit(fallthroughBlock->predecessors, curBlock->id);
+ } else if (codePtr < codeEnd) {
+ /* Create a fallthrough block for real instructions (incl. OP_NOP) */
+ if (contentIsInsn(codePtr)) {
+ findBlock(cUnit, curOffset + width,
+ /* split */
+ false,
+ /* create */
+ true);
+ }
+ }
+}
+
+/* Process instructions with the kInstrCanSwitch flag */
+static void processCanSwitch(CompilationUnit *cUnit, BasicBlock *curBlock,
+ MIR *insn, int curOffset, int width, int flags)
+{
+ u2 *switchData= (u2 *) (cUnit->method->insns + curOffset +
+ insn->dalvikInsn.vB);
+ int size;
+ int *keyTable;
+ int *targetTable;
+ int i;
+ int firstKey;
+
+ /*
+ * Packed switch data format:
+ * ushort ident = 0x0100 magic value
+ * ushort size number of entries in the table
+ * int first_key first (and lowest) switch case value
+ * int targets[size] branch targets, relative to switch opcode
+ *
+ * Total size is (4+size*2) 16-bit code units.
+ */
+ if (insn->dalvikInsn.opcode == OP_PACKED_SWITCH) {
+ assert(switchData[0] == kPackedSwitchSignature);
+ size = switchData[1];
+ firstKey = switchData[2] | (switchData[3] << 16);
+ targetTable = (int *) &switchData[4];
+ keyTable = NULL; // Make the compiler happy
+ /*
+ * Sparse switch data format:
+ * ushort ident = 0x0200 magic value
+ * ushort size number of entries in the table; > 0
+ * int keys[size] keys, sorted low-to-high; 32-bit aligned
+ * int targets[size] branch targets, relative to switch opcode
+ *
+ * Total size is (2+size*4) 16-bit code units.
+ */
+ } else {
+ assert(switchData[0] == kSparseSwitchSignature);
+ size = switchData[1];
+ keyTable = (int *) &switchData[2];
+ targetTable = (int *) &switchData[2 + size*2];
+ firstKey = 0; // To make the compiler happy
+ }
+
+ if (curBlock->successorBlockList.blockListType != kNotUsed) {
+ LOGE("Successor block list already in use: %d",
+ curBlock->successorBlockList.blockListType);
+ dvmAbort();
+ }
+ curBlock->successorBlockList.blockListType =
+ (insn->dalvikInsn.opcode == OP_PACKED_SWITCH) ?
+ kPackedSwitch : kSparseSwitch;
+ dvmInitGrowableList(&curBlock->successorBlockList.blocks, size);
+
+ for (i = 0; i < size; i++) {
+ BasicBlock *caseBlock = findBlock(cUnit, curOffset + targetTable[i],
+ /* split */
+ true,
+ /* create */
+ true);
+ SuccessorBlockInfo *successorBlockInfo =
+ (SuccessorBlockInfo *) dvmCompilerNew(sizeof(SuccessorBlockInfo),
+ false);
+ successorBlockInfo->block = caseBlock;
+ successorBlockInfo->key = (insn->dalvikInsn.opcode == OP_PACKED_SWITCH)?
+ firstKey + i : keyTable[i];
+ dvmInsertGrowableList(&curBlock->successorBlockList.blocks,
+ (intptr_t) successorBlockInfo);
+ dvmCompilerSetBit(caseBlock->predecessors, curBlock->id);
+ }
+
+ /* Fall-through case */
+ BasicBlock *fallthroughBlock = findBlock(cUnit,
+ curOffset + width,
+ /* split */
+ false,
+ /* create */
+ true);
+ curBlock->fallThrough = fallthroughBlock;
+ dvmCompilerSetBit(fallthroughBlock->predecessors, curBlock->id);
+}
+
+/* Process instructions with the kInstrCanThrow flag */
+static void processCanThrow(CompilationUnit *cUnit, BasicBlock *curBlock,
+ MIR *insn, int curOffset, int width, int flags,
+ BitVector *tryBlockAddr, const u2 *codePtr,
+ const u2* codeEnd)
+{
+ const Method *method = cUnit->method;
+ const DexCode *dexCode = dvmGetMethodCode(method);
+
+ /* In try block */
+ if (dvmIsBitSet(tryBlockAddr, curOffset)) {
+ DexCatchIterator iterator;
+
+ if (!dexFindCatchHandler(&iterator, dexCode, curOffset)) {
+ LOGE("Catch block not found in dexfile for insn %x in %s",
+ curOffset, method->name);
+ dvmAbort();
+
+ }
+ if (curBlock->successorBlockList.blockListType != kNotUsed) {
+ LOGE("Successor block list already in use: %d",
+ curBlock->successorBlockList.blockListType);
+ dvmAbort();
+ }
+ curBlock->successorBlockList.blockListType = kCatch;
+ dvmInitGrowableList(&curBlock->successorBlockList.blocks, 2);
+
+ for (;;) {
+ DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
+
+ if (handler == NULL) {
+ break;
+ }
+
+ BasicBlock *catchBlock = findBlock(cUnit, handler->address,
+ /* split */
+ false,
+ /* create */
+ false);
+
+ SuccessorBlockInfo *successorBlockInfo =
+ (SuccessorBlockInfo *) dvmCompilerNew(sizeof(SuccessorBlockInfo),
+ false);
+ successorBlockInfo->block = catchBlock;
+ successorBlockInfo->key = handler->typeIdx;
+ dvmInsertGrowableList(&curBlock->successorBlockList.blocks,
+ (intptr_t) successorBlockInfo);
+ dvmCompilerSetBit(catchBlock->predecessors, curBlock->id);
+ }
+ } else {
+ BasicBlock *ehBlock = dvmCompilerNewBB(kExceptionHandling,
+ cUnit->numBlocks++);
+ curBlock->taken = ehBlock;
+ dvmInsertGrowableList(&cUnit->blockList, (intptr_t) ehBlock);
+ ehBlock->startOffset = curOffset;
+ dvmCompilerSetBit(ehBlock->predecessors, curBlock->id);
+ }
+
+ /*
+ * Force the current block to terminate.
+ *
+ * Data may be present before codeEnd, so we need to parse it to know
+ * whether it is code or data.
+ */
+ if (codePtr < codeEnd) {
+ /* Create a fallthrough block for real instructions (incl. OP_NOP) */
+ if (contentIsInsn(codePtr)) {
+ BasicBlock *fallthroughBlock = findBlock(cUnit,
+ curOffset + width,
+ /* split */
+ false,
+ /* create */
+ true);
+ /*
+ * OP_THROW and OP_THROW_VERIFICATION_ERROR are unconditional
+ * branches.
+ */
+ if (insn->dalvikInsn.opcode != OP_THROW_VERIFICATION_ERROR &&
+ insn->dalvikInsn.opcode != OP_THROW) {
+ curBlock->fallThrough = fallthroughBlock;
+ dvmCompilerSetBit(fallthroughBlock->predecessors, curBlock->id);
+ }
+ }
+ }
+}
+
+/*
+ * Similar to dvmCompileTrace, but the entity processed here is the whole
+ * method.
+ *
+ * TODO: implementation will be revisited when the trace builder can provide
+ * whole-method traces.
+ */
+bool dvmCompileMethod(const Method *method, JitTranslationInfo *info)
+{
+ CompilationUnit cUnit;
+ const DexCode *dexCode = dvmGetMethodCode(method);
+ const u2 *codePtr = dexCode->insns;
+ const u2 *codeEnd = dexCode->insns + dexCode->insnsSize;
+ int numBlocks = 0;
+ unsigned int curOffset = 0;
+
+ /* Method already compiled */
+ if (dvmJitGetMethodAddr(codePtr)) {
+ info->codeAddress = NULL;
+ return false;
+ }
+
+ memset(&cUnit, 0, sizeof(cUnit));
+ cUnit.method = method;
+
+ cUnit.jitMode = kJitMethod;
+
+ /* Initialize the block list */
+ dvmInitGrowableList(&cUnit.blockList, 4);
+
+ /*
+ * FIXME - PC reconstruction list won't be needed after the codegen routines
+ * are enhanced to true method mode.
+ */
+ /* Initialize the PC reconstruction list */
+ dvmInitGrowableList(&cUnit.pcReconstructionList, 8);
+
+ /* Allocate the bit-vector to track the beginning of basic blocks */
+ BitVector *tryBlockAddr = dvmCompilerAllocBitVector(dexCode->insnsSize,
+ true /* expandable */);
+ cUnit.tryBlockAddr = tryBlockAddr;
+
+ /* Create the default entry and exit blocks and enter them to the list */
+ BasicBlock *entryBlock = dvmCompilerNewBB(kMethodEntryBlock, numBlocks++);
+ BasicBlock *exitBlock = dvmCompilerNewBB(kMethodExitBlock, numBlocks++);
+
+ cUnit.entryBlock = entryBlock;
+ cUnit.exitBlock = exitBlock;
+
+ dvmInsertGrowableList(&cUnit.blockList, (intptr_t) entryBlock);
+ dvmInsertGrowableList(&cUnit.blockList, (intptr_t) exitBlock);
+
+ /* Current block to record parsed instructions */
+ BasicBlock *curBlock = dvmCompilerNewBB(kDalvikByteCode, numBlocks++);
+ curBlock->startOffset = 0;
+ dvmInsertGrowableList(&cUnit.blockList, (intptr_t) curBlock);
+ entryBlock->fallThrough = curBlock;
+ dvmCompilerSetBit(curBlock->predecessors, entryBlock->id);
+
+ /*
+ * Store back the number of blocks since new blocks may be created of
+ * accessing cUnit.
+ */
+ cUnit.numBlocks = numBlocks;
+
+ /* Identify code range in try blocks and set up the empty catch blocks */
+ processTryCatchBlocks(&cUnit);
+
+ /* Parse all instructions and put them into containing basic blocks */
+ while (codePtr < codeEnd) {
+ MIR *insn = (MIR *) dvmCompilerNew(sizeof(MIR), true);
+ insn->offset = curOffset;
+ int width = parseInsn(codePtr, &insn->dalvikInsn, false);
+ insn->width = width;
+
+ /* Terminate when the data section is seen */
+ if (width == 0)
+ break;
+
+ dvmCompilerAppendMIR(curBlock, insn);
+
+ codePtr += width;
+ int flags = dexGetFlagsFromOpcode(insn->dalvikInsn.opcode);
+
+ if (flags & kInstrCanBranch) {
+ processCanBranch(&cUnit, curBlock, insn, curOffset, width, flags,
+ codePtr, codeEnd);
+ } else if (flags & kInstrCanReturn) {
+ curBlock->fallThrough = exitBlock;
+ dvmCompilerSetBit(exitBlock->predecessors, curBlock->id);
+ /*
+ * Terminate the current block if there are instructions
+ * afterwards.
+ */
+ if (codePtr < codeEnd) {
+ /*
+ * Create a fallthrough block for real instructions
+ * (incl. OP_NOP).
+ */
+ if (contentIsInsn(codePtr)) {
+ findBlock(&cUnit, curOffset + width,
+ /* split */
+ false,
+ /* create */
+ true);
+ }
+ }
+ } else if (flags & kInstrCanThrow) {
+ processCanThrow(&cUnit, curBlock, insn, curOffset, width, flags,
+ tryBlockAddr, codePtr, codeEnd);
+ } else if (flags & kInstrCanSwitch) {
+ processCanSwitch(&cUnit, curBlock, insn, curOffset, width, flags);
+ }
+ curOffset += width;
+ BasicBlock *nextBlock = findBlock(&cUnit, curOffset,
+ /* split */
+ false,
+ /* create */
+ false);
+ if (nextBlock) {
+ /*
+ * The next instruction could be the target of a previously parsed
+ * forward branch so a block is already created. If the current
+ * instruction is not an unconditional branch, connect them through
+ * the fall-through link.
+ */
+ assert(curBlock->fallThrough == NULL ||
+ curBlock->fallThrough == nextBlock ||
+ curBlock->fallThrough == exitBlock);
+
+ if ((curBlock->fallThrough == NULL) &&
+ (flags & kInstrCanContinue)) {
+ curBlock->fallThrough = nextBlock;
+ dvmCompilerSetBit(nextBlock->predecessors, curBlock->id);
+ }
+ curBlock = nextBlock;
+ }
+ }
+
+ if (cUnit.printMe) {
+ dvmCompilerDumpCompilationUnit(&cUnit);
+ }
+
+ /* Adjust this value accordingly once inlining is performed */
+ cUnit.numDalvikRegisters = cUnit.method->registersSize;
+
+ /* Verify if all blocks are connected as claimed */
+ /* FIXME - to be disabled in the future */
+ dvmCompilerDataFlowAnalysisDispatcher(&cUnit, verifyPredInfo,
+ kAllNodes,
+ false /* isIterative */);
+
+
+ /* Perform SSA transformation for the whole method */
+ dvmCompilerMethodSSATransformation(&cUnit);
+
+ dvmCompilerInitializeRegAlloc(&cUnit); // Needs to happen after SSA naming
+
+ /* Allocate Registers using simple local allocation scheme */
+ dvmCompilerLocalRegAlloc(&cUnit);
+
+ /* Convert MIR to LIR, etc. */
+ dvmCompilerMethodMIR2LIR(&cUnit);
+
+ // Debugging only
+ //dumpCFG(&cUnit, "/sdcard/cfg/");
+
+ /* Method is not empty */
+ if (cUnit.firstLIRInsn) {
+ /* Convert LIR into machine code. Loop for recoverable retries */
+ do {
+ dvmCompilerAssembleLIR(&cUnit, info);
+ cUnit.assemblerRetries++;
+ if (cUnit.printMe && cUnit.assemblerStatus != kSuccess)
+ LOGD("Assembler abort #%d on %d",cUnit.assemblerRetries,
+ cUnit.assemblerStatus);
+ } while (cUnit.assemblerStatus == kRetryAll);
+
+ if (cUnit.printMe) {
+ dvmCompilerCodegenDump(&cUnit);
+ }
+
+ if (info->codeAddress) {
+ dvmJitSetCodeAddr(dexCode->insns, info->codeAddress,
+ info->instructionSet, true, 0);
+ /*
+ * Clear the codeAddress for the enclosing trace to reuse the info
+ */
+ info->codeAddress = NULL;
+ }
+ }
+
+ return false;
+}
+
+/* Extending the trace by crawling the code from curBlock */
+static bool exhaustTrace(CompilationUnit *cUnit, BasicBlock *curBlock)
+{
+ unsigned int curOffset = curBlock->startOffset;
+ const u2 *codePtr = cUnit->method->insns + curOffset;
+
+ if (curBlock->visited == true) return false;
+
+ curBlock->visited = true;
+
+ if (curBlock->blockType == kMethodEntryBlock ||
+ curBlock->blockType == kMethodExitBlock) {
+ return false;
+ }
+
+ /*
+ * Block has been parsed - check the taken/fallThrough in case it is a split
+ * block.
+ */
+ if (curBlock->firstMIRInsn != NULL) {
+ bool changed = false;
+ if (curBlock->taken)
+ changed |= exhaustTrace(cUnit, curBlock->taken);
+ if (curBlock->fallThrough)
+ changed |= exhaustTrace(cUnit, curBlock->fallThrough);
+ return changed;
+ }
+ while (true) {
+ MIR *insn = (MIR *) dvmCompilerNew(sizeof(MIR), true);
+ insn->offset = curOffset;
+ int width = parseInsn(codePtr, &insn->dalvikInsn, false);
+ insn->width = width;
+
+ /* Terminate when the data section is seen */
+ if (width == 0)
+ break;
+
+ dvmCompilerAppendMIR(curBlock, insn);
+
+ codePtr += width;
+ int flags = dexGetFlagsFromOpcode(insn->dalvikInsn.opcode);
+
+ /* Stop extending the trace after seeing these instructions */
+ if (flags & (kInstrCanReturn | kInstrCanSwitch | kInstrInvoke)) {
+ curBlock->fallThrough = cUnit->exitBlock;
+ dvmCompilerSetBit(cUnit->exitBlock->predecessors, curBlock->id);
+ break;
+ } else if (flags & kInstrCanBranch) {
+ processCanBranch(cUnit, curBlock, insn, curOffset, width, flags,
+ codePtr, NULL);
+ if (curBlock->taken) {
+ exhaustTrace(cUnit, curBlock->taken);
+ }
+ if (curBlock->fallThrough) {
+ exhaustTrace(cUnit, curBlock->fallThrough);
+ }
+ break;
+ }
+ curOffset += width;
+ }
+ return true;
+}
+
+/* Compile a loop */
+static bool compileLoop(CompilationUnit *cUnit, unsigned int startOffset,
+ JitTraceDescription *desc, int numMaxInsts,
+ JitTranslationInfo *info, jmp_buf *bailPtr,
+ int optHints)
+{
+ int numBlocks = 0;
+ unsigned int curOffset = startOffset;
+ bool changed;
+
+ cUnit->jitMode = kJitLoop;
+
+ /* Initialize the block list */
+ dvmInitGrowableList(&cUnit->blockList, 4);
+
+ /* Initialize the PC reconstruction list */
+ dvmInitGrowableList(&cUnit->pcReconstructionList, 8);
+
+ /* Create the default entry and exit blocks and enter them to the list */
+ BasicBlock *entryBlock = dvmCompilerNewBB(kMethodEntryBlock, numBlocks++);
+ entryBlock->startOffset = curOffset;
+ BasicBlock *exitBlock = dvmCompilerNewBB(kMethodExitBlock, numBlocks++);
+
+ cUnit->entryBlock = entryBlock;
+ cUnit->exitBlock = exitBlock;
+
+ dvmInsertGrowableList(&cUnit->blockList, (intptr_t) entryBlock);
+ dvmInsertGrowableList(&cUnit->blockList, (intptr_t) exitBlock);
+
+ /* Current block to record parsed instructions */
+ BasicBlock *curBlock = dvmCompilerNewBB(kDalvikByteCode, numBlocks++);
+ curBlock->startOffset = curOffset;
+
+ dvmInsertGrowableList(&cUnit->blockList, (intptr_t) curBlock);
+ entryBlock->fallThrough = curBlock;
+ dvmCompilerSetBit(curBlock->predecessors, entryBlock->id);
+
+ /*
+ * Store back the number of blocks since new blocks may be created of
+ * accessing cUnit.
+ */
+ cUnit->numBlocks = numBlocks;
+
+ do {
+ dvmCompilerDataFlowAnalysisDispatcher(cUnit,
+ dvmCompilerClearVisitedFlag,
+ kAllNodes,
+ false /* isIterative */);
+ changed = exhaustTrace(cUnit, curBlock);
+ } while (changed);
+
+ cUnit->numDalvikRegisters = cUnit->method->registersSize;
+
+ /* Verify if all blocks are connected as claimed */
+ /* FIXME - to be disabled in the future */
+ dvmCompilerDataFlowAnalysisDispatcher(cUnit, verifyPredInfo,
+ kAllNodes,
+ false /* isIterative */);
+
+
+ /* Try to identify a loop */
+ if (!dvmCompilerBuildLoop(cUnit))
+ goto bail;
+
+ dvmCompilerInitializeRegAlloc(cUnit);
+
+ /* Allocate Registers using simple local allocation scheme */
+ dvmCompilerLocalRegAlloc(cUnit);
+
+ if (gDvmJit.receivedSIGUSR2) {
+ dumpCFG(cUnit, "/sdcard/cfg/");
+ }
+
+bail:
+ /* Retry the original trace with JIT_OPT_NO_LOOP disabled */
+ dvmCompilerArenaReset();
+ return dvmCompileTrace(desc, numMaxInsts, info, bailPtr,
+ optHints | JIT_OPT_NO_LOOP);
+}
+
+/*
* Main entry point to start trace compilation. Basic blocks are constructed
* first and they will be passed to the codegen routines to convert Dalvik
* bytecode into machine code.
@@ -427,6 +1493,7 @@
const DexCode *dexCode = dvmGetMethodCode(desc->method);
const JitTraceRun* currRun = &desc->trace[0];
unsigned int curOffset = currRun->info.frag.startOffset;
+ unsigned int startOffset = curOffset;
unsigned int numInsts = currRun->info.frag.numInsts;
const u2 *codePtr = dexCode->insns + curOffset;
int traceSize = 0; // # of half-words
@@ -670,6 +1737,17 @@
cUnit.hasInvoke = true;
}
+ /* Backward branch seen */
+ if (isInvoke == false &&
+ (flags & kInstrCanBranch) != 0 &&
+ targetOffset < curOffset &&
+ (optHints & JIT_OPT_NO_LOOP) == 0) {
+ dvmCompilerArenaReset();
+ /* TODO - constructed loop is abandoned for now */
+ return compileLoop(&cUnit, startOffset, desc, numMaxInsts,
+ info, bailPtr, optHints);
+ }
+
/* No backward branch in the trace - start searching the next BB */
size_t searchBlockId;
for (searchBlockId = blockId+1; searchBlockId < blockList->numUsed;
@@ -974,910 +2052,3 @@
return info->codeAddress != NULL;
}
-
-/*
- * Since we are including instructions from possibly a cold method into the
- * current trace, we need to make sure that all the associated information
- * with the callee is properly initialized. If not, we punt on this inline
- * target.
- *
- * TODO: volatile instructions will be handled later.
- */
-bool dvmCompilerCanIncludeThisInstruction(const Method *method,
- const DecodedInstruction *insn)
-{
- switch (insn->opcode) {
- case OP_NEW_INSTANCE:
- case OP_NEW_INSTANCE_JUMBO:
- case OP_CHECK_CAST:
- case OP_CHECK_CAST_JUMBO: {
- ClassObject *classPtr = (ClassObject *)(void*)
- (method->clazz->pDvmDex->pResClasses[insn->vB]);
-
- /* Class hasn't been initialized yet */
- if (classPtr == NULL) {
- return false;
- }
- return true;
- }
- case OP_SGET:
- case OP_SGET_JUMBO:
- case OP_SGET_WIDE:
- case OP_SGET_WIDE_JUMBO:
- case OP_SGET_OBJECT:
- case OP_SGET_OBJECT_JUMBO:
- case OP_SGET_BOOLEAN:
- case OP_SGET_BOOLEAN_JUMBO:
- case OP_SGET_BYTE:
- case OP_SGET_BYTE_JUMBO:
- case OP_SGET_CHAR:
- case OP_SGET_CHAR_JUMBO:
- case OP_SGET_SHORT:
- case OP_SGET_SHORT_JUMBO:
- case OP_SPUT:
- case OP_SPUT_JUMBO:
- case OP_SPUT_WIDE:
- case OP_SPUT_WIDE_JUMBO:
- case OP_SPUT_OBJECT:
- case OP_SPUT_OBJECT_JUMBO:
- case OP_SPUT_BOOLEAN:
- case OP_SPUT_BOOLEAN_JUMBO:
- case OP_SPUT_BYTE:
- case OP_SPUT_BYTE_JUMBO:
- case OP_SPUT_CHAR:
- case OP_SPUT_CHAR_JUMBO:
- case OP_SPUT_SHORT:
- case OP_SPUT_SHORT_JUMBO: {
- void *fieldPtr = (void*)
- (method->clazz->pDvmDex->pResFields[insn->vB]);
-
- if (fieldPtr == NULL) {
- return false;
- }
- return true;
- }
- case OP_INVOKE_SUPER:
- case OP_INVOKE_SUPER_RANGE:
- case OP_INVOKE_SUPER_JUMBO: {
- int mIndex = method->clazz->pDvmDex->
- pResMethods[insn->vB]->methodIndex;
- const Method *calleeMethod = method->clazz->super->vtable[mIndex];
- if (calleeMethod == NULL) {
- return false;
- }
- return true;
- }
- case OP_INVOKE_SUPER_QUICK:
- case OP_INVOKE_SUPER_QUICK_RANGE: {
- const Method *calleeMethod = method->clazz->super->vtable[insn->vB];
- if (calleeMethod == NULL) {
- return false;
- }
- return true;
- }
- case OP_INVOKE_STATIC:
- case OP_INVOKE_STATIC_RANGE:
- case OP_INVOKE_STATIC_JUMBO:
- case OP_INVOKE_DIRECT:
- case OP_INVOKE_DIRECT_RANGE:
- case OP_INVOKE_DIRECT_JUMBO: {
- const Method *calleeMethod =
- method->clazz->pDvmDex->pResMethods[insn->vB];
- if (calleeMethod == NULL) {
- return false;
- }
- return true;
- }
- case OP_CONST_CLASS:
- case OP_CONST_CLASS_JUMBO: {
- void *classPtr = (void*)
- (method->clazz->pDvmDex->pResClasses[insn->vB]);
-
- if (classPtr == NULL) {
- return false;
- }
- return true;
- }
- case OP_CONST_STRING_JUMBO:
- case OP_CONST_STRING: {
- void *strPtr = (void*)
- (method->clazz->pDvmDex->pResStrings[insn->vB]);
-
- if (strPtr == NULL) {
- return false;
- }
- return true;
- }
- default:
- return true;
- }
-}
-
-/* Split an existing block from the specified code offset into two */
-static BasicBlock *splitBlock(CompilationUnit *cUnit,
- unsigned int codeOffset,
- BasicBlock *origBlock)
-{
- MIR *insn = origBlock->firstMIRInsn;
- while (insn) {
- if (insn->offset == codeOffset) break;
- insn = insn->next;
- }
- if (insn == NULL) {
- LOGE("Break split failed");
- dvmAbort();
- }
- BasicBlock *bottomBlock = dvmCompilerNewBB(kDalvikByteCode,
- cUnit->numBlocks++);
- dvmInsertGrowableList(&cUnit->blockList, (intptr_t) bottomBlock);
-
- bottomBlock->startOffset = codeOffset;
- bottomBlock->firstMIRInsn = insn;
- bottomBlock->lastMIRInsn = origBlock->lastMIRInsn;
-
- /* Handle the taken path */
- bottomBlock->taken = origBlock->taken;
- if (bottomBlock->taken) {
- origBlock->taken = NULL;
- dvmCompilerClearBit(bottomBlock->taken->predecessors, origBlock->id);
- dvmCompilerSetBit(bottomBlock->taken->predecessors, bottomBlock->id);
- }
-
- /* Handle the fallthrough path */
- bottomBlock->fallThrough = origBlock->fallThrough;
- origBlock->fallThrough = bottomBlock;
- dvmCompilerSetBit(bottomBlock->predecessors, origBlock->id);
- if (bottomBlock->fallThrough) {
- dvmCompilerClearBit(bottomBlock->fallThrough->predecessors,
- origBlock->id);
- dvmCompilerSetBit(bottomBlock->fallThrough->predecessors,
- bottomBlock->id);
- }
-
- /* Handle the successor list */
- if (origBlock->successorBlockList.blockListType != kNotUsed) {
- bottomBlock->successorBlockList = origBlock->successorBlockList;
- origBlock->successorBlockList.blockListType = kNotUsed;
- GrowableListIterator iterator;
-
- dvmGrowableListIteratorInit(&bottomBlock->successorBlockList.blocks,
- &iterator);
- while (true) {
- SuccessorBlockInfo *successorBlockInfo =
- (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator);
- if (successorBlockInfo == NULL) break;
- BasicBlock *bb = successorBlockInfo->block;
- dvmCompilerClearBit(bb->predecessors, origBlock->id);
- dvmCompilerSetBit(bb->predecessors, bottomBlock->id);
- }
- }
-
- origBlock->lastMIRInsn = insn->prev;
-
- insn->prev->next = NULL;
- insn->prev = NULL;
- return bottomBlock;
-}
-
-/*
- * Given a code offset, find out the block that starts with it. If the offset
- * is in the middle of an existing block, split it into two.
- */
-static BasicBlock *findBlock(CompilationUnit *cUnit,
- unsigned int codeOffset,
- bool split, bool create)
-{
- GrowableList *blockList = &cUnit->blockList;
- BasicBlock *bb;
- unsigned int i;
-
- for (i = 0; i < blockList->numUsed; i++) {
- bb = (BasicBlock *) blockList->elemList[i];
- if (bb->blockType != kDalvikByteCode) continue;
- if (bb->startOffset == codeOffset) return bb;
- /* Check if a branch jumps into the middle of an existing block */
- if ((split == true) && (codeOffset > bb->startOffset) &&
- (bb->lastMIRInsn != NULL) &&
- (codeOffset <= bb->lastMIRInsn->offset)) {
- BasicBlock *newBB = splitBlock(cUnit, codeOffset, bb);
- return newBB;
- }
- }
- if (create) {
- bb = dvmCompilerNewBB(kDalvikByteCode, cUnit->numBlocks++);
- dvmInsertGrowableList(&cUnit->blockList, (intptr_t) bb);
- bb->startOffset = codeOffset;
- return bb;
- }
- return NULL;
-}
-
-/* Dump the CFG into a DOT graph */
-void dumpCFG(CompilationUnit *cUnit, const char *dirPrefix)
-{
- const Method *method = cUnit->method;
- FILE *file;
- char* signature = dexProtoCopyMethodDescriptor(&method->prototype);
- char *fileName = (char *) dvmCompilerNew(
- strlen(dirPrefix) +
- strlen(method->clazz->descriptor) +
- strlen(method->name) +
- strlen(signature) +
- strlen(".dot") + 1, true);
- sprintf(fileName, "%s%s%s%s.dot", dirPrefix,
- method->clazz->descriptor, method->name, signature);
- free(signature);
-
- /*
- * Convert the special characters into a filesystem- and shell-friendly
- * format.
- */
- int i;
- for (i = strlen(dirPrefix); fileName[i]; i++) {
- if (fileName[i] == '/') {
- fileName[i] = '_';
- } else if (fileName[i] == ';') {
- fileName[i] = '#';
- } else if (fileName[i] == '$') {
- fileName[i] = '+';
- } else if (fileName[i] == '(' || fileName[i] == ')') {
- fileName[i] = '@';
- } else if (fileName[i] == '<' || fileName[i] == '>') {
- fileName[i] = '=';
- }
- }
- file = fopen(fileName, "w");
- if (file == NULL) {
- return;
- }
- fprintf(file, "digraph G {\n");
-
- fprintf(file, " rankdir=TB\n");
-
- int numReachableBlocks = cUnit->numReachableBlocks;
- int idx;
- const GrowableList *blockList = &cUnit->blockList;
-
- for (idx = 0; idx < numReachableBlocks; idx++) {
- int blockIdx = cUnit->dfsOrder.elemList[idx];
- BasicBlock *bb = (BasicBlock *) dvmGrowableListGetElement(blockList,
- blockIdx);
- if (bb == NULL) break;
- if (bb->blockType == kMethodEntryBlock) {
- fprintf(file, " entry [shape=Mdiamond];\n");
- } else if (bb->blockType == kMethodExitBlock) {
- fprintf(file, " exit [shape=Mdiamond];\n");
- } else if (bb->blockType == kDalvikByteCode) {
- fprintf(file, " block%04x [shape=record,label = \"{ \\\n",
- bb->startOffset);
- const MIR *mir;
- for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
- fprintf(file, " {%04x %s\\l}%s\\\n", mir->offset,
- dvmCompilerFullDisassembler(cUnit, mir),
- mir->next ? " | " : " ");
- }
- fprintf(file, " }\"];\n\n");
- } else if (bb->blockType == kExceptionHandling) {
- char blockName[BLOCK_NAME_LEN];
-
- dvmGetBlockName(bb, blockName);
- fprintf(file, " %s [shape=invhouse];\n", blockName);
- }
-
- char blockName1[BLOCK_NAME_LEN], blockName2[BLOCK_NAME_LEN];
-
- if (bb->taken) {
- dvmGetBlockName(bb, blockName1);
- dvmGetBlockName(bb->taken, blockName2);
- fprintf(file, " %s:s -> %s:n [style=dotted]\n",
- blockName1, blockName2);
- }
- if (bb->fallThrough) {
- dvmGetBlockName(bb, blockName1);
- dvmGetBlockName(bb->fallThrough, blockName2);
- fprintf(file, " %s:s -> %s:n\n", blockName1, blockName2);
- }
-
- if (bb->successorBlockList.blockListType != kNotUsed) {
- fprintf(file, " succ%04x [shape=%s,label = \"{ \\\n",
- bb->startOffset,
- (bb->successorBlockList.blockListType == kCatch) ?
- "Mrecord" : "record");
- GrowableListIterator iterator;
- dvmGrowableListIteratorInit(&bb->successorBlockList.blocks,
- &iterator);
- SuccessorBlockInfo *successorBlockInfo =
- (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator);
-
- int succId = 0;
- while (true) {
- if (successorBlockInfo == NULL) break;
-
- BasicBlock *destBlock = successorBlockInfo->block;
- SuccessorBlockInfo *nextSuccessorBlockInfo =
- (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator);
-
- fprintf(file, " {<f%d> %04x: %04x\\l}%s\\\n",
- succId++,
- successorBlockInfo->key,
- destBlock->startOffset,
- (nextSuccessorBlockInfo != NULL) ? " | " : " ");
-
- successorBlockInfo = nextSuccessorBlockInfo;
- }
- fprintf(file, " }\"];\n\n");
-
- dvmGetBlockName(bb, blockName1);
- fprintf(file, " %s:s -> succ%04x:n [style=dashed]\n",
- blockName1, bb->startOffset);
-
- if (bb->successorBlockList.blockListType == kPackedSwitch ||
- bb->successorBlockList.blockListType == kSparseSwitch) {
-
- dvmGrowableListIteratorInit(&bb->successorBlockList.blocks,
- &iterator);
-
- succId = 0;
- while (true) {
- SuccessorBlockInfo *successorBlockInfo =
- (SuccessorBlockInfo *)
- dvmGrowableListIteratorNext(&iterator);
- if (successorBlockInfo == NULL) break;
-
- BasicBlock *destBlock = successorBlockInfo->block;
-
- dvmGetBlockName(destBlock, blockName2);
- fprintf(file, " succ%04x:f%d:e -> %s:n\n",
- bb->startOffset, succId++,
- blockName2);
- }
- }
- }
- fprintf(file, "\n");
-
- /*
- * If we need to debug the dominator tree, uncomment the following code
- */
-#if 0
- dvmGetBlockName(bb, blockName1);
- fprintf(file, " cfg%s [label=\"%s\", shape=none];\n",
- blockName1, blockName1);
- if (bb->iDom) {
- dvmGetBlockName(bb->iDom, blockName2);
- fprintf(file, " cfg%s:s -> cfg%s:n\n\n",
- blockName2, blockName1);
- }
-#endif
- }
- fprintf(file, "}\n");
- fclose(file);
-}
-
-/* Verify if all the successor is connected with all the claimed predecessors */
-static bool verifyPredInfo(CompilationUnit *cUnit, BasicBlock *bb)
-{
- BitVectorIterator bvIterator;
-
- dvmBitVectorIteratorInit(bb->predecessors, &bvIterator);
- while (true) {
- int blockIdx = dvmBitVectorIteratorNext(&bvIterator);
- if (blockIdx == -1) break;
- BasicBlock *predBB = (BasicBlock *)
- dvmGrowableListGetElement(&cUnit->blockList, blockIdx);
- bool found = false;
- if (predBB->taken == bb) {
- found = true;
- } else if (predBB->fallThrough == bb) {
- found = true;
- } else if (predBB->successorBlockList.blockListType != kNotUsed) {
- GrowableListIterator iterator;
- dvmGrowableListIteratorInit(&predBB->successorBlockList.blocks,
- &iterator);
- while (true) {
- SuccessorBlockInfo *successorBlockInfo =
- (SuccessorBlockInfo *)
- dvmGrowableListIteratorNext(&iterator);
- if (successorBlockInfo == NULL) break;
- BasicBlock *succBB = successorBlockInfo->block;
- if (succBB == bb) {
- found = true;
- break;
- }
- }
- }
- if (found == false) {
- char blockName1[BLOCK_NAME_LEN], blockName2[BLOCK_NAME_LEN];
- dvmGetBlockName(bb, blockName1);
- dvmGetBlockName(predBB, blockName2);
- dumpCFG(cUnit, "/data/tombstones/");
- LOGE("Successor %s not found from %s",
- blockName1, blockName2);
- dvmAbort();
- }
- }
- return true;
-}
-
-/* Identify code range in try blocks and set up the empty catch blocks */
-static void processTryCatchBlocks(CompilationUnit *cUnit)
-{
- const Method *meth = cUnit->method;
- const DexCode *pCode = dvmGetMethodCode(meth);
- int triesSize = pCode->triesSize;
- int i;
- int offset;
-
- if (triesSize == 0) {
- return;
- }
-
- const DexTry *pTries = dexGetTries(pCode);
- BitVector *tryBlockAddr = cUnit->tryBlockAddr;
-
- /* Mark all the insn offsets in Try blocks */
- for (i = 0; i < triesSize; i++) {
- const DexTry* pTry = &pTries[i];
- /* all in 16-bit units */
- int startOffset = pTry->startAddr;
- int endOffset = startOffset + pTry->insnCount;
-
- for (offset = startOffset; offset < endOffset; offset++) {
- dvmCompilerSetBit(tryBlockAddr, offset);
- }
- }
-
- /* Iterate over each of the handlers to enqueue the empty Catch blocks */
- offset = dexGetFirstHandlerOffset(pCode);
- int handlersSize = dexGetHandlersSize(pCode);
-
- for (i = 0; i < handlersSize; i++) {
- DexCatchIterator iterator;
- dexCatchIteratorInit(&iterator, pCode, offset);
-
- for (;;) {
- DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
-
- if (handler == NULL) {
- break;
- }
-
- /*
- * Create dummy catch blocks first. Since these are created before
- * other blocks are processed, "split" is specified as false.
- */
- findBlock(cUnit, handler->address,
- /* split */
- false,
- /* create */
- true);
- }
-
- offset = dexCatchIteratorGetEndOffset(&iterator, pCode);
- }
-}
-
-/* Process instructions with the kInstrCanBranch flag */
-static void processCanBranch(CompilationUnit *cUnit, BasicBlock *curBlock,
- MIR *insn, int curOffset, int width, int flags,
- const u2* codePtr, const u2* codeEnd)
-{
- int target = curOffset;
- switch (insn->dalvikInsn.opcode) {
- case OP_GOTO:
- case OP_GOTO_16:
- case OP_GOTO_32:
- target += (int) insn->dalvikInsn.vA;
- break;
- case OP_IF_EQ:
- case OP_IF_NE:
- case OP_IF_LT:
- case OP_IF_GE:
- case OP_IF_GT:
- case OP_IF_LE:
- target += (int) insn->dalvikInsn.vC;
- break;
- case OP_IF_EQZ:
- case OP_IF_NEZ:
- case OP_IF_LTZ:
- case OP_IF_GEZ:
- case OP_IF_GTZ:
- case OP_IF_LEZ:
- target += (int) insn->dalvikInsn.vB;
- break;
- default:
- LOGE("Unexpected opcode(%d) with kInstrCanBranch set",
- insn->dalvikInsn.opcode);
- dvmAbort();
- }
- BasicBlock *takenBlock = findBlock(cUnit, target,
- /* split */
- true,
- /* create */
- true);
- curBlock->taken = takenBlock;
- dvmCompilerSetBit(takenBlock->predecessors, curBlock->id);
-
- /* Always terminate the current block for conditional branches */
- if (flags & kInstrCanContinue) {
- BasicBlock *fallthroughBlock = findBlock(cUnit,
- curOffset + width,
- /* split */
- false,
- /* create */
- true);
- curBlock->fallThrough = fallthroughBlock;
- dvmCompilerSetBit(fallthroughBlock->predecessors, curBlock->id);
- } else if (codePtr < codeEnd) {
- /* Create a fallthrough block for real instructions (incl. OP_NOP) */
- if (contentIsInsn(codePtr)) {
- findBlock(cUnit, curOffset + width,
- /* split */
- false,
- /* create */
- true);
- }
- }
-}
-
-/* Process instructions with the kInstrCanSwitch flag */
-static void processCanSwitch(CompilationUnit *cUnit, BasicBlock *curBlock,
- MIR *insn, int curOffset, int width, int flags)
-{
- u2 *switchData= (u2 *) (cUnit->method->insns + curOffset +
- insn->dalvikInsn.vB);
- int size;
- int *keyTable;
- int *targetTable;
- int i;
- int firstKey;
-
- /*
- * Packed switch data format:
- * ushort ident = 0x0100 magic value
- * ushort size number of entries in the table
- * int first_key first (and lowest) switch case value
- * int targets[size] branch targets, relative to switch opcode
- *
- * Total size is (4+size*2) 16-bit code units.
- */
- if (insn->dalvikInsn.opcode == OP_PACKED_SWITCH) {
- assert(switchData[0] == kPackedSwitchSignature);
- size = switchData[1];
- firstKey = switchData[2] | (switchData[3] << 16);
- targetTable = (int *) &switchData[4];
- keyTable = NULL; // Make the compiler happy
- /*
- * Sparse switch data format:
- * ushort ident = 0x0200 magic value
- * ushort size number of entries in the table; > 0
- * int keys[size] keys, sorted low-to-high; 32-bit aligned
- * int targets[size] branch targets, relative to switch opcode
- *
- * Total size is (2+size*4) 16-bit code units.
- */
- } else {
- assert(switchData[0] == kSparseSwitchSignature);
- size = switchData[1];
- keyTable = (int *) &switchData[2];
- targetTable = (int *) &switchData[2 + size*2];
- firstKey = 0; // To make the compiler happy
- }
-
- if (curBlock->successorBlockList.blockListType != kNotUsed) {
- LOGE("Successor block list already in use: %d",
- curBlock->successorBlockList.blockListType);
- dvmAbort();
- }
- curBlock->successorBlockList.blockListType =
- (insn->dalvikInsn.opcode == OP_PACKED_SWITCH) ?
- kPackedSwitch : kSparseSwitch;
- dvmInitGrowableList(&curBlock->successorBlockList.blocks, size);
-
- for (i = 0; i < size; i++) {
- BasicBlock *caseBlock = findBlock(cUnit, curOffset + targetTable[i],
- /* split */
- true,
- /* create */
- true);
- SuccessorBlockInfo *successorBlockInfo =
- (SuccessorBlockInfo *) dvmCompilerNew(sizeof(SuccessorBlockInfo),
- false);
- successorBlockInfo->block = caseBlock;
- successorBlockInfo->key = (insn->dalvikInsn.opcode == OP_PACKED_SWITCH)?
- firstKey + i : keyTable[i];
- dvmInsertGrowableList(&curBlock->successorBlockList.blocks,
- (intptr_t) successorBlockInfo);
- dvmCompilerSetBit(caseBlock->predecessors, curBlock->id);
- }
-
- /* Fall-through case */
- BasicBlock *fallthroughBlock = findBlock(cUnit,
- curOffset + width,
- /* split */
- false,
- /* create */
- true);
- curBlock->fallThrough = fallthroughBlock;
- dvmCompilerSetBit(fallthroughBlock->predecessors, curBlock->id);
-}
-
-/* Process instructions with the kInstrCanThrow flag */
-static void processCanThrow(CompilationUnit *cUnit, BasicBlock *curBlock,
- MIR *insn, int curOffset, int width, int flags,
- BitVector *tryBlockAddr, const u2 *codePtr,
- const u2* codeEnd)
-{
- const Method *method = cUnit->method;
- const DexCode *dexCode = dvmGetMethodCode(method);
-
- /* In try block */
- if (dvmIsBitSet(tryBlockAddr, curOffset)) {
- DexCatchIterator iterator;
-
- if (!dexFindCatchHandler(&iterator, dexCode, curOffset)) {
- LOGE("Catch block not found in dexfile for insn %x in %s",
- curOffset, method->name);
- dvmAbort();
-
- }
- if (curBlock->successorBlockList.blockListType != kNotUsed) {
- LOGE("Successor block list already in use: %d",
- curBlock->successorBlockList.blockListType);
- dvmAbort();
- }
- curBlock->successorBlockList.blockListType = kCatch;
- dvmInitGrowableList(&curBlock->successorBlockList.blocks, 2);
-
- for (;;) {
- DexCatchHandler* handler = dexCatchIteratorNext(&iterator);
-
- if (handler == NULL) {
- break;
- }
-
- BasicBlock *catchBlock = findBlock(cUnit, handler->address,
- /* split */
- false,
- /* create */
- false);
-
- SuccessorBlockInfo *successorBlockInfo =
- (SuccessorBlockInfo *) dvmCompilerNew(sizeof(SuccessorBlockInfo),
- false);
- successorBlockInfo->block = catchBlock;
- successorBlockInfo->key = handler->typeIdx;
- dvmInsertGrowableList(&curBlock->successorBlockList.blocks,
- (intptr_t) successorBlockInfo);
- dvmCompilerSetBit(catchBlock->predecessors, curBlock->id);
- }
- } else {
- BasicBlock *ehBlock = dvmCompilerNewBB(kExceptionHandling,
- cUnit->numBlocks++);
- curBlock->taken = ehBlock;
- dvmInsertGrowableList(&cUnit->blockList, (intptr_t) ehBlock);
- ehBlock->startOffset = curOffset;
- dvmCompilerSetBit(ehBlock->predecessors, curBlock->id);
- }
-
- /*
- * Force the current block to terminate.
- *
- * Data may be present before codeEnd, so we need to parse it to know
- * whether it is code or data.
- */
- if (codePtr < codeEnd) {
- /* Create a fallthrough block for real instructions (incl. OP_NOP) */
- if (contentIsInsn(codePtr)) {
- BasicBlock *fallthroughBlock = findBlock(cUnit,
- curOffset + width,
- /* split */
- false,
- /* create */
- true);
- /*
- * OP_THROW and OP_THROW_VERIFICATION_ERROR are unconditional
- * branches.
- */
- if (insn->dalvikInsn.opcode != OP_THROW_VERIFICATION_ERROR &&
- insn->dalvikInsn.opcode != OP_THROW) {
- curBlock->fallThrough = fallthroughBlock;
- dvmCompilerSetBit(fallthroughBlock->predecessors, curBlock->id);
- }
- }
- }
-}
-
-/*
- * Similar to dvmCompileTrace, but the entity processed here is the whole
- * method.
- *
- * TODO: implementation will be revisited when the trace builder can provide
- * whole-method traces.
- */
-bool dvmCompileMethod(const Method *method, JitTranslationInfo *info)
-{
- CompilationUnit cUnit;
- const DexCode *dexCode = dvmGetMethodCode(method);
- const u2 *codePtr = dexCode->insns;
- const u2 *codeEnd = dexCode->insns + dexCode->insnsSize;
- int numBlocks = 0;
- unsigned int curOffset = 0;
-
- /* Method already compiled */
- if (dvmJitGetMethodAddr(codePtr)) {
- info->codeAddress = NULL;
- return false;
- }
-
- memset(&cUnit, 0, sizeof(cUnit));
- cUnit.method = method;
-
- cUnit.methodJitMode = true;
-
- /* Initialize the block list */
- dvmInitGrowableList(&cUnit.blockList, 4);
-
- /*
- * FIXME - PC reconstruction list won't be needed after the codegen routines
- * are enhanced to true method mode.
- */
- /* Initialize the PC reconstruction list */
- dvmInitGrowableList(&cUnit.pcReconstructionList, 8);
-
- /* Allocate the bit-vector to track the beginning of basic blocks */
- BitVector *tryBlockAddr = dvmCompilerAllocBitVector(dexCode->insnsSize,
- true /* expandable */);
- cUnit.tryBlockAddr = tryBlockAddr;
-
- /* Create the default entry and exit blocks and enter them to the list */
- BasicBlock *entryBlock = dvmCompilerNewBB(kMethodEntryBlock, numBlocks++);
- BasicBlock *exitBlock = dvmCompilerNewBB(kMethodExitBlock, numBlocks++);
-
- cUnit.entryBlock = entryBlock;
- cUnit.exitBlock = exitBlock;
-
- dvmInsertGrowableList(&cUnit.blockList, (intptr_t) entryBlock);
- dvmInsertGrowableList(&cUnit.blockList, (intptr_t) exitBlock);
-
- /* Current block to record parsed instructions */
- BasicBlock *curBlock = dvmCompilerNewBB(kDalvikByteCode, numBlocks++);
- curBlock->startOffset = 0;
- dvmInsertGrowableList(&cUnit.blockList, (intptr_t) curBlock);
- entryBlock->fallThrough = curBlock;
- dvmCompilerSetBit(curBlock->predecessors, entryBlock->id);
-
- /*
- * Store back the number of blocks since new blocks may be created of
- * accessing cUnit.
- */
- cUnit.numBlocks = numBlocks;
-
- /* Identify code range in try blocks and set up the empty catch blocks */
- processTryCatchBlocks(&cUnit);
-
- /* Parse all instructions and put them into containing basic blocks */
- while (codePtr < codeEnd) {
- MIR *insn = (MIR *) dvmCompilerNew(sizeof(MIR), true);
- insn->offset = curOffset;
- int width = parseInsn(codePtr, &insn->dalvikInsn, false);
- insn->width = width;
-
- /* Terminate when the data section is seen */
- if (width == 0)
- break;
-
- dvmCompilerAppendMIR(curBlock, insn);
-
- codePtr += width;
- int flags = dexGetFlagsFromOpcode(insn->dalvikInsn.opcode);
-
- if (flags & kInstrCanBranch) {
- processCanBranch(&cUnit, curBlock, insn, curOffset, width, flags,
- codePtr, codeEnd);
- } else if (flags & kInstrCanReturn) {
- curBlock->fallThrough = exitBlock;
- dvmCompilerSetBit(exitBlock->predecessors, curBlock->id);
- /*
- * Terminate the current block if there are instructions
- * afterwards.
- */
- if (codePtr < codeEnd) {
- /*
- * Create a fallthrough block for real instructions
- * (incl. OP_NOP).
- */
- if (contentIsInsn(codePtr)) {
- findBlock(&cUnit, curOffset + width,
- /* split */
- false,
- /* create */
- true);
- }
- }
- } else if (flags & kInstrCanThrow) {
- processCanThrow(&cUnit, curBlock, insn, curOffset, width, flags,
- tryBlockAddr, codePtr, codeEnd);
- } else if (flags & kInstrCanSwitch) {
- processCanSwitch(&cUnit, curBlock, insn, curOffset, width, flags);
- }
- curOffset += width;
- BasicBlock *nextBlock = findBlock(&cUnit, curOffset,
- /* split */
- false,
- /* create */
- false);
- if (nextBlock) {
- /*
- * The next instruction could be the target of a previously parsed
- * forward branch so a block is already created. If the current
- * instruction is not an unconditional branch, connect them through
- * the fall-through link.
- */
- assert(curBlock->fallThrough == NULL ||
- curBlock->fallThrough == nextBlock ||
- curBlock->fallThrough == exitBlock);
-
- if ((curBlock->fallThrough == NULL) &&
- (flags & kInstrCanContinue)) {
- curBlock->fallThrough = nextBlock;
- dvmCompilerSetBit(nextBlock->predecessors, curBlock->id);
- }
- curBlock = nextBlock;
- }
- }
-
- if (cUnit.printMe) {
- dvmCompilerDumpCompilationUnit(&cUnit);
- }
-
- /* Adjust this value accordingly once inlining is performed */
- cUnit.numDalvikRegisters = cUnit.method->registersSize;
-
- /* Verify if all blocks are connected as claimed */
- /* FIXME - to be disabled in the future */
- dvmCompilerDataFlowAnalysisDispatcher(&cUnit, verifyPredInfo,
- kAllNodes,
- false /* isIterative */);
-
-
- /* Perform SSA transformation for the whole method */
- dvmCompilerMethodSSATransformation(&cUnit);
-
- dvmCompilerInitializeRegAlloc(&cUnit); // Needs to happen after SSA naming
-
- /* Allocate Registers using simple local allocation scheme */
- dvmCompilerLocalRegAlloc(&cUnit);
-
- /* Convert MIR to LIR, etc. */
- dvmCompilerMethodMIR2LIR(&cUnit);
-
- // Debugging only
- //dumpCFG(&cUnit, "/data/tombstones/");
-
- /* Method is not empty */
- if (cUnit.firstLIRInsn) {
- /* Convert LIR into machine code. Loop for recoverable retries */
- do {
- dvmCompilerAssembleLIR(&cUnit, info);
- cUnit.assemblerRetries++;
- if (cUnit.printMe && cUnit.assemblerStatus != kSuccess)
- LOGD("Assembler abort #%d on %d",cUnit.assemblerRetries,
- cUnit.assemblerStatus);
- } while (cUnit.assemblerStatus == kRetryAll);
-
- if (cUnit.printMe) {
- dvmCompilerCodegenDump(&cUnit);
- }
-
- if (info->codeAddress) {
- dvmJitSetCodeAddr(dexCode->insns, info->codeAddress,
- info->instructionSet, true, 0);
- /*
- * Clear the codeAddress for the enclosing trace to reuse the info
- */
- info->codeAddress = NULL;
- }
- }
-
- return false;
-}
diff --git a/vm/compiler/Loop.c b/vm/compiler/Loop.c
index 9ee430d..b9ad3d3 100644
--- a/vm/compiler/Loop.c
+++ b/vm/compiler/Loop.c
@@ -552,3 +552,125 @@
genHoistedChecks(cUnit);
return true;
}
+
+void resetBlockEdges(BasicBlock *bb)
+{
+ bb->taken = NULL;
+ bb->fallThrough = NULL;
+ bb->successorBlockList.blockListType = kNotUsed;
+}
+
+static bool clearPredecessorVector(struct CompilationUnit *cUnit,
+ struct BasicBlock *bb)
+{
+ dvmClearAllBits(bb->predecessors);
+ return false;
+}
+
+bool dvmCompilerFilterLoopBlocks(CompilationUnit *cUnit)
+{
+ BasicBlock *firstBB = cUnit->entryBlock->fallThrough;
+
+ int numPred = dvmCountSetBits(firstBB->predecessors);
+ /*
+ * A loop body should have at least two incoming edges. Here we go with the
+ * simple case and only form loops if numPred == 2.
+ */
+ if (numPred != 2) return false;
+
+ BitVectorIterator bvIterator;
+ GrowableList *blockList = &cUnit->blockList;
+ BasicBlock *predBB = NULL;
+
+ dvmBitVectorIteratorInit(firstBB->predecessors, &bvIterator);
+ while (true) {
+ int predIdx = dvmBitVectorIteratorNext(&bvIterator);
+ if (predIdx == -1) break;
+ predBB = (BasicBlock *) dvmGrowableListGetElement(blockList, predIdx);
+ if (predBB != cUnit->entryBlock) break;
+ }
+
+ /* Used to record which block is in the loop */
+ dvmClearAllBits(cUnit->tempBlockV);
+
+ dvmCompilerSetBit(cUnit->tempBlockV, predBB->id);
+
+ /* Form a loop by only including iDom block that is also a predecessor */
+ while (predBB != firstBB) {
+ BasicBlock *iDom = predBB->iDom;
+ if (!dvmIsBitSet(predBB->predecessors, iDom->id)) {
+ return false;
+ /*
+ * And don't form nested loops (ie by detecting if the branch target
+ * of iDom dominates iDom).
+ */
+ } else if (iDom->taken &&
+ dvmIsBitSet(iDom->dominators, iDom->taken->id) &&
+ iDom != firstBB) {
+ return false;
+ }
+ dvmCompilerSetBit(cUnit->tempBlockV, iDom->id);
+ predBB = iDom;
+ }
+
+ /* Add the entry block and first block */
+ dvmCompilerSetBit(cUnit->tempBlockV, firstBB->id);
+ dvmCompilerSetBit(cUnit->tempBlockV, cUnit->entryBlock->id);
+
+ /* Now mark blocks not included in the loop as hidden */
+ GrowableListIterator iterator;
+ dvmGrowableListIteratorInit(&cUnit->blockList, &iterator);
+ while (true) {
+ BasicBlock *bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator);
+ if (bb == NULL) break;
+ if (!dvmIsBitSet(cUnit->tempBlockV, bb->id)) {
+ bb->hidden = true;
+ /* Clear the insn list */
+ bb->firstMIRInsn = bb->lastMIRInsn = NULL;
+ resetBlockEdges(bb);
+ }
+ }
+
+ dvmCompilerDataFlowAnalysisDispatcher(cUnit, clearPredecessorVector,
+ kAllNodes, false /* isIterative */);
+
+ dvmGrowableListIteratorInit(&cUnit->blockList, &iterator);
+ while (true) {
+ BasicBlock *bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator);
+ if (bb == NULL) break;
+ if (dvmIsBitSet(cUnit->tempBlockV, bb->id)) {
+ if (bb->taken) {
+ /*
+ * exit block means we run into control-flow that we don't want
+ * to handle.
+ */
+ if (bb->taken == cUnit->exitBlock) {
+ return false;
+ }
+ if (bb->taken->hidden) {
+ bb->taken->blockType = kChainingCellNormal;
+ bb->taken->hidden = false;
+ }
+ dvmCompilerSetBit(bb->taken->predecessors, bb->id);
+ }
+ if (bb->fallThrough) {
+ /*
+ * exit block means we run into control-flow that we don't want
+ * to handle.
+ */
+ if (bb->fallThrough == cUnit->exitBlock) {
+ return false;
+ }
+ if (bb->fallThrough->hidden) {
+ bb->fallThrough->blockType = kChainingCellNormal;
+ bb->fallThrough->hidden = false;
+ }
+ dvmCompilerSetBit(bb->fallThrough->predecessors, bb->id);
+ }
+ /* Loop blocks shouldn't contain any successor blocks (yet) */
+ assert(bb->successorBlockList.blockListType == kNotUsed);
+ }
+ }
+
+ return true;
+}
diff --git a/vm/compiler/Loop.h b/vm/compiler/Loop.h
index 8981dae..ec87e57 100644
--- a/vm/compiler/Loop.h
+++ b/vm/compiler/Loop.h
@@ -34,4 +34,6 @@
bool bodyIsClean; // loop body cannot throw any exceptions
} LoopAnalysis;
+bool dvmCompilerFilterLoopBlocks(CompilationUnit *cUnit);
+
#endif /* _DALVIK_VM_LOOP */
diff --git a/vm/compiler/MethodSSATransformation.c b/vm/compiler/SSATransformation.c
similarity index 82%
rename from vm/compiler/MethodSSATransformation.c
rename to vm/compiler/SSATransformation.c
index bacf43c..b045a1e 100644
--- a/vm/compiler/MethodSSATransformation.c
+++ b/vm/compiler/SSATransformation.c
@@ -23,7 +23,7 @@
static void recordDFSPreOrder(CompilationUnit *cUnit, BasicBlock *block)
{
- if (block->visited) return;
+ if (block->visited || block->hidden) return;
block->visited = true;
/* Enqueue the block id */
@@ -49,9 +49,13 @@
/* Sort the blocks by the Depth-First-Search pre-order */
static void computeDFSOrder(CompilationUnit *cUnit)
{
- /* Initialize the DFS order list */
- dvmInitGrowableList(&cUnit->dfsOrder, cUnit->numBlocks);
-
+ /* Initialize or reset the DFS order list */
+ if (cUnit->dfsOrder.elemList == NULL) {
+ dvmInitGrowableList(&cUnit->dfsOrder, cUnit->numBlocks);
+ } else {
+ /* Just reset the used length on the counter */
+ cUnit->dfsOrder.numUsed = 0;
+ }
dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerClearVisitedFlag,
kAllNodes,
@@ -101,14 +105,16 @@
kAllNodes,
false /* isIterative */);
- /*
- * Also set the incoming parameters as defs in the entry block.
- * Only need to handle the parameters for the outer method.
- */
- int inReg = cUnit->method->registersSize - cUnit->method->insSize;
- for (; inReg < cUnit->method->registersSize; inReg++) {
- dvmCompilerSetBit(cUnit->defBlockMatrix[inReg],
- cUnit->entryBlock->id);
+ if (cUnit->jitMode == kJitMethod) {
+ /*
+ * Also set the incoming parameters as defs in the entry block.
+ * Only need to handle the parameters for the outer method.
+ */
+ int inReg = cUnit->method->registersSize - cUnit->method->insSize;
+ for (; inReg < cUnit->method->registersSize; inReg++) {
+ dvmCompilerSetBit(cUnit->defBlockMatrix[inReg],
+ cUnit->entryBlock->id);
+ }
}
}
@@ -137,17 +143,31 @@
}
}
+static void checkForDominanceFrontier(BasicBlock *domBB,
+ const BasicBlock *succBB)
+{
+ /*
+ * TODO - evaluate whether phi will ever need to be inserted into exit
+ * blocks.
+ */
+ if (succBB->iDom != domBB &&
+ succBB->blockType == kDalvikByteCode &&
+ succBB->hidden == false) {
+ dvmSetBit(domBB->domFrontier, succBB->id);
+ }
+}
+
/* Worker function to compute the dominance frontier */
static bool computeDominanceFrontier(CompilationUnit *cUnit, BasicBlock *bb)
{
GrowableList *blockList = &cUnit->blockList;
/* Calculate DF_local */
- if (bb->taken && (bb->taken->iDom != bb)) {
- dvmSetBit(bb->domFrontier, bb->taken->id);
+ if (bb->taken) {
+ checkForDominanceFrontier(bb, bb->taken);
}
- if (bb->fallThrough && (bb->fallThrough->iDom != bb)) {
- dvmSetBit(bb->domFrontier, bb->fallThrough->id);
+ if (bb->fallThrough) {
+ checkForDominanceFrontier(bb, bb->fallThrough);
}
if (bb->successorBlockList.blockListType != kNotUsed) {
GrowableListIterator iterator;
@@ -158,9 +178,7 @@
(SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator);
if (successorBlockInfo == NULL) break;
BasicBlock *succBB = successorBlockInfo->block;
- if (succBB->iDom != bb) {
- dvmSetBit(bb->domFrontier, succBB->id);
- }
+ checkForDominanceFrontier(bb, succBB);
}
}
@@ -179,11 +197,10 @@
if (dfUpIdx == -1) break;
BasicBlock *dfUpBlock = (BasicBlock *)
dvmGrowableListGetElement(blockList, dfUpIdx);
- if (dfUpBlock->iDom != bb) {
- dvmSetBit(bb->domFrontier, dfUpBlock->id);
- }
+ checkForDominanceFrontier(bb, dfUpBlock);
}
}
+
return true;
}
@@ -192,12 +209,18 @@
{
int numTotalBlocks = cUnit->blockList.numUsed;
- bb->dominators = dvmCompilerAllocBitVector(numTotalBlocks,
- false /* expandable */);
- bb->iDominated = dvmCompilerAllocBitVector(numTotalBlocks,
- false /* expandable */);
- bb->domFrontier = dvmCompilerAllocBitVector(numTotalBlocks,
- false /* expandable */);
+ if (bb->dominators == NULL ) {
+ bb->dominators = dvmCompilerAllocBitVector(numTotalBlocks,
+ false /* expandable */);
+ bb->iDominated = dvmCompilerAllocBitVector(numTotalBlocks,
+ false /* expandable */);
+ bb->domFrontier = dvmCompilerAllocBitVector(numTotalBlocks,
+ false /* expandable */);
+ } else {
+ dvmClearAllBits(bb->dominators);
+ dvmClearAllBits(bb->iDominated);
+ dvmClearAllBits(bb->domFrontier);
+ }
/* Set all bits in the dominator vector */
dvmSetInitialBits(bb->dominators, numTotalBlocks);
@@ -296,8 +319,12 @@
dvmClearAllBits(cUnit->entryBlock->dominators);
dvmSetBit(cUnit->entryBlock->dominators, cUnit->entryBlock->id);
- cUnit->tempBlockV = dvmCompilerAllocBitVector(numTotalBlocks,
- false /* expandable */);
+ if (cUnit->tempBlockV == NULL) {
+ cUnit->tempBlockV = dvmCompilerAllocBitVector(numTotalBlocks,
+ false /* expandable */);
+ } else {
+ dvmClearAllBits(cUnit->tempBlockV);
+ }
dvmCompilerDataFlowAnalysisDispatcher(cUnit, computeBlockDominators,
kPreOrderDFSTraversal,
true /* isIterative */);
@@ -311,7 +338,12 @@
* Now go ahead and compute the post order traversal based on the
* iDominated sets.
*/
- dvmInitGrowableList(&cUnit->domPostOrderTraversal, numReachableBlocks);
+ if (cUnit->domPostOrderTraversal.elemList == NULL) {
+ dvmInitGrowableList(&cUnit->domPostOrderTraversal, numReachableBlocks);
+ } else {
+ cUnit->domPostOrderTraversal.numUsed = 0;
+ }
+
computeDomPostOrderTraversal(cUnit, cUnit->entryBlock);
assert(cUnit->domPostOrderTraversal.numUsed ==
(unsigned) cUnit->numReachableBlocks);
@@ -411,16 +443,19 @@
dvmCopyBitVector(inputBlocks, cUnit->defBlockMatrix[dalvikReg]);
dvmClearAllBits(phiBlocks);
+
/* Calculate the phi blocks for each Dalvik register */
do {
change = false;
dvmClearAllBits(tmpBlocks);
dvmBitVectorIteratorInit(inputBlocks, &iterator);
+
while (true) {
int idx = dvmBitVectorIteratorNext(&iterator);
if (idx == -1) break;
BasicBlock *defBB =
(BasicBlock *) dvmGrowableListGetElement(blockList, idx);
+
/* Merge the dominance frontier to tmpBlocks */
dvmUnifyBitVectors(tmpBlocks, tmpBlocks, defBB->domFrontier);
}
@@ -552,3 +587,51 @@
kReachableNodes,
false /* isIterative */);
}
+
+/* Build a loop. Return true if a loop structure is successfully identified. */
+bool dvmCompilerBuildLoop(CompilationUnit *cUnit)
+{
+ /* Compute the DFS order */
+ computeDFSOrder(cUnit);
+
+ /* Compute the dominator info */
+ computeDominators(cUnit);
+
+ /* Loop structure not recognized/supported - return false */
+ if (dvmCompilerFilterLoopBlocks(cUnit) == false)
+ return false;
+
+ /* Re-compute the DFS order just for the loop */
+ computeDFSOrder(cUnit);
+
+ /* Re-compute the dominator info just for the loop */
+ computeDominators(cUnit);
+
+ /* Allocate data structures in preparation for SSA conversion */
+ dvmInitializeSSAConversion(cUnit);
+
+ /* Find out the "Dalvik reg def x block" relation */
+ computeDefBlockMatrix(cUnit);
+
+ /* Insert phi nodes to dominance frontiers for all variables */
+ insertPhiNodes(cUnit);
+
+ /* Rename register names by local defs and phi nodes */
+ dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerDoSSAConversion,
+ kPreOrderDFSTraversal,
+ false /* isIterative */);
+
+ /*
+ * Shared temp bit vector used by each block to count the number of defs
+ * from all the predecessor blocks.
+ */
+ cUnit->tempSSARegisterV = dvmCompilerAllocBitVector(cUnit->numSSARegs,
+ false);
+
+ /* Insert phi-operands with latest SSA names from predecessor blocks */
+ dvmCompilerDataFlowAnalysisDispatcher(cUnit, insertPhiNodeOperands,
+ kReachableNodes,
+ false /* isIterative */);
+
+ return true;
+}
diff --git a/vm/compiler/Utility.c b/vm/compiler/Utility.c
index 7be57ef..fb16388 100644
--- a/vm/compiler/Utility.c
+++ b/vm/compiler/Utility.c
@@ -352,7 +352,7 @@
LOGE("%s", msg);
for (i = 0; i < length; i++) {
if (dvmIsBitSet(bv, i)) {
- LOGE("Bit %d is set", i);
+ LOGE(" Bit %d is set", i);
}
}
}
@@ -398,6 +398,9 @@
case kDalvikByteCode:
snprintf(name, BLOCK_NAME_LEN, "block%04x", bb->startOffset);
break;
+ case kChainingCellNormal:
+ snprintf(name, BLOCK_NAME_LEN, "chain%04x", bb->startOffset);
+ break;
case kExceptionHandling:
snprintf(name, BLOCK_NAME_LEN, "exception%04x", bb->startOffset);
break;
diff --git a/vm/compiler/codegen/arm/ArchFactory.c b/vm/compiler/codegen/arm/ArchFactory.c
index 805a6fc..5a03b17 100644
--- a/vm/compiler/codegen/arm/ArchFactory.c
+++ b/vm/compiler/codegen/arm/ArchFactory.c
@@ -32,7 +32,7 @@
TGT_LIR *pcrLabel)
{
TGT_LIR *branch = genCmpImmBranch(cUnit, cond, reg, checkValue);
- if (cUnit->methodJitMode) {
+ if (cUnit->jitMode == kJitMethod) {
BasicBlock *bb = cUnit->curBlock;
if (bb->taken) {
ArmLIR *exceptionLabel = (ArmLIR *) cUnit->blockLabelList;
diff --git a/vm/compiler/codegen/arm/Assemble.c b/vm/compiler/codegen/arm/Assemble.c
index 9b24b75..17fef2b 100644
--- a/vm/compiler/codegen/arm/Assemble.c
+++ b/vm/compiler/codegen/arm/Assemble.c
@@ -1336,8 +1336,8 @@
int offset = 0;
int i;
ChainCellCounts chainCellCounts;
- int descSize =
- cUnit->methodJitMode ? 0 : getTraceDescriptionSize(cUnit->traceDesc);
+ int descSize = (cUnit->jitMode == kJitMethod) ?
+ 0 : getTraceDescriptionSize(cUnit->traceDesc);
int chainingCellGap = 0;
info->instructionSet = cUnit->instructionSet;
@@ -1367,7 +1367,7 @@
u4 chainCellOffset = offset;
ArmLIR *chainCellOffsetLIR = NULL;
- if (!cUnit->methodJitMode) {
+ if (cUnit->jitMode != kJitMethod) {
/*
* Get the gap (# of u4) between the offset of chaining cell count and
* the bottom of real chaining cells. If the translation has chaining
@@ -1430,7 +1430,7 @@
break;
case kRetryAll:
if (cUnit->assemblerRetries < MAX_ASSEMBLER_RETRIES) {
- if (!cUnit->methodJitMode) {
+ if (cUnit->jitMode != kJitMethod) {
/* Restore pristine chain cell marker on retry */
chainCellOffsetLIR->operands[0] = CHAIN_CELL_OFFSET_TAG;
}
@@ -1482,7 +1482,7 @@
memcpy((char*)cUnit->baseAddr, cUnit->codeBuffer, chainCellOffset);
gDvmJit.numCompilations++;
- if (!cUnit->methodJitMode) {
+ if (cUnit->jitMode != kJitMethod) {
/* Install the chaining cell counts */
for (i=0; i< kChainingCellGap; i++) {
chainCellCounts.u.count[i] = cUnit->numChainingCells[i];
