X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FPromoteMemoryToRegister.cpp;h=b84f1a378fa2970409e05a66e87ced6e050f01d7;hb=d76efa018660e806cd87c0a24512e3c532fc1d36;hp=f94632e3df975e987497c51e473f937f83edad72;hpb=b1be061a76b47fe3f87596afb59674cc0c88a9b4;p=oota-llvm.git diff --git a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp index f94632e3df9..b84f1a378fa 100644 --- a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp +++ b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp @@ -17,326 +17,260 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/Scalar/PromoteMemoryToRegister.h" +#include "llvm/Transforms/Scalar.h" #include "llvm/Analysis/Dominators.h" #include "llvm/iMemory.h" -#include "llvm/Pass.h" -#include "llvm/Method.h" -#include "llvm/BasicBlock.h" -#include "llvm/Assembly/Writer.h" // For debugging #include "llvm/iPHINode.h" #include "llvm/iTerminators.h" +#include "llvm/Function.h" +#include "llvm/BasicBlock.h" +#include "llvm/Constant.h" +#include "llvm/Type.h" +#include "Support/StatisticReporter.h" -using namespace std; - +static Statistic<> NumPromoted("mem2reg\t\t- Number of alloca's promoted"); -using cfg::DominanceFrontier; +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 + + 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(); + AU.preservesCFG(); + } -//instance of the promoter -- to keep all the local method data. -// gets re-created for each method 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 > new_phinodes; //the phinodes we're adding - - - void traverse(BasicBlock *f, BasicBlock * predecessor); - bool PromoteMethod(Method *M, DominanceFrontier & DF); - bool queuePhiNode(BasicBlock *bb, int alloca_index); - void findSafeAllocas(Method *M); - bool didchange; - public: - // I do this so that I can force the deconstruction of the local variables - PromoteInstance(Method *M, DominanceFrontier & DF) - { - didchange=PromoteMethod(M, DF); - } - //This returns whether the pass changes anything - operator bool () { return didchange; } -}; + private: + void Traverse(BasicBlock *BB, BasicBlock *Pred, vector &IncVals, + set &Visited); + bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx); + void FindSafeAllocas(Function &F); + }; + RegisterOpt X("mem2reg", "Promote Memory to Register"); } // end of anonymous namespace -// findSafeAllocas - Find allocas that are safe to promote + +// isSafeAlloca - This predicate controls what types of alloca instructions are +// allowed to be promoted... // -void PromoteInstance::findSafeAllocas(Method *M) -{ - BasicBlock *BB = M->front(); // Get the entry node for the method +static inline bool isSafeAlloca(const AllocaInst *AI) { + if (AI->isArrayAllocation()) return false; + + // Only allow direct loads and stores... + 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 + if (!isa(*UI) && !isa(*UI)) + return false; // Not a load or store? + + return true; +} + +// FindSafeAllocas - Find allocas that are safe to promote +// +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); - } + for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) + if (AllocaInst *AI = dyn_cast(&*I)) // Is it an alloca? + if (isSafeAlloca(AI)) { // If safe alloca, add alloca to safe list + AllocaLookup[AI] = Allocas.size(); // Keep reverse mapping + Allocas.push_back(AI); } } -bool PromoteInstance::PromoteMethod(Method *M, DominanceFrontier & DF) { - // Calculate the set of safe allocas - findSafeAllocas(M); - - // Add each alloca to the killlist - // note: killlist is destroyed MOST recently added to least recently. - killlist.assign(Allocas.begin(), Allocas.end()); - - // Calculate the set of write-locations for each alloca. - // this is analogous to counting the number of 'redefinitions' of each variable. - for (unsigned i = 0; i()); //add a new set - for (Value::use_iterator U = AI->use_begin();U!=AI->use_end();++U) - { - if (MemAccessInst *MAI = dyn_cast(*U)) { - WriteSets[i].push_back(MAI->getParent()); // jot down the basic-block it came from - } - } - } - - // Compute the locations where PhiNodes need to be inserted - // look at the dominance frontier of EACH basic-block we have a write in - PhiNodes.resize(Allocas.size()); - for (unsigned i = 0; isecond; - for (DominanceFrontier::DomSetType::iterator p = s.begin(); p!=s.end(); ++p) - { - if (queuePhiNode((BasicBlock *)*p,i)) - PhiNodes[i].push_back((BasicBlock*)*p); - } - } - } - - // Walks all basic blocks in the method - // performing the SSA rename algorithm - // and inserting the phi nodes we marked as necessary - BasicBlock * f = M->front(); //get root basic-block - - CurrentValue.push_back(vector(Allocas.size())); - - traverse(f, NULL); // there is no predecessor of the root node - - - // ** REMOVE EVERYTHING IN THE KILL-LIST ** - // we need to kill 'uses' before root values - // so we should probably run through in reverse - for (vector::reverse_iterator i = killlist.rbegin(); i!=killlist.rend(); ++i) - { - Instruction * r = *i; - BasicBlock * o = r->getParent(); - //now go find.. - - BasicBlock::InstListType & l = o->getInstList(); - o->getInstList().remove(r); - delete r; - } - - return !Allocas.empty(); +bool PromotePass::runOnFunction(Function &F) { + // Calculate the set of safe allocas + 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. + KillList.assign(Allocas.begin(), Allocas.end()); + + // 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]; + for (Value::use_iterator U =AI->use_begin(), E = AI->use_end(); U != E; ++U) + if (StoreInst *SI = dyn_cast(*U)) + // jot down the basic-block it came from + 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 + // + PhiNodes.resize(Allocas.size()); + for (unsigned i = 0; i != Allocas.size(); ++i) { + for (unsigned j = 0; j != WriteSets[i].size(); j++) { + // Look up the DF for this write, add it to PhiNodes + DominanceFrontier::const_iterator it = DF.find(WriteSets[i][j]); + DominanceFrontier::DomSetType S = it->second; + for (DominanceFrontier::DomSetType::iterator P = S.begin(), PE = S.end(); + P != PE; ++P) + QueuePhiNode(*P, i); + } + + // Perform iterative step + for (unsigned k = 0; k != PhiNodes[i].size(); k++) { + DominanceFrontier::const_iterator it = DF.find(PhiNodes[i][k]); + DominanceFrontier::DomSetType S = it->second; + for (DominanceFrontier::DomSetType::iterator P = S.begin(), PE = S.end(); + P != PE; ++P) + QueuePhiNode(*P, i); + } + } + + // Set the incoming values for the basic block to be null values for all of + // 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. + // + vector Values(Allocas.size()); + for (unsigned i = 0, e = Allocas.size(); i != e; ++i) + Values[i] = Constant::getNullValue(Allocas[i]->getAllocatedType()); + + // Walks all basic blocks in the function performing the SSA rename algorithm + // and inserting the phi nodes we marked as necessary + // + set Visited; // The basic blocks we've already visited + Traverse(F.begin(), 0, Values, Visited); + + // Remove all instructions marked by being placed in the KillList... + // + while (!KillList.empty()) { + Instruction *I = KillList.back(); + KillList.pop_back(); + + I->getParent()->getInstList().erase(I); + } + + NumPromoted += Allocas.size(); + + // Purge data structurse so they are available the next iteration... + Allocas.clear(); + AllocaLookup.clear(); + PhiNodes.clear(); + NewPhiNodes.clear(); + return true; } - -void PromoteInstance::traverse(BasicBlock *f, BasicBlock * predecessor) -{ - vector * tos = &CurrentValue.back(); //look at top- - - //if this is a BB needing a phi node, lookup/create the phinode for - // each variable we need phinodes for. - map >::iterator nd = new_phinodes.find(f); - if (nd!=new_phinodes.end()) - { - for (unsigned k = 0; k!=nd->second.size(); ++k) - if (nd->second[k]) - { - //at this point we can assume that the array has phi nodes.. let's - // add the incoming data - if ((*tos)[k]) - nd->second[k]->addIncoming((*tos)[k],predecessor); - //also note that the active variable IS designated by the phi node - (*tos)[k] = nd->second[k]; - } - } - - //don't revisit nodes - if (visited.find(f)!=visited.end()) - return; - //mark as visited - visited.insert(f); - - BasicBlock::iterator i = f->begin(); - //keep track of the value of each variable we're watching.. how? - while(i!=f->end()) - { - Instruction * inst = *i; //get the instruction - //is this a write/read? - if (LoadInst * LI = dyn_cast(inst)) - { - // This is a bit weird... - Value * ptr = LI->getPointerOperand(); //of type value - if (AllocaInst * srcinstr = dyn_cast(ptr)) - { - map::iterator ai = AllocaLookup.find(srcinstr); - if (ai!=AllocaLookup.end()) - { - if (Value *r = (*tos)[ai->second]) - { - //walk the use list of this load and replace - // all uses with r - LI->replaceAllUsesWith(r); - //now delete the instruction.. somehow.. - killlist.push_back((Instruction *)LI); - } - } - } - } - else if (StoreInst * SI = dyn_cast(inst)) - { - // delete this instruction and mark the name as the - // current holder of the value - Value * ptr = SI->getPointerOperand(); //of type value - if (Instruction * srcinstr = dyn_cast(ptr)) - { - map::iterator ai = AllocaLookup.find(srcinstr); - if (ai!=AllocaLookup.end()) - { - //what value were we writing? - Value * writeval = SI->getOperand(0); - //write down... - (*tos)[ai->second] = writeval; - //now delete it.. somehow? - killlist.push_back((Instruction *)SI); - } - } - - } - else if (TerminatorInst * TI = dyn_cast(inst)) - { - // Recurse across our sucessors - for (unsigned i = 0; i!=TI->getNumSuccessors(); i++) - { - CurrentValue.push_back(CurrentValue.back()); - traverse(TI->getSuccessor(i),f); //this node IS the predecessor - CurrentValue.pop_back(); - } - } - i++; - } +// 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 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[AllocaNo]) return false; + + // Create a PhiNode using the dereferenced type... and add the phi-node to the + // BasicBlock + PHINode *PN = new PHINode(Allocas[AllocaNo]->getAllocatedType(), + Allocas[AllocaNo]->getName()+".mem2reg", + BB->begin()); + BBPNs[AllocaNo] = PN; + PhiNodes[AllocaNo].push_back(BB); + return true; } -// 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, int i /*the alloca*/) -{ - map >::iterator nd; - //look up the basic-block in question - nd = new_phinodes.find(bb); - //if the basic-block has no phi-nodes added, or at least none - //for the i'th alloca. then add. - if (nd==new_phinodes.end() || nd->second[i]==NULL) - { - //we're not added any phi nodes to this basicblock yet - // create the phi-node array. - if (nd==new_phinodes.end()) - { - new_phinodes[bb] = vector(Allocas.size()); - nd = new_phinodes.find(bb); - } - - //find the type the alloca returns - const PointerType * pt = Allocas[i]->getType(); - //create a phi-node using the DEREFERENCED type - PHINode * ph = new PHINode(pt->getElementType(), Allocas[i]->getName()+".mem2reg"); - nd->second[i] = ph; - //add the phi-node to the basic-block - bb->getInstList().push_front(ph); - return true; - } - return false; -} +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]; + for (unsigned k = 0; k != BBPNs.size(); ++k) + 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(IncomingVals[k], Pred); + + // also note that the active variable IS designated by the phi node + IncomingVals[k] = PN; + } + // don't revisit nodes + if (Visited.count(BB)) return; + + // mark as visited + Visited.insert(BB); -namespace { - class PromotePass : public MethodPass { - public: + // keep track of the value of each variable we're watching.. how? + for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II) { + Instruction *I = II; // get the instruction - // runOnMethod - To run this pass, first we calculate the alloca - // instructions that are safe for promotion, then we promote each one. - // - virtual bool runOnMethod(Method *M) - { - PromoteInstance inst(M, getAnalysis()); - return (bool)inst; - } - + if (LoadInst *LI = dyn_cast(I)) { + Value *Ptr = LI->getPointerOperand(); - // getAnalysisUsageInfo - We need dominance frontiers - // - virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires, - Pass::AnalysisSet &Destroyed, - Pass::AnalysisSet &Provided) { - Requires.push_back(DominanceFrontier::ID); + if (AllocaInst *Src = dyn_cast(Ptr)) { + 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); + KillList.push_back(LI); // Mark the load to be deleted + } + } + } else if (StoreInst *SI = dyn_cast(I)) { + // delete this instruction and mark the name as the current holder of the + // value + Value *Ptr = SI->getPointerOperand(); + if (AllocaInst *Dest = dyn_cast(Ptr)) { + map::iterator ai = AllocaLookup.find(Dest); + if (ai != AllocaLookup.end()) { + // what value were we writing? + IncomingVals[ai->second] = SI->getOperand(0); + KillList.push_back(SI); // Mark the store to be deleted + } + } + + } else if (TerminatorInst *TI = dyn_cast(I)) { + // Recurse across our successors + for (unsigned i = 0; i != TI->getNumSuccessors(); i++) { + vector OutgoingVals(IncomingVals); + Traverse(TI->getSuccessor(i), BB, OutgoingVals, Visited); + } } - }; + } } - + // createPromoteMemoryToRegister - Provide an entry point to create this pass. // Pass *createPromoteMemoryToRegister() { - return new PromotePass(); + return new PromotePass(); } - -