X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FPromoteMemoryToRegister.cpp;h=8679701e6a7d0233cd27040e2758cfd0ab233b95;hb=b9ddce65c281f023780d2b6578e7ed6d2913a2cb;hp=23dd2865a06120dbf64cb77da08b9868873de3d0;hpb=5b5df1747feac197fd839c956952fd4d79c58e79;p=oota-llvm.git diff --git a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp index 23dd2865a06..8679701e6a7 100644 --- a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp +++ b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp @@ -27,85 +27,92 @@ #include "llvm/BasicBlock.h" #include "llvm/ConstantVals.h" -using namespace std; +using std::vector; +using std::map; +using std::set; namespace { + struct PromotePass : public FunctionPass { + vector Allocas; // the alloca instruction.. + map AllocaLookup; // reverse mapping of above + + vector > PhiNodes; // index corresponds to Allocas + + // List of instructions to remove at end of pass + vector KillList; + + map > NewPhiNodes; // the PhiNodes we're adding -// instance of the promoter -- to keep all the local function data. -// gets re-created for each function processed -class PromoteInstance { -protected: - vector Allocas; // the alloca instruction.. - map AllocaLookup; // reverse mapping of above - - vector > WriteSets; // index corresponds to Allocas - vector > PhiNodes; // index corresponds to Allocas - vector > CurrentValue; // the current value stack - - //list of instructions to remove at end of pass :) - vector KillList; - - set visited; // the basic blocks we've already visited - map > NewPhiNodes; // the phinodes we're adding - - void traverse(BasicBlock *f, BasicBlock * predecessor); - bool PromoteFunction(Function *F, DominanceFrontier &DF); - bool QueuePhiNode(BasicBlock *bb, unsigned alloca_index); - void findSafeAllocas(Function *M); - bool didchange; -public: - // I do this so that I can force the deconstruction of the local variables - PromoteInstance(Function *F, DominanceFrontier &DF) { - didchange = PromoteFunction(F, DF); - } - //This returns whether the pass changes anything - operator bool () { return didchange; } -}; + public: + // runOnFunction - To run this pass, first we calculate the alloca + // instructions that are safe for promotion, then we promote each one. + // + virtual bool runOnFunction(Function *F); + + // getAnalysisUsage - We need dominance frontiers + // + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(DominanceFrontier::ID); + } + + private: + void Traverse(BasicBlock *BB, BasicBlock *Pred, vector &IncVals, + set &Visited); + bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx); + void FindSafeAllocas(Function *F); + }; } // end of anonymous namespace +// isSafeAlloca - This predicate controls what types of alloca instructions are +// allowed to be promoted... +// +static inline bool isSafeAlloca(const AllocaInst *AI) { + if (AI->isArrayAllocation()) return false; + + for (Value::use_const_iterator UI = AI->use_begin(), UE = AI->use_end(); + UI != UE; ++UI) { // Loop over all of the uses of the alloca + + // Only allow nonindexed memory access instructions... + if (MemAccessInst *MAI = dyn_cast(*UI)) { + if (MAI->hasIndices()) { // indexed? + // Allow the access if there is only one index and the index is + // zero. + if (*MAI->idx_begin() != ConstantUInt::get(Type::UIntTy, 0) || + MAI->idx_begin()+1 != MAI->idx_end()) + return false; + } + } else { + return false; // Not a load or store? + } + } + + return true; +} -// findSafeAllocas - Find allocas that are safe to promote +// FindSafeAllocas - Find allocas that are safe to promote // -void PromoteInstance::findSafeAllocas(Function *F) { +void PromotePass::FindSafeAllocas(Function *F) { BasicBlock *BB = F->getEntryNode(); // Get the entry node for the function // Look at all instructions in the entry node for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) if (AllocaInst *AI = dyn_cast(*I)) // Is it an alloca? - if (!AI->isArrayAllocation()) { - bool isSafe = true; - for (Value::use_iterator UI = AI->use_begin(), UE = AI->use_end(); - UI != UE; ++UI) { // Loop over all of the uses of the alloca - - // Only allow nonindexed memory access instructions... - if (MemAccessInst *MAI = dyn_cast(*UI)) { - if (MAI->hasIndices()) { // indexed? - // Allow the access if there is only one index and the index is - // zero. - if (*MAI->idx_begin() != ConstantUInt::get(Type::UIntTy, 0) || - MAI->idx_begin()+1 != MAI->idx_end()) { - isSafe = false; - break; - } - } - } else { - isSafe = false; break; // Not a load or store? - } - } - if (isSafe) { // If all checks pass, add alloca to safe list - AllocaLookup[AI] = Allocas.size(); - Allocas.push_back(AI); - } + if (isSafeAlloca(AI)) { // If safe alloca, add alloca to safe list + AllocaLookup[AI] = Allocas.size(); // Keep reverse mapping + Allocas.push_back(AI); } } -bool PromoteInstance::PromoteFunction(Function *F, DominanceFrontier &DF) { +bool PromotePass::runOnFunction(Function *F) { // Calculate the set of safe allocas - findSafeAllocas(F); + FindSafeAllocas(F); + + // If there is nothing to do, bail out... + if (Allocas.empty()) return false; // Add each alloca to the KillList. Note: KillList is destroyed MOST recently // added to least recently. @@ -113,6 +120,7 @@ bool PromoteInstance::PromoteFunction(Function *F, DominanceFrontier &DF) { // Calculate the set of write-locations for each alloca. This is analogous to // counting the number of 'redefinitions' of each variable. + vector > WriteSets; // index corresponds to Allocas WriteSets.resize(Allocas.size()); for (unsigned i = 0; i != Allocas.size(); ++i) { AllocaInst *AI = Allocas[i]; @@ -122,6 +130,9 @@ bool PromoteInstance::PromoteFunction(Function *F, DominanceFrontier &DF) { WriteSets[i].push_back(SI->getParent()); } + // Get dominance frontier information... + DominanceFrontier &DF = getAnalysis(); + // Compute the locations where PhiNodes need to be inserted. Look at the // dominance frontier of EACH basic-block we have a write in // @@ -150,15 +161,15 @@ bool PromoteInstance::PromoteFunction(Function *F, DominanceFrontier &DF) { // the alloca's. We do this in case there is a load of a value that has not // been stored yet. In this case, it will get this null value. // - CurrentValue.push_back(vector(Allocas.size())); + vector Values(Allocas.size()); for (unsigned i = 0, e = Allocas.size(); i != e; ++i) - CurrentValue[0][i] = - Constant::getNullValue(Allocas[i]->getType()->getElementType()); + Values[i] = Constant::getNullValue(Allocas[i]->getType()->getElementType()); // Walks all basic blocks in the function performing the SSA rename algorithm // and inserting the phi nodes we marked as necessary // - traverse(F->front(), 0); // there is no predecessor of the root node + set Visited; // The basic blocks we've already visited + Traverse(F->front(), 0, Values, Visited); // Remove all instructions marked by being placed in the KillList... // @@ -166,41 +177,45 @@ bool PromoteInstance::PromoteFunction(Function *F, DominanceFrontier &DF) { Instruction *I = KillList.back(); KillList.pop_back(); - //now go find.. I->getParent()->getInstList().remove(I); delete I; } - return !Allocas.empty(); + // Purge data structurse so they are available the next iteration... + Allocas.clear(); + AllocaLookup.clear(); + PhiNodes.clear(); + NewPhiNodes.clear(); + return true; } // QueuePhiNode - queues a phi-node to be added to a basic-block for a specific // Alloca returns true if there wasn't already a phi-node for that variable // -bool PromoteInstance::QueuePhiNode(BasicBlock *BB, unsigned i /*the alloca*/) { +bool PromotePass::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo) { // Look up the basic-block in question vector &BBPNs = NewPhiNodes[BB]; if (BBPNs.empty()) BBPNs.resize(Allocas.size()); // If the BB already has a phi node added for the i'th alloca then we're done! - if (BBPNs[i]) return false; + if (BBPNs[AllocaNo]) return false; - // Create a phi-node using the dereferenced type... - PHINode *PN = new PHINode(Allocas[i]->getType()->getElementType(), - Allocas[i]->getName()+".mem2reg"); - BBPNs[i] = PN; + // Create a PhiNode using the dereferenced type... + PHINode *PN = new PHINode(Allocas[AllocaNo]->getType()->getElementType(), + Allocas[AllocaNo]->getName()+".mem2reg"); + BBPNs[AllocaNo] = PN; // Add the phi-node to the basic-block BB->getInstList().push_front(PN); - PhiNodes[i].push_back(BB); + PhiNodes[AllocaNo].push_back(BB); return true; } -void PromoteInstance::traverse(BasicBlock *BB, BasicBlock *Pred) { - vector &TOS = CurrentValue.back(); // look at top - +void PromotePass::Traverse(BasicBlock *BB, BasicBlock *Pred, + vector &IncomingVals, + set &Visited) { // If this is a BB needing a phi node, lookup/create the phinode for each // variable we need phinodes for. vector &BBPNs = NewPhiNodes[BB]; @@ -208,17 +223,17 @@ void PromoteInstance::traverse(BasicBlock *BB, BasicBlock *Pred) { if (PHINode *PN = BBPNs[k]) { // at this point we can assume that the array has phi nodes.. let's add // the incoming data - PN->addIncoming(TOS[k], Pred); + PN->addIncoming(IncomingVals[k], Pred); // also note that the active variable IS designated by the phi node - TOS[k] = PN; + IncomingVals[k] = PN; } // don't revisit nodes - if (visited.count(BB)) return; + if (Visited.count(BB)) return; // mark as visited - visited.insert(BB); + Visited.insert(BB); // keep track of the value of each variable we're watching.. how? for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II) { @@ -228,9 +243,9 @@ void PromoteInstance::traverse(BasicBlock *BB, BasicBlock *Pred) { Value *Ptr = LI->getPointerOperand(); if (AllocaInst *Src = dyn_cast(Ptr)) { - map::iterator ai = AllocaLookup.find(Src); - if (ai != AllocaLookup.end()) { - Value *V = TOS[ai->second]; + map::iterator AI = AllocaLookup.find(Src); + if (AI != AllocaLookup.end()) { + Value *V = IncomingVals[AI->second]; // walk the use list of this load and replace all uses with r LI->replaceAllUsesWith(V); @@ -245,7 +260,7 @@ void PromoteInstance::traverse(BasicBlock *BB, BasicBlock *Pred) { map::iterator ai = AllocaLookup.find(Dest); if (ai != AllocaLookup.end()) { // what value were we writing? - TOS[ai->second] = SI->getOperand(0); + IncomingVals[ai->second] = SI->getOperand(0); KillList.push_back(SI); // Mark the store to be deleted } } @@ -253,34 +268,14 @@ void PromoteInstance::traverse(BasicBlock *BB, BasicBlock *Pred) { } else if (TerminatorInst *TI = dyn_cast(I)) { // Recurse across our successors for (unsigned i = 0; i != TI->getNumSuccessors(); i++) { - CurrentValue.push_back(CurrentValue.back()); - traverse(TI->getSuccessor(i), BB); // This node becomes the predecessor - CurrentValue.pop_back(); + vector OutgoingVals(IncomingVals); + Traverse(TI->getSuccessor(i), BB, OutgoingVals, Visited); } } } } -namespace { - struct PromotePass : public FunctionPass { - - // runOnFunction - To run this pass, first we calculate the alloca - // instructions that are safe for promotion, then we promote each one. - // - virtual bool runOnFunction(Function *F) { - return (bool)PromoteInstance(F, getAnalysis()); - } - - // getAnalysisUsage - We need dominance frontiers - // - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(DominanceFrontier::ID); - } - }; -} - - // createPromoteMemoryToRegister - Provide an entry point to create this pass. // Pass *createPromoteMemoryToRegister() {