[Compiler] use Art indentation standard
First of several CLs to bring code closer to alignment with Art and LLVM
standards. Move to 2-space indenting. Sticking with 80-col line
length (which LLVM apparently also wants). LLVM also prefers camel
case names, so keeping Dalvik convention there as well (for now).
Change-Id: I351ab234e640678d97747377cccdd6df0a770f4a
diff --git a/src/compiler/SSATransformation.cc b/src/compiler/SSATransformation.cc
index c5a6b8f..ada9351 100644
--- a/src/compiler/SSATransformation.cc
+++ b/src/compiler/SSATransformation.cc
@@ -23,74 +23,73 @@
void recordDFSOrders(CompilationUnit* cUnit, BasicBlock* block)
{
- if (block->visited || block->hidden) return;
- block->visited = true;
+ if (block->visited || block->hidden) return;
+ block->visited = true;
- // Can this block be reached only via previous block fallthrough?
- if ((block->blockType == kDalvikByteCode) &&
- (block->predecessors->numUsed == 1)) {
- DCHECK_GE(cUnit->dfsOrder.numUsed, 1U);
- int prevIdx = cUnit->dfsOrder.numUsed - 1;
- int prevId = cUnit->dfsOrder.elemList[prevIdx];
- BasicBlock* predBB = (BasicBlock*)block->predecessors->elemList[0];
- if (predBB->id == prevId) {
- block->fallThroughTarget = true;
- }
+ // Can this block be reached only via previous block fallthrough?
+ if ((block->blockType == kDalvikByteCode) &&
+ (block->predecessors->numUsed == 1)) {
+ DCHECK_GE(cUnit->dfsOrder.numUsed, 1U);
+ int prevIdx = cUnit->dfsOrder.numUsed - 1;
+ int prevId = cUnit->dfsOrder.elemList[prevIdx];
+ BasicBlock* predBB = (BasicBlock*)block->predecessors->elemList[0];
+ if (predBB->id == prevId) {
+ block->fallThroughTarget = true;
}
+ }
- /* Enqueue the preOrder block id */
- oatInsertGrowableList(cUnit, &cUnit->dfsOrder, block->id);
+ /* Enqueue the preOrder block id */
+ oatInsertGrowableList(cUnit, &cUnit->dfsOrder, block->id);
- if (block->fallThrough) {
- recordDFSOrders(cUnit, block->fallThrough);
+ if (block->fallThrough) {
+ recordDFSOrders(cUnit, block->fallThrough);
+ }
+ if (block->taken) recordDFSOrders(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;
+ recordDFSOrders(cUnit, succBB);
}
- if (block->taken) recordDFSOrders(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;
- recordDFSOrders(cUnit, succBB);
- }
- }
+ }
- /* Record postorder in basic block and enqueue normal id in dfsPostOrder */
- block->dfsId = cUnit->dfsPostOrder.numUsed;
- oatInsertGrowableList(cUnit, &cUnit->dfsPostOrder, block->id);
- return;
+ /* Record postorder in basic block and enqueue normal id in dfsPostOrder */
+ block->dfsId = cUnit->dfsPostOrder.numUsed;
+ oatInsertGrowableList(cUnit, &cUnit->dfsPostOrder, block->id);
+ return;
}
/* Sort the blocks by the Depth-First-Search */
void computeDFSOrders(CompilationUnit* cUnit)
{
- /* Initialize or reset the DFS preOrder list */
- if (cUnit->dfsOrder.elemList == NULL) {
- oatInitGrowableList(cUnit, &cUnit->dfsOrder, cUnit->numBlocks,
- kListDfsOrder);
- } else {
- /* Just reset the used length on the counter */
- cUnit->dfsOrder.numUsed = 0;
- }
+ /* Initialize or reset the DFS preOrder list */
+ if (cUnit->dfsOrder.elemList == NULL) {
+ oatInitGrowableList(cUnit, &cUnit->dfsOrder, cUnit->numBlocks,
+ kListDfsOrder);
+ } else {
+ /* Just reset the used length on the counter */
+ cUnit->dfsOrder.numUsed = 0;
+ }
- /* Initialize or reset the DFS postOrder list */
- if (cUnit->dfsPostOrder.elemList == NULL) {
- oatInitGrowableList(cUnit, &cUnit->dfsPostOrder, cUnit->numBlocks,
- kListDfsPostOrder);
- } else {
- /* Just reset the used length on the counter */
- cUnit->dfsPostOrder.numUsed = 0;
- }
+ /* Initialize or reset the DFS postOrder list */
+ if (cUnit->dfsPostOrder.elemList == NULL) {
+ oatInitGrowableList(cUnit, &cUnit->dfsPostOrder, cUnit->numBlocks,
+ kListDfsPostOrder);
+ } else {
+ /* Just reset the used length on the counter */
+ cUnit->dfsPostOrder.numUsed = 0;
+ }
- oatDataFlowAnalysisDispatcher(cUnit, oatClearVisitedFlag,
- kAllNodes,
- false /* isIterative */);
+ oatDataFlowAnalysisDispatcher(cUnit, oatClearVisitedFlag,
+ kAllNodes, false /* isIterative */);
- recordDFSOrders(cUnit, cUnit->entryBlock);
- cUnit->numReachableBlocks = cUnit->dfsOrder.numUsed;
+ recordDFSOrders(cUnit, cUnit->entryBlock);
+ cUnit->numReachableBlocks = cUnit->dfsOrder.numUsed;
}
/*
@@ -99,165 +98,163 @@
*/
bool fillDefBlockMatrix(CompilationUnit* cUnit, BasicBlock* bb)
{
- if (bb->dataFlowInfo == NULL) return false;
+ if (bb->dataFlowInfo == NULL) return false;
- ArenaBitVectorIterator iterator;
+ ArenaBitVectorIterator iterator;
- oatBitVectorIteratorInit(bb->dataFlowInfo->defV, &iterator);
- while (true) {
- int idx = oatBitVectorIteratorNext(&iterator);
- if (idx == -1) break;
- /* Block bb defines register idx */
- oatSetBit(cUnit, cUnit->defBlockMatrix[idx], bb->id);
- }
- return true;
+ oatBitVectorIteratorInit(bb->dataFlowInfo->defV, &iterator);
+ while (true) {
+ int idx = oatBitVectorIteratorNext(&iterator);
+ if (idx == -1) break;
+ /* Block bb defines register idx */
+ oatSetBit(cUnit, cUnit->defBlockMatrix[idx], bb->id);
+ }
+ return true;
}
void computeDefBlockMatrix(CompilationUnit* cUnit)
{
- int numRegisters = cUnit->numDalvikRegisters;
- /* Allocate numDalvikRegisters bit vector pointers */
- cUnit->defBlockMatrix = (ArenaBitVector **)
- oatNew(cUnit, sizeof(ArenaBitVector *) * numRegisters, true,
- kAllocDFInfo);
- int i;
+ int numRegisters = cUnit->numDalvikRegisters;
+ /* Allocate numDalvikRegisters bit vector pointers */
+ cUnit->defBlockMatrix = (ArenaBitVector **)
+ oatNew(cUnit, sizeof(ArenaBitVector *) * numRegisters, true,
+ kAllocDFInfo);
+ int i;
- /* Initialize numRegister vectors with numBlocks bits each */
- for (i = 0; i < numRegisters; i++) {
- cUnit->defBlockMatrix[i] = oatAllocBitVector(cUnit, cUnit->numBlocks,
- false, kBitMapBMatrix);
- }
- oatDataFlowAnalysisDispatcher(cUnit, oatFindLocalLiveIn,
- kAllNodes,
- false /* isIterative */);
- oatDataFlowAnalysisDispatcher(cUnit, fillDefBlockMatrix,
- kAllNodes,
- false /* isIterative */);
+ /* Initialize numRegister vectors with numBlocks bits each */
+ for (i = 0; i < numRegisters; i++) {
+ cUnit->defBlockMatrix[i] = oatAllocBitVector(cUnit, cUnit->numBlocks,
+ false, kBitMapBMatrix);
+ }
+ 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 numRegs = cUnit->numDalvikRegisters;
- int inReg = numRegs - cUnit->numIns;
- for (; inReg < numRegs; inReg++) {
- oatSetBit(cUnit, cUnit->defBlockMatrix[inReg], cUnit->entryBlock->id);
- }
+ /*
+ * Also set the incoming parameters as defs in the entry block.
+ * Only need to handle the parameters for the outer method.
+ */
+ int numRegs = cUnit->numDalvikRegisters;
+ int inReg = numRegs - cUnit->numIns;
+ for (; inReg < numRegs; inReg++) {
+ oatSetBit(cUnit, cUnit->defBlockMatrix[inReg], cUnit->entryBlock->id);
+ }
}
/* Compute the post-order traversal of the CFG */
void computeDomPostOrderTraversal(CompilationUnit* cUnit, BasicBlock* bb)
{
- ArenaBitVectorIterator bvIterator;
- oatBitVectorIteratorInit(bb->iDominated, &bvIterator);
- GrowableList* blockList = &cUnit->blockList;
+ ArenaBitVectorIterator bvIterator;
+ oatBitVectorIteratorInit(bb->iDominated, &bvIterator);
+ GrowableList* blockList = &cUnit->blockList;
- /* Iterate through the dominated blocks first */
- while (true) {
- //TUNING: hot call to oatBitVectorIteratorNext
- int bbIdx = oatBitVectorIteratorNext(&bvIterator);
- if (bbIdx == -1) break;
- BasicBlock* dominatedBB =
- (BasicBlock* ) oatGrowableListGetElement(blockList, bbIdx);
- computeDomPostOrderTraversal(cUnit, dominatedBB);
- }
+ /* Iterate through the dominated blocks first */
+ while (true) {
+ //TUNING: hot call to oatBitVectorIteratorNext
+ int bbIdx = oatBitVectorIteratorNext(&bvIterator);
+ if (bbIdx == -1) break;
+ BasicBlock* dominatedBB =
+ (BasicBlock* ) oatGrowableListGetElement(blockList, bbIdx);
+ computeDomPostOrderTraversal(cUnit, dominatedBB);
+ }
- /* Enter the current block id */
- oatInsertGrowableList(cUnit, &cUnit->domPostOrderTraversal, bb->id);
+ /* Enter the current block id */
+ oatInsertGrowableList(cUnit, &cUnit->domPostOrderTraversal, bb->id);
- /* hacky loop detection */
- if (bb->taken && oatIsBitSet(bb->dominators, bb->taken->id)) {
- cUnit->hasLoop = true;
- }
+ /* hacky loop detection */
+ if (bb->taken && oatIsBitSet(bb->dominators, bb->taken->id)) {
+ cUnit->hasLoop = true;
+ }
}
void checkForDominanceFrontier(CompilationUnit* cUnit, BasicBlock* domBB,
- const BasicBlock* succBB)
+ 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(cUnit, domBB->domFrontier, succBB->id);
- }
+ /*
+ * TODO - evaluate whether phi will ever need to be inserted into exit
+ * blocks.
+ */
+ if (succBB->iDom != domBB &&
+ succBB->blockType == kDalvikByteCode &&
+ succBB->hidden == false) {
+ oatSetBit(cUnit, domBB->domFrontier, succBB->id);
+ }
}
/* Worker function to compute the dominance frontier */
bool computeDominanceFrontier(CompilationUnit* cUnit, BasicBlock* bb)
{
- GrowableList* blockList = &cUnit->blockList;
+ GrowableList* blockList = &cUnit->blockList;
- /* Calculate DF_local */
- if (bb->taken) {
- checkForDominanceFrontier(cUnit, bb, bb->taken);
- }
- if (bb->fallThrough) {
- checkForDominanceFrontier(cUnit, 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(cUnit, bb, succBB);
- }
- }
+ /* Calculate DF_local */
+ if (bb->taken) {
+ checkForDominanceFrontier(cUnit, bb, bb->taken);
+ }
+ if (bb->fallThrough) {
+ checkForDominanceFrontier(cUnit, 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(cUnit, bb, succBB);
+ }
+ }
- /* Calculate DF_up */
- ArenaBitVectorIterator bvIterator;
- oatBitVectorIteratorInit(bb->iDominated, &bvIterator);
+ /* Calculate DF_up */
+ ArenaBitVectorIterator bvIterator;
+ oatBitVectorIteratorInit(bb->iDominated, &bvIterator);
+ while (true) {
+ //TUNING: hot call to oatBitVectorIteratorNext
+ int dominatedIdx = oatBitVectorIteratorNext(&bvIterator);
+ if (dominatedIdx == -1) break;
+ BasicBlock* dominatedBB = (BasicBlock* )
+ oatGrowableListGetElement(blockList, dominatedIdx);
+ ArenaBitVectorIterator dfIterator;
+ oatBitVectorIteratorInit(dominatedBB->domFrontier, &dfIterator);
while (true) {
- //TUNING: hot call to oatBitVectorIteratorNext
- int dominatedIdx = oatBitVectorIteratorNext(&bvIterator);
- if (dominatedIdx == -1) break;
- BasicBlock* dominatedBB = (BasicBlock* )
- oatGrowableListGetElement(blockList, dominatedIdx);
- ArenaBitVectorIterator dfIterator;
- oatBitVectorIteratorInit(dominatedBB->domFrontier, &dfIterator);
- while (true) {
- //TUNING: hot call to oatBitVectorIteratorNext
- int dfUpIdx = oatBitVectorIteratorNext(&dfIterator);
- if (dfUpIdx == -1) break;
- BasicBlock* dfUpBlock = (BasicBlock* )
- oatGrowableListGetElement(blockList, dfUpIdx);
- checkForDominanceFrontier(cUnit, bb, dfUpBlock);
- }
+ //TUNING: hot call to oatBitVectorIteratorNext
+ int dfUpIdx = oatBitVectorIteratorNext(&dfIterator);
+ if (dfUpIdx == -1) break;
+ BasicBlock* dfUpBlock = (BasicBlock* )
+ oatGrowableListGetElement(blockList, dfUpIdx);
+ checkForDominanceFrontier(cUnit, bb, dfUpBlock);
}
+ }
- return true;
+ return true;
}
/* Worker function for initializing domination-related data structures */
bool initializeDominationInfo(CompilationUnit* cUnit, BasicBlock* bb)
{
- int numTotalBlocks = cUnit->blockList.numUsed;
+ int numTotalBlocks = cUnit->blockList.numUsed;
- if (bb->dominators == NULL ) {
- bb->dominators = oatAllocBitVector(cUnit, numTotalBlocks,
- false /* expandable */,
- kBitMapDominators);
- bb->iDominated = oatAllocBitVector(cUnit, numTotalBlocks,
- false /* expandable */,
- kBitMapIDominated);
- bb->domFrontier = oatAllocBitVector(cUnit, numTotalBlocks,
- false /* expandable */,
- kBitMapDomFrontier);
- } else {
- oatClearAllBits(bb->dominators);
- oatClearAllBits(bb->iDominated);
- oatClearAllBits(bb->domFrontier);
- }
- /* Set all bits in the dominator vector */
- oatSetInitialBits(bb->dominators, numTotalBlocks);
+ if (bb->dominators == NULL ) {
+ bb->dominators = oatAllocBitVector(cUnit, numTotalBlocks,
+ false /* expandable */,
+ kBitMapDominators);
+ bb->iDominated = oatAllocBitVector(cUnit, numTotalBlocks,
+ false /* expandable */,
+ kBitMapIDominated);
+ bb->domFrontier = oatAllocBitVector(cUnit, numTotalBlocks,
+ false /* expandable */,
+ kBitMapDomFrontier);
+ } else {
+ oatClearAllBits(bb->dominators);
+ oatClearAllBits(bb->iDominated);
+ oatClearAllBits(bb->domFrontier);
+ }
+ /* Set all bits in the dominator vector */
+ oatSetInitialBits(bb->dominators, numTotalBlocks);
- return true;
+ return true;
}
/*
@@ -267,35 +264,35 @@
*/
bool slowComputeBlockDominators(CompilationUnit* cUnit, BasicBlock* bb)
{
- GrowableList* blockList = &cUnit->blockList;
- int numTotalBlocks = blockList->numUsed;
- ArenaBitVector* tempBlockV = cUnit->tempBlockV;
- GrowableListIterator iter;
+ GrowableList* blockList = &cUnit->blockList;
+ int numTotalBlocks = blockList->numUsed;
+ ArenaBitVector* tempBlockV = cUnit->tempBlockV;
+ GrowableListIterator iter;
- /*
- * 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;
+ /*
+ * 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);
+ oatSetInitialBits(tempBlockV, numTotalBlocks);
- /* Iterate through the predecessors */
- oatGrowableListIteratorInit(bb->predecessors, &iter);
- while (true) {
- BasicBlock* predBB = (BasicBlock*)oatGrowableListIteratorNext(&iter);
- if (!predBB) break;
- /* tempBlockV = tempBlockV ^ dominators */
- if (predBB->dominators != NULL) {
- oatIntersectBitVectors(tempBlockV, tempBlockV, predBB->dominators);
- }
+ /* Iterate through the predecessors */
+ oatGrowableListIteratorInit(bb->predecessors, &iter);
+ while (true) {
+ BasicBlock* predBB = (BasicBlock*)oatGrowableListIteratorNext(&iter);
+ if (!predBB) break;
+ /* tempBlockV = tempBlockV ^ dominators */
+ if (predBB->dominators != NULL) {
+ oatIntersectBitVectors(tempBlockV, tempBlockV, predBB->dominators);
}
- oatSetBit(cUnit, tempBlockV, bb->id);
- if (oatCompareBitVectors(tempBlockV, bb->dominators)) {
- oatCopyBitVector(bb->dominators, tempBlockV);
- return true;
- }
- return false;
+ }
+ oatSetBit(cUnit, tempBlockV, bb->id);
+ if (oatCompareBitVectors(tempBlockV, bb->dominators)) {
+ oatCopyBitVector(bb->dominators, tempBlockV);
+ return true;
+ }
+ return false;
}
/*
@@ -305,44 +302,45 @@
*/
bool slowComputeBlockIDom(CompilationUnit* cUnit, BasicBlock* bb)
{
- GrowableList* blockList = &cUnit->blockList;
- ArenaBitVector* tempBlockV = cUnit->tempBlockV;
- ArenaBitVectorIterator bvIterator;
- BasicBlock* iDom;
+ GrowableList* blockList = &cUnit->blockList;
+ ArenaBitVector* tempBlockV = cUnit->tempBlockV;
+ ArenaBitVectorIterator bvIterator;
+ BasicBlock* iDom;
- if (bb == cUnit->entryBlock) return false;
+ if (bb == cUnit->entryBlock) return false;
- oatCopyBitVector(tempBlockV, bb->dominators);
- oatClearBit(tempBlockV, bb->id);
- oatBitVectorIteratorInit(tempBlockV, &bvIterator);
+ oatCopyBitVector(tempBlockV, bb->dominators);
+ oatClearBit(tempBlockV, bb->id);
+ oatBitVectorIteratorInit(tempBlockV, &bvIterator);
- /* Should not see any dead block */
- DCHECK_NE(oatCountSetBits(tempBlockV), 0);
- if (oatCountSetBits(tempBlockV) == 1) {
- iDom = (BasicBlock* ) oatGrowableListGetElement(
- blockList, oatBitVectorIteratorNext(&bvIterator));
- bb->iDom = iDom;
- } else {
- int iDomIdx = oatBitVectorIteratorNext(&bvIterator);
- DCHECK_NE(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;
- }
+ /* Should not see any dead block */
+ DCHECK_NE(oatCountSetBits(tempBlockV), 0);
+ if (oatCountSetBits(tempBlockV) == 1) {
+ iDom = (BasicBlock* )
+ oatGrowableListGetElement(blockList,
+ oatBitVectorIteratorNext(&bvIterator));
+ bb->iDom = iDom;
+ } else {
+ int iDomIdx = oatBitVectorIteratorNext(&bvIterator);
+ DCHECK_NE(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(cUnit, iDom->iDominated, bb->id);
- return true;
+ 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(cUnit, iDom->iDominated, bb->id);
+ return true;
}
/*
@@ -352,175 +350,174 @@
*/
int findCommonParent(CompilationUnit *cUnit, int block1, int block2)
{
- while (block1 != block2) {
- while (block1 < block2) {
- block1 = cUnit->iDomList[block1];
- DCHECK_NE(block1, NOTVISITED);
- }
- while (block2 < block1) {
- block2 = cUnit->iDomList[block2];
- DCHECK_NE(block2, NOTVISITED);
- }
+ while (block1 != block2) {
+ while (block1 < block2) {
+ block1 = cUnit->iDomList[block1];
+ DCHECK_NE(block1, NOTVISITED);
}
- return block1;
+ while (block2 < block1) {
+ block2 = cUnit->iDomList[block2];
+ DCHECK_NE(block2, NOTVISITED);
+ }
+ }
+ return block1;
}
/* Worker function to compute each block's immediate dominator */
bool computeBlockIDom(CompilationUnit* cUnit, BasicBlock* bb)
{
- GrowableListIterator iter;
- int idom = -1;
+ GrowableListIterator iter;
+ int idom = -1;
- /* Special-case entry block */
- if (bb == cUnit->entryBlock) {
- return false;
- }
-
- /* Iterate through the predecessors */
- oatGrowableListIteratorInit(bb->predecessors, &iter);
-
- /* Find the first processed predecessor */
- while (true) {
- BasicBlock* predBB = (BasicBlock*)oatGrowableListIteratorNext(&iter);
- CHECK(predBB != NULL);
- if (cUnit->iDomList[predBB->dfsId] != NOTVISITED) {
- idom = predBB->dfsId;
- break;
- }
- }
-
- /* Scan the rest of the predecessors */
- while (true) {
- BasicBlock* predBB = (BasicBlock*)oatGrowableListIteratorNext(&iter);
- if (!predBB) break;
- if (cUnit->iDomList[predBB->dfsId] == NOTVISITED) {
- continue;
- } else {
- idom = findCommonParent(cUnit, predBB->dfsId, idom);
- }
- }
-
- DCHECK_NE(idom, NOTVISITED);
-
- /* Did something change? */
- if (cUnit->iDomList[bb->dfsId] != idom) {
- cUnit->iDomList[bb->dfsId] = idom;
- return true;
- }
+ /* Special-case entry block */
+ if (bb == cUnit->entryBlock) {
return false;
+ }
+
+ /* Iterate through the predecessors */
+ oatGrowableListIteratorInit(bb->predecessors, &iter);
+
+ /* Find the first processed predecessor */
+ while (true) {
+ BasicBlock* predBB = (BasicBlock*)oatGrowableListIteratorNext(&iter);
+ CHECK(predBB != NULL);
+ if (cUnit->iDomList[predBB->dfsId] != NOTVISITED) {
+ idom = predBB->dfsId;
+ break;
+ }
+ }
+
+ /* Scan the rest of the predecessors */
+ while (true) {
+ BasicBlock* predBB = (BasicBlock*)oatGrowableListIteratorNext(&iter);
+ if (!predBB) break;
+ if (cUnit->iDomList[predBB->dfsId] == NOTVISITED) {
+ continue;
+ } else {
+ idom = findCommonParent(cUnit, predBB->dfsId, idom);
+ }
+ }
+
+ DCHECK_NE(idom, NOTVISITED);
+
+ /* Did something change? */
+ if (cUnit->iDomList[bb->dfsId] != idom) {
+ cUnit->iDomList[bb->dfsId] = idom;
+ return true;
+ }
+ return false;
}
/* Worker function to compute each block's domintors */
bool computeBlockDominators(CompilationUnit* cUnit, BasicBlock* bb)
{
- if (bb == cUnit->entryBlock) {
- oatClearAllBits(bb->dominators);
- } else {
- oatCopyBitVector(bb->dominators, bb->iDom->dominators);
- }
- oatSetBit(cUnit, bb->dominators, bb->id);
- return false;
+ if (bb == cUnit->entryBlock) {
+ oatClearAllBits(bb->dominators);
+ } else {
+ oatCopyBitVector(bb->dominators, bb->iDom->dominators);
+ }
+ oatSetBit(cUnit, bb->dominators, bb->id);
+ return false;
}
bool setDominators(CompilationUnit* cUnit, BasicBlock* bb)
{
- if (bb != cUnit->entryBlock) {
- int iDomDFSIdx = cUnit->iDomList[bb->dfsId];
- DCHECK_NE(iDomDFSIdx, NOTVISITED);
- int iDomIdx = cUnit->dfsPostOrder.elemList[iDomDFSIdx];
- BasicBlock* iDom = (BasicBlock*)
- oatGrowableListGetElement(&cUnit->blockList, iDomIdx);
- if (cUnit->enableDebug & (1 << kDebugVerifyDataflow)) {
- DCHECK_EQ(bb->iDom->id, iDom->id);
- }
- bb->iDom = iDom;
- /* Add bb to the iDominated set of the immediate dominator block */
- oatSetBit(cUnit, iDom->iDominated, bb->id);
+ if (bb != cUnit->entryBlock) {
+ int iDomDFSIdx = cUnit->iDomList[bb->dfsId];
+ DCHECK_NE(iDomDFSIdx, NOTVISITED);
+ int iDomIdx = cUnit->dfsPostOrder.elemList[iDomDFSIdx];
+ BasicBlock* iDom = (BasicBlock*)
+ oatGrowableListGetElement(&cUnit->blockList, iDomIdx);
+ if (cUnit->enableDebug & (1 << kDebugVerifyDataflow)) {
+ DCHECK_EQ(bb->iDom->id, iDom->id);
}
- return false;
+ bb->iDom = iDom;
+ /* Add bb to the iDominated set of the immediate dominator block */
+ oatSetBit(cUnit, iDom->iDominated, bb->id);
+ }
+ return false;
}
/* Compute dominators, immediate dominator, and dominance fronter */
void computeDominators(CompilationUnit* cUnit)
{
- int numReachableBlocks = cUnit->numReachableBlocks;
- int numTotalBlocks = cUnit->blockList.numUsed;
+ int numReachableBlocks = cUnit->numReachableBlocks;
+ int numTotalBlocks = cUnit->blockList.numUsed;
- /* Initialize domination-related data structures */
- oatDataFlowAnalysisDispatcher(cUnit, initializeDominationInfo,
- kReachableNodes,
- false /* isIterative */);
+ /* Initialize domination-related data structures */
+ oatDataFlowAnalysisDispatcher(cUnit, initializeDominationInfo,
+ kReachableNodes, false /* isIterative */);
- /* Initalize & Clear iDomList */
- if (cUnit->iDomList == NULL) {
- cUnit->iDomList = (int*)oatNew(cUnit, sizeof(int) * numReachableBlocks,
- false, kAllocDFInfo);
- }
- for (int i = 0; i < numReachableBlocks; i++) {
- cUnit->iDomList[i] = NOTVISITED;
- }
+ /* Initalize & Clear iDomList */
+ if (cUnit->iDomList == NULL) {
+ cUnit->iDomList = (int*)oatNew(cUnit, sizeof(int) * numReachableBlocks,
+ false, kAllocDFInfo);
+ }
+ for (int i = 0; i < numReachableBlocks; i++) {
+ cUnit->iDomList[i] = NOTVISITED;
+ }
- /* For post-order, last block is entry block. Set its iDom to istelf */
- DCHECK_EQ(cUnit->entryBlock->dfsId, numReachableBlocks-1);
- cUnit->iDomList[cUnit->entryBlock->dfsId] = cUnit->entryBlock->dfsId;
+ /* For post-order, last block is entry block. Set its iDom to istelf */
+ DCHECK_EQ(cUnit->entryBlock->dfsId, numReachableBlocks-1);
+ cUnit->iDomList[cUnit->entryBlock->dfsId] = cUnit->entryBlock->dfsId;
- /* Compute the immediate dominators */
- oatDataFlowAnalysisDispatcher(cUnit, computeBlockIDom,
- kReversePostOrderTraversal,
+ /* Compute the immediate dominators */
+ oatDataFlowAnalysisDispatcher(cUnit, computeBlockIDom,
+ kReversePostOrderTraversal,
+ true /* isIterative */);
+
+ /* Set the dominator for the root node */
+ oatClearAllBits(cUnit->entryBlock->dominators);
+ oatSetBit(cUnit, cUnit->entryBlock->dominators, cUnit->entryBlock->id);
+
+ if (cUnit->tempBlockV == NULL) {
+ cUnit->tempBlockV = oatAllocBitVector(cUnit, numTotalBlocks,
+ false /* expandable */,
+ kBitMapTmpBlockV);
+ } else {
+ oatClearAllBits(cUnit->tempBlockV);
+ }
+ cUnit->entryBlock->iDom = NULL;
+
+ /* For testing, compute sets using alternate mechanism */
+ if (cUnit->enableDebug & (1 << kDebugVerifyDataflow)) {
+ // Use alternate mechanism to compute dominators for comparison
+ oatDataFlowAnalysisDispatcher(cUnit, slowComputeBlockDominators,
+ kPreOrderDFSTraversal,
true /* isIterative */);
- /* Set the dominator for the root node */
- oatClearAllBits(cUnit->entryBlock->dominators);
- oatSetBit(cUnit, cUnit->entryBlock->dominators, cUnit->entryBlock->id);
+ oatDataFlowAnalysisDispatcher(cUnit, slowComputeBlockIDom,
+ kReachableNodes,
+ false /* isIterative */);
+ }
- if (cUnit->tempBlockV == NULL) {
- cUnit->tempBlockV = oatAllocBitVector(cUnit, numTotalBlocks,
- false /* expandable */,
- kBitMapTmpBlockV);
- } else {
- oatClearAllBits(cUnit->tempBlockV);
- }
- cUnit->entryBlock->iDom = NULL;
+ oatDataFlowAnalysisDispatcher(cUnit, setDominators,
+ kReachableNodes,
+ false /* isIterative */);
- /* For testing, compute sets using alternate mechanism */
- if (cUnit->enableDebug & (1 << kDebugVerifyDataflow)) {
- // Use alternate mechanism to compute dominators for comparison
- oatDataFlowAnalysisDispatcher(cUnit, slowComputeBlockDominators,
- kPreOrderDFSTraversal,
- true /* isIterative */);
+ oatDataFlowAnalysisDispatcher(cUnit, computeBlockDominators,
+ kReversePostOrderTraversal,
+ false /* isIterative */);
- oatDataFlowAnalysisDispatcher(cUnit, slowComputeBlockIDom,
- kReachableNodes,
- false /* isIterative */);
- }
+ /*
+ * Now go ahead and compute the post order traversal based on the
+ * iDominated sets.
+ */
+ if (cUnit->domPostOrderTraversal.elemList == NULL) {
+ oatInitGrowableList(cUnit, &cUnit->domPostOrderTraversal,
+ numReachableBlocks, kListDomPostOrderTraversal);
+ } else {
+ cUnit->domPostOrderTraversal.numUsed = 0;
+ }
- oatDataFlowAnalysisDispatcher(cUnit, setDominators,
- kReachableNodes,
- false /* isIterative */);
+ computeDomPostOrderTraversal(cUnit, cUnit->entryBlock);
+ DCHECK_EQ(cUnit->domPostOrderTraversal.numUsed,
+ (unsigned) cUnit->numReachableBlocks);
- oatDataFlowAnalysisDispatcher(cUnit, computeBlockDominators,
- kReversePostOrderTraversal,
- false /* isIterative */);
-
- /*
- * Now go ahead and compute the post order traversal based on the
- * iDominated sets.
- */
- if (cUnit->domPostOrderTraversal.elemList == NULL) {
- oatInitGrowableList(cUnit, &cUnit->domPostOrderTraversal,
- numReachableBlocks, kListDomPostOrderTraversal);
- } else {
- cUnit->domPostOrderTraversal.numUsed = 0;
- }
-
- computeDomPostOrderTraversal(cUnit, cUnit->entryBlock);
- DCHECK_EQ(cUnit->domPostOrderTraversal.numUsed,
- (unsigned) cUnit->numReachableBlocks);
-
- /* Now compute the dominance frontier for each block */
- oatDataFlowAnalysisDispatcher(cUnit, computeDominanceFrontier,
- kPostOrderDOMTraversal,
- false /* isIterative */);
+ /* Now compute the dominance frontier for each block */
+ oatDataFlowAnalysisDispatcher(cUnit, computeDominanceFrontier,
+ kPostOrderDOMTraversal,
+ false /* isIterative */);
}
/*
@@ -528,20 +525,20 @@
* This is probably not general enough to be placed in BitVector.[ch].
*/
void computeSuccLiveIn(ArenaBitVector* dest,
- const ArenaBitVector* src1,
- const ArenaBitVector* src2)
+ 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";
- }
+ 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];
- }
+ unsigned int idx;
+ for (idx = 0; idx < dest->storageSize; idx++) {
+ dest->storage[idx] |= src1->storage[idx] & ~src2->storage[idx];
+ }
}
/*
@@ -551,121 +548,120 @@
*/
bool computeBlockLiveIns(CompilationUnit* cUnit, BasicBlock* bb)
{
- ArenaBitVector* tempDalvikRegisterV = cUnit->tempDalvikRegisterV;
+ 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)
+ 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,
- bb->fallThrough->dataFlowInfo->liveInV,
+ succBB->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;
+ }
+ 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 */
void insertPhiNodes(CompilationUnit* cUnit)
{
- int dalvikReg;
- const GrowableList* blockList = &cUnit->blockList;
- ArenaBitVector* phiBlocks =
- oatAllocBitVector(cUnit, cUnit->numBlocks, false, kBitMapPhi);
- ArenaBitVector* tmpBlocks =
- oatAllocBitVector(cUnit, cUnit->numBlocks, false, kBitMapTmpBlocks);
- ArenaBitVector* inputBlocks =
- oatAllocBitVector(cUnit, cUnit->numBlocks, false, kBitMapInputBlocks);
+ int dalvikReg;
+ const GrowableList* blockList = &cUnit->blockList;
+ ArenaBitVector* phiBlocks =
+ oatAllocBitVector(cUnit, cUnit->numBlocks, false, kBitMapPhi);
+ ArenaBitVector* tmpBlocks =
+ oatAllocBitVector(cUnit, cUnit->numBlocks, false, kBitMapTmpBlocks);
+ ArenaBitVector* inputBlocks =
+ oatAllocBitVector(cUnit, cUnit->numBlocks, false, kBitMapInputBlocks);
- cUnit->tempDalvikRegisterV =
- oatAllocBitVector(cUnit, cUnit->numDalvikRegisters, false,
- kBitMapRegisterV);
+ cUnit->tempDalvikRegisterV =
+ oatAllocBitVector(cUnit, cUnit->numDalvikRegisters, false,
+ kBitMapRegisterV);
- oatDataFlowAnalysisDispatcher(cUnit, computeBlockLiveIns,
- kPostOrderDFSTraversal,
- true /* isIterative */);
+ oatDataFlowAnalysisDispatcher(cUnit, computeBlockLiveIns,
+ kPostOrderDFSTraversal, true /* isIterative */);
- /* Iterate through each Dalvik register */
- for (dalvikReg = 0; dalvikReg < cUnit->numDalvikRegisters; dalvikReg++) {
- bool change;
- ArenaBitVectorIterator iterator;
+ /* Iterate through each Dalvik register */
+ for (dalvikReg = 0; dalvikReg < cUnit->numDalvikRegisters; dalvikReg++) {
+ bool change;
+ ArenaBitVectorIterator iterator;
- oatCopyBitVector(inputBlocks, cUnit->defBlockMatrix[dalvikReg]);
- oatClearAllBits(phiBlocks);
+ oatCopyBitVector(inputBlocks, cUnit->defBlockMatrix[dalvikReg]);
+ oatClearAllBits(phiBlocks);
- /* Calculate the phi blocks for each Dalvik register */
- do {
- change = false;
- oatClearAllBits(tmpBlocks);
- oatBitVectorIteratorInit(inputBlocks, &iterator);
+ /* 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);
+ while (true) {
+ int idx = oatBitVectorIteratorNext(&iterator);
+ if (idx == -1) break;
+ BasicBlock* defBB =
+ (BasicBlock* ) oatGrowableListGetElement(blockList, idx);
- /* Merge the dominance frontier to tmpBlocks */
- //TUNING: hot call to oatUnifyBitVectors
- if (defBB->domFrontier != NULL) {
- 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(cUnit, sizeof(MIR), true, kAllocDFInfo);
- phi->dalvikInsn.opcode = (Instruction::Code)kMirOpPhi;
- phi->dalvikInsn.vA = dalvikReg;
- phi->offset = phiBB->startOffset;
- phi->meta.phiNext = cUnit->phiList;
- cUnit->phiList = phi;
- oatPrependMIR(phiBB, phi);
+ /* Merge the dominance frontier to tmpBlocks */
+ //TUNING: hot call to oatUnifyBitVectors
+ if (defBB->domFrontier != NULL) {
+ 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(cUnit, sizeof(MIR), true, kAllocDFInfo);
+ phi->dalvikInsn.opcode = (Instruction::Code)kMirOpPhi;
+ phi->dalvikInsn.vA = dalvikReg;
+ phi->offset = phiBB->startOffset;
+ phi->meta.phiNext = cUnit->phiList;
+ cUnit->phiList = phi;
+ oatPrependMIR(phiBB, phi);
}
+ }
}
/*
@@ -674,139 +670,136 @@
*/
bool insertPhiNodeOperands(CompilationUnit* cUnit, BasicBlock* bb)
{
- ArenaBitVector* ssaRegV = cUnit->tempSSARegisterV;
- GrowableListIterator iter;
- MIR *mir;
+ ArenaBitVector* ssaRegV = cUnit->tempSSARegisterV;
+ GrowableListIterator iter;
+ MIR *mir;
- /* Phi nodes are at the beginning of each block */
- for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
- if (mir->dalvikInsn.opcode != (Instruction::Code)kMirOpPhi)
- return true;
- int ssaReg = mir->ssaRep->defs[0];
- DCHECK_GE(ssaReg, 0); // Shouldn't see compiler temps here
- int vReg = SRegToVReg(cUnit, ssaReg);
+ /* Phi nodes are at the beginning of each block */
+ for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
+ if (mir->dalvikInsn.opcode != (Instruction::Code)kMirOpPhi)
+ return true;
+ int ssaReg = mir->ssaRep->defs[0];
+ DCHECK_GE(ssaReg, 0); // Shouldn't see compiler temps here
+ int vReg = SRegToVReg(cUnit, ssaReg);
- oatClearAllBits(ssaRegV);
+ oatClearAllBits(ssaRegV);
- /* Iterate through the predecessors */
- oatGrowableListIteratorInit(bb->predecessors, &iter);
- while (true) {
- BasicBlock* predBB =
- (BasicBlock*)oatGrowableListIteratorNext(&iter);
- if (!predBB) break;
- int ssaReg =
- predBB->dataFlowInfo->vRegToSSAMap[vReg];
- oatSetBit(cUnit, 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(cUnit, sizeof(int) * numUses, false, kAllocDFInfo);
- mir->ssaRep->fpUse =
- (bool *) oatNew(cUnit, sizeof(bool) * numUses, true, kAllocDFInfo);
-
- 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;
- }
+ /* Iterate through the predecessors */
+ oatGrowableListIteratorInit(bb->predecessors, &iter);
+ while (true) {
+ BasicBlock* predBB =
+ (BasicBlock*)oatGrowableListIteratorNext(&iter);
+ if (!predBB) break;
+ int ssaReg = predBB->dataFlowInfo->vRegToSSAMap[vReg];
+ oatSetBit(cUnit, ssaRegV, ssaReg);
}
- return true;
+ /* Count the number of SSA registers for a Dalvik register */
+ int numUses = oatCountSetBits(ssaRegV);
+ mir->ssaRep->numUses = numUses;
+ mir->ssaRep->uses =
+ (int *) oatNew(cUnit, sizeof(int) * numUses, false, kAllocDFInfo);
+ mir->ssaRep->fpUse =
+ (bool *) oatNew(cUnit, sizeof(bool) * numUses, true, kAllocDFInfo);
+
+ 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;
}
void doDFSPreOrderSSARename(CompilationUnit* cUnit, BasicBlock* block)
{
- if (block->visited || block->hidden) return;
- block->visited = true;
+ if (block->visited || block->hidden) return;
+ block->visited = true;
- /* Process this block */
- oatDoSSAConversion(cUnit, block);
- int mapSize = sizeof(int) * cUnit->numDalvikRegisters;
+ /* Process this block */
+ oatDoSSAConversion(cUnit, block);
+ int mapSize = sizeof(int) * cUnit->numDalvikRegisters;
- /* Save SSA map snapshot */
- int* savedSSAMap = (int*)oatNew(cUnit, mapSize, false,
- kAllocDalvikToSSAMap);
- memcpy(savedSSAMap, cUnit->vRegToSSAMap, mapSize);
+ /* Save SSA map snapshot */
+ int* savedSSAMap = (int*)oatNew(cUnit, mapSize, false,
+ kAllocDalvikToSSAMap);
+ memcpy(savedSSAMap, cUnit->vRegToSSAMap, mapSize);
- if (block->fallThrough) {
- doDFSPreOrderSSARename(cUnit, block->fallThrough);
- /* Restore SSA map snapshot */
- memcpy(cUnit->vRegToSSAMap, savedSSAMap, mapSize);
+ if (block->fallThrough) {
+ doDFSPreOrderSSARename(cUnit, block->fallThrough);
+ /* Restore SSA map snapshot */
+ memcpy(cUnit->vRegToSSAMap, savedSSAMap, mapSize);
+ }
+ if (block->taken) {
+ doDFSPreOrderSSARename(cUnit, block->taken);
+ /* Restore SSA map snapshot */
+ memcpy(cUnit->vRegToSSAMap, savedSSAMap, mapSize);
+ }
+ 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;
+ doDFSPreOrderSSARename(cUnit, succBB);
+ /* Restore SSA map snapshot */
+ memcpy(cUnit->vRegToSSAMap, savedSSAMap, mapSize);
}
- if (block->taken) {
- doDFSPreOrderSSARename(cUnit, block->taken);
- /* Restore SSA map snapshot */
- memcpy(cUnit->vRegToSSAMap, savedSSAMap, mapSize);
- }
- 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;
- doDFSPreOrderSSARename(cUnit, succBB);
- /* Restore SSA map snapshot */
- memcpy(cUnit->vRegToSSAMap, savedSSAMap, mapSize);
- }
- }
- cUnit->vRegToSSAMap = savedSSAMap;
- return;
+ }
+ cUnit->vRegToSSAMap = savedSSAMap;
+ return;
}
/* Perform SSA transformation for the whole method */
void oatMethodSSATransformation(CompilationUnit* cUnit)
{
- /* Compute the DFS order */
- computeDFSOrders(cUnit);
+ /* Compute the DFS order */
+ computeDFSOrders(cUnit);
- if (!cUnit->disableDataflow) {
- /* Compute the dominator info */
- computeDominators(cUnit);
- }
+ if (!cUnit->disableDataflow) {
+ /* Compute the dominator info */
+ computeDominators(cUnit);
+ }
- /* Allocate data structures in preparation for SSA conversion */
- oatInitializeSSAConversion(cUnit);
+ /* Allocate data structures in preparation for SSA conversion */
+ oatInitializeSSAConversion(cUnit);
- if (!cUnit->disableDataflow) {
- /* Find out the "Dalvik reg def x block" relation */
- computeDefBlockMatrix(cUnit);
+ if (!cUnit->disableDataflow) {
+ /* Find out the "Dalvik reg def x block" relation */
+ computeDefBlockMatrix(cUnit);
- /* Insert phi nodes to dominance frontiers for all variables */
- insertPhiNodes(cUnit);
- }
+ /* Insert phi nodes to dominance frontiers for all variables */
+ insertPhiNodes(cUnit);
+ }
- /* Rename register names by local defs and phi nodes */
- oatDataFlowAnalysisDispatcher(cUnit, oatClearVisitedFlag,
- kAllNodes,
- false /* isIterative */);
- doDFSPreOrderSSARename(cUnit, cUnit->entryBlock);
+ /* Rename register names by local defs and phi nodes */
+ oatDataFlowAnalysisDispatcher(cUnit, oatClearVisitedFlag,
+ kAllNodes, false /* isIterative */);
+ doDFSPreOrderSSARename(cUnit, cUnit->entryBlock);
- if (!cUnit->disableDataflow) {
- /*
- * Shared temp bit vector used by each block to count the number of defs
- * from all the predecessor blocks.
- */
- cUnit->tempSSARegisterV = oatAllocBitVector(cUnit, cUnit->numSSARegs,
- false, kBitMapTempSSARegisterV);
+ if (!cUnit->disableDataflow) {
+ /*
+ * Shared temp bit vector used by each block to count the number of defs
+ * from all the predecessor blocks.
+ */
+ cUnit->tempSSARegisterV = oatAllocBitVector(cUnit, cUnit->numSSARegs,
+ false, kBitMapTempSSARegisterV);
- /* Insert phi-operands with latest SSA names from predecessor blocks */
- oatDataFlowAnalysisDispatcher(cUnit, insertPhiNodeOperands,
- kReachableNodes,
- false /* isIterative */);
- }
+ /* Insert phi-operands with latest SSA names from predecessor blocks */
+ oatDataFlowAnalysisDispatcher(cUnit, insertPhiNodeOperands,
+ kReachableNodes, false /* isIterative */);
+ }
}
} // namespace art