X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FUtils%2FPromoteMemoryToRegister.cpp;h=bbb131fabfb7a39920f0734432bd85694be0d899;hb=1b7f7dc4b45a900fae2e9b062d588a995935727a;hp=e53150d643d568f7be54be355822dc6d13b26c07;hpb=d3db02248264b3ede56753cbb28df9d4ae45a1dd;p=oota-llvm.git diff --git a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp index e53150d643d..bbb131fabfb 100644 --- a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp +++ b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp @@ -13,81 +13,322 @@ // 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/Analysis/Dominators.h" #include "llvm/iMemory.h" +#include "llvm/iPHINode.h" +#include "llvm/iTerminators.h" #include "llvm/Pass.h" -#include "llvm/Method.h" - -#include "llvm/Assembly/Writer.h" // For debugging - -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 - - // Transform each alloca in turn... - for (std::vector::iterator I = Allocas.begin(), - E = Allocas.end(); I != E; ++I) - promoteAlloca(*I); - - return !Allocas.empty(); - } - - // findSafeAllocas - Find allocas that are safe to promote - // - void findSafeAllocas(Method *M, std::vector &Allocas) const; - - // promoteAlloca - Convert the use chain of an alloca instruction into - // register references. - // - void promoteAlloca(AllocaInst *AI); +#include "llvm/Function.h" +#include "llvm/BasicBlock.h" +#include "llvm/ConstantVals.h" + +using namespace std; + +namespace { + +//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 > new_phinodes; //the phinodes we're adding + + + void traverse(BasicBlock *f, BasicBlock * predecessor); + bool PromoteFunction(Function *F, DominanceFrontier &DF); + bool queuePhiNode(BasicBlock *bb, int 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; } }; +} // end of anonymous namespace // 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 +void PromoteInstance::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()) { isSafe = false; break; } // indexed? - } else { - isSafe = false; break; // Not a load or store? - } - } - - if (isSafe) // If all checks pass, add alloca to safe list - Allocas.push_back(AI); + 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); + } } +} + + + +bool PromoteInstance::PromoteFunction(Function *F, DominanceFrontier & DF) { + // Calculate the set of safe allocas + findSafeAllocas(F); + + // 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(*p,i)) + PhiNodes[i].push_back(*p); + } + } + } + + // Walks all basic blocks in the function + // performing the SSA rename algorithm + // and inserting the phi nodes we marked as necessary + BasicBlock * f = F->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(); } -// promoteAlloca - Convert the use chain of an alloca instruction into -// register references. -// -void PromotePass::promoteAlloca(AllocaInst *AI) { - cerr << "TODO: Should process: " << AI; + + +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++; + } +} + +// 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; } +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()); + } + -Pass *newPromoteMemoryToRegister() { - return new PromotePass(); + // 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() { + return new PromotePass(); +} + +