/*
* 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;
ALOGE("LOOP starting offset: %x", cUnit->entryBlock->startOffset);
for (i = 0; i < cUnit->numSSARegs; i++) {
if (dvmIsBitSet(cUnit->isConstantV, i)) {
int subNReg = dvmConvertSSARegToDalvik(cUnit, i);
ALOGE("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) {
ALOGE("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);
ALOGE("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));
ALOGE("Array access %d", i);
ALOGE(" arrayReg %d", arrayReg);
ALOGE(" idxReg %d", idxReg);
ALOGE(" endReg %d", loopAnalysis->endConditionReg);
ALOGE(" maxC %d", arrayAccessInfo->maxC);
ALOGE(" minC %d", arrayAccessInfo->minC);
ALOGE(" 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:
ALOGE("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 ((u2) 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;
ALOGE("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 {
ALOGE("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 = dvmCompilerAllocBitVector(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 = dvmCompilerAllocBitVector(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.
*/
#ifndef ARCH_IA32
#if !defined(WITH_SELF_VERIFICATION)
if (gDvmJit.profileMode != kTraceProfilingContinuous &&
gDvmJit.profileMode != kTraceProfilingPeriodicOn) {
return;
}
#endif
#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;
}