/*
* 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 || block->hidden) return;
block->visited = true;
/* Enqueue the block id */
dvmInsertGrowableList(&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;
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 or reset the DFS order list */
if (cUnit->dfsOrder.elemList == NULL) {
dvmInitGrowableList(&cUnit->dfsOrder, cUnit->numBlocks);
} else {
/* Just reset the used length on the counter */
cUnit->dfsOrder.numUsed = 0;
}
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 */);
if (cUnit->jitMode == kJitMethod) {
/*
* 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;
}
}
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) {
dvmSetBit(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;
dvmGrowableListIteratorInit(&bb->successorBlockList.blocks,
&iterator);
while (true) {
SuccessorBlockInfo *successorBlockInfo =
(SuccessorBlockInfo *) dvmGrowableListIteratorNext(&iterator);
if (successorBlockInfo == NULL) break;
BasicBlock *succBB = successorBlockInfo->block;
checkForDominanceFrontier(bb, succBB);
}
}
/* 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);
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 = dvmCompilerAllocBitVector(numTotalBlocks,
false /* expandable */);
bb->iDominated = dvmCompilerAllocBitVector(numTotalBlocks,
false /* expandable */);
bb->domFrontier = dvmCompilerAllocBitVector(numTotalBlocks,
false /* expandable */);
} else {
dvmClearAllBits(bb->dominators);
dvmClearAllBits(bb->iDominated);
dvmClearAllBits(bb->domFrontier);
}
/* 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);
if (cUnit->tempBlockV == NULL) {
cUnit->tempBlockV = dvmCompilerAllocBitVector(numTotalBlocks,
false /* expandable */);
} else {
dvmClearAllBits(cUnit->tempBlockV);
}
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.
*/
if (cUnit->domPostOrderTraversal.elemList == NULL) {
dvmInitGrowableList(&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 */
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) {
ALOGE("Incompatible set properties");
dvmAbort();
}
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)
{
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->numBlocks, false);
BitVector *tmpBlocks =
dvmCompilerAllocBitVector(cUnit->numBlocks, false);
BitVector *inputBlocks =
dvmCompilerAllocBitVector(cUnit->numBlocks, 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 = (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 != (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, true);
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 */);
}
/* Build a loop. Return true if a loop structure is successfully identified. */
bool dvmCompilerBuildLoop(CompilationUnit *cUnit)
{
/* Compute the DFS order */
computeDFSOrder(cUnit);
/* Compute the dominator info */
computeDominators(cUnit);
/* Loop structure not recognized/supported - return false */
if (dvmCompilerFilterLoopBlocks(cUnit) == false)
return false;
/* Re-compute the DFS order just for the loop */
computeDFSOrder(cUnit);
/* Re-compute the dominator info just for the loop */
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 */);
if (gDvmJit.receivedSIGUSR2 || gDvmJit.printMe) {
dvmDumpCFG(cUnit, "/sdcard/cfg/");
}
return true;
}