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 /* 25 * Given the current simple natural loops, the phi node placement can be 26 * determined in the following fashion: 27 * entry (B0) 28 * +---v v 29 * | loop body (B1) 30 * | v 31 * | loop back (B2) 32 * +---+ v 33 * exit (B3) 34 * 35 * 1) Add live-ins of B1 to B0 as defs 36 * 2) The intersect of defs(B0)/defs(B1) and defs(B2)/def(B0) are the variables 37 * that need PHI nodes in B1. 38 */ 39 static void handlePhiPlacement(CompilationUnit *cUnit) 40 { 41 BasicBlock *entry = cUnit->blockList[0]; 42 BasicBlock *loopBody = cUnit->blockList[1]; 43 BasicBlock *loopBranch = cUnit->blockList[2]; 44 dvmCopyBitVector(entry->dataFlowInfo->defV, 45 loopBody->dataFlowInfo->liveInV); 46 47 BitVector *phiV = dvmCompilerAllocBitVector(cUnit->method->registersSize, 48 false); 49 dvmIntersectBitVectors(phiV, entry->dataFlowInfo->defV, 50 loopBody->dataFlowInfo->defV); 51 dvmIntersectBitVectors(phiV, entry->dataFlowInfo->defV, 52 loopBranch->dataFlowInfo->defV); 53 54 /* Insert the PHI MIRs */ 55 int i; 56 for (i = 0; i < cUnit->method->registersSize; i++) { 57 if (!dvmIsBitSet(phiV, i)) { 58 continue; 59 } 60 MIR *phi = dvmCompilerNew(sizeof(MIR), true); 61 phi->dalvikInsn.opCode = kMirOpPhi; 62 phi->dalvikInsn.vA = i; 63 dvmCompilerPrependMIR(loopBody, phi); 64 } 65 } 66 67 static void fillPhiNodeContents(CompilationUnit *cUnit) 68 { 69 BasicBlock *entry = cUnit->blockList[0]; 70 BasicBlock *loopBody = cUnit->blockList[1]; 71 BasicBlock *loopBranch = cUnit->blockList[2]; 72 MIR *mir; 73 74 for (mir = loopBody->firstMIRInsn; mir; mir = mir->next) { 75 if (mir->dalvikInsn.opCode != kMirOpPhi) break; 76 int dalvikReg = mir->dalvikInsn.vA; 77 78 mir->ssaRep->numUses = 2; 79 mir->ssaRep->uses = dvmCompilerNew(sizeof(int) * 2, false); 80 mir->ssaRep->uses[0] = 81 DECODE_REG(entry->dataFlowInfo->dalvikToSSAMap[dalvikReg]); 82 mir->ssaRep->uses[1] = 83 DECODE_REG(loopBranch->dataFlowInfo->dalvikToSSAMap[dalvikReg]); 84 } 85 86 87 } 88 89 #if 0 90 /* Debugging routines */ 91 static void dumpConstants(CompilationUnit *cUnit) 92 { 93 int i; 94 for (i = 0; i < cUnit->numSSARegs; i++) { 95 if (dvmIsBitSet(cUnit->isConstantV, i)) { 96 int subNReg = dvmConvertSSARegToDalvik(cUnit, i); 97 LOGE("s%d(v%d_%d) has %d", i, 98 DECODE_REG(subNReg), DECODE_SUB(subNReg), 99 cUnit->constantValues[i]); 100 } 101 } 102 } 103 104 static void dumpIVList(CompilationUnit *cUnit) 105 { 106 unsigned int i; 107 GrowableList *ivList = cUnit->loopAnalysis->ivList; 108 int *ssaToDalvikMap = (int *) cUnit->ssaToDalvikMap->elemList; 109 110 for (i = 0; i < ivList->numUsed; i++) { 111 InductionVariableInfo *ivInfo = ivList->elemList[i]; 112 /* Basic IV */ 113 if (ivInfo->ssaReg == ivInfo->basicSSAReg) { 114 LOGE("BIV %d: s%d(v%d) + %d", i, 115 ivInfo->ssaReg, 116 ssaToDalvikMap[ivInfo->ssaReg] & 0xffff, 117 ivInfo->inc); 118 /* Dependent IV */ 119 } else { 120 LOGE("DIV %d: s%d(v%d) = %d * s%d(v%d) + %d", i, 121 ivInfo->ssaReg, 122 ssaToDalvikMap[ivInfo->ssaReg] & 0xffff, 123 ivInfo->m, 124 ivInfo->basicSSAReg, 125 ssaToDalvikMap[ivInfo->basicSSAReg] & 0xffff, 126 ivInfo->c); 127 } 128 } 129 } 130 131 static void dumpHoistedChecks(CompilationUnit *cUnit) 132 { 133 LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; 134 unsigned int i; 135 136 for (i = 0; i < loopAnalysis->arrayAccessInfo->numUsed; i++) { 137 ArrayAccessInfo *arrayAccessInfo = 138 GET_ELEM_N(loopAnalysis->arrayAccessInfo, 139 ArrayAccessInfo*, i); 140 int arrayReg = DECODE_REG( 141 dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->arrayReg)); 142 int idxReg = DECODE_REG( 143 dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->ivReg)); 144 LOGE("Array access %d", i); 145 LOGE(" arrayReg %d", arrayReg); 146 LOGE(" idxReg %d", idxReg); 147 LOGE(" endReg %d", loopAnalysis->endConditionReg); 148 LOGE(" maxC %d", arrayAccessInfo->maxC); 149 LOGE(" minC %d", arrayAccessInfo->minC); 150 LOGE(" opcode %d", loopAnalysis->loopBranchOpcode); 151 } 152 } 153 154 #endif 155 156 /* 157 * A loop is considered optimizable if: 158 * 1) It has one basic induction variable 159 * 2) The loop back branch compares the BIV with a constant 160 * 3) If it is a count-up loop, the condition is GE/GT, or LE/LT/LEZ/LTZ for 161 * a count-down loop. 162 * 163 * Return false if the loop is not optimizable. 164 */ 165 static bool isLoopOptimizable(CompilationUnit *cUnit) 166 { 167 unsigned int i; 168 BasicBlock *loopBranch = cUnit->blockList[2]; 169 LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; 170 171 if (loopAnalysis->numBasicIV != 1) return false; 172 for (i = 0; i < loopAnalysis->ivList->numUsed; i++) { 173 InductionVariableInfo *ivInfo; 174 175 ivInfo = GET_ELEM_N(loopAnalysis->ivList, InductionVariableInfo*, i); 176 /* Count up or down loop? */ 177 if (ivInfo->ssaReg == ivInfo->basicSSAReg) { 178 /* Infinite loop */ 179 if (ivInfo->inc == 0) { 180 return false; 181 } 182 loopAnalysis->isCountUpLoop = ivInfo->inc > 0; 183 break; 184 } 185 } 186 187 MIR *branch = loopBranch->lastMIRInsn; 188 OpCode opCode = branch->dalvikInsn.opCode; 189 190 /* 191 * If the instruction is not accessing the IV as the first operand, return 192 * false. 193 */ 194 if (branch->ssaRep->numUses == 0 || branch->ssaRep->numDefs != 0) { 195 return false; 196 } 197 198 /* 199 * If the first operand of the comparison is not the basic induction 200 * variable, return false. 201 */ 202 if (branch->ssaRep->uses[0] != loopAnalysis->ssaBIV) { 203 return false; 204 } 205 206 if (loopAnalysis->isCountUpLoop) { 207 /* 208 * If the condition op is not > or >=, this is not an optimization 209 * candidate. 210 */ 211 if (opCode != OP_IF_GT && opCode != OP_IF_GE) { 212 return false; 213 } 214 /* 215 * If the comparison is not between the BIV and a loop invariant, 216 * return false. endReg is loop invariant if one of the following is 217 * true: 218 * - It is not defined in the loop (ie DECODE_SUB returns 0) 219 * - It is reloaded with a constant 220 */ 221 int endReg = dvmConvertSSARegToDalvik(cUnit, branch->ssaRep->uses[1]); 222 if (DECODE_SUB(endReg) != 0 && 223 !dvmIsBitSet(cUnit->isConstantV, branch->ssaRep->uses[1])) { 224 return false; 225 } 226 loopAnalysis->endConditionReg = DECODE_REG(endReg); 227 } else { 228 /* 229 * If the condition op is not < or <=, this is not an optimization 230 * candidate. 231 */ 232 if (opCode == OP_IF_LT || opCode == OP_IF_LE) { 233 /* 234 * If the comparison is not between the BIV and a loop invariant, 235 * return false. 236 */ 237 int endReg = dvmConvertSSARegToDalvik(cUnit, 238 branch->ssaRep->uses[1]); 239 240 if (DECODE_SUB(endReg) != 0) { 241 return false; 242 } 243 loopAnalysis->endConditionReg = DECODE_REG(endReg); 244 } else if (opCode != OP_IF_LTZ && opCode != OP_IF_LEZ) { 245 return false; 246 } 247 } 248 loopAnalysis->loopBranchOpcode = opCode; 249 return true; 250 } 251 252 /* 253 * Record the upper and lower bound information for range checks for each 254 * induction variable. If array A is accessed by index "i+5", the upper and 255 * lower bound will be len(A)-5 and -5, respectively. 256 */ 257 static void updateRangeCheckInfo(CompilationUnit *cUnit, int arrayReg, 258 int idxReg) 259 { 260 InductionVariableInfo *ivInfo; 261 LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; 262 unsigned int i, j; 263 264 for (i = 0; i < loopAnalysis->ivList->numUsed; i++) { 265 ivInfo = GET_ELEM_N(loopAnalysis->ivList, InductionVariableInfo*, i); 266 if (ivInfo->ssaReg == idxReg) { 267 ArrayAccessInfo *arrayAccessInfo = NULL; 268 for (j = 0; j < loopAnalysis->arrayAccessInfo->numUsed; j++) { 269 ArrayAccessInfo *existingArrayAccessInfo = 270 GET_ELEM_N(loopAnalysis->arrayAccessInfo, 271 ArrayAccessInfo*, 272 j); 273 if (existingArrayAccessInfo->arrayReg == arrayReg) { 274 if (ivInfo->c > existingArrayAccessInfo->maxC) { 275 existingArrayAccessInfo->maxC = ivInfo->c; 276 } 277 if (ivInfo->c < existingArrayAccessInfo->minC) { 278 existingArrayAccessInfo->minC = ivInfo->c; 279 } 280 arrayAccessInfo = existingArrayAccessInfo; 281 break; 282 } 283 } 284 if (arrayAccessInfo == NULL) { 285 arrayAccessInfo = 286 dvmCompilerNew(sizeof(ArrayAccessInfo), false); 287 arrayAccessInfo->ivReg = ivInfo->basicSSAReg; 288 arrayAccessInfo->arrayReg = arrayReg; 289 arrayAccessInfo->maxC = (ivInfo->c > 0) ? ivInfo->c : 0; 290 arrayAccessInfo->minC = (ivInfo->c < 0) ? ivInfo->c : 0; 291 dvmInsertGrowableList(loopAnalysis->arrayAccessInfo, 292 arrayAccessInfo); 293 } 294 break; 295 } 296 } 297 } 298 299 /* Returns true if the loop body cannot throw any exceptions */ 300 static bool doLoopBodyCodeMotion(CompilationUnit *cUnit) 301 { 302 BasicBlock *loopBody = cUnit->blockList[1]; 303 MIR *mir; 304 bool loopBodyCanThrow = false; 305 306 for (mir = loopBody->firstMIRInsn; mir; mir = mir->next) { 307 DecodedInstruction *dInsn = &mir->dalvikInsn; 308 int dfAttributes = 309 dvmCompilerDataFlowAttributes[mir->dalvikInsn.opCode]; 310 311 /* Skip extended MIR instructions */ 312 if (dInsn->opCode > 255) continue; 313 314 int instrFlags = dexGetInstrFlags(gDvm.instrFlags, dInsn->opCode); 315 316 /* Instruction is clean */ 317 if ((instrFlags & kInstrCanThrow) == 0) continue; 318 319 /* 320 * Currently we can only optimize away null and range checks. Punt on 321 * instructions that can throw due to other exceptions. 322 */ 323 if (!(dfAttributes & DF_HAS_NR_CHECKS)) { 324 loopBodyCanThrow = true; 325 continue; 326 } 327 328 /* 329 * This comparison is redundant now, but we will have more than one 330 * group of flags to check soon. 331 */ 332 if (dfAttributes & DF_HAS_NR_CHECKS) { 333 /* 334 * Check if the null check is applied on a loop invariant register? 335 * If the register's SSA id is less than the number of Dalvik 336 * registers, then it is loop invariant. 337 */ 338 int refIdx; 339 switch (dfAttributes & DF_HAS_NR_CHECKS) { 340 case DF_NULL_N_RANGE_CHECK_0: 341 refIdx = 0; 342 break; 343 case DF_NULL_N_RANGE_CHECK_1: 344 refIdx = 1; 345 break; 346 case DF_NULL_N_RANGE_CHECK_2: 347 refIdx = 2; 348 break; 349 default: 350 refIdx = 0; 351 LOGE("Jit: bad case in doLoopBodyCodeMotion"); 352 dvmCompilerAbort(cUnit); 353 } 354 355 int useIdx = refIdx + 1; 356 int subNRegArray = 357 dvmConvertSSARegToDalvik(cUnit, mir->ssaRep->uses[refIdx]); 358 int arraySub = DECODE_SUB(subNRegArray); 359 360 /* 361 * If the register is never updated in the loop (ie subscript == 0), 362 * it is an optimization candidate. 363 */ 364 if (arraySub != 0) { 365 loopBodyCanThrow = true; 366 continue; 367 } 368 369 /* 370 * Then check if the range check can be hoisted out of the loop if 371 * it is basic or dependent induction variable. 372 */ 373 if (dvmIsBitSet(cUnit->loopAnalysis->isIndVarV, 374 mir->ssaRep->uses[useIdx])) { 375 mir->OptimizationFlags |= 376 MIR_IGNORE_RANGE_CHECK | MIR_IGNORE_NULL_CHECK; 377 updateRangeCheckInfo(cUnit, mir->ssaRep->uses[refIdx], 378 mir->ssaRep->uses[useIdx]); 379 } 380 } 381 } 382 383 return !loopBodyCanThrow; 384 } 385 386 static void genHoistedChecks(CompilationUnit *cUnit) 387 { 388 unsigned int i; 389 BasicBlock *entry = cUnit->blockList[0]; 390 LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; 391 int globalMaxC = 0; 392 int globalMinC = 0; 393 /* Should be loop invariant */ 394 int idxReg = 0; 395 396 for (i = 0; i < loopAnalysis->arrayAccessInfo->numUsed; i++) { 397 ArrayAccessInfo *arrayAccessInfo = 398 GET_ELEM_N(loopAnalysis->arrayAccessInfo, 399 ArrayAccessInfo*, i); 400 int arrayReg = DECODE_REG( 401 dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->arrayReg)); 402 idxReg = DECODE_REG( 403 dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->ivReg)); 404 405 MIR *rangeCheckMIR = dvmCompilerNew(sizeof(MIR), true); 406 rangeCheckMIR->dalvikInsn.opCode = (loopAnalysis->isCountUpLoop) ? 407 kMirOpNullNRangeUpCheck : kMirOpNullNRangeDownCheck; 408 rangeCheckMIR->dalvikInsn.vA = arrayReg; 409 rangeCheckMIR->dalvikInsn.vB = idxReg; 410 rangeCheckMIR->dalvikInsn.vC = loopAnalysis->endConditionReg; 411 rangeCheckMIR->dalvikInsn.arg[0] = arrayAccessInfo->maxC; 412 rangeCheckMIR->dalvikInsn.arg[1] = arrayAccessInfo->minC; 413 rangeCheckMIR->dalvikInsn.arg[2] = loopAnalysis->loopBranchOpcode; 414 dvmCompilerAppendMIR(entry, rangeCheckMIR); 415 if (arrayAccessInfo->maxC > globalMaxC) { 416 globalMaxC = arrayAccessInfo->maxC; 417 } 418 if (arrayAccessInfo->minC < globalMinC) { 419 globalMinC = arrayAccessInfo->minC; 420 } 421 } 422 423 if (loopAnalysis->arrayAccessInfo->numUsed != 0) { 424 if (loopAnalysis->isCountUpLoop) { 425 MIR *boundCheckMIR = dvmCompilerNew(sizeof(MIR), true); 426 boundCheckMIR->dalvikInsn.opCode = kMirOpLowerBound; 427 boundCheckMIR->dalvikInsn.vA = idxReg; 428 boundCheckMIR->dalvikInsn.vB = globalMinC; 429 dvmCompilerAppendMIR(entry, boundCheckMIR); 430 } else { 431 if (loopAnalysis->loopBranchOpcode == OP_IF_LT || 432 loopAnalysis->loopBranchOpcode == OP_IF_LE) { 433 MIR *boundCheckMIR = dvmCompilerNew(sizeof(MIR), true); 434 boundCheckMIR->dalvikInsn.opCode = kMirOpLowerBound; 435 boundCheckMIR->dalvikInsn.vA = loopAnalysis->endConditionReg; 436 boundCheckMIR->dalvikInsn.vB = globalMinC; 437 /* 438 * If the end condition is ">" in the source, the check in the 439 * Dalvik bytecode is OP_IF_LE. In this case add 1 back to the 440 * constant field to reflect the fact that the smallest index 441 * value is "endValue + constant + 1". 442 */ 443 if (loopAnalysis->loopBranchOpcode == OP_IF_LE) { 444 boundCheckMIR->dalvikInsn.vB++; 445 } 446 dvmCompilerAppendMIR(entry, boundCheckMIR); 447 } else if (loopAnalysis->loopBranchOpcode == OP_IF_LTZ) { 448 /* Array index will fall below 0 */ 449 if (globalMinC < 0) { 450 MIR *boundCheckMIR = dvmCompilerNew(sizeof(MIR), true); 451 boundCheckMIR->dalvikInsn.opCode = kMirOpPunt; 452 dvmCompilerAppendMIR(entry, boundCheckMIR); 453 } 454 } else if (loopAnalysis->loopBranchOpcode == OP_IF_LEZ) { 455 /* Array index will fall below 0 */ 456 if (globalMinC < -1) { 457 MIR *boundCheckMIR = dvmCompilerNew(sizeof(MIR), true); 458 boundCheckMIR->dalvikInsn.opCode = kMirOpPunt; 459 dvmCompilerAppendMIR(entry, boundCheckMIR); 460 } 461 } else { 462 LOGE("Jit: bad case in genHoistedChecks"); 463 dvmCompilerAbort(cUnit); 464 } 465 } 466 467 } 468 } 469 470 /* 471 * Main entry point to do loop optimization. 472 * Return false if sanity checks for loop formation/optimization failed. 473 */ 474 bool dvmCompilerLoopOpt(CompilationUnit *cUnit) 475 { 476 LoopAnalysis *loopAnalysis = dvmCompilerNew(sizeof(LoopAnalysis), true); 477 478 assert(cUnit->blockList[0]->blockType == kTraceEntryBlock); 479 assert(cUnit->blockList[2]->blockType == kDalvikByteCode); 480 assert(cUnit->blockList[3]->blockType == kTraceExitBlock); 481 482 cUnit->loopAnalysis = loopAnalysis; 483 /* 484 * Find live-in variables to the loop body so that we can fake their 485 * definitions in the entry block. 486 */ 487 dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerFindLiveIn); 488 489 /* Insert phi nodes to the loop body */ 490 handlePhiPlacement(cUnit); 491 492 dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerDoSSAConversion); 493 fillPhiNodeContents(cUnit); 494 495 /* Constant propagation */ 496 cUnit->isConstantV = dvmAllocBitVector(cUnit->numSSARegs, false); 497 cUnit->constantValues = dvmCompilerNew(sizeof(int) * cUnit->numSSARegs, 498 true); 499 dvmCompilerDataFlowAnalysisDispatcher(cUnit, 500 dvmCompilerDoConstantPropagation); 501 DEBUG_LOOP(dumpConstants(cUnit);) 502 503 /* Find induction variables - basic and dependent */ 504 loopAnalysis->ivList = dvmCompilerNew(sizeof(GrowableList), true); 505 dvmInitGrowableList(loopAnalysis->ivList, 4); 506 loopAnalysis->isIndVarV = dvmAllocBitVector(cUnit->numSSARegs, false); 507 dvmCompilerDataFlowAnalysisDispatcher(cUnit, 508 dvmCompilerFindInductionVariables); 509 DEBUG_LOOP(dumpIVList(cUnit);) 510 511 /* If the loop turns out to be non-optimizable, return early */ 512 if (!isLoopOptimizable(cUnit)) 513 return false; 514 515 loopAnalysis->arrayAccessInfo = dvmCompilerNew(sizeof(GrowableList), true); 516 dvmInitGrowableList(loopAnalysis->arrayAccessInfo, 4); 517 loopAnalysis->bodyIsClean = doLoopBodyCodeMotion(cUnit); 518 DEBUG_LOOP(dumpHoistedChecks(cUnit);) 519 520 /* 521 * Convert the array access information into extended MIR code in the loop 522 * header. 523 */ 524 genHoistedChecks(cUnit); 525 return true; 526 } 527
