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 */
recordDFSPreOrder(CompilationUnit * cUnit,BasicBlock * block)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 */
computeDFSOrder(CompilationUnit * cUnit)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 */
fillDefBlockMatrix(CompilationUnit * cUnit,BasicBlock * bb)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
computeDefBlockMatrix(CompilationUnit * cUnit)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 */
computeDomPostOrderTraversal(CompilationUnit * cUnit,BasicBlock * bb)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
checkForDominanceFrontier(BasicBlock * domBB,const BasicBlock * succBB)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 */
computeDominanceFrontier(CompilationUnit * cUnit,BasicBlock * bb)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 */
initializeDominationInfo(CompilationUnit * cUnit,BasicBlock * bb)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 */
computeBlockDominators(CompilationUnit * cUnit,BasicBlock * bb)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 */
computeImmediateDominator(CompilationUnit * cUnit,BasicBlock * bb)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 */
computeDominators(CompilationUnit * cUnit)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 */
computeSuccLiveIn(BitVector * dest,const BitVector * src1,const BitVector * src2)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 */
computeBlockLiveIns(CompilationUnit * cUnit,BasicBlock * bb)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 */
insertPhiNodes(CompilationUnit * cUnit)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 */
insertPhiNodeOperands(CompilationUnit * cUnit,BasicBlock * bb)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 */
dvmCompilerMethodSSATransformation(CompilationUnit * cUnit)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. */
dvmCompilerBuildLoop(CompilationUnit * cUnit)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