ssa_transformation.cc revision f0cde549bed96e16401a347a4511b59130c61e84
167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Copyright (C) 2011 The Android Open Source Project 367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * 467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Licensed under the Apache License, Version 2.0 (the "License"); 567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * you may not use this file except in compliance with the License. 667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * You may obtain a copy of the License at 767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * 867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * http://www.apache.org/licenses/LICENSE-2.0 967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * 1067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Unless required by applicable law or agreed to in writing, software 1167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * distributed under the License is distributed on an "AS IS" BASIS, 1267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * See the License for the specific language governing permissions and 1467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * limitations under the License. 1567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 1667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 1767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee#include "Dalvik.h" 1867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee#include "Dataflow.h" 1967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 2067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Enter the node to the dfsOrder list then visit its successors */ 2167bf885d62b1473c833bece1c9e0bb624e6ba391buzbeestatic void recordDFSPreOrder(CompilationUnit* cUnit, BasicBlock* block) 2267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 2367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 2467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (block->visited || block->hidden) return; 2567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee block->visited = true; 2667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 2767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Enqueue the block id */ 2867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatInsertGrowableList(&cUnit->dfsOrder, block->id); 2967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 3067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (block->fallThrough) recordDFSPreOrder(cUnit, block->fallThrough); 3167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (block->taken) recordDFSPreOrder(cUnit, block->taken); 3267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (block->successorBlockList.blockListType != kNotUsed) { 3367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee GrowableListIterator iterator; 3467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatGrowableListIteratorInit(&block->successorBlockList.blocks, 3567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee &iterator); 3667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee while (true) { 3767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee SuccessorBlockInfo *successorBlockInfo = 3867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee (SuccessorBlockInfo *) oatGrowableListIteratorNext(&iterator); 3967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (successorBlockInfo == NULL) break; 4067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee BasicBlock* succBB = successorBlockInfo->block; 4167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee recordDFSPreOrder(cUnit, succBB); 4267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 4367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 4467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee return; 4567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 4667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 4767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Sort the blocks by the Depth-First-Search pre-order */ 4867bf885d62b1473c833bece1c9e0bb624e6ba391buzbeestatic void computeDFSOrder(CompilationUnit* cUnit) 4967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 5067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Initialize or reset the DFS order list */ 5167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (cUnit->dfsOrder.elemList == NULL) { 5267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatInitGrowableList(&cUnit->dfsOrder, cUnit->numBlocks); 5367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } else { 5467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Just reset the used length on the counter */ 5567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee cUnit->dfsOrder.numUsed = 0; 5667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 5767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 5867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatDataFlowAnalysisDispatcher(cUnit, oatClearVisitedFlag, 5967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee kAllNodes, 6067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee false /* isIterative */); 6167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 6267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee recordDFSPreOrder(cUnit, cUnit->entryBlock); 6367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee cUnit->numReachableBlocks = cUnit->dfsOrder.numUsed; 6467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 6567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 6667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 6767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Mark block bit on the per-Dalvik register vector to denote that Dalvik 6867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * register idx is defined in BasicBlock bb. 6967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 7067bf885d62b1473c833bece1c9e0bb624e6ba391buzbeestatic bool fillDefBlockMatrix(CompilationUnit* cUnit, BasicBlock* bb) 7167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 7267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (bb->dataFlowInfo == NULL) return false; 7367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 7467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee ArenaBitVectorIterator iterator; 7567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 7667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatBitVectorIteratorInit(bb->dataFlowInfo->defV, &iterator); 7767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee while (true) { 7867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int idx = oatBitVectorIteratorNext(&iterator); 7967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (idx == -1) break; 8067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Block bb defines register idx */ 8167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatSetBit(cUnit->defBlockMatrix[idx], bb->id); 8267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 8367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee return true; 8467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 8567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 8667bf885d62b1473c833bece1c9e0bb624e6ba391buzbeestatic void computeDefBlockMatrix(CompilationUnit* cUnit) 8767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 8867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int numRegisters = cUnit->numDalvikRegisters; 8967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Allocate numDalvikRegisters bit vector pointers */ 9067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee cUnit->defBlockMatrix = (ArenaBitVector **) 9167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatNew(sizeof(ArenaBitVector *) * numRegisters, true); 9267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int i; 9367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 9467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Initialize numRegister vectors with numBlocks bits each */ 9567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee for (i = 0; i < numRegisters; i++) { 9667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee cUnit->defBlockMatrix[i] = oatAllocBitVector(cUnit->numBlocks, 9767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee false); 9867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 9967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatDataFlowAnalysisDispatcher(cUnit, oatFindLocalLiveIn, 10067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee kAllNodes, 10167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee false /* isIterative */); 10267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatDataFlowAnalysisDispatcher(cUnit, fillDefBlockMatrix, 10367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee kAllNodes, 10467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee false /* isIterative */); 10567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 10667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* 10767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Also set the incoming parameters as defs in the entry block. 10867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Only need to handle the parameters for the outer method. 10967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 1100cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers int inReg = cUnit->method->NumRegisters() - cUnit->method->NumIns(); 1110cfe1fb7060576d047f7f894fc0d8b87de84fcabIan Rogers for (; inReg < cUnit->method->NumRegisters(); inReg++) { 11267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatSetBit(cUnit->defBlockMatrix[inReg], 11367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee cUnit->entryBlock->id); 11467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 11567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 11667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 11767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Compute the post-order traversal of the CFG */ 11867bf885d62b1473c833bece1c9e0bb624e6ba391buzbeestatic void computeDomPostOrderTraversal(CompilationUnit* cUnit, BasicBlock* bb) 11967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 12067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee ArenaBitVectorIterator bvIterator; 12167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatBitVectorIteratorInit(bb->iDominated, &bvIterator); 12267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee GrowableList* blockList = &cUnit->blockList; 12367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 12467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Iterate through the dominated blocks first */ 12567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee while (true) { 12667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int bbIdx = oatBitVectorIteratorNext(&bvIterator); 12767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (bbIdx == -1) break; 12867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee BasicBlock* dominatedBB = 12967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee (BasicBlock* ) oatGrowableListGetElement(blockList, bbIdx); 13067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee computeDomPostOrderTraversal(cUnit, dominatedBB); 13167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 13267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 13367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Enter the current block id */ 13467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatInsertGrowableList(&cUnit->domPostOrderTraversal, bb->id); 13567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 13667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* hacky loop detection */ 13767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (bb->taken && oatIsBitSet(bb->dominators, bb->taken->id)) { 13867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee cUnit->hasLoop = true; 13967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 14067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 14167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 14267bf885d62b1473c833bece1c9e0bb624e6ba391buzbeestatic void checkForDominanceFrontier(BasicBlock* domBB, 14367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee const BasicBlock* succBB) 14467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 14567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* 14667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * TODO - evaluate whether phi will ever need to be inserted into exit 14767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * blocks. 14867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 14967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (succBB->iDom != domBB && 15067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee succBB->blockType == kDalvikByteCode && 15167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee succBB->hidden == false) { 15267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatSetBit(domBB->domFrontier, succBB->id); 15367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 15467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 15567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 15667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Worker function to compute the dominance frontier */ 15767bf885d62b1473c833bece1c9e0bb624e6ba391buzbeestatic bool computeDominanceFrontier(CompilationUnit* cUnit, BasicBlock* bb) 15867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 15967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee GrowableList* blockList = &cUnit->blockList; 16067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 16167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Calculate DF_local */ 16267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (bb->taken) { 16367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee checkForDominanceFrontier(bb, bb->taken); 16467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 16567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (bb->fallThrough) { 16667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee checkForDominanceFrontier(bb, bb->fallThrough); 16767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 16867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (bb->successorBlockList.blockListType != kNotUsed) { 16967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee GrowableListIterator iterator; 17067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatGrowableListIteratorInit(&bb->successorBlockList.blocks, 17167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee &iterator); 17267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee while (true) { 17367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee SuccessorBlockInfo *successorBlockInfo = 17467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee (SuccessorBlockInfo *) oatGrowableListIteratorNext(&iterator); 17567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (successorBlockInfo == NULL) break; 17667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee BasicBlock* succBB = successorBlockInfo->block; 17767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee checkForDominanceFrontier(bb, succBB); 17867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 17967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 18067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 18167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Calculate DF_up */ 18267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee ArenaBitVectorIterator bvIterator; 18367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatBitVectorIteratorInit(bb->iDominated, &bvIterator); 18467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee while (true) { 18567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int dominatedIdx = oatBitVectorIteratorNext(&bvIterator); 18667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (dominatedIdx == -1) break; 18767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee BasicBlock* dominatedBB = (BasicBlock* ) 18867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatGrowableListGetElement(blockList, dominatedIdx); 18967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee ArenaBitVectorIterator dfIterator; 19067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatBitVectorIteratorInit(dominatedBB->domFrontier, &dfIterator); 19167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee while (true) { 19267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int dfUpIdx = oatBitVectorIteratorNext(&dfIterator); 19367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (dfUpIdx == -1) break; 19467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee BasicBlock* dfUpBlock = (BasicBlock* ) 19567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatGrowableListGetElement(blockList, dfUpIdx); 19667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee checkForDominanceFrontier(bb, dfUpBlock); 19767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 19867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 19967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 20067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee return true; 20167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 20267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 20367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Worker function for initializing domination-related data structures */ 20467bf885d62b1473c833bece1c9e0bb624e6ba391buzbeestatic bool initializeDominationInfo(CompilationUnit* cUnit, BasicBlock* bb) 20567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 20667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int numTotalBlocks = cUnit->blockList.numUsed; 20767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 20867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (bb->dominators == NULL ) { 20967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee bb->dominators = oatAllocBitVector(numTotalBlocks, 21067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee false /* expandable */); 21167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee bb->iDominated = oatAllocBitVector(numTotalBlocks, 21267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee false /* expandable */); 21367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee bb->domFrontier = oatAllocBitVector(numTotalBlocks, 21467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee false /* expandable */); 21567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } else { 21667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatClearAllBits(bb->dominators); 21767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatClearAllBits(bb->iDominated); 21867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatClearAllBits(bb->domFrontier); 21967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 22067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Set all bits in the dominator vector */ 22167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatSetInitialBits(bb->dominators, numTotalBlocks); 22267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 22367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee return true; 22467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 22567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 22667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Worker function to compute each block's dominators */ 22767bf885d62b1473c833bece1c9e0bb624e6ba391buzbeestatic bool computeBlockDominators(CompilationUnit* cUnit, BasicBlock* bb) 22867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 22967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee GrowableList* blockList = &cUnit->blockList; 23067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int numTotalBlocks = blockList->numUsed; 23167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee ArenaBitVector* tempBlockV = cUnit->tempBlockV; 23267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee ArenaBitVectorIterator bvIterator; 23367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 23467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* 23567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * The dominator of the entry block has been preset to itself and we need 23667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * to skip the calculation here. 23767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 23867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (bb == cUnit->entryBlock) return false; 23967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 24067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatSetInitialBits(tempBlockV, numTotalBlocks); 24167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 24267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Iterate through the predecessors */ 24367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatBitVectorIteratorInit(bb->predecessors, &bvIterator); 24467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee while (true) { 24567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int predIdx = oatBitVectorIteratorNext(&bvIterator); 24667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (predIdx == -1) break; 24767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee BasicBlock* predBB = (BasicBlock* ) oatGrowableListGetElement( 24867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee blockList, predIdx); 24967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* tempBlockV = tempBlockV ^ dominators */ 25067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatIntersectBitVectors(tempBlockV, tempBlockV, predBB->dominators); 25167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 25267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatSetBit(tempBlockV, bb->id); 25367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (oatCompareBitVectors(tempBlockV, bb->dominators)) { 25467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatCopyBitVector(bb->dominators, tempBlockV); 25567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee return true; 25667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 25767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee return false; 25867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 25967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 26067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Worker function to compute the idom */ 26167bf885d62b1473c833bece1c9e0bb624e6ba391buzbeestatic bool computeImmediateDominator(CompilationUnit* cUnit, BasicBlock* bb) 26267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 26367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee GrowableList* blockList = &cUnit->blockList; 26467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee ArenaBitVector* tempBlockV = cUnit->tempBlockV; 26567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee ArenaBitVectorIterator bvIterator; 26667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee BasicBlock* iDom; 26767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 26867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (bb == cUnit->entryBlock) return false; 26967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 27067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatCopyBitVector(tempBlockV, bb->dominators); 27167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatClearBit(tempBlockV, bb->id); 27267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatBitVectorIteratorInit(tempBlockV, &bvIterator); 27367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 27467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Should not see any dead block */ 27567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee assert(oatCountSetBits(tempBlockV) != 0); 27667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (oatCountSetBits(tempBlockV) == 1) { 27767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee iDom = (BasicBlock* ) oatGrowableListGetElement( 27867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee blockList, oatBitVectorIteratorNext(&bvIterator)); 27967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee bb->iDom = iDom; 28067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } else { 28167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int iDomIdx = oatBitVectorIteratorNext(&bvIterator); 28267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee assert(iDomIdx != -1); 28367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee while (true) { 28467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int nextDom = oatBitVectorIteratorNext(&bvIterator); 28567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (nextDom == -1) break; 28667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee BasicBlock* nextDomBB = (BasicBlock* ) 28767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatGrowableListGetElement(blockList, nextDom); 28867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* iDom dominates nextDom - set new iDom */ 28967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (oatIsBitSet(nextDomBB->dominators, iDomIdx)) { 29067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee iDomIdx = nextDom; 29167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 29267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 29367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 29467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee iDom = (BasicBlock* ) oatGrowableListGetElement(blockList, iDomIdx); 29567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Set the immediate dominator block for bb */ 29667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee bb->iDom = iDom; 29767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 29867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Add bb to the iDominated set of the immediate dominator block */ 29967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatSetBit(iDom->iDominated, bb->id); 30067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee return true; 30167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 30267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 30367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Compute dominators, immediate dominator, and dominance fronter */ 30467bf885d62b1473c833bece1c9e0bb624e6ba391buzbeestatic void computeDominators(CompilationUnit* cUnit) 30567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 30667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int numReachableBlocks = cUnit->numReachableBlocks; 30767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int numTotalBlocks = cUnit->blockList.numUsed; 30867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 30967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Initialize domination-related data structures */ 31067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatDataFlowAnalysisDispatcher(cUnit, initializeDominationInfo, 31167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee kReachableNodes, 31267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee false /* isIterative */); 31367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 31467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Set the dominator for the root node */ 31567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatClearAllBits(cUnit->entryBlock->dominators); 31667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatSetBit(cUnit->entryBlock->dominators, cUnit->entryBlock->id); 31767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 31867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (cUnit->tempBlockV == NULL) { 31967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee cUnit->tempBlockV = oatAllocBitVector(numTotalBlocks, 32067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee false /* expandable */); 32167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } else { 32267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatClearAllBits(cUnit->tempBlockV); 32367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 32467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatDataFlowAnalysisDispatcher(cUnit, computeBlockDominators, 32567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee kPreOrderDFSTraversal, 32667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee true /* isIterative */); 32767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 32867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee cUnit->entryBlock->iDom = NULL; 32967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatDataFlowAnalysisDispatcher(cUnit, computeImmediateDominator, 33067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee kReachableNodes, 33167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee false /* isIterative */); 33267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 33367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* 33467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Now go ahead and compute the post order traversal based on the 33567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * iDominated sets. 33667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 33767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (cUnit->domPostOrderTraversal.elemList == NULL) { 33867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatInitGrowableList(&cUnit->domPostOrderTraversal, numReachableBlocks); 33967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } else { 34067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee cUnit->domPostOrderTraversal.numUsed = 0; 34167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 34267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 34367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee computeDomPostOrderTraversal(cUnit, cUnit->entryBlock); 34467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee assert(cUnit->domPostOrderTraversal.numUsed == 34567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee (unsigned) cUnit->numReachableBlocks); 34667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 34767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Now compute the dominance frontier for each block */ 34867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatDataFlowAnalysisDispatcher(cUnit, computeDominanceFrontier, 34967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee kPostOrderDOMTraversal, 35067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee false /* isIterative */); 35167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 35267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 35367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 35467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Perform dest U= src1 ^ ~src2 35567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * This is probably not general enough to be placed in BitVector.[ch]. 35667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 35767bf885d62b1473c833bece1c9e0bb624e6ba391buzbeestatic void computeSuccLiveIn(ArenaBitVector* dest, 35867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee const ArenaBitVector* src1, 35967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee const ArenaBitVector* src2) 36067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 36167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (dest->storageSize != src1->storageSize || 36267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee dest->storageSize != src2->storageSize || 36367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee dest->expandable != src1->expandable || 36467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee dest->expandable != src2->expandable) { 36567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee LOG(FATAL) << "Incompatible set properties"; 36667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 36767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 36867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee unsigned int idx; 36967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee for (idx = 0; idx < dest->storageSize; idx++) { 37067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee dest->storage[idx] |= src1->storage[idx] & ~src2->storage[idx]; 37167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 37267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 37367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 37467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 37567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Iterate through all successor blocks and propagate up the live-in sets. 37667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * The calculated result is used for phi-node pruning - where we only need to 37767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * insert a phi node if the variable is live-in to the block. 37867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 37967bf885d62b1473c833bece1c9e0bb624e6ba391buzbeestatic bool computeBlockLiveIns(CompilationUnit* cUnit, BasicBlock* bb) 38067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 38167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee ArenaBitVector* tempDalvikRegisterV = cUnit->tempDalvikRegisterV; 38267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 38367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (bb->dataFlowInfo == NULL) return false; 38467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatCopyBitVector(tempDalvikRegisterV, bb->dataFlowInfo->liveInV); 38567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (bb->taken && bb->taken->dataFlowInfo) 38667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee computeSuccLiveIn(tempDalvikRegisterV, bb->taken->dataFlowInfo->liveInV, 38767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee bb->dataFlowInfo->defV); 38867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (bb->fallThrough && bb->fallThrough->dataFlowInfo) 38967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee computeSuccLiveIn(tempDalvikRegisterV, 39067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee bb->fallThrough->dataFlowInfo->liveInV, 39167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee bb->dataFlowInfo->defV); 39267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (bb->successorBlockList.blockListType != kNotUsed) { 39367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee GrowableListIterator iterator; 39467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatGrowableListIteratorInit(&bb->successorBlockList.blocks, 39567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee &iterator); 39667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee while (true) { 39767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee SuccessorBlockInfo *successorBlockInfo = 39867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee (SuccessorBlockInfo *) oatGrowableListIteratorNext(&iterator); 39967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (successorBlockInfo == NULL) break; 40067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee BasicBlock* succBB = successorBlockInfo->block; 40167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (succBB->dataFlowInfo) { 40267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee computeSuccLiveIn(tempDalvikRegisterV, 40367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee succBB->dataFlowInfo->liveInV, 40467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee bb->dataFlowInfo->defV); 40567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 40667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 40767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 40867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (oatCompareBitVectors(tempDalvikRegisterV, bb->dataFlowInfo->liveInV)) { 40967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatCopyBitVector(bb->dataFlowInfo->liveInV, tempDalvikRegisterV); 41067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee return true; 41167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 41267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee return false; 41367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 41467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 41567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Insert phi nodes to for each variable to the dominance frontiers */ 41667bf885d62b1473c833bece1c9e0bb624e6ba391buzbeestatic void insertPhiNodes(CompilationUnit* cUnit) 41767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 41867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int dalvikReg; 41967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee const GrowableList* blockList = &cUnit->blockList; 42067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee ArenaBitVector* phiBlocks = 42167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatAllocBitVector(cUnit->numBlocks, false); 42267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee ArenaBitVector* tmpBlocks = 42367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatAllocBitVector(cUnit->numBlocks, false); 42467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee ArenaBitVector* inputBlocks = 42567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatAllocBitVector(cUnit->numBlocks, false); 42667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 42767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee cUnit->tempDalvikRegisterV = 42867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatAllocBitVector(cUnit->numDalvikRegisters, false); 42967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 43067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatDataFlowAnalysisDispatcher(cUnit, computeBlockLiveIns, 43167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee kPostOrderDFSTraversal, 43267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee true /* isIterative */); 43367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 43467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Iterate through each Dalvik register */ 43567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee for (dalvikReg = 0; dalvikReg < cUnit->numDalvikRegisters; dalvikReg++) { 43667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee bool change; 43767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee ArenaBitVectorIterator iterator; 43867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 43967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatCopyBitVector(inputBlocks, cUnit->defBlockMatrix[dalvikReg]); 44067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatClearAllBits(phiBlocks); 44167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 44267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Calculate the phi blocks for each Dalvik register */ 44367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee do { 44467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee change = false; 44567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatClearAllBits(tmpBlocks); 44667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatBitVectorIteratorInit(inputBlocks, &iterator); 44767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 44867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee while (true) { 44967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int idx = oatBitVectorIteratorNext(&iterator); 45067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (idx == -1) break; 45167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee BasicBlock* defBB = 45267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee (BasicBlock* ) oatGrowableListGetElement(blockList, idx); 45367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 45467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Merge the dominance frontier to tmpBlocks */ 45567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatUnifyBitVectors(tmpBlocks, tmpBlocks, defBB->domFrontier); 45667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 45767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (oatCompareBitVectors(phiBlocks, tmpBlocks)) { 45867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee change = true; 45967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatCopyBitVector(phiBlocks, tmpBlocks); 46067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 46167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* 46267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Iterate through the original blocks plus the new ones in 46367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * the dominance frontier. 46467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 46567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatCopyBitVector(inputBlocks, phiBlocks); 46667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatUnifyBitVectors(inputBlocks, inputBlocks, 46767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee cUnit->defBlockMatrix[dalvikReg]); 46867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 46967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } while (change); 47067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 47167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* 47267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Insert a phi node for dalvikReg in the phiBlocks if the Dalvik 47367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * register is in the live-in set. 47467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 47567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatBitVectorIteratorInit(phiBlocks, &iterator); 47667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee while (true) { 47767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int idx = oatBitVectorIteratorNext(&iterator); 47867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (idx == -1) break; 47967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee BasicBlock* phiBB = 48067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee (BasicBlock* ) oatGrowableListGetElement(blockList, idx); 48167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Variable will be clobbered before being used - no need for phi */ 48267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (!oatIsBitSet(phiBB->dataFlowInfo->liveInV, dalvikReg)) continue; 48367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee MIR *phi = (MIR *) oatNew(sizeof(MIR), true); 48467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee phi->dalvikInsn.opcode = (Opcode)kMirOpPhi; 48567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee phi->dalvikInsn.vA = dalvikReg; 48667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee phi->offset = phiBB->startOffset; 48767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatPrependMIR(phiBB, phi); 48867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 48967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 49067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 49167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 49267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* 49367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Worker function to insert phi-operands with latest SSA names from 49467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * predecessor blocks 49567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 49667bf885d62b1473c833bece1c9e0bb624e6ba391buzbeestatic bool insertPhiNodeOperands(CompilationUnit* cUnit, BasicBlock* bb) 49767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 49867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee ArenaBitVector* ssaRegV = cUnit->tempSSARegisterV; 49967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee ArenaBitVectorIterator bvIterator; 50067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee GrowableList* blockList = &cUnit->blockList; 50167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee MIR *mir; 50267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 50367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Phi nodes are at the beginning of each block */ 50467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee for (mir = bb->firstMIRInsn; mir; mir = mir->next) { 50567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (mir->dalvikInsn.opcode != (Opcode)kMirOpPhi) 50667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee return true; 50767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int ssaReg = mir->ssaRep->defs[0]; 50867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int encodedDalvikValue = 50967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee (int) oatGrowableListGetElement(cUnit->ssaToDalvikMap, ssaReg); 51067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int dalvikReg = DECODE_REG(encodedDalvikValue); 51167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 51267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatClearAllBits(ssaRegV); 51367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 51467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Iterate through the predecessors */ 51567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatBitVectorIteratorInit(bb->predecessors, &bvIterator); 51667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee while (true) { 51767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int predIdx = oatBitVectorIteratorNext(&bvIterator); 51867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (predIdx == -1) break; 51967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee BasicBlock* predBB = (BasicBlock* ) oatGrowableListGetElement( 52067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee blockList, predIdx); 52167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int encodedSSAValue = 52267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee predBB->dataFlowInfo->dalvikToSSAMap[dalvikReg]; 52367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int ssaReg = DECODE_REG(encodedSSAValue); 52467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatSetBit(ssaRegV, ssaReg); 52567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 52667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 52767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Count the number of SSA registers for a Dalvik register */ 52867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int numUses = oatCountSetBits(ssaRegV); 52967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee mir->ssaRep->numUses = numUses; 53067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee mir->ssaRep->uses = 53167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee (int *) oatNew(sizeof(int) * numUses, false); 53267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee mir->ssaRep->fpUse = 53367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee (bool *) oatNew(sizeof(bool) * numUses, true); 53467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 53567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee ArenaBitVectorIterator phiIterator; 53667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 53767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatBitVectorIteratorInit(ssaRegV, &phiIterator); 53867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int *usePtr = mir->ssaRep->uses; 53967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 54067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Set the uses array for the phi node */ 54167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee while (true) { 54267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee int ssaRegIdx = oatBitVectorIteratorNext(&phiIterator); 54367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee if (ssaRegIdx == -1) break; 54467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee *usePtr++ = ssaRegIdx; 54567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 54667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee } 54767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 54867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee return true; 54967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 55067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 551f0cde549bed96e16401a347a4511b59130c61e84buzbeestatic void doDFSPreOrderSSARename(CompilationUnit* cUnit, BasicBlock* block) 552f0cde549bed96e16401a347a4511b59130c61e84buzbee{ 553f0cde549bed96e16401a347a4511b59130c61e84buzbee 554f0cde549bed96e16401a347a4511b59130c61e84buzbee if (block->visited || block->hidden) return; 555f0cde549bed96e16401a347a4511b59130c61e84buzbee block->visited = true; 556f0cde549bed96e16401a347a4511b59130c61e84buzbee 557f0cde549bed96e16401a347a4511b59130c61e84buzbee /* Process this block */ 558f0cde549bed96e16401a347a4511b59130c61e84buzbee oatDoSSAConversion(cUnit, block); 559f0cde549bed96e16401a347a4511b59130c61e84buzbee int mapSize = sizeof(int) * cUnit->method->NumRegisters(); 560f0cde549bed96e16401a347a4511b59130c61e84buzbee 561f0cde549bed96e16401a347a4511b59130c61e84buzbee /* Save SSA map snapshot */ 562f0cde549bed96e16401a347a4511b59130c61e84buzbee int* savedSSAMap = (int*)oatNew(mapSize, false); 563f0cde549bed96e16401a347a4511b59130c61e84buzbee memcpy(savedSSAMap, cUnit->dalvikToSSAMap, mapSize); 564f0cde549bed96e16401a347a4511b59130c61e84buzbee 565f0cde549bed96e16401a347a4511b59130c61e84buzbee if (block->fallThrough) { 566f0cde549bed96e16401a347a4511b59130c61e84buzbee doDFSPreOrderSSARename(cUnit, block->fallThrough); 567f0cde549bed96e16401a347a4511b59130c61e84buzbee /* Restore SSA map snapshot */ 568f0cde549bed96e16401a347a4511b59130c61e84buzbee memcpy(cUnit->dalvikToSSAMap, savedSSAMap, mapSize); 569f0cde549bed96e16401a347a4511b59130c61e84buzbee } 570f0cde549bed96e16401a347a4511b59130c61e84buzbee if (block->taken) { 571f0cde549bed96e16401a347a4511b59130c61e84buzbee doDFSPreOrderSSARename(cUnit, block->taken); 572f0cde549bed96e16401a347a4511b59130c61e84buzbee /* Restore SSA map snapshot */ 573f0cde549bed96e16401a347a4511b59130c61e84buzbee memcpy(cUnit->dalvikToSSAMap, savedSSAMap, mapSize); 574f0cde549bed96e16401a347a4511b59130c61e84buzbee } 575f0cde549bed96e16401a347a4511b59130c61e84buzbee if (block->successorBlockList.blockListType != kNotUsed) { 576f0cde549bed96e16401a347a4511b59130c61e84buzbee GrowableListIterator iterator; 577f0cde549bed96e16401a347a4511b59130c61e84buzbee oatGrowableListIteratorInit(&block->successorBlockList.blocks, 578f0cde549bed96e16401a347a4511b59130c61e84buzbee &iterator); 579f0cde549bed96e16401a347a4511b59130c61e84buzbee while (true) { 580f0cde549bed96e16401a347a4511b59130c61e84buzbee SuccessorBlockInfo *successorBlockInfo = 581f0cde549bed96e16401a347a4511b59130c61e84buzbee (SuccessorBlockInfo *) oatGrowableListIteratorNext(&iterator); 582f0cde549bed96e16401a347a4511b59130c61e84buzbee if (successorBlockInfo == NULL) break; 583f0cde549bed96e16401a347a4511b59130c61e84buzbee BasicBlock* succBB = successorBlockInfo->block; 584f0cde549bed96e16401a347a4511b59130c61e84buzbee doDFSPreOrderSSARename(cUnit, succBB); 585f0cde549bed96e16401a347a4511b59130c61e84buzbee /* Restore SSA map snapshot */ 586f0cde549bed96e16401a347a4511b59130c61e84buzbee memcpy(cUnit->dalvikToSSAMap, savedSSAMap, mapSize); 587f0cde549bed96e16401a347a4511b59130c61e84buzbee } 588f0cde549bed96e16401a347a4511b59130c61e84buzbee } 589f0cde549bed96e16401a347a4511b59130c61e84buzbee cUnit->dalvikToSSAMap = savedSSAMap; 590f0cde549bed96e16401a347a4511b59130c61e84buzbee return; 591f0cde549bed96e16401a347a4511b59130c61e84buzbee} 592f0cde549bed96e16401a347a4511b59130c61e84buzbee 59367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee/* Perform SSA transformation for the whole method */ 59467bf885d62b1473c833bece1c9e0bb624e6ba391buzbeevoid oatMethodSSATransformation(CompilationUnit* cUnit) 59567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee{ 59667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Compute the DFS order */ 59767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee computeDFSOrder(cUnit); 59867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 59967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Compute the dominator info */ 60067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee computeDominators(cUnit); 60167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 60267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Allocate data structures in preparation for SSA conversion */ 60367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatInitializeSSAConversion(cUnit); 60467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 60567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Find out the "Dalvik reg def x block" relation */ 60667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee computeDefBlockMatrix(cUnit); 60767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 60867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Insert phi nodes to dominance frontiers for all variables */ 60967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee insertPhiNodes(cUnit); 61067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 61167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Rename register names by local defs and phi nodes */ 612f0cde549bed96e16401a347a4511b59130c61e84buzbee oatDataFlowAnalysisDispatcher(cUnit, oatClearVisitedFlag, 613f0cde549bed96e16401a347a4511b59130c61e84buzbee kAllNodes, 61467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee false /* isIterative */); 615f0cde549bed96e16401a347a4511b59130c61e84buzbee doDFSPreOrderSSARename(cUnit, cUnit->entryBlock); 61667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 61767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* 61867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * Shared temp bit vector used by each block to count the number of defs 61967bf885d62b1473c833bece1c9e0bb624e6ba391buzbee * from all the predecessor blocks. 62067bf885d62b1473c833bece1c9e0bb624e6ba391buzbee */ 62167bf885d62b1473c833bece1c9e0bb624e6ba391buzbee cUnit->tempSSARegisterV = oatAllocBitVector(cUnit->numSSARegs, 62267bf885d62b1473c833bece1c9e0bb624e6ba391buzbee false); 62367bf885d62b1473c833bece1c9e0bb624e6ba391buzbee 62467bf885d62b1473c833bece1c9e0bb624e6ba391buzbee /* Insert phi-operands with latest SSA names from predecessor blocks */ 62567bf885d62b1473c833bece1c9e0bb624e6ba391buzbee oatDataFlowAnalysisDispatcher(cUnit, insertPhiNodeOperands, 62667bf885d62b1473c833bece1c9e0bb624e6ba391buzbee kReachableNodes, 62767bf885d62b1473c833bece1c9e0bb624e6ba391buzbee false /* isIterative */); 62867bf885d62b1473c833bece1c9e0bb624e6ba391buzbee} 629