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