X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FPromoteMemoryToRegister.cpp;h=b84f1a378fa2970409e05a66e87ced6e050f01d7;hb=d76efa018660e806cd87c0a24512e3c532fc1d36;hp=f8cdb08520a641245039c5b6137421c6a8f6977a;hpb=71b9411b8c90cfb479ab7d641ba81fbe379f33df;p=oota-llvm.git diff --git a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp index f8cdb08520a..b84f1a378fa 100644 --- a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp +++ b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp @@ -13,100 +13,264 @@ // Currently this just loops over all alloca instructions, looking for // instructions that are only used in simple load and stores. // -// After this, the code is transformed by... +// After this, the code is transformed by...something magical :) // //===----------------------------------------------------------------------===// -#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/Assembly/Writer.h" // For debugging -using cfg::DominanceFrontier; +#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" -// PromotePass - This class is implements the PromoteMemoryToRegister pass +static Statistic<> NumPromoted("mem2reg\t\t- Number of alloca's promoted"); + +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(); + } + + 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 + + +// isSafeAlloca - This predicate controls what types of alloca instructions are +// allowed to be promoted... // -class PromotePass : public MethodPass { -public: - // 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) { - std::vector Allocas; - findSafeAllocas(M, Allocas); // Calculate safe allocas +static inline bool isSafeAlloca(const AllocaInst *AI) { + if (AI->isArrayAllocation()) return false; - // Get dominance frontier information... - DominanceFrontier &DF = getAnalysis(); + // 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; +} - // Transform each alloca in turn... - for (std::vector::iterator I = Allocas.begin(), - E = Allocas.end(); I != E; ++I) - promoteAlloca(*I, DF); +// FindSafeAllocas - Find allocas that are safe to promote +// +void PromotePass::FindSafeAllocas(Function &F) { + BasicBlock &BB = F.getEntryNode(); // Get the entry node for the function - return !Allocas.empty(); + // 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 (isSafeAlloca(AI)) { // If safe alloca, add alloca to safe list + AllocaLookup[AI] = Allocas.size(); // Keep reverse mapping + Allocas.push_back(AI); + } +} + + + +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(); - // getAnalysisUsageInfo - We need dominance frontiers + // Compute the locations where PhiNodes need to be inserted. Look at the + // dominance frontier of EACH basic-block we have a write in // - virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Requires, - Pass::AnalysisSet &Destroyed, - Pass::AnalysisSet &Provided) { - Requires.push_back(DominanceFrontier::ID); + 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); + } } -private: - // findSafeAllocas - Find allocas that are safe to promote + // 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 // - void findSafeAllocas(Method *M, std::vector &Allocas) const; + set Visited; // The basic blocks we've already visited + Traverse(F.begin(), 0, Values, Visited); - // promoteAlloca - Convert the use chain of an alloca instruction into - // register references. + // Remove all instructions marked by being placed in the KillList... // - void promoteAlloca(AllocaInst *AI, DominanceFrontier &DF); -}; + while (!KillList.empty()) { + Instruction *I = KillList.back(); + KillList.pop_back(); + I->getParent()->getInstList().erase(I); + } -// findSafeAllocas - Find allocas that are safe to promote -// -void PromotePass::findSafeAllocas(Method *M, - std::vector &Allocas) const { - BasicBlock *BB = M->front(); // Get the entry node for the method + NumPromoted += Allocas.size(); - // 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()) { isSafe = false; break; } // indexed? - } else { - isSafe = false; break; // Not a load or store? - } - } + // Purge data structurse so they are available the next iteration... + Allocas.clear(); + AllocaLookup.clear(); + PhiNodes.clear(); + NewPhiNodes.clear(); + return true; +} - if (isSafe) // If all checks pass, add alloca to safe list - Allocas.push_back(AI); - } +// 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; } +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; + } -// promoteAlloca - Convert the use chain of an alloca instruction into -// register references. -// -void PromotePass::promoteAlloca(AllocaInst *AI, DominanceFrontier &DFInfo) { - cerr << "TODO: Should process: " << AI; + // don't revisit nodes + if (Visited.count(BB)) return; + + // mark as visited + 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) { + Instruction *I = II; // get the instruction + + if (LoadInst *LI = dyn_cast(I)) { + Value *Ptr = LI->getPointerOperand(); + + 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); + } + } + } } -// newPromoteMemoryToRegister - Provide an entry point to create this pass. +// createPromoteMemoryToRegister - Provide an entry point to create this pass. // -Pass *newPromoteMemoryToRegister() { +Pass *createPromoteMemoryToRegister() { return new PromotePass(); }