Home | History | Annotate | Download | only in compiler 
      1 /*
      2  * Copyright (C) 2010 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 "Dataflow.h"
     19 #include "Loop.h"
     20 #include "libdex/DexOpcodes.h"
     21 
     22 /* Enter the node to the dfsOrder list then visit its successors */
     23 static void recordDFSPreOrder(CompilationUnit *cUnit, BasicBlock *block)
     24 {
     25 
     26     if (block->visited || block->hidden) return;
     27     block->visited = true;
     28 
     29     /* Enqueue the block id */
     30     dvmInsertGrowableList(&cUnit->dfsOrder, block->id);
     31 
     32     if (block->fallThrough) recordDFSPreOrder(cUnit, block->fallThrough);
     33     if (block->taken) recordDFSPreOrder(cUnit, block->taken);
     34     if (block->successorBlockList.blockListType != kNotUsed) {
     35         GrowableListIterator iterator;
     36         dvmGrowableListIteratorInit(&block->successorBlockList.blocks,
     37                                     &iterator);
     38         while (true) {
     39             SuccessorBlockInfo *successorBlockInfo =
     40                 (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator);
     41             if (successorBlockInfo == NULL) break;
     42             BasicBlock *succBB = successorBlockInfo->block;
     43             recordDFSPreOrder(cUnit, succBB);
     44         }
     45     }
     46     return;
     47 }
     48 
     49 /* Sort the blocks by the Depth-First-Search pre-order */
     50 static void computeDFSOrder(CompilationUnit *cUnit)
     51 {
     52     /* Initialize or reset the DFS order list */
     53     if (cUnit->dfsOrder.elemList == NULL) {
     54         dvmInitGrowableList(&cUnit->dfsOrder, cUnit->numBlocks);
     55     } else {
     56         /* Just reset the used length on the counter */
     57         cUnit->dfsOrder.numUsed = 0;
     58     }
     59 
     60     dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerClearVisitedFlag,
     61                                           kAllNodes,
     62                                           false /* isIterative */);
     63 
     64     recordDFSPreOrder(cUnit, cUnit->entryBlock);
     65     cUnit->numReachableBlocks = cUnit->dfsOrder.numUsed;
     66 }
     67 
     68 /*
     69  * Mark block bit on the per-Dalvik register vector to denote that Dalvik
     70  * register idx is defined in BasicBlock bb.
     71  */
     72 static bool fillDefBlockMatrix(CompilationUnit *cUnit, BasicBlock *bb)
     73 {
     74     if (bb->dataFlowInfo == NULL) return false;
     75 
     76     BitVectorIterator iterator;
     77 
     78     dvmBitVectorIteratorInit(bb->dataFlowInfo->defV, &iterator);
     79     while (true) {
     80         int idx = dvmBitVectorIteratorNext(&iterator);
     81         if (idx == -1) break;
     82         /* Block bb defines register idx */
     83         dvmCompilerSetBit(cUnit->defBlockMatrix[idx], bb->id);
     84     }
     85     return true;
     86 }
     87 
     88 static void computeDefBlockMatrix(CompilationUnit *cUnit)
     89 {
     90     int numRegisters = cUnit->numDalvikRegisters;
     91     /* Allocate numDalvikRegisters bit vector pointers */
     92     cUnit->defBlockMatrix = (BitVector **)
     93         dvmCompilerNew(sizeof(BitVector *) * numRegisters, true);
     94     int i;
     95 
     96     /* Initialize numRegister vectors with numBlocks bits each */
     97     for (i = 0; i < numRegisters; i++) {
     98         cUnit->defBlockMatrix[i] = dvmCompilerAllocBitVector(cUnit->numBlocks,
     99                                                              false);
    100     }
    101     dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerFindLocalLiveIn,
    102                                           kAllNodes,
    103                                           false /* isIterative */);
    104     dvmCompilerDataFlowAnalysisDispatcher(cUnit, fillDefBlockMatrix,
    105                                           kAllNodes,
    106                                           false /* isIterative */);
    107 
    108     if (cUnit->jitMode == kJitMethod) {
    109         /*
    110          * Also set the incoming parameters as defs in the entry block.
    111          * Only need to handle the parameters for the outer method.
    112          */
    113         int inReg = cUnit->method->registersSize - cUnit->method->insSize;
    114         for (; inReg < cUnit->method->registersSize; inReg++) {
    115             dvmCompilerSetBit(cUnit->defBlockMatrix[inReg],
    116                               cUnit->entryBlock->id);
    117         }
    118     }
    119 }
    120 
    121 /* Compute the post-order traversal of the CFG */
    122 static void computeDomPostOrderTraversal(CompilationUnit *cUnit, BasicBlock *bb)
    123 {
    124     BitVectorIterator bvIterator;
    125     dvmBitVectorIteratorInit(bb->iDominated, &bvIterator);
    126     GrowableList *blockList = &cUnit->blockList;
    127 
    128     /* Iterate through the dominated blocks first */
    129     while (true) {
    130         int bbIdx = dvmBitVectorIteratorNext(&bvIterator);
    131         if (bbIdx == -1) break;
    132         BasicBlock *dominatedBB =
    133             (BasicBlock *) dvmGrowableListGetElement(blockList, bbIdx);
    134         computeDomPostOrderTraversal(cUnit, dominatedBB);
    135     }
    136 
    137     /* Enter the current block id */
    138     dvmInsertGrowableList(&cUnit->domPostOrderTraversal, bb->id);
    139 
    140     /* hacky loop detection */
    141     if (bb->taken && dvmIsBitSet(bb->dominators, bb->taken->id)) {
    142         cUnit->hasLoop = true;
    143     }
    144 }
    145 
    146 static void checkForDominanceFrontier(BasicBlock *domBB,
    147                                       const BasicBlock *succBB)
    148 {
    149     /*
    150      * TODO - evaluate whether phi will ever need to be inserted into exit
    151      * blocks.
    152      */
    153     if (succBB->iDom != domBB &&
    154         succBB->blockType == kDalvikByteCode &&
    155         succBB->hidden == false) {
    156         dvmSetBit(domBB->domFrontier, succBB->id);
    157     }
    158 }
    159 
    160 /* Worker function to compute the dominance frontier */
    161 static bool computeDominanceFrontier(CompilationUnit *cUnit, BasicBlock *bb)
    162 {
    163     GrowableList *blockList = &cUnit->blockList;
    164 
    165     /* Calculate DF_local */
    166     if (bb->taken) {
    167         checkForDominanceFrontier(bb, bb->taken);
    168     }
    169     if (bb->fallThrough) {
    170         checkForDominanceFrontier(bb, bb->fallThrough);
    171     }
    172     if (bb->successorBlockList.blockListType != kNotUsed) {
    173         GrowableListIterator iterator;
    174         dvmGrowableListIteratorInit(&bb->successorBlockList.blocks,
    175                                     &iterator);
    176         while (true) {
    177             SuccessorBlockInfo *successorBlockInfo =
    178                 (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator);
    179             if (successorBlockInfo == NULL) break;
    180             BasicBlock *succBB = successorBlockInfo->block;
    181             checkForDominanceFrontier(bb, succBB);
    182         }
    183     }
    184 
    185     /* Calculate DF_up */
    186     BitVectorIterator bvIterator;
    187     dvmBitVectorIteratorInit(bb->iDominated, &bvIterator);
    188     while (true) {
    189         int dominatedIdx = dvmBitVectorIteratorNext(&bvIterator);
    190         if (dominatedIdx == -1) break;
    191         BasicBlock *dominatedBB = (BasicBlock *)
    192             dvmGrowableListGetElement(blockList, dominatedIdx);
    193         BitVectorIterator dfIterator;
    194         dvmBitVectorIteratorInit(dominatedBB->domFrontier, &dfIterator);
    195         while (true) {
    196             int dfUpIdx = dvmBitVectorIteratorNext(&dfIterator);
    197             if (dfUpIdx == -1) break;
    198             BasicBlock *dfUpBlock = (BasicBlock *)
    199                 dvmGrowableListGetElement(blockList, dfUpIdx);
    200             checkForDominanceFrontier(bb, dfUpBlock);
    201         }
    202     }
    203 
    204     return true;
    205 }
    206 
    207 /* Worker function for initializing domination-related data structures */
    208 static bool initializeDominationInfo(CompilationUnit *cUnit, BasicBlock *bb)
    209 {
    210     int numTotalBlocks = cUnit->blockList.numUsed;
    211 
    212     if (bb->dominators == NULL ) {
    213         bb->dominators = dvmCompilerAllocBitVector(numTotalBlocks,
    214                                                    false /* expandable */);
    215         bb->iDominated = dvmCompilerAllocBitVector(numTotalBlocks,
    216                                                    false /* expandable */);
    217         bb->domFrontier = dvmCompilerAllocBitVector(numTotalBlocks,
    218                                                    false /* expandable */);
    219     } else {
    220         dvmClearAllBits(bb->dominators);
    221         dvmClearAllBits(bb->iDominated);
    222         dvmClearAllBits(bb->domFrontier);
    223     }
    224     /* Set all bits in the dominator vector */
    225     dvmSetInitialBits(bb->dominators, numTotalBlocks);
    226 
    227     return true;
    228 }
    229 
    230 /* Worker function to compute each block's dominators */
    231 static bool computeBlockDominators(CompilationUnit *cUnit, BasicBlock *bb)
    232 {
    233     GrowableList *blockList = &cUnit->blockList;
    234     int numTotalBlocks = blockList->numUsed;
    235     BitVector *tempBlockV = cUnit->tempBlockV;
    236     BitVectorIterator bvIterator;
    237 
    238     /*
    239      * The dominator of the entry block has been preset to itself and we need
    240      * to skip the calculation here.
    241      */
    242     if (bb == cUnit->entryBlock) return false;
    243 
    244     dvmSetInitialBits(tempBlockV, numTotalBlocks);
    245 
    246     /* Iterate through the predecessors */
    247     dvmBitVectorIteratorInit(bb->predecessors, &bvIterator);
    248     while (true) {
    249         int predIdx = dvmBitVectorIteratorNext(&bvIterator);
    250         if (predIdx == -1) break;
    251         BasicBlock *predBB = (BasicBlock *) dvmGrowableListGetElement(
    252                                  blockList, predIdx);
    253         /* tempBlockV = tempBlockV ^ dominators */
    254         dvmIntersectBitVectors(tempBlockV, tempBlockV, predBB->dominators);
    255     }
    256     dvmSetBit(tempBlockV, bb->id);
    257     if (dvmCompareBitVectors(tempBlockV, bb->dominators)) {
    258         dvmCopyBitVector(bb->dominators, tempBlockV);
    259         return true;
    260     }
    261     return false;
    262 }
    263 
    264 /* Worker function to compute the idom */
    265 static bool computeImmediateDominator(CompilationUnit *cUnit, BasicBlock *bb)
    266 {
    267     GrowableList *blockList = &cUnit->blockList;
    268     BitVector *tempBlockV = cUnit->tempBlockV;
    269     BitVectorIterator bvIterator;
    270     BasicBlock *iDom;
    271 
    272     if (bb == cUnit->entryBlock) return false;
    273 
    274     dvmCopyBitVector(tempBlockV, bb->dominators);
    275     dvmClearBit(tempBlockV, bb->id);
    276     dvmBitVectorIteratorInit(tempBlockV, &bvIterator);
    277 
    278     /* Should not see any dead block */
    279     assert(dvmCountSetBits(tempBlockV) != 0);
    280     if (dvmCountSetBits(tempBlockV) == 1) {
    281         iDom = (BasicBlock *) dvmGrowableListGetElement(
    282                        blockList, dvmBitVectorIteratorNext(&bvIterator));
    283         bb->iDom = iDom;
    284     } else {
    285         int iDomIdx = dvmBitVectorIteratorNext(&bvIterator);
    286         assert(iDomIdx != -1);
    287         while (true) {
    288             int nextDom = dvmBitVectorIteratorNext(&bvIterator);
    289             if (nextDom == -1) break;
    290             BasicBlock *nextDomBB = (BasicBlock *)
    291                 dvmGrowableListGetElement(blockList, nextDom);
    292             /* iDom dominates nextDom - set new iDom */
    293             if (dvmIsBitSet(nextDomBB->dominators, iDomIdx)) {
    294                 iDomIdx = nextDom;
    295             }
    296 
    297         }
    298         iDom = (BasicBlock *) dvmGrowableListGetElement(blockList, iDomIdx);
    299         /* Set the immediate dominator block for bb */
    300         bb->iDom = iDom;
    301     }
    302     /* Add bb to the iDominated set of the immediate dominator block */
    303     dvmCompilerSetBit(iDom->iDominated, bb->id);
    304     return true;
    305 }
    306 
    307 /* Compute dominators, immediate dominator, and dominance fronter */
    308 static void computeDominators(CompilationUnit *cUnit)
    309 {
    310     int numReachableBlocks = cUnit->numReachableBlocks;
    311     int numTotalBlocks = cUnit->blockList.numUsed;
    312 
    313     /* Initialize domination-related data structures */
    314     dvmCompilerDataFlowAnalysisDispatcher(cUnit, initializeDominationInfo,
    315                                           kReachableNodes,
    316                                           false /* isIterative */);
    317 
    318     /* Set the dominator for the root node */
    319     dvmClearAllBits(cUnit->entryBlock->dominators);
    320     dvmSetBit(cUnit->entryBlock->dominators, cUnit->entryBlock->id);
    321 
    322     if (cUnit->tempBlockV == NULL) {
    323         cUnit->tempBlockV = dvmCompilerAllocBitVector(numTotalBlocks,
    324                                                   false /* expandable */);
    325     } else {
    326         dvmClearAllBits(cUnit->tempBlockV);
    327     }
    328     dvmCompilerDataFlowAnalysisDispatcher(cUnit, computeBlockDominators,
    329                                           kPreOrderDFSTraversal,
    330                                           true /* isIterative */);
    331 
    332     cUnit->entryBlock->iDom = NULL;
    333     dvmCompilerDataFlowAnalysisDispatcher(cUnit, computeImmediateDominator,
    334                                           kReachableNodes,
    335                                           false /* isIterative */);
    336 
    337     /*
    338      * Now go ahead and compute the post order traversal based on the
    339      * iDominated sets.
    340      */
    341     if (cUnit->domPostOrderTraversal.elemList == NULL) {
    342         dvmInitGrowableList(&cUnit->domPostOrderTraversal, numReachableBlocks);
    343     } else {
    344         cUnit->domPostOrderTraversal.numUsed = 0;
    345     }
    346 
    347     computeDomPostOrderTraversal(cUnit, cUnit->entryBlock);
    348     assert(cUnit->domPostOrderTraversal.numUsed ==
    349            (unsigned) cUnit->numReachableBlocks);
    350 
    351     /* Now compute the dominance frontier for each block */
    352     dvmCompilerDataFlowAnalysisDispatcher(cUnit, computeDominanceFrontier,
    353                                           kPostOrderDOMTraversal,
    354                                           false /* isIterative */);
    355 }
    356 
    357 /*
    358  * Perform dest U= src1 ^ ~src2
    359  * This is probably not general enough to be placed in BitVector.[ch].
    360  */
    361 static void computeSuccLiveIn(BitVector *dest,
    362                               const BitVector *src1,
    363                               const BitVector *src2)
    364 {
    365     if (dest->storageSize != src1->storageSize ||
    366         dest->storageSize != src2->storageSize ||
    367         dest->expandable != src1->expandable ||
    368         dest->expandable != src2->expandable) {
    369         ALOGE("Incompatible set properties");
    370         dvmAbort();
    371     }
    372 
    373     unsigned int idx;
    374     for (idx = 0; idx < dest->storageSize; idx++) {
    375         dest->storage[idx] |= src1->storage[idx] & ~src2->storage[idx];
    376     }
    377 }
    378 
    379 /*
    380  * Iterate through all successor blocks and propagate up the live-in sets.
    381  * The calculated result is used for phi-node pruning - where we only need to
    382  * insert a phi node if the variable is live-in to the block.
    383  */
    384 static bool computeBlockLiveIns(CompilationUnit *cUnit, BasicBlock *bb)
    385 {
    386     BitVector *tempDalvikRegisterV = cUnit->tempDalvikRegisterV;
    387 
    388     if (bb->dataFlowInfo == NULL) return false;
    389     dvmCopyBitVector(tempDalvikRegisterV, bb->dataFlowInfo->liveInV);
    390     if (bb->taken && bb->taken->dataFlowInfo)
    391         computeSuccLiveIn(tempDalvikRegisterV, bb->taken->dataFlowInfo->liveInV,
    392                           bb->dataFlowInfo->defV);
    393     if (bb->fallThrough && bb->fallThrough->dataFlowInfo)
    394         computeSuccLiveIn(tempDalvikRegisterV,
    395                           bb->fallThrough->dataFlowInfo->liveInV,
    396                           bb->dataFlowInfo->defV);
    397     if (bb->successorBlockList.blockListType != kNotUsed) {
    398         GrowableListIterator iterator;
    399         dvmGrowableListIteratorInit(&bb->successorBlockList.blocks,
    400                                     &iterator);
    401         while (true) {
    402             SuccessorBlockInfo *successorBlockInfo =
    403                 (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator);
    404             if (successorBlockInfo == NULL) break;
    405             BasicBlock *succBB = successorBlockInfo->block;
    406             if (succBB->dataFlowInfo) {
    407                 computeSuccLiveIn(tempDalvikRegisterV,
    408                                   succBB->dataFlowInfo->liveInV,
    409                                   bb->dataFlowInfo->defV);
    410             }
    411         }
    412     }
    413     if (dvmCompareBitVectors(tempDalvikRegisterV, bb->dataFlowInfo->liveInV)) {
    414         dvmCopyBitVector(bb->dataFlowInfo->liveInV, tempDalvikRegisterV);
    415         return true;
    416     }
    417     return false;
    418 }
    419 
    420 /* Insert phi nodes to for each variable to the dominance frontiers */
    421 static void insertPhiNodes(CompilationUnit *cUnit)
    422 {
    423     int dalvikReg;
    424     const GrowableList *blockList = &cUnit->blockList;
    425     BitVector *phiBlocks =
    426         dvmCompilerAllocBitVector(cUnit->numBlocks, false);
    427     BitVector *tmpBlocks =
    428         dvmCompilerAllocBitVector(cUnit->numBlocks, false);
    429     BitVector *inputBlocks =
    430         dvmCompilerAllocBitVector(cUnit->numBlocks, false);
    431 
    432     cUnit->tempDalvikRegisterV =
    433         dvmCompilerAllocBitVector(cUnit->numDalvikRegisters, false);
    434 
    435     dvmCompilerDataFlowAnalysisDispatcher(cUnit, computeBlockLiveIns,
    436                                           kPostOrderDFSTraversal,
    437                                           true /* isIterative */);
    438 
    439     /* Iterate through each Dalvik register */
    440     for (dalvikReg = 0; dalvikReg < cUnit->numDalvikRegisters; dalvikReg++) {
    441         bool change;
    442         BitVectorIterator iterator;
    443 
    444         dvmCopyBitVector(inputBlocks, cUnit->defBlockMatrix[dalvikReg]);
    445         dvmClearAllBits(phiBlocks);
    446 
    447         /* Calculate the phi blocks for each Dalvik register */
    448         do {
    449             change = false;
    450             dvmClearAllBits(tmpBlocks);
    451             dvmBitVectorIteratorInit(inputBlocks, &iterator);
    452 
    453             while (true) {
    454                 int idx = dvmBitVectorIteratorNext(&iterator);
    455                 if (idx == -1) break;
    456                 BasicBlock *defBB =
    457                     (BasicBlock *) dvmGrowableListGetElement(blockList, idx);
    458 
    459                 /* Merge the dominance frontier to tmpBlocks */
    460                 dvmUnifyBitVectors(tmpBlocks, tmpBlocks, defBB->domFrontier);
    461             }
    462             if (dvmCompareBitVectors(phiBlocks, tmpBlocks)) {
    463                 change = true;
    464                 dvmCopyBitVector(phiBlocks, tmpBlocks);
    465 
    466                 /*
    467                  * Iterate through the original blocks plus the new ones in
    468                  * the dominance frontier.
    469                  */
    470                 dvmCopyBitVector(inputBlocks, phiBlocks);
    471                 dvmUnifyBitVectors(inputBlocks, inputBlocks,
    472                                    cUnit->defBlockMatrix[dalvikReg]);
    473             }
    474         } while (change);
    475 
    476         /*
    477          * Insert a phi node for dalvikReg in the phiBlocks if the Dalvik
    478          * register is in the live-in set.
    479          */
    480         dvmBitVectorIteratorInit(phiBlocks, &iterator);
    481         while (true) {
    482             int idx = dvmBitVectorIteratorNext(&iterator);
    483             if (idx == -1) break;
    484             BasicBlock *phiBB =
    485                 (BasicBlock *) dvmGrowableListGetElement(blockList, idx);
    486             /* Variable will be clobbered before being used - no need for phi */
    487             if (!dvmIsBitSet(phiBB->dataFlowInfo->liveInV, dalvikReg)) continue;
    488             MIR *phi = (MIR *) dvmCompilerNew(sizeof(MIR), true);
    489             phi->dalvikInsn.opcode = (Opcode)kMirOpPhi;
    490             phi->dalvikInsn.vA = dalvikReg;
    491             phi->offset = phiBB->startOffset;
    492             dvmCompilerPrependMIR(phiBB, phi);
    493         }
    494     }
    495 }
    496 
    497 /*
    498  * Worker function to insert phi-operands with latest SSA names from
    499  * predecessor blocks
    500  */
    501 static bool insertPhiNodeOperands(CompilationUnit *cUnit, BasicBlock *bb)
    502 {
    503     BitVector *ssaRegV = cUnit->tempSSARegisterV;
    504     BitVectorIterator bvIterator;
    505     GrowableList *blockList = &cUnit->blockList;
    506     MIR *mir;
    507 
    508     /* Phi nodes are at the beginning of each block */
    509     for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
    510         if (mir->dalvikInsn.opcode != (Opcode)kMirOpPhi)
    511             return true;
    512         int ssaReg = mir->ssaRep->defs[0];
    513         int encodedDalvikValue =
    514             (int) dvmGrowableListGetElement(cUnit->ssaToDalvikMap, ssaReg);
    515         int dalvikReg = DECODE_REG(encodedDalvikValue);
    516 
    517         dvmClearAllBits(ssaRegV);
    518 
    519         /* Iterate through the predecessors */
    520         dvmBitVectorIteratorInit(bb->predecessors, &bvIterator);
    521         while (true) {
    522             int predIdx = dvmBitVectorIteratorNext(&bvIterator);
    523             if (predIdx == -1) break;
    524             BasicBlock *predBB = (BasicBlock *) dvmGrowableListGetElement(
    525                                      blockList, predIdx);
    526             int encodedSSAValue =
    527                 predBB->dataFlowInfo->dalvikToSSAMap[dalvikReg];
    528             int ssaReg = DECODE_REG(encodedSSAValue);
    529             dvmSetBit(ssaRegV, ssaReg);
    530         }
    531 
    532         /* Count the number of SSA registers for a Dalvik register */
    533         int numUses = dvmCountSetBits(ssaRegV);
    534         mir->ssaRep->numUses = numUses;
    535         mir->ssaRep->uses =
    536             (int *) dvmCompilerNew(sizeof(int) * numUses, false);
    537         mir->ssaRep->fpUse =
    538             (bool *) dvmCompilerNew(sizeof(bool) * numUses, true);
    539 
    540         BitVectorIterator phiIterator;
    541 
    542         dvmBitVectorIteratorInit(ssaRegV, &phiIterator);
    543         int *usePtr = mir->ssaRep->uses;
    544 
    545         /* Set the uses array for the phi node */
    546         while (true) {
    547             int ssaRegIdx = dvmBitVectorIteratorNext(&phiIterator);
    548             if (ssaRegIdx == -1) break;
    549             *usePtr++ = ssaRegIdx;
    550         }
    551     }
    552 
    553     return true;
    554 }
    555 
    556 /* Perform SSA transformation for the whole method */
    557 void dvmCompilerMethodSSATransformation(CompilationUnit *cUnit)
    558 {
    559     /* Compute the DFS order */
    560     computeDFSOrder(cUnit);
    561 
    562     /* Compute the dominator info */
    563     computeDominators(cUnit);
    564 
    565     /* Allocate data structures in preparation for SSA conversion */
    566     dvmInitializeSSAConversion(cUnit);
    567 
    568     /* Find out the "Dalvik reg def x block" relation */
    569     computeDefBlockMatrix(cUnit);
    570 
    571     /* Insert phi nodes to dominance frontiers for all variables */
    572     insertPhiNodes(cUnit);
    573 
    574     /* Rename register names by local defs and phi nodes */
    575     dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerDoSSAConversion,
    576                                           kPreOrderDFSTraversal,
    577                                           false /* isIterative */);
    578 
    579     /*
    580      * Shared temp bit vector used by each block to count the number of defs
    581      * from all the predecessor blocks.
    582      */
    583     cUnit->tempSSARegisterV = dvmCompilerAllocBitVector(cUnit->numSSARegs,
    584                                                         false);
    585 
    586     /* Insert phi-operands with latest SSA names from predecessor blocks */
    587     dvmCompilerDataFlowAnalysisDispatcher(cUnit, insertPhiNodeOperands,
    588                                           kReachableNodes,
    589                                           false /* isIterative */);
    590 }
    591 
    592 /* Build a loop. Return true if a loop structure is successfully identified. */
    593 bool dvmCompilerBuildLoop(CompilationUnit *cUnit)
    594 {
    595     /* Compute the DFS order */
    596     computeDFSOrder(cUnit);
    597 
    598     /* Compute the dominator info */
    599     computeDominators(cUnit);
    600 
    601     /* Loop structure not recognized/supported - return false */
    602     if (dvmCompilerFilterLoopBlocks(cUnit) == false)
    603         return false;
    604 
    605     /* Re-compute the DFS order just for the loop */
    606     computeDFSOrder(cUnit);
    607 
    608     /* Re-compute the dominator info just for the loop */
    609     computeDominators(cUnit);
    610 
    611     /* Allocate data structures in preparation for SSA conversion */
    612     dvmInitializeSSAConversion(cUnit);
    613 
    614     /* Find out the "Dalvik reg def x block" relation */
    615     computeDefBlockMatrix(cUnit);
    616 
    617     /* Insert phi nodes to dominance frontiers for all variables */
    618     insertPhiNodes(cUnit);
    619 
    620     /* Rename register names by local defs and phi nodes */
    621     dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerDoSSAConversion,
    622                                           kPreOrderDFSTraversal,
    623                                           false /* isIterative */);
    624 
    625     /*
    626      * Shared temp bit vector used by each block to count the number of defs
    627      * from all the predecessor blocks.
    628      */
    629     cUnit->tempSSARegisterV = dvmCompilerAllocBitVector(cUnit->numSSARegs,
    630                                                         false);
    631 
    632     /* Insert phi-operands with latest SSA names from predecessor blocks */
    633     dvmCompilerDataFlowAnalysisDispatcher(cUnit, insertPhiNodeOperands,
    634                                           kReachableNodes,
    635                                           false /* isIterative */);
    636 
    637     if (gDvmJit.receivedSIGUSR2 || gDvmJit.printMe) {
    638         dvmDumpCFG(cUnit, "/sdcard/cfg/");
    639     }
    640 
    641     return true;
    642 }
    643