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 ALOGE("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 ALOGE("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 ALOGE("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 ALOGE("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 ALOGE("Array access %d", i); 84 ALOGE(" arrayReg %d", arrayReg); 85 ALOGE(" idxReg %d", idxReg); 86 ALOGE(" endReg %d", loopAnalysis->endConditionReg); 87 ALOGE(" maxC %d", arrayAccessInfo->maxC); 88 ALOGE(" minC %d", arrayAccessInfo->minC); 89 ALOGE(" 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 ALOGE("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 ((u2) 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 ALOGE("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 ALOGE("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 #ifndef ARCH_IA32 732 #if !defined(WITH_SELF_VERIFICATION) 733 if (gDvmJit.profileMode != kTraceProfilingContinuous && 734 gDvmJit.profileMode != kTraceProfilingPeriodicOn) { 735 return; 736 } 737 #endif 738 #endif 739 740 /* 741 * In self-verification or profiling mode, the backward branch is altered 742 * to go to the backward chaining cell. Without using the backward chaining 743 * cell we won't be able to do check-pointing on the target PC, or count the 744 * number of iterations accurately. 745 */ 746 BasicBlock *firstBB = cUnit->entryBlock->fallThrough; 747 BasicBlock *backBranchBB = findPredecessorBlock(cUnit, firstBB); 748 if (backBranchBB->taken == firstBB) { 749 backBranchBB->taken = cUnit->backChainBlock; 750 } else { 751 assert(backBranchBB->fallThrough == firstBB); 752 backBranchBB->fallThrough = cUnit->backChainBlock; 753 } 754 cUnit->backChainBlock->startOffset = firstBB->startOffset; 755 } 756
