path: root/vm/compiler/SSATransformation.cpp

/*
 * 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) {
        LOGE("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;
}