Implement method parser and SSA transformation.
Change-Id: If3fb3a36f33aaee8e5fdded4e9fa607be54f0bfb
diff --git a/vm/compiler/MethodSSATransformation.c b/vm/compiler/MethodSSATransformation.c
new file mode 100644
index 0000000..fc56891
--- /dev/null
+++ b/vm/compiler/MethodSSATransformation.c
@@ -0,0 +1,559 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "Dalvik.h"
+#include "Dataflow.h"
+#include "Loop.h"
+#include "libdex/DexOpcodes.h"
+
+/* Enter the node to the dfsOrder list then visit its successors */
+static void recordDFSPreOrder(CompilationUnit *cUnit, BasicBlock *block)
+{
+
+ if (block->visited) return;
+ block->visited = true;
+
+ /* Enqueue the block id */
+ dvmInsertGrowableList(&cUnit->dfsOrder, block->id);
+
+ if (block->taken) recordDFSPreOrder(cUnit, block->taken);
+ if (block->fallThrough) recordDFSPreOrder(cUnit, block->fallThrough);
+ if (block->successorBlockList.blockListType != kNotUsed) {
+ GrowableListIterator iterator;
+ dvmGrowableListIteratorInit(&block->successorBlockList.blocks,
+ &iterator);
+ while (true) {
+ BasicBlock *succBB =
+ (BasicBlock *) dvmGrowableListIteratorNext(&iterator);
+ if (succBB == NULL) break;
+ recordDFSPreOrder(cUnit, succBB);
+ }
+ }
+ return;
+}
+
+/* Sort the blocks by the Depth-First-Search pre-order */
+static void computeDFSOrder(CompilationUnit *cUnit)
+{
+ /* Initialize the DFS order list */
+ dvmInitGrowableList(&cUnit->dfsOrder, cUnit->numBlocks);
+
+
+ dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerClearVisitedFlag,
+ kAllNodes,
+ false /* isIterative */);
+
+ recordDFSPreOrder(cUnit, cUnit->entryBlock);
+ cUnit->numReachableBlocks = cUnit->dfsOrder.numUsed;
+}
+
+/*
+ * Mark block bit on the per-Dalvik register vector to denote that Dalvik
+ * register idx is defined in BasicBlock bb.
+ */
+static bool fillDefBlockMatrix(CompilationUnit *cUnit, BasicBlock *bb)
+{
+ if (bb->dataFlowInfo == NULL) return false;
+
+ BitVectorIterator iterator;
+
+ dvmBitVectorIteratorInit(bb->dataFlowInfo->defV, &iterator);
+ while (true) {
+ int idx = dvmBitVectorIteratorNext(&iterator);
+ if (idx == -1) break;
+ /* Block bb defines register idx */
+ dvmCompilerSetBit(cUnit->defBlockMatrix[idx], bb->id);
+ }
+ return true;
+}
+
+static void computeDefBlockMatrix(CompilationUnit *cUnit)
+{
+ int numRegisters = cUnit->numDalvikRegisters;
+ /* Allocate numDalvikRegisters bit vector pointers */
+ cUnit->defBlockMatrix = (BitVector **)
+ dvmCompilerNew(sizeof(BitVector *) * numRegisters, true);
+ int i;
+
+ /* Initialize numRegister vectors with numBlocks bits each */
+ for (i = 0; i < numRegisters; i++) {
+ cUnit->defBlockMatrix[i] = dvmCompilerAllocBitVector(cUnit->numBlocks,
+ false);
+ }
+ dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerFindLocalLiveIn,
+ kAllNodes,
+ false /* isIterative */);
+ dvmCompilerDataFlowAnalysisDispatcher(cUnit, fillDefBlockMatrix,
+ kAllNodes,
+ false /* isIterative */);
+
+ /*
+ * Also set the incoming parameters as defs in the entry block.
+ * Only need to handle the parameters for the outer method.
+ */
+ int inReg = cUnit->method->registersSize - cUnit->method->insSize;
+ for (; inReg < cUnit->method->registersSize; inReg++) {
+ dvmCompilerSetBit(cUnit->defBlockMatrix[inReg],
+ cUnit->entryBlock->id);
+ }
+}
+
+/* Compute the post-order traversal of the CFG */
+static void computeDomPostOrderTraversal(CompilationUnit *cUnit, BasicBlock *bb)
+{
+ BitVectorIterator bvIterator;
+ dvmBitVectorIteratorInit(bb->iDominated, &bvIterator);
+ GrowableList *blockList = &cUnit->blockList;
+
+ /* Iterate through the dominated blocks first */
+ while (true) {
+ int bbIdx = dvmBitVectorIteratorNext(&bvIterator);
+ if (bbIdx == -1) break;
+ BasicBlock *dominatedBB =
+ (BasicBlock *) dvmGrowableListGetElement(blockList, bbIdx);
+ computeDomPostOrderTraversal(cUnit, dominatedBB);
+ }
+
+ /* Enter the current block id */
+ dvmInsertGrowableList(&cUnit->domPostOrderTraversal, bb->id);
+
+ /* hacky loop detection */
+ if (bb->taken && dvmIsBitSet(bb->dominators, bb->taken->id)) {
+ cUnit->hasLoop = true;
+ }
+}
+
+/* Worker function to compute the dominance frontier */
+static bool computeDominanceFrontier(CompilationUnit *cUnit, BasicBlock *bb)
+{
+ GrowableList *blockList = &cUnit->blockList;
+
+ /* Calculate DF_local */
+ if (bb->taken && !dvmIsBitSet(bb->taken->dominators, bb->id)) {
+ dvmSetBit(bb->domFrontier, bb->taken->id);
+ }
+ if (bb->fallThrough &&
+ !dvmIsBitSet(bb->fallThrough->dominators, bb->id)) {
+ dvmSetBit(bb->domFrontier, bb->fallThrough->id);
+ }
+ if (bb->successorBlockList.blockListType != kNotUsed) {
+ GrowableListIterator iterator;
+ dvmGrowableListIteratorInit(&bb->successorBlockList.blocks,
+ &iterator);
+ while (true) {
+ BasicBlock *succBB =
+ (BasicBlock *) dvmGrowableListIteratorNext(&iterator);
+ if (succBB == NULL) break;
+ if (!dvmIsBitSet(succBB->dominators, bb->id)) {
+ dvmSetBit(bb->domFrontier, succBB->id);
+ }
+ }
+ }
+
+ /* Calculate DF_up */
+ BitVectorIterator bvIterator;
+ dvmBitVectorIteratorInit(bb->iDominated, &bvIterator);
+ while (true) {
+ int dominatedIdx = dvmBitVectorIteratorNext(&bvIterator);
+ if (dominatedIdx == -1) break;
+ BasicBlock *dominatedBB = (BasicBlock *)
+ dvmGrowableListGetElement(blockList, dominatedIdx);
+ BitVectorIterator dfIterator;
+ dvmBitVectorIteratorInit(dominatedBB->domFrontier, &dfIterator);
+ while (true) {
+ int dfUpIdx = dvmBitVectorIteratorNext(&dfIterator);
+ if (dfUpIdx == -1) break;
+ BasicBlock *dfUpBlock = (BasicBlock *)
+ dvmGrowableListGetElement(blockList, dfUpIdx);
+ if (!dvmIsBitSet(dfUpBlock->dominators, bb->id)) {
+ dvmSetBit(bb->domFrontier, dfUpBlock->id);
+ }
+ }
+ }
+ if (cUnit->printMe) {
+ char blockName[BLOCK_NAME_LEN];
+ dvmGetBlockName(bb, blockName);
+ dvmDumpBlockBitVector(blockList, blockName, bb->domFrontier,
+ cUnit->numBlocks);
+ }
+
+ return true;
+}
+
+/* Worker function for initializing domination-related data structures */
+static bool initializeDominationInfo(CompilationUnit *cUnit, BasicBlock *bb)
+{
+ int numTotalBlocks = cUnit->blockList.numUsed;
+
+ bb->dominators = dvmCompilerAllocBitVector(numTotalBlocks,
+ false /* expandable */);
+ bb->iDominated = dvmCompilerAllocBitVector(numTotalBlocks,
+ false /* expandable */);
+ bb->domFrontier = dvmCompilerAllocBitVector(numTotalBlocks,
+ false /* expandable */);
+ /* Set all bits in the dominator vector */
+ dvmSetInitialBits(bb->dominators, numTotalBlocks);
+
+ return true;
+}
+
+/* Worker function to compute each block's dominators */
+static bool computeBlockDominators(CompilationUnit *cUnit, BasicBlock *bb)
+{
+ GrowableList *blockList = &cUnit->blockList;
+ int numTotalBlocks = blockList->numUsed;
+ BitVector *tempBlockV = cUnit->tempBlockV;
+ BitVectorIterator bvIterator;
+
+ /*
+ * The dominator of the entry block has been preset to itself and we need
+ * to skip the calculation here.
+ */
+ if (bb == cUnit->entryBlock) return false;
+
+ dvmSetInitialBits(tempBlockV, numTotalBlocks);
+
+ /* Iterate through the predecessors */
+ dvmBitVectorIteratorInit(bb->predecessors, &bvIterator);
+ while (true) {
+ int predIdx = dvmBitVectorIteratorNext(&bvIterator);
+ if (predIdx == -1) break;
+ BasicBlock *predBB = (BasicBlock *) dvmGrowableListGetElement(
+ blockList, predIdx);
+ /* tempBlockV = tempBlockV ^ dominators */
+ dvmIntersectBitVectors(tempBlockV, tempBlockV, predBB->dominators);
+ }
+ dvmSetBit(tempBlockV, bb->id);
+ if (dvmCompareBitVectors(tempBlockV, bb->dominators)) {
+ dvmCopyBitVector(bb->dominators, tempBlockV);
+ return true;
+ }
+ return false;
+}
+
+/* Worker function to compute the idom */
+static bool computeImmediateDominator(CompilationUnit *cUnit, BasicBlock *bb)
+{
+ GrowableList *blockList = &cUnit->blockList;
+ BitVector *tempBlockV = cUnit->tempBlockV;
+ BitVectorIterator bvIterator;
+ BasicBlock *iDom;
+
+ if (bb == cUnit->entryBlock) return false;
+
+ dvmCopyBitVector(tempBlockV, bb->dominators);
+ dvmClearBit(tempBlockV, bb->id);
+ dvmBitVectorIteratorInit(tempBlockV, &bvIterator);
+
+ /* Should not see any dead block */
+ assert(dvmCountSetBits(tempBlockV) != 0);
+ if (dvmCountSetBits(tempBlockV) == 1) {
+ iDom = (BasicBlock *) dvmGrowableListGetElement(
+ blockList, dvmBitVectorIteratorNext(&bvIterator));
+ bb->iDom = iDom;
+ } else {
+ int iDomIdx = dvmBitVectorIteratorNext(&bvIterator);
+ assert(iDomIdx != -1);
+ while (true) {
+ int nextDom = dvmBitVectorIteratorNext(&bvIterator);
+ if (nextDom == -1) break;
+ BasicBlock *nextDomBB = (BasicBlock *)
+ dvmGrowableListGetElement(blockList, nextDom);
+ /* iDom dominates nextDom - set new iDom */
+ if (dvmIsBitSet(nextDomBB->dominators, iDomIdx)) {
+ iDomIdx = nextDom;
+ }
+
+ }
+ iDom = (BasicBlock *) dvmGrowableListGetElement(blockList, iDomIdx);
+ /* Set the immediate dominator block for bb */
+ bb->iDom = iDom;
+ }
+ /* Add bb to the iDominated set of the immediate dominator block */
+ dvmCompilerSetBit(iDom->iDominated, bb->id);
+ return true;
+}
+
+/* Compute dominators, immediate dominator, and dominance fronter */
+static void computeDominators(CompilationUnit *cUnit)
+{
+ int numReachableBlocks = cUnit->numReachableBlocks;
+ int numTotalBlocks = cUnit->blockList.numUsed;
+
+ /* Initialize domination-related data structures */
+ dvmCompilerDataFlowAnalysisDispatcher(cUnit, initializeDominationInfo,
+ kReachableNodes,
+ false /* isIterative */);
+
+ /* Set the dominator for the root node */
+ dvmClearAllBits(cUnit->entryBlock->dominators);
+ dvmSetBit(cUnit->entryBlock->dominators, cUnit->entryBlock->id);
+
+ cUnit->tempBlockV = dvmCompilerAllocBitVector(numTotalBlocks,
+ false /* expandable */);
+ dvmCompilerDataFlowAnalysisDispatcher(cUnit, computeBlockDominators,
+ kPreOrderDFSTraversal,
+ true /* isIterative */);
+
+ cUnit->entryBlock->iDom = NULL;
+ dvmCompilerDataFlowAnalysisDispatcher(cUnit, computeImmediateDominator,
+ kReachableNodes,
+ false /* isIterative */);
+
+ /*
+ * Now go ahead and compute the post order traversal based on the
+ * iDominated sets.
+ */
+ dvmInitGrowableList(&cUnit->domPostOrderTraversal, numReachableBlocks);
+ computeDomPostOrderTraversal(cUnit, cUnit->entryBlock);
+ assert(cUnit->domPostOrderTraversal.numUsed ==
+ (unsigned) cUnit->numReachableBlocks);
+
+ /* Now compute the dominance frontier for each block */
+ dvmCompilerDataFlowAnalysisDispatcher(cUnit, computeDominanceFrontier,
+ kPostOrderDOMTraversal,
+ false /* isIterative */);
+}
+
+/*
+ * Perform dest U= src1 ^ ~src2
+ * This is probably not general enough to be placed in BitVector.[ch].
+ */
+static void computeSuccLiveIn(BitVector *dest,
+ const BitVector *src1,
+ const BitVector *src2)
+{
+ if (dest->storageSize != src1->storageSize ||
+ dest->storageSize != src2->storageSize ||
+ dest->expandable != src1->expandable ||
+ dest->expandable != src2->expandable) {
+ LOGE("Incompatible set properties");
+ dvmAbort();
+ }
+
+ int i;
+ for (i = 0; i < dest->storageSize; i++) {
+ dest->storage[i] |= src1->storage[i] & ~src2->storage[i];
+ }
+}
+
+/*
+ * Iterate through all successor blocks and propagate up the live-in sets.
+ * The calculated result is used for phi-node pruning - where we only need to
+ * insert a phi node if the variable is live-in to the block.
+ */
+static bool computeBlockLiveIns(CompilationUnit *cUnit, BasicBlock *bb)
+{
+ BitVector *tempDalvikRegisterV = cUnit->tempDalvikRegisterV;
+
+ if (bb->dataFlowInfo == NULL) return false;
+ dvmCopyBitVector(tempDalvikRegisterV, bb->dataFlowInfo->liveInV);
+ if (bb->taken && bb->taken->dataFlowInfo)
+ computeSuccLiveIn(tempDalvikRegisterV, bb->taken->dataFlowInfo->liveInV,
+ bb->dataFlowInfo->defV);
+ if (bb->fallThrough && bb->fallThrough->dataFlowInfo)
+ computeSuccLiveIn(tempDalvikRegisterV,
+ bb->fallThrough->dataFlowInfo->liveInV,
+ bb->dataFlowInfo->defV);
+ if (bb->successorBlockList.blockListType != kNotUsed) {
+ GrowableListIterator iterator;
+ dvmGrowableListIteratorInit(&bb->successorBlockList.blocks,
+ &iterator);
+ while (true) {
+ BasicBlock *succBB =
+ (BasicBlock *) dvmGrowableListIteratorNext(&iterator);
+ if (succBB == NULL) break;
+ if (succBB->dataFlowInfo) {
+ computeSuccLiveIn(tempDalvikRegisterV,
+ succBB->dataFlowInfo->liveInV,
+ bb->dataFlowInfo->defV);
+ }
+ }
+ }
+ if (dvmCompareBitVectors(tempDalvikRegisterV, bb->dataFlowInfo->liveInV)) {
+ dvmCopyBitVector(bb->dataFlowInfo->liveInV, tempDalvikRegisterV);
+ return true;
+ }
+ return false;
+}
+
+/* Insert phi nodes to for each variable to the dominance frontiers */
+static void insertPhiNodes(CompilationUnit *cUnit)
+{
+ int dalvikReg;
+ const GrowableList *blockList = &cUnit->blockList;
+ BitVector *phiBlocks =
+ dvmCompilerAllocBitVector(cUnit->numDalvikRegisters, false);
+ BitVector *tmpBlocks =
+ dvmCompilerAllocBitVector(cUnit->numDalvikRegisters, false);
+ BitVector *inputBlocks =
+ dvmCompilerAllocBitVector(cUnit->numDalvikRegisters, false);
+
+ cUnit->tempDalvikRegisterV =
+ dvmCompilerAllocBitVector(cUnit->numDalvikRegisters, false);
+
+ dvmCompilerDataFlowAnalysisDispatcher(cUnit, computeBlockLiveIns,
+ kPostOrderDFSTraversal,
+ true /* isIterative */);
+
+ /* Iterate through each Dalvik register */
+ for (dalvikReg = 0; dalvikReg < cUnit->numDalvikRegisters; dalvikReg++) {
+ bool change;
+ BitVectorIterator iterator;
+
+ dvmCopyBitVector(inputBlocks, cUnit->defBlockMatrix[dalvikReg]);
+ dvmClearAllBits(phiBlocks);
+ /* Calculate the phi blocks for each Dalvik register */
+ do {
+ change = false;
+ dvmClearAllBits(tmpBlocks);
+ dvmBitVectorIteratorInit(inputBlocks, &iterator);
+ while (true) {
+ int idx = dvmBitVectorIteratorNext(&iterator);
+ if (idx == -1) break;
+ BasicBlock *defBB =
+ (BasicBlock *) dvmGrowableListGetElement(blockList, idx);
+ /* Merge the dominance frontier to tmpBlocks */
+ dvmUnifyBitVectors(tmpBlocks, tmpBlocks, defBB->domFrontier);
+ }
+ if (dvmCompareBitVectors(phiBlocks, tmpBlocks)) {
+ change = true;
+ dvmCopyBitVector(phiBlocks, tmpBlocks);
+
+ /*
+ * Iterate through the original blocks plus the new ones in
+ * the dominance frontier.
+ */
+ dvmCopyBitVector(inputBlocks, phiBlocks);
+ dvmUnifyBitVectors(inputBlocks, inputBlocks,
+ cUnit->defBlockMatrix[dalvikReg]);
+ }
+ } while (change);
+
+ /*
+ * Insert a phi node for dalvikReg in the phiBlocks if the Dalvik
+ * register is in the live-in set.
+ */
+ dvmBitVectorIteratorInit(phiBlocks, &iterator);
+ while (true) {
+ int idx = dvmBitVectorIteratorNext(&iterator);
+ if (idx == -1) break;
+ BasicBlock *phiBB =
+ (BasicBlock *) dvmGrowableListGetElement(blockList, idx);
+ /* Variable will be clobbered before being used - no need for phi */
+ if (!dvmIsBitSet(phiBB->dataFlowInfo->liveInV, dalvikReg)) continue;
+ MIR *phi = (MIR *) dvmCompilerNew(sizeof(MIR), true);
+ phi->dalvikInsn.opcode = kMirOpPhi;
+ phi->dalvikInsn.vA = dalvikReg;
+ phi->offset = phiBB->startOffset;
+ dvmCompilerPrependMIR(phiBB, phi);
+ }
+ }
+}
+
+/*
+ * Worker function to insert phi-operands with latest SSA names from
+ * predecessor blocks
+ */
+static bool insertPhiNodeOperands(CompilationUnit *cUnit, BasicBlock *bb)
+{
+ BitVector *ssaRegV = cUnit->tempSSARegisterV;
+ BitVectorIterator bvIterator;
+ GrowableList *blockList = &cUnit->blockList;
+ MIR *mir;
+
+ /* Phi nodes are at the beginning of each block */
+ for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
+ if (mir->dalvikInsn.opcode != kMirOpPhi) return true;
+ int ssaReg = mir->ssaRep->defs[0];
+ int encodedDalvikValue =
+ (int) dvmGrowableListGetElement(cUnit->ssaToDalvikMap, ssaReg);
+ int dalvikReg = DECODE_REG(encodedDalvikValue);
+
+ dvmClearAllBits(ssaRegV);
+
+ /* Iterate through the predecessors */
+ dvmBitVectorIteratorInit(bb->predecessors, &bvIterator);
+ while (true) {
+ int predIdx = dvmBitVectorIteratorNext(&bvIterator);
+ if (predIdx == -1) break;
+ BasicBlock *predBB = (BasicBlock *) dvmGrowableListGetElement(
+ blockList, predIdx);
+ int encodedSSAValue =
+ predBB->dataFlowInfo->dalvikToSSAMap[dalvikReg];
+ int ssaReg = DECODE_REG(encodedSSAValue);
+ dvmSetBit(ssaRegV, ssaReg);
+ }
+
+ /* Count the number of SSA registers for a Dalvik register */
+ int numUses = dvmCountSetBits(ssaRegV);
+ mir->ssaRep->numUses = numUses;
+ mir->ssaRep->uses =
+ (int *) dvmCompilerNew(sizeof(int) * numUses, false);
+ mir->ssaRep->fpUse =
+ (bool *) dvmCompilerNew(sizeof(bool) * numUses, false);
+
+ BitVectorIterator phiIterator;
+
+ dvmBitVectorIteratorInit(ssaRegV, &phiIterator);
+ int *usePtr = mir->ssaRep->uses;
+
+ /* Set the uses array for the phi node */
+ while (true) {
+ int ssaRegIdx = dvmBitVectorIteratorNext(&phiIterator);
+ if (ssaRegIdx == -1) break;
+ *usePtr++ = ssaRegIdx;
+ }
+ }
+
+ return true;
+}
+
+/* Perform SSA transformation for the whole method */
+void dvmCompilerMethodSSATransformation(CompilationUnit *cUnit)
+{
+ /* Compute the DFS order */
+ computeDFSOrder(cUnit);
+
+ /* Compute the dominator info */
+ computeDominators(cUnit);
+
+ /* Allocate data structures in preparation for SSA conversion */
+ dvmInitializeSSAConversion(cUnit);
+
+ /* Find out the "Dalvik reg def x block" relation */
+ computeDefBlockMatrix(cUnit);
+
+ /* Insert phi nodes to dominance frontiers for all variables */
+ insertPhiNodes(cUnit);
+
+ /* Rename register names by local defs and phi nodes */
+ dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerDoSSAConversion,
+ kPreOrderDFSTraversal,
+ false /* isIterative */);
+
+ /*
+ * Shared temp bit vector used by each block to count the number of defs
+ * from all the predecessor blocks.
+ */
+ cUnit->tempSSARegisterV = dvmCompilerAllocBitVector(cUnit->numSSARegs,
+ false);
+
+ /* Insert phi-operands with latest SSA names from predecessor blocks */
+ dvmCompilerDataFlowAnalysisDispatcher(cUnit, insertPhiNodeOperands,
+ kReachableNodes,
+ false /* isIterative */);
+}