vm/compiler/Loop.cpp

   1 /*
   2  * Copyright (C) 2009 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include "Dalvik.h"
  18 #include "CompilerInternals.h"
  19 #include "Dataflow.h"
  20 #include "Loop.h"
  21
  22 #define DEBUG_LOOP(X)
  23
  24 #if 0
  25 /* Debugging routines */
  26 static void dumpConstants(CompilationUnit *cUnit)
  27 {
  28     int i;
  29     LOGE("LOOP starting offset: %x", cUnit->entryBlock->startOffset);
  30     for (i = 0; i < cUnit->numSSARegs; i++) {
  31         if (dvmIsBitSet(cUnit->isConstantV, i)) {
  32             int subNReg = dvmConvertSSARegToDalvik(cUnit, i);
  33             LOGE("CONST: s%d(v%d_%d) has %d", i,
  34                  DECODE_REG(subNReg), DECODE_SUB(subNReg),
  35                  cUnit->constantValues[i]);
  36         }
  37     }
  38 }
  39
  40 static void dumpIVList(CompilationUnit *cUnit)
  41 {
  42     unsigned int i;
  43     GrowableList *ivList = cUnit->loopAnalysis->ivList;
  44
  45     for (i = 0; i < ivList->numUsed; i++) {
  46         InductionVariableInfo *ivInfo =
  47             (InductionVariableInfo *) ivList->elemList[i];
  48         int iv = dvmConvertSSARegToDalvik(cUnit, ivInfo->ssaReg);
  49         /* Basic IV */
  50         if (ivInfo->ssaReg == ivInfo->basicSSAReg) {
  51             LOGE("BIV %d: s%d(v%d_%d) + %d", i,
  52                  ivInfo->ssaReg,
  53                  DECODE_REG(iv), DECODE_SUB(iv),
  54                  ivInfo->inc);
  55         /* Dependent IV */
  56         } else {
  57             int biv = dvmConvertSSARegToDalvik(cUnit, ivInfo->basicSSAReg);
  58
  59             LOGE("DIV %d: s%d(v%d_%d) = %d * s%d(v%d_%d) + %d", i,
  60                  ivInfo->ssaReg,
  61                  DECODE_REG(iv), DECODE_SUB(iv),
  62                  ivInfo->m,
  63                  ivInfo->basicSSAReg,
  64                  DECODE_REG(biv), DECODE_SUB(biv),
  65                  ivInfo->c);
  66         }
  67     }
  68 }
  69
  70 static void dumpHoistedChecks(CompilationUnit *cUnit)
  71 {
  72     LoopAnalysis *loopAnalysis = cUnit->loopAnalysis;
  73     unsigned int i;
  74
  75     for (i = 0; i < loopAnalysis->arrayAccessInfo->numUsed; i++) {
  76         ArrayAccessInfo *arrayAccessInfo =
  77             GET_ELEM_N(loopAnalysis->arrayAccessInfo,
  78                        ArrayAccessInfo*, i);
  79         int arrayReg = DECODE_REG(
  80             dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->arrayReg));
  81         int idxReg = DECODE_REG(
  82             dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->ivReg));
  83         LOGE("Array access %d", i);
  84         LOGE("  arrayReg %d", arrayReg);
  85         LOGE("  idxReg %d", idxReg);
  86         LOGE("  endReg %d", loopAnalysis->endConditionReg);
  87         LOGE("  maxC %d", arrayAccessInfo->maxC);
  88         LOGE("  minC %d", arrayAccessInfo->minC);
  89         LOGE("  opcode %d", loopAnalysis->loopBranchOpcode);
  90     }
  91 }
  92
  93 #endif
  94
  95 static BasicBlock *findPredecessorBlock(const CompilationUnit *cUnit,
  96                                         const BasicBlock *bb)
  97 {
  98     int numPred = dvmCountSetBits(bb->predecessors);
  99     BitVectorIterator bvIterator;
 100     dvmBitVectorIteratorInit(bb->predecessors, &bvIterator);
 101
 102     if (numPred == 1) {
 103         int predIdx = dvmBitVectorIteratorNext(&bvIterator);
 104         return (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList,
 105                                                         predIdx);
 106     /* First loop block */
 107     } else if ((numPred == 2) &&
 108                dvmIsBitSet(bb->predecessors, cUnit->entryBlock->id)) {
 109         while (true) {
 110             int predIdx = dvmBitVectorIteratorNext(&bvIterator);
 111             if (predIdx == cUnit->entryBlock->id) continue;
 112             return (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList,
 113                                                             predIdx);
 114         }
 115     /* Doesn't support other shape of control flow yet */
 116     } else {
 117         return NULL;
 118     }
 119 }
 120
 121 /* Used for normalized loop exit condition checks */
 122 static Opcode negateOpcode(Opcode opcode)
 123 {
 124     switch (opcode) {
 125         /* reg/reg cmp */
 126         case OP_IF_EQ:
 127             return OP_IF_NE;
 128         case OP_IF_NE:
 129             return OP_IF_EQ;
 130         case OP_IF_LT:
 131             return OP_IF_GE;
 132         case OP_IF_GE:
 133             return OP_IF_LT;
 134         case OP_IF_GT:
 135             return OP_IF_LE;
 136         case OP_IF_LE:
 137             return OP_IF_GT;
 138         /* reg/zero cmp */
 139         case OP_IF_EQZ:
 140             return OP_IF_NEZ;
 141         case OP_IF_NEZ:
 142             return OP_IF_EQZ;
 143         case OP_IF_LTZ:
 144             return OP_IF_GEZ;
 145         case OP_IF_GEZ:
 146             return OP_IF_LTZ;
 147         case OP_IF_GTZ:
 148             return OP_IF_LEZ;
 149         case OP_IF_LEZ:
 150             return OP_IF_GTZ;
 151         default:
 152             LOGE("opcode %d cannot be negated", opcode);
 153             dvmAbort();
 154             break;
 155     }
 156     return (Opcode)-1;  // unreached
 157 }
 158
 159 /*
 160  * A loop is considered optimizable if:
 161  * 1) It has one basic induction variable.
 162  * 2) The loop back branch compares the BIV with a constant.
 163  * 3) We need to normalize the loop exit condition so that the loop is exited
 164  *    via the taken path.
 165  * 4) If it is a count-up loop, the condition is GE/GT. Otherwise it is
 166  *    LE/LT/LEZ/LTZ for a count-down loop.
 167  *
 168  * Return false for loops that fail the above tests.
 169  */
 170 static bool isSimpleCountedLoop(CompilationUnit *cUnit)
 171 {
 172     unsigned int i;
 173     BasicBlock *loopBackBlock = cUnit->entryBlock->fallThrough;
 174     LoopAnalysis *loopAnalysis = cUnit->loopAnalysis;
 175
 176     if (loopAnalysis->numBasicIV != 1) return false;
 177     for (i = 0; i < loopAnalysis->ivList->numUsed; i++) {
 178         InductionVariableInfo *ivInfo;
 179
 180         ivInfo = GET_ELEM_N(loopAnalysis->ivList, InductionVariableInfo*, i);
 181         /* Count up or down loop? */
 182         if (ivInfo->ssaReg == ivInfo->basicSSAReg) {
 183             /* Infinite loop */
 184             if (ivInfo->inc == 0) {
 185                 return false;
 186             }
 187             loopAnalysis->isCountUpLoop = ivInfo->inc > 0;
 188             break;
 189         }
 190     }
 191
 192     /* Find the block that ends with a branch to exit the loop */
 193     while (true) {
 194         loopBackBlock = findPredecessorBlock(cUnit, loopBackBlock);
 195         /* Loop structure not recognized as counted blocks */
 196         if (loopBackBlock == NULL) {
 197             return false;
 198         }
 199         /* Unconditional goto - continue to trace up the predecessor chain */
 200         if (loopBackBlock->taken == NULL) {
 201             continue;
 202         }
 203         break;
 204     }
 205
 206     MIR *branch = loopBackBlock->lastMIRInsn;
 207     Opcode opcode = branch->dalvikInsn.opcode;
 208
 209     /* Last instruction is not a conditional branch - bail */
 210     if (dexGetFlagsFromOpcode(opcode) != (kInstrCanContinue|kInstrCanBranch)) {
 211         return false;
 212     }
 213
 214     int endSSAReg;
 215     int endDalvikReg;
 216
 217     /* reg/reg comparison */
 218     if (branch->ssaRep->numUses == 2) {
 219         if (branch->ssaRep->uses[0] == loopAnalysis->ssaBIV) {
 220             endSSAReg = branch->ssaRep->uses[1];
 221         } else if (branch->ssaRep->uses[1] == loopAnalysis->ssaBIV) {
 222             endSSAReg = branch->ssaRep->uses[0];
 223             opcode = negateOpcode(opcode);
 224         } else {
 225             return false;
 226         }
 227         endDalvikReg = dvmConvertSSARegToDalvik(cUnit, endSSAReg);
 228         /*
 229          * If the comparison is not between the BIV and a loop invariant,
 230          * return false. endDalvikReg is loop invariant if one of the
 231          * following is true:
 232          * - It is not defined in the loop (ie DECODE_SUB returns 0)
 233          * - It is reloaded with a constant
 234          */
 235         if ((DECODE_SUB(endDalvikReg) != 0) &&
 236             !dvmIsBitSet(cUnit->isConstantV, endSSAReg)) {
 237             return false;
 238         }
 239     /* Compare against zero */
 240     } else if (branch->ssaRep->numUses == 1) {
 241         if (branch->ssaRep->uses[0] == loopAnalysis->ssaBIV) {
 242             /* Keep the compiler happy */
 243             endDalvikReg = -1;
 244         } else {
 245             return false;
 246         }
 247     } else {
 248         return false;
 249     }
 250
 251     /* Normalize the loop exit check as "if (iv op end) exit;" */
 252     if (loopBackBlock->taken->blockType == kDalvikByteCode) {
 253         opcode = negateOpcode(opcode);
 254     }
 255
 256     if (loopAnalysis->isCountUpLoop) {
 257         /*
 258          * If the normalized condition op is not > or >=, this is not an
 259          * optimization candidate.
 260          */
 261         switch (opcode) {
 262             case OP_IF_GT:
 263             case OP_IF_GE:
 264                 break;
 265             default:
 266                 return false;
 267         }
 268         loopAnalysis->endConditionReg = DECODE_REG(endDalvikReg);
 269     } else  {
 270         /*
 271          * If the normalized condition op is not < or <=, this is not an
 272          * optimization candidate.
 273          */
 274         switch (opcode) {
 275             case OP_IF_LT:
 276             case OP_IF_LE:
 277                 loopAnalysis->endConditionReg = DECODE_REG(endDalvikReg);
 278                 break;
 279             case OP_IF_LTZ:
 280             case OP_IF_LEZ:
 281                 break;
 282             default:
 283                 return false;
 284         }
 285     }
 286     /*
 287      * Remember the normalized opcode, which will be used to determine the end
 288      * value used for the yanked range checks.
 289      */
 290     loopAnalysis->loopBranchOpcode = opcode;
 291     return true;
 292 }
 293
 294 /*
 295  * Record the upper and lower bound information for range checks for each
 296  * induction variable. If array A is accessed by index "i+5", the upper and
 297  * lower bound will be len(A)-5 and -5, respectively.
 298  */
 299 static void updateRangeCheckInfo(CompilationUnit *cUnit, int arrayReg,
 300                                  int idxReg)
 301 {
 302     InductionVariableInfo *ivInfo;
 303     LoopAnalysis *loopAnalysis = cUnit->loopAnalysis;
 304     unsigned int i, j;
 305
 306     for (i = 0; i < loopAnalysis->ivList->numUsed; i++) {
 307         ivInfo = GET_ELEM_N(loopAnalysis->ivList, InductionVariableInfo*, i);
 308         if (ivInfo->ssaReg == idxReg) {
 309             ArrayAccessInfo *arrayAccessInfo = NULL;
 310             for (j = 0; j < loopAnalysis->arrayAccessInfo->numUsed; j++) {
 311                 ArrayAccessInfo *existingArrayAccessInfo =
 312                     GET_ELEM_N(loopAnalysis->arrayAccessInfo,
 313                                ArrayAccessInfo*,
 314                                j);
 315                 if (existingArrayAccessInfo->arrayReg == arrayReg) {
 316                     if (ivInfo->c > existingArrayAccessInfo->maxC) {
 317                         existingArrayAccessInfo->maxC = ivInfo->c;
 318                     }
 319                     if (ivInfo->c < existingArrayAccessInfo->minC) {
 320                         existingArrayAccessInfo->minC = ivInfo->c;
 321                     }
 322                     arrayAccessInfo = existingArrayAccessInfo;
 323                     break;
 324                 }
 325             }
 326             if (arrayAccessInfo == NULL) {
 327                 arrayAccessInfo =
 328                     (ArrayAccessInfo *)dvmCompilerNew(sizeof(ArrayAccessInfo),
 329                                                       false);
 330                 arrayAccessInfo->ivReg = ivInfo->basicSSAReg;
 331                 arrayAccessInfo->arrayReg = arrayReg;
 332                 arrayAccessInfo->maxC = (ivInfo->c > 0) ? ivInfo->c : 0;
 333                 arrayAccessInfo->minC = (ivInfo->c < 0) ? ivInfo->c : 0;
 334                 dvmInsertGrowableList(loopAnalysis->arrayAccessInfo,
 335                                       (intptr_t) arrayAccessInfo);
 336             }
 337             break;
 338         }
 339     }
 340 }
 341
 342 /* Returns true if the loop body cannot throw any exceptions */
 343 static bool doLoopBodyCodeMotion(CompilationUnit *cUnit)
 344 {
 345     BasicBlock *loopBody = cUnit->entryBlock->fallThrough;
 346     MIR *mir;
 347     bool loopBodyCanThrow = false;
 348
 349     for (mir = loopBody->firstMIRInsn; mir; mir = mir->next) {
 350         DecodedInstruction *dInsn = &mir->dalvikInsn;
 351         int dfAttributes =
 352             dvmCompilerDataFlowAttributes[mir->dalvikInsn.opcode];
 353
 354         /* Skip extended MIR instructions */
 355         if (dInsn->opcode >= kNumPackedOpcodes) continue;
 356
 357         int instrFlags = dexGetFlagsFromOpcode(dInsn->opcode);
 358
 359         /* Instruction is clean */
 360         if ((instrFlags & kInstrCanThrow) == 0) continue;
 361
 362         /*
 363          * Currently we can only optimize away null and range checks. Punt on
 364          * instructions that can throw due to other exceptions.
 365          */
 366         if (!(dfAttributes & DF_HAS_NR_CHECKS)) {
 367             loopBodyCanThrow = true;
 368             continue;
 369         }
 370
 371         /*
 372          * This comparison is redundant now, but we will have more than one
 373          * group of flags to check soon.
 374          */
 375         if (dfAttributes & DF_HAS_NR_CHECKS) {
 376             /*
 377              * Check if the null check is applied on a loop invariant register?
 378              * If the register's SSA id is less than the number of Dalvik
 379              * registers, then it is loop invariant.
 380              */
 381             int refIdx;
 382             switch (dfAttributes & DF_HAS_NR_CHECKS) {
 383                 case DF_NULL_N_RANGE_CHECK_0:
 384                     refIdx = 0;
 385                     break;
 386                 case DF_NULL_N_RANGE_CHECK_1:
 387                     refIdx = 1;
 388                     break;
 389                 case DF_NULL_N_RANGE_CHECK_2:
 390                     refIdx = 2;
 391                     break;
 392                 default:
 393                     refIdx = 0;
 394                     LOGE("Jit: bad case in doLoopBodyCodeMotion");
 395                     dvmCompilerAbort(cUnit);
 396             }
 397
 398             int useIdx = refIdx + 1;
 399             int subNRegArray =
 400                 dvmConvertSSARegToDalvik(cUnit, mir->ssaRep->uses[refIdx]);
 401             int arraySub = DECODE_SUB(subNRegArray);
 402
 403             /*
 404              * If the register is never updated in the loop (ie subscript == 0),
 405              * it is an optimization candidate.
 406              */
 407             if (arraySub != 0) {
 408                 loopBodyCanThrow = true;
 409                 continue;
 410             }
 411
 412             /*
 413              * Then check if the range check can be hoisted out of the loop if
 414              * it is basic or dependent induction variable.
 415              */
 416             if (dvmIsBitSet(cUnit->loopAnalysis->isIndVarV,
 417                             mir->ssaRep->uses[useIdx])) {
 418                 mir->OptimizationFlags |=
 419                     MIR_IGNORE_RANGE_CHECK | MIR_IGNORE_NULL_CHECK;
 420                 updateRangeCheckInfo(cUnit, mir->ssaRep->uses[refIdx],
 421                                      mir->ssaRep->uses[useIdx]);
 422             }
 423         }
 424     }
 425
 426     return !loopBodyCanThrow;
 427 }
 428
 429 static void genHoistedChecks(CompilationUnit *cUnit)
 430 {
 431     unsigned int i;
 432     BasicBlock *entry = cUnit->entryBlock;
 433     LoopAnalysis *loopAnalysis = cUnit->loopAnalysis;
 434     int globalMaxC = 0;
 435     int globalMinC = 0;
 436     /* Should be loop invariant */
 437     int idxReg = 0;
 438
 439     for (i = 0; i < loopAnalysis->arrayAccessInfo->numUsed; i++) {
 440         ArrayAccessInfo *arrayAccessInfo =
 441             GET_ELEM_N(loopAnalysis->arrayAccessInfo,
 442                        ArrayAccessInfo*, i);
 443         int arrayReg = DECODE_REG(
 444             dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->arrayReg));
 445         idxReg = DECODE_REG(
 446             dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->ivReg));
 447
 448         MIR *rangeCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true);
 449         rangeCheckMIR->dalvikInsn.opcode = (loopAnalysis->isCountUpLoop) ?
 450             (Opcode)kMirOpNullNRangeUpCheck : (Opcode)kMirOpNullNRangeDownCheck;
 451         rangeCheckMIR->dalvikInsn.vA = arrayReg;
 452         rangeCheckMIR->dalvikInsn.vB = idxReg;
 453         rangeCheckMIR->dalvikInsn.vC = loopAnalysis->endConditionReg;
 454         rangeCheckMIR->dalvikInsn.arg[0] = arrayAccessInfo->maxC;
 455         rangeCheckMIR->dalvikInsn.arg[1] = arrayAccessInfo->minC;
 456         rangeCheckMIR->dalvikInsn.arg[2] = loopAnalysis->loopBranchOpcode;
 457         dvmCompilerAppendMIR(entry, rangeCheckMIR);
 458         if (arrayAccessInfo->maxC > globalMaxC) {
 459             globalMaxC = arrayAccessInfo->maxC;
 460         }
 461         if (arrayAccessInfo->minC < globalMinC) {
 462             globalMinC = arrayAccessInfo->minC;
 463         }
 464     }
 465
 466     if (loopAnalysis->arrayAccessInfo->numUsed != 0) {
 467         if (loopAnalysis->isCountUpLoop) {
 468             MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true);
 469             boundCheckMIR->dalvikInsn.opcode = (Opcode)kMirOpLowerBound;
 470             boundCheckMIR->dalvikInsn.vA = idxReg;
 471             boundCheckMIR->dalvikInsn.vB = globalMinC;
 472             dvmCompilerAppendMIR(entry, boundCheckMIR);
 473         } else {
 474             if (loopAnalysis->loopBranchOpcode == OP_IF_LT ||
 475                 loopAnalysis->loopBranchOpcode == OP_IF_LE) {
 476                 MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true);
 477                 boundCheckMIR->dalvikInsn.opcode = (Opcode)kMirOpLowerBound;
 478                 boundCheckMIR->dalvikInsn.vA = loopAnalysis->endConditionReg;
 479                 boundCheckMIR->dalvikInsn.vB = globalMinC;
 480                 /*
 481                  * If the end condition is ">" in the source, the check in the
 482                  * Dalvik bytecode is OP_IF_LE. In this case add 1 back to the
 483                  * constant field to reflect the fact that the smallest index
 484                  * value is "endValue + constant + 1".
 485                  */
 486                 if (loopAnalysis->loopBranchOpcode == OP_IF_LE) {
 487                     boundCheckMIR->dalvikInsn.vB++;
 488                 }
 489                 dvmCompilerAppendMIR(entry, boundCheckMIR);
 490             } else if (loopAnalysis->loopBranchOpcode == OP_IF_LTZ) {
 491                 /* Array index will fall below 0 */
 492                 if (globalMinC < 0) {
 493                     MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR),
 494                                                                true);
 495                     boundCheckMIR->dalvikInsn.opcode = (Opcode)kMirOpPunt;
 496                     dvmCompilerAppendMIR(entry, boundCheckMIR);
 497                 }
 498             } else if (loopAnalysis->loopBranchOpcode == OP_IF_LEZ) {
 499                 /* Array index will fall below 0 */
 500                 if (globalMinC < -1) {
 501                     MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR),
 502                                                                true);
 503                     boundCheckMIR->dalvikInsn.opcode = (Opcode)kMirOpPunt;
 504                     dvmCompilerAppendMIR(entry, boundCheckMIR);
 505                 }
 506             } else {
 507                 LOGE("Jit: bad case in genHoistedChecks");
 508                 dvmCompilerAbort(cUnit);
 509             }
 510         }
 511     }
 512 }
 513
 514 void resetBlockEdges(BasicBlock *bb)
 515 {
 516     bb->taken = NULL;
 517     bb->fallThrough = NULL;
 518     bb->successorBlockList.blockListType = kNotUsed;
 519 }
 520
 521 static bool clearPredecessorVector(struct CompilationUnit *cUnit,
 522                                    struct BasicBlock *bb)
 523 {
 524     dvmClearAllBits(bb->predecessors);
 525     return false;
 526 }
 527
 528 bool dvmCompilerFilterLoopBlocks(CompilationUnit *cUnit)
 529 {
 530     BasicBlock *firstBB = cUnit->entryBlock->fallThrough;
 531
 532     int numPred = dvmCountSetBits(firstBB->predecessors);
 533     /*
 534      * A loop body should have at least two incoming edges.
 535      */
 536     if (numPred < 2) return false;
 537
 538     GrowableList *blockList = &cUnit->blockList;
 539
 540     /* Record blocks included in the loop */
 541     dvmClearAllBits(cUnit->tempBlockV);
 542
 543     dvmCompilerSetBit(cUnit->tempBlockV, cUnit->entryBlock->id);
 544     dvmCompilerSetBit(cUnit->tempBlockV, firstBB->id);
 545
 546     BasicBlock *bodyBB = firstBB;
 547
 548     /*
 549      * First try to include the fall-through block in the loop, then the taken
 550      * block. Stop loop formation on the first backward branch that enters the
 551      * first block (ie only include the inner-most loop).
 552      */
 553     while (true) {
 554         /* Loop formed */
 555         if (bodyBB->taken == firstBB) {
 556             /* Check if the fallThrough edge will cause a nested loop */
 557             if (bodyBB->fallThrough &&
 558                 dvmIsBitSet(cUnit->tempBlockV, bodyBB->fallThrough->id)) {
 559                 return false;
 560             }
 561             /* Single loop formed */
 562             break;
 563         } else if (bodyBB->fallThrough == firstBB) {
 564             /* Check if the taken edge will cause a nested loop */
 565             if (bodyBB->taken &&
 566                 dvmIsBitSet(cUnit->tempBlockV, bodyBB->taken->id)) {
 567                 return false;
 568             }
 569             /* Single loop formed */
 570             break;
 571         }
 572
 573         /* Inner loops formed first - quit */
 574         if (bodyBB->fallThrough &&
 575             dvmIsBitSet(cUnit->tempBlockV, bodyBB->fallThrough->id)) {
 576             return false;
 577         }
 578         if (bodyBB->taken &&
 579             dvmIsBitSet(cUnit->tempBlockV, bodyBB->taken->id)) {
 580             return false;
 581         }
 582
 583         if (bodyBB->fallThrough) {
 584             if (bodyBB->fallThrough->iDom == bodyBB) {
 585                 bodyBB = bodyBB->fallThrough;
 586                 dvmCompilerSetBit(cUnit->tempBlockV, bodyBB->id);
 587                 /*
 588                  * Loop formation to be detected at the beginning of next
 589                  * iteration.
 590                  */
 591                 continue;
 592             }
 593         }
 594         if (bodyBB->taken) {
 595             if (bodyBB->taken->iDom == bodyBB) {
 596                 bodyBB = bodyBB->taken;
 597                 dvmCompilerSetBit(cUnit->tempBlockV, bodyBB->id);
 598                 /*
 599                  * Loop formation to be detected at the beginning of next
 600                  * iteration.
 601                  */
 602                 continue;
 603             }
 604         }
 605         /*
 606          * Current block is not the immediate dominator of either fallthrough
 607          * nor taken block - bail out of loop formation.
 608          */
 609         return false;
 610     }
 611
 612
 613     /* Now mark blocks not included in the loop as hidden */
 614     GrowableListIterator iterator;
 615     dvmGrowableListIteratorInit(blockList, &iterator);
 616     while (true) {
 617         BasicBlock *bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator);
 618         if (bb == NULL) break;
 619         if (!dvmIsBitSet(cUnit->tempBlockV, bb->id)) {
 620             bb->hidden = true;
 621             /* Clear the insn list */
 622             bb->firstMIRInsn = bb->lastMIRInsn = NULL;
 623             resetBlockEdges(bb);
 624         }
 625     }
 626
 627     dvmCompilerDataFlowAnalysisDispatcher(cUnit, clearPredecessorVector,
 628                                           kAllNodes, false /* isIterative */);
 629
 630     dvmGrowableListIteratorInit(blockList, &iterator);
 631     while (true) {
 632         BasicBlock *bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator);
 633         if (bb == NULL) break;
 634         if (dvmIsBitSet(cUnit->tempBlockV, bb->id)) {
 635             if (bb->taken) {
 636                 /*
 637                  * exit block means we run into control-flow that we don't want
 638                  * to handle.
 639                  */
 640                 if (bb->taken == cUnit->exitBlock) {
 641                     return false;
 642                 }
 643                 if (bb->taken->hidden) {
 644                     bb->taken->blockType = kChainingCellNormal;
 645                     bb->taken->hidden = false;
 646                 }
 647                 dvmCompilerSetBit(bb->taken->predecessors, bb->id);
 648             }
 649             if (bb->fallThrough) {
 650                 /*
 651                  * exit block means we run into control-flow that we don't want
 652                  * to handle.
 653                  */
 654                 if (bb->fallThrough == cUnit->exitBlock) {
 655                     return false;
 656                 }
 657                 if (bb->fallThrough->hidden) {
 658                     bb->fallThrough->blockType = kChainingCellNormal;
 659                     bb->fallThrough->hidden = false;
 660                 }
 661                 dvmCompilerSetBit(bb->fallThrough->predecessors, bb->id);
 662             }
 663             /* Loop blocks shouldn't contain any successor blocks (yet) */
 664             assert(bb->successorBlockList.blockListType == kNotUsed);
 665         }
 666     }
 667     return true;
 668 }
 669
 670 /*
 671  * Main entry point to do loop optimization.
 672  * Return false if sanity checks for loop formation/optimization failed.
 673  */
 674 bool dvmCompilerLoopOpt(CompilationUnit *cUnit)
 675 {
 676     LoopAnalysis *loopAnalysis =
 677         (LoopAnalysis *)dvmCompilerNew(sizeof(LoopAnalysis), true);
 678     cUnit->loopAnalysis = loopAnalysis;
 679
 680     /* Constant propagation */
 681     cUnit->isConstantV = dvmCompilerAllocBitVector(cUnit->numSSARegs, false);
 682     cUnit->constantValues =
 683         (int *)dvmCompilerNew(sizeof(int) * cUnit->numSSARegs,
 684                               true);
 685     dvmCompilerDataFlowAnalysisDispatcher(cUnit,
 686                                           dvmCompilerDoConstantPropagation,
 687                                           kAllNodes,
 688                                           false /* isIterative */);
 689     DEBUG_LOOP(dumpConstants(cUnit);)
 690
 691     /* Find induction variables - basic and dependent */
 692     loopAnalysis->ivList =
 693         (GrowableList *)dvmCompilerNew(sizeof(GrowableList), true);
 694     dvmInitGrowableList(loopAnalysis->ivList, 4);
 695     loopAnalysis->isIndVarV = dvmCompilerAllocBitVector(cUnit->numSSARegs, false);
 696     dvmCompilerDataFlowAnalysisDispatcher(cUnit,
 697                                           dvmCompilerFindInductionVariables,
 698                                           kAllNodes,
 699                                           false /* isIterative */);
 700     DEBUG_LOOP(dumpIVList(cUnit);)
 701
 702     /* Only optimize array accesses for simple counted loop for now */
 703     if (!isSimpleCountedLoop(cUnit))
 704         return false;
 705
 706     loopAnalysis->arrayAccessInfo =
 707         (GrowableList *)dvmCompilerNew(sizeof(GrowableList), true);
 708     dvmInitGrowableList(loopAnalysis->arrayAccessInfo, 4);
 709     loopAnalysis->bodyIsClean = doLoopBodyCodeMotion(cUnit);
 710     DEBUG_LOOP(dumpHoistedChecks(cUnit);)
 711
 712     /*
 713      * Convert the array access information into extended MIR code in the loop
 714      * header.
 715      */
 716     genHoistedChecks(cUnit);
 717     return true;
 718 }
 719
 720 /*
 721  * Select the target block of the backward branch.
 722  */
 723 void dvmCompilerInsertBackwardChaining(CompilationUnit *cUnit)
 724 {
 725     /*
 726      * If we are not in self-verification or profiling mode, the backward
 727      * branch can go to the entryBlock->fallThrough directly. Suspend polling
 728      * code will be generated along the backward branch to honor the suspend
 729      * requests.
 730      */
 731 #if !defined(WITH_SELF_VERIFICATION)
 732     if (gDvmJit.profileMode != kTraceProfilingContinuous &&
 733         gDvmJit.profileMode != kTraceProfilingPeriodicOn) {
 734         return;
 735     }
 736 #endif
 737     /*
 738      * In self-verification or profiling mode, the backward branch is altered
 739      * to go to the backward chaining cell. Without using the backward chaining
 740      * cell we won't be able to do check-pointing on the target PC, or count the
 741      * number of iterations accurately.
 742      */
 743     BasicBlock *firstBB = cUnit->entryBlock->fallThrough;
 744     BasicBlock *backBranchBB = findPredecessorBlock(cUnit, firstBB);
 745     if (backBranchBB->taken == firstBB) {
 746         backBranchBB->taken = cUnit->backChainBlock;
 747     } else {
 748         assert(backBranchBB->fallThrough == firstBB);
 749         backBranchBB->fallThrough = cUnit->backChainBlock;
 750     }
 751     cUnit->backChainBlock->startOffset = firstBB->startOffset;
 752 }