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 24fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng#if 0 25fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng/* Debugging routines */ 264238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengstatic void dumpConstants(CompilationUnit *cUnit) 274238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng{ 284238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int i; 29c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE("LOOP starting offset: %x", cUnit->entryBlock->startOffset); 304238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng for (i = 0; i < cUnit->numSSARegs; i++) { 314238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (dvmIsBitSet(cUnit->isConstantV, i)) { 324238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int subNReg = dvmConvertSSARegToDalvik(cUnit, i); 33c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE("CONST: s%d(v%d_%d) has %d", i, 344238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng DECODE_REG(subNReg), DECODE_SUB(subNReg), 354238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng cUnit->constantValues[i]); 364238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 374238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 384238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} 394238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 404238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengstatic void dumpIVList(CompilationUnit *cUnit) 414238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng{ 424238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng unsigned int i; 434238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng GrowableList *ivList = cUnit->loopAnalysis->ivList; 444238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 454238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng for (i = 0; i < ivList->numUsed; i++) { 4632115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng InductionVariableInfo *ivInfo = 4732115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng (InductionVariableInfo *) ivList->elemList[i]; 4832115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng int iv = dvmConvertSSARegToDalvik(cUnit, ivInfo->ssaReg); 494238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Basic IV */ 504238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (ivInfo->ssaReg == ivInfo->basicSSAReg) { 51c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE("BIV %d: s%d(v%d_%d) + %d", i, 524238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ivInfo->ssaReg, 5332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng DECODE_REG(iv), DECODE_SUB(iv), 544238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ivInfo->inc); 554238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Dependent IV */ 564238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } else { 5732115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng int biv = dvmConvertSSARegToDalvik(cUnit, ivInfo->basicSSAReg); 5832115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng 59c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE("DIV %d: s%d(v%d_%d) = %d * s%d(v%d_%d) + %d", i, 604238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ivInfo->ssaReg, 6132115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng DECODE_REG(iv), DECODE_SUB(iv), 624238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ivInfo->m, 634238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ivInfo->basicSSAReg, 6432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng DECODE_REG(biv), DECODE_SUB(biv), 654238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ivInfo->c); 664238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 674238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 684238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} 694238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 70fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Chengstatic void dumpHoistedChecks(CompilationUnit *cUnit) 71fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng{ 72fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; 73fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng unsigned int i; 74fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng 75fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng for (i = 0; i < loopAnalysis->arrayAccessInfo->numUsed; i++) { 76fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng ArrayAccessInfo *arrayAccessInfo = 77fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng GET_ELEM_N(loopAnalysis->arrayAccessInfo, 78fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng ArrayAccessInfo*, i); 79fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng int arrayReg = DECODE_REG( 80fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->arrayReg)); 81fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng int idxReg = DECODE_REG( 82fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->ivReg)); 83c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE("Array access %d", i); 84c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE(" arrayReg %d", arrayReg); 85c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE(" idxReg %d", idxReg); 86c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE(" endReg %d", loopAnalysis->endConditionReg); 87c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE(" maxC %d", arrayAccessInfo->maxC); 88c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE(" minC %d", arrayAccessInfo->minC); 89c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE(" opcode %d", loopAnalysis->loopBranchOpcode); 90fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng } 91fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng} 92fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng 93fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng#endif 94fc075c2d1ae63c26f96e0c6eeb72efc898dbebbfBen Cheng 9532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Chengstatic BasicBlock *findPredecessorBlock(const CompilationUnit *cUnit, 9632115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng const BasicBlock *bb) 9732115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng{ 9832115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng int numPred = dvmCountSetBits(bb->predecessors); 9932115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng BitVectorIterator bvIterator; 10032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng dvmBitVectorIteratorInit(bb->predecessors, &bvIterator); 10132115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng 10232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng if (numPred == 1) { 10332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng int predIdx = dvmBitVectorIteratorNext(&bvIterator); 10432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng return (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 10532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng predIdx); 10632115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng /* First loop block */ 10732115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng } else if ((numPred == 2) && 10832115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng dvmIsBitSet(bb->predecessors, cUnit->entryBlock->id)) { 10932115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng while (true) { 11032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng int predIdx = dvmBitVectorIteratorNext(&bvIterator); 11132115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng if (predIdx == cUnit->entryBlock->id) continue; 11232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng return (BasicBlock *) dvmGrowableListGetElement(&cUnit->blockList, 11332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng predIdx); 11432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng } 11532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng /* Doesn't support other shape of control flow yet */ 11632115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng } else { 11732115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng return NULL; 11832115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng } 11932115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng} 12032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng 121535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng/* Used for normalized loop exit condition checks */ 122535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Chengstatic Opcode negateOpcode(Opcode opcode) 123535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng{ 124535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng switch (opcode) { 125535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng /* reg/reg cmp */ 126535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_EQ: 127535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng return OP_IF_NE; 128535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_NE: 129535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng return OP_IF_EQ; 130535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_LT: 131535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng return OP_IF_GE; 132535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_GE: 133535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng return OP_IF_LT; 134535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_GT: 135535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng return OP_IF_LE; 136535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_LE: 137535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng return OP_IF_GT; 138535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng /* reg/zero cmp */ 139535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_EQZ: 140535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng return OP_IF_NEZ; 141535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_NEZ: 142535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng return OP_IF_EQZ; 143535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_LTZ: 144535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng return OP_IF_GEZ; 145535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_GEZ: 146535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng return OP_IF_LTZ; 147535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_GTZ: 148535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng return OP_IF_LEZ; 149535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_LEZ: 150535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng return OP_IF_GTZ; 151535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng default: 152c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE("opcode %d cannot be negated", opcode); 153535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng dvmAbort(); 154535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng break; 155535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng } 1565d5b94c8d14b166af580d5dd5906db4f9527d6caCarl Shapiro return (Opcode)-1; // unreached 157535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng} 158535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng 1594238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng/* 1604238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * A loop is considered optimizable if: 161535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng * 1) It has one basic induction variable. 162535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng * 2) The loop back branch compares the BIV with a constant. 163535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng * 3) We need to normalize the loop exit condition so that the loop is exited 164535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng * via the taken path. 165535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng * 4) If it is a count-up loop, the condition is GE/GT. Otherwise it is 166535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng * LE/LT/LEZ/LTZ for a count-down loop. 1674a41958266fb432629dea30832f4b3194667ba99Ben Cheng * 168535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng * Return false for loops that fail the above tests. 1694238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 17032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Chengstatic bool isSimpleCountedLoop(CompilationUnit *cUnit) 1714238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng{ 1724238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng unsigned int i; 173535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng BasicBlock *loopBackBlock = cUnit->entryBlock->fallThrough; 1744238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; 1754238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 1764238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (loopAnalysis->numBasicIV != 1) return false; 1774238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng for (i = 0; i < loopAnalysis->ivList->numUsed; i++) { 1784238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng InductionVariableInfo *ivInfo; 1794238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 1804238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ivInfo = GET_ELEM_N(loopAnalysis->ivList, InductionVariableInfo*, i); 1814238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Count up or down loop? */ 1824238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (ivInfo->ssaReg == ivInfo->basicSSAReg) { 1834a41958266fb432629dea30832f4b3194667ba99Ben Cheng /* Infinite loop */ 1844a41958266fb432629dea30832f4b3194667ba99Ben Cheng if (ivInfo->inc == 0) { 1854a41958266fb432629dea30832f4b3194667ba99Ben Cheng return false; 1864a41958266fb432629dea30832f4b3194667ba99Ben Cheng } 1874238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng loopAnalysis->isCountUpLoop = ivInfo->inc > 0; 1884238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng break; 1894238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 1904238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 1914238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 192535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng /* Find the block that ends with a branch to exit the loop */ 193535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng while (true) { 194535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng loopBackBlock = findPredecessorBlock(cUnit, loopBackBlock); 195535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng /* Loop structure not recognized as counted blocks */ 196535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng if (loopBackBlock == NULL) { 197535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng return false; 198535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng } 199535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng /* Unconditional goto - continue to trace up the predecessor chain */ 200535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng if (loopBackBlock->taken == NULL) { 201535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng continue; 202535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng } 203535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng break; 204535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng } 205535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng 206535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng MIR *branch = loopBackBlock->lastMIRInsn; 2079a1f81699cc05b58378ffb9aadb4e97677943791Dan Bornstein Opcode opcode = branch->dalvikInsn.opcode; 2084238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 209535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng /* Last instruction is not a conditional branch - bail */ 210535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng if (dexGetFlagsFromOpcode(opcode) != (kInstrCanContinue|kInstrCanBranch)) { 2114238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng return false; 2124238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 2134238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 214535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng int endSSAReg; 215535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng int endDalvikReg; 2164238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 217535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng /* reg/reg comparison */ 218535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng if (branch->ssaRep->numUses == 2) { 219535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng if (branch->ssaRep->uses[0] == loopAnalysis->ssaBIV) { 220535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng endSSAReg = branch->ssaRep->uses[1]; 221535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng } else if (branch->ssaRep->uses[1] == loopAnalysis->ssaBIV) { 222535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng endSSAReg = branch->ssaRep->uses[0]; 223535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng opcode = negateOpcode(opcode); 224535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng } else { 2254238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng return false; 2264238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 227535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng endDalvikReg = dvmConvertSSARegToDalvik(cUnit, endSSAReg); 2284238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 2294238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * If the comparison is not between the BIV and a loop invariant, 230535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng * return false. endDalvikReg is loop invariant if one of the 231535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng * following is true: 2324a41958266fb432629dea30832f4b3194667ba99Ben Cheng * - It is not defined in the loop (ie DECODE_SUB returns 0) 2334a41958266fb432629dea30832f4b3194667ba99Ben Cheng * - It is reloaded with a constant 2344238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 235535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng if ((DECODE_SUB(endDalvikReg) != 0) && 236535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng !dvmIsBitSet(cUnit->isConstantV, endSSAReg)) { 2374238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng return false; 2384238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 239535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng /* Compare against zero */ 240535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng } else if (branch->ssaRep->numUses == 1) { 241535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng if (branch->ssaRep->uses[0] == loopAnalysis->ssaBIV) { 242535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng /* Keep the compiler happy */ 243535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng endDalvikReg = -1; 244535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng } else { 245535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng return false; 246535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng } 247535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng } else { 248535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng return false; 249535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng } 250535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng 251535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng /* Normalize the loop exit check as "if (iv op end) exit;" */ 252535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng if (loopBackBlock->taken->blockType == kDalvikByteCode) { 253535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng opcode = negateOpcode(opcode); 254535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng } 255535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng 256535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng if (loopAnalysis->isCountUpLoop) { 257535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng /* 258535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng * If the normalized condition op is not > or >=, this is not an 259535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng * optimization candidate. 260535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng */ 261535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng switch (opcode) { 262535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_GT: 263535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_GE: 264535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng break; 265535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng default: 266535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng return false; 267535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng } 268535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng loopAnalysis->endConditionReg = DECODE_REG(endDalvikReg); 2694238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } else { 2704238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 271535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng * If the normalized condition op is not < or <=, this is not an 272535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng * optimization candidate. 2734238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 274535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng switch (opcode) { 275535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_LT: 276535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_LE: 277535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng loopAnalysis->endConditionReg = DECODE_REG(endDalvikReg); 278535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng break; 279535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_LTZ: 280535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng case OP_IF_LEZ: 281535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng break; 282535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng default: 2834238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng return false; 2844238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 2854238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 286535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng /* 287535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng * Remember the normalized opcode, which will be used to determine the end 288535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng * value used for the yanked range checks. 289535abddae5a5d833612f0ff8a4504d24bfa9da10Ben Cheng */ 2909a1f81699cc05b58378ffb9aadb4e97677943791Dan Bornstein loopAnalysis->loopBranchOpcode = opcode; 2914238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng return true; 2924238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} 2934238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 2944238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng/* 2954238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * Record the upper and lower bound information for range checks for each 2964238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * induction variable. If array A is accessed by index "i+5", the upper and 2974238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * lower bound will be len(A)-5 and -5, respectively. 2984238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 2994238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengstatic void updateRangeCheckInfo(CompilationUnit *cUnit, int arrayReg, 3004238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int idxReg) 3014238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng{ 3024238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng InductionVariableInfo *ivInfo; 3034238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; 3044238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng unsigned int i, j; 3054238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3064238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng for (i = 0; i < loopAnalysis->ivList->numUsed; i++) { 3074238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ivInfo = GET_ELEM_N(loopAnalysis->ivList, InductionVariableInfo*, i); 3084238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (ivInfo->ssaReg == idxReg) { 3094238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ArrayAccessInfo *arrayAccessInfo = NULL; 3104238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng for (j = 0; j < loopAnalysis->arrayAccessInfo->numUsed; j++) { 3114238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ArrayAccessInfo *existingArrayAccessInfo = 3124238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng GET_ELEM_N(loopAnalysis->arrayAccessInfo, 3134238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ArrayAccessInfo*, 3144238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng j); 3154238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (existingArrayAccessInfo->arrayReg == arrayReg) { 3164238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (ivInfo->c > existingArrayAccessInfo->maxC) { 3174238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng existingArrayAccessInfo->maxC = ivInfo->c; 3184238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3194238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (ivInfo->c < existingArrayAccessInfo->minC) { 3204238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng existingArrayAccessInfo->minC = ivInfo->c; 3214238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3224238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng arrayAccessInfo = existingArrayAccessInfo; 3234238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng break; 3244238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3254238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3264238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (arrayAccessInfo == NULL) { 3274238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng arrayAccessInfo = 328fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro (ArrayAccessInfo *)dvmCompilerNew(sizeof(ArrayAccessInfo), 329fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro false); 3304238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng arrayAccessInfo->ivReg = ivInfo->basicSSAReg; 3314238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng arrayAccessInfo->arrayReg = arrayReg; 3324238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng arrayAccessInfo->maxC = (ivInfo->c > 0) ? ivInfo->c : 0; 3334238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng arrayAccessInfo->minC = (ivInfo->c < 0) ? ivInfo->c : 0; 3344238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmInsertGrowableList(loopAnalysis->arrayAccessInfo, 33500603079b8723b32c955513eae63a8f97898074dBen Cheng (intptr_t) arrayAccessInfo); 3364238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3374238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng break; 3384238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3394238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3404238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} 3414238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3424238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng/* Returns true if the loop body cannot throw any exceptions */ 3434238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengstatic bool doLoopBodyCodeMotion(CompilationUnit *cUnit) 3444238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng{ 34532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng BasicBlock *loopBody = cUnit->entryBlock->fallThrough; 3464238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng MIR *mir; 3474238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng bool loopBodyCanThrow = false; 3484238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3494238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng for (mir = loopBody->firstMIRInsn; mir; mir = mir->next) { 3504238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng DecodedInstruction *dInsn = &mir->dalvikInsn; 3514238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int dfAttributes = 3529a1f81699cc05b58378ffb9aadb4e97677943791Dan Bornstein dvmCompilerDataFlowAttributes[mir->dalvikInsn.opcode]; 3534238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3544238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Skip extended MIR instructions */ 35568e74fda779ca28ecb2b3af10d5193691603b3d0Ben Cheng if ((u2) dInsn->opcode >= kNumPackedOpcodes) continue; 3564238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 357e485276c6ba778cafa373b3b5c867f84e91b0bfdDan Bornstein int instrFlags = dexGetFlagsFromOpcode(dInsn->opcode); 3584238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3594238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Instruction is clean */ 3604238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if ((instrFlags & kInstrCanThrow) == 0) continue; 3614238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3624238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 3634238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * Currently we can only optimize away null and range checks. Punt on 3644238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * instructions that can throw due to other exceptions. 3654238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 3664238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (!(dfAttributes & DF_HAS_NR_CHECKS)) { 3674238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng loopBodyCanThrow = true; 3684238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng continue; 3694238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3704238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3714238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 3724238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * This comparison is redundant now, but we will have more than one 3734238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * group of flags to check soon. 3744238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 3754238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (dfAttributes & DF_HAS_NR_CHECKS) { 3764238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 3774238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * Check if the null check is applied on a loop invariant register? 3784238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * If the register's SSA id is less than the number of Dalvik 3794238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * registers, then it is loop invariant. 3804238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 3814238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int refIdx; 3824238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng switch (dfAttributes & DF_HAS_NR_CHECKS) { 3834238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng case DF_NULL_N_RANGE_CHECK_0: 3844238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng refIdx = 0; 3854238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng break; 3864238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng case DF_NULL_N_RANGE_CHECK_1: 3874238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng refIdx = 1; 3884238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng break; 3894238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng case DF_NULL_N_RANGE_CHECK_2: 3904238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng refIdx = 2; 3914238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng break; 3924238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng default: 3934238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng refIdx = 0; 394c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE("Jit: bad case in doLoopBodyCodeMotion"); 395fc519dc8f4444f6d93806ec15ce7445b322070fdBill Buzbee dvmCompilerAbort(cUnit); 3964238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 3974238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 3984238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int useIdx = refIdx + 1; 3994238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int subNRegArray = 4004238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmConvertSSARegToDalvik(cUnit, mir->ssaRep->uses[refIdx]); 4014238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int arraySub = DECODE_SUB(subNRegArray); 4024238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 4034238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 4044238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * If the register is never updated in the loop (ie subscript == 0), 4054238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * it is an optimization candidate. 4064238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 4074238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (arraySub != 0) { 4084238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng loopBodyCanThrow = true; 4094238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng continue; 4104238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4114238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 4124238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 4134238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * Then check if the range check can be hoisted out of the loop if 4144238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng * it is basic or dependent induction variable. 4154238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 4164238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (dvmIsBitSet(cUnit->loopAnalysis->isIndVarV, 4174238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng mir->ssaRep->uses[useIdx])) { 4184238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng mir->OptimizationFlags |= 41932115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng MIR_IGNORE_RANGE_CHECK | MIR_IGNORE_NULL_CHECK; 4204238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng updateRangeCheckInfo(cUnit, mir->ssaRep->uses[refIdx], 4214238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng mir->ssaRep->uses[useIdx]); 4224238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4234238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4244238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4254238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 4264238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng return !loopBodyCanThrow; 4274238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} 4284238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 4294238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Chengstatic void genHoistedChecks(CompilationUnit *cUnit) 4304238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng{ 4314238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng unsigned int i; 43232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng BasicBlock *entry = cUnit->entryBlock; 4334238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng LoopAnalysis *loopAnalysis = cUnit->loopAnalysis; 4344238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int globalMaxC = 0; 4354238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int globalMinC = 0; 4364238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Should be loop invariant */ 4374238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int idxReg = 0; 4384238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 4394238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng for (i = 0; i < loopAnalysis->arrayAccessInfo->numUsed; i++) { 4404238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ArrayAccessInfo *arrayAccessInfo = 4414238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng GET_ELEM_N(loopAnalysis->arrayAccessInfo, 4424238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng ArrayAccessInfo*, i); 4434238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng int arrayReg = DECODE_REG( 4444238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->arrayReg)); 4454238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng idxReg = DECODE_REG( 4464238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmConvertSSARegToDalvik(cUnit, arrayAccessInfo->ivReg)); 4474238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 448fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro MIR *rangeCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); 4499a1f81699cc05b58378ffb9aadb4e97677943791Dan Bornstein rangeCheckMIR->dalvikInsn.opcode = (loopAnalysis->isCountUpLoop) ? 4505d5b94c8d14b166af580d5dd5906db4f9527d6caCarl Shapiro (Opcode)kMirOpNullNRangeUpCheck : (Opcode)kMirOpNullNRangeDownCheck; 4514238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng rangeCheckMIR->dalvikInsn.vA = arrayReg; 4524238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng rangeCheckMIR->dalvikInsn.vB = idxReg; 4534238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng rangeCheckMIR->dalvikInsn.vC = loopAnalysis->endConditionReg; 4544238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng rangeCheckMIR->dalvikInsn.arg[0] = arrayAccessInfo->maxC; 4554238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng rangeCheckMIR->dalvikInsn.arg[1] = arrayAccessInfo->minC; 4564238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng rangeCheckMIR->dalvikInsn.arg[2] = loopAnalysis->loopBranchOpcode; 4574238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmCompilerAppendMIR(entry, rangeCheckMIR); 4584238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (arrayAccessInfo->maxC > globalMaxC) { 4594238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng globalMaxC = arrayAccessInfo->maxC; 4604238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4614238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (arrayAccessInfo->minC < globalMinC) { 4624238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng globalMinC = arrayAccessInfo->minC; 4634238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4644238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4654238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 4664238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (loopAnalysis->arrayAccessInfo->numUsed != 0) { 4674238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (loopAnalysis->isCountUpLoop) { 468fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); 4695d5b94c8d14b166af580d5dd5906db4f9527d6caCarl Shapiro boundCheckMIR->dalvikInsn.opcode = (Opcode)kMirOpLowerBound; 4704238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng boundCheckMIR->dalvikInsn.vA = idxReg; 4714238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng boundCheckMIR->dalvikInsn.vB = globalMinC; 4724238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmCompilerAppendMIR(entry, boundCheckMIR); 4734238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } else { 4744238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (loopAnalysis->loopBranchOpcode == OP_IF_LT || 4754238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng loopAnalysis->loopBranchOpcode == OP_IF_LE) { 476fc75f3ed87b55d625b6054e18645da5cbdba31c6Carl Shapiro MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), true); 4775d5b94c8d14b166af580d5dd5906db4f9527d6caCarl Shapiro boundCheckMIR->dalvikInsn.opcode = (Opcode)kMirOpLowerBound; 4784238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng boundCheckMIR->dalvikInsn.vA = loopAnalysis->endConditionReg; 4794238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng boundCheckMIR->dalvikInsn.vB = globalMinC; 4804238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* 48136bd13455b1e28c3918ced442f225e775363239eBen Cheng * If the end condition is ">" in the source, the check in the 48236bd13455b1e28c3918ced442f225e775363239eBen Cheng * Dalvik bytecode is OP_IF_LE. In this case add 1 back to the 48336bd13455b1e28c3918ced442f225e775363239eBen Cheng * constant field to reflect the fact that the smallest index 48436bd13455b1e28c3918ced442f225e775363239eBen Cheng * value is "endValue + constant + 1". 4854238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng */ 48636bd13455b1e28c3918ced442f225e775363239eBen Cheng if (loopAnalysis->loopBranchOpcode == OP_IF_LE) { 4874238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng boundCheckMIR->dalvikInsn.vB++; 4884238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4894238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmCompilerAppendMIR(entry, boundCheckMIR); 4904238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } else if (loopAnalysis->loopBranchOpcode == OP_IF_LTZ) { 4914238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Array index will fall below 0 */ 4924238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (globalMinC < 0) { 49332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), 49432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng true); 4955d5b94c8d14b166af580d5dd5906db4f9527d6caCarl Shapiro boundCheckMIR->dalvikInsn.opcode = (Opcode)kMirOpPunt; 4964238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmCompilerAppendMIR(entry, boundCheckMIR); 4974238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 4984238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } else if (loopAnalysis->loopBranchOpcode == OP_IF_LEZ) { 4994238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng /* Array index will fall below 0 */ 5004238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng if (globalMinC < -1) { 50132115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng MIR *boundCheckMIR = (MIR *)dvmCompilerNew(sizeof(MIR), 50232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng true); 5035d5b94c8d14b166af580d5dd5906db4f9527d6caCarl Shapiro boundCheckMIR->dalvikInsn.opcode = (Opcode)kMirOpPunt; 5044238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng dvmCompilerAppendMIR(entry, boundCheckMIR); 5054238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 5064238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } else { 507c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2efSteve Block ALOGE("Jit: bad case in genHoistedChecks"); 508fc519dc8f4444f6d93806ec15ce7445b322070fdBill Buzbee dvmCompilerAbort(cUnit); 5094238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 5104238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 5114238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng } 5124238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng} 5134238ec2ad1ace5103b2206a483f5f03d2e96c476Ben Cheng 51446cd4fb73824ab57160994c149ce2d7a06923b83Ben Chengvoid resetBlockEdges(BasicBlock *bb) 51546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng{ 51646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->taken = NULL; 51746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->fallThrough = NULL; 51846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->successorBlockList.blockListType = kNotUsed; 51946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng} 52046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 52146cd4fb73824ab57160994c149ce2d7a06923b83Ben Chengstatic bool clearPredecessorVector(struct CompilationUnit *cUnit, 52246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng struct BasicBlock *bb) 52346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng{ 52446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmClearAllBits(bb->predecessors); 52546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng return false; 52646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng} 52746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 52846cd4fb73824ab57160994c149ce2d7a06923b83Ben Chengbool dvmCompilerFilterLoopBlocks(CompilationUnit *cUnit) 52946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng{ 53046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng BasicBlock *firstBB = cUnit->entryBlock->fallThrough; 53146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 53246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng int numPred = dvmCountSetBits(firstBB->predecessors); 53346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng /* 53432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * A loop body should have at least two incoming edges. 53546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng */ 53632115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng if (numPred < 2) return false; 53746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 53846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng GrowableList *blockList = &cUnit->blockList; 53946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 54032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng /* Record blocks included in the loop */ 54146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmClearAllBits(cUnit->tempBlockV); 54246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 54332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng dvmCompilerSetBit(cUnit->tempBlockV, cUnit->entryBlock->id); 54432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng dvmCompilerSetBit(cUnit->tempBlockV, firstBB->id); 54532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng 54632115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng BasicBlock *bodyBB = firstBB; 54746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 54832115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng /* 54932115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * First try to include the fall-through block in the loop, then the taken 55032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * block. Stop loop formation on the first backward branch that enters the 55132115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * first block (ie only include the inner-most loop). 55232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng */ 55332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng while (true) { 55432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng /* Loop formed */ 5559f54185b4186def90351903bb2e97090e06ab559Ben Cheng if (bodyBB->taken == firstBB) { 5569f54185b4186def90351903bb2e97090e06ab559Ben Cheng /* Check if the fallThrough edge will cause a nested loop */ 5579f54185b4186def90351903bb2e97090e06ab559Ben Cheng if (bodyBB->fallThrough && 5589f54185b4186def90351903bb2e97090e06ab559Ben Cheng dvmIsBitSet(cUnit->tempBlockV, bodyBB->fallThrough->id)) { 5599f54185b4186def90351903bb2e97090e06ab559Ben Cheng return false; 5609f54185b4186def90351903bb2e97090e06ab559Ben Cheng } 5619f54185b4186def90351903bb2e97090e06ab559Ben Cheng /* Single loop formed */ 5629f54185b4186def90351903bb2e97090e06ab559Ben Cheng break; 5639f54185b4186def90351903bb2e97090e06ab559Ben Cheng } else if (bodyBB->fallThrough == firstBB) { 5649f54185b4186def90351903bb2e97090e06ab559Ben Cheng /* Check if the taken edge will cause a nested loop */ 5659f54185b4186def90351903bb2e97090e06ab559Ben Cheng if (bodyBB->taken && 5669f54185b4186def90351903bb2e97090e06ab559Ben Cheng dvmIsBitSet(cUnit->tempBlockV, bodyBB->taken->id)) { 5679f54185b4186def90351903bb2e97090e06ab559Ben Cheng return false; 5689f54185b4186def90351903bb2e97090e06ab559Ben Cheng } 5699f54185b4186def90351903bb2e97090e06ab559Ben Cheng /* Single loop formed */ 5709f54185b4186def90351903bb2e97090e06ab559Ben Cheng break; 5719f54185b4186def90351903bb2e97090e06ab559Ben Cheng } 57232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng 57332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng /* Inner loops formed first - quit */ 57432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng if (bodyBB->fallThrough && 57532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng dvmIsBitSet(cUnit->tempBlockV, bodyBB->fallThrough->id)) { 57646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng return false; 57732115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng } 57832115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng if (bodyBB->taken && 57932115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng dvmIsBitSet(cUnit->tempBlockV, bodyBB->taken->id)) { 58046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng return false; 58146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 58232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng 58332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng if (bodyBB->fallThrough) { 58432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng if (bodyBB->fallThrough->iDom == bodyBB) { 58532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng bodyBB = bodyBB->fallThrough; 58632115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng dvmCompilerSetBit(cUnit->tempBlockV, bodyBB->id); 58732115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng /* 58832115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * Loop formation to be detected at the beginning of next 58932115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * iteration. 59032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng */ 59132115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng continue; 59232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng } 59332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng } 59432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng if (bodyBB->taken) { 59532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng if (bodyBB->taken->iDom == bodyBB) { 59632115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng bodyBB = bodyBB->taken; 59732115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng dvmCompilerSetBit(cUnit->tempBlockV, bodyBB->id); 59832115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng /* 59932115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * Loop formation to be detected at the beginning of next 60032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * iteration. 60132115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng */ 60232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng continue; 60332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng } 60432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng } 60532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng /* 60632115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * Current block is not the immediate dominator of either fallthrough 60732115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * nor taken block - bail out of loop formation. 60832115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng */ 60932115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng return false; 61046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 61146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 61246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 61346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng /* Now mark blocks not included in the loop as hidden */ 61446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng GrowableListIterator iterator; 61532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng dvmGrowableListIteratorInit(blockList, &iterator); 61646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng while (true) { 61746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng BasicBlock *bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator); 61846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (bb == NULL) break; 61946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (!dvmIsBitSet(cUnit->tempBlockV, bb->id)) { 62046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->hidden = true; 62146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng /* Clear the insn list */ 62246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->firstMIRInsn = bb->lastMIRInsn = NULL; 62346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng resetBlockEdges(bb); 62446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 62546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 62646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 62746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmCompilerDataFlowAnalysisDispatcher(cUnit, clearPredecessorVector, 62846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng kAllNodes, false /* isIterative */); 62946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 63032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng dvmGrowableListIteratorInit(blockList, &iterator); 63146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng while (true) { 63246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng BasicBlock *bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator); 63346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (bb == NULL) break; 63446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (dvmIsBitSet(cUnit->tempBlockV, bb->id)) { 63546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (bb->taken) { 63646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng /* 63746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng * exit block means we run into control-flow that we don't want 63846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng * to handle. 63946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng */ 64046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (bb->taken == cUnit->exitBlock) { 64146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng return false; 64246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 64346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (bb->taken->hidden) { 64446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->taken->blockType = kChainingCellNormal; 64546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->taken->hidden = false; 64646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 64746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmCompilerSetBit(bb->taken->predecessors, bb->id); 64846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 64946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (bb->fallThrough) { 65046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng /* 65146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng * exit block means we run into control-flow that we don't want 65246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng * to handle. 65346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng */ 65446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (bb->fallThrough == cUnit->exitBlock) { 65546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng return false; 65646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 65746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng if (bb->fallThrough->hidden) { 65846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->fallThrough->blockType = kChainingCellNormal; 65946cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng bb->fallThrough->hidden = false; 66046cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 66146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng dvmCompilerSetBit(bb->fallThrough->predecessors, bb->id); 66246cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 66346cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng /* Loop blocks shouldn't contain any successor blocks (yet) */ 66446cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng assert(bb->successorBlockList.blockListType == kNotUsed); 66546cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 66646cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng } 66732115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng return true; 66832115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng} 66932115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng 67032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng/* 67132115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * Main entry point to do loop optimization. 67232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * Return false if sanity checks for loop formation/optimization failed. 67332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng */ 67432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Chengbool dvmCompilerLoopOpt(CompilationUnit *cUnit) 67532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng{ 67632115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng LoopAnalysis *loopAnalysis = 67732115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng (LoopAnalysis *)dvmCompilerNew(sizeof(LoopAnalysis), true); 67832115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng cUnit->loopAnalysis = loopAnalysis; 67932115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng 68032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng /* Constant propagation */ 6813897bab038a89d09c97eec00653cd3a2870d2c06Elliott Hughes cUnit->isConstantV = dvmCompilerAllocBitVector(cUnit->numSSARegs, false); 68232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng cUnit->constantValues = 68332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng (int *)dvmCompilerNew(sizeof(int) * cUnit->numSSARegs, 68432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng true); 68532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng dvmCompilerDataFlowAnalysisDispatcher(cUnit, 68632115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng dvmCompilerDoConstantPropagation, 68732115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng kAllNodes, 68832115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng false /* isIterative */); 68932115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng DEBUG_LOOP(dumpConstants(cUnit);) 69032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng 69132115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng /* Find induction variables - basic and dependent */ 69232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng loopAnalysis->ivList = 69332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng (GrowableList *)dvmCompilerNew(sizeof(GrowableList), true); 69432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng dvmInitGrowableList(loopAnalysis->ivList, 4); 6953897bab038a89d09c97eec00653cd3a2870d2c06Elliott Hughes loopAnalysis->isIndVarV = dvmCompilerAllocBitVector(cUnit->numSSARegs, false); 69632115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng dvmCompilerDataFlowAnalysisDispatcher(cUnit, 69732115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng dvmCompilerFindInductionVariables, 69832115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng kAllNodes, 69932115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng false /* isIterative */); 70032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng DEBUG_LOOP(dumpIVList(cUnit);) 70132115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng 70232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng /* Only optimize array accesses for simple counted loop for now */ 70332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng if (!isSimpleCountedLoop(cUnit)) 70432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng return false; 70532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng 70632115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng loopAnalysis->arrayAccessInfo = 70732115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng (GrowableList *)dvmCompilerNew(sizeof(GrowableList), true); 70832115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng dvmInitGrowableList(loopAnalysis->arrayAccessInfo, 4); 70932115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng loopAnalysis->bodyIsClean = doLoopBodyCodeMotion(cUnit); 71032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng DEBUG_LOOP(dumpHoistedChecks(cUnit);) 71146cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng 71232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng /* 71332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * Convert the array access information into extended MIR code in the loop 71432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * header. 71532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng */ 71632115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng genHoistedChecks(cUnit); 71746cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng return true; 71846cd4fb73824ab57160994c149ce2d7a06923b83Ben Cheng} 71932115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng 72032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng/* 72132115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * Select the target block of the backward branch. 72232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng */ 72332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Chengvoid dvmCompilerInsertBackwardChaining(CompilationUnit *cUnit) 72432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng{ 72532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng /* 72632115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * If we are not in self-verification or profiling mode, the backward 72732115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * branch can go to the entryBlock->fallThrough directly. Suspend polling 72832115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * code will be generated along the backward branch to honor the suspend 72932115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * requests. 73032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng */ 7310c2dc522d0e120f346cf0a40c8cf0c93346131c2Dong-Yuan Chen#ifndef ARCH_IA32 73232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng#if !defined(WITH_SELF_VERIFICATION) 73332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng if (gDvmJit.profileMode != kTraceProfilingContinuous && 73432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng gDvmJit.profileMode != kTraceProfilingPeriodicOn) { 73532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng return; 73632115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng } 73732115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng#endif 7380c2dc522d0e120f346cf0a40c8cf0c93346131c2Dong-Yuan Chen#endif 7390c2dc522d0e120f346cf0a40c8cf0c93346131c2Dong-Yuan Chen 74032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng /* 74132115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * In self-verification or profiling mode, the backward branch is altered 74232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * to go to the backward chaining cell. Without using the backward chaining 74332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * cell we won't be able to do check-pointing on the target PC, or count the 74432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng * number of iterations accurately. 74532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng */ 74632115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng BasicBlock *firstBB = cUnit->entryBlock->fallThrough; 74732115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng BasicBlock *backBranchBB = findPredecessorBlock(cUnit, firstBB); 74832115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng if (backBranchBB->taken == firstBB) { 74932115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng backBranchBB->taken = cUnit->backChainBlock; 75032115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng } else { 75132115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng assert(backBranchBB->fallThrough == firstBB); 75232115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng backBranchBB->fallThrough = cUnit->backChainBlock; 75332115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng } 75432115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng cUnit->backChainBlock->startOffset = firstBB->startOffset; 75532115a971ea00ab2421fab4e4a3afa6c50c82173Ben Cheng} 756