diff options
Diffstat (limited to 'vm/compiler/Loop.cpp')
| -rw-r--r-- | vm/compiler/Loop.cpp | 752 |
1 files changed, 752 insertions, 0 deletions
diff --git a/vm/compiler/Loop.cpp b/vm/compiler/Loop.cpp new file mode 100644 index 0000000..90c97d7 --- /dev/null +++ b/vm/compiler/Loop.cpp @@ -0,0 +1,752 @@ +/* + * Copyright (C) 2009 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 "CompilerInternals.h" +#include "Dataflow.h" +#include "Loop.h" + +#define DEBUG_LOOP(X) + +#if 0 +/* Debugging routines */ +static void dumpConstants(CompilationUnit *cUnit) +{ + int i; + LOGE("LOOP starting offset: %x", cUnit->entryBlock->startOffset); + for (i = 0; i < cUnit->numSSARegs; i++) { + if (dvmIsBitSet(cUnit->isConstantV, i)) { + int subNReg = dvmConvertSSARegToDalvik(cUnit, i); + LOGE("CONST: s%d(v%d_%d) has %d", i, + DECODE_REG(subNReg), DECODE_SUB(subNReg), + cUnit->constantValues[i]); + } + } +} + +static void dumpIVList(CompilationUnit *cUnit) +{ + unsigned int i; + GrowableList *ivList = cUnit->loopAnalysis->ivList; + + for (i = 0; i < ivList->numUsed; i++) { + InductionVariableInfo *ivInfo = + (InductionVariableInfo *) ivList->elemList[i]; + int iv = dvmConvertSSARegToDalvik(cUnit, ivInfo->ssaReg); + /* Basic IV */ + if (ivInfo->ssaReg == ivInfo->basicSSAReg) { + LOGE("BIV %d: s%d(v%d_%d) + %d", i, + ivInfo->ssaReg, + DECODE_REG(iv), DECODE_SUB(iv), + ivInfo->inc); + /* Dependent IV */ + } else { + int biv = dvmConvertSSARegToDalvik(cUnit, ivInfo->basicSSAReg); + + LOGE("DIV %d: s%d(v%d_%d) = %d * s%d(v%d_%d) + %d", i, + ivInfo->ssaReg, + DECODE_REG(iv), DECODE_SUB(iv), + ivInfo->m, + ivInfo->basicSSAReg, + DECODE_REG(biv), DECODE_SUB(biv), + ivInfo->c); + } + } +} + +static void dumpHoistedChecks(CompilationUnit *cUnit) +{ + LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; + unsigned int i; + + for (i = 0; i < loopAnalysis->arrayAccessInfo->numUsed; i++) { + ArrayAccessInfo *arrayAccessInfo = + GET_ELEM_N(loopAnalysis->arrayAccessInfo, + ArrayAccessInfo*, i); + int arrayReg = DECODE_REG( + dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->arrayReg)); + int idxReg = DECODE_REG( + dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->ivReg)); + LOGE("Array access %d", i); + LOGE(" arrayReg %d", arrayReg); + LOGE(" idxReg %d", idxReg); + LOGE(" endReg %d", loopAnalysis->endConditionReg); + LOGE(" maxC %d", arrayAccessInfo->maxC); + LOGE(" minC %d", arrayAccessInfo->minC); + LOGE(" opcode %d", loopAnalysis->loopBranchOpcode); + } +} + +#endif + +static BasicBlock *findPredecessorBlock(const CompilationUnit *cUnit, + const BasicBlock *bb) +{ + int numPred = dvmCountSetBits(bb->predecessors); + BitVectorIterator bvIterator; + dvmBitVectorIteratorInit(bb->predecessors, &bvIterator); + + if (numPred == 1) { + int predIdx = dvmBitVectorIteratorNext(&bvIterator); + return (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, + predIdx); + /* First loop block */ + } else if ((numPred == 2) && + dvmIsBitSet(bb->predecessors, cUnit->entryBlock->id)) { + while (true) { + int predIdx = dvmBitVectorIteratorNext(&bvIterator); + if (predIdx == cUnit->entryBlock->id) continue; + return (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, + predIdx); + } + /* Doesn't support other shape of control flow yet */ + } else { + return NULL; + } +} + +/* Used for normalized loop exit condition checks */ +static Opcode negateOpcode(Opcode opcode) +{ + switch (opcode) { + /* reg/reg cmp */ + case OP_IF_EQ: + return OP_IF_NE; + case OP_IF_NE: + return OP_IF_EQ; + case OP_IF_LT: + return OP_IF_GE; + case OP_IF_GE: + return OP_IF_LT; + case OP_IF_GT: + return OP_IF_LE; + case OP_IF_LE: + return OP_IF_GT; + /* reg/zero cmp */ + case OP_IF_EQZ: + return OP_IF_NEZ; + case OP_IF_NEZ: + return OP_IF_EQZ; + case OP_IF_LTZ: + return OP_IF_GEZ; + case OP_IF_GEZ: + return OP_IF_LTZ; + case OP_IF_GTZ: + return OP_IF_LEZ; + case OP_IF_LEZ: + return OP_IF_GTZ; + default: + LOGE("opcode %d cannot be negated", opcode); + dvmAbort(); + break; + } + return (Opcode)-1; // unreached +} + +/* + * A loop is considered optimizable if: + * 1) It has one basic induction variable. + * 2) The loop back branch compares the BIV with a constant. + * 3) We need to normalize the loop exit condition so that the loop is exited + * via the taken path. + * 4) If it is a count-up loop, the condition is GE/GT. Otherwise it is + * LE/LT/LEZ/LTZ for a count-down loop. + * + * Return false for loops that fail the above tests. + */ +static bool isSimpleCountedLoop(CompilationUnit *cUnit) +{ + unsigned int i; + BasicBlock *loopBackBlock = cUnit->entryBlock->fallThrough; + LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; + + if (loopAnalysis->numBasicIV != 1) return false; + for (i = 0; i < loopAnalysis->ivList->numUsed; i++) { + InductionVariableInfo *ivInfo; + + ivInfo = GET_ELEM_N(loopAnalysis->ivList, InductionVariableInfo*, i); + /* Count up or down loop? */ + if (ivInfo->ssaReg == ivInfo->basicSSAReg) { + /* Infinite loop */ + if (ivInfo->inc == 0) { + return false; + } + loopAnalysis->isCountUpLoop = ivInfo->inc > 0; + break; + } + } + + /* Find the block that ends with a branch to exit the loop */ + while (true) { + loopBackBlock = findPredecessorBlock(cUnit, loopBackBlock); + /* Loop structure not recognized as counted blocks */ + if (loopBackBlock == NULL) { + return false; + } + /* Unconditional goto - continue to trace up the predecessor chain */ + if (loopBackBlock->taken == NULL) { + continue; + } + break; + } + + MIR *branch = loopBackBlock->lastMIRInsn; + Opcode opcode = branch->dalvikInsn.opcode; + + /* Last instruction is not a conditional branch - bail */ + if (dexGetFlagsFromOpcode(opcode) != (kInstrCanContinue|kInstrCanBranch)) { + return false; + } + + int endSSAReg; + int endDalvikReg; + + /* reg/reg comparison */ + if (branch->ssaRep->numUses == 2) { + if (branch->ssaRep->uses[0] == loopAnalysis->ssaBIV) { + endSSAReg = branch->ssaRep->uses[1]; + } else if (branch->ssaRep->uses[1] == loopAnalysis->ssaBIV) { + endSSAReg = branch->ssaRep->uses[0]; + opcode = negateOpcode(opcode); + } else { + return false; + } + endDalvikReg = dvmConvertSSARegToDalvik(cUnit, endSSAReg); + /* + * If the comparison is not between the BIV and a loop invariant, + * return false. endDalvikReg is loop invariant if one of the + * following is true: + * - It is not defined in the loop (ie DECODE_SUB returns 0) + * - It is reloaded with a constant + */ + if ((DECODE_SUB(endDalvikReg) != 0) && + !dvmIsBitSet(cUnit->isConstantV, endSSAReg)) { + return false; + } + /* Compare against zero */ + } else if (branch->ssaRep->numUses == 1) { + if (branch->ssaRep->uses[0] == loopAnalysis->ssaBIV) { + /* Keep the compiler happy */ + endDalvikReg = -1; + } else { + return false; + } + } else { + return false; + } + + /* Normalize the loop exit check as "if (iv op end) exit;" */ + if (loopBackBlock->taken->blockType == kDalvikByteCode) { + opcode = negateOpcode(opcode); + } + + if (loopAnalysis->isCountUpLoop) { + /* + * If the normalized condition op is not > or >=, this is not an + * optimization candidate. + */ + switch (opcode) { + case OP_IF_GT: + case OP_IF_GE: + break; + default: + return false; + } + loopAnalysis->endConditionReg = DECODE_REG(endDalvikReg); + } else { + /* + * If the normalized condition op is not < or <=, this is not an + * optimization candidate. + */ + switch (opcode) { + case OP_IF_LT: + case OP_IF_LE: + loopAnalysis->endConditionReg = DECODE_REG(endDalvikReg); + break; + case OP_IF_LTZ: + case OP_IF_LEZ: + break; + default: + return false; + } + } + /* + * Remember the normalized opcode, which will be used to determine the end + * value used for the yanked range checks. + */ + loopAnalysis->loopBranchOpcode = opcode; + return true; +} + +/* + * Record the upper and lower bound information for range checks for each + * induction variable. If array A is accessed by index "i+5", the upper and + * lower bound will be len(A)-5 and -5, respectively. + */ +static void updateRangeCheckInfo(CompilationUnit *cUnit, int arrayReg, + int idxReg) +{ + InductionVariableInfo *ivInfo; + LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; + unsigned int i, j; + + for (i = 0; i < loopAnalysis->ivList->numUsed; i++) { + ivInfo = GET_ELEM_N(loopAnalysis->ivList, InductionVariableInfo*, i); + if (ivInfo->ssaReg == idxReg) { + ArrayAccessInfo *arrayAccessInfo = NULL; + for (j = 0; j < loopAnalysis->arrayAccessInfo->numUsed; j++) { + ArrayAccessInfo *existingArrayAccessInfo = + GET_ELEM_N(loopAnalysis->arrayAccessInfo, + ArrayAccessInfo*, + j); + if (existingArrayAccessInfo->arrayReg == arrayReg) { + if (ivInfo->c > existingArrayAccessInfo->maxC) { + existingArrayAccessInfo->maxC = ivInfo->c; + } + if (ivInfo->c < existingArrayAccessInfo->minC) { + existingArrayAccessInfo->minC = ivInfo->c; + } + arrayAccessInfo = existingArrayAccessInfo; + break; + } + } + if (arrayAccessInfo == NULL) { + arrayAccessInfo = + (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, + (intptr_t) arrayAccessInfo); + } + break; + } + } +} + +/* Returns true if the loop body cannot throw any exceptions */ +static bool doLoopBodyCodeMotion(CompilationUnit *cUnit) +{ + BasicBlock *loopBody = cUnit->entryBlock->fallThrough; + MIR *mir; + bool loopBodyCanThrow = false; + + for (mir = loopBody->firstMIRInsn; mir; mir = mir->next) { + DecodedInstruction *dInsn = &mir->dalvikInsn; + int dfAttributes = + dvmCompilerDataFlowAttributes[mir->dalvikInsn.opcode]; + + /* Skip extended MIR instructions */ + if (dInsn->opcode >= kNumPackedOpcodes) continue; + + int instrFlags = dexGetFlagsFromOpcode(dInsn->opcode); + + /* Instruction is clean */ + if ((instrFlags & kInstrCanThrow) == 0) continue; + + /* + * Currently we can only optimize away null and range checks. Punt on + * instructions that can throw due to other exceptions. + */ + if (!(dfAttributes & DF_HAS_NR_CHECKS)) { + loopBodyCanThrow = true; + continue; + } + + /* + * This comparison is redundant now, but we will have more than one + * group of flags to check soon. + */ + if (dfAttributes & DF_HAS_NR_CHECKS) { + /* + * Check if the null check is applied on a loop invariant register? + * If the register's SSA id is less than the number of Dalvik + * registers, then it is loop invariant. + */ + int refIdx; + switch (dfAttributes & DF_HAS_NR_CHECKS) { + case DF_NULL_N_RANGE_CHECK_0: + refIdx = 0; + break; + case DF_NULL_N_RANGE_CHECK_1: + refIdx = 1; + break; + case DF_NULL_N_RANGE_CHECK_2: + refIdx = 2; + break; + default: + refIdx = 0; + LOGE("Jit: bad case in doLoopBodyCodeMotion"); + dvmCompilerAbort(cUnit); + } + + int useIdx = refIdx + 1; + int subNRegArray = + dvmConvertSSARegToDalvik(cUnit, mir->ssaRep->uses[refIdx]); + int arraySub = DECODE_SUB(subNRegArray); + + /* + * If the register is never updated in the loop (ie subscript == 0), + * it is an optimization candidate. + */ + if (arraySub != 0) { + loopBodyCanThrow = true; + continue; + } + + /* + * Then check if the range check can be hoisted out of the loop if + * it is basic or dependent induction variable. + */ + if (dvmIsBitSet(cUnit->loopAnalysis->isIndVarV, + mir->ssaRep->uses[useIdx])) { + mir->OptimizationFlags |= + MIR_IGNORE_RANGE_CHECK | MIR_IGNORE_NULL_CHECK; + updateRangeCheckInfo(cUnit, mir->ssaRep->uses[refIdx], + mir->ssaRep->uses[useIdx]); + } + } + } + + return !loopBodyCanThrow; +} + +static void genHoistedChecks(CompilationUnit *cUnit) +{ + unsigned int i; + BasicBlock *entry = cUnit->entryBlock; + LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; + int globalMaxC = 0; + int globalMinC = 0; + /* Should be loop invariant */ + int idxReg = 0; + + for (i = 0; i < loopAnalysis->arrayAccessInfo->numUsed; i++) { + ArrayAccessInfo *arrayAccessInfo = + GET_ELEM_N(loopAnalysis->arrayAccessInfo, + ArrayAccessInfo*, i); + int arrayReg = DECODE_REG( + dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->arrayReg)); + idxReg = DECODE_REG( + dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->ivReg)); + + MIR *rangeCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); + rangeCheckMIR->dalvikInsn.opcode = (loopAnalysis->isCountUpLoop) ? + (Opcode)kMirOpNullNRangeUpCheck : (Opcode)kMirOpNullNRangeDownCheck; + rangeCheckMIR->dalvikInsn.vA = arrayReg; + rangeCheckMIR->dalvikInsn.vB = idxReg; + rangeCheckMIR->dalvikInsn.vC = loopAnalysis->endConditionReg; + rangeCheckMIR->dalvikInsn.arg[0] = arrayAccessInfo->maxC; + rangeCheckMIR->dalvikInsn.arg[1] = arrayAccessInfo->minC; + rangeCheckMIR->dalvikInsn.arg[2] = loopAnalysis->loopBranchOpcode; + dvmCompilerAppendMIR(entry, rangeCheckMIR); + if (arrayAccessInfo->maxC > globalMaxC) { + globalMaxC = arrayAccessInfo->maxC; + } + if (arrayAccessInfo->minC < globalMinC) { + globalMinC = arrayAccessInfo->minC; + } + } + + if (loopAnalysis->arrayAccessInfo->numUsed != 0) { + if (loopAnalysis->isCountUpLoop) { + MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); + boundCheckMIR->dalvikInsn.opcode = (Opcode)kMirOpLowerBound; + boundCheckMIR->dalvikInsn.vA = idxReg; + boundCheckMIR->dalvikInsn.vB = globalMinC; + dvmCompilerAppendMIR(entry, boundCheckMIR); + } else { + if (loopAnalysis->loopBranchOpcode == OP_IF_LT || + loopAnalysis->loopBranchOpcode == OP_IF_LE) { + MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); + boundCheckMIR->dalvikInsn.opcode = (Opcode)kMirOpLowerBound; + boundCheckMIR->dalvikInsn.vA = loopAnalysis->endConditionReg; + boundCheckMIR->dalvikInsn.vB = globalMinC; + /* + * If the end condition is ">" in the source, the check in the + * Dalvik bytecode is OP_IF_LE. In this case add 1 back to the + * constant field to reflect the fact that the smallest index + * value is "endValue + constant + 1". + */ + if (loopAnalysis->loopBranchOpcode == OP_IF_LE) { + boundCheckMIR->dalvikInsn.vB++; + } + dvmCompilerAppendMIR(entry, boundCheckMIR); + } else if (loopAnalysis->loopBranchOpcode == OP_IF_LTZ) { + /* Array index will fall below 0 */ + if (globalMinC < 0) { + MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), + true); + boundCheckMIR->dalvikInsn.opcode = (Opcode)kMirOpPunt; + dvmCompilerAppendMIR(entry, boundCheckMIR); + } + } else if (loopAnalysis->loopBranchOpcode == OP_IF_LEZ) { + /* Array index will fall below 0 */ + if (globalMinC < -1) { + MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), + true); + boundCheckMIR->dalvikInsn.opcode = (Opcode)kMirOpPunt; + dvmCompilerAppendMIR(entry, boundCheckMIR); + } + } else { + LOGE("Jit: bad case in genHoistedChecks"); + dvmCompilerAbort(cUnit); + } + } + } +} + +void resetBlockEdges(BasicBlock *bb) +{ + bb->taken = NULL; + bb->fallThrough = NULL; + bb->successorBlockList.blockListType = kNotUsed; +} + +static bool clearPredecessorVector(struct CompilationUnit *cUnit, + struct BasicBlock *bb) +{ + dvmClearAllBits(bb->predecessors); + return false; +} + +bool dvmCompilerFilterLoopBlocks(CompilationUnit *cUnit) +{ + BasicBlock *firstBB = cUnit->entryBlock->fallThrough; + + int numPred = dvmCountSetBits(firstBB->predecessors); + /* + * A loop body should have at least two incoming edges. + */ + if (numPred < 2) return false; + + GrowableList *blockList = &cUnit->blockList; + + /* Record blocks included in the loop */ + dvmClearAllBits(cUnit->tempBlockV); + + dvmCompilerSetBit(cUnit->tempBlockV, cUnit->entryBlock->id); + dvmCompilerSetBit(cUnit->tempBlockV, firstBB->id); + + BasicBlock *bodyBB = firstBB; + + /* + * First try to include the fall-through block in the loop, then the taken + * block. Stop loop formation on the first backward branch that enters the + * first block (ie only include the inner-most loop). + */ + while (true) { + /* Loop formed */ + if (bodyBB->taken == firstBB) { + /* Check if the fallThrough edge will cause a nested loop */ + if (bodyBB->fallThrough && + dvmIsBitSet(cUnit->tempBlockV, bodyBB->fallThrough->id)) { + return false; + } + /* Single loop formed */ + break; + } else if (bodyBB->fallThrough == firstBB) { + /* Check if the taken edge will cause a nested loop */ + if (bodyBB->taken && + dvmIsBitSet(cUnit->tempBlockV, bodyBB->taken->id)) { + return false; + } + /* Single loop formed */ + break; + } + + /* Inner loops formed first - quit */ + if (bodyBB->fallThrough && + dvmIsBitSet(cUnit->tempBlockV, bodyBB->fallThrough->id)) { + return false; + } + if (bodyBB->taken && + dvmIsBitSet(cUnit->tempBlockV, bodyBB->taken->id)) { + return false; + } + + if (bodyBB->fallThrough) { + if (bodyBB->fallThrough->iDom == bodyBB) { + bodyBB = bodyBB->fallThrough; + dvmCompilerSetBit(cUnit->tempBlockV, bodyBB->id); + /* + * Loop formation to be detected at the beginning of next + * iteration. + */ + continue; + } + } + if (bodyBB->taken) { + if (bodyBB->taken->iDom == bodyBB) { + bodyBB = bodyBB->taken; + dvmCompilerSetBit(cUnit->tempBlockV, bodyBB->id); + /* + * Loop formation to be detected at the beginning of next + * iteration. + */ + continue; + } + } + /* + * Current block is not the immediate dominator of either fallthrough + * nor taken block - bail out of loop formation. + */ + return false; + } + + + /* Now mark blocks not included in the loop as hidden */ + GrowableListIterator iterator; + dvmGrowableListIteratorInit(blockList, &iterator); + while (true) { + BasicBlock *bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator); + if (bb == NULL) break; + if (!dvmIsBitSet(cUnit->tempBlockV, bb->id)) { + bb->hidden = true; + /* Clear the insn list */ + bb->firstMIRInsn = bb->lastMIRInsn = NULL; + resetBlockEdges(bb); + } + } + + dvmCompilerDataFlowAnalysisDispatcher(cUnit, clearPredecessorVector, + kAllNodes, false /* isIterative */); + + dvmGrowableListIteratorInit(blockList, &iterator); + while (true) { + BasicBlock *bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator); + if (bb == NULL) break; + if (dvmIsBitSet(cUnit->tempBlockV, bb->id)) { + if (bb->taken) { + /* + * exit block means we run into control-flow that we don't want + * to handle. + */ + if (bb->taken == cUnit->exitBlock) { + return false; + } + if (bb->taken->hidden) { + bb->taken->blockType = kChainingCellNormal; + bb->taken->hidden = false; + } + dvmCompilerSetBit(bb->taken->predecessors, bb->id); + } + if (bb->fallThrough) { + /* + * exit block means we run into control-flow that we don't want + * to handle. + */ + if (bb->fallThrough == cUnit->exitBlock) { + return false; + } + if (bb->fallThrough->hidden) { + bb->fallThrough->blockType = kChainingCellNormal; + bb->fallThrough->hidden = false; + } + dvmCompilerSetBit(bb->fallThrough->predecessors, bb->id); + } + /* Loop blocks shouldn't contain any successor blocks (yet) */ + assert(bb->successorBlockList.blockListType == kNotUsed); + } + } + return true; +} + +/* + * Main entry point to do loop optimization. + * Return false if sanity checks for loop formation/optimization failed. + */ +bool dvmCompilerLoopOpt(CompilationUnit *cUnit) +{ + LoopAnalysis *loopAnalysis = + (LoopAnalysis *)dvmCompilerNew(sizeof(LoopAnalysis), true); + cUnit->loopAnalysis = loopAnalysis; + + /* Constant propagation */ + cUnit->isConstantV = dvmAllocBitVector(cUnit->numSSARegs, false); + cUnit->constantValues = + (int *)dvmCompilerNew(sizeof(int) * cUnit->numSSARegs, + true); + dvmCompilerDataFlowAnalysisDispatcher(cUnit, + dvmCompilerDoConstantPropagation, + kAllNodes, + false /* isIterative */); + DEBUG_LOOP(dumpConstants(cUnit);) + + /* Find induction variables - basic and dependent */ + loopAnalysis->ivList = + (GrowableList *)dvmCompilerNew(sizeof(GrowableList), true); + dvmInitGrowableList(loopAnalysis->ivList, 4); + loopAnalysis->isIndVarV = dvmAllocBitVector(cUnit->numSSARegs, false); + dvmCompilerDataFlowAnalysisDispatcher(cUnit, + dvmCompilerFindInductionVariables, + kAllNodes, + false /* isIterative */); + DEBUG_LOOP(dumpIVList(cUnit);) + + /* Only optimize array accesses for simple counted loop for now */ + if (!isSimpleCountedLoop(cUnit)) + return false; + + loopAnalysis->arrayAccessInfo = + (GrowableList *)dvmCompilerNew(sizeof(GrowableList), true); + dvmInitGrowableList(loopAnalysis->arrayAccessInfo, 4); + loopAnalysis->bodyIsClean = doLoopBodyCodeMotion(cUnit); + DEBUG_LOOP(dumpHoistedChecks(cUnit);) + + /* + * Convert the array access information into extended MIR code in the loop + * header. + */ + genHoistedChecks(cUnit); + return true; +} + +/* + * Select the target block of the backward branch. + */ +void dvmCompilerInsertBackwardChaining(CompilationUnit *cUnit) +{ + /* + * If we are not in self-verification or profiling mode, the backward + * branch can go to the entryBlock->fallThrough directly. Suspend polling + * code will be generated along the backward branch to honor the suspend + * requests. + */ +#if !defined(WITH_SELF_VERIFICATION) + if (gDvmJit.profileMode != kTraceProfilingContinuous && + gDvmJit.profileMode != kTraceProfilingPeriodicOn) { + return; + } +#endif + /* + * In self-verification or profiling mode, the backward branch is altered + * to go to the backward chaining cell. Without using the backward chaining + * cell we won't be able to do check-pointing on the target PC, or count the + * number of iterations accurately. + */ + BasicBlock *firstBB = cUnit->entryBlock->fallThrough; + BasicBlock *backBranchBB = findPredecessorBlock(cUnit, firstBB); + if (backBranchBB->taken == firstBB) { + backBranchBB->taken = cUnit->backChainBlock; + } else { + assert(backBranchBB->fallThrough == firstBB); + backBranchBB->fallThrough = cUnit->backChainBlock; + } + cUnit->backChainBlock->startOffset = firstBB->startOffset; +} |