2 * Copyright (C) 2010 The Android Open Source Project
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
20 #include "libdex/DexOpcodes.h"
22 /* Enter the node to the dfsOrder list then visit its successors */
23 static void recordDFSPreOrder(CompilationUnit *cUnit, BasicBlock *block)
26 if (block->visited || block->hidden) return;
27 block->visited = true;
29 /* Enqueue the block id */
30 dvmInsertGrowableList(&cUnit->dfsOrder, block->id);
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,
39 SuccessorBlockInfo *successorBlockInfo =
40 (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator);
41 if (successorBlockInfo == NULL) break;
42 BasicBlock *succBB = successorBlockInfo->block;
43 recordDFSPreOrder(cUnit, succBB);
49 /* Sort the blocks by the Depth-First-Search pre-order */
50 static void computeDFSOrder(CompilationUnit *cUnit)
52 /* Initialize or reset the DFS order list */
53 if (cUnit->dfsOrder.elemList == NULL) {
54 dvmInitGrowableList(&cUnit->dfsOrder, cUnit->numBlocks);
56 /* Just reset the used length on the counter */
57 cUnit->dfsOrder.numUsed = 0;
60 dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerClearVisitedFlag,
62 false /* isIterative */);
64 recordDFSPreOrder(cUnit, cUnit->entryBlock);
65 cUnit->numReachableBlocks = cUnit->dfsOrder.numUsed;
69 * Mark block bit on the per-Dalvik register vector to denote that Dalvik
70 * register idx is defined in BasicBlock bb.
72 static bool fillDefBlockMatrix(CompilationUnit *cUnit, BasicBlock *bb)
74 if (bb->dataFlowInfo == NULL) return false;
76 BitVectorIterator iterator;
78 dvmBitVectorIteratorInit(bb->dataFlowInfo->defV, &iterator);
80 int idx = dvmBitVectorIteratorNext(&iterator);
82 /* Block bb defines register idx */
83 dvmCompilerSetBit(cUnit->defBlockMatrix[idx], bb->id);
88 static void computeDefBlockMatrix(CompilationUnit *cUnit)
90 int numRegisters = cUnit->numDalvikRegisters;
91 /* Allocate numDalvikRegisters bit vector pointers */
92 cUnit->defBlockMatrix = (BitVector **)
93 dvmCompilerNew(sizeof(BitVector *) * numRegisters, true);
96 /* Initialize numRegister vectors with numBlocks bits each */
97 for (i = 0; i < numRegisters; i++) {
98 cUnit->defBlockMatrix[i] = dvmCompilerAllocBitVector(cUnit->numBlocks,
101 dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerFindLocalLiveIn,
103 false /* isIterative */);
104 dvmCompilerDataFlowAnalysisDispatcher(cUnit, fillDefBlockMatrix,
106 false /* isIterative */);
108 if (cUnit->jitMode == kJitMethod) {
110 * Also set the incoming parameters as defs in the entry block.
111 * Only need to handle the parameters for the outer method.
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);
121 /* Compute the post-order traversal of the CFG */
122 static void computeDomPostOrderTraversal(CompilationUnit *cUnit, BasicBlock *bb)
124 BitVectorIterator bvIterator;
125 dvmBitVectorIteratorInit(bb->iDominated, &bvIterator);
126 GrowableList *blockList = &cUnit->blockList;
128 /* Iterate through the dominated blocks first */
130 int bbIdx = dvmBitVectorIteratorNext(&bvIterator);
131 if (bbIdx == -1) break;
132 BasicBlock *dominatedBB =
133 (BasicBlock *) dvmGrowableListGetElement(blockList, bbIdx);
134 computeDomPostOrderTraversal(cUnit, dominatedBB);
137 /* Enter the current block id */
138 dvmInsertGrowableList(&cUnit->domPostOrderTraversal, bb->id);
140 /* hacky loop detection */
141 if (bb->taken && dvmIsBitSet(bb->dominators, bb->taken->id)) {
142 cUnit->hasLoop = true;
146 static void checkForDominanceFrontier(BasicBlock *domBB,
147 const BasicBlock *succBB)
150 * TODO - evaluate whether phi will ever need to be inserted into exit
153 if (succBB->iDom != domBB &&
154 succBB->blockType == kDalvikByteCode &&
155 succBB->hidden == false) {
156 dvmSetBit(domBB->domFrontier, succBB->id);
160 /* Worker function to compute the dominance frontier */
161 static bool computeDominanceFrontier(CompilationUnit *cUnit, BasicBlock *bb)
163 GrowableList *blockList = &cUnit->blockList;
165 /* Calculate DF_local */
167 checkForDominanceFrontier(bb, bb->taken);
169 if (bb->fallThrough) {
170 checkForDominanceFrontier(bb, bb->fallThrough);
172 if (bb->successorBlockList.blockListType != kNotUsed) {
173 GrowableListIterator iterator;
174 dvmGrowableListIteratorInit(&bb->successorBlockList.blocks,
177 SuccessorBlockInfo *successorBlockInfo =
178 (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator);
179 if (successorBlockInfo == NULL) break;
180 BasicBlock *succBB = successorBlockInfo->block;
181 checkForDominanceFrontier(bb, succBB);
185 /* Calculate DF_up */
186 BitVectorIterator bvIterator;
187 dvmBitVectorIteratorInit(bb->iDominated, &bvIterator);
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);
196 int dfUpIdx = dvmBitVectorIteratorNext(&dfIterator);
197 if (dfUpIdx == -1) break;
198 BasicBlock *dfUpBlock = (BasicBlock *)
199 dvmGrowableListGetElement(blockList, dfUpIdx);
200 checkForDominanceFrontier(bb, dfUpBlock);
207 /* Worker function for initializing domination-related data structures */
208 static bool initializeDominationInfo(CompilationUnit *cUnit, BasicBlock *bb)
210 int numTotalBlocks = cUnit->blockList.numUsed;
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 */);
220 dvmClearAllBits(bb->dominators);
221 dvmClearAllBits(bb->iDominated);
222 dvmClearAllBits(bb->domFrontier);
224 /* Set all bits in the dominator vector */
225 dvmSetInitialBits(bb->dominators, numTotalBlocks);
230 /* Worker function to compute each block's dominators */
231 static bool computeBlockDominators(CompilationUnit *cUnit, BasicBlock *bb)
233 GrowableList *blockList = &cUnit->blockList;
234 int numTotalBlocks = blockList->numUsed;
235 BitVector *tempBlockV = cUnit->tempBlockV;
236 BitVectorIterator bvIterator;
239 * The dominator of the entry block has been preset to itself and we need
240 * to skip the calculation here.
242 if (bb == cUnit->entryBlock) return false;
244 dvmSetInitialBits(tempBlockV, numTotalBlocks);
246 /* Iterate through the predecessors */
247 dvmBitVectorIteratorInit(bb->predecessors, &bvIterator);
249 int predIdx = dvmBitVectorIteratorNext(&bvIterator);
250 if (predIdx == -1) break;
251 BasicBlock *predBB = (BasicBlock *) dvmGrowableListGetElement(
253 /* tempBlockV = tempBlockV ^ dominators */
254 dvmIntersectBitVectors(tempBlockV, tempBlockV, predBB->dominators);
256 dvmSetBit(tempBlockV, bb->id);
257 if (dvmCompareBitVectors(tempBlockV, bb->dominators)) {
258 dvmCopyBitVector(bb->dominators, tempBlockV);
264 /* Worker function to compute the idom */
265 static bool computeImmediateDominator(CompilationUnit *cUnit, BasicBlock *bb)
267 GrowableList *blockList = &cUnit->blockList;
268 BitVector *tempBlockV = cUnit->tempBlockV;
269 BitVectorIterator bvIterator;
272 if (bb == cUnit->entryBlock) return false;
274 dvmCopyBitVector(tempBlockV, bb->dominators);
275 dvmClearBit(tempBlockV, bb->id);
276 dvmBitVectorIteratorInit(tempBlockV, &bvIterator);
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));
285 int iDomIdx = dvmBitVectorIteratorNext(&bvIterator);
286 assert(iDomIdx != -1);
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)) {
298 iDom = (BasicBlock *) dvmGrowableListGetElement(blockList, iDomIdx);
299 /* Set the immediate dominator block for bb */
302 /* Add bb to the iDominated set of the immediate dominator block */
303 dvmCompilerSetBit(iDom->iDominated, bb->id);
307 /* Compute dominators, immediate dominator, and dominance fronter */
308 static void computeDominators(CompilationUnit *cUnit)
310 int numReachableBlocks = cUnit->numReachableBlocks;
311 int numTotalBlocks = cUnit->blockList.numUsed;
313 /* Initialize domination-related data structures */
314 dvmCompilerDataFlowAnalysisDispatcher(cUnit, initializeDominationInfo,
316 false /* isIterative */);
318 /* Set the dominator for the root node */
319 dvmClearAllBits(cUnit->entryBlock->dominators);
320 dvmSetBit(cUnit->entryBlock->dominators, cUnit->entryBlock->id);
322 if (cUnit->tempBlockV == NULL) {
323 cUnit->tempBlockV = dvmCompilerAllocBitVector(numTotalBlocks,
324 false /* expandable */);
326 dvmClearAllBits(cUnit->tempBlockV);
328 dvmCompilerDataFlowAnalysisDispatcher(cUnit, computeBlockDominators,
329 kPreOrderDFSTraversal,
330 true /* isIterative */);
332 cUnit->entryBlock->iDom = NULL;
333 dvmCompilerDataFlowAnalysisDispatcher(cUnit, computeImmediateDominator,
335 false /* isIterative */);
338 * Now go ahead and compute the post order traversal based on the
341 if (cUnit->domPostOrderTraversal.elemList == NULL) {
342 dvmInitGrowableList(&cUnit->domPostOrderTraversal, numReachableBlocks);
344 cUnit->domPostOrderTraversal.numUsed = 0;
347 computeDomPostOrderTraversal(cUnit, cUnit->entryBlock);
348 assert(cUnit->domPostOrderTraversal.numUsed ==
349 (unsigned) cUnit->numReachableBlocks);
351 /* Now compute the dominance frontier for each block */
352 dvmCompilerDataFlowAnalysisDispatcher(cUnit, computeDominanceFrontier,
353 kPostOrderDOMTraversal,
354 false /* isIterative */);
358 * Perform dest U= src1 ^ ~src2
359 * This is probably not general enough to be placed in BitVector.[ch].
361 static void computeSuccLiveIn(BitVector *dest,
362 const BitVector *src1,
363 const BitVector *src2)
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");
374 for (idx = 0; idx < dest->storageSize; idx++) {
375 dest->storage[idx] |= src1->storage[idx] & ~src2->storage[idx];
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.
384 static bool computeBlockLiveIns(CompilationUnit *cUnit, BasicBlock *bb)
386 BitVector *tempDalvikRegisterV = cUnit->tempDalvikRegisterV;
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,
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);
413 if (dvmCompareBitVectors(tempDalvikRegisterV, bb->dataFlowInfo->liveInV)) {
414 dvmCopyBitVector(bb->dataFlowInfo->liveInV, tempDalvikRegisterV);
420 /* Insert phi nodes to for each variable to the dominance frontiers */
421 static void insertPhiNodes(CompilationUnit *cUnit)
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);
432 cUnit->tempDalvikRegisterV =
433 dvmCompilerAllocBitVector(cUnit->numDalvikRegisters, false);
435 dvmCompilerDataFlowAnalysisDispatcher(cUnit, computeBlockLiveIns,
436 kPostOrderDFSTraversal,
437 true /* isIterative */);
439 /* Iterate through each Dalvik register */
440 for (dalvikReg = 0; dalvikReg < cUnit->numDalvikRegisters; dalvikReg++) {
442 BitVectorIterator iterator;
444 dvmCopyBitVector(inputBlocks, cUnit->defBlockMatrix[dalvikReg]);
445 dvmClearAllBits(phiBlocks);
447 /* Calculate the phi blocks for each Dalvik register */
450 dvmClearAllBits(tmpBlocks);
451 dvmBitVectorIteratorInit(inputBlocks, &iterator);
454 int idx = dvmBitVectorIteratorNext(&iterator);
455 if (idx == -1) break;
457 (BasicBlock *) dvmGrowableListGetElement(blockList, idx);
459 /* Merge the dominance frontier to tmpBlocks */
460 dvmUnifyBitVectors(tmpBlocks, tmpBlocks, defBB->domFrontier);
462 if (dvmCompareBitVectors(phiBlocks, tmpBlocks)) {
464 dvmCopyBitVector(phiBlocks, tmpBlocks);
467 * Iterate through the original blocks plus the new ones in
468 * the dominance frontier.
470 dvmCopyBitVector(inputBlocks, phiBlocks);
471 dvmUnifyBitVectors(inputBlocks, inputBlocks,
472 cUnit->defBlockMatrix[dalvikReg]);
477 * Insert a phi node for dalvikReg in the phiBlocks if the Dalvik
478 * register is in the live-in set.
480 dvmBitVectorIteratorInit(phiBlocks, &iterator);
482 int idx = dvmBitVectorIteratorNext(&iterator);
483 if (idx == -1) break;
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);
498 * Worker function to insert phi-operands with latest SSA names from
501 static bool insertPhiNodeOperands(CompilationUnit *cUnit, BasicBlock *bb)
503 BitVector *ssaRegV = cUnit->tempSSARegisterV;
504 BitVectorIterator bvIterator;
505 GrowableList *blockList = &cUnit->blockList;
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)
512 int ssaReg = mir->ssaRep->defs[0];
513 int encodedDalvikValue =
514 (int) dvmGrowableListGetElement(cUnit->ssaToDalvikMap, ssaReg);
515 int dalvikReg = DECODE_REG(encodedDalvikValue);
517 dvmClearAllBits(ssaRegV);
519 /* Iterate through the predecessors */
520 dvmBitVectorIteratorInit(bb->predecessors, &bvIterator);
522 int predIdx = dvmBitVectorIteratorNext(&bvIterator);
523 if (predIdx == -1) break;
524 BasicBlock *predBB = (BasicBlock *) dvmGrowableListGetElement(
526 int encodedSSAValue =
527 predBB->dataFlowInfo->dalvikToSSAMap[dalvikReg];
528 int ssaReg = DECODE_REG(encodedSSAValue);
529 dvmSetBit(ssaRegV, ssaReg);
532 /* Count the number of SSA registers for a Dalvik register */
533 int numUses = dvmCountSetBits(ssaRegV);
534 mir->ssaRep->numUses = numUses;
536 (int *) dvmCompilerNew(sizeof(int) * numUses, false);
538 (bool *) dvmCompilerNew(sizeof(bool) * numUses, true);
540 BitVectorIterator phiIterator;
542 dvmBitVectorIteratorInit(ssaRegV, &phiIterator);
543 int *usePtr = mir->ssaRep->uses;
545 /* Set the uses array for the phi node */
547 int ssaRegIdx = dvmBitVectorIteratorNext(&phiIterator);
548 if (ssaRegIdx == -1) break;
549 *usePtr++ = ssaRegIdx;
556 /* Perform SSA transformation for the whole method */
557 void dvmCompilerMethodSSATransformation(CompilationUnit *cUnit)
559 /* Compute the DFS order */
560 computeDFSOrder(cUnit);
562 /* Compute the dominator info */
563 computeDominators(cUnit);
565 /* Allocate data structures in preparation for SSA conversion */
566 dvmInitializeSSAConversion(cUnit);
568 /* Find out the "Dalvik reg def x block" relation */
569 computeDefBlockMatrix(cUnit);
571 /* Insert phi nodes to dominance frontiers for all variables */
572 insertPhiNodes(cUnit);
574 /* Rename register names by local defs and phi nodes */
575 dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerDoSSAConversion,
576 kPreOrderDFSTraversal,
577 false /* isIterative */);
580 * Shared temp bit vector used by each block to count the number of defs
581 * from all the predecessor blocks.
583 cUnit->tempSSARegisterV = dvmCompilerAllocBitVector(cUnit->numSSARegs,
586 /* Insert phi-operands with latest SSA names from predecessor blocks */
587 dvmCompilerDataFlowAnalysisDispatcher(cUnit, insertPhiNodeOperands,
589 false /* isIterative */);
592 /* Build a loop. Return true if a loop structure is successfully identified. */
593 bool dvmCompilerBuildLoop(CompilationUnit *cUnit)
595 /* Compute the DFS order */
596 computeDFSOrder(cUnit);
598 /* Compute the dominator info */
599 computeDominators(cUnit);
601 /* Loop structure not recognized/supported - return false */
602 if (dvmCompilerFilterLoopBlocks(cUnit) == false)
605 /* Re-compute the DFS order just for the loop */
606 computeDFSOrder(cUnit);
608 /* Re-compute the dominator info just for the loop */
609 computeDominators(cUnit);
611 /* Allocate data structures in preparation for SSA conversion */
612 dvmInitializeSSAConversion(cUnit);
614 /* Find out the "Dalvik reg def x block" relation */
615 computeDefBlockMatrix(cUnit);
617 /* Insert phi nodes to dominance frontiers for all variables */
618 insertPhiNodes(cUnit);
620 /* Rename register names by local defs and phi nodes */
621 dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerDoSSAConversion,
622 kPreOrderDFSTraversal,
623 false /* isIterative */);
626 * Shared temp bit vector used by each block to count the number of defs
627 * from all the predecessor blocks.
629 cUnit->tempSSARegisterV = dvmCompilerAllocBitVector(cUnit->numSSARegs,
632 /* Insert phi-operands with latest SSA names from predecessor blocks */
633 dvmCompilerDataFlowAnalysisDispatcher(cUnit, insertPhiNodeOperands,
635 false /* isIterative */);
637 if (gDvmJit.receivedSIGUSR2 || gDvmJit.printMe) {
638 dvmDumpCFG(cUnit, "/sdcard/cfg/");