diff options
Diffstat (limited to 'vm/compiler/MethodSSATransformation.c')
| -rw-r--r-- | vm/compiler/MethodSSATransformation.c | 562 |
1 files changed, 562 insertions, 0 deletions
diff --git a/vm/compiler/MethodSSATransformation.c b/vm/compiler/MethodSSATransformation.c new file mode 100644 index 000000000..48d5b5ce9 --- /dev/null +++ b/vm/compiler/MethodSSATransformation.c @@ -0,0 +1,562 @@ +/* + * 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) { + SuccessorBlockInfo *successorBlockInfo = + (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&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 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) { + SuccessorBlockInfo *successorBlockInfo = + (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator); + if (successorBlockInfo == NULL) break; + BasicBlock *succBB = successorBlockInfo->block; + 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) { + SuccessorBlockInfo *successorBlockInfo = + (SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator); + if (successorBlockInfo == NULL) break; + BasicBlock *succBB = successorBlockInfo->block; + 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 */); +} |