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 */
23static 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 */
50static 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 */
72static 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
88static 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 */
122static 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
146static 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 */
161static 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 */
208static 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 */
231static 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 */
265static 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 */
308static 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 */
361static 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 */
384static 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 */
421static 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 */
501static 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 */
557void 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. */
593bool 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