Loop.cpp revision 46cd4fb73824ab57160994c149ce2d7a06923b83
14238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng/* 24238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * Copyright (C) 2009 The Android Open Source Project 34238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * 44238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * Licensed under the Apache License, Version 2.0 (the "License"); 54238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * you may not use this file except in compliance with the License. 64238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * You may obtain a copy of the License at 74238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * 84238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * http://www.apache.org/licenses/LICENSE-2.0 94238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * 104238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * Unless required by applicable law or agreed to in writing, software 114238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * distributed under the License is distributed on an "AS IS" BASIS, 124238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 134238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * See the License for the specific language governing permissions and 144238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * limitations under the License. 154238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 164238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 174238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#include "Dalvik.h" 184238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#include "CompilerInternals.h" 194238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#include "Dataflow.h" 204238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#include "Loop.h" 214238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 224238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng#define DEBUG_LOOP(X) 234238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 244238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng/* 254238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * Given the current simple natural loops, the phi node placement can be 264238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * determined in the following fashion: 274238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * entry (B0) 284238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * +---v v 294238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * | loop body (B1) 304238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * | v 314238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * | loop back (B2) 324238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * +---+ v 334238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * exit (B3) 344238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * 354238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * 1) Add live-ins of B1 to B0 as defs 364238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * 2) The intersect of defs(B0)/defs(B1) and defs(B2)/def(B0) are the variables 374238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * that need PHI nodes in B1. 384238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 394238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengstatic void handlePhiPlacement(CompilationUnit *cUnit) 404238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng{ 4100603079b8723b32c955513eae63a8f97898074dBen Cheng BasicBlock *entry = 4200603079b8723b32c955513eae63a8f97898074dBen Cheng (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 0); 4300603079b8723b32c955513eae63a8f97898074dBen Cheng BasicBlock *loopBody = 4400603079b8723b32c955513eae63a8f97898074dBen Cheng (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 1); 4500603079b8723b32c955513eae63a8f97898074dBen Cheng BasicBlock *loopBranch = 4600603079b8723b32c955513eae63a8f97898074dBen Cheng (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 2); 474238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmCopyBitVector(entry->dataFlowInfo->defV, 484238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng loopBody->dataFlowInfo->liveInV); 494238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 504238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng BitVector *phiV = dvmCompilerAllocBitVector(cUnit->method->registersSize, 514238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng false); 5200603079b8723b32c955513eae63a8f97898074dBen Cheng BitVector *phi2V = dvmCompilerAllocBitVector(cUnit->method->registersSize, 5300603079b8723b32c955513eae63a8f97898074dBen Cheng false); 544238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmIntersectBitVectors(phiV, entry->dataFlowInfo->defV, 554238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng loopBody->dataFlowInfo->defV); 5600603079b8723b32c955513eae63a8f97898074dBen Cheng dvmIntersectBitVectors(phi2V, entry->dataFlowInfo->defV, 574238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng loopBranch->dataFlowInfo->defV); 5800603079b8723b32c955513eae63a8f97898074dBen Cheng dvmUnifyBitVectors(phiV, phiV, phi2V); 594238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 604238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Insert the PHI MIRs */ 614238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int i; 624238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng for (i = 0; i < cUnit->method->registersSize; i++) { 634238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (!dvmIsBitSet(phiV, i)) { 644238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng continue; 654238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 66fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro MIR *phi = (MIR *)dvmCompilerNew(sizeof(MIR), true); 679a1f81699cc05b58378ffb9aadb4e97677943791Dan Bornstein phi->dalvikInsn.opcode = kMirOpPhi; 684238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng phi->dalvikInsn.vA = i; 694238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmCompilerPrependMIR(loopBody, phi); 704238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 714238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} 724238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 734238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengstatic void fillPhiNodeContents(CompilationUnit *cUnit) 744238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng{ 7500603079b8723b32c955513eae63a8f97898074dBen Cheng BasicBlock *entry = 7600603079b8723b32c955513eae63a8f97898074dBen Cheng (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 0); 7700603079b8723b32c955513eae63a8f97898074dBen Cheng BasicBlock *loopBody = 7800603079b8723b32c955513eae63a8f97898074dBen Cheng (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 1); 7900603079b8723b32c955513eae63a8f97898074dBen Cheng BasicBlock *loopBranch = 8000603079b8723b32c955513eae63a8f97898074dBen Cheng (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 2); 814238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng MIR *mir; 824238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 834238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng for (mir = loopBody->firstMIRInsn; mir; mir = mir->next) { 849a1f81699cc05b58378ffb9aadb4e97677943791Dan Bornstein if (mir->dalvikInsn.opcode != kMirOpPhi) break; 854238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int dalvikReg = mir->dalvikInsn.vA; 864238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 874238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng mir->ssaRep->numUses = 2; 88fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro mir->ssaRep->uses = (int *)dvmCompilerNew(sizeof(int) * 2, false); 894238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng mir->ssaRep->uses[0] = 904238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng DECODE_REG(entry->dataFlowInfo->dalvikToSSAMap[dalvikReg]); 914238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng mir->ssaRep->uses[1] = 924238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng DECODE_REG(loopBranch->dataFlowInfo->dalvikToSSAMap[dalvikReg]); 934238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 944238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 954238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 964238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} 974238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 98fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng#if 0 99fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng/* Debugging routines */ 1004238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengstatic void dumpConstants(CompilationUnit *cUnit) 1014238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng{ 1024238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int i; 1034238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng for (i = 0; i < cUnit->numSSARegs; i++) { 1044238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (dvmIsBitSet(cUnit->isConstantV, i)) { 1054238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int subNReg = dvmConvertSSARegToDalvik(cUnit, i); 1064238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng LOGE("s%d(v%d_%d) has %d", i, 1074238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng DECODE_REG(subNReg), DECODE_SUB(subNReg), 1084238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng cUnit->constantValues[i]); 1094238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 1104238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 1114238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} 1124238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 1134238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengstatic void dumpIVList(CompilationUnit *cUnit) 1144238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng{ 1154238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng unsigned int i; 1164238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng GrowableList *ivList = cUnit->loopAnalysis->ivList; 1174238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int *ssaToDalvikMap = (int *) cUnit->ssaToDalvikMap->elemList; 1184238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 1194238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng for (i = 0; i < ivList->numUsed; i++) { 1204238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng InductionVariableInfo *ivInfo = ivList->elemList[i]; 1214238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Basic IV */ 1224238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (ivInfo->ssaReg == ivInfo->basicSSAReg) { 1234238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng LOGE("BIV %d: s%d(v%d) + %d", i, 1244238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ivInfo->ssaReg, 1254238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ssaToDalvikMap[ivInfo->ssaReg] & 0xffff, 1264238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ivInfo->inc); 1274238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Dependent IV */ 1284238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } else { 1294238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng LOGE("DIV %d: s%d(v%d) = %d * s%d(v%d) + %d", i, 1304238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ivInfo->ssaReg, 1314238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ssaToDalvikMap[ivInfo->ssaReg] & 0xffff, 1324238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ivInfo->m, 1334238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ivInfo->basicSSAReg, 1344238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ssaToDalvikMap[ivInfo->basicSSAReg] & 0xffff, 1354238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ivInfo->c); 1364238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 1374238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 1384238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} 1394238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 140fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Chengstatic void dumpHoistedChecks(CompilationUnit *cUnit) 141fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng{ 142fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; 143fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng unsigned int i; 144fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng 145fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng for (i = 0; i < loopAnalysis->arrayAccessInfo->numUsed; i++) { 146fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng ArrayAccessInfo *arrayAccessInfo = 147fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng GET_ELEM_N(loopAnalysis->arrayAccessInfo, 148fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng ArrayAccessInfo*, i); 149fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng int arrayReg = DECODE_REG( 150fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->arrayReg)); 151fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng int idxReg = DECODE_REG( 152fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->ivReg)); 153fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng LOGE("Array access %d", i); 154fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng LOGE(" arrayReg %d", arrayReg); 155fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng LOGE(" idxReg %d", idxReg); 156fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng LOGE(" endReg %d", loopAnalysis->endConditionReg); 157fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng LOGE(" maxC %d", arrayAccessInfo->maxC); 158fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng LOGE(" minC %d", arrayAccessInfo->minC); 159fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng LOGE(" opcode %d", loopAnalysis->loopBranchOpcode); 160fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng } 161fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng} 162fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng 163fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng#endif 164fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng 1654238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng/* 1664238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * A loop is considered optimizable if: 1674238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * 1) It has one basic induction variable 1684238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * 2) The loop back branch compares the BIV with a constant 1694238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * 3) If it is a count-up loop, the condition is GE/GT, or LE/LT/LEZ/LTZ for 1704238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * a count-down loop. 1714a41958266fb432629dea30832f4b3194667ba99Ben Cheng * 1724a41958266fb432629dea30832f4b3194667ba99Ben Cheng * Return false if the loop is not optimizable. 1734238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 1744238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengstatic bool isLoopOptimizable(CompilationUnit *cUnit) 1754238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng{ 1764238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng unsigned int i; 17700603079b8723b32c955513eae63a8f97898074dBen Cheng BasicBlock *loopBranch = 17800603079b8723b32c955513eae63a8f97898074dBen Cheng (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 2); 1794238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; 1804238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 1814238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (loopAnalysis->numBasicIV != 1) return false; 1824238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng for (i = 0; i < loopAnalysis->ivList->numUsed; i++) { 1834238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng InductionVariableInfo *ivInfo; 1844238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 1854238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ivInfo = GET_ELEM_N(loopAnalysis->ivList, InductionVariableInfo*, i); 1864238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Count up or down loop? */ 1874238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (ivInfo->ssaReg == ivInfo->basicSSAReg) { 1884a41958266fb432629dea30832f4b3194667ba99Ben Cheng /* Infinite loop */ 1894a41958266fb432629dea30832f4b3194667ba99Ben Cheng if (ivInfo->inc == 0) { 1904a41958266fb432629dea30832f4b3194667ba99Ben Cheng return false; 1914a41958266fb432629dea30832f4b3194667ba99Ben Cheng } 1924238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng loopAnalysis->isCountUpLoop = ivInfo->inc > 0; 1934238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng break; 1944238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 1954238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 1964238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 1974238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng MIR *branch = loopBranch->lastMIRInsn; 1989a1f81699cc05b58378ffb9aadb4e97677943791Dan Bornstein Opcode opcode = branch->dalvikInsn.opcode; 1994238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 2004238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 2014238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * If the instruction is not accessing the IV as the first operand, return 2024238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * false. 2034238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 2044238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (branch->ssaRep->numUses == 0 || branch->ssaRep->numDefs != 0) { 2054238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng return false; 2064238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 2074238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 2084238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 2094238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * If the first operand of the comparison is not the basic induction 2104238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * variable, return false. 2114238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 2124238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (branch->ssaRep->uses[0] != loopAnalysis->ssaBIV) { 2134238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng return false; 2144238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 2154238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 2164238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (loopAnalysis->isCountUpLoop) { 2174238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 2184238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * If the condition op is not > or >=, this is not an optimization 2194238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * candidate. 2204238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 2219a1f81699cc05b58378ffb9aadb4e97677943791Dan Bornstein if (opcode != OP_IF_GT && opcode != OP_IF_GE) { 2224238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng return false; 2234238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 2244238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 2254238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * If the comparison is not between the BIV and a loop invariant, 2264a41958266fb432629dea30832f4b3194667ba99Ben Cheng * return false. endReg is loop invariant if one of the following is 2274a41958266fb432629dea30832f4b3194667ba99Ben Cheng * true: 2284a41958266fb432629dea30832f4b3194667ba99Ben Cheng * - It is not defined in the loop (ie DECODE_SUB returns 0) 2294a41958266fb432629dea30832f4b3194667ba99Ben Cheng * - It is reloaded with a constant 2304238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 2314238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int endReg = dvmConvertSSARegToDalvik(cUnit, branch->ssaRep->uses[1]); 2324a41958266fb432629dea30832f4b3194667ba99Ben Cheng if (DECODE_SUB(endReg) != 0 && 2334a41958266fb432629dea30832f4b3194667ba99Ben Cheng !dvmIsBitSet(cUnit->isConstantV, branch->ssaRep->uses[1])) { 2344238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng return false; 2354238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 2364238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng loopAnalysis->endConditionReg = DECODE_REG(endReg); 2374238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } else { 2384238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 2394238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * If the condition op is not < or <=, this is not an optimization 2404238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * candidate. 2414238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 2429a1f81699cc05b58378ffb9aadb4e97677943791Dan Bornstein if (opcode == OP_IF_LT || opcode == OP_IF_LE) { 2434238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 2444238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * If the comparison is not between the BIV and a loop invariant, 2454238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * return false. 2464238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 2474238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int endReg = dvmConvertSSARegToDalvik(cUnit, 2484238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng branch->ssaRep->uses[1]); 2494238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 2504238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (DECODE_SUB(endReg) != 0) { 2514238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng return false; 2524238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 2534238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng loopAnalysis->endConditionReg = DECODE_REG(endReg); 2549a1f81699cc05b58378ffb9aadb4e97677943791Dan Bornstein } else if (opcode != OP_IF_LTZ && opcode != OP_IF_LEZ) { 2554238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng return false; 2564238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 2574238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 2589a1f81699cc05b58378ffb9aadb4e97677943791Dan Bornstein loopAnalysis->loopBranchOpcode = opcode; 2594238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng return true; 2604238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} 2614238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 2624238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng/* 2634238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * Record the upper and lower bound information for range checks for each 2644238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * induction variable. If array A is accessed by index "i+5", the upper and 2654238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * lower bound will be len(A)-5 and -5, respectively. 2664238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 2674238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengstatic void updateRangeCheckInfo(CompilationUnit *cUnit, int arrayReg, 2684238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int idxReg) 2694238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng{ 2704238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng InductionVariableInfo *ivInfo; 2714238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; 2724238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng unsigned int i, j; 2734238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 2744238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng for (i = 0; i < loopAnalysis->ivList->numUsed; i++) { 2754238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ivInfo = GET_ELEM_N(loopAnalysis->ivList, InductionVariableInfo*, i); 2764238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (ivInfo->ssaReg == idxReg) { 2774238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ArrayAccessInfo *arrayAccessInfo = NULL; 2784238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng for (j = 0; j < loopAnalysis->arrayAccessInfo->numUsed; j++) { 2794238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ArrayAccessInfo *existingArrayAccessInfo = 2804238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng GET_ELEM_N(loopAnalysis->arrayAccessInfo, 2814238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ArrayAccessInfo*, 2824238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng j); 2834238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (existingArrayAccessInfo->arrayReg == arrayReg) { 2844238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (ivInfo->c > existingArrayAccessInfo->maxC) { 2854238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng existingArrayAccessInfo->maxC = ivInfo->c; 2864238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 2874238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (ivInfo->c < existingArrayAccessInfo->minC) { 2884238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng existingArrayAccessInfo->minC = ivInfo->c; 2894238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 2904238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng arrayAccessInfo = existingArrayAccessInfo; 2914238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng break; 2924238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 2934238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 2944238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (arrayAccessInfo == NULL) { 2954238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng arrayAccessInfo = 296fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro (ArrayAccessInfo *)dvmCompilerNew(sizeof(ArrayAccessInfo), 297fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro false); 2984238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng arrayAccessInfo->ivReg = ivInfo->basicSSAReg; 2994238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng arrayAccessInfo->arrayReg = arrayReg; 3004238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng arrayAccessInfo->maxC = (ivInfo->c > 0) ? ivInfo->c : 0; 3014238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng arrayAccessInfo->minC = (ivInfo->c < 0) ? ivInfo->c : 0; 3024238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmInsertGrowableList(loopAnalysis->arrayAccessInfo, 30300603079b8723b32c955513eae63a8f97898074dBen Cheng (intptr_t) arrayAccessInfo); 3044238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3054238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng break; 3064238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3074238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3084238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} 3094238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3104238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng/* Returns true if the loop body cannot throw any exceptions */ 3114238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengstatic bool doLoopBodyCodeMotion(CompilationUnit *cUnit) 3124238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng{ 31300603079b8723b32c955513eae63a8f97898074dBen Cheng BasicBlock *loopBody = 31400603079b8723b32c955513eae63a8f97898074dBen Cheng (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 1); 3154238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng MIR *mir; 3164238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng bool loopBodyCanThrow = false; 3174238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3184238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng for (mir = loopBody->firstMIRInsn; mir; mir = mir->next) { 3194238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng DecodedInstruction *dInsn = &mir->dalvikInsn; 3204238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int dfAttributes = 3219a1f81699cc05b58378ffb9aadb4e97677943791Dan Bornstein dvmCompilerDataFlowAttributes[mir->dalvikInsn.opcode]; 3224238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3234238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Skip extended MIR instructions */ 324ccaab18ae6d203108445fef7682065dfbb007657Dan Bornstein if (dInsn->opcode >= kNumPackedOpcodes) continue; 3254238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 326e485276c6ba778cafa373b3b5c867f84e91b0bfdDan Bornstein int instrFlags = dexGetFlagsFromOpcode(dInsn->opcode); 3274238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3284238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Instruction is clean */ 3294238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if ((instrFlags & kInstrCanThrow) == 0) continue; 3304238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3314238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 3324238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * Currently we can only optimize away null and range checks. Punt on 3334238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * instructions that can throw due to other exceptions. 3344238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 3354238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (!(dfAttributes & DF_HAS_NR_CHECKS)) { 3364238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng loopBodyCanThrow = true; 3374238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng continue; 3384238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3394238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3404238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 3414238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * This comparison is redundant now, but we will have more than one 3424238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * group of flags to check soon. 3434238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 3444238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (dfAttributes & DF_HAS_NR_CHECKS) { 3454238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 3464238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * Check if the null check is applied on a loop invariant register? 3474238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * If the register's SSA id is less than the number of Dalvik 3484238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * registers, then it is loop invariant. 3494238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 3504238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int refIdx; 3514238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng switch (dfAttributes & DF_HAS_NR_CHECKS) { 3524238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng case DF_NULL_N_RANGE_CHECK_0: 3534238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng refIdx = 0; 3544238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng break; 3554238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng case DF_NULL_N_RANGE_CHECK_1: 3564238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng refIdx = 1; 3574238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng break; 3584238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng case DF_NULL_N_RANGE_CHECK_2: 3594238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng refIdx = 2; 3604238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng break; 3614238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng default: 3624238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng refIdx = 0; 363fc519dc8f4444f6d93806ec15ce7445b322070fdBill Buzbee LOGE("Jit: bad case in doLoopBodyCodeMotion"); 364fc519dc8f4444f6d93806ec15ce7445b322070fdBill Buzbee dvmCompilerAbort(cUnit); 3654238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3664238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3674238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int useIdx = refIdx + 1; 3684238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int subNRegArray = 3694238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmConvertSSARegToDalvik(cUnit, mir->ssaRep->uses[refIdx]); 3704238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int arraySub = DECODE_SUB(subNRegArray); 3714238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3724238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 3734238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * If the register is never updated in the loop (ie subscript == 0), 3744238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * it is an optimization candidate. 3754238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 3764238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (arraySub != 0) { 3774238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng loopBodyCanThrow = true; 3784238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng continue; 3794238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3804238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3814238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 3824238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * Then check if the range check can be hoisted out of the loop if 3834238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * it is basic or dependent induction variable. 3844238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 3854238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (dvmIsBitSet(cUnit->loopAnalysis->isIndVarV, 3864238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng mir->ssaRep->uses[useIdx])) { 3874238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng mir->OptimizationFlags |= 3884238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng MIR_IGNORE_RANGE_CHECK | MIR_IGNORE_NULL_CHECK; 3894238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng updateRangeCheckInfo(cUnit, mir->ssaRep->uses[refIdx], 3904238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng mir->ssaRep->uses[useIdx]); 3914238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3924238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3934238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3944238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3954238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng return !loopBodyCanThrow; 3964238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} 3974238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3984238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengstatic void genHoistedChecks(CompilationUnit *cUnit) 3994238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng{ 4004238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng unsigned int i; 40100603079b8723b32c955513eae63a8f97898074dBen Cheng BasicBlock *entry = 40200603079b8723b32c955513eae63a8f97898074dBen Cheng (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 0); 4034238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; 4044238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int globalMaxC = 0; 4054238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int globalMinC = 0; 4064238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Should be loop invariant */ 4074238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int idxReg = 0; 4084238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 4094238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng for (i = 0; i < loopAnalysis->arrayAccessInfo->numUsed; i++) { 4104238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ArrayAccessInfo *arrayAccessInfo = 4114238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng GET_ELEM_N(loopAnalysis->arrayAccessInfo, 4124238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ArrayAccessInfo*, i); 4134238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int arrayReg = DECODE_REG( 4144238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->arrayReg)); 4154238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng idxReg = DECODE_REG( 4164238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->ivReg)); 4174238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 418fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro MIR *rangeCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); 4199a1f81699cc05b58378ffb9aadb4e97677943791Dan Bornstein rangeCheckMIR->dalvikInsn.opcode = (loopAnalysis->isCountUpLoop) ? 4201465db5ee2d3c4c4dcc8e017a294172e858765cbBill Buzbee kMirOpNullNRangeUpCheck : kMirOpNullNRangeDownCheck; 4214238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng rangeCheckMIR->dalvikInsn.vA = arrayReg; 4224238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng rangeCheckMIR->dalvikInsn.vB = idxReg; 4234238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng rangeCheckMIR->dalvikInsn.vC = loopAnalysis->endConditionReg; 4244238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng rangeCheckMIR->dalvikInsn.arg[0] = arrayAccessInfo->maxC; 4254238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng rangeCheckMIR->dalvikInsn.arg[1] = arrayAccessInfo->minC; 4264238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng rangeCheckMIR->dalvikInsn.arg[2] = loopAnalysis->loopBranchOpcode; 4274238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmCompilerAppendMIR(entry, rangeCheckMIR); 4284238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (arrayAccessInfo->maxC > globalMaxC) { 4294238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng globalMaxC = arrayAccessInfo->maxC; 4304238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4314238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (arrayAccessInfo->minC < globalMinC) { 4324238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng globalMinC = arrayAccessInfo->minC; 4334238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4344238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4354238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 4364238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (loopAnalysis->arrayAccessInfo->numUsed != 0) { 4374238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (loopAnalysis->isCountUpLoop) { 438fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); 4399a1f81699cc05b58378ffb9aadb4e97677943791Dan Bornstein boundCheckMIR->dalvikInsn.opcode = kMirOpLowerBound; 4404238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng boundCheckMIR->dalvikInsn.vA = idxReg; 4414238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng boundCheckMIR->dalvikInsn.vB = globalMinC; 4424238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmCompilerAppendMIR(entry, boundCheckMIR); 4434238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } else { 4444238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (loopAnalysis->loopBranchOpcode == OP_IF_LT || 4454238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng loopAnalysis->loopBranchOpcode == OP_IF_LE) { 446fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); 4479a1f81699cc05b58378ffb9aadb4e97677943791Dan Bornstein boundCheckMIR->dalvikInsn.opcode = kMirOpLowerBound; 4484238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng boundCheckMIR->dalvikInsn.vA = loopAnalysis->endConditionReg; 4494238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng boundCheckMIR->dalvikInsn.vB = globalMinC; 4504238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 45136bd13455b1e28c3918ced442f225e775363239eBen Cheng * If the end condition is ">" in the source, the check in the 45236bd13455b1e28c3918ced442f225e775363239eBen Cheng * Dalvik bytecode is OP_IF_LE. In this case add 1 back to the 45336bd13455b1e28c3918ced442f225e775363239eBen Cheng * constant field to reflect the fact that the smallest index 45436bd13455b1e28c3918ced442f225e775363239eBen Cheng * value is "endValue + constant + 1". 4554238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 45636bd13455b1e28c3918ced442f225e775363239eBen Cheng if (loopAnalysis->loopBranchOpcode == OP_IF_LE) { 4574238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng boundCheckMIR->dalvikInsn.vB++; 4584238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4594238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmCompilerAppendMIR(entry, boundCheckMIR); 4604238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } else if (loopAnalysis->loopBranchOpcode == OP_IF_LTZ) { 4614238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Array index will fall below 0 */ 4624238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (globalMinC < 0) { 463fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); 4649a1f81699cc05b58378ffb9aadb4e97677943791Dan Bornstein boundCheckMIR->dalvikInsn.opcode = kMirOpPunt; 4654238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmCompilerAppendMIR(entry, boundCheckMIR); 4664238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4674238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } else if (loopAnalysis->loopBranchOpcode == OP_IF_LEZ) { 4684238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Array index will fall below 0 */ 4694238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (globalMinC < -1) { 470fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); 4719a1f81699cc05b58378ffb9aadb4e97677943791Dan Bornstein boundCheckMIR->dalvikInsn.opcode = kMirOpPunt; 4724238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmCompilerAppendMIR(entry, boundCheckMIR); 4734238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4744238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } else { 475fc519dc8f4444f6d93806ec15ce7445b322070fdBill Buzbee LOGE("Jit: bad case in genHoistedChecks"); 476fc519dc8f4444f6d93806ec15ce7445b322070fdBill Buzbee dvmCompilerAbort(cUnit); 4774238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4784238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4794238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 4804238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4814238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} 4824238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 4834a41958266fb432629dea30832f4b3194667ba99Ben Cheng/* 4844a41958266fb432629dea30832f4b3194667ba99Ben Cheng * Main entry point to do loop optimization. 4854a41958266fb432629dea30832f4b3194667ba99Ben Cheng * Return false if sanity checks for loop formation/optimization failed. 4864a41958266fb432629dea30832f4b3194667ba99Ben Cheng */ 4874a41958266fb432629dea30832f4b3194667ba99Ben Chengbool dvmCompilerLoopOpt(CompilationUnit *cUnit) 4884238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng{ 489fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro LoopAnalysis *loopAnalysis = 490fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro (LoopAnalysis *)dvmCompilerNew(sizeof(LoopAnalysis), true); 4914238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 49200603079b8723b32c955513eae63a8f97898074dBen Cheng assert(((BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 0)) 49300603079b8723b32c955513eae63a8f97898074dBen Cheng ->blockType == kTraceEntryBlock); 49400603079b8723b32c955513eae63a8f97898074dBen Cheng assert(((BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 2)) 49500603079b8723b32c955513eae63a8f97898074dBen Cheng ->blockType == kDalvikByteCode); 49600603079b8723b32c955513eae63a8f97898074dBen Cheng assert(((BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 3)) 49700603079b8723b32c955513eae63a8f97898074dBen Cheng ->blockType == kTraceExitBlock); 4984238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 4994238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng cUnit->loopAnalysis = loopAnalysis; 5004238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 5014238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * Find live-in variables to the loop body so that we can fake their 5024238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * definitions in the entry block. 5034238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 50400603079b8723b32c955513eae63a8f97898074dBen Cheng dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerFindLocalLiveIn, 50500603079b8723b32c955513eae63a8f97898074dBen Cheng kAllNodes, 50600603079b8723b32c955513eae63a8f97898074dBen Cheng false /* isIterative */); 5074238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 5084238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Insert phi nodes to the loop body */ 5094238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng handlePhiPlacement(cUnit); 5104238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 51100603079b8723b32c955513eae63a8f97898074dBen Cheng dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerDoSSAConversion, 51200603079b8723b32c955513eae63a8f97898074dBen Cheng kAllNodes, 51300603079b8723b32c955513eae63a8f97898074dBen Cheng false /* isIterative */); 5144238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng fillPhiNodeContents(cUnit); 5154238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 5164238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Constant propagation */ 5174238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng cUnit->isConstantV = dvmAllocBitVector(cUnit->numSSARegs, false); 518fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro cUnit->constantValues = 519fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro (int *)dvmCompilerNew(sizeof(int) * cUnit->numSSARegs, 520fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro true); 5214238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmCompilerDataFlowAnalysisDispatcher(cUnit, 52200603079b8723b32c955513eae63a8f97898074dBen Cheng dvmCompilerDoConstantPropagation, 52300603079b8723b32c955513eae63a8f97898074dBen Cheng kAllNodes, 52400603079b8723b32c955513eae63a8f97898074dBen Cheng false /* isIterative */); 5254238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng DEBUG_LOOP(dumpConstants(cUnit);) 5264238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 5274238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Find induction variables - basic and dependent */ 528fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro loopAnalysis->ivList = 529fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro (GrowableList *)dvmCompilerNew(sizeof(GrowableList), true); 5304238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmInitGrowableList(loopAnalysis->ivList, 4); 5314238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng loopAnalysis->isIndVarV = dvmAllocBitVector(cUnit->numSSARegs, false); 5324238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmCompilerDataFlowAnalysisDispatcher(cUnit, 53300603079b8723b32c955513eae63a8f97898074dBen Cheng dvmCompilerFindInductionVariables, 53400603079b8723b32c955513eae63a8f97898074dBen Cheng kAllNodes, 53500603079b8723b32c955513eae63a8f97898074dBen Cheng false /* isIterative */); 5364238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng DEBUG_LOOP(dumpIVList(cUnit);) 5374238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 5384238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* If the loop turns out to be non-optimizable, return early */ 5394238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (!isLoopOptimizable(cUnit)) 5404a41958266fb432629dea30832f4b3194667ba99Ben Cheng return false; 5414238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 542fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro loopAnalysis->arrayAccessInfo = 543fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro (GrowableList *)dvmCompilerNew(sizeof(GrowableList), true); 5444238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmInitGrowableList(loopAnalysis->arrayAccessInfo, 4); 5454238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng loopAnalysis->bodyIsClean = doLoopBodyCodeMotion(cUnit); 5464238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng DEBUG_LOOP(dumpHoistedChecks(cUnit);) 5474238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 5484238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 5494238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * Convert the array access information into extended MIR code in the loop 5504238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * header. 5514238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 5524238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng genHoistedChecks(cUnit); 5534a41958266fb432629dea30832f4b3194667ba99Ben Cheng return true; 5544238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} 55546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 55646cd4fb73824ab57160994c149ce2d7a06923b83Ben Chengvoid resetBlockEdges(BasicBlock *bb) 55746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng{ 55846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->taken = NULL; 55946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->fallThrough = NULL; 56046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->successorBlockList.blockListType = kNotUsed; 56146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng} 56246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 56346cd4fb73824ab57160994c149ce2d7a06923b83Ben Chengstatic bool clearPredecessorVector(struct CompilationUnit *cUnit, 56446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng struct BasicBlock *bb) 56546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng{ 56646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmClearAllBits(bb->predecessors); 56746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng return false; 56846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng} 56946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 57046cd4fb73824ab57160994c149ce2d7a06923b83Ben Chengbool dvmCompilerFilterLoopBlocks(CompilationUnit *cUnit) 57146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng{ 57246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng BasicBlock *firstBB = cUnit->entryBlock->fallThrough; 57346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 57446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng int numPred = dvmCountSetBits(firstBB->predecessors); 57546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng /* 57646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng * A loop body should have at least two incoming edges. Here we go with the 57746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng * simple case and only form loops if numPred == 2. 57846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng */ 57946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (numPred != 2) return false; 58046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 58146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng BitVectorIterator bvIterator; 58246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng GrowableList *blockList = &cUnit->blockList; 58346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng BasicBlock *predBB = NULL; 58446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 58546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmBitVectorIteratorInit(firstBB->predecessors, &bvIterator); 58646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng while (true) { 58746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng int predIdx = dvmBitVectorIteratorNext(&bvIterator); 58846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (predIdx == -1) break; 58946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng predBB = (BasicBlock *) dvmGrowableListGetElement(blockList, predIdx); 59046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (predBB != cUnit->entryBlock) break; 59146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 59246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 59346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng /* Used to record which block is in the loop */ 59446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmClearAllBits(cUnit->tempBlockV); 59546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 59646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmCompilerSetBit(cUnit->tempBlockV, predBB->id); 59746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 59846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng /* Form a loop by only including iDom block that is also a predecessor */ 59946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng while (predBB != firstBB) { 60046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng BasicBlock *iDom = predBB->iDom; 60146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (!dvmIsBitSet(predBB->predecessors, iDom->id)) { 60246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng return false; 60346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng /* 60446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng * And don't form nested loops (ie by detecting if the branch target 60546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng * of iDom dominates iDom). 60646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng */ 60746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } else if (iDom->taken && 60846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmIsBitSet(iDom->dominators, iDom->taken->id) && 60946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng iDom != firstBB) { 61046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng return false; 61146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 61246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmCompilerSetBit(cUnit->tempBlockV, iDom->id); 61346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng predBB = iDom; 61446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 61546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 61646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng /* Add the entry block and first block */ 61746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmCompilerSetBit(cUnit->tempBlockV, firstBB->id); 61846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmCompilerSetBit(cUnit->tempBlockV, cUnit->entryBlock->id); 61946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 62046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng /* Now mark blocks not included in the loop as hidden */ 62146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng GrowableListIterator iterator; 62246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmGrowableListIteratorInit(&cUnit->blockList, &iterator); 62346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng while (true) { 62446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng BasicBlock *bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator); 62546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (bb == NULL) break; 62646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (!dvmIsBitSet(cUnit->tempBlockV, bb->id)) { 62746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->hidden = true; 62846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng /* Clear the insn list */ 62946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->firstMIRInsn = bb->lastMIRInsn = NULL; 63046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng resetBlockEdges(bb); 63146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 63246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 63346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 63446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmCompilerDataFlowAnalysisDispatcher(cUnit, clearPredecessorVector, 63546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng kAllNodes, false /* isIterative */); 63646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 63746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmGrowableListIteratorInit(&cUnit->blockList, &iterator); 63846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng while (true) { 63946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng BasicBlock *bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator); 64046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (bb == NULL) break; 64146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (dvmIsBitSet(cUnit->tempBlockV, bb->id)) { 64246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (bb->taken) { 64346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng /* 64446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng * exit block means we run into control-flow that we don't want 64546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng * to handle. 64646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng */ 64746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (bb->taken == cUnit->exitBlock) { 64846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng return false; 64946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 65046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (bb->taken->hidden) { 65146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->taken->blockType = kChainingCellNormal; 65246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->taken->hidden = false; 65346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 65446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmCompilerSetBit(bb->taken->predecessors, bb->id); 65546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 65646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (bb->fallThrough) { 65746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng /* 65846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng * exit block means we run into control-flow that we don't want 65946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng * to handle. 66046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng */ 66146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (bb->fallThrough == cUnit->exitBlock) { 66246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng return false; 66346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 66446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (bb->fallThrough->hidden) { 66546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->fallThrough->blockType = kChainingCellNormal; 66646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->fallThrough->hidden = false; 66746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 66846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmCompilerSetBit(bb->fallThrough->predecessors, bb->id); 66946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 67046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng /* Loop blocks shouldn't contain any successor blocks (yet) */ 67146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng assert(bb->successorBlockList.blockListType == kNotUsed); 67246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 67346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 67446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 67546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng return true; 67646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng} 677