path: root/vm/compiler/Loop.cpp

/*
 * 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;
        }
    }
}

__attribute__((weak)) void dvmCompilerDumpMIRInCodeMotion(CompilationUnit *cUnit, MIR *mir)
{
    if(cUnit->printMe){
        DecodedInstruction *decInsn = &(mir->dalvikInsn);
        char *decodedString = dvmCompilerGetDalvikDisassembly(decInsn, NULL);
        ALOGD("%#06x %s", decInsn->opcode, decodedString);
    }
}

/* 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 =
            dvmGetDexOptAttributes(&mir->dalvikInsn);

        /* 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]);
            }
            dvmCompilerDumpMIRInCodeMotion(cUnit, mir);
        }
    }

    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);
            }
        }
        cUnit->hasHoistedChecks=true;
    }
}

void resetBlockEdges(BasicBlock *bb)
{
    bb->taken = NULL;
    bb->fallThrough = NULL;
    bb->successorBlockList.blockListType = kNotUsed;
}

static bool clearPredecessorVector(struct CompilationUnit *cUnit,
                                   struct BasicBlock *bb)
{
    dvmClearAllBits(bb->predecessors);
    return false;
}

bool dvmCompilerFilterLoopBlocks(CompilationUnit *cUnit)
{
    BasicBlock *firstBB = cUnit->entryBlock->fallThrough;

    int numPred = dvmCountSetBits(firstBB->predecessors);
    /*
     * A loop body should have at least two incoming edges.
     */
    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;
}

__attribute__((weak)) void dvmCompilerDumpIVList(CompilationUnit *cUnit)
{
    unsigned int i;
    GrowableList *ivList = cUnit->loopAnalysis->ivList;

    if(cUnit->printMe){
        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) {
                ALOGD("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);

                ALOGD("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);
            }
        }
    }
}

__attribute__((weak)) void dvmCompilerDumpHoistedChecks(CompilationUnit *cUnit)
{
    LoopAnalysis *loopAnalysis = cUnit->loopAnalysis;
    unsigned int i;
    if(cUnit->printMe){
        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));
            ALOGD("Array access %d", i);
            ALOGD("  arrayReg %d", arrayReg);
            ALOGD("  idxReg %d", idxReg);
            ALOGD("  endReg %d", loopAnalysis->endConditionReg);
            ALOGD("  maxC %d", arrayAccessInfo->maxC);
            ALOGD("  minC %d", arrayAccessInfo->minC);
            ALOGD("  opcode %d", loopAnalysis->loopBranchOpcode);
        }
    }
}

/*
 * 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);)

    dvmCompilerDumpIVList(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);
    dvmCompilerDumpHoistedChecks(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;
}