From d99bf49a53d170112c0241a4393ab374666b04bd Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Sat, 22 Feb 2003 23:57:48 +0000 Subject: [PATCH] Split mem2reg promotion into two parts: a function which does the work, and a pass which wraps the function. This allows other passes to use the functionality git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5610 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Utils/Mem2Reg.cpp | 59 ++++++++ .../Utils/PromoteMemoryToRegister.cpp | 138 +++++++----------- 2 files changed, 112 insertions(+), 85 deletions(-) create mode 100644 lib/Transforms/Utils/Mem2Reg.cpp diff --git a/lib/Transforms/Utils/Mem2Reg.cpp b/lib/Transforms/Utils/Mem2Reg.cpp new file mode 100644 index 00000000000..6fbb43f6c3f --- /dev/null +++ b/lib/Transforms/Utils/Mem2Reg.cpp @@ -0,0 +1,59 @@ +//===- Mem2Reg.cpp - The -mem2reg pass, a wrapper around the Utils lib ----===// +// +// This pass is a simple pass wrapper around the PromoteMemToReg function call +// exposed by the Utils library. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/PromoteMemToReg.h" +#include "llvm/Analysis/Dominators.h" +#include "llvm/iMemory.h" +#include "llvm/Function.h" +#include "Support/Statistic.h" + +namespace { + Statistic<> NumPromoted("mem2reg", "Number of alloca's promoted"); + + 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); + + // getAnalysisUsage - We need dominance frontiers + // + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + AU.setPreservesCFG(); + } + }; + + RegisterOpt X("mem2reg", "Promote Memory to Register"); +} // end of anonymous namespace + +bool PromotePass::runOnFunction(Function &F) { + std::vector Allocas; + + BasicBlock &BB = F.getEntryNode(); // Get the entry node for the function + + // Find allocas that are safe to promote, by looking 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 (isAllocaPromotable(AI)) + Allocas.push_back(AI); + + if (!Allocas.empty()) { + PromoteMemToReg(Allocas, getAnalysis()); + NumPromoted += Allocas.size(); + return true; + } + return false; +} + +// createPromoteMemoryToRegister - Provide an entry point to create this pass. +// +Pass *createPromoteMemoryToRegister() { + return new PromotePass(); +} diff --git a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp index 3c4b16c3c36..1efa8c2393f 100644 --- a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp +++ b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp @@ -1,7 +1,7 @@ //===- PromoteMemoryToRegister.cpp - Convert memory refs to regs ----------===// // -// This pass is used to promote memory references to be register references. A -// simple example of the transformation performed by this pass is: +// This file is used to promote memory references to be register references. A +// simple example of the transformation performed by this function is: // // FROM CODE TO CODE // %X = alloca int, uint 1 ret int 42 @@ -9,17 +9,14 @@ // %Y = load int* %X // ret int %Y // -// To do this transformation, a simple analysis is done to ensure it is safe. -// 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 looping over all of the alloca -// instruction, calculating dominator frontiers, then inserting phi-nodes -// following the usual SSA construction algorithm. +// The code is transformed by looping over all of the alloca instruction, +// calculating dominator frontiers, then inserting phi-nodes following the usual +// SSA construction algorithm. This code does not modify the CFG of the +// function. // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/PromoteMemToReg.h" #include "llvm/Analysis/Dominators.h" #include "llvm/iMemory.h" #include "llvm/iPHINode.h" @@ -27,13 +24,31 @@ #include "llvm/Function.h" #include "llvm/Constant.h" #include "llvm/Type.h" -#include "Support/Statistic.h" + +/// isAllocaPromotable - Return true if this alloca is legal for promotion. +/// This is true if there are only loads and stores to the alloca... +/// +bool isAllocaPromotable(const AllocaInst *AI) { + // 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)) + if (const StoreInst *SI = dyn_cast(*UI)) { + if (SI->getOperand(0) == AI) + return false; // Don't allow a store of the AI, only INTO the AI. + } else { + return false; // Not a load or store? + } + + return true; +} + namespace { - Statistic<> NumPromoted("mem2reg", "Number of alloca's promoted"); + struct PromoteMem2Reg { + const std::vector &Allocas; // the alloca instructions.. + DominanceFrontier &DF; - struct PromotePass : public FunctionPass { - std::vector Allocas; // the alloca instruction.. std::map AllocaLookup; // reverse mapping of above std::vector > PhiNodes;// Idx corresponds 2 Allocas @@ -45,72 +60,34 @@ namespace { std::vector > 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); + PromoteMem2Reg(const std::vector &A, DominanceFrontier &df) + :Allocas(A), DF(df) {} - // getAnalysisUsage - We need dominance frontiers - // - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); - AU.setPreservesCFG(); - } + void run(); private: void RenamePass(BasicBlock *BB, BasicBlock *Pred, std::vector &IncVals, std::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... -// -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)) - if (const StoreInst *SI = dyn_cast(*UI)) { - if (SI->getOperand(0) == AI) - return false; // Don't allow a store of the AI, only INTO the AI. - } else { - 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 (isSafeAlloca(AI)) { // If safe alloca, add alloca to safe list - AllocaLookup[AI] = Allocas.size(); // Keep reverse mapping - Allocas.push_back(AI); - } -} - +void PromoteMem2Reg::run() { + // If there is nothing to do, bail out... + if (Allocas.empty()) return; + Function &F = *DF.getRoot()->getParent(); -bool PromotePass::runOnFunction(Function &F) { - // Calculate the set of safe allocas - FindSafeAllocas(F); + for (unsigned i = 0, e = Allocas.size(); i != e; ++i) { + assert(isAllocaPromotable(Allocas[i]) && + "Cannot promote non-promotable alloca!"); + assert(Allocas[i]->getParent()->getParent() == &F && + "All allocas should be in the same function, which is same as DF!"); + AllocaLookup[Allocas[i]] = i; + } - // 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. @@ -128,9 +105,6 @@ bool PromotePass::runOnFunction(Function &F) { 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 // @@ -177,22 +151,13 @@ bool PromotePass::runOnFunction(Function &F) { 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; } // 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) { +bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo) { // Look up the basic-block in question std::vector &BBPNs = NewPhiNodes[BB]; if (BBPNs.empty()) BBPNs.resize(Allocas.size()); @@ -210,7 +175,7 @@ bool PromotePass::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo) { return true; } -void PromotePass::RenamePass(BasicBlock *BB, BasicBlock *Pred, +void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred, std::vector &IncomingVals, std::set &Visited) { // If this is a BB needing a phi node, lookup/create the phinode for each @@ -269,9 +234,12 @@ void PromotePass::RenamePass(BasicBlock *BB, BasicBlock *Pred, } } - -// createPromoteMemoryToRegister - Provide an entry point to create this pass. -// -Pass *createPromoteMemoryToRegister() { - return new PromotePass(); +/// PromoteMemToReg - Promote the specified list of alloca instructions into +/// scalar registers, inserting PHI nodes as appropriate. This function makes +/// use of DominanceFrontier information. This function does not modify the CFG +/// of the function at all. All allocas must be from the same function. +/// +void PromoteMemToReg(const std::vector &Allocas, + DominanceFrontier &DF) { + PromoteMem2Reg(Allocas, DF).run(); } -- 2.34.1