diff options
Diffstat (limited to 'vm/compiler')
36 files changed, 2343 insertions, 801 deletions
diff --git a/vm/compiler/Compiler.c b/vm/compiler/Compiler.c index 1ac6e9789..c8ff62ee3 100644 --- a/vm/compiler/Compiler.c +++ b/vm/compiler/Compiler.c @@ -178,8 +178,8 @@ bool dvmCompilerSetupCodeCache(void) gDvmJit.codeCacheByteUsed = templateSize; /* Only flush the part in the code cache that is being used now */ - cacheflush((intptr_t) gDvmJit.codeCache, - (intptr_t) gDvmJit.codeCache + templateSize, 0); + dvmCompilerCacheFlush((intptr_t) gDvmJit.codeCache, + (intptr_t) gDvmJit.codeCache + templateSize, 0); int result = mprotect(gDvmJit.codeCache, gDvmJit.codeCacheSize, PROTECT_CODE_CACHE_ATTRS); @@ -209,7 +209,7 @@ static void crawlDalvikStack(Thread *thread, bool print) saveArea = SAVEAREA_FROM_FP(fp); if (print) { - if (dvmIsBreakFrame(fp)) { + if (dvmIsBreakFrame((u4*)fp)) { LOGD(" #%d: break frame (%p)", stackLevel, saveArea->returnAddr); } @@ -281,8 +281,9 @@ static void resetCodeCache(void) memset((char *) gDvmJit.codeCache + gDvmJit.templateSize, 0, gDvmJit.codeCacheByteUsed - gDvmJit.templateSize); - cacheflush((intptr_t) gDvmJit.codeCache, - (intptr_t) gDvmJit.codeCache + gDvmJit.codeCacheByteUsed, 0); + dvmCompilerCacheFlush((intptr_t) gDvmJit.codeCache, + (intptr_t) gDvmJit.codeCache + + gDvmJit.codeCacheByteUsed, 0); PROTECT_CODE_CACHE(gDvmJit.codeCache, gDvmJit.codeCacheByteUsed); @@ -627,6 +628,11 @@ static void *compilerThreadStart(void *arg) compileOK = dvmCompilerDoWork(&work); } if (aborted || !compileOK) { +#if 0 // for x86 JIT testing + dvmJitSetCodeAddr(work.pc, + dvmCompilerGetInterpretTemplate(), + work.result.instructionSet); +#endif dvmCompilerArenaReset(); } else if (!work.result.discardResult && work.result.codeAddress) { diff --git a/vm/compiler/Compiler.h b/vm/compiler/Compiler.h index 6dd9cbd58..0a43df3c9 100644 --- a/vm/compiler/Compiler.h +++ b/vm/compiler/Compiler.h @@ -236,6 +236,15 @@ typedef enum JitOptimizationHints { #define JIT_OPT_NO_LOOP (1 << kJitOptNoLoop) +/* Customized node traversal orders for different needs */ +typedef enum DataFlowAnalysisMode { + kAllNodes = 0, // All nodes + kReachableNodes, // All reachable nodes + kPreOrderDFSTraversal, // Depth-First-Search / Pre-Order + kPostOrderDFSTraversal, // Depth-First-Search / Post-Order + kPostOrderDOMTraversal, // Dominator tree / Post-Order +} DataFlowAnalysisMode; + typedef struct CompilerMethodStats { const Method *method; // Used as hash entry signature int dalvikSize; // # of bytes for dalvik bytecodes @@ -262,8 +271,7 @@ CompilerMethodStats *dvmCompilerAnalyzeMethodBody(const Method *method, bool isCallee); bool dvmCompilerCanIncludeThisInstruction(const Method *method, const DecodedInstruction *insn); -bool dvmCompileMethod(struct CompilationUnit *cUnit, const Method *method, - JitTranslationInfo *info); +bool dvmCompileMethod(const Method *method); bool dvmCompileTrace(JitTraceDescription *trace, int numMaxInsts, JitTranslationInfo *info, jmp_buf *bailPtr, int optHints); void dvmCompilerDumpStats(void); @@ -273,22 +281,31 @@ void dvmCompilerSortAndPrintTraceProfiles(void); void dvmCompilerPerformSafePointChecks(void); void dvmCompilerInlineMIR(struct CompilationUnit *cUnit); void dvmInitializeSSAConversion(struct CompilationUnit *cUnit); -int dvmConvertSSARegToDalvik(struct CompilationUnit *cUnit, int ssaReg); +int dvmConvertSSARegToDalvik(const struct CompilationUnit *cUnit, int ssaReg); bool dvmCompilerLoopOpt(struct CompilationUnit *cUnit); void dvmCompilerNonLoopAnalysis(struct CompilationUnit *cUnit); -void dvmCompilerFindLiveIn(struct CompilationUnit *cUnit, - struct BasicBlock *bb); -void dvmCompilerDoSSAConversion(struct CompilationUnit *cUnit, +bool dvmCompilerFindLocalLiveIn(struct CompilationUnit *cUnit, + struct BasicBlock *bb); +bool dvmCompilerDoSSAConversion(struct CompilationUnit *cUnit, struct BasicBlock *bb); -void dvmCompilerDoConstantPropagation(struct CompilationUnit *cUnit, +bool dvmCompilerDoConstantPropagation(struct CompilationUnit *cUnit, struct BasicBlock *bb); -void dvmCompilerFindInductionVariables(struct CompilationUnit *cUnit, +bool dvmCompilerFindInductionVariables(struct CompilationUnit *cUnit, struct BasicBlock *bb); -char *dvmCompilerGetDalvikDisassembly(DecodedInstruction *insn, char *note); +/* Clear the visited flag for each BB */ +bool dvmCompilerClearVisitedFlag(struct CompilationUnit *cUnit, + struct BasicBlock *bb); +char *dvmCompilerGetDalvikDisassembly(const DecodedInstruction *insn, + char *note); +char *dvmCompilerFullDisassembler(const struct CompilationUnit *cUnit, + const struct MIR *mir); char *dvmCompilerGetSSAString(struct CompilationUnit *cUnit, struct SSARepresentation *ssaRep); void dvmCompilerDataFlowAnalysisDispatcher(struct CompilationUnit *cUnit, - void (*func)(struct CompilationUnit *, struct BasicBlock *)); + bool (*func)(struct CompilationUnit *, struct BasicBlock *), + DataFlowAnalysisMode dfaMode, + bool isIterative); +void dvmCompilerMethodSSATransformation(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 712ca4ce8..caf6fa617 100644 --- a/vm/compiler/CompilerIR.h +++ b/vm/compiler/CompilerIR.h @@ -61,6 +61,7 @@ typedef enum BBType { kMethodExitBlock, kPCReconstruction, kExceptionHandling, + kCatchEntry, } BBType; typedef struct ChainCellCounts { @@ -133,9 +134,17 @@ typedef struct MIR { struct BasicBlockDataFlow; +/* For successorBlockList */ +typedef enum BlockListType { + kNotUsed = 0, + kCatch, + kPackedSwitch, + kSparseSwitch, +} BlockListType; + typedef struct BasicBlock { int id; - int visited; + bool visited; unsigned int startOffset; const Method *containingMethod; // For blocks from the callee BBType blockType; @@ -145,10 +154,29 @@ typedef struct BasicBlock { MIR *lastMIRInsn; struct BasicBlock *fallThrough; struct BasicBlock *taken; - struct BasicBlock *next; // Serial link for book keeping purposes + struct BasicBlock *iDom; // Immediate dominator struct BasicBlockDataFlow *dataFlowInfo; + BitVector *predecessors; + BitVector *dominators; + BitVector *iDominated; // Set nodes being immediately dominated + BitVector *domFrontier; // Dominance frontier + struct { // For one-to-many successors like + BlockListType blockListType; // switch and exception handling + GrowableList blocks; + } successorBlockList; } BasicBlock; +/* + * The "blocks" field in "successorBlockList" points to an array of + * elements with the type "SuccessorBlockInfo". + * For catch blocks, key is type index for the exception. + * For swtich blocks, key is the case value. + */ +typedef struct SuccessorBlockInfo { + BasicBlock *block; + int key; +} SuccessorBlockInfo; + struct LoopAnalysis; struct RegisterPool; @@ -161,7 +189,7 @@ typedef enum AssemblerStatus { typedef struct CompilationUnit { int numInsts; int numBlocks; - BasicBlock **blockList; + GrowableList blockList; const Method *method; const JitTraceDescription *traceDesc; LIR *firstLIRInsn; @@ -213,6 +241,20 @@ typedef struct CompilationUnit { * MAX_CHAINED_SWITCH_CASES cases. */ const u2 *switchOverflowPad; + + /* New fields only for method-based compilation */ + int numReachableBlocks; + int numDalvikRegisters; // method->registersSize + inlined + BasicBlock *entryBlock; + BasicBlock *exitBlock; + GrowableList dfsOrder; + GrowableList domPostOrderTraversal; + BitVector *tryBlockAddr; + BitVector **defBlockMatrix; // numDalvikRegister x numBlocks + BitVector *tempBlockV; + BitVector *tempDalvikRegisterV; + BitVector *tempSSARegisterV; // numSSARegs + bool printSSANames; } CompilationUnit; #if defined(WITH_SELF_VERIFICATION) @@ -221,7 +263,7 @@ typedef struct CompilationUnit { #define HEAP_ACCESS_SHADOW(_state) #endif -BasicBlock *dvmCompilerNewBB(BBType blockType); +BasicBlock *dvmCompilerNewBB(BBType blockType, int blockId); void dvmCompilerAppendMIR(BasicBlock *bb, MIR *mir); diff --git a/vm/compiler/CompilerUtility.h b/vm/compiler/CompilerUtility.h index 551edb8ab..3e65a2eb0 100644 --- a/vm/compiler/CompilerUtility.h +++ b/vm/compiler/CompilerUtility.h @@ -39,19 +39,41 @@ void dvmCompilerArenaReset(void); typedef struct GrowableList { size_t numAllocated; size_t numUsed; - void **elemList; + intptr_t *elemList; } GrowableList; +typedef struct GrowableListIterator { + GrowableList *list; + size_t idx; + size_t size; +} GrowableListIterator; + #define GET_ELEM_N(LIST, TYPE, N) (((TYPE*) LIST->elemList)[N]) +#define BLOCK_NAME_LEN 80 + +/* Forward declarations */ struct LIR; +struct BasicBlock; void dvmInitGrowableList(GrowableList *gList, size_t initLength); -void dvmInsertGrowableList(GrowableList *gList, void *elem); +void dvmInsertGrowableList(GrowableList *gList, intptr_t elem); +void dvmGrowableListIteratorInit(GrowableList *gList, + GrowableListIterator *iterator); +intptr_t dvmGrowableListIteratorNext(GrowableListIterator *iterator); +intptr_t dvmGrowableListGetElement(const GrowableList *gList, size_t idx); + BitVector* dvmCompilerAllocBitVector(int startBits, bool expandable); bool dvmCompilerSetBit(BitVector* pBits, int num); +bool dvmCompilerClearBit(BitVector* pBits, int num); +void dvmCompilerMarkAllBits(BitVector *pBits, bool set); void dvmDebugBitVector(char *msg, const BitVector *bv, int length); void dvmDumpLIRInsn(struct LIR *lir, unsigned char *baseAddr); void dvmDumpResourceMask(struct LIR *lir, u8 mask, const char *prefix); +void dvmDumpBlockBitVector(const GrowableList *blocks, char *msg, + const BitVector *bv, int length); +void dvmGetBlockName(struct BasicBlock *bb, char *name); +int dvmCompilerCacheFlush(long start, long end, long flags); + #endif /* _DALVIK_COMPILER_UTILITY */ diff --git a/vm/compiler/Dataflow.c b/vm/compiler/Dataflow.c index 82f52b931..411f456e7 100644 --- a/vm/compiler/Dataflow.c +++ b/vm/compiler/Dataflow.c @@ -809,7 +809,7 @@ int dvmCompilerDataFlowAttributes[kMirOpLast] = { }; /* Return the Dalvik register/subscript pair of a given SSA register */ -int dvmConvertSSARegToDalvik(CompilationUnit *cUnit, int ssaReg) +int dvmConvertSSARegToDalvik(const CompilationUnit *cUnit, int ssaReg) { return GET_ELEM_N(cUnit->ssaToDalvikMap, int, ssaReg); } @@ -819,21 +819,58 @@ int dvmConvertSSARegToDalvik(CompilationUnit *cUnit, int ssaReg) * and subscript pair. Each SSA register can be used to index the * ssaToDalvikMap list to get the subscript[31..16]/dalvik_reg[15..0] mapping. */ -char *dvmCompilerGetDalvikDisassembly(DecodedInstruction *insn, +char *dvmCompilerGetDalvikDisassembly(const DecodedInstruction *insn, char *note) { char buffer[256]; int opcode = insn->opcode; int dfAttributes = dvmCompilerDataFlowAttributes[opcode]; + int flags = dexGetFlagsFromOpcode(insn->opcode); char *ret; buffer[0] = 0; - strcpy(buffer, dexGetOpcodeName(opcode)); + if (opcode >= kMirOpFirst) { + if (opcode == kMirOpPhi) { + strcpy(buffer, "PHI"); + } + else { + sprintf(buffer, "Opcode 0x%x", opcode); + } + } else { + strcpy(buffer, dexGetOpcodeName(opcode)); + } if (note) strcat(buffer, note); - if (dfAttributes & DF_FORMAT_35C) { + /* For branches, decode the instructions to print out the branch targets */ + if (flags & kInstrCanBranch) { + InstructionFormat dalvikFormat = dexGetFormatFromOpcode(insn->opcode); + int offset = 0; + switch (dalvikFormat) { + case kFmt21t: + snprintf(buffer + strlen(buffer), 256, " v%d,", insn->vA); + offset = (int) insn->vB; + break; + case kFmt22t: + snprintf(buffer + strlen(buffer), 256, " v%d, v%d,", + insn->vA, insn->vB); + offset = (int) insn->vC; + break; + case kFmt10t: + case kFmt20t: + case kFmt30t: + offset = (int) insn->vA; + break; + default: + LOGE("Unexpected branch format: %d", dalvikFormat); + dvmAbort(); + break; + } + snprintf(buffer + strlen(buffer), 256, " (%c%x)", + offset > 0 ? '+' : '-', + offset > 0 ? offset : -offset); + } else if (dfAttributes & DF_FORMAT_35C) { unsigned int i; for (i = 0; i < insn->vA; i++) { if (i != 0) strcat(buffer, ","); @@ -851,18 +888,153 @@ char *dvmCompilerGetDalvikDisassembly(DecodedInstruction *insn, if (dfAttributes & DF_B_IS_REG) { snprintf(buffer + strlen(buffer), 256, ", v%d", insn->vB); } - else { + else if (opcode < kMirOpFirst) { snprintf(buffer + strlen(buffer), 256, ", (#%d)", insn->vB); } if (dfAttributes & DF_C_IS_REG) { snprintf(buffer + strlen(buffer), 256, ", v%d", insn->vC); } - else { + else if (opcode < kMirOpFirst) { snprintf(buffer + strlen(buffer), 256, ", (#%d)", insn->vC); } } int length = strlen(buffer) + 1; - ret = dvmCompilerNew(length, false); + ret = (char *)dvmCompilerNew(length, false); + memcpy(ret, buffer, length); + return ret; +} + +char *getSSAName(const CompilationUnit *cUnit, int ssaReg, char *name) +{ + int ssa2DalvikValue = dvmConvertSSARegToDalvik(cUnit, ssaReg); + + sprintf(name, "v%d_%d", + DECODE_REG(ssa2DalvikValue), DECODE_SUB(ssa2DalvikValue)); + return name; +} + +/* + * Dalvik instruction disassembler with optional SSA printing. + */ +char *dvmCompilerFullDisassembler(const CompilationUnit *cUnit, + const MIR *mir) +{ + char buffer[256]; + char operand0[256], operand1[256]; + const DecodedInstruction *insn = &mir->dalvikInsn; + int opcode = insn->opcode; + int dfAttributes = dvmCompilerDataFlowAttributes[opcode]; + int flags = dexGetFlagsFromOpcode(insn->opcode); + char *ret; + int length; + + buffer[0] = 0; + if (opcode >= kMirOpFirst) { + if (opcode == kMirOpPhi) { + snprintf(buffer, 256, "PHI %s = (%s", + getSSAName(cUnit, mir->ssaRep->defs[0], operand0), + getSSAName(cUnit, mir->ssaRep->uses[0], operand1)); + int i; + for (i = 1; i < mir->ssaRep->numUses; i++) { + snprintf(buffer + strlen(buffer), 256, ", %s", + getSSAName(cUnit, mir->ssaRep->uses[i], operand0)); + } + snprintf(buffer + strlen(buffer), 256, ")"); + } + else { + sprintf(buffer, "Opcode 0x%x", opcode); + } + goto done; + } else { + strcpy(buffer, dexGetOpcodeName(opcode)); + } + + /* For branches, decode the instructions to print out the branch targets */ + if (flags & kInstrCanBranch) { + InstructionFormat dalvikFormat = dexGetFormatFromOpcode(insn->opcode); + int delta = 0; + switch (dalvikFormat) { + case kFmt21t: + snprintf(buffer + strlen(buffer), 256, " %s, ", + getSSAName(cUnit, mir->ssaRep->uses[0], operand0)); + delta = (int) insn->vB; + break; + case kFmt22t: + snprintf(buffer + strlen(buffer), 256, " %s, %s, ", + getSSAName(cUnit, mir->ssaRep->uses[0], operand0), + getSSAName(cUnit, mir->ssaRep->uses[1], operand1)); + delta = (int) insn->vC; + break; + case kFmt10t: + case kFmt20t: + case kFmt30t: + delta = (int) insn->vA; + break; + default: + LOGE("Unexpected branch format: %d", dalvikFormat); + dvmAbort(); + break; + } + snprintf(buffer + strlen(buffer), 256, " %04x", + mir->offset + delta); + } else if (dfAttributes & (DF_FORMAT_35C | DF_FORMAT_3RC)) { + unsigned int i; + for (i = 0; i < insn->vA; i++) { + if (i != 0) strcat(buffer, ","); + snprintf(buffer + strlen(buffer), 256, " %s", + getSSAName(cUnit, mir->ssaRep->uses[i], operand0)); + } + } else { + int udIdx; + if (mir->ssaRep->numDefs) { + + for (udIdx = 0; udIdx < mir->ssaRep->numDefs; udIdx++) { + snprintf(buffer + strlen(buffer), 256, " %s", + getSSAName(cUnit, mir->ssaRep->defs[udIdx], operand0)); + } + strcat(buffer, ","); + } + if (mir->ssaRep->numUses) { + /* No leading ',' for the first use */ + snprintf(buffer + strlen(buffer), 256, " %s", + getSSAName(cUnit, mir->ssaRep->uses[0], operand0)); + for (udIdx = 1; udIdx < mir->ssaRep->numUses; udIdx++) { + snprintf(buffer + strlen(buffer), 256, ", %s", + getSSAName(cUnit, mir->ssaRep->uses[udIdx], operand0)); + } + } + if (opcode < kMirOpFirst) { + InstructionFormat dalvikFormat = dexGetFormatFromOpcode(opcode); + switch (dalvikFormat) { + case kFmt11n: // op vA, #+B + case kFmt21s: // op vAA, #+BBBB + case kFmt21h: // op vAA, #+BBBB00000[00000000] + case kFmt31i: // op vAA, #+BBBBBBBB + case kFmt51l: // op vAA, #+BBBBBBBBBBBBBBBB + snprintf(buffer + strlen(buffer), 256, " #%#x", insn->vB); + break; + case kFmt21c: // op vAA, thing@BBBB + case kFmt31c: // op vAA, thing@BBBBBBBB + snprintf(buffer + strlen(buffer), 256, " @%#x", insn->vB); + break; + case kFmt22b: // op vAA, vBB, #+CC + case kFmt22s: // op vA, vB, #+CCCC + snprintf(buffer + strlen(buffer), 256, " #%#x", insn->vC); + break; + case kFmt22c: // op vA, vB, thing@CCCC + case kFmt22cs: // [opt] op vA, vB, field offset CCCC + snprintf(buffer + strlen(buffer), 256, " @%#x", insn->vC); + break; + /* No need for special printing */ + default: + break; + } + } + } + +done: + length = strlen(buffer) + 1; + ret = (char *) dvmCompilerNew(length, false); memcpy(ret, buffer, length); return ret; } @@ -904,7 +1076,7 @@ char *dvmCompilerGetSSAString(CompilationUnit *cUnit, SSARepresentation *ssaRep) } int length = strlen(buffer) + 1; - ret = dvmCompilerNew(length, false); + ret = (char *)dvmCompilerNew(length, false); memcpy(ret, buffer, length); return ret; } @@ -920,7 +1092,7 @@ static inline void handleLiveInUse(BitVector *useV, BitVector *defV, } /* Mark a reg as being defined */ -static inline void handleLiveInDef(BitVector *defV, int dalvikRegId) +static inline void handleDef(BitVector *defV, int dalvikRegId) { dvmCompilerSetBit(defV, dalvikRegId); } @@ -929,22 +1101,19 @@ static inline void handleLiveInDef(BitVector *defV, int dalvikRegId) * Find out live-in variables for natural loops. Variables that are live-in in * the main loop body are considered to be defined in the entry block. */ -void dvmCompilerFindLiveIn(CompilationUnit *cUnit, BasicBlock *bb) +bool dvmCompilerFindLocalLiveIn(CompilationUnit *cUnit, BasicBlock *bb) { MIR *mir; BitVector *useV, *defV, *liveInV; - if (bb->blockType != kDalvikByteCode && - bb->blockType != kTraceEntryBlock) { - return; - } + if (bb->dataFlowInfo == NULL) return false; useV = bb->dataFlowInfo->useV = - dvmCompilerAllocBitVector(cUnit->method->registersSize, false); + dvmCompilerAllocBitVector(cUnit->numDalvikRegisters, false); defV = bb->dataFlowInfo->defV = - dvmCompilerAllocBitVector(cUnit->method->registersSize, false); + dvmCompilerAllocBitVector(cUnit->numDalvikRegisters, false); liveInV = bb->dataFlowInfo->liveInV = - dvmCompilerAllocBitVector(cUnit->method->registersSize, false); + dvmCompilerAllocBitVector(cUnit->numDalvikRegisters, false); for (mir = bb->firstMIRInsn; mir; mir = mir->next) { int dfAttributes = @@ -972,12 +1141,13 @@ void dvmCompilerFindLiveIn(CompilationUnit *cUnit, BasicBlock *bb) } } if (dfAttributes & DF_HAS_DEFS) { - handleLiveInDef(defV, dInsn->vA); + handleDef(defV, dInsn->vA); if (dfAttributes & DF_DA_WIDE) { - handleLiveInDef(defV, dInsn->vA+1); + handleDef(defV, dInsn->vA+1); } } } + return true; } /* Find out the latest SSA register for a given Dalvik register */ @@ -1002,7 +1172,7 @@ static void handleSSADef(CompilationUnit *cUnit, int *defs, int dalvikReg, cUnit->dalvikToSSAMap[dalvikReg] = newD2SMapping; int newS2DMapping = ENCODE_REG_SUB(dalvikReg, dalvikSub); - dvmInsertGrowableList(cUnit->ssaToDalvikMap, (void *) newS2DMapping); + dvmInsertGrowableList(cUnit->ssaToDalvikMap, newS2DMapping); defs[regIndex] = ssaReg; } @@ -1015,7 +1185,7 @@ static void dataFlowSSAFormat35C(CompilationUnit *cUnit, MIR *mir) int i; mir->ssaRep->numUses = numUses; - mir->ssaRep->uses = dvmCompilerNew(sizeof(int) * numUses, false); + mir->ssaRep->uses = (int *)dvmCompilerNew(sizeof(int) * numUses, false); for (i = 0; i < numUses; i++) { handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->arg[i], i); @@ -1030,7 +1200,7 @@ static void dataFlowSSAFormat3RC(CompilationUnit *cUnit, MIR *mir) int i; mir->ssaRep->numUses = numUses; - mir->ssaRep->uses = dvmCompilerNew(sizeof(int) * numUses, false); + mir->ssaRep->uses = (int *)dvmCompilerNew(sizeof(int) * numUses, false); for (i = 0; i < numUses; i++) { handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vC+i, i); @@ -1038,16 +1208,15 @@ static void dataFlowSSAFormat3RC(CompilationUnit *cUnit, MIR *mir) } /* Entry function to convert a block into SSA representation */ -void dvmCompilerDoSSAConversion(CompilationUnit *cUnit, BasicBlock *bb) +bool dvmCompilerDoSSAConversion(CompilationUnit *cUnit, BasicBlock *bb) { MIR *mir; - if (bb->blockType != kDalvikByteCode && bb->blockType != kTraceEntryBlock) { - return; - } + if (bb->dataFlowInfo == NULL) return false; for (mir = bb->firstMIRInsn; mir; mir = mir->next) { - mir->ssaRep = dvmCompilerNew(sizeof(SSARepresentation), true); + mir->ssaRep = (struct SSARepresentation *) + dvmCompilerNew(sizeof(SSARepresentation), true); int dfAttributes = dvmCompilerDataFlowAttributes[mir->dalvikInsn.opcode]; @@ -1084,8 +1253,10 @@ void dvmCompilerDoSSAConversion(CompilationUnit *cUnit, BasicBlock *bb) if (numUses) { mir->ssaRep->numUses = numUses; - mir->ssaRep->uses = dvmCompilerNew(sizeof(int) * numUses, false); - mir->ssaRep->fpUse = dvmCompilerNew(sizeof(bool) * numUses, false); + mir->ssaRep->uses = (int *)dvmCompilerNew(sizeof(int) * numUses, + false); + mir->ssaRep->fpUse = (bool *)dvmCompilerNew(sizeof(bool) * numUses, + false); } int numDefs = 0; @@ -1099,8 +1270,10 @@ void dvmCompilerDoSSAConversion(CompilationUnit *cUnit, BasicBlock *bb) if (numDefs) { mir->ssaRep->numDefs = numDefs; - mir->ssaRep->defs = dvmCompilerNew(sizeof(int) * numDefs, false); - mir->ssaRep->fpDef = dvmCompilerNew(sizeof(bool) * numDefs, false); + mir->ssaRep->defs = (int *)dvmCompilerNew(sizeof(int) * numDefs, + false); + mir->ssaRep->fpDef = (bool *)dvmCompilerNew(sizeof(bool) * numDefs, + false); } DecodedInstruction *dInsn = &mir->dalvikInsn; @@ -1145,12 +1318,18 @@ void dvmCompilerDoSSAConversion(CompilationUnit *cUnit, BasicBlock *bb) } } + /* + * Take a snapshot of Dalvik->SSA mapping at the end of each block. The + * input to PHI nodes can be derived from the snapshot of all predecessor + * blocks. + */ bb->dataFlowInfo->dalvikToSSAMap = - dvmCompilerNew(sizeof(int) * cUnit->method->registersSize, false); + (int *)dvmCompilerNew(sizeof(int) * cUnit->method->registersSize, + false); - /* Take a snapshot of Dalvik->SSA mapping at the end of each block */ memcpy(bb->dataFlowInfo->dalvikToSSAMap, cUnit->dalvikToSSAMap, sizeof(int) * cUnit->method->registersSize); + return true; } /* Setup a constant value for opcodes thare have the DF_SETS_CONST attribute */ @@ -1160,7 +1339,7 @@ static void setConstant(CompilationUnit *cUnit, int ssaReg, int value) cUnit->constantValues[ssaReg] = value; } -void dvmCompilerDoConstantPropagation(CompilationUnit *cUnit, BasicBlock *bb) +bool dvmCompilerDoConstantPropagation(CompilationUnit *cUnit, BasicBlock *bb) { MIR *mir; BitVector *isConstantV = cUnit->isConstantV; @@ -1230,9 +1409,10 @@ void dvmCompilerDoConstantPropagation(CompilationUnit *cUnit, BasicBlock *bb) } } /* TODO: implement code to handle arithmetic operations */ + return true; } -void dvmCompilerFindInductionVariables(struct CompilationUnit *cUnit, +bool dvmCompilerFindInductionVariables(struct CompilationUnit *cUnit, struct BasicBlock *bb) { BitVector *isIndVarV = cUnit->loopAnalysis->isIndVarV; @@ -1242,13 +1422,13 @@ void dvmCompilerFindInductionVariables(struct CompilationUnit *cUnit, if (bb->blockType != kDalvikByteCode && bb->blockType != kTraceEntryBlock) { - return; + return false; } /* If the bb doesn't have a phi it cannot contain an induction variable */ if (bb->firstMIRInsn == NULL || bb->firstMIRInsn->dalvikInsn.opcode != kMirOpPhi) { - return; + return false; } /* Find basic induction variable first */ @@ -1299,7 +1479,7 @@ void dvmCompilerFindInductionVariables(struct CompilationUnit *cUnit, } if (deltaIsConstant) { dvmSetBit(isIndVarV, mir->ssaRep->uses[0]); - InductionVariableInfo *ivInfo = + InductionVariableInfo *ivInfo = (InductionVariableInfo *) dvmCompilerNew(sizeof(InductionVariableInfo), false); @@ -1308,7 +1488,7 @@ void dvmCompilerFindInductionVariables(struct CompilationUnit *cUnit, ivInfo->m = 1; // always 1 to basic iv ivInfo->c = 0; // N/A to basic iv ivInfo->inc = deltaValue; - dvmInsertGrowableList(ivList, (void *) ivInfo); + dvmInsertGrowableList(ivList, (intptr_t) ivInfo); cUnit->loopAnalysis->numBasicIV++; break; } @@ -1372,13 +1552,13 @@ void dvmCompilerFindInductionVariables(struct CompilationUnit *cUnit, if (cIsConstant) { unsigned int i; dvmSetBit(isIndVarV, mir->ssaRep->defs[0]); - InductionVariableInfo *ivInfo = + InductionVariableInfo *ivInfo = (InductionVariableInfo *) dvmCompilerNew(sizeof(InductionVariableInfo), false); InductionVariableInfo *ivInfoOld = NULL ; for (i = 0; i < ivList->numUsed; i++) { - ivInfoOld = ivList->elemList[i]; + ivInfoOld = (InductionVariableInfo *) ivList->elemList[i]; if (ivInfoOld->ssaReg == mir->ssaRep->uses[0]) break; } @@ -1390,10 +1570,11 @@ void dvmCompilerFindInductionVariables(struct CompilationUnit *cUnit, ivInfo->m = ivInfoOld->m; ivInfo->c = c + ivInfoOld->c; ivInfo->inc = ivInfoOld->inc; - dvmInsertGrowableList(ivList, (void *) ivInfo); + dvmInsertGrowableList(ivList, (intptr_t) ivInfo); } } } + return true; } /* Setup the basic data structures for SSA conversion */ @@ -1402,7 +1583,8 @@ void dvmInitializeSSAConversion(CompilationUnit *cUnit) int i; int numDalvikReg = cUnit->method->registersSize; - cUnit->ssaToDalvikMap = dvmCompilerNew(sizeof(GrowableList), false); + cUnit->ssaToDalvikMap = (GrowableList *)dvmCompilerNew(sizeof(GrowableList), + false); dvmInitGrowableList(cUnit->ssaToDalvikMap, numDalvikReg); /* @@ -1417,8 +1599,7 @@ void dvmInitializeSSAConversion(CompilationUnit *cUnit) * into "(0 << 16) | i" */ for (i = 0; i < numDalvikReg; i++) { - dvmInsertGrowableList(cUnit->ssaToDalvikMap, - (void *) ENCODE_REG_SUB(i, 0)); + dvmInsertGrowableList(cUnit->ssaToDalvikMap, ENCODE_REG_SUB(i, 0)); } /* @@ -1426,7 +1607,8 @@ void dvmInitializeSSAConversion(CompilationUnit *cUnit) * while the high 16 bit is the current subscript. The original Dalvik * register N is mapped to SSA register N with subscript 0. */ - cUnit->dalvikToSSAMap = dvmCompilerNew(sizeof(int) * numDalvikReg, false); + cUnit->dalvikToSSAMap = (int *)dvmCompilerNew(sizeof(int) * numDalvikReg, + false); for (i = 0; i < numDalvikReg; i++) { cUnit->dalvikToSSAMap[i] = i; } @@ -1434,27 +1616,127 @@ void dvmInitializeSSAConversion(CompilationUnit *cUnit) /* * Allocate the BasicBlockDataFlow structure for the entry and code blocks */ - for (i = 0; i < cUnit->numBlocks; i++) { - BasicBlock *bb = cUnit->blockList[i]; + GrowableListIterator iterator; + + dvmGrowableListIteratorInit(&cUnit->blockList, &iterator); + + while (true) { + BasicBlock *bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator); + if (bb == NULL) break; if (bb->blockType == kDalvikByteCode || - bb->blockType == kTraceEntryBlock) { - bb->dataFlowInfo = dvmCompilerNew(sizeof(BasicBlockDataFlow), true); + bb->blockType == kTraceEntryBlock || + bb->blockType == kMethodEntryBlock || + bb->blockType == kMethodExitBlock) { + bb->dataFlowInfo = (BasicBlockDataFlow *) + dvmCompilerNew(sizeof(BasicBlockDataFlow), + true); } } } +/* Clear the visited flag for each BB */ +bool dvmCompilerClearVisitedFlag(struct CompilationUnit *cUnit, + struct BasicBlock *bb) +{ + bb->visited = false; + return true; +} + void dvmCompilerDataFlowAnalysisDispatcher(CompilationUnit *cUnit, - void (*func)(CompilationUnit *, BasicBlock *)) + bool (*func)(CompilationUnit *, BasicBlock *), + DataFlowAnalysisMode dfaMode, + bool isIterative) { - int i; - for (i = 0; i < cUnit->numBlocks; i++) { - BasicBlock *bb = cUnit->blockList[i]; - (*func)(cUnit, bb); + bool change = true; + + while (change) { + change = false; + + /* Scan all blocks and perform the operations specified in func */ + if (dfaMode == kAllNodes) { + GrowableListIterator iterator; + dvmGrowableListIteratorInit(&cUnit->blockList, &iterator); + while (true) { + BasicBlock *bb = + (BasicBlock *) dvmGrowableListIteratorNext(&iterator); + if (bb == NULL) break; + change |= (*func)(cUnit, bb); + } + } + /* + * Scan all reachable blocks and perform the operations specified in + * func. + */ + else if (dfaMode == kReachableNodes) { + 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); + change |= (*func)(cUnit, bb); + } + } + /* + * Scan all reachable blocks by the pre-order in the depth-first-search + * CFG and perform the operations specified in func. + */ + else if (dfaMode == kPreOrderDFSTraversal) { + int numReachableBlocks = cUnit->numReachableBlocks; + int idx; + const GrowableList *blockList = &cUnit->blockList; + + for (idx = 0; idx < numReachableBlocks; idx++) { + int dfsIdx = cUnit->dfsOrder.elemList[idx]; + BasicBlock *bb = + (BasicBlock *) dvmGrowableListGetElement(blockList, dfsIdx); + change |= (*func)(cUnit, bb); + } + } + /* + * Scan all reachable blocks by the post-order in the depth-first-search + * CFG and perform the operations specified in func. + */ + else if (dfaMode == kPostOrderDFSTraversal) { + int numReachableBlocks = cUnit->numReachableBlocks; + int idx; + const GrowableList *blockList = &cUnit->blockList; + + for (idx = numReachableBlocks - 1; idx >= 0; idx--) { + int dfsIdx = cUnit->dfsOrder.elemList[idx]; + BasicBlock *bb = + (BasicBlock *) dvmGrowableListGetElement(blockList, dfsIdx); + change |= (*func)(cUnit, bb); + } + } + /* + * Scan all reachable blocks by the post-order in the dominator tree + * and perform the operations specified in func. + */ + else if (dfaMode == kPostOrderDOMTraversal) { + int numReachableBlocks = cUnit->numReachableBlocks; + int idx; + const GrowableList *blockList = &cUnit->blockList; + + for (idx = 0; idx < numReachableBlocks; idx++) { + int domIdx = cUnit->domPostOrderTraversal.elemList[idx]; + BasicBlock *bb = + (BasicBlock *) dvmGrowableListGetElement(blockList, domIdx); + change |= (*func)(cUnit, bb); + } + } + /* If isIterative is false, exit the loop after the first iteration */ + change &= isIterative; } } /* Main entry point to do SSA conversion for non-loop traces */ void dvmCompilerNonLoopAnalysis(CompilationUnit *cUnit) { - dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerDoSSAConversion); + dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerDoSSAConversion, + kAllNodes, + false /* isIterative */); } diff --git a/vm/compiler/Frontend.c b/vm/compiler/Frontend.c index a44c4894e..95ef026c0 100644 --- a/vm/compiler/Frontend.c +++ b/vm/compiler/Frontend.c @@ -16,36 +16,42 @@ #include "Dalvik.h" #include "libdex/DexOpcodes.h" +#include "libdex/DexCatch.h" #include "interp/Jit.h" #include "CompilerInternals.h" #include "Dataflow.h" +static inline bool contentIsInsn(const u2 *codePtr) { + u2 instr = *codePtr; + Opcode opcode = instr & 0xff; + + /* + * Since the low 8-bit in metadata may look like OP_NOP, we need to check + * both the low and whole sub-word to determine whether it is code or data. + */ + return (opcode != OP_NOP || instr == 0); +} + /* * Parse an instruction, return the length of the instruction */ static inline int parseInsn(const u2 *codePtr, DecodedInstruction *decInsn, bool printMe) { - u2 instr = *codePtr; - Opcode opcode = dexOpcodeFromCodeUnit(instr); - int insnWidth; - // Don't parse instruction data - if (opcode == OP_NOP && instr != 0) { + if (!contentIsInsn(codePtr)) { return 0; - } else { - insnWidth = dexGetWidthFromOpcode(opcode); - if (insnWidth < 0) { - insnWidth = -insnWidth; - } } + u2 instr = *codePtr; + Opcode opcode = dexOpcodeFromCodeUnit(instr); + dexDecodeInstruction(codePtr, decInsn); if (printMe) { char *decodedString = dvmCompilerGetDalvikDisassembly(decInsn, NULL); LOGD("%p: %#06x %s\n", codePtr, opcode, decodedString); } - return insnWidth; + return dexGetWidthFromOpcode(opcode); } #define UNKNOWN_TARGET 0xffffffff @@ -277,10 +283,11 @@ CompilerMethodStats *dvmCompilerAnalyzeMethodBody(const Method *method, /* For lookup only */ dummyMethodEntry.method = method; - realMethodEntry = dvmHashTableLookup(gDvmJit.methodStatsTable, hashValue, - &dummyMethodEntry, - (HashCompareFunc) compareMethod, - false); + realMethodEntry = + (CompilerMethodStats *) dvmHashTableLookup(gDvmJit.methodStatsTable, hashValue, + &dummyMethodEntry, + (HashCompareFunc) compareMethod, + false); /* This method has never been analyzed before - create an entry */ if (realMethodEntry == NULL) { @@ -418,10 +425,11 @@ bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, const u2 *codePtr = dexCode->insns + curOffset; int traceSize = 0; // # of half-words const u2 *startCodePtr = codePtr; - BasicBlock *startBB, *curBB, *lastBB; + BasicBlock *curBB, *entryCodeBB; int numBlocks = 0; static int compilationId; CompilationUnit cUnit; + GrowableList *blockList; #if defined(WITH_JIT_TUNING) CompilerMethodStats *methodStats; #endif @@ -459,11 +467,15 @@ bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, /* Initialize the PC reconstruction list */ dvmInitGrowableList(&cUnit.pcReconstructionList, 8); + /* Initialize the basic block list */ + blockList = &cUnit.blockList; + dvmInitGrowableList(blockList, 8); + /* Identify traces that we don't want to compile */ if (gDvmJit.methodTable) { int len = strlen(desc->method->clazz->descriptor) + strlen(desc->method->name) + 1; - char *fullSignature = dvmCompilerNew(len, true); + char *fullSignature = (char *)dvmCompilerNew(len, true); strcpy(fullSignature, desc->method->clazz->descriptor); strcat(fullSignature, desc->method->name); @@ -533,18 +545,15 @@ bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, } /* Allocate the entry block */ - lastBB = startBB = curBB = dvmCompilerNewBB(kTraceEntryBlock); - curBB->startOffset = curOffset; - curBB->id = numBlocks++; - - curBB = dvmCompilerNewBB(kDalvikByteCode); + curBB = dvmCompilerNewBB(kTraceEntryBlock, numBlocks++); + dvmInsertGrowableList(blockList, (intptr_t) curBB); curBB->startOffset = curOffset; - curBB->id = numBlocks++; - /* Make the first real dalvik block the fallthrough of the entry block */ - startBB->fallThrough = curBB; - lastBB->next = curBB; - lastBB = curBB; + entryCodeBB = dvmCompilerNewBB(kDalvikByteCode, numBlocks++); + dvmInsertGrowableList(blockList, (intptr_t) entryCodeBB); + entryCodeBB->startOffset = curOffset; + curBB->fallThrough = entryCodeBB; + curBB = entryCodeBB; if (cUnit.printMe) { LOGD("--------\nCompiler: Building trace for %s, offset 0x%x\n", @@ -558,7 +567,7 @@ bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, while (1) { MIR *insn; int width; - insn = dvmCompilerNew(sizeof(MIR), true); + insn = (MIR *)dvmCompilerNew(sizeof(MIR), true); insn->offset = curOffset; width = parseInsn(codePtr, &insn->dalvikInsn, cUnit.printMe); @@ -574,9 +583,9 @@ bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, if (flags & kInstrInvoke) { assert(numInsts == 1); CallsiteInfo *callsiteInfo = - dvmCompilerNew(sizeof(CallsiteInfo), true); - callsiteInfo->clazz = currRun[1].meta; - callsiteInfo->method = currRun[2].meta; + (CallsiteInfo *)dvmCompilerNew(sizeof(CallsiteInfo), true); + callsiteInfo->clazz = (ClassObject *)currRun[1].meta; + callsiteInfo->method = (Method *)currRun[2].meta; insn->meta.callsiteInfo = callsiteInfo; } @@ -598,10 +607,8 @@ bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, break; } - curBB = dvmCompilerNewBB(kDalvikByteCode); - lastBB->next = curBB; - lastBB = curBB; - curBB->id = numBlocks++; + curBB = dvmCompilerNewBB(kDalvikByteCode, numBlocks++); + dvmInsertGrowableList(blockList, (intptr_t) curBB); curOffset = currRun->frag.startOffset; numInsts = currRun->frag.numInsts; curBB->startOffset = curOffset; @@ -623,7 +630,9 @@ bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, * taken/fallthrough links. Also create chaining cells for code not included * in the trace. */ - for (curBB = startBB; curBB; curBB = curBB->next) { + size_t blockId; + for (blockId = 0; blockId < blockList->numUsed; blockId++) { + curBB = (BasicBlock *) dvmGrowableListGetElement(blockList, blockId); MIR *lastInsn = curBB->lastMIRInsn; /* Skip empty blocks */ if (lastInsn == NULL) { @@ -648,7 +657,11 @@ bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, } /* No backward branch in the trace - start searching the next BB */ - for (searchBB = curBB->next; searchBB; searchBB = searchBB->next) { + size_t searchBlockId; + for (searchBlockId = blockId+1; searchBlockId < blockList->numUsed; + searchBlockId++) { + searchBB = (BasicBlock *) dvmGrowableListGetElement(blockList, + searchBlockId); if (targetOffset == searchBB->startOffset) { curBB->taken = searchBB; } @@ -680,7 +693,7 @@ bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, if (curBB->taken == NULL && curBB->fallThrough == NULL && flags == (kInstrCanBranch | kInstrCanContinue) && - fallThroughOffset == startBB->startOffset && + fallThroughOffset == entryCodeBB->startOffset && JIT_OPT_NO_LOOP != (optHints & JIT_OPT_NO_LOOP)) { BasicBlock *loopBranch = curBB; BasicBlock *exitBB; @@ -689,48 +702,37 @@ bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, if (cUnit.printMe) { LOGD("Natural loop detected!"); } - exitBB = dvmCompilerNewBB(kTraceExitBlock); - lastBB->next = exitBB; - lastBB = exitBB; - + exitBB = dvmCompilerNewBB(kTraceExitBlock, numBlocks++); + dvmInsertGrowableList(blockList, (intptr_t) exitBB); exitBB->startOffset = targetOffset; - exitBB->id = numBlocks++; exitBB->needFallThroughBranch = true; loopBranch->taken = exitBB; #if defined(WITH_SELF_VERIFICATION) BasicBlock *backwardCell = - dvmCompilerNewBB(kChainingCellBackwardBranch); - lastBB->next = backwardCell; - lastBB = backwardCell; - - backwardCell->startOffset = startBB->startOffset; - backwardCell->id = numBlocks++; + dvmCompilerNewBB(kChainingCellBackwardBranch, numBlocks++); + dvmInsertGrowableList(blockList, (intptr_t) backwardCell); + backwardCell->startOffset = entryCodeBB->startOffset; loopBranch->fallThrough = backwardCell; #elif defined(WITH_JIT_TUNING) if (gDvmJit.profile) { BasicBlock *backwardCell = - dvmCompilerNewBB(kChainingCellBackwardBranch); - lastBB->next = backwardCell; - lastBB = backwardCell; - - backwardCell->startOffset = startBB->startOffset; - backwardCell->id = numBlocks++; + dvmCompilerNewBB(kChainingCellBackwardBranch, numBlocks++); + dvmInsertGrowableList(blockList, (intptr_t) backwardCell); + backwardCell->startOffset = entryCodeBB->startOffset; loopBranch->fallThrough = backwardCell; } else { - loopBranch->fallThrough = startBB->next; + loopBranch->fallThrough = entryCodeBB; } #else - loopBranch->fallThrough = startBB->next; + loopBranch->fallThrough = entryCodeBB; #endif /* Create the chaining cell as the fallthrough of the exit block */ - exitChainingCell = dvmCompilerNewBB(kChainingCellNormal); - lastBB->next = exitChainingCell; - lastBB = exitChainingCell; - + exitChainingCell = dvmCompilerNewBB(kChainingCellNormal, + numBlocks++); + dvmInsertGrowableList(blockList, (intptr_t) exitChainingCell); exitChainingCell->startOffset = targetOffset; - exitChainingCell->id = numBlocks++; exitBB->fallThrough = exitChainingCell; @@ -761,38 +763,35 @@ bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, /* One chaining cell for the first MAX_CHAINED_SWITCH_CASES cases */ for (i = 0; i < maxChains; i++) { - BasicBlock *caseChain = dvmCompilerNewBB(kChainingCellNormal); - lastBB->next = caseChain; - lastBB = caseChain; - + BasicBlock *caseChain = dvmCompilerNewBB(kChainingCellNormal, + numBlocks++); + dvmInsertGrowableList(blockList, (intptr_t) caseChain); caseChain->startOffset = lastInsn->offset + targets[i]; - caseChain->id = numBlocks++; } /* One more chaining cell for the default case */ - BasicBlock *caseChain = dvmCompilerNewBB(kChainingCellNormal); - lastBB->next = caseChain; - lastBB = caseChain; - + BasicBlock *caseChain = dvmCompilerNewBB(kChainingCellNormal, + numBlocks++); + dvmInsertGrowableList(blockList, (intptr_t) caseChain); caseChain->startOffset = lastInsn->offset + lastInsn->width; - caseChain->id = numBlocks++; /* Fallthrough block not included in the trace */ } else if (!isUnconditionalBranch(lastInsn) && curBB->fallThrough == NULL) { + BasicBlock *fallThroughBB; /* * If the chaining cell is after an invoke or * instruction that cannot change the control flow, request a hot * chaining cell. */ if (isInvoke || curBB->needFallThroughBranch) { - lastBB->next = dvmCompilerNewBB(kChainingCellHot); + fallThroughBB = dvmCompilerNewBB(kChainingCellHot, numBlocks++); } else { - lastBB->next = dvmCompilerNewBB(kChainingCellNormal); + fallThroughBB = dvmCompilerNewBB(kChainingCellNormal, + numBlocks++); } - lastBB = lastBB->next; - lastBB->id = numBlocks++; - lastBB->startOffset = fallThroughOffset; - curBB->fallThrough = lastBB; + dvmInsertGrowableList(blockList, (intptr_t) fallThroughBB); + fallThroughBB->startOffset = fallThroughOffset; + curBB->fallThrough = fallThroughBB; } /* Target block not included in the trace */ if (curBB->taken == NULL && @@ -802,12 +801,14 @@ bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, if (isInvoke) { /* Monomorphic callee */ if (callee) { - newBB = dvmCompilerNewBB(kChainingCellInvokeSingleton); + newBB = dvmCompilerNewBB(kChainingCellInvokeSingleton, + numBlocks++); newBB->startOffset = 0; newBB->containingMethod = callee; /* Will resolve at runtime */ } else { - newBB = dvmCompilerNewBB(kChainingCellInvokePredicted); + newBB = dvmCompilerNewBB(kChainingCellInvokePredicted, + numBlocks++); newBB->startOffset = 0; } /* For unconditional branches, request a hot chaining cell */ @@ -815,40 +816,40 @@ bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, #if !defined(WITH_SELF_VERIFICATION) newBB = dvmCompilerNewBB(dexIsGoto(flags) ? kChainingCellHot : - kChainingCellNormal); + kChainingCellNormal, + numBlocks++); newBB->startOffset = targetOffset; #else /* Handle branches that branch back into the block */ if (targetOffset >= curBB->firstMIRInsn->offset && targetOffset <= curBB->lastMIRInsn->offset) { - newBB = dvmCompilerNewBB(kChainingCellBackwardBranch); + newBB = dvmCompilerNewBB(kChainingCellBackwardBranch, + numBlocks++); } else { newBB = dvmCompilerNewBB(dexIsGoto(flags) ? kChainingCellHot : - kChainingCellNormal); + kChainingCellNormal, + numBlocks++); } newBB->startOffset = targetOffset; #endif } - newBB->id = numBlocks++; curBB->taken = newBB; - lastBB->next = newBB; - lastBB = newBB; + dvmInsertGrowableList(blockList, (intptr_t) newBB); } } /* Now create a special block to host PC reconstruction code */ - lastBB->next = dvmCompilerNewBB(kPCReconstruction); - lastBB = lastBB->next; - lastBB->id = numBlocks++; + curBB = dvmCompilerNewBB(kPCReconstruction, numBlocks++); + dvmInsertGrowableList(blockList, (intptr_t) curBB); /* And one final block that publishes the PC and raise the exception */ - lastBB->next = dvmCompilerNewBB(kExceptionHandling); - lastBB = lastBB->next; - lastBB->id = numBlocks++; + curBB = dvmCompilerNewBB(kExceptionHandling, numBlocks++); + dvmInsertGrowableList(blockList, (intptr_t) curBB); if (cUnit.printMe) { - char* signature = dexProtoCopyMethodDescriptor(&desc->method->prototype); + char* signature = + dexProtoCopyMethodDescriptor(&desc->method->prototype); LOGD("TRACEINFO (%d): 0x%08x %s%s.%s 0x%x %d of %d, %d blocks", compilationId, (intptr_t) desc->method->insns, @@ -862,21 +863,8 @@ bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, free(signature); } - BasicBlock **blockList; - cUnit.traceDesc = desc; cUnit.numBlocks = numBlocks; - blockList = cUnit.blockList = - dvmCompilerNew(sizeof(BasicBlock *) * numBlocks, true); - - int i; - - for (i = 0, curBB = startBB; i < numBlocks; i++) { - blockList[i] = curBB; - curBB = curBB->next; - } - /* Make sure all blocks are added to the cUnit */ - assert(curBB == NULL); /* Set the instruction set to use (NOTE: later components may change it) */ cUnit.instructionSet = dvmCompilerInstructionSet(); @@ -886,6 +874,8 @@ bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, dvmCompilerInlineMIR(&cUnit); } + cUnit.numDalvikRegisters = cUnit.method->registersSize; + /* Preparation for SSA conversion */ dvmInitializeSSAConversion(&cUnit); @@ -916,8 +906,8 @@ bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, dvmCompilerDumpCompilationUnit(&cUnit); } - /* Allocate Registers */ - dvmCompilerRegAlloc(&cUnit); + /* Allocate Registers using simple local allocation scheme */ + dvmCompilerLocalRegAlloc(&cUnit); /* Convert MIR to LIR, etc. */ dvmCompilerMIR2LIR(&cUnit); @@ -951,6 +941,15 @@ bool dvmCompileTrace(JitTraceDescription *desc, int numMaxInsts, #if defined(WITH_JIT_TUNING) methodStats->nativeSize += cUnit.totalSize; #endif + + /* FIXME - to exercise the method parser, uncomment the following code */ +#if 0 + bool dvmCompileMethod(const Method *method); + if (desc->trace[0].frag.startOffset == 0) { + dvmCompileMethod(desc->method); + } +#endif + return info->codeAddress != NULL; } @@ -968,7 +967,7 @@ bool dvmCompilerCanIncludeThisInstruction(const Method *method, switch (insn->opcode) { case OP_NEW_INSTANCE: case OP_CHECK_CAST: { - ClassObject *classPtr = (void*) + ClassObject *classPtr = (ClassObject *)(void*) (method->clazz->pDvmDex->pResClasses[insn->vB]); /* Class hasn't been initialized yet */ @@ -1052,255 +1051,742 @@ bool dvmCompilerCanIncludeThisInstruction(const Method *method, } } -/* - * 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(CompilationUnit *cUnit, const Method *method, - JitTranslationInfo *info) +/* Split an existing block from the specified code offset into two */ +static BasicBlock *splitBlock(CompilationUnit *cUnit, + unsigned int codeOffset, + BasicBlock *origBlock) { - const DexCode *dexCode = dvmGetMethodCode(method); - const u2 *codePtr = dexCode->insns; - const u2 *codeEnd = dexCode->insns + dexCode->insnsSize; - int blockID = 0; - unsigned int curOffset = 0; + 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); + } - /* If we've already compiled this trace, just return success */ - if (dvmJitGetCodeAddr(codePtr) && !info->discardResult) { - return true; + /* 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); + } } - /* Doing method-based compilation */ - cUnit->wholeMethod = true; + origBlock->lastMIRInsn = insn->prev; - BasicBlock *firstBlock = dvmCompilerNewBB(kDalvikByteCode); - firstBlock->id = blockID++; + insn->prev->next = NULL; + insn->prev = NULL; + return bottomBlock; +} - /* Allocate the bit-vector to track the beginning of basic blocks */ - BitVector *bbStartAddr = dvmCompilerAllocBitVector(dexCode->insnsSize+1, - false); - dvmCompilerSetBit(bbStartAddr, 0); +/* + * 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; +} - int numInvokeTargets = 0; +/* 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); /* - * Sequentially go through every instruction first and put them in a single - * basic block. Identify block boundaries at the mean time. + * Convert the special characters into a filesystem- and shell-friendly + * format. */ - while (codePtr < codeEnd) { - MIR *insn = dvmCompilerNew(sizeof(MIR), true); - insn->offset = curOffset; - int width = parseInsn(codePtr, &insn->dalvikInsn, false); - bool isInvoke = false; - const Method *callee; - insn->width = width; + 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]; - /* Terminate when the data section is seen */ - if (width == 0) - break; + dvmGetBlockName(bb, blockName); + fprintf(file, " %s [shape=invhouse];\n", blockName); + } - if (!dvmCompilerCanIncludeThisInstruction(cUnit->method, - &insn->dalvikInsn)) { - return false; + 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); } - dvmCompilerAppendMIR(firstBlock, insn); - /* - * Check whether this is a block ending instruction and whether it - * suggests the start of a new block - */ - unsigned int target = curOffset; + 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 findBlockBoundary returns true, it means the current instruction - * is terminating the current block. If it is a branch, the target - * address will be recorded in target. + * If we need to debug the dominator tree, uncomment the following code */ - if (findBlockBoundary(method, insn, curOffset, &target, &isInvoke, - &callee)) { - dvmCompilerSetBit(bbStartAddr, curOffset + width); - /* Each invoke needs a chaining cell block */ - if (isInvoke) { - numInvokeTargets++; - } - /* A branch will end the current block */ - else if (target != curOffset && target != UNKNOWN_TARGET) { - dvmCompilerSetBit(bbStartAddr, target); +#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; +} - codePtr += width; - /* each bit represents 16-bit quantity */ - curOffset += width; +/* 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; } - /* - * The number of blocks will be equal to the number of bits set to 1 in the - * bit vector minus 1, because the bit representing the location after the - * last instruction is set to one. - * - * We also add additional blocks for invoke chaining and the number is - * denoted by numInvokeTargets. - */ - int numBlocks = dvmCountSetBits(bbStartAddr); - if (dvmIsBitSet(bbStartAddr, dexCode->insnsSize)) { - numBlocks--; + 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); + } } - BasicBlock **blockList; - blockList = cUnit->blockList = - dvmCompilerNew(sizeof(BasicBlock *) * (numBlocks + numInvokeTargets), - true); + /* Iterate over each of the handlers to enqueue the empty Catch blocks */ + offset = dexGetFirstHandlerOffset(pCode); + int handlersSize = dexGetHandlersSize(pCode); - /* - * Register the first block onto the list and start splitting it into - * sub-blocks. - */ - blockList[0] = firstBlock; - cUnit->numBlocks = 1; + for (i = 0; i < handlersSize; i++) { + DexCatchIterator iterator; + dexCatchIteratorInit(&iterator, pCode, offset); - int i; - for (i = 0; i < numBlocks; i++) { - MIR *insn; - BasicBlock *curBB = blockList[i]; - curOffset = curBB->lastMIRInsn->offset; - - for (insn = curBB->firstMIRInsn->next; insn; insn = insn->next) { - /* Found the beginning of a new block, see if it is created yet */ - if (dvmIsBitSet(bbStartAddr, insn->offset)) { - int j; - for (j = 0; j < cUnit->numBlocks; j++) { - if (blockList[j]->firstMIRInsn->offset == insn->offset) - break; - } + for (;;) { + DexCatchHandler* handler = dexCatchIteratorNext(&iterator); - /* Block not split yet - do it now */ - if (j == cUnit->numBlocks) { - BasicBlock *newBB = dvmCompilerNewBB(kDalvikByteCode); - newBB->id = blockID++; - newBB->firstMIRInsn = insn; - newBB->startOffset = insn->offset; - newBB->lastMIRInsn = curBB->lastMIRInsn; - curBB->lastMIRInsn = insn->prev; - insn->prev->next = NULL; - insn->prev = NULL; - - /* - * If the insn is not an unconditional branch, set up the - * fallthrough link. - */ - if (!isUnconditionalBranch(curBB->lastMIRInsn)) { - curBB->fallThrough = newBB; - } - - /* - * Fallthrough block of an invoke instruction needs to be - * aligned to 4-byte boundary (alignment instruction to be - * inserted later. - */ - if (dexGetFlagsFromOpcode(curBB->lastMIRInsn->dalvikInsn.opcode) - & kInstrInvoke) { - newBB->isFallThroughFromInvoke = true; - } - - /* enqueue the new block */ - blockList[cUnit->numBlocks++] = newBB; - break; - } + 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); } +} - if (numBlocks != cUnit->numBlocks) { - LOGE("Expect %d vs %d basic blocks\n", numBlocks, cUnit->numBlocks); - dvmCompilerAbort(cUnit); +/* 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); + } } +} - /* Connect the basic blocks through the taken links */ - for (i = 0; i < numBlocks; i++) { - BasicBlock *curBB = blockList[i]; - MIR *insn = curBB->lastMIRInsn; - unsigned int target = insn->offset; - bool isInvoke = false; - const Method *callee = NULL; +/* 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; - findBlockBoundary(method, insn, target, &target, &isInvoke, &callee); + /* + * 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 + } - /* Found a block ended on a branch (not invoke) */ - if (isInvoke == false && target != insn->offset) { - int j; - /* Forward branch */ - if (target > insn->offset) { - j = i + 1; - } else { - /* Backward branch */ - j = 0; - } - for (; j < numBlocks; j++) { - if (blockList[j]->firstMIRInsn->offset == target) { - curBB->taken = blockList[j]; - break; - } - } + 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); - if (isInvoke) { - BasicBlock *newBB; - /* Monomorphic callee */ - if (callee) { - newBB = dvmCompilerNewBB(kChainingCellInvokeSingleton); - newBB->startOffset = 0; - newBB->containingMethod = callee; - /* Will resolve at runtime */ - } else { - newBB = dvmCompilerNewBB(kChainingCellInvokePredicted); - newBB->startOffset = 0; + for (;;) { + DexCatchHandler* handler = dexCatchIteratorNext(&iterator); + + if (handler == NULL) { + break; } - newBB->id = blockID++; - curBB->taken = newBB; - /* enqueue the new block */ - blockList[cUnit->numBlocks++] = newBB; + + 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); } - if (cUnit->numBlocks != numBlocks + numInvokeTargets) { - LOGE("Expect %d vs %d total blocks\n", numBlocks + numInvokeTargets, - cUnit->numBlocks); - dvmCompilerDumpCompilationUnit(cUnit); - dvmCompilerAbort(cUnit); + /* + * 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); + } + } } +} - /* Set the instruction set to use (NOTE: later components may change it) */ - cUnit->instructionSet = dvmCompilerInstructionSet(); +/* + * 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) +{ + 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; - /* Preparation for SSA conversion */ - dvmInitializeSSAConversion(cUnit); + memset(&cUnit, 0, sizeof(cUnit)); + cUnit.method = method; + + /* Initialize the block list */ + dvmInitGrowableList(&cUnit.blockList, 4); - /* SSA analysis */ - dvmCompilerNonLoopAnalysis(cUnit); + /* Allocate the bit-vector to track the beginning of basic blocks */ + BitVector *tryBlockAddr = dvmCompilerAllocBitVector(dexCode->insnsSize, + true /* expandable */); + cUnit.tryBlockAddr = tryBlockAddr; - /* Needs to happen after SSA naming */ - dvmCompilerInitializeRegAlloc(cUnit); + /* Create the default entry and exit blocks and enter them to the list */ + BasicBlock *entryBlock = dvmCompilerNewBB(kMethodEntryBlock, numBlocks++); + BasicBlock *exitBlock = dvmCompilerNewBB(kMethodExitBlock, numBlocks++); - /* Allocate Registers */ - dvmCompilerRegAlloc(cUnit); + cUnit.entryBlock = entryBlock; + cUnit.exitBlock = exitBlock; - /* Convert MIR to LIR, etc. */ - dvmCompilerMIR2LIR(cUnit); + 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; - /* Convert LIR into machine code. */ - dvmCompilerAssembleLIR(cUnit, info); + /* Identify code range in try blocks and set up the empty catch blocks */ + processTryCatchBlocks(&cUnit); - if (cUnit->assemblerStatus != kSuccess) { - return false; + /* 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) && + !dexIsGoto(flags) && + !(flags & kInstrCanReturn)) { + curBlock->fallThrough = nextBlock; + dvmCompilerSetBit(nextBlock->predecessors, curBlock->id); + } + curBlock = nextBlock; + } } - 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); + + if (cUnit.printMe) dumpCFG(&cUnit, "/data/tombstones/"); + + /* Reset the compiler resource pool */ dvmCompilerArenaReset(); - return info->codeAddress != NULL; + return false; } diff --git a/vm/compiler/InlineTransformation.c b/vm/compiler/InlineTransformation.c index 0b1330f16..2cdba18cd 100644 --- a/vm/compiler/InlineTransformation.c +++ b/vm/compiler/InlineTransformation.c @@ -43,7 +43,7 @@ static void inlineGetter(CompilationUnit *cUnit, { BasicBlock *moveResultBB = invokeBB->fallThrough; MIR *moveResultMIR = moveResultBB->firstMIRInsn; - MIR *newGetterMIR = dvmCompilerNew(sizeof(MIR), true); + MIR *newGetterMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); DecodedInstruction getterInsn; dexDecodeInstruction(calleeMethod->insns, &getterInsn); @@ -100,7 +100,7 @@ static void inlineGetter(CompilationUnit *cUnit, dvmCompilerInsertMIRAfter(invokeBB, invokeMIR, newGetterMIR); if (isPredicted) { - MIR *invokeMIRSlow = dvmCompilerNew(sizeof(MIR), true); + MIR *invokeMIRSlow = (MIR *)dvmCompilerNew(sizeof(MIR), true); *invokeMIRSlow = *invokeMIR; invokeMIR->dalvikInsn.opcode = kMirOpCheckInlinePrediction; @@ -134,7 +134,7 @@ static void inlineSetter(CompilationUnit *cUnit, bool isPredicted, bool isRange) { - MIR *newSetterMIR = dvmCompilerNew(sizeof(MIR), true); + MIR *newSetterMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); DecodedInstruction setterInsn; dexDecodeInstruction(calleeMethod->insns, &setterInsn); @@ -179,7 +179,7 @@ static void inlineSetter(CompilationUnit *cUnit, dvmCompilerInsertMIRAfter(invokeBB, invokeMIR, newSetterMIR); if (isPredicted) { - MIR *invokeMIRSlow = dvmCompilerNew(sizeof(MIR), true); + MIR *invokeMIRSlow = (MIR *)dvmCompilerNew(sizeof(MIR), true); *invokeMIRSlow = *invokeMIR; invokeMIR->dalvikInsn.opcode = kMirOpCheckInlinePrediction; @@ -246,7 +246,7 @@ static void inlineEmptyVirtualCallee(CompilationUnit *cUnit, MIR *invokeMIR, BasicBlock *invokeBB) { - MIR *invokeMIRSlow = dvmCompilerNew(sizeof(MIR), true); + MIR *invokeMIRSlow = (MIR *)dvmCompilerNew(sizeof(MIR), true); *invokeMIRSlow = *invokeMIR; invokeMIR->dalvikInsn.opcode = kMirOpCheckInlinePrediction; @@ -284,14 +284,16 @@ static void tryInlineVirtualCallsite(CompilationUnit *cUnit, void dvmCompilerInlineMIR(CompilationUnit *cUnit) { - int i; bool isRange = false; + GrowableListIterator iterator; + dvmGrowableListIteratorInit(&cUnit->blockList, &iterator); /* * Analyze the basic block containing an invoke to see if it can be inlined */ - for (i = 0; i < cUnit->numBlocks; i++) { - BasicBlock *bb = cUnit->blockList[i]; + while (true) { + BasicBlock *bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator); + if (bb == NULL) break; if (bb->blockType != kDalvikByteCode) continue; MIR *lastMIRInsn = bb->lastMIRInsn; diff --git a/vm/compiler/IntermediateRep.c b/vm/compiler/IntermediateRep.c index 825a69079..db68c3c85 100644 --- a/vm/compiler/IntermediateRep.c +++ b/vm/compiler/IntermediateRep.c @@ -18,10 +18,13 @@ #include "CompilerInternals.h" /* Allocate a new basic block */ -BasicBlock *dvmCompilerNewBB(BBType blockType) +BasicBlock *dvmCompilerNewBB(BBType blockType, int blockId) { - BasicBlock *bb = dvmCompilerNew(sizeof(BasicBlock), true); + BasicBlock *bb = (BasicBlock *)dvmCompilerNew(sizeof(BasicBlock), true); bb->blockType = blockType; + bb->id = blockId; + bb->predecessors = dvmCompilerAllocBitVector(blockId > 32 ? blockId : 32, + true /* expandable */); return bb; } diff --git a/vm/compiler/Loop.c b/vm/compiler/Loop.c index 031464c3c..9ee430d42 100644 --- a/vm/compiler/Loop.c +++ b/vm/compiler/Loop.c @@ -38,18 +38,24 @@ */ static void handlePhiPlacement(CompilationUnit *cUnit) { - BasicBlock *entry = cUnit->blockList[0]; - BasicBlock *loopBody = cUnit->blockList[1]; - BasicBlock *loopBranch = cUnit->blockList[2]; + BasicBlock *entry = + (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 0); + BasicBlock *loopBody = + (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 1); + BasicBlock *loopBranch = + (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 2); dvmCopyBitVector(entry->dataFlowInfo->defV, loopBody->dataFlowInfo->liveInV); BitVector *phiV = dvmCompilerAllocBitVector(cUnit->method->registersSize, false); + BitVector *phi2V = dvmCompilerAllocBitVector(cUnit->method->registersSize, + false); dvmIntersectBitVectors(phiV, entry->dataFlowInfo->defV, loopBody->dataFlowInfo->defV); - dvmIntersectBitVectors(phiV, entry->dataFlowInfo->defV, + dvmIntersectBitVectors(phi2V, entry->dataFlowInfo->defV, loopBranch->dataFlowInfo->defV); + dvmUnifyBitVectors(phiV, phiV, phi2V); /* Insert the PHI MIRs */ int i; @@ -57,7 +63,7 @@ static void handlePhiPlacement(CompilationUnit *cUnit) if (!dvmIsBitSet(phiV, i)) { continue; } - MIR *phi = dvmCompilerNew(sizeof(MIR), true); + MIR *phi = (MIR *)dvmCompilerNew(sizeof(MIR), true); phi->dalvikInsn.opcode = kMirOpPhi; phi->dalvikInsn.vA = i; dvmCompilerPrependMIR(loopBody, phi); @@ -66,9 +72,12 @@ static void handlePhiPlacement(CompilationUnit *cUnit) static void fillPhiNodeContents(CompilationUnit *cUnit) { - BasicBlock *entry = cUnit->blockList[0]; - BasicBlock *loopBody = cUnit->blockList[1]; - BasicBlock *loopBranch = cUnit->blockList[2]; + BasicBlock *entry = + (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 0); + BasicBlock *loopBody = + (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 1); + BasicBlock *loopBranch = + (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 2); MIR *mir; for (mir = loopBody->firstMIRInsn; mir; mir = mir->next) { @@ -76,7 +85,7 @@ static void fillPhiNodeContents(CompilationUnit *cUnit) int dalvikReg = mir->dalvikInsn.vA; mir->ssaRep->numUses = 2; - mir->ssaRep->uses = dvmCompilerNew(sizeof(int) * 2, false); + mir->ssaRep->uses = (int *)dvmCompilerNew(sizeof(int) * 2, false); mir->ssaRep->uses[0] = DECODE_REG(entry->dataFlowInfo->dalvikToSSAMap[dalvikReg]); mir->ssaRep->uses[1] = @@ -165,7 +174,8 @@ static void dumpHoistedChecks(CompilationUnit *cUnit) static bool isLoopOptimizable(CompilationUnit *cUnit) { unsigned int i; - BasicBlock *loopBranch = cUnit->blockList[2]; + BasicBlock *loopBranch = + (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 2); LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; if (loopAnalysis->numBasicIV != 1) return false; @@ -283,13 +293,14 @@ static void updateRangeCheckInfo(CompilationUnit *cUnit, int arrayReg, } if (arrayAccessInfo == NULL) { arrayAccessInfo = - dvmCompilerNew(sizeof(ArrayAccessInfo), false); + (ArrayAccessInfo *)dvmCompilerNew(sizeof(ArrayAccessInfo), + false); arrayAccessInfo->ivReg = ivInfo->basicSSAReg; arrayAccessInfo->arrayReg = arrayReg; arrayAccessInfo->maxC = (ivInfo->c > 0) ? ivInfo->c : 0; arrayAccessInfo->minC = (ivInfo->c < 0) ? ivInfo->c : 0; dvmInsertGrowableList(loopAnalysis->arrayAccessInfo, - arrayAccessInfo); + (intptr_t) arrayAccessInfo); } break; } @@ -299,7 +310,8 @@ static void updateRangeCheckInfo(CompilationUnit *cUnit, int arrayReg, /* Returns true if the loop body cannot throw any exceptions */ static bool doLoopBodyCodeMotion(CompilationUnit *cUnit) { - BasicBlock *loopBody = cUnit->blockList[1]; + BasicBlock *loopBody = + (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 1); MIR *mir; bool loopBodyCanThrow = false; @@ -386,7 +398,8 @@ static bool doLoopBodyCodeMotion(CompilationUnit *cUnit) static void genHoistedChecks(CompilationUnit *cUnit) { unsigned int i; - BasicBlock *entry = cUnit->blockList[0]; + BasicBlock *entry = + (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 0); LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; int globalMaxC = 0; int globalMinC = 0; @@ -402,7 +415,7 @@ static void genHoistedChecks(CompilationUnit *cUnit) idxReg = DECODE_REG( dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->ivReg)); - MIR *rangeCheckMIR = dvmCompilerNew(sizeof(MIR), true); + MIR *rangeCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); rangeCheckMIR->dalvikInsn.opcode = (loopAnalysis->isCountUpLoop) ? kMirOpNullNRangeUpCheck : kMirOpNullNRangeDownCheck; rangeCheckMIR->dalvikInsn.vA = arrayReg; @@ -422,7 +435,7 @@ static void genHoistedChecks(CompilationUnit *cUnit) if (loopAnalysis->arrayAccessInfo->numUsed != 0) { if (loopAnalysis->isCountUpLoop) { - MIR *boundCheckMIR = dvmCompilerNew(sizeof(MIR), true); + MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); boundCheckMIR->dalvikInsn.opcode = kMirOpLowerBound; boundCheckMIR->dalvikInsn.vA = idxReg; boundCheckMIR->dalvikInsn.vB = globalMinC; @@ -430,7 +443,7 @@ static void genHoistedChecks(CompilationUnit *cUnit) } else { if (loopAnalysis->loopBranchOpcode == OP_IF_LT || loopAnalysis->loopBranchOpcode == OP_IF_LE) { - MIR *boundCheckMIR = dvmCompilerNew(sizeof(MIR), true); + MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); boundCheckMIR->dalvikInsn.opcode = kMirOpLowerBound; boundCheckMIR->dalvikInsn.vA = loopAnalysis->endConditionReg; boundCheckMIR->dalvikInsn.vB = globalMinC; @@ -447,14 +460,14 @@ static void genHoistedChecks(CompilationUnit *cUnit) } else if (loopAnalysis->loopBranchOpcode == OP_IF_LTZ) { /* Array index will fall below 0 */ if (globalMinC < 0) { - MIR *boundCheckMIR = dvmCompilerNew(sizeof(MIR), true); + MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); boundCheckMIR->dalvikInsn.opcode = kMirOpPunt; dvmCompilerAppendMIR(entry, boundCheckMIR); } } else if (loopAnalysis->loopBranchOpcode == OP_IF_LEZ) { /* Array index will fall below 0 */ if (globalMinC < -1) { - MIR *boundCheckMIR = dvmCompilerNew(sizeof(MIR), true); + MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); boundCheckMIR->dalvikInsn.opcode = kMirOpPunt; dvmCompilerAppendMIR(entry, boundCheckMIR); } @@ -473,46 +486,61 @@ static void genHoistedChecks(CompilationUnit *cUnit) */ bool dvmCompilerLoopOpt(CompilationUnit *cUnit) { - LoopAnalysis *loopAnalysis = dvmCompilerNew(sizeof(LoopAnalysis), true); + LoopAnalysis *loopAnalysis = + (LoopAnalysis *)dvmCompilerNew(sizeof(LoopAnalysis), true); - assert(cUnit->blockList[0]->blockType == kTraceEntryBlock); - assert(cUnit->blockList[2]->blockType == kDalvikByteCode); - assert(cUnit->blockList[3]->blockType == kTraceExitBlock); + assert(((BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 0)) + ->blockType == kTraceEntryBlock); + assert(((BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 2)) + ->blockType == kDalvikByteCode); + assert(((BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 3)) + ->blockType == kTraceExitBlock); cUnit->loopAnalysis = loopAnalysis; /* * Find live-in variables to the loop body so that we can fake their * definitions in the entry block. */ - dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerFindLiveIn); + dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerFindLocalLiveIn, + kAllNodes, + false /* isIterative */); /* Insert phi nodes to the loop body */ handlePhiPlacement(cUnit); - dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerDoSSAConversion); + dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerDoSSAConversion, + kAllNodes, + false /* isIterative */); fillPhiNodeContents(cUnit); /* Constant propagation */ cUnit->isConstantV = dvmAllocBitVector(cUnit->numSSARegs, false); - cUnit->constantValues = dvmCompilerNew(sizeof(int) * cUnit->numSSARegs, - true); + cUnit->constantValues = + (int *)dvmCompilerNew(sizeof(int) * cUnit->numSSARegs, + true); dvmCompilerDataFlowAnalysisDispatcher(cUnit, - dvmCompilerDoConstantPropagation); + dvmCompilerDoConstantPropagation, + kAllNodes, + false /* isIterative */); DEBUG_LOOP(dumpConstants(cUnit);) /* Find induction variables - basic and dependent */ - loopAnalysis->ivList = dvmCompilerNew(sizeof(GrowableList), true); + loopAnalysis->ivList = + (GrowableList *)dvmCompilerNew(sizeof(GrowableList), true); dvmInitGrowableList(loopAnalysis->ivList, 4); loopAnalysis->isIndVarV = dvmAllocBitVector(cUnit->numSSARegs, false); dvmCompilerDataFlowAnalysisDispatcher(cUnit, - dvmCompilerFindInductionVariables); + dvmCompilerFindInductionVariables, + kAllNodes, + false /* isIterative */); DEBUG_LOOP(dumpIVList(cUnit);) /* If the loop turns out to be non-optimizable, return early */ if (!isLoopOptimizable(cUnit)) return false; - loopAnalysis->arrayAccessInfo = dvmCompilerNew(sizeof(GrowableList), true); + loopAnalysis->arrayAccessInfo = + (GrowableList *)dvmCompilerNew(sizeof(GrowableList), true); dvmInitGrowableList(loopAnalysis->arrayAccessInfo, 4); loopAnalysis->bodyIsClean = doLoopBodyCodeMotion(cUnit); DEBUG_LOOP(dumpHoistedChecks(cUnit);) diff --git a/vm/compiler/MethodSSATransformation.c b/vm/compiler/MethodSSATransformation.c new file mode 100644 index 000000000..48d5b5ce9 --- /dev/null +++ b/vm/compiler/MethodSSATransformation.c @@ -0,0 +1,562 @@ +/* + * 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. + */ + +#include "Dalvik.h" +#include "Dataflow.h" +#include "Loop.h" +#include "libdex/DexOpcodes.h" + +/* Enter the node to the dfsOrder list then visit its successors */ +static void recordDFSPreOrder(CompilationUnit *cUnit, BasicBlock *block) +{ + + if (block->visited) return; + block->visited = true; + + /* Enqueue the block id */ + dvmInsertGrowableList(&cUnit->dfsOrder, block->id); + + if (block->taken) recordDFSPreOrder(cUnit, block->taken); + if (block->fallThrough) recordDFSPreOrder(cUnit, block->fallThrough); + if (block->successorBlockList.blockListType != kNotUsed) { + GrowableListIterator iterator; + dvmGrowableListIteratorInit(&block->successorBlockList.blocks, + &iterator); + while (true) { + SuccessorBlockInfo *successorBlockInfo = + (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator); + if (successorBlockInfo == NULL) break; + BasicBlock *succBB = successorBlockInfo->block; + recordDFSPreOrder(cUnit, succBB); + } + } + return; +} + +/* 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); + + + dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerClearVisitedFlag, + kAllNodes, + false /* isIterative */); + + recordDFSPreOrder(cUnit, cUnit->entryBlock); + cUnit->numReachableBlocks = cUnit->dfsOrder.numUsed; +} + +/* + * Mark block bit on the per-Dalvik register vector to denote that Dalvik + * register idx is defined in BasicBlock bb. + */ +static bool fillDefBlockMatrix(CompilationUnit *cUnit, BasicBlock *bb) +{ + if (bb->dataFlowInfo == NULL) return false; + + BitVectorIterator iterator; + + dvmBitVectorIteratorInit(bb->dataFlowInfo->defV, &iterator); + while (true) { + int idx = dvmBitVectorIteratorNext(&iterator); + if (idx == -1) break; + /* Block bb defines register idx */ + dvmCompilerSetBit(cUnit->defBlockMatrix[idx], bb->id); + } + return true; +} + +static void computeDefBlockMatrix(CompilationUnit *cUnit) +{ + int numRegisters = cUnit->numDalvikRegisters; + /* Allocate numDalvikRegisters bit vector pointers */ + cUnit->defBlockMatrix = (BitVector **) + dvmCompilerNew(sizeof(BitVector *) * numRegisters, true); + int i; + + /* Initialize numRegister vectors with numBlocks bits each */ + for (i = 0; i < numRegisters; i++) { + cUnit->defBlockMatrix[i] = dvmCompilerAllocBitVector(cUnit->numBlocks, + false); + } + dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerFindLocalLiveIn, + kAllNodes, + false /* isIterative */); + dvmCompilerDataFlowAnalysisDispatcher(cUnit, fillDefBlockMatrix, + 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); + } +} + +/* Compute the post-order traversal of the CFG */ +static void computeDomPostOrderTraversal(CompilationUnit *cUnit, BasicBlock *bb) +{ + BitVectorIterator bvIterator; + dvmBitVectorIteratorInit(bb->iDominated, &bvIterator); + GrowableList *blockList = &cUnit->blockList; + + /* Iterate through the dominated blocks first */ + while (true) { + int bbIdx = dvmBitVectorIteratorNext(&bvIterator); + if (bbIdx == -1) break; + BasicBlock *dominatedBB = + (BasicBlock *) dvmGrowableListGetElement(blockList, bbIdx); + computeDomPostOrderTraversal(cUnit, dominatedBB); + } + + /* Enter the current block id */ + dvmInsertGrowableList(&cUnit->domPostOrderTraversal, bb->id); + + /* hacky loop detection */ + if (bb->taken && dvmIsBitSet(bb->dominators, bb->taken->id)) { + cUnit->hasLoop = true; + } +} + +/* Worker function to compute the dominance frontier */ +static bool computeDominanceFrontier(CompilationUnit *cUnit, BasicBlock *bb) +{ + GrowableList *blockList = &cUnit->blockList; + + /* Calculate DF_local */ + if (bb->taken && !dvmIsBitSet(bb->taken->dominators, bb->id)) { + dvmSetBit(bb->domFrontier, bb->taken->id); + } + if (bb->fallThrough && + !dvmIsBitSet(bb->fallThrough->dominators, bb->id)) { + dvmSetBit(bb->domFrontier, bb->fallThrough->id); + } + if (bb->successorBlockList.blockListType != kNotUsed) { + GrowableListIterator iterator; + dvmGrowableListIteratorInit(&bb->successorBlockList.blocks, + &iterator); + while (true) { + SuccessorBlockInfo *successorBlockInfo = + (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator); + if (successorBlockInfo == NULL) break; + BasicBlock *succBB = successorBlockInfo->block; + if (!dvmIsBitSet(succBB->dominators, bb->id)) { + dvmSetBit(bb->domFrontier, succBB->id); + } + } + } + + /* Calculate DF_up */ + BitVectorIterator bvIterator; + dvmBitVectorIteratorInit(bb->iDominated, &bvIterator); + while (true) { + int dominatedIdx = dvmBitVectorIteratorNext(&bvIterator); + if (dominatedIdx == -1) break; + BasicBlock *dominatedBB = (BasicBlock *) + dvmGrowableListGetElement(blockList, dominatedIdx); + BitVectorIterator dfIterator; + dvmBitVectorIteratorInit(dominatedBB->domFrontier, &dfIterator); + while (true) { + int dfUpIdx = dvmBitVectorIteratorNext(&dfIterator); + if (dfUpIdx == -1) break; + BasicBlock *dfUpBlock = (BasicBlock *) + dvmGrowableListGetElement(blockList, dfUpIdx); + if (!dvmIsBitSet(dfUpBlock->dominators, bb->id)) { + dvmSetBit(bb->domFrontier, dfUpBlock->id); + } + } + } + if (cUnit->printMe) { + char blockName[BLOCK_NAME_LEN]; + dvmGetBlockName(bb, blockName); + dvmDumpBlockBitVector(blockList, blockName, bb->domFrontier, + cUnit->numBlocks); + } + + return true; +} + +/* Worker function for initializing domination-related data structures */ +static bool initializeDominationInfo(CompilationUnit *cUnit, BasicBlock *bb) +{ + int numTotalBlocks = cUnit->blockList.numUsed; + + bb->dominators = dvmCompilerAllocBitVector(numTotalBlocks, + false /* expandable */); + bb->iDominated = dvmCompilerAllocBitVector(numTotalBlocks, + false /* expandable */); + bb->domFrontier = dvmCompilerAllocBitVector(numTotalBlocks, + false /* expandable */); + /* Set all bits in the dominator vector */ + dvmSetInitialBits(bb->dominators, numTotalBlocks); + + return true; +} + +/* Worker function to compute each block's dominators */ +static bool computeBlockDominators(CompilationUnit *cUnit, BasicBlock *bb) +{ + GrowableList *blockList = &cUnit->blockList; + int numTotalBlocks = blockList->numUsed; + BitVector *tempBlockV = cUnit->tempBlockV; + BitVectorIterator bvIterator; + + /* + * The dominator of the entry block has been preset to itself and we need + * to skip the calculation here. + */ + if (bb == cUnit->entryBlock) return false; + + dvmSetInitialBits(tempBlockV, numTotalBlocks); + + /* Iterate through the predecessors */ + dvmBitVectorIteratorInit(bb->predecessors, &bvIterator); + while (true) { + int predIdx = dvmBitVectorIteratorNext(&bvIterator); + if (predIdx == -1) break; + BasicBlock *predBB = (BasicBlock *) dvmGrowableListGetElement( + blockList, predIdx); + /* tempBlockV = tempBlockV ^ dominators */ + dvmIntersectBitVectors(tempBlockV, tempBlockV, predBB->dominators); + } + dvmSetBit(tempBlockV, bb->id); + if (dvmCompareBitVectors(tempBlockV, bb->dominators)) { + dvmCopyBitVector(bb->dominators, tempBlockV); + return true; + } + return false; +} + +/* Worker function to compute the idom */ +static bool computeImmediateDominator(CompilationUnit *cUnit, BasicBlock *bb) +{ + GrowableList *blockList = &cUnit->blockList; + BitVector *tempBlockV = cUnit->tempBlockV; + BitVectorIterator bvIterator; + BasicBlock *iDom; + + if (bb == cUnit->entryBlock) return false; + + dvmCopyBitVector(tempBlockV, bb->dominators); + dvmClearBit(tempBlockV, bb->id); + dvmBitVectorIteratorInit(tempBlockV, &bvIterator); + + /* Should not see any dead block */ + assert(dvmCountSetBits(tempBlockV) != 0); + if (dvmCountSetBits(tempBlockV) == 1) { + iDom = (BasicBlock *) dvmGrowableListGetElement( + blockList, dvmBitVectorIteratorNext(&bvIterator)); + bb->iDom = iDom; + } else { + int iDomIdx = dvmBitVectorIteratorNext(&bvIterator); + assert(iDomIdx != -1); + while (true) { + int nextDom = dvmBitVectorIteratorNext(&bvIterator); + if (nextDom == -1) break; + BasicBlock *nextDomBB = (BasicBlock *) + dvmGrowableListGetElement(blockList, nextDom); + /* iDom dominates nextDom - set new iDom */ + if (dvmIsBitSet(nextDomBB->dominators, iDomIdx)) { + iDomIdx = nextDom; + } + + } + iDom = (BasicBlock *) dvmGrowableListGetElement(blockList, iDomIdx); + /* Set the immediate dominator block for bb */ + bb->iDom = iDom; + } + /* Add bb to the iDominated set of the immediate dominator block */ + dvmCompilerSetBit(iDom->iDominated, bb->id); + return true; +} + +/* Compute dominators, immediate dominator, and dominance fronter */ +static void computeDominators(CompilationUnit *cUnit) +{ + int numReachableBlocks = cUnit->numReachableBlocks; + int numTotalBlocks = cUnit->blockList.numUsed; + + /* Initialize domination-related data structures */ + dvmCompilerDataFlowAnalysisDispatcher(cUnit, initializeDominationInfo, + kReachableNodes, + false /* isIterative */); + + /* Set the dominator for the root node */ + dvmClearAllBits(cUnit->entryBlock->dominators); + dvmSetBit(cUnit->entryBlock->dominators, cUnit->entryBlock->id); + + cUnit->tempBlockV = dvmCompilerAllocBitVector(numTotalBlocks, + false /* expandable */); + dvmCompilerDataFlowAnalysisDispatcher(cUnit, computeBlockDominators, + kPreOrderDFSTraversal, + true /* isIterative */); + + cUnit->entryBlock->iDom = NULL; + dvmCompilerDataFlowAnalysisDispatcher(cUnit, computeImmediateDominator, + kReachableNodes, + false /* isIterative */); + + /* + * Now go ahead and compute the post order traversal based on the + * iDominated sets. + */ + dvmInitGrowableList(&cUnit->domPostOrderTraversal, numReachableBlocks); + computeDomPostOrderTraversal(cUnit, cUnit->entryBlock); + assert(cUnit->domPostOrderTraversal.numUsed == + (unsigned) cUnit->numReachableBlocks); + + /* Now compute the dominance frontier for each block */ + dvmCompilerDataFlowAnalysisDispatcher(cUnit, computeDominanceFrontier, + kPostOrderDOMTraversal, + false /* isIterative */); +} + +/* + * Perform dest U= src1 ^ ~src2 + * This is probably not general enough to be placed in BitVector.[ch]. + */ +static void computeSuccLiveIn(BitVector *dest, + const BitVector *src1, + const BitVector *src2) +{ + if (dest->storageSize != src1->storageSize || + dest->storageSize != src2->storageSize || + dest->expandable != src1->expandable || + dest->expandable != src2->expandable) { + LOGE("Incompatible set properties"); + dvmAbort(); + } + + int i; + for (i = 0; i < dest->storageSize; i++) { + dest->storage[i] |= src1->storage[i] & ~src2->storage[i]; + } +} + +/* + * Iterate through all successor blocks and propagate up the live-in sets. + * The calculated result is used for phi-node pruning - where we only need to + * insert a phi node if the variable is live-in to the block. + */ +static bool computeBlockLiveIns(CompilationUnit *cUnit, BasicBlock *bb) +{ + BitVector *tempDalvikRegisterV = cUnit->tempDalvikRegisterV; + + if (bb->dataFlowInfo == NULL) return false; + dvmCopyBitVector(tempDalvikRegisterV, bb->dataFlowInfo->liveInV); + if (bb->taken && bb->taken->dataFlowInfo) + computeSuccLiveIn(tempDalvikRegisterV, bb->taken->dataFlowInfo->liveInV, + bb->dataFlowInfo->defV); + if (bb->fallThrough && bb->fallThrough->dataFlowInfo) + computeSuccLiveIn(tempDalvikRegisterV, + bb->fallThrough->dataFlowInfo->liveInV, + bb->dataFlowInfo->defV); + if (bb->successorBlockList.blockListType != kNotUsed) { + GrowableListIterator iterator; + dvmGrowableListIteratorInit(&bb->successorBlockList.blocks, + &iterator); + while (true) { + SuccessorBlockInfo *successorBlockInfo = + (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator); + if (successorBlockInfo == NULL) break; + BasicBlock *succBB = successorBlockInfo->block; + if (succBB->dataFlowInfo) { + computeSuccLiveIn(tempDalvikRegisterV, + succBB->dataFlowInfo->liveInV, + bb->dataFlowInfo->defV); + } + } + } + if (dvmCompareBitVectors(tempDalvikRegisterV, bb->dataFlowInfo->liveInV)) { + dvmCopyBitVector(bb->dataFlowInfo->liveInV, tempDalvikRegisterV); + return true; + } + return false; +} + +/* Insert phi nodes to for each variable to the dominance frontiers */ +static void insertPhiNodes(CompilationUnit *cUnit) +{ + int dalvikReg; + const GrowableList *blockList = &cUnit->blockList; + BitVector *phiBlocks = + dvmCompilerAllocBitVector(cUnit->numDalvikRegisters, false); + BitVector *tmpBlocks = + dvmCompilerAllocBitVector(cUnit->numDalvikRegisters, false); + BitVector *inputBlocks = + dvmCompilerAllocBitVector(cUnit->numDalvikRegisters, false); + + cUnit->tempDalvikRegisterV = + dvmCompilerAllocBitVector(cUnit->numDalvikRegisters, false); + + dvmCompilerDataFlowAnalysisDispatcher(cUnit, computeBlockLiveIns, + kPostOrderDFSTraversal, + true /* isIterative */); + + /* Iterate through each Dalvik register */ + for (dalvikReg = 0; dalvikReg < cUnit->numDalvikRegisters; dalvikReg++) { + bool change; + BitVectorIterator iterator; + + 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); + } + if (dvmCompareBitVectors(phiBlocks, tmpBlocks)) { + change = true; + dvmCopyBitVector(phiBlocks, tmpBlocks); + + /* + * Iterate through the original blocks plus the new ones in + * the dominance frontier. + */ + dvmCopyBitVector(inputBlocks, phiBlocks); + dvmUnifyBitVectors(inputBlocks, inputBlocks, + cUnit->defBlockMatrix[dalvikReg]); + } + } while (change); + + /* + * Insert a phi node for dalvikReg in the phiBlocks if the Dalvik + * register is in the live-in set. + */ + dvmBitVectorIteratorInit(phiBlocks, &iterator); + while (true) { + int idx = dvmBitVectorIteratorNext(&iterator); + if (idx == -1) break; + BasicBlock *phiBB = + (BasicBlock *) dvmGrowableListGetElement(blockList, idx); + /* Variable will be clobbered before being used - no need for phi */ + if (!dvmIsBitSet(phiBB->dataFlowInfo->liveInV, dalvikReg)) continue; + MIR *phi = (MIR *) dvmCompilerNew(sizeof(MIR), true); + phi->dalvikInsn.opcode = kMirOpPhi; + phi->dalvikInsn.vA = dalvikReg; + phi->offset = phiBB->startOffset; + dvmCompilerPrependMIR(phiBB, phi); + } + } +} + +/* + * Worker function to insert phi-operands with latest SSA names from + * predecessor blocks + */ +static bool insertPhiNodeOperands(CompilationUnit *cUnit, BasicBlock *bb) +{ + BitVector *ssaRegV = cUnit->tempSSARegisterV; + BitVectorIterator bvIterator; + GrowableList *blockList = &cUnit->blockList; + MIR *mir; + + /* Phi nodes are at the beginning of each block */ + for (mir = bb->firstMIRInsn; mir; mir = mir->next) { + if (mir->dalvikInsn.opcode != kMirOpPhi) return true; + int ssaReg = mir->ssaRep->defs[0]; + int encodedDalvikValue = + (int) dvmGrowableListGetElement(cUnit->ssaToDalvikMap, ssaReg); + int dalvikReg = DECODE_REG(encodedDalvikValue); + + dvmClearAllBits(ssaRegV); + + /* Iterate through the predecessors */ + dvmBitVectorIteratorInit(bb->predecessors, &bvIterator); + while (true) { + int predIdx = dvmBitVectorIteratorNext(&bvIterator); + if (predIdx == -1) break; + BasicBlock *predBB = (BasicBlock *) dvmGrowableListGetElement( + blockList, predIdx); + int encodedSSAValue = + predBB->dataFlowInfo->dalvikToSSAMap[dalvikReg]; + int ssaReg = DECODE_REG(encodedSSAValue); + dvmSetBit(ssaRegV, ssaReg); + } + + /* Count the number of SSA registers for a Dalvik register */ + int numUses = dvmCountSetBits(ssaRegV); + mir->ssaRep->numUses = numUses; + mir->ssaRep->uses = + (int *) dvmCompilerNew(sizeof(int) * numUses, false); + mir->ssaRep->fpUse = + (bool *) dvmCompilerNew(sizeof(bool) * numUses, false); + + BitVectorIterator phiIterator; + + dvmBitVectorIteratorInit(ssaRegV, &phiIterator); + int *usePtr = mir->ssaRep->uses; + + /* Set the uses array for the phi node */ + while (true) { + int ssaRegIdx = dvmBitVectorIteratorNext(&phiIterator); + if (ssaRegIdx == -1) break; + *usePtr++ = ssaRegIdx; + } + } + + return true; +} + +/* Perform SSA transformation for the whole method */ +void dvmCompilerMethodSSATransformation(CompilationUnit *cUnit) +{ + /* Compute the DFS order */ + computeDFSOrder(cUnit); + + /* Compute the dominator info */ + 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 */); +} diff --git a/vm/compiler/Ralloc.c b/vm/compiler/Ralloc.c index 744bc3262..d772a3148 100644 --- a/vm/compiler/Ralloc.c +++ b/vm/compiler/Ralloc.c @@ -18,42 +18,6 @@ #include "CompilerInternals.h" #include "Dataflow.h" -typedef struct LiveRange { - int ssaName; - bool active; - int first; - int last; -} LiveRange; - -static int computeLiveRange(LiveRange *list, BasicBlock *bb, int seqNum) -{ - MIR *mir; - int i; - - if (bb->blockType != kDalvikByteCode && - bb->blockType != kTraceEntryBlock) - return seqNum; - - for (mir = bb->firstMIRInsn; mir; mir = mir->next) { - SSARepresentation *ssaRep = mir->ssaRep; - mir->seqNum = seqNum; - if (ssaRep) { - for (i=0; i< ssaRep->numUses; i++) { - int reg = ssaRep->uses[i]; - list[reg].first = MIN(list[reg].first, seqNum); - list[reg].active = true; - } - for (i=0; i< ssaRep->numDefs; i++) { - int reg = ssaRep->defs[i]; - list[reg].last = MAX(list[reg].last, seqNum + 1); - list[reg].active = true; - } - seqNum += 2; - } - } - return seqNum; -} - /* * Quick & dirty - make FP usage sticky. This is strictly a hint - local * code generation will handle misses. It might be worthwhile to collaborate @@ -83,46 +47,17 @@ static void inferTypes(CompilationUnit *cUnit, BasicBlock *bb) } } -/* - * Determine whether to use simple or aggressive register allocation. In - * general, loops and full methods will get aggressive. - */ -static bool simpleTrace(CompilationUnit *cUnit) -{ - //TODO: flesh out - return true; -} +static const RegLocation freshLoc = {kLocDalvikFrame, 0, 0, INVALID_REG, + INVALID_REG, INVALID_SREG}; /* - * Target-independent register allocation. Requires target-dependent - * helper functions and assumes free list, temp list and spill region. - * Uses a variant of linear scan and produces a mapping between SSA names - * and location. Location may be original Dalvik register, hardware - * register or spill location. - * - * Method: - * 0. Allocate the structure to hold the SSA name life ranges - * 1. Number each MIR instruction, counting by 2. - * +0 -> The "read" of the operands - * +1 -> The definition of the target resource - * 2. Compute live ranges for all SSA names *not* including the - * subscript 0 original Dalvik names. Phi functions ignored - * at this point. - * 3. Sort the live range list by lowest range start. - * 4. Process and remove all Phi functions. - * o If there is no live range collisions among all operands and - * the target of a Phi function, collapse operands and target - * and rewrite using target SSA name. - * o If there is a collision, introduce copies. - * 5. Allocate in order of increasing live range start. + * Local register allocation for simple traces. Most of the work for + * local allocation is done on the fly. Here we do some initialization + * and type inference. */ -static const RegLocation freshLoc = {kLocDalvikFrame, 0, 0, INVALID_REG, - INVALID_REG, INVALID_SREG}; -void dvmCompilerRegAlloc(CompilationUnit *cUnit) +void dvmCompilerLocalRegAlloc(CompilationUnit *cUnit) { int i; - int seqNum = 0; - LiveRange *ranges; RegLocation *loc; /* Allocate the location map */ @@ -133,27 +68,19 @@ void dvmCompilerRegAlloc(CompilationUnit *cUnit) } cUnit->regLocation = loc; + GrowableListIterator iterator; + + dvmGrowableListIteratorInit(&cUnit->blockList, &iterator); /* Do type inference pass */ - for (i=0; i < cUnit->numBlocks; i++) { - inferTypes(cUnit, cUnit->blockList[i]); + while (true) { + BasicBlock *bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator); + if (bb == NULL) break; + inferTypes(cUnit, bb); } - if (simpleTrace(cUnit)) { - /* - * Just rename everything back to subscript 0 names and don't do - * any explicit promotion. Local allocator will opportunistically - * promote on the fly. - */ - for (i=0; i < cUnit->numSSARegs; i++) { - cUnit->regLocation[i].sRegLow = + /* Remap SSA names back to original frame locations. */ + for (i=0; i < cUnit->numSSARegs; i++) { + cUnit->regLocation[i].sRegLow = DECODE_REG(dvmConvertSSARegToDalvik(cUnit, loc[i].sRegLow)); - } - } else { - // Compute live ranges - ranges = dvmCompilerNew(cUnit->numSSARegs * sizeof(*ranges), true); - for (i=0; i < cUnit->numSSARegs; i++) - ranges[i].active = false; - seqNum = computeLiveRange(ranges, cUnit->blockList[i], seqNum); - //TODO: phi squash & linear scan promotion } } diff --git a/vm/compiler/Utility.c b/vm/compiler/Utility.c index daeb8937c..fe258331f 100644 --- a/vm/compiler/Utility.c +++ b/vm/compiler/Utility.c @@ -82,7 +82,8 @@ retry: LOGI("Total arena pages for JIT: %d", numArenaBlocks); goto retry; } - return NULL; + /* Should not reach here */ + dvmAbort(); } /* Reclaim all the arena blocks allocated so far */ @@ -101,8 +102,8 @@ void dvmInitGrowableList(GrowableList *gList, size_t initLength) { gList->numAllocated = initLength; gList->numUsed = 0; - gList->elemList = (void **) dvmCompilerNew(sizeof(void *) * initLength, - true); + gList->elemList = (intptr_t *) dvmCompilerNew(sizeof(intptr_t) * initLength, + true); } /* Expand the capacity of a growable list */ @@ -114,14 +115,15 @@ static void expandGrowableList(GrowableList *gList) } else { newLength += 128; } - void *newArray = dvmCompilerNew(sizeof(void *) * newLength, true); - memcpy(newArray, gList->elemList, sizeof(void *) * gList->numAllocated); + intptr_t *newArray = + (intptr_t *) dvmCompilerNew(sizeof(intptr_t) * newLength, true); + memcpy(newArray, gList->elemList, sizeof(intptr_t) * gList->numAllocated); gList->numAllocated = newLength; gList->elemList = newArray; } /* Insert a new element into the growable list */ -void dvmInsertGrowableList(GrowableList *gList, void *elem) +void dvmInsertGrowableList(GrowableList *gList, intptr_t elem) { assert(gList->numAllocated != 0); if (gList->numUsed == gList->numAllocated) { @@ -130,10 +132,30 @@ void dvmInsertGrowableList(GrowableList *gList, void *elem) gList->elemList[gList->numUsed++] = elem; } +void dvmGrowableListIteratorInit(GrowableList *gList, + GrowableListIterator *iterator) +{ + iterator->list = gList; + iterator->idx = 0; + iterator->size = gList->numUsed; +} + +intptr_t dvmGrowableListIteratorNext(GrowableListIterator *iterator) +{ + assert(iterator->size == iterator->list->numUsed); + if (iterator->idx == iterator->size) return 0; + return iterator->list->elemList[iterator->idx++]; +} + +intptr_t dvmGrowableListGetElement(const GrowableList *gList, size_t idx) +{ + assert(idx < gList->numUsed); + return gList->elemList[idx]; +} + /* Debug Utility - dump a compilation unit */ void dvmCompilerDumpCompilationUnit(CompilationUnit *cUnit) { - int i; BasicBlock *bb; char *blockTypeNames[] = { "Normal Chaining Cell", @@ -156,9 +178,13 @@ void dvmCompilerDumpCompilationUnit(CompilationUnit *cUnit) cUnit->method->name); LOGD("%d insns", dvmGetMethodInsnsSize(cUnit->method)); LOGD("%d blocks in total", cUnit->numBlocks); + GrowableListIterator iterator; + + dvmGrowableListIteratorInit(&cUnit->blockList, &iterator); - for (i = 0; i < cUnit->numBlocks; i++) { - bb = cUnit->blockList[i]; + while (true) { + bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator); + if (bb == NULL) break; LOGD("Block %d (%s) (insn %04x - %04x%s)\n", bb->id, blockTypeNames[bb->blockType], @@ -275,12 +301,12 @@ bool dvmCompilerSetBit(BitVector *pBits, int num) assert(num >= 0); if (num >= pBits->storageSize * (int)sizeof(u4) * 8) { if (!pBits->expandable) - return false; + dvmAbort(); /* Round up to word boundaries for "num+1" bits */ int newSize = (num + 1 + 31) >> 5; assert(newSize > pBits->storageSize); - u4 *newStorage = dvmCompilerNew(newSize * sizeof(u4), false); + u4 *newStorage = (u4*)dvmCompilerNew(newSize * sizeof(u4), false); memcpy(newStorage, pBits->storage, pBits->storageSize * sizeof(u4)); memset(&newStorage[pBits->storageSize], 0, (newSize - pBits->storageSize) * sizeof(u4)); @@ -292,6 +318,36 @@ bool dvmCompilerSetBit(BitVector *pBits, int num) return true; } +/* + * Mark the specified bit as "unset". + * + * Returns "false" if the bit is outside the range of the vector and we're + * not allowed to expand. + * + * NOTE: this is the sister implementation of dvmClearBit. In this version + * memory is allocated from the compiler arena. + */ +bool dvmCompilerClearBit(BitVector *pBits, int num) +{ + assert(num >= 0); + if (num >= pBits->storageSize * (int)sizeof(u4) * 8) { + LOGE("Trying to clear a bit that is not set in the vector yet!"); + dvmAbort(); + } + + pBits->storage[num >> 5] &= ~(1 << (num & 0x1f)); + return true; +} + +/* + * If set is true, mark all bits as 1. Otherwise mark all bits as 0. + */ +void dvmCompilerMarkAllBits(BitVector *pBits, bool set) +{ + int value = set ? -1 : 0; + memset(pBits->storage, value, pBits->storageSize * (int)sizeof(u4)); +} + void dvmDebugBitVector(char *msg, const BitVector *bv, int length) { int i; @@ -315,3 +371,41 @@ void dvmCompilerAbort(CompilationUnit *cUnit) */ longjmp(*cUnit->bailPtr, 1); } + +void dvmDumpBlockBitVector(const GrowableList *blocks, char *msg, + const BitVector *bv, int length) +{ + int i; + + LOGE("%s", msg); + for (i = 0; i < length; i++) { + if (dvmIsBitSet(bv, i)) { + BasicBlock *bb = + (BasicBlock *) dvmGrowableListGetElement(blocks, i); + char blockName[BLOCK_NAME_LEN]; + dvmGetBlockName(bb, blockName); + LOGE("Bit %d / %s is set", i, blockName); + } + } +} + +void dvmGetBlockName(BasicBlock *bb, char *name) +{ + switch (bb->blockType) { + case kMethodEntryBlock: + snprintf(name, BLOCK_NAME_LEN, "entry"); + break; + case kMethodExitBlock: + snprintf(name, BLOCK_NAME_LEN, "exit"); + break; + case kDalvikByteCode: + snprintf(name, BLOCK_NAME_LEN, "block%04x", bb->startOffset); + break; + case kExceptionHandling: + snprintf(name, BLOCK_NAME_LEN, "exception%04x", bb->startOffset); + break; + default: + snprintf(name, BLOCK_NAME_LEN, "??"); + break; + } +} diff --git a/vm/compiler/codegen/CompilerCodegen.h b/vm/compiler/codegen/CompilerCodegen.h index d871c3b7b..70a2bbd64 100644 --- a/vm/compiler/codegen/CompilerCodegen.h +++ b/vm/compiler/codegen/CompilerCodegen.h @@ -44,7 +44,7 @@ void dvmJitUnchainAll(void); void dvmCompilerPatchInlineCache(void); /* Implemented in codegen/<target>/Ralloc.c */ -void dvmCompilerRegAlloc(CompilationUnit *cUnit); +void dvmCompilerLocalRegAlloc(CompilationUnit *cUnit); /* Implemented in codegen/<target>/Thumb<version>Util.c */ void dvmCompilerInitializeRegAlloc(CompilationUnit *cUnit); diff --git a/vm/compiler/codegen/RallocUtil.c b/vm/compiler/codegen/RallocUtil.c index 32977eb24..51162430a 100644 --- a/vm/compiler/codegen/RallocUtil.c +++ b/vm/compiler/codegen/RallocUtil.c @@ -364,10 +364,6 @@ extern void dvmCompilerFreeTemp(CompilationUnit *cUnit, int reg) dvmCompilerAbort(cUnit); } -/* - * FIXME - this needs to also check the preserved pool once we start - * start using preserved registers. - */ extern RegisterInfo *dvmCompilerIsLive(CompilationUnit *cUnit, int reg) { RegisterInfo *p = cUnit->regPool->coreTemps; diff --git a/vm/compiler/codegen/arm/ArchUtility.c b/vm/compiler/codegen/arm/ArchUtility.c index 0b76eb58b..95b96c496 100644 --- a/vm/compiler/codegen/arm/ArchUtility.c +++ b/vm/compiler/codegen/arm/ArchUtility.c @@ -375,7 +375,7 @@ void dvmCompilerCodegenDump(CompilationUnit *cUnit) LOGD("installed code is at %p\n", cUnit->baseAddr); LOGD("total size is %d bytes\n", cUnit->totalSize); for (lirInsn = cUnit->firstLIRInsn; lirInsn; lirInsn = lirInsn->next) { - dvmDumpLIRInsn(lirInsn, cUnit->baseAddr); + dvmDumpLIRInsn(lirInsn, (unsigned char *) cUnit->baseAddr); } for (lirInsn = cUnit->wordList; lirInsn; lirInsn = lirInsn->next) { armLIR = (ArmLIR *) lirInsn; @@ -385,3 +385,9 @@ void dvmCompilerCodegenDump(CompilationUnit *cUnit) armLIR->operands[0]); } } + +/* Target-specific cache flushing */ +int dvmCompilerCacheFlush(long start, long end, long flags) +{ + return cacheflush(start, end, flags); +} diff --git a/vm/compiler/codegen/arm/ArmLIR.h b/vm/compiler/codegen/arm/ArmLIR.h index 213344cd8..4f3434dec 100644 --- a/vm/compiler/codegen/arm/ArmLIR.h +++ b/vm/compiler/codegen/arm/ArmLIR.h @@ -119,10 +119,6 @@ typedef struct RegisterPool { int numFPTemps; RegisterInfo *FPTemps; int nextFPTemp; - int numCoreRegs; - RegisterInfo *coreRegs; - int numFPRegs; - RegisterInfo *FPRegs; } RegisterPool; typedef enum ResourceEncodingPos { diff --git a/vm/compiler/codegen/arm/Assemble.c b/vm/compiler/codegen/arm/Assemble.c index 42a8d3740..4154387ba 100644 --- a/vm/compiler/codegen/arm/Assemble.c +++ b/vm/compiler/codegen/arm/Assemble.c @@ -20,7 +20,6 @@ #include "../../CompilerInternals.h" #include "ArmLIR.h" #include "Codegen.h" -#include <unistd.h> /* for cacheflush */ #include <sys/mman.h> /* for protection change */ #define MAX_ASSEMBLER_RETRIES 10 @@ -973,7 +972,8 @@ static AssemblerStatus assembleInstructions(CompilationUnit *cUnit, int delta = target - pc; if (delta > 126 || delta < 0) { /* Convert to cmp rx,#0 / b[eq/ne] tgt pair */ - ArmLIR *newInst = dvmCompilerNew(sizeof(ArmLIR), true); + ArmLIR *newInst = + (ArmLIR *)dvmCompilerNew(sizeof(ArmLIR), true); /* Make new branch instruction and insert after */ newInst->opcode = kThumbBCond; newInst->operands[0] = 0; @@ -1280,7 +1280,7 @@ void dvmCompilerAssembleLIR(CompilationUnit *cUnit, JitTranslationInfo *info) } /* Allocate enough space for the code block */ - cUnit->codeBuffer = dvmCompilerNew(chainCellOffset, true); + cUnit->codeBuffer = (unsigned char *)dvmCompilerNew(chainCellOffset, true); if (cUnit->codeBuffer == NULL) { LOGE("Code buffer allocation failure\n"); cUnit->baseAddr = NULL; @@ -1352,8 +1352,8 @@ void dvmCompilerAssembleLIR(CompilationUnit *cUnit, JitTranslationInfo *info) installDataContent(cUnit); /* Flush dcache and invalidate the icache to maintain coherence */ - cacheflush((long)cUnit->baseAddr, - (long)((char *) cUnit->baseAddr + offset), 0); + dvmCompilerCacheFlush((long)cUnit->baseAddr, + (long)((char *) cUnit->baseAddr + offset), 0); UPDATE_CODE_CACHE_PATCHES(); PROTECT_CODE_CACHE(cUnit->baseAddr, offset); @@ -1448,7 +1448,7 @@ void* dvmJitChain(void* tgtAddr, u4* branchAddr) UNPROTECT_CODE_CACHE(branchAddr, sizeof(*branchAddr)); *branchAddr = newInst; - cacheflush((long)branchAddr, (long)branchAddr + 4, 0); + dvmCompilerCacheFlush((long)branchAddr, (long)branchAddr + 4, 0); UPDATE_CODE_CACHE_PATCHES(); PROTECT_CODE_CACHE(branchAddr, sizeof(*branchAddr)); @@ -1487,8 +1487,8 @@ static void inlineCachePatchEnqueue(PredictedChainingCell *cellAddr, * will bring the uninitialized chaining cell to life. */ android_atomic_release_store((int32_t)newContent->clazz, - (void*) &cellAddr->clazz); - cacheflush((intptr_t) cellAddr, (intptr_t) (cellAddr+1), 0); + (volatile int32_t *)(void *)&cellAddr->clazz); + dvmCompilerCacheFlush((intptr_t) cellAddr, (intptr_t) (cellAddr+1), 0); UPDATE_CODE_CACHE_PATCHES(); PROTECT_CODE_CACHE(cellAddr, sizeof(*cellAddr)); @@ -1583,7 +1583,7 @@ const Method *dvmJitToPatchPredictedChain(const Method *method, * trigger immediate patching and will continue to fail to match with * a real clazz pointer. */ - cell->clazz = (void *) PREDICTED_CHAIN_FAKE_CLAZZ; + cell->clazz = (ClassObject *) PREDICTED_CHAIN_FAKE_CLAZZ; UPDATE_CODE_CACHE_PATCHES(); PROTECT_CODE_CACHE(cell, sizeof(*cell)); @@ -1680,7 +1680,7 @@ void dvmCompilerPatchInlineCache(void) } /* Then synchronize the I/D cache */ - cacheflush((long) minAddr, (long) (maxAddr+1), 0); + dvmCompilerCacheFlush((long) minAddr, (long) (maxAddr+1), 0); UPDATE_CODE_CACHE_PATCHES(); PROTECT_CODE_CACHE(gDvmJit.codeCache, gDvmJit.codeCacheByteUsed); @@ -1801,7 +1801,7 @@ void dvmJitUnchainAll() highAddress = lastAddress; } } - cacheflush((long)lowAddress, (long)highAddress, 0); + dvmCompilerCacheFlush((long)lowAddress, (long)highAddress, 0); UPDATE_CODE_CACHE_PATCHES(); PROTECT_CODE_CACHE(gDvmJit.codeCache, gDvmJit.codeCacheByteUsed); @@ -1912,7 +1912,7 @@ static int dumpTraceProfile(JitEntry *p, bool silent, bool reset, * be a meta info field (only used by callsite info for now). */ if (!desc->trace[idx].frag.isCode) { - const Method *method = desc->trace[idx+1].meta; + const Method *method = (const Method *)desc->trace[idx+1].meta; char *methodDesc = dexProtoCopyMethodDescriptor(&method->prototype); /* Print the callee info in the trace */ LOGD(" -> %s%s;%s", method->clazz->descriptor, method->name, @@ -1964,8 +1964,8 @@ static inline int getProfileCount(const JitEntry *entry) /* qsort callback function */ static int sortTraceProfileCount(const void *entry1, const void *entry2) { - const JitEntry *jitEntry1 = entry1; - const JitEntry *jitEntry2 = entry2; + const JitEntry *jitEntry1 = (const JitEntry *)entry1; + const JitEntry *jitEntry2 = (const JitEntry *)entry2; int count1 = getProfileCount(jitEntry1); int count2 = getProfileCount(jitEntry2); @@ -1984,7 +1984,7 @@ void dvmCompilerSortAndPrintTraceProfiles() dvmLockMutex(&gDvmJit.tableLock); /* Sort the entries by descending order */ - sortedEntries = malloc(sizeof(JitEntry) * gDvmJit.jitTableSize); + sortedEntries = (JitEntry *)malloc(sizeof(JitEntry) * gDvmJit.jitTableSize); if (sortedEntries == NULL) goto done; memcpy(sortedEntries, gDvmJit.pJitEntryTable, diff --git a/vm/compiler/codegen/arm/CodegenCommon.c b/vm/compiler/codegen/arm/CodegenCommon.c index 4a2057976..c29efa640 100644 --- a/vm/compiler/codegen/arm/CodegenCommon.c +++ b/vm/compiler/codegen/arm/CodegenCommon.c @@ -204,7 +204,7 @@ static void setupResourceMasks(ArmLIR *lir) */ static ArmLIR *newLIR0(CompilationUnit *cUnit, ArmOpcode opcode) { - ArmLIR *insn = dvmCompilerNew(sizeof(ArmLIR), true); + ArmLIR *insn = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); assert(isPseudoOpcode(opcode) || (EncodingMap[opcode].flags & NO_OPERAND)); insn->opcode = opcode; setupResourceMasks(insn); @@ -215,7 +215,7 @@ static ArmLIR *newLIR0(CompilationUnit *cUnit, ArmOpcode opcode) static ArmLIR *newLIR1(CompilationUnit *cUnit, ArmOpcode opcode, int dest) { - ArmLIR *insn = dvmCompilerNew(sizeof(ArmLIR), true); + ArmLIR *insn = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); assert(isPseudoOpcode(opcode) || (EncodingMap[opcode].flags & IS_UNARY_OP)); insn->opcode = opcode; insn->operands[0] = dest; @@ -227,7 +227,7 @@ static ArmLIR *newLIR1(CompilationUnit *cUnit, ArmOpcode opcode, static ArmLIR *newLIR2(CompilationUnit *cUnit, ArmOpcode opcode, int dest, int src1) { - ArmLIR *insn = dvmCompilerNew(sizeof(ArmLIR), true); + ArmLIR *insn = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); assert(isPseudoOpcode(opcode) || (EncodingMap[opcode].flags & IS_BINARY_OP)); insn->opcode = opcode; @@ -241,7 +241,7 @@ static ArmLIR *newLIR2(CompilationUnit *cUnit, ArmOpcode opcode, static ArmLIR *newLIR3(CompilationUnit *cUnit, ArmOpcode opcode, int dest, int src1, int src2) { - ArmLIR *insn = dvmCompilerNew(sizeof(ArmLIR), true); + ArmLIR *insn = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); if (!(EncodingMap[opcode].flags & IS_TERTIARY_OP)) { LOGE("Bad LIR3: %s[%d]",EncodingMap[opcode].name,opcode); } @@ -260,7 +260,7 @@ static ArmLIR *newLIR3(CompilationUnit *cUnit, ArmOpcode opcode, static ArmLIR *newLIR4(CompilationUnit *cUnit, ArmOpcode opcode, int dest, int src1, int src2, int info) { - ArmLIR *insn = dvmCompilerNew(sizeof(ArmLIR), true); + ArmLIR *insn = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); assert(isPseudoOpcode(opcode) || (EncodingMap[opcode].flags & IS_QUAD_OP)); insn->opcode = opcode; @@ -321,7 +321,7 @@ static ArmLIR *addWordData(CompilationUnit *cUnit, int value, bool inPlace) { /* Add the constant to the literal pool */ if (!inPlace) { - ArmLIR *newValue = dvmCompilerNew(sizeof(ArmLIR), true); + ArmLIR *newValue = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); newValue->operands[0] = value; newValue->generic.next = cUnit->wordList; cUnit->wordList = (LIR *) newValue; @@ -371,12 +371,13 @@ static ArmLIR *genCheckCommon(CompilationUnit *cUnit, int dOffset, /* Set up the place holder to reconstruct this Dalvik PC */ if (pcrLabel == NULL) { int dPC = (int) (cUnit->method->insns + dOffset); - pcrLabel = dvmCompilerNew(sizeof(ArmLIR), true); + pcrLabel = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); pcrLabel->opcode = kArmPseudoPCReconstructionCell; pcrLabel->operands[0] = dPC; pcrLabel->operands[1] = dOffset; /* Insert the place holder to the growable list */ - dvmInsertGrowableList(&cUnit->pcReconstructionList, pcrLabel); + dvmInsertGrowableList(&cUnit->pcReconstructionList, + (intptr_t) pcrLabel); } /* Branch to the PC reconstruction code */ branch->generic.target = (LIR *) pcrLabel; diff --git a/vm/compiler/codegen/arm/CodegenDriver.c b/vm/compiler/codegen/arm/CodegenDriver.c index 98236b6ba..6473edb50 100644 --- a/vm/compiler/codegen/arm/CodegenDriver.c +++ b/vm/compiler/codegen/arm/CodegenDriver.c @@ -205,7 +205,7 @@ static bool genConversionPortable(CompilationUnit *cUnit, MIR *mir) static void selfVerificationBranchInsert(LIR *currentLIR, ArmOpcode opcode, int dest, int src1) { - ArmLIR *insn = dvmCompilerNew(sizeof(ArmLIR), true); + ArmLIR *insn = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); insn->opcode = opcode; insn->operands[0] = dest; insn->operands[1] = src1; @@ -912,12 +912,12 @@ static void genReturnCommon(CompilationUnit *cUnit, MIR *mir) /* Insert branch, but defer setting of target */ ArmLIR *branch = genUnconditionalBranch(cUnit, NULL); /* Set up the place holder to reconstruct this Dalvik PC */ - ArmLIR *pcrLabel = dvmCompilerNew(sizeof(ArmLIR), true); + ArmLIR *pcrLabel = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); pcrLabel->opcode = kArmPseudoPCReconstructionCell; pcrLabel->operands[0] = dPC; pcrLabel->operands[1] = mir->offset; /* Insert the place holder to the growable list */ - dvmInsertGrowableList(&cUnit->pcReconstructionList, pcrLabel); + dvmInsertGrowableList(&cUnit->pcReconstructionList, (intptr_t) pcrLabel); /* Branch to the PC reconstruction code */ branch->generic.target = (LIR *) pcrLabel; } @@ -1156,12 +1156,13 @@ static void genInvokeVirtualCommon(CompilationUnit *cUnit, MIR *mir, */ if (pcrLabel == NULL) { int dPC = (int) (cUnit->method->insns + mir->offset); - pcrLabel = dvmCompilerNew(sizeof(ArmLIR), true); + pcrLabel = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); pcrLabel->opcode = kArmPseudoPCReconstructionCell; pcrLabel->operands[0] = dPC; pcrLabel->operands[1] = mir->offset; /* Insert the place holder to the growable list */ - dvmInsertGrowableList(&cUnit->pcReconstructionList, pcrLabel); + dvmInsertGrowableList(&cUnit->pcReconstructionList, + (intptr_t) pcrLabel); } /* return through lr+2 - punt to the interpreter */ @@ -1481,7 +1482,7 @@ static bool handleFmt21c_Fmt31c(CompilationUnit *cUnit, MIR *mir) isVolatile = (mir->dalvikInsn.opcode == OP_SGET_VOLATILE) || (mir->dalvikInsn.opcode == OP_SGET_OBJECT_VOLATILE) || - dvmIsVolatileField(fieldPtr); + dvmIsVolatileField((Field *) fieldPtr); rlDest = dvmCompilerGetDest(cUnit, mir, 0); rlResult = dvmCompilerEvalLoc(cUnit, rlDest, kAnyReg, true); @@ -1541,7 +1542,7 @@ static bool handleFmt21c_Fmt31c(CompilationUnit *cUnit, MIR *mir) isVolatile = (mir->dalvikInsn.opcode == OP_SPUT_VOLATILE) || (mir->dalvikInsn.opcode == OP_SPUT_OBJECT_VOLATILE) || - dvmIsVolatileField(fieldPtr); + dvmIsVolatileField((Field *) fieldPtr); isSputObject = (mir->dalvikInsn.opcode == OP_SPUT_OBJECT) || (mir->dalvikInsn.opcode == OP_SPUT_OBJECT_VOLATILE); @@ -1600,7 +1601,7 @@ static bool handleFmt21c_Fmt31c(CompilationUnit *cUnit, MIR *mir) * Obey the calling convention and don't mess with the register * usage. */ - ClassObject *classPtr = (void*) + ClassObject *classPtr = (ClassObject *) (cUnit->method->clazz->pDvmDex->pResClasses[mir->dalvikInsn.vB]); if (classPtr == NULL) { @@ -3008,12 +3009,13 @@ static bool handleFmt35c_3rc(CompilationUnit *cUnit, MIR *mir, BasicBlock *bb, */ if (pcrLabel == NULL) { int dPC = (int) (cUnit->method->insns + mir->offset); - pcrLabel = dvmCompilerNew(sizeof(ArmLIR), true); + pcrLabel = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); pcrLabel->opcode = kArmPseudoPCReconstructionCell; pcrLabel->operands[0] = dPC; pcrLabel->operands[1] = mir->offset; /* Insert the place holder to the growable list */ - dvmInsertGrowableList(&cUnit->pcReconstructionList, pcrLabel); + dvmInsertGrowableList(&cUnit->pcReconstructionList, + (intptr_t) pcrLabel); } /* return through lr+2 - punt to the interpreter */ @@ -3832,8 +3834,8 @@ static void genValidationForPredictedInline(CompilationUnit *cUnit, MIR *mir) static void handleExtendedMIR(CompilationUnit *cUnit, MIR *mir) { int opOffset = mir->dalvikInsn.opcode - kMirOpFirst; - char *msg = dvmCompilerNew(strlen(extendedMIROpNames[opOffset]) + 1, - false); + char *msg = (char *)dvmCompilerNew(strlen(extendedMIROpNames[opOffset]) + 1, + false); strcpy(msg, extendedMIROpNames[opOffset]); newLIR1(cUnit, kArmPseudoExtended, (int) msg); @@ -3880,25 +3882,25 @@ static void setupLoopEntryBlock(CompilationUnit *cUnit, BasicBlock *entry, ArmLIR *bodyLabel) { /* Set up the place holder to reconstruct this Dalvik PC */ - ArmLIR *pcrLabel = dvmCompilerNew(sizeof(ArmLIR), true); + ArmLIR *pcrLabel = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); pcrLabel->opcode = kArmPseudoPCReconstructionCell; pcrLabel->operands[0] = (int) (cUnit->method->insns + entry->startOffset); pcrLabel->operands[1] = entry->startOffset; /* Insert the place holder to the growable list */ - dvmInsertGrowableList(&cUnit->pcReconstructionList, pcrLabel); + dvmInsertGrowableList(&cUnit->pcReconstructionList, (intptr_t) pcrLabel); /* * Next, create two branches - one branch over to the loop body and the * other branch to the PCR cell to punt. */ - ArmLIR *branchToBody = dvmCompilerNew(sizeof(ArmLIR), true); + ArmLIR *branchToBody = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); branchToBody->opcode = kThumbBUncond; branchToBody->generic.target = (LIR *) bodyLabel; setupResourceMasks(branchToBody); cUnit->loopAnalysis->branchToBody = (LIR *) branchToBody; - ArmLIR *branchToPCR = dvmCompilerNew(sizeof(ArmLIR), true); + ArmLIR *branchToPCR = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); branchToPCR->opcode = kThumbBUncond; branchToPCR->generic.target = (LIR *) pcrLabel; setupResourceMasks(branchToPCR); @@ -3928,7 +3930,7 @@ void dvmCompilerMIR2LIR(CompilationUnit *cUnit) { /* Used to hold the labels of each block */ ArmLIR *labelList = - dvmCompilerNew(sizeof(ArmLIR) * cUnit->numBlocks, true); + (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR) * cUnit->numBlocks, true); GrowableList chainingListByType[kChainingCellGap]; int i; @@ -3939,7 +3941,8 @@ void dvmCompilerMIR2LIR(CompilationUnit *cUnit) dvmInitGrowableList(&chainingListByType[i], 2); } - BasicBlock **blockList = cUnit->blockList; + GrowableListIterator iterator; + dvmGrowableListIteratorInit(&cUnit->blockList, &iterator); if (cUnit->executionCount) { /* @@ -3976,14 +3979,15 @@ void dvmCompilerMIR2LIR(CompilationUnit *cUnit) } /* Handle the content in each basic block */ - for (i = 0; i < cUnit->numBlocks; i++) { - blockList[i]->visited = true; + for (i = 0; ; i++) { MIR *mir; + BasicBlock *bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator); + if (bb == NULL) break; - labelList[i].operands[0] = blockList[i]->startOffset; + labelList[i].operands[0] = bb->startOffset; - if (blockList[i]->blockType >= kChainingCellGap) { - if (blockList[i]->isFallThroughFromInvoke == true) { + if (bb->blockType >= kChainingCellGap) { + if (bb->isFallThroughFromInvoke == true) { /* Align this block first since it is a return chaining cell */ newLIR0(cUnit, kArmPseudoPseudoAlign4); } @@ -3994,56 +3998,53 @@ void dvmCompilerMIR2LIR(CompilationUnit *cUnit) dvmCompilerAppendLIR(cUnit, (LIR *) &labelList[i]); } - if (blockList[i]->blockType == kTraceEntryBlock) { + if (bb->blockType == kTraceEntryBlock) { labelList[i].opcode = kArmPseudoEntryBlock; - if (blockList[i]->firstMIRInsn == NULL) { + if (bb->firstMIRInsn == NULL) { continue; } else { - setupLoopEntryBlock(cUnit, blockList[i], - &labelList[blockList[i]->fallThrough->id]); + setupLoopEntryBlock(cUnit, bb, + &labelList[bb->fallThrough->id]); } - } else if (blockList[i]->blockType == kTraceExitBlock) { + } else if (bb->blockType == kTraceExitBlock) { labelList[i].opcode = kArmPseudoExitBlock; goto gen_fallthrough; - } else if (blockList[i]->blockType == kDalvikByteCode) { + } else if (bb->blockType == kDalvikByteCode) { labelList[i].opcode = kArmPseudoNormalBlockLabel; /* Reset the register state */ dvmCompilerResetRegPool(cUnit); dvmCompilerClobberAllRegs(cUnit); dvmCompilerResetNullCheck(cUnit); } else { - switch (blockList[i]->blockType) { + switch (bb->blockType) { case kChainingCellNormal: labelList[i].opcode = kArmPseudoChainingCellNormal; /* handle the codegen later */ dvmInsertGrowableList( - &chainingListByType[kChainingCellNormal], (void *) i); + &chainingListByType[kChainingCellNormal], i); break; case kChainingCellInvokeSingleton: labelList[i].opcode = kArmPseudoChainingCellInvokeSingleton; labelList[i].operands[0] = - (int) blockList[i]->containingMethod; + (int) bb->containingMethod; /* handle the codegen later */ dvmInsertGrowableList( - &chainingListByType[kChainingCellInvokeSingleton], - (void *) i); + &chainingListByType[kChainingCellInvokeSingleton], i); break; case kChainingCellInvokePredicted: labelList[i].opcode = kArmPseudoChainingCellInvokePredicted; /* handle the codegen later */ dvmInsertGrowableList( - &chainingListByType[kChainingCellInvokePredicted], - (void *) i); + &chainingListByType[kChainingCellInvokePredicted], i); break; case kChainingCellHot: labelList[i].opcode = kArmPseudoChainingCellHot; /* handle the codegen later */ dvmInsertGrowableList( - &chainingListByType[kChainingCellHot], - (void *) i); + &chainingListByType[kChainingCellHot], i); break; case kPCReconstruction: /* Make sure exception handling block is next */ @@ -4068,7 +4069,7 @@ void dvmCompilerMIR2LIR(CompilationUnit *cUnit) /* handle the codegen later */ dvmInsertGrowableList( &chainingListByType[kChainingCellBackwardBranch], - (void *) i); + i); break; #endif default: @@ -4079,7 +4080,7 @@ void dvmCompilerMIR2LIR(CompilationUnit *cUnit) ArmLIR *headLIR = NULL; - for (mir = blockList[i]->firstMIRInsn; mir; mir = mir->next) { + for (mir = bb->firstMIRInsn; mir; mir = mir->next) { dvmCompilerResetRegPool(cUnit); if (gDvmJit.disableOpt & (1 << kTrackLiveTemps)) { @@ -4147,7 +4148,7 @@ void dvmCompilerMIR2LIR(CompilationUnit *cUnit) case kFmt20t: case kFmt30t: notHandled = handleFmt10t_Fmt20t_Fmt30t(cUnit, - mir, blockList[i], labelList); + mir, bb, labelList); break; case kFmt10x: notHandled = handleFmt10x(cUnit, mir); @@ -4176,8 +4177,7 @@ void dvmCompilerMIR2LIR(CompilationUnit *cUnit) notHandled = handleFmt21s(cUnit, mir); break; case kFmt21t: - notHandled = handleFmt21t(cUnit, mir, blockList[i], - labelList); + notHandled = handleFmt21t(cUnit, mir, bb, labelList); break; case kFmt22b: case kFmt22s: @@ -4190,8 +4190,7 @@ void dvmCompilerMIR2LIR(CompilationUnit *cUnit) notHandled = handleFmt22cs(cUnit, mir); break; case kFmt22t: - notHandled = handleFmt22t(cUnit, mir, blockList[i], - labelList); + notHandled = handleFmt22t(cUnit, mir, bb, labelList); break; case kFmt22x: case kFmt32x: @@ -4205,12 +4204,12 @@ void dvmCompilerMIR2LIR(CompilationUnit *cUnit) break; case kFmt3rc: case kFmt35c: - notHandled = handleFmt35c_3rc(cUnit, mir, blockList[i], + notHandled = handleFmt35c_3rc(cUnit, mir, bb, labelList); break; case kFmt3rms: case kFmt35ms: - notHandled = handleFmt35ms_3rms(cUnit, mir,blockList[i], + notHandled = handleFmt35ms_3rms(cUnit, mir, bb, labelList); break; case kFmt35mi: @@ -4235,7 +4234,7 @@ void dvmCompilerMIR2LIR(CompilationUnit *cUnit) } } - if (blockList[i]->blockType == kTraceEntryBlock) { + if (bb->blockType == kTraceEntryBlock) { dvmCompilerAppendLIR(cUnit, (LIR *) cUnit->loopAnalysis->branchToBody); dvmCompilerAppendLIR(cUnit, @@ -4256,9 +4255,9 @@ gen_fallthrough: * Check if the block is terminated due to trace length constraint - * insert an unconditional branch to the chaining cell. */ - if (blockList[i]->needFallThroughBranch) { + if (bb->needFallThroughBranch) { genUnconditionalBranch(cUnit, - &labelList[blockList[i]->fallThrough->id]); + &labelList[bb->fallThrough->id]); } } @@ -4279,6 +4278,9 @@ gen_fallthrough: for (j = 0; j < chainingListByType[i].numUsed; j++) { int blockId = blockIdList[j]; + BasicBlock *chainingBlock = + (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, + blockId); /* Align this chaining cell first */ newLIR0(cUnit, kArmPseudoPseudoAlign4); @@ -4287,30 +4289,28 @@ gen_fallthrough: dvmCompilerAppendLIR(cUnit, (LIR *) &labelList[blockId]); - switch (blockList[blockId]->blockType) { + switch (chainingBlock->blockType) { case kChainingCellNormal: - handleNormalChainingCell(cUnit, - blockList[blockId]->startOffset); + handleNormalChainingCell(cUnit, chainingBlock->startOffset); break; case kChainingCellInvokeSingleton: handleInvokeSingletonChainingCell(cUnit, - blockList[blockId]->containingMethod); + chainingBlock->containingMethod); break; case kChainingCellInvokePredicted: handleInvokePredictedChainingCell(cUnit); break; case kChainingCellHot: - handleHotChainingCell(cUnit, - blockList[blockId]->startOffset); + handleHotChainingCell(cUnit, chainingBlock->startOffset); break; #if defined(WITH_SELF_VERIFICATION) || defined(WITH_JIT_TUNING) case kChainingCellBackwardBranch: handleBackwardBranchChainingCell(cUnit, - blockList[blockId]->startOffset); + chainingBlock->startOffset); break; #endif default: - LOGE("Bad blocktype %d", blockList[blockId]->blockType); + LOGE("Bad blocktype %d", chainingBlock->blockType); dvmCompilerAbort(cUnit); } } @@ -4345,6 +4345,7 @@ gen_fallthrough: /* Accept the work and start compiling */ bool dvmCompilerDoWork(CompilerWorkOrder *work) { + JitTraceDescription *desc; bool res; if (gDvmJit.codeCacheFull) { @@ -4354,14 +4355,16 @@ bool dvmCompilerDoWork(CompilerWorkOrder *work) switch (work->kind) { case kWorkOrderTrace: /* Start compilation with maximally allowed trace length */ - res = dvmCompileTrace(work->info, JIT_MAX_TRACE_LEN, &work->result, + desc = (JitTraceDescription *)work->info; + res = dvmCompileTrace(desc, JIT_MAX_TRACE_LEN, &work->result, work->bailPtr, 0 /* no hints */); break; case kWorkOrderTraceDebug: { bool oldPrintMe = gDvmJit.printMe; gDvmJit.printMe = true; /* Start compilation with maximally allowed trace length */ - res = dvmCompileTrace(work->info, JIT_MAX_TRACE_LEN, &work->result, + desc = (JitTraceDescription *)work->info; + res = dvmCompileTrace(desc, JIT_MAX_TRACE_LEN, &work->result, work->bailPtr, 0 /* no hints */); gDvmJit.printMe = oldPrintMe; break; diff --git a/vm/compiler/codegen/arm/LocalOptimizations.c b/vm/compiler/codegen/arm/LocalOptimizations.c index 33e1e4188..d91734fcf 100644 --- a/vm/compiler/codegen/arm/LocalOptimizations.c +++ b/vm/compiler/codegen/arm/LocalOptimizations.c @@ -147,7 +147,7 @@ static void applyLoadStoreElimination(CompilationUnit *cUnit, /* The store can be sunk for at least one cycle */ if (sinkDistance != 0) { ArmLIR *newStoreLIR = - dvmCompilerNew(sizeof(ArmLIR), true); + (ArmLIR *)dvmCompilerNew(sizeof(ArmLIR), true); *newStoreLIR = *thisLIR; newStoreLIR->age = cUnit->optRound; /* @@ -369,7 +369,7 @@ static void applyLoadHoisting(CompilationUnit *cUnit, /* The load can be hoisted for at least one cycle */ if (hoistDistance != 0) { ArmLIR *newLoadLIR = - dvmCompilerNew(sizeof(ArmLIR), true); + (ArmLIR *)dvmCompilerNew(sizeof(ArmLIR), true); *newLoadLIR = *thisLIR; newLoadLIR->age = cUnit->optRound; /* @@ -473,7 +473,7 @@ static void applyLoadHoisting(CompilationUnit *cUnit, /* The store can be hoisted for at least one cycle */ if (hoistDistance != 0) { ArmLIR *newLoadLIR = - dvmCompilerNew(sizeof(ArmLIR), true); + (ArmLIR *)dvmCompilerNew(sizeof(ArmLIR), true); *newLoadLIR = *thisLIR; newLoadLIR->age = cUnit->optRound; /* diff --git a/vm/compiler/codegen/arm/Thumb/Factory.c b/vm/compiler/codegen/arm/Thumb/Factory.c index af255a939..53dc2ce55 100644 --- a/vm/compiler/codegen/arm/Thumb/Factory.c +++ b/vm/compiler/codegen/arm/Thumb/Factory.c @@ -73,7 +73,7 @@ static ArmLIR *loadConstantNoClobber(CompilationUnit *cUnit, int rDest, if (dataTarget == NULL) { dataTarget = addWordData(cUnit, value, false); } - ArmLIR *loadPcRel = dvmCompilerNew(sizeof(ArmLIR), true); + ArmLIR *loadPcRel = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); loadPcRel->opcode = kThumbLdrPcRel; loadPcRel->generic.target = (LIR *) dataTarget; loadPcRel->operands[0] = tDest; @@ -819,7 +819,7 @@ static ArmLIR* genRegCopyNoInsert(CompilationUnit *cUnit, int rDest, int rSrc) { ArmLIR* res; ArmOpcode opcode; - res = dvmCompilerNew(sizeof(ArmLIR), true); + res = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); if (LOWREG(rDest) && LOWREG(rSrc)) opcode = kThumbMovRR; else if (!LOWREG(rDest) && !LOWREG(rSrc)) diff --git a/vm/compiler/codegen/arm/Thumb/Gen.c b/vm/compiler/codegen/arm/Thumb/Gen.c index 37cc18d97..07f3f092f 100644 --- a/vm/compiler/codegen/arm/Thumb/Gen.c +++ b/vm/compiler/codegen/arm/Thumb/Gen.c @@ -113,21 +113,15 @@ static void genLong3Addr(CompilationUnit *cUnit, MIR *mir, OpKind firstOp, void dvmCompilerInitializeRegAlloc(CompilationUnit *cUnit) { int numTemps = sizeof(coreTemps)/sizeof(int); - RegisterPool *pool = dvmCompilerNew(sizeof(*pool), true); + RegisterPool *pool = (RegisterPool *) dvmCompilerNew(sizeof(*pool), true); cUnit->regPool = pool; pool->numCoreTemps = numTemps; - pool->coreTemps = + pool->coreTemps = (RegisterInfo *) dvmCompilerNew(numTemps * sizeof(*pool->coreTemps), true); pool->numFPTemps = 0; pool->FPTemps = NULL; - pool->numCoreRegs = 0; - pool->coreRegs = NULL; - pool->numFPRegs = 0; - pool->FPRegs = NULL; dvmCompilerInitPool(pool->coreTemps, coreTemps, pool->numCoreTemps); dvmCompilerInitPool(pool->FPTemps, NULL, 0); - dvmCompilerInitPool(pool->coreRegs, NULL, 0); - dvmCompilerInitPool(pool->FPRegs, NULL, 0); pool->nullCheckedRegs = dvmCompilerAllocBitVector(cUnit->numSSARegs, false); } diff --git a/vm/compiler/codegen/arm/Thumb2/Factory.c b/vm/compiler/codegen/arm/Thumb2/Factory.c index 141c925fa..f50edfe32 100644 --- a/vm/compiler/codegen/arm/Thumb2/Factory.c +++ b/vm/compiler/codegen/arm/Thumb2/Factory.c @@ -60,7 +60,7 @@ static ArmLIR *loadFPConstantValue(CompilationUnit *cUnit, int rDest, if (dataTarget == NULL) { dataTarget = addWordData(cUnit, value, false); } - ArmLIR *loadPcRel = dvmCompilerNew(sizeof(ArmLIR), true); + ArmLIR *loadPcRel = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); loadPcRel->opcode = kThumb2Vldrs; loadPcRel->generic.target = (LIR *) dataTarget; loadPcRel->operands[0] = rDest; @@ -170,7 +170,7 @@ static ArmLIR *loadConstantNoClobber(CompilationUnit *cUnit, int rDest, if (dataTarget == NULL) { dataTarget = addWordData(cUnit, value, false); } - ArmLIR *loadPcRel = dvmCompilerNew(sizeof(ArmLIR), true); + ArmLIR *loadPcRel = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); loadPcRel->opcode = kThumb2LdrPcRel12; loadPcRel->generic.target = (LIR *) dataTarget; loadPcRel->operands[0] = rDest; @@ -1121,7 +1121,7 @@ static ArmLIR *genCmpImmBranch(CompilationUnit *cUnit, static ArmLIR *fpRegCopy(CompilationUnit *cUnit, int rDest, int rSrc) { - ArmLIR* res = dvmCompilerNew(sizeof(ArmLIR), true); + ArmLIR* res = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); res->operands[0] = rDest; res->operands[1] = rSrc; if (rDest == rSrc) { @@ -1151,7 +1151,7 @@ static ArmLIR* genRegCopyNoInsert(CompilationUnit *cUnit, int rDest, int rSrc) ArmOpcode opcode; if (FPREG(rDest) || FPREG(rSrc)) return fpRegCopy(cUnit, rDest, rSrc); - res = dvmCompilerNew(sizeof(ArmLIR), true); + res = (ArmLIR *) dvmCompilerNew(sizeof(ArmLIR), true); if (LOWREG(rDest) && LOWREG(rSrc)) opcode = kThumbMovRR; else if (!LOWREG(rDest) && !LOWREG(rSrc)) diff --git a/vm/compiler/codegen/arm/Thumb2/Gen.c b/vm/compiler/codegen/arm/Thumb2/Gen.c index 825b271a7..0891524f7 100644 --- a/vm/compiler/codegen/arm/Thumb2/Gen.c +++ b/vm/compiler/codegen/arm/Thumb2/Gen.c @@ -89,22 +89,16 @@ void dvmCompilerInitializeRegAlloc(CompilationUnit *cUnit) { int numTemps = sizeof(coreTemps)/sizeof(int); int numFPTemps = sizeof(fpTemps)/sizeof(int); - RegisterPool *pool = dvmCompilerNew(sizeof(*pool), true); + RegisterPool *pool = (RegisterPool *)dvmCompilerNew(sizeof(*pool), true); cUnit->regPool = pool; pool->numCoreTemps = numTemps; - pool->coreTemps = + pool->coreTemps = (RegisterInfo *) dvmCompilerNew(numTemps * sizeof(*cUnit->regPool->coreTemps), true); pool->numFPTemps = numFPTemps; - pool->FPTemps = + pool->FPTemps = (RegisterInfo *) dvmCompilerNew(numFPTemps * sizeof(*cUnit->regPool->FPTemps), true); - pool->numCoreRegs = 0; - pool->coreRegs = NULL; - pool->numFPRegs = 0; - pool->FPRegs = NULL; dvmCompilerInitPool(pool->coreTemps, coreTemps, pool->numCoreTemps); dvmCompilerInitPool(pool->FPTemps, fpTemps, pool->numFPTemps); - dvmCompilerInitPool(pool->coreRegs, NULL, 0); - dvmCompilerInitPool(pool->FPRegs, NULL, 0); pool->nullCheckedRegs = dvmCompilerAllocBitVector(cUnit->numSSARegs, false); } diff --git a/vm/compiler/codegen/x86/ArchUtility.c b/vm/compiler/codegen/x86/ArchUtility.c index 171c3b5ef..f7c48d628 100644 --- a/vm/compiler/codegen/x86/ArchUtility.c +++ b/vm/compiler/codegen/x86/ArchUtility.c @@ -22,3 +22,9 @@ void dvmCompilerCodegenDump(CompilationUnit *cUnit) { } + +/* Target-specific cache flushing (not needed for x86 */ +int dvmCompilerCacheFlush(long start, long end, long flags) +{ + return 0; +} diff --git a/vm/compiler/codegen/x86/Assemble.c b/vm/compiler/codegen/x86/Assemble.c index fbf53ca36..3c0b3c7d6 100644 --- a/vm/compiler/codegen/x86/Assemble.c +++ b/vm/compiler/codegen/x86/Assemble.c @@ -20,7 +20,6 @@ #include "../../CompilerInternals.h" #include "X86LIR.h" #include "Codegen.h" -#include <unistd.h> /* for cacheflush */ #include <sys/mman.h> /* for protection change */ #define MAX_ASSEMBLER_RETRIES 10 @@ -34,8 +33,6 @@ #endif /* - * FIXME - redo for x86 - * * Translation layout in the code cache. Note that the codeAddress pointer * in JitTable will point directly to the code body (field codeAddress). The * chain cell offset codeAddress - 2, and (if present) executionCount is at @@ -52,7 +49,7 @@ * | . . * | | | * | +----------------------------+ - * | | Chaining Cells | -> 12/16 bytes each, must be 4 byte aligned + * | | Chaining Cells | -> 16 bytes each, 8 byte aligned * | . . * | . . * | | | @@ -66,8 +63,8 @@ * | | * +----------------------------+ * | Literal pool | -> 4-byte aligned, variable size - * . . - * . . + * . . Note: for x86 literals will + * . . generally appear inline. * | | * +----------------------------+ * diff --git a/vm/compiler/codegen/x86/CodegenDriver.c b/vm/compiler/codegen/x86/CodegenDriver.c index 69f637ed7..4f31563ea 100644 --- a/vm/compiler/codegen/x86/CodegenDriver.c +++ b/vm/compiler/codegen/x86/CodegenDriver.c @@ -24,9 +24,64 @@ * applicable directory below this one. */ +extern X86LIR *loadConstant(CompilationUnit *cUnit, int rDest, int value); +extern X86LIR *loadWordDisp(CompilationUnit *cUnit, int rBase, + int displacement, int rDest); +extern void dvmCompilerFlushAllRegs(CompilationUnit *cUnit); +extern void storeWordDisp(CompilationUnit *cUnit, int rBase, + int displacement, int rSrc); +extern X86LIR *opReg(CompilationUnit *cUnit, OpKind op, int rDestSrc); + static int opcodeCoverage[kNumPackedOpcodes]; static intptr_t templateEntryOffsets[TEMPLATE_LAST_MARK]; +#if 0 // Avoid compiler warnings when x86 disabled during development +/* + * Bail to the interpreter. Will not return to this trace. + * On entry, rPC must be set correctly. + */ +static void genPuntToInterp(CompilationUnit *cUnit, unsigned int offset) +{ + dvmCompilerFlushAllRegs(cUnit); + loadConstant(cUnit, rPC, (int)(cUnit->method->insns + offset)); + loadWordDisp(cUnit, rEBP, 0, rECX); // Get glue + loadWordDisp(cUnit, rECX, + offsetof(InterpState, jitToInterpEntries.dvmJitToInterpPunt), + rEAX); + opReg(cUnit, kOpUncondBr, rEAX); +} + +static void genInterpSingleStep(CompilationUnit *cUnit, MIR *mir) +{ + int flags = dexGetFlagsFromOpcode(mir->dalvikInsn.opcode); + int flagsToCheck = kInstrCanBranch | kInstrCanSwitch | kInstrCanReturn | + kInstrCanThrow; + + //If already optimized out, just ignore + if (mir->dalvikInsn.opcode == OP_NOP) + return; + + //Ugly, but necessary. Flush all Dalvik regs so Interp can find them + dvmCompilerFlushAllRegs(cUnit); + + if ((mir->next == NULL) || (flags & flagsToCheck)) { + genPuntToInterp(cUnit, mir->offset); + return; + } + int entryAddr = offsetof(InterpState, + jitToInterpEntries.dvmJitToInterpSingleStep); + loadWordDisp(cUnit, rEBP, 0, rECX); // Get glue + loadWordDisp(cUnit, rECX, entryAddr, rEAX); // rEAX<- entry address + /* rPC = dalvik pc */ + loadConstant(cUnit, rPC, (int) (cUnit->method->insns + mir->offset)); + /* rECX = dalvik pc of following instruction */ + loadConstant(cUnit, rECX, (int) (cUnit->method->insns + mir->next->offset)); + /* Pass on the stack */ + storeWordDisp(cUnit, rESP, OUT_ARG0, rECX); + opReg(cUnit, kOpCall, rEAX); +} +#endif + /* * The following are the first-level codegen routines that analyze the format * of each bytecode then either dispatch special purpose codegen routines @@ -158,6 +213,7 @@ void dvmCompilerMIR2LIR(CompilationUnit *cUnit) /* Accept the work and start compiling */ bool dvmCompilerDoWork(CompilerWorkOrder *work) { + JitTraceDescription *desc; bool res; if (gDvmJit.codeCacheFull) { @@ -167,14 +223,16 @@ bool dvmCompilerDoWork(CompilerWorkOrder *work) switch (work->kind) { case kWorkOrderTrace: /* Start compilation with maximally allowed trace length */ - res = dvmCompileTrace(work->info, JIT_MAX_TRACE_LEN, &work->result, + desc = (JitTraceDescription *)work->info; + res = dvmCompileTrace(desc, JIT_MAX_TRACE_LEN, &work->result, work->bailPtr, 0 /* no hints */); break; case kWorkOrderTraceDebug: { bool oldPrintMe = gDvmJit.printMe; gDvmJit.printMe = true; /* Start compilation with maximally allowed trace length */ - res = dvmCompileTrace(work->info, JIT_MAX_TRACE_LEN, &work->result, + desc = (JitTraceDescription *)work->info; + res = dvmCompileTrace(desc, JIT_MAX_TRACE_LEN, &work->result, work->bailPtr, 0 /* no hints */); gDvmJit.printMe = oldPrintMe; break; diff --git a/vm/compiler/codegen/x86/X86LIR.h b/vm/compiler/codegen/x86/X86LIR.h index 62ac44733..19f08e1db 100644 --- a/vm/compiler/codegen/x86/X86LIR.h +++ b/vm/compiler/codegen/x86/X86LIR.h @@ -27,7 +27,7 @@ * esp is native SP * * For interpreter: - * edx is Dalvik PC (rPC) + * edi is Dalvik PC (rPC) * ebx is rINST * * For JIT: @@ -80,10 +80,6 @@ typedef struct RegisterPool { int numFPTemps; RegisterInfo *FPTemps; int nextFPTemp; - int numCoreRegs; - RegisterInfo *coreRegs; - int numFPRegs; - RegisterInfo *FPRegs; } RegisterPool; typedef enum OpSize { @@ -99,7 +95,6 @@ typedef enum OpSize { typedef enum OpKind { kOpMov, - kOpMvn, kOpCmp, kOpLsl, kOpLsr, @@ -114,15 +109,11 @@ typedef enum OpKind { kOpAdc, kOpSub, kOpSbc, - kOpRsub, kOpMul, kOpDiv, kOpRem, - kOpBic, - kOpCmn, kOpTst, - kOpBkpt, - kOpBlx, + kOpCall, kOpPush, kOpPop, kOp2Char, @@ -132,6 +123,37 @@ typedef enum OpKind { kOpUncondBr, } OpKind; +#define FP_REG_OFFSET 8 + +typedef enum NativeRegisterPool { + rEAX = 0, + rECX = 1, + rEDX = 2, + rEBX = 3, + rESP = 4, + rEBP = 5, + rESI = 6, + rEDI = 7, + rXMM0 = 0 + FP_REG_OFFSET, + rXMM1 = 1 + FP_REG_OFFSET, + rXMM2 = 2 + FP_REG_OFFSET, + rXMM3 = 3 + FP_REG_OFFSET, + rXMM4 = 4 + FP_REG_OFFSET, + rXMM5 = 5 + FP_REG_OFFSET, + rXMM6 = 6 + FP_REG_OFFSET, + rXMM7 = 7 + FP_REG_OFFSET, +} NativeRegisterPool; + +#define rPC rEDI +#define rFP rESI +#define rINST rEBX + +#define OUT_ARG0 0 +#define OUT_ARG1 4 +#define OUT_ARG2 8 +#define OUT_ARG3 12 +#define OUT_ARG4 16 + typedef struct X86LIR { LIR generic; //X86Opcode opcode; diff --git a/vm/compiler/template/ia32/TEMPLATE_INTERPRET.S b/vm/compiler/template/ia32/TEMPLATE_INTERPRET.S index 4c98917a3..68b2d0de0 100644 --- a/vm/compiler/template/ia32/TEMPLATE_INTERPRET.S +++ b/vm/compiler/template/ia32/TEMPLATE_INTERPRET.S @@ -1,27 +1,30 @@ /* - * TODO: figure out how best to do this on x86, as we don't have - * an lr equivalent and probably don't want to push. + * This handler is a bit odd - it may be called via chaining or + * from static code and is expected to cause control to flow + * to the interpreter. The problem is where to find the Dalvik + * PC of the next instruction. When called via chaining, the dPC + * will be located at *rp. When called from static code, rPC is + * valid and rp is a real return pointer (that should be ignored). + * The Arm target deals with this by using the link register as + * a flag. If it is zero, we know we were called from static code. + * If non-zero, it points to the chain cell containing dPC. + * For x86, we'll infer the source by looking where rp points. + * If it points to anywhere within the code cache, we'll assume + * we got here via chaining. Otherwise, we'll assume rPC is valid. * - * This handler transfers control to the interpeter without performing - * any lookups. It may be called either as part of a normal chaining - * operation, or from the transition code in header.S. We distinquish - * the two cases by looking at the link register. If called from a - * translation chain, it will point to the chaining Dalvik PC -3. * On entry: - * lr - if NULL: - * r1 - the Dalvik PC to begin interpretation. - * else - * [lr, #3] contains Dalvik PC to begin interpretation - * rGLUE - pointer to interpState - * rFP - Dalvik frame pointer - * - *cmp lr, #0 - *ldrne r1,[lr, #3] - *ldr r2, .LinterpPunt - *mov r0, r1 @ set Dalvik PC - *bx r2 - *@ doesn't return + * (TOS)<- return pointer or pointer to dPC */ + movl rGLUE,%ecx + movl $$.LinterpPunt,%edx + pop %eax + cmpl %eax,offGlue_jitCacheEnd(%ecx) + ja 1f + cmpl %eax,offGlue_jitCacheStart(%ecx) + jb 1f + movl %eax,rPC +1: + jmp *(%edx) .LinterpPunt: .long dvmJitToInterpPunt diff --git a/vm/compiler/template/ia32/footer.S b/vm/compiler/template/ia32/footer.S index 1b1a1aef0..d350c7739 100644 --- a/vm/compiler/template/ia32/footer.S +++ b/vm/compiler/template/ia32/footer.S @@ -6,14 +6,6 @@ .text .align 4 -/* - * FIXME - need a cacheflush for x86 - */ - .global cacheflush -cacheflush: - movl $$0xdeadf0f0, %eax - call *%eax - .global dmvCompilerTemplateEnd dmvCompilerTemplateEnd: diff --git a/vm/compiler/template/ia32/header.S b/vm/compiler/template/ia32/header.S index 57f5a5b1c..a67ba6e61 100644 --- a/vm/compiler/template/ia32/header.S +++ b/vm/compiler/template/ia32/header.S @@ -16,6 +16,12 @@ #if defined(WITH_JIT) +/* Subset of defines from mterp/x86/header.S */ +#define rGLUE (%ebp) +#define rPC %esi +#define rFP %edi +#define rINST %ebx + /* * This is a #include, not a %include, because we want the C pre-processor * to expand the macros into assembler assignment statements. diff --git a/vm/compiler/template/out/CompilerTemplateAsm-armv5te-vfp.S b/vm/compiler/template/out/CompilerTemplateAsm-armv5te-vfp.S index e1d052403..8efbcaa60 100644 --- a/vm/compiler/template/out/CompilerTemplateAsm-armv5te-vfp.S +++ b/vm/compiler/template/out/CompilerTemplateAsm-armv5te-vfp.S @@ -108,17 +108,6 @@ unspecified registers or condition codes. * =========================================================================== */ -/* - * Macro for "MOV LR,PC / LDR PC,xxx", which is not allowed pre-ARMv5. - * Jump to subroutine. - * - * May modify IP and LR. - */ -.macro LDR_PC_LR source - mov lr, pc - ldr pc, \source -.endm - .global dvmCompilerTemplateStart .type dvmCompilerTemplateStart, %function @@ -181,7 +170,8 @@ dvmCompiler_TEMPLATE_RETURN: stmfd sp!, {r0-r2,lr} @ preserve live registers mov r0, r6 @ r0=rGlue - LDR_PC_LR ".LdvmFastJavaMethodTraceExit" + mov lr, pc + ldr pc, .LdvmFastJavaMethodTraceExit ldmfd sp!, {r0-r2,lr} @ restore live registers #endif SAVEAREA_FROM_FP(r0, rFP) @ r0<- saveArea (old) @@ -285,7 +275,8 @@ dvmCompiler_TEMPLATE_INVOKE_METHOD_NO_OPT: stmfd sp!, {r0-r3} @ preserve r0-r3 mov r1, r6 @ r0=methodToCall, r1=rGlue - LDR_PC_LR ".LdvmFastMethodTraceEnter" + mov lr, pc + ldr pc, .LdvmFastMethodTraceEnter ldmfd sp!, {r0-r3} @ restore r0-r3 #endif @@ -344,7 +335,8 @@ dvmCompiler_TEMPLATE_INVOKE_METHOD_CHAIN: stmfd sp!, {r0-r2,lr} @ preserve clobbered live registers mov r1, r6 @ r0=methodToCall, r1=rGlue - LDR_PC_LR ".LdvmFastMethodTraceEnter" + mov lr, pc + ldr pc, .LdvmFastMethodTraceEnter ldmfd sp!, {r0-r2,lr} @ restore registers #endif @@ -468,7 +460,8 @@ dvmCompiler_TEMPLATE_INVOKE_METHOD_NATIVE: mov r0, r2 mov r1, r6 @ r0=JNIMethod, r1=rGlue - LDR_PC_LR ".LdvmFastMethodTraceEnter" + mov lr, pc + ldr pc, .LdvmFastMethodTraceEnter ldmfd sp!, {r0-r3} @ restore r0-r3 #endif @@ -477,7 +470,8 @@ dvmCompiler_TEMPLATE_INVOKE_METHOD_NATIVE: #if defined(WITH_INLINE_PROFILING) ldmfd sp!, {r0-r1} @ restore r2 and r6 @ r0=JNIMethod, r1=rGlue - LDR_PC_LR ".LdvmFastNativeMethodTraceExit" + mov lr, pc + ldr pc, .LdvmFastNativeMethodTraceExit #endif @ native return; r9=self, r10=newSaveArea @ equivalent to dvmPopJniLocals @@ -1511,15 +1505,18 @@ dvmCompiler_TEMPLATE_MONITOR_ENTER_DEBUG: stmfd sp!, {r0-r3} mov r0, r2 mov r1, r6 - LDR_PC_LR ".LdvmFastMethodTraceEnter" + mov lr, pc + ldr pc, .LdvmFastMethodTraceEnter ldmfd sp!, {r0-r3} #endif - LDR_PC_LR "[r2, #offMethod_nativeFunc]" + mov lr, pc + ldr pc, [r2, #offMethod_nativeFunc] #if defined(WITH_INLINE_PROFILING) ldmfd sp!, {r0-r1} - LDR_PC_LR ".LdvmFastNativeMethodTraceExit" + mov lr, pc + ldr pc, .LdvmFastNativeMethodTraceExit #endif @ Refresh Jit's on/off status ldr r3, [rGLUE, #offGlue_ppJitProfTable] diff --git a/vm/compiler/template/out/CompilerTemplateAsm-armv5te.S b/vm/compiler/template/out/CompilerTemplateAsm-armv5te.S index 5a47750ee..0df3ae65a 100644 --- a/vm/compiler/template/out/CompilerTemplateAsm-armv5te.S +++ b/vm/compiler/template/out/CompilerTemplateAsm-armv5te.S @@ -108,17 +108,6 @@ unspecified registers or condition codes. * =========================================================================== */ -/* - * Macro for "MOV LR,PC / LDR PC,xxx", which is not allowed pre-ARMv5. - * Jump to subroutine. - * - * May modify IP and LR. - */ -.macro LDR_PC_LR source - mov lr, pc - ldr pc, \source -.endm - .global dvmCompilerTemplateStart .type dvmCompilerTemplateStart, %function @@ -181,7 +170,8 @@ dvmCompiler_TEMPLATE_RETURN: stmfd sp!, {r0-r2,lr} @ preserve live registers mov r0, r6 @ r0=rGlue - LDR_PC_LR ".LdvmFastJavaMethodTraceExit" + mov lr, pc + ldr pc, .LdvmFastJavaMethodTraceExit ldmfd sp!, {r0-r2,lr} @ restore live registers #endif SAVEAREA_FROM_FP(r0, rFP) @ r0<- saveArea (old) @@ -285,7 +275,8 @@ dvmCompiler_TEMPLATE_INVOKE_METHOD_NO_OPT: stmfd sp!, {r0-r3} @ preserve r0-r3 mov r1, r6 @ r0=methodToCall, r1=rGlue - LDR_PC_LR ".LdvmFastMethodTraceEnter" + mov lr, pc + ldr pc, .LdvmFastMethodTraceEnter ldmfd sp!, {r0-r3} @ restore r0-r3 #endif @@ -344,7 +335,8 @@ dvmCompiler_TEMPLATE_INVOKE_METHOD_CHAIN: stmfd sp!, {r0-r2,lr} @ preserve clobbered live registers mov r1, r6 @ r0=methodToCall, r1=rGlue - LDR_PC_LR ".LdvmFastMethodTraceEnter" + mov lr, pc + ldr pc, .LdvmFastMethodTraceEnter ldmfd sp!, {r0-r2,lr} @ restore registers #endif @@ -468,7 +460,8 @@ dvmCompiler_TEMPLATE_INVOKE_METHOD_NATIVE: mov r0, r2 mov r1, r6 @ r0=JNIMethod, r1=rGlue - LDR_PC_LR ".LdvmFastMethodTraceEnter" + mov lr, pc + ldr pc, .LdvmFastMethodTraceEnter ldmfd sp!, {r0-r3} @ restore r0-r3 #endif @@ -477,7 +470,8 @@ dvmCompiler_TEMPLATE_INVOKE_METHOD_NATIVE: #if defined(WITH_INLINE_PROFILING) ldmfd sp!, {r0-r1} @ restore r2 and r6 @ r0=JNIMethod, r1=rGlue - LDR_PC_LR ".LdvmFastNativeMethodTraceExit" + mov lr, pc + ldr pc, .LdvmFastNativeMethodTraceExit #endif @ native return; r9=self, r10=newSaveArea @ equivalent to dvmPopJniLocals @@ -527,7 +521,8 @@ dvmCompiler_TEMPLATE_CMPG_DOUBLE: /* op vAA, vBB, vCC */ push {r0-r3} @ save operands mov r11, lr @ save return address - LDR_PC_LR ".L__aeabi_cdcmple" @ PIC way of "bl __aeabi_cdcmple" + mov lr, pc + ldr pc, .L__aeabi_cdcmple @ PIC way of "bl __aeabi_cdcmple" bhi .LTEMPLATE_CMPG_DOUBLE_gt_or_nan @ C set and Z clear, disambiguate mvncc r0, #0 @ (less than) r1<- -1 moveq r0, #0 @ (equal) r1<- 0, trumps less than @@ -540,7 +535,8 @@ dvmCompiler_TEMPLATE_CMPG_DOUBLE: .LTEMPLATE_CMPG_DOUBLE_gt_or_nan: pop {r2-r3} @ restore operands in reverse order pop {r0-r1} @ restore operands in reverse order - LDR_PC_LR ".L__aeabi_cdcmple" @ r0<- Z set if eq, C clear if < + mov lr, pc + ldr pc, .L__aeabi_cdcmple @ r0<- Z set if eq, C clear if < movcc r0, #1 @ (greater than) r1<- 1 bxcc r11 mov r0, #1 @ r1<- 1 or -1 for NaN @@ -569,7 +565,8 @@ dvmCompiler_TEMPLATE_CMPL_DOUBLE: /* op vAA, vBB, vCC */ push {r0-r3} @ save operands mov r11, lr @ save return address - LDR_PC_LR ".L__aeabi_cdcmple" @ PIC way of "bl __aeabi_cdcmple" + mov lr, pc + ldr pc, .L__aeabi_cdcmple @ PIC way of "bl __aeabi_cdcmple" bhi .LTEMPLATE_CMPL_DOUBLE_gt_or_nan @ C set and Z clear, disambiguate mvncc r0, #0 @ (less than) r1<- -1 moveq r0, #0 @ (equal) r1<- 0, trumps less than @@ -582,7 +579,8 @@ dvmCompiler_TEMPLATE_CMPL_DOUBLE: .LTEMPLATE_CMPL_DOUBLE_gt_or_nan: pop {r2-r3} @ restore operands in reverse order pop {r0-r1} @ restore operands in reverse order - LDR_PC_LR ".L__aeabi_cdcmple" @ r0<- Z set if eq, C clear if < + mov lr, pc + ldr pc, .L__aeabi_cdcmple @ r0<- Z set if eq, C clear if < movcc r0, #1 @ (greater than) r1<- 1 bxcc r11 mvn r0, #0 @ r1<- 1 or -1 for NaN @@ -631,7 +629,8 @@ dvmCompiler_TEMPLATE_CMPG_FLOAT: mov r9, r0 @ Save copies - we may need to redo mov r10, r1 mov r11, lr @ save return address - LDR_PC_LR ".L__aeabi_cfcmple" @ cmp <=: C clear if <, Z set if eq + mov lr, pc + ldr pc, .L__aeabi_cfcmple @ cmp <=: C clear if <, Z set if eq bhi .LTEMPLATE_CMPG_FLOAT_gt_or_nan @ C set and Z clear, disambiguate mvncc r0, #0 @ (less than) r0<- -1 moveq r0, #0 @ (equal) r0<- 0, trumps less than @@ -642,7 +641,8 @@ dvmCompiler_TEMPLATE_CMPG_FLOAT: .LTEMPLATE_CMPG_FLOAT_gt_or_nan: mov r0, r10 @ restore in reverse order mov r1, r9 - LDR_PC_LR ".L__aeabi_cfcmple" @ r0<- Z set if eq, C clear if < + mov lr, pc + ldr pc, .L__aeabi_cfcmple @ r0<- Z set if eq, C clear if < movcc r0, #1 @ (greater than) r1<- 1 bxcc r11 mov r0, #1 @ r1<- 1 or -1 for NaN @@ -691,7 +691,8 @@ dvmCompiler_TEMPLATE_CMPL_FLOAT: mov r9, r0 @ Save copies - we may need to redo mov r10, r1 mov r11, lr @ save return address - LDR_PC_LR ".L__aeabi_cfcmple" @ cmp <=: C clear if <, Z set if eq + mov lr, pc + ldr pc, .L__aeabi_cfcmple @ cmp <=: C clear if <, Z set if eq bhi .LTEMPLATE_CMPL_FLOAT_gt_or_nan @ C set and Z clear, disambiguate mvncc r0, #0 @ (less than) r0<- -1 moveq r0, #0 @ (equal) r0<- 0, trumps less than @@ -702,7 +703,8 @@ dvmCompiler_TEMPLATE_CMPL_FLOAT: .LTEMPLATE_CMPL_FLOAT_gt_or_nan: mov r0, r10 @ restore in reverse order mov r1, r9 - LDR_PC_LR ".L__aeabi_cfcmple" @ r0<- Z set if eq, C clear if < + mov lr, pc + ldr pc, .L__aeabi_cfcmple @ r0<- Z set if eq, C clear if < movcc r0, #1 @ (greater than) r1<- 1 bxcc r11 mvn r0, #0 @ r1<- 1 or -1 for NaN @@ -1234,15 +1236,18 @@ dvmCompiler_TEMPLATE_MONITOR_ENTER_DEBUG: stmfd sp!, {r0-r3} mov r0, r2 mov r1, r6 - LDR_PC_LR ".LdvmFastMethodTraceEnter" + mov lr, pc + ldr pc, .LdvmFastMethodTraceEnter ldmfd sp!, {r0-r3} #endif - LDR_PC_LR "[r2, #offMethod_nativeFunc]" + mov lr, pc + ldr pc, [r2, #offMethod_nativeFunc] #if defined(WITH_INLINE_PROFILING) ldmfd sp!, {r0-r1} - LDR_PC_LR ".LdvmFastNativeMethodTraceExit" + mov lr, pc + ldr pc, .LdvmFastNativeMethodTraceExit #endif @ Refresh Jit's on/off status ldr r3, [rGLUE, #offGlue_ppJitProfTable] diff --git a/vm/compiler/template/out/CompilerTemplateAsm-armv7-a-neon.S b/vm/compiler/template/out/CompilerTemplateAsm-armv7-a-neon.S index 9fb8892b3..ee3f8cbec 100644 --- a/vm/compiler/template/out/CompilerTemplateAsm-armv7-a-neon.S +++ b/vm/compiler/template/out/CompilerTemplateAsm-armv7-a-neon.S @@ -108,17 +108,6 @@ unspecified registers or condition codes. * =========================================================================== */ -/* - * Macro for "MOV LR,PC / LDR PC,xxx", which is not allowed pre-ARMv5. - * Jump to subroutine. - * - * May modify IP and LR. - */ -.macro LDR_PC_LR source - mov lr, pc - ldr pc, \source -.endm - .global dvmCompilerTemplateStart .type dvmCompilerTemplateStart, %function @@ -181,7 +170,8 @@ dvmCompiler_TEMPLATE_RETURN: stmfd sp!, {r0-r2,lr} @ preserve live registers mov r0, r6 @ r0=rGlue - LDR_PC_LR ".LdvmFastJavaMethodTraceExit" + mov lr, pc + ldr pc, .LdvmFastJavaMethodTraceExit ldmfd sp!, {r0-r2,lr} @ restore live registers #endif SAVEAREA_FROM_FP(r0, rFP) @ r0<- saveArea (old) @@ -285,7 +275,8 @@ dvmCompiler_TEMPLATE_INVOKE_METHOD_NO_OPT: stmfd sp!, {r0-r3} @ preserve r0-r3 mov r1, r6 @ r0=methodToCall, r1=rGlue - LDR_PC_LR ".LdvmFastMethodTraceEnter" + mov lr, pc + ldr pc, .LdvmFastMethodTraceEnter ldmfd sp!, {r0-r3} @ restore r0-r3 #endif @@ -344,7 +335,8 @@ dvmCompiler_TEMPLATE_INVOKE_METHOD_CHAIN: stmfd sp!, {r0-r2,lr} @ preserve clobbered live registers mov r1, r6 @ r0=methodToCall, r1=rGlue - LDR_PC_LR ".LdvmFastMethodTraceEnter" + mov lr, pc + ldr pc, .LdvmFastMethodTraceEnter ldmfd sp!, {r0-r2,lr} @ restore registers #endif @@ -468,7 +460,8 @@ dvmCompiler_TEMPLATE_INVOKE_METHOD_NATIVE: mov r0, r2 mov r1, r6 @ r0=JNIMethod, r1=rGlue - LDR_PC_LR ".LdvmFastMethodTraceEnter" + mov lr, pc + ldr pc, .LdvmFastMethodTraceEnter ldmfd sp!, {r0-r3} @ restore r0-r3 #endif @@ -477,7 +470,8 @@ dvmCompiler_TEMPLATE_INVOKE_METHOD_NATIVE: #if defined(WITH_INLINE_PROFILING) ldmfd sp!, {r0-r1} @ restore r2 and r6 @ r0=JNIMethod, r1=rGlue - LDR_PC_LR ".LdvmFastNativeMethodTraceExit" + mov lr, pc + ldr pc, .LdvmFastNativeMethodTraceExit #endif @ native return; r9=self, r10=newSaveArea @ equivalent to dvmPopJniLocals @@ -1511,15 +1505,18 @@ dvmCompiler_TEMPLATE_MONITOR_ENTER_DEBUG: stmfd sp!, {r0-r3} mov r0, r2 mov r1, r6 - LDR_PC_LR ".LdvmFastMethodTraceEnter" + mov lr, pc + ldr pc, .LdvmFastMethodTraceEnter ldmfd sp!, {r0-r3} #endif - LDR_PC_LR "[r2, #offMethod_nativeFunc]" + mov lr, pc + ldr pc, [r2, #offMethod_nativeFunc] #if defined(WITH_INLINE_PROFILING) ldmfd sp!, {r0-r1} - LDR_PC_LR ".LdvmFastNativeMethodTraceExit" + mov lr, pc + ldr pc, .LdvmFastNativeMethodTraceExit #endif @ Refresh Jit's on/off status ldr r3, [rGLUE, #offGlue_ppJitProfTable] diff --git a/vm/compiler/template/out/CompilerTemplateAsm-armv7-a.S b/vm/compiler/template/out/CompilerTemplateAsm-armv7-a.S index 6d40d6000..3875f5a24 100644 --- a/vm/compiler/template/out/CompilerTemplateAsm-armv7-a.S +++ b/vm/compiler/template/out/CompilerTemplateAsm-armv7-a.S @@ -108,17 +108,6 @@ unspecified registers or condition codes. * =========================================================================== */ -/* - * Macro for "MOV LR,PC / LDR PC,xxx", which is not allowed pre-ARMv5. - * Jump to subroutine. - * - * May modify IP and LR. - */ -.macro LDR_PC_LR source - mov lr, pc - ldr pc, \source -.endm - .global dvmCompilerTemplateStart .type dvmCompilerTemplateStart, %function @@ -181,7 +170,8 @@ dvmCompiler_TEMPLATE_RETURN: stmfd sp!, {r0-r2,lr} @ preserve live registers mov r0, r6 @ r0=rGlue - LDR_PC_LR ".LdvmFastJavaMethodTraceExit" + mov lr, pc + ldr pc, .LdvmFastJavaMethodTraceExit ldmfd sp!, {r0-r2,lr} @ restore live registers #endif SAVEAREA_FROM_FP(r0, rFP) @ r0<- saveArea (old) @@ -285,7 +275,8 @@ dvmCompiler_TEMPLATE_INVOKE_METHOD_NO_OPT: stmfd sp!, {r0-r3} @ preserve r0-r3 mov r1, r6 @ r0=methodToCall, r1=rGlue - LDR_PC_LR ".LdvmFastMethodTraceEnter" + mov lr, pc + ldr pc, .LdvmFastMethodTraceEnter ldmfd sp!, {r0-r3} @ restore r0-r3 #endif @@ -344,7 +335,8 @@ dvmCompiler_TEMPLATE_INVOKE_METHOD_CHAIN: stmfd sp!, {r0-r2,lr} @ preserve clobbered live registers mov r1, r6 @ r0=methodToCall, r1=rGlue - LDR_PC_LR ".LdvmFastMethodTraceEnter" + mov lr, pc + ldr pc, .LdvmFastMethodTraceEnter ldmfd sp!, {r0-r2,lr} @ restore registers #endif @@ -468,7 +460,8 @@ dvmCompiler_TEMPLATE_INVOKE_METHOD_NATIVE: mov r0, r2 mov r1, r6 @ r0=JNIMethod, r1=rGlue - LDR_PC_LR ".LdvmFastMethodTraceEnter" + mov lr, pc + ldr pc, .LdvmFastMethodTraceEnter ldmfd sp!, {r0-r3} @ restore r0-r3 #endif @@ -477,7 +470,8 @@ dvmCompiler_TEMPLATE_INVOKE_METHOD_NATIVE: #if defined(WITH_INLINE_PROFILING) ldmfd sp!, {r0-r1} @ restore r2 and r6 @ r0=JNIMethod, r1=rGlue - LDR_PC_LR ".LdvmFastNativeMethodTraceExit" + mov lr, pc + ldr pc, .LdvmFastNativeMethodTraceExit #endif @ native return; r9=self, r10=newSaveArea @ equivalent to dvmPopJniLocals @@ -1511,15 +1505,18 @@ dvmCompiler_TEMPLATE_MONITOR_ENTER_DEBUG: stmfd sp!, {r0-r3} mov r0, r2 mov r1, r6 - LDR_PC_LR ".LdvmFastMethodTraceEnter" + mov lr, pc + ldr pc, .LdvmFastMethodTraceEnter ldmfd sp!, {r0-r3} #endif - LDR_PC_LR "[r2, #offMethod_nativeFunc]" + mov lr, pc + ldr pc, [r2, #offMethod_nativeFunc] #if defined(WITH_INLINE_PROFILING) ldmfd sp!, {r0-r1} - LDR_PC_LR ".LdvmFastNativeMethodTraceExit" + mov lr, pc + ldr pc, .LdvmFastNativeMethodTraceExit #endif @ Refresh Jit's on/off status ldr r3, [rGLUE, #offGlue_ppJitProfTable] diff --git a/vm/compiler/template/out/CompilerTemplateAsm-ia32.S b/vm/compiler/template/out/CompilerTemplateAsm-ia32.S index 7726e9749..ae548e413 100644 --- a/vm/compiler/template/out/CompilerTemplateAsm-ia32.S +++ b/vm/compiler/template/out/CompilerTemplateAsm-ia32.S @@ -23,6 +23,12 @@ #if defined(WITH_JIT) +/* Subset of defines from mterp/x86/header.S */ +#define rGLUE (%ebp) +#define rPC %esi +#define rFP %edi +#define rINST %ebx + /* * This is a #include, not a %include, because we want the C pre-processor * to expand the macros into assembler assignment statements. @@ -51,29 +57,32 @@ dvmCompilerTemplateStart: dvmCompiler_TEMPLATE_INTERPRET: /* File: ia32/TEMPLATE_INTERPRET.S */ /* - * TODO: figure out how best to do this on x86, as we don't have - * an lr equivalent and probably don't want to push. + * This handler is a bit odd - it may be called via chaining or + * from static code and is expected to cause control to flow + * to the interpreter. The problem is where to find the Dalvik + * PC of the next instruction. When called via chaining, the dPC + * will be located at *rp. When called from static code, rPC is + * valid and rp is a real return pointer (that should be ignored). + * The Arm target deals with this by using the link register as + * a flag. If it is zero, we know we were called from static code. + * If non-zero, it points to the chain cell containing dPC. + * For x86, we'll infer the source by looking where rp points. + * If it points to anywhere within the code cache, we'll assume + * we got here via chaining. Otherwise, we'll assume rPC is valid. * - * This handler transfers control to the interpeter without performing - * any lookups. It may be called either as part of a normal chaining - * operation, or from the transition code in header.S. We distinquish - * the two cases by looking at the link register. If called from a - * translation chain, it will point to the chaining Dalvik PC -3. * On entry: - * lr - if NULL: - * r1 - the Dalvik PC to begin interpretation. - * else - * [lr, #3] contains Dalvik PC to begin interpretation - * rGLUE - pointer to interpState - * rFP - Dalvik frame pointer - * - *cmp lr, #0 - *ldrne r1,[lr, #3] - *ldr r2, .LinterpPunt - *mov r0, r1 @ set Dalvik PC - *bx r2 - *@ doesn't return + * (TOS)<- return pointer or pointer to dPC */ + movl rGLUE,%ecx + movl $.LinterpPunt,%edx + pop %eax + cmpl %eax,offGlue_jitCacheEnd(%ecx) + ja 1f + cmpl %eax,offGlue_jitCacheStart(%ecx) + jb 1f + movl %eax,rPC +1: + jmp *(%edx) .LinterpPunt: .long dvmJitToInterpPunt @@ -88,14 +97,6 @@ dvmCompiler_TEMPLATE_INTERPRET: .text .align 4 -/* - * FIXME - need a cacheflush for x86 - */ - .global cacheflush -cacheflush: - movl $0xdeadf0f0, %eax - call *%eax - .global dmvCompilerTemplateEnd dmvCompilerTemplateEnd: |