1 //===- PromoteMemoryToRegister.cpp - Convert memory refs to regs ----------===//
3 // This pass is used to promote memory references to be register references. A
4 // simple example of the transformation performed by this pass is:
7 // %X = alloca int, uint 1 ret int 42
8 // store int 42, int *%X
12 // To do this transformation, a simple analysis is done to ensure it is safe.
13 // Currently this just loops over all alloca instructions, looking for
14 // instructions that are only used in simple load and stores.
16 // After this, the code is transformed by...something magical :)
18 //===----------------------------------------------------------------------===//
20 #include "llvm/Transforms/Scalar/PromoteMemoryToRegister.h"
21 #include "llvm/Analysis/Dominators.h"
22 #include "llvm/iMemory.h"
23 #include "llvm/iPHINode.h"
24 #include "llvm/iTerminators.h"
25 #include "llvm/Pass.h"
26 #include "llvm/Function.h"
27 #include "llvm/BasicBlock.h"
28 #include "llvm/ConstantVals.h"
34 // instance of the promoter -- to keep all the local function data.
35 // gets re-created for each function processed
36 class PromoteInstance {
38 vector<AllocaInst*> Allocas; // the alloca instruction..
39 map<Instruction*, unsigned> AllocaLookup; // reverse mapping of above
41 vector<vector<BasicBlock*> > WriteSets; // index corresponds to Allocas
42 vector<vector<BasicBlock*> > PhiNodes; // index corresponds to Allocas
43 vector<vector<Value*> > CurrentValue; // the current value stack
45 //list of instructions to remove at end of pass :)
46 vector<Instruction *> KillList;
48 set<BasicBlock*> visited; // the basic blocks we've already visited
49 map<BasicBlock*, vector<PHINode*> > NewPhiNodes; // the phinodes we're adding
51 void traverse(BasicBlock *f, BasicBlock * predecessor);
52 bool PromoteFunction(Function *F, DominanceFrontier &DF);
53 bool QueuePhiNode(BasicBlock *bb, unsigned alloca_index);
54 void findSafeAllocas(Function *M);
57 // I do this so that I can force the deconstruction of the local variables
58 PromoteInstance(Function *F, DominanceFrontier &DF) {
59 didchange = PromoteFunction(F, DF);
61 //This returns whether the pass changes anything
62 operator bool () { return didchange; }
65 } // end of anonymous namespace
69 // findSafeAllocas - Find allocas that are safe to promote
71 void PromoteInstance::findSafeAllocas(Function *F) {
72 BasicBlock *BB = F->getEntryNode(); // Get the entry node for the function
74 // Look at all instructions in the entry node
75 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
76 if (AllocaInst *AI = dyn_cast<AllocaInst>(*I)) // Is it an alloca?
77 if (!AI->isArrayAllocation()) {
79 for (Value::use_iterator UI = AI->use_begin(), UE = AI->use_end();
80 UI != UE; ++UI) { // Loop over all of the uses of the alloca
82 // Only allow nonindexed memory access instructions...
83 if (MemAccessInst *MAI = dyn_cast<MemAccessInst>(*UI)) {
84 if (MAI->hasIndices()) { // indexed?
85 // Allow the access if there is only one index and the index is
87 if (*MAI->idx_begin() != ConstantUInt::get(Type::UIntTy, 0) ||
88 MAI->idx_begin()+1 != MAI->idx_end()) {
94 isSafe = false; break; // Not a load or store?
97 if (isSafe) { // If all checks pass, add alloca to safe list
98 AllocaLookup[AI] = Allocas.size();
99 Allocas.push_back(AI);
106 bool PromoteInstance::PromoteFunction(Function *F, DominanceFrontier &DF) {
107 // Calculate the set of safe allocas
110 // Add each alloca to the KillList. Note: KillList is destroyed MOST recently
111 // added to least recently.
112 KillList.assign(Allocas.begin(), Allocas.end());
114 // Calculate the set of write-locations for each alloca. This is analogous to
115 // counting the number of 'redefinitions' of each variable.
116 WriteSets.resize(Allocas.size());
117 for (unsigned i = 0; i != Allocas.size(); ++i) {
118 AllocaInst *AI = Allocas[i];
119 for (Value::use_iterator U =AI->use_begin(), E = AI->use_end(); U != E; ++U)
120 if (StoreInst *SI = dyn_cast<StoreInst>(*U))
121 // jot down the basic-block it came from
122 WriteSets[i].push_back(SI->getParent());
125 // Compute the locations where PhiNodes need to be inserted. Look at the
126 // dominance frontier of EACH basic-block we have a write in
128 PhiNodes.resize(Allocas.size());
129 for (unsigned i = 0; i != Allocas.size(); ++i) {
130 for (unsigned j = 0; j != WriteSets[i].size(); j++) {
131 // Look up the DF for this write, add it to PhiNodes
132 DominanceFrontier::const_iterator it = DF.find(WriteSets[i][j]);
133 DominanceFrontier::DomSetType S = it->second;
134 for (DominanceFrontier::DomSetType::iterator P = S.begin(), PE = S.end();
139 // Perform iterative step
140 for (unsigned k = 0; k != PhiNodes[i].size(); k++) {
141 DominanceFrontier::const_iterator it = DF.find(PhiNodes[i][k]);
142 DominanceFrontier::DomSetType S = it->second;
143 for (DominanceFrontier::DomSetType::iterator P = S.begin(), PE = S.end();
149 // Walks all basic blocks in the function performing the SSA rename algorithm
150 // and inserting the phi nodes we marked as necessary
152 CurrentValue.push_back(vector<Value *>(Allocas.size()));
153 traverse(F->front(), 0); // there is no predecessor of the root node
155 // Remove all instructions marked by being placed in the KillList...
157 while (!KillList.empty()) {
158 Instruction *I = KillList.back();
162 I->getParent()->getInstList().remove(I);
166 return !Allocas.empty();
170 // QueuePhiNode - queues a phi-node to be added to a basic-block for a specific
171 // Alloca returns true if there wasn't already a phi-node for that variable
173 bool PromoteInstance::QueuePhiNode(BasicBlock *BB, unsigned i /*the alloca*/) {
174 // Look up the basic-block in question
175 vector<PHINode*> &BBPNs = NewPhiNodes[BB];
176 if (BBPNs.empty()) BBPNs.resize(Allocas.size());
178 // If the BB already has a phi node added for the i'th alloca then we're done!
179 if (BBPNs[i]) return false;
181 // Create a phi-node using the dereferenced type...
182 PHINode *PN = new PHINode(Allocas[i]->getType()->getElementType(),
183 Allocas[i]->getName()+".mem2reg");
186 // Add the phi-node to the basic-block
187 BB->getInstList().push_front(PN);
189 PhiNodes[i].push_back(BB);
193 void PromoteInstance::traverse(BasicBlock *BB, BasicBlock *Pred) {
194 vector<Value *> &TOS = CurrentValue.back(); // look at top
196 // If this is a BB needing a phi node, lookup/create the phinode for each
197 // variable we need phinodes for.
198 vector<PHINode *> &BBPNs = NewPhiNodes[BB];
199 for (unsigned k = 0; k != BBPNs.size(); ++k)
201 // at this point we can assume that the array has phi nodes.. let's add
203 BBPNs[k]->addIncoming(TOS[k], Pred);
205 // also note that the active variable IS designated by the phi node
209 // don't revisit nodes
210 if (visited.count(BB)) return;
215 // keep track of the value of each variable we're watching.. how?
216 for (BasicBlock::iterator II = BB->begin(); II != BB->end(); ++II) {
217 Instruction *I = *II; //get the instruction
219 if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
220 Value *Ptr = LI->getPointerOperand();
222 if (AllocaInst *Src = dyn_cast<AllocaInst>(Ptr)) {
223 map<Instruction*, unsigned>::iterator ai = AllocaLookup.find(Src);
224 if (ai != AllocaLookup.end()) {
225 Value *V = TOS[ai->second];
227 // walk the use list of this load and replace all uses with r
228 LI->replaceAllUsesWith(V);
229 KillList.push_back(LI); // Mark the load to be deleted
232 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
233 // delete this instruction and mark the name as the current holder of the
235 Value *Ptr = SI->getPointerOperand();
236 if (AllocaInst *Dest = dyn_cast<AllocaInst>(Ptr)) {
237 map<Instruction *, unsigned>::iterator ai = AllocaLookup.find(Dest);
238 if (ai != AllocaLookup.end()) {
239 // what value were we writing?
240 TOS[ai->second] = SI->getOperand(0);
241 KillList.push_back(SI); // Mark the store to be deleted
245 } else if (TerminatorInst *TI = dyn_cast<TerminatorInst>(I)) {
246 // Recurse across our successors
247 for (unsigned i = 0; i != TI->getNumSuccessors(); i++) {
248 CurrentValue.push_back(CurrentValue.back());
249 traverse(TI->getSuccessor(i), BB); // This node becomes the predecessor
250 CurrentValue.pop_back();
258 struct PromotePass : public FunctionPass {
260 // runOnFunction - To run this pass, first we calculate the alloca
261 // instructions that are safe for promotion, then we promote each one.
263 virtual bool runOnFunction(Function *F) {
264 return (bool)PromoteInstance(F, getAnalysis<DominanceFrontier>());
267 // getAnalysisUsage - We need dominance frontiers
269 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
270 AU.addRequired(DominanceFrontier::ID);
276 // createPromoteMemoryToRegister - Provide an entry point to create this pass.
278 Pass *createPromoteMemoryToRegister() {
279 return new PromotePass();