Oat compiler integration snapshot.
Cleanly compiles, but not integrated. Old-world dependencies captured
in hacked-up temporary files "Dalvik.h" and "HackStubs.cc".
Dalvik.h is a placeholder that captures all of the constants, struct
definitions and inline functions the compiler needs. It largely consists
of declaration fragments of libdex, Object.h, DvmDex.h and Thread.h.
HackStubs.cc contains empty shells for some required libdex routines.
Change-Id: Ia479dda41da4e3162ff6df383252fdc7dbf38d71
diff --git a/src/compiler/SSATransformation.cc b/src/compiler/SSATransformation.cc
new file mode 100644
index 0000000..a843d51
--- /dev/null
+++ b/src/compiler/SSATransformation.cc
@@ -0,0 +1,585 @@
+/*
+ * Copyright (C) 2011 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"
+
+/* Enter the node to the dfsOrder list then visit its successors */
+static void recordDFSPreOrder(CompilationUnit* cUnit, BasicBlock* block)
+{
+
+ if (block->visited || block->hidden) return;
+ block->visited = true;
+
+ /* Enqueue the block id */
+ oatInsertGrowableList(&cUnit->dfsOrder, block->id);
+
+ if (block->fallThrough) recordDFSPreOrder(cUnit, block->fallThrough);
+ if (block->taken) recordDFSPreOrder(cUnit, block->taken);
+ if (block->successorBlockList.blockListType != kNotUsed) {
+ GrowableListIterator iterator;
+ oatGrowableListIteratorInit(&block->successorBlockList.blocks,
+ &iterator);
+ while (true) {
+ SuccessorBlockInfo *successorBlockInfo =
+ (SuccessorBlockInfo *) oatGrowableListIteratorNext(&iterator);
+ if (successorBlockInfo == NULL) break;
+ BasicBlock* succBB = successorBlockInfo->block;
+ recordDFSPreOrder(cUnit, succBB);
+ }
+ }
+ return;
+}
+
+/* Sort the blocks by the Depth-First-Search pre-order */
+static void computeDFSOrder(CompilationUnit* cUnit)
+{
+ /* Initialize or reset the DFS order list */
+ if (cUnit->dfsOrder.elemList == NULL) {
+ oatInitGrowableList(&cUnit->dfsOrder, cUnit->numBlocks);
+ } else {
+ /* Just reset the used length on the counter */
+ cUnit->dfsOrder.numUsed = 0;
+ }
+
+ oatDataFlowAnalysisDispatcher(cUnit, oatClearVisitedFlag,
+ 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;
+
+ ArenaBitVectorIterator iterator;
+
+ oatBitVectorIteratorInit(bb->dataFlowInfo->defV, &iterator);
+ while (true) {
+ int idx = oatBitVectorIteratorNext(&iterator);
+ if (idx == -1) break;
+ /* Block bb defines register idx */
+ oatSetBit(cUnit->defBlockMatrix[idx], bb->id);
+ }
+ return true;
+}
+
+static void computeDefBlockMatrix(CompilationUnit* cUnit)
+{
+ int numRegisters = cUnit->numDalvikRegisters;
+ /* Allocate numDalvikRegisters bit vector pointers */
+ cUnit->defBlockMatrix = (ArenaBitVector **)
+ oatNew(sizeof(ArenaBitVector *) * numRegisters, true);
+ int i;
+
+ /* Initialize numRegister vectors with numBlocks bits each */
+ for (i = 0; i < numRegisters; i++) {
+ cUnit->defBlockMatrix[i] = oatAllocBitVector(cUnit->numBlocks,
+ false);
+ }
+ oatDataFlowAnalysisDispatcher(cUnit, oatFindLocalLiveIn,
+ kAllNodes,
+ false /* isIterative */);
+ oatDataFlowAnalysisDispatcher(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++) {
+ oatSetBit(cUnit->defBlockMatrix[inReg],
+ cUnit->entryBlock->id);
+ }
+}
+
+/* Compute the post-order traversal of the CFG */
+static void computeDomPostOrderTraversal(CompilationUnit* cUnit, BasicBlock* bb)
+{
+ ArenaBitVectorIterator bvIterator;
+ oatBitVectorIteratorInit(bb->iDominated, &bvIterator);
+ GrowableList* blockList = &cUnit->blockList;
+
+ /* Iterate through the dominated blocks first */
+ while (true) {
+ int bbIdx = oatBitVectorIteratorNext(&bvIterator);
+ if (bbIdx == -1) break;
+ BasicBlock* dominatedBB =
+ (BasicBlock* ) oatGrowableListGetElement(blockList, bbIdx);
+ computeDomPostOrderTraversal(cUnit, dominatedBB);
+ }
+
+ /* Enter the current block id */
+ oatInsertGrowableList(&cUnit->domPostOrderTraversal, bb->id);
+
+ /* hacky loop detection */
+ if (bb->taken && oatIsBitSet(bb->dominators, bb->taken->id)) {
+ cUnit->hasLoop = true;
+ }
+}
+
+static void checkForDominanceFrontier(BasicBlock* domBB,
+ const BasicBlock* succBB)
+{
+ /*
+ * TODO - evaluate whether phi will ever need to be inserted into exit
+ * blocks.
+ */
+ if (succBB->iDom != domBB &&
+ succBB->blockType == kDalvikByteCode &&
+ succBB->hidden == false) {
+ oatSetBit(domBB->domFrontier, succBB->id);
+ }
+}
+
+/* Worker function to compute the dominance frontier */
+static bool computeDominanceFrontier(CompilationUnit* cUnit, BasicBlock* bb)
+{
+ GrowableList* blockList = &cUnit->blockList;
+
+ /* Calculate DF_local */
+ if (bb->taken) {
+ checkForDominanceFrontier(bb, bb->taken);
+ }
+ if (bb->fallThrough) {
+ checkForDominanceFrontier(bb, bb->fallThrough);
+ }
+ if (bb->successorBlockList.blockListType != kNotUsed) {
+ GrowableListIterator iterator;
+ oatGrowableListIteratorInit(&bb->successorBlockList.blocks,
+ &iterator);
+ while (true) {
+ SuccessorBlockInfo *successorBlockInfo =
+ (SuccessorBlockInfo *) oatGrowableListIteratorNext(&iterator);
+ if (successorBlockInfo == NULL) break;
+ BasicBlock* succBB = successorBlockInfo->block;
+ checkForDominanceFrontier(bb, succBB);
+ }
+ }
+
+ /* Calculate DF_up */
+ ArenaBitVectorIterator bvIterator;
+ oatBitVectorIteratorInit(bb->iDominated, &bvIterator);
+ while (true) {
+ int dominatedIdx = oatBitVectorIteratorNext(&bvIterator);
+ if (dominatedIdx == -1) break;
+ BasicBlock* dominatedBB = (BasicBlock* )
+ oatGrowableListGetElement(blockList, dominatedIdx);
+ ArenaBitVectorIterator dfIterator;
+ oatBitVectorIteratorInit(dominatedBB->domFrontier, &dfIterator);
+ while (true) {
+ int dfUpIdx = oatBitVectorIteratorNext(&dfIterator);
+ if (dfUpIdx == -1) break;
+ BasicBlock* dfUpBlock = (BasicBlock* )
+ oatGrowableListGetElement(blockList, dfUpIdx);
+ checkForDominanceFrontier(bb, dfUpBlock);
+ }
+ }
+
+ return true;
+}
+
+/* Worker function for initializing domination-related data structures */
+static bool initializeDominationInfo(CompilationUnit* cUnit, BasicBlock* bb)
+{
+ int numTotalBlocks = cUnit->blockList.numUsed;
+
+ if (bb->dominators == NULL ) {
+ bb->dominators = oatAllocBitVector(numTotalBlocks,
+ false /* expandable */);
+ bb->iDominated = oatAllocBitVector(numTotalBlocks,
+ false /* expandable */);
+ bb->domFrontier = oatAllocBitVector(numTotalBlocks,
+ false /* expandable */);
+ } else {
+ oatClearAllBits(bb->dominators);
+ oatClearAllBits(bb->iDominated);
+ oatClearAllBits(bb->domFrontier);
+ }
+ /* Set all bits in the dominator vector */
+ oatSetInitialBits(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;
+ ArenaBitVector* tempBlockV = cUnit->tempBlockV;
+ ArenaBitVectorIterator 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;
+
+ oatSetInitialBits(tempBlockV, numTotalBlocks);
+
+ /* Iterate through the predecessors */
+ oatBitVectorIteratorInit(bb->predecessors, &bvIterator);
+ while (true) {
+ int predIdx = oatBitVectorIteratorNext(&bvIterator);
+ if (predIdx == -1) break;
+ BasicBlock* predBB = (BasicBlock* ) oatGrowableListGetElement(
+ blockList, predIdx);
+ /* tempBlockV = tempBlockV ^ dominators */
+ oatIntersectBitVectors(tempBlockV, tempBlockV, predBB->dominators);
+ }
+ oatSetBit(tempBlockV, bb->id);
+ if (oatCompareBitVectors(tempBlockV, bb->dominators)) {
+ oatCopyBitVector(bb->dominators, tempBlockV);
+ return true;
+ }
+ return false;
+}
+
+/* Worker function to compute the idom */
+static bool computeImmediateDominator(CompilationUnit* cUnit, BasicBlock* bb)
+{
+ GrowableList* blockList = &cUnit->blockList;
+ ArenaBitVector* tempBlockV = cUnit->tempBlockV;
+ ArenaBitVectorIterator bvIterator;
+ BasicBlock* iDom;
+
+ if (bb == cUnit->entryBlock) return false;
+
+ oatCopyBitVector(tempBlockV, bb->dominators);
+ oatClearBit(tempBlockV, bb->id);
+ oatBitVectorIteratorInit(tempBlockV, &bvIterator);
+
+ /* Should not see any dead block */
+ assert(oatCountSetBits(tempBlockV) != 0);
+ if (oatCountSetBits(tempBlockV) == 1) {
+ iDom = (BasicBlock* ) oatGrowableListGetElement(
+ blockList, oatBitVectorIteratorNext(&bvIterator));
+ bb->iDom = iDom;
+ } else {
+ int iDomIdx = oatBitVectorIteratorNext(&bvIterator);
+ assert(iDomIdx != -1);
+ while (true) {
+ int nextDom = oatBitVectorIteratorNext(&bvIterator);
+ if (nextDom == -1) break;
+ BasicBlock* nextDomBB = (BasicBlock* )
+ oatGrowableListGetElement(blockList, nextDom);
+ /* iDom dominates nextDom - set new iDom */
+ if (oatIsBitSet(nextDomBB->dominators, iDomIdx)) {
+ iDomIdx = nextDom;
+ }
+
+ }
+ iDom = (BasicBlock* ) oatGrowableListGetElement(blockList, iDomIdx);
+ /* Set the immediate dominator block for bb */
+ bb->iDom = iDom;
+ }
+ /* Add bb to the iDominated set of the immediate dominator block */
+ oatSetBit(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 */
+ oatDataFlowAnalysisDispatcher(cUnit, initializeDominationInfo,
+ kReachableNodes,
+ false /* isIterative */);
+
+ /* Set the dominator for the root node */
+ oatClearAllBits(cUnit->entryBlock->dominators);
+ oatSetBit(cUnit->entryBlock->dominators, cUnit->entryBlock->id);
+
+ if (cUnit->tempBlockV == NULL) {
+ cUnit->tempBlockV = oatAllocBitVector(numTotalBlocks,
+ false /* expandable */);
+ } else {
+ oatClearAllBits(cUnit->tempBlockV);
+ }
+ oatDataFlowAnalysisDispatcher(cUnit, computeBlockDominators,
+ kPreOrderDFSTraversal,
+ true /* isIterative */);
+
+ cUnit->entryBlock->iDom = NULL;
+ oatDataFlowAnalysisDispatcher(cUnit, computeImmediateDominator,
+ kReachableNodes,
+ false /* isIterative */);
+
+ /*
+ * Now go ahead and compute the post order traversal based on the
+ * iDominated sets.
+ */
+ if (cUnit->domPostOrderTraversal.elemList == NULL) {
+ oatInitGrowableList(&cUnit->domPostOrderTraversal, numReachableBlocks);
+ } else {
+ cUnit->domPostOrderTraversal.numUsed = 0;
+ }
+
+ computeDomPostOrderTraversal(cUnit, cUnit->entryBlock);
+ assert(cUnit->domPostOrderTraversal.numUsed ==
+ (unsigned) cUnit->numReachableBlocks);
+
+ /* Now compute the dominance frontier for each block */
+ oatDataFlowAnalysisDispatcher(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(ArenaBitVector* dest,
+ const ArenaBitVector* src1,
+ const ArenaBitVector* src2)
+{
+ if (dest->storageSize != src1->storageSize ||
+ dest->storageSize != src2->storageSize ||
+ dest->expandable != src1->expandable ||
+ dest->expandable != src2->expandable) {
+ LOG(FATAL) << "Incompatible set properties";
+ }
+
+ unsigned int idx;
+ for (idx = 0; idx < dest->storageSize; idx++) {
+ dest->storage[idx] |= src1->storage[idx] & ~src2->storage[idx];
+ }
+}
+
+/*
+ * 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)
+{
+ ArenaBitVector* tempDalvikRegisterV = cUnit->tempDalvikRegisterV;
+
+ if (bb->dataFlowInfo == NULL) return false;
+ oatCopyBitVector(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;
+ oatGrowableListIteratorInit(&bb->successorBlockList.blocks,
+ &iterator);
+ while (true) {
+ SuccessorBlockInfo *successorBlockInfo =
+ (SuccessorBlockInfo *) oatGrowableListIteratorNext(&iterator);
+ if (successorBlockInfo == NULL) break;
+ BasicBlock* succBB = successorBlockInfo->block;
+ if (succBB->dataFlowInfo) {
+ computeSuccLiveIn(tempDalvikRegisterV,
+ succBB->dataFlowInfo->liveInV,
+ bb->dataFlowInfo->defV);
+ }
+ }
+ }
+ if (oatCompareBitVectors(tempDalvikRegisterV, bb->dataFlowInfo->liveInV)) {
+ oatCopyBitVector(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;
+ ArenaBitVector* phiBlocks =
+ oatAllocBitVector(cUnit->numBlocks, false);
+ ArenaBitVector* tmpBlocks =
+ oatAllocBitVector(cUnit->numBlocks, false);
+ ArenaBitVector* inputBlocks =
+ oatAllocBitVector(cUnit->numBlocks, false);
+
+ cUnit->tempDalvikRegisterV =
+ oatAllocBitVector(cUnit->numDalvikRegisters, false);
+
+ oatDataFlowAnalysisDispatcher(cUnit, computeBlockLiveIns,
+ kPostOrderDFSTraversal,
+ true /* isIterative */);
+
+ /* Iterate through each Dalvik register */
+ for (dalvikReg = 0; dalvikReg < cUnit->numDalvikRegisters; dalvikReg++) {
+ bool change;
+ ArenaBitVectorIterator iterator;
+
+ oatCopyBitVector(inputBlocks, cUnit->defBlockMatrix[dalvikReg]);
+ oatClearAllBits(phiBlocks);
+
+ /* Calculate the phi blocks for each Dalvik register */
+ do {
+ change = false;
+ oatClearAllBits(tmpBlocks);
+ oatBitVectorIteratorInit(inputBlocks, &iterator);
+
+ while (true) {
+ int idx = oatBitVectorIteratorNext(&iterator);
+ if (idx == -1) break;
+ BasicBlock* defBB =
+ (BasicBlock* ) oatGrowableListGetElement(blockList, idx);
+
+ /* Merge the dominance frontier to tmpBlocks */
+ oatUnifyBitVectors(tmpBlocks, tmpBlocks, defBB->domFrontier);
+ }
+ if (oatCompareBitVectors(phiBlocks, tmpBlocks)) {
+ change = true;
+ oatCopyBitVector(phiBlocks, tmpBlocks);
+
+ /*
+ * Iterate through the original blocks plus the new ones in
+ * the dominance frontier.
+ */
+ oatCopyBitVector(inputBlocks, phiBlocks);
+ oatUnifyBitVectors(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.
+ */
+ oatBitVectorIteratorInit(phiBlocks, &iterator);
+ while (true) {
+ int idx = oatBitVectorIteratorNext(&iterator);
+ if (idx == -1) break;
+ BasicBlock* phiBB =
+ (BasicBlock* ) oatGrowableListGetElement(blockList, idx);
+ /* Variable will be clobbered before being used - no need for phi */
+ if (!oatIsBitSet(phiBB->dataFlowInfo->liveInV, dalvikReg)) continue;
+ MIR *phi = (MIR *) oatNew(sizeof(MIR), true);
+ phi->dalvikInsn.opcode = (Opcode)kMirOpPhi;
+ phi->dalvikInsn.vA = dalvikReg;
+ phi->offset = phiBB->startOffset;
+ oatPrependMIR(phiBB, phi);
+ }
+ }
+}
+
+/*
+ * Worker function to insert phi-operands with latest SSA names from
+ * predecessor blocks
+ */
+static bool insertPhiNodeOperands(CompilationUnit* cUnit, BasicBlock* bb)
+{
+ ArenaBitVector* ssaRegV = cUnit->tempSSARegisterV;
+ ArenaBitVectorIterator 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 != (Opcode)kMirOpPhi)
+ return true;
+ int ssaReg = mir->ssaRep->defs[0];
+ int encodedDalvikValue =
+ (int) oatGrowableListGetElement(cUnit->ssaToDalvikMap, ssaReg);
+ int dalvikReg = DECODE_REG(encodedDalvikValue);
+
+ oatClearAllBits(ssaRegV);
+
+ /* Iterate through the predecessors */
+ oatBitVectorIteratorInit(bb->predecessors, &bvIterator);
+ while (true) {
+ int predIdx = oatBitVectorIteratorNext(&bvIterator);
+ if (predIdx == -1) break;
+ BasicBlock* predBB = (BasicBlock* ) oatGrowableListGetElement(
+ blockList, predIdx);
+ int encodedSSAValue =
+ predBB->dataFlowInfo->dalvikToSSAMap[dalvikReg];
+ int ssaReg = DECODE_REG(encodedSSAValue);
+ oatSetBit(ssaRegV, ssaReg);
+ }
+
+ /* Count the number of SSA registers for a Dalvik register */
+ int numUses = oatCountSetBits(ssaRegV);
+ mir->ssaRep->numUses = numUses;
+ mir->ssaRep->uses =
+ (int *) oatNew(sizeof(int) * numUses, false);
+ mir->ssaRep->fpUse =
+ (bool *) oatNew(sizeof(bool) * numUses, true);
+
+ ArenaBitVectorIterator phiIterator;
+
+ oatBitVectorIteratorInit(ssaRegV, &phiIterator);
+ int *usePtr = mir->ssaRep->uses;
+
+ /* Set the uses array for the phi node */
+ while (true) {
+ int ssaRegIdx = oatBitVectorIteratorNext(&phiIterator);
+ if (ssaRegIdx == -1) break;
+ *usePtr++ = ssaRegIdx;
+ }
+ }
+
+ return true;
+}
+
+/* Perform SSA transformation for the whole method */
+void oatMethodSSATransformation(CompilationUnit* cUnit)
+{
+ /* Compute the DFS order */
+ computeDFSOrder(cUnit);
+
+ /* Compute the dominator info */
+ computeDominators(cUnit);
+
+ /* Allocate data structures in preparation for SSA conversion */
+ oatInitializeSSAConversion(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 */
+ oatDataFlowAnalysisDispatcher(cUnit, oatDoSSAConversion,
+ kPreOrderDFSTraversal,
+ false /* isIterative */);
+
+ /*
+ * Shared temp bit vector used by each block to count the number of defs
+ * from all the predecessor blocks.
+ */
+ cUnit->tempSSARegisterV = oatAllocBitVector(cUnit->numSSARegs,
+ false);
+
+ /* Insert phi-operands with latest SSA names from predecessor blocks */
+ oatDataFlowAnalysisDispatcher(cUnit, insertPhiNodeOperands,
+ kReachableNodes,
+ false /* isIterative */);
+}