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