vm/compiler/SSATransformation.cpp

   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 }