PromoteMemoryToRegister.cpp revision 43f820d1f7638656be2158efac7dd8f5b08b8b77
1//===- PromoteMemoryToRegister.cpp - Convert allocas to registers ---------===// 2// 3// This file promote memory references to be register references. It promotes 4// alloca instructions which only have loads and stores as uses. An alloca is 5// transformed by using dominator frontiers to place PHI nodes, then traversing 6// the function in depth-first order to rewrite loads and stores as appropriate. 7// This is just the standard SSA construction algorithm. 8// 9//===----------------------------------------------------------------------===// 10 11#include "llvm/Transforms/Utils/PromoteMemToReg.h" 12#include "llvm/Analysis/Dominators.h" 13#include "llvm/iMemory.h" 14#include "llvm/iPHINode.h" 15#include "llvm/Function.h" 16#include "llvm/Constant.h" 17#include "llvm/Support/CFG.h" 18#include "Support/StringExtras.h" 19 20/// isAllocaPromotable - Return true if this alloca is legal for promotion. 21/// This is true if there are only loads and stores to the alloca... 22/// 23bool isAllocaPromotable(const AllocaInst *AI, const TargetData &TD) { 24 // FIXME: If the memory unit is of pointer or integer type, we can permit 25 // assignments to subsections of the memory unit. 26 27 // Only allow direct loads and stores... 28 for (Value::use_const_iterator UI = AI->use_begin(), UE = AI->use_end(); 29 UI != UE; ++UI) // Loop over all of the uses of the alloca 30 if (!isa<LoadInst>(*UI)) 31 if (const StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 32 if (SI->getOperand(0) == AI) 33 return false; // Don't allow a store of the AI, only INTO the AI. 34 } else { 35 return false; // Not a load or store? 36 } 37 38 return true; 39} 40 41namespace { 42 struct PromoteMem2Reg { 43 // Allocas - The alloca instructions being promoted 44 std::vector<AllocaInst*> Allocas; 45 DominanceFrontier &DF; 46 const TargetData &TD; 47 48 // AllocaLookup - Reverse mapping of Allocas 49 std::map<AllocaInst*, unsigned> AllocaLookup; 50 51 // NewPhiNodes - The PhiNodes we're adding. 52 std::map<BasicBlock*, std::vector<PHINode*> > NewPhiNodes; 53 54 // Visited - The set of basic blocks the renamer has already visited. 55 std::set<BasicBlock*> Visited; 56 57 public: 58 PromoteMem2Reg(const std::vector<AllocaInst*> &A, DominanceFrontier &df, 59 const TargetData &td) : Allocas(A), DF(df), TD(td) {} 60 61 void run(); 62 63 private: 64 void PromoteLocallyUsedAlloca(AllocaInst *AI); 65 66 void RenamePass(BasicBlock *BB, BasicBlock *Pred, 67 std::vector<Value*> &IncVals); 68 bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version); 69 }; 70} // end of anonymous namespace 71 72void PromoteMem2Reg::run() { 73 Function &F = *DF.getRoot()->getParent(); 74 75 for (unsigned i = 0; i != Allocas.size(); ++i) { 76 AllocaInst *AI = Allocas[i]; 77 78 assert(isAllocaPromotable(AI, TD) && 79 "Cannot promote non-promotable alloca!"); 80 assert(Allocas[i]->getParent()->getParent() == &F && 81 "All allocas should be in the same function, which is same as DF!"); 82 83 if (AI->use_empty()) { 84 // If there are no uses of the alloca, just delete it now. 85 AI->getParent()->getInstList().erase(AI); 86 87 // Remove the alloca from the Allocas list, since it has been processed 88 Allocas[i] = Allocas.back(); 89 Allocas.pop_back(); 90 --i; 91 continue; 92 } 93 94 // Calculate the set of write-locations for each alloca. This is analogous 95 // to counting the number of 'redefinitions' of each variable. 96 std::vector<BasicBlock*> DefiningBlocks; 97 98 BasicBlock *OnlyBlock = 0; 99 bool OnlyUsedInOneBlock = true; 100 101 // As we scan the uses of the alloca instruction, keep track of stores, and 102 // decide whether all of the loads and stores to the alloca are within the 103 // same basic block. 104 for (Value::use_iterator U =AI->use_begin(), E = AI->use_end(); U != E;++U){ 105 Instruction *User = cast<Instruction>(*U); 106 if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 107 // Remember the basic blocks which define new values for the alloca 108 DefiningBlocks.push_back(SI->getParent()); 109 } 110 111 if (OnlyUsedInOneBlock) { 112 if (OnlyBlock == 0) 113 OnlyBlock = User->getParent(); 114 else if (OnlyBlock != User->getParent()) 115 OnlyUsedInOneBlock = false; 116 } 117 } 118 119 // If the alloca is only read and written in one basic block, just perform a 120 // linear sweep over the block to eliminate it. 121 if (OnlyUsedInOneBlock) { 122 PromoteLocallyUsedAlloca(AI); 123 124 // Remove the alloca from the Allocas list, since it has been processed 125 Allocas[i] = Allocas.back(); 126 Allocas.pop_back(); 127 --i; 128 continue; 129 } 130 131 AllocaLookup[Allocas[i]] = i; 132 133 // PhiNodeBlocks - A list of blocks that phi nodes have been inserted for 134 // this alloca. 135 std::vector<BasicBlock*> PhiNodeBlocks; 136 137 // Compute the locations where PhiNodes need to be inserted. Look at the 138 // dominance frontier of EACH basic-block we have a write in. 139 // 140 unsigned CurrentVersion = 0; 141 while (!DefiningBlocks.empty()) { 142 BasicBlock *BB = DefiningBlocks.back(); 143 DefiningBlocks.pop_back(); 144 145 // Look up the DF for this write, add it to PhiNodes 146 DominanceFrontier::const_iterator it = DF.find(BB); 147 if (it != DF.end()) { 148 const DominanceFrontier::DomSetType &S = it->second; 149 for (DominanceFrontier::DomSetType::iterator P = S.begin(),PE = S.end(); 150 P != PE; ++P) 151 if (QueuePhiNode(*P, i, CurrentVersion)) 152 DefiningBlocks.push_back(*P); 153 } 154 } 155 } 156 157 if (Allocas.empty()) 158 return; // All of the allocas must have been trivial! 159 160 // Set the incoming values for the basic block to be null values for all of 161 // the alloca's. We do this in case there is a load of a value that has not 162 // been stored yet. In this case, it will get this null value. 163 // 164 std::vector<Value *> Values(Allocas.size()); 165 for (unsigned i = 0, e = Allocas.size(); i != e; ++i) 166 Values[i] = Constant::getNullValue(Allocas[i]->getAllocatedType()); 167 168 // Walks all basic blocks in the function performing the SSA rename algorithm 169 // and inserting the phi nodes we marked as necessary 170 // 171 RenamePass(F.begin(), 0, Values); 172 173 // The renamer uses the Visited set to avoid infinite loops. Clear it now. 174 Visited.clear(); 175 176 // Remove the allocas themselves from the function... 177 for (unsigned i = 0, e = Allocas.size(); i != e; ++i) { 178 Instruction *A = Allocas[i]; 179 180 // If there are any uses of the alloca instructions left, they must be in 181 // sections of dead code that were not processed on the dominance frontier. 182 // Just delete the users now. 183 // 184 if (!A->use_empty()) 185 A->replaceAllUsesWith(Constant::getNullValue(A->getType())); 186 A->getParent()->getInstList().erase(A); 187 } 188 189 // At this point, the renamer has added entries to PHI nodes for all reachable 190 // code. Unfortunately, there may be blocks which are not reachable, which 191 // the renamer hasn't traversed. If this is the case, the PHI nodes may not 192 // have incoming values for all predecessors. Loop over all PHI nodes we have 193 // created, inserting null constants if they are missing any incoming values. 194 // 195 for (std::map<BasicBlock*, std::vector<PHINode *> >::iterator I = 196 NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) { 197 198 std::vector<BasicBlock*> Preds(pred_begin(I->first), pred_end(I->first)); 199 std::vector<PHINode*> &PNs = I->second; 200 assert(!PNs.empty() && "Empty PHI node list??"); 201 202 // Only do work here if there the PHI nodes are missing incoming values. We 203 // know that all PHI nodes that were inserted in a block will have the same 204 // number of incoming values, so we can just check any PHI node. 205 PHINode *FirstPHI; 206 for (unsigned i = 0; (FirstPHI = PNs[i]) == 0; ++i) 207 /*empty*/; 208 209 if (Preds.size() != FirstPHI->getNumIncomingValues()) { 210 // Ok, now we know that all of the PHI nodes are missing entries for some 211 // basic blocks. Start by sorting the incoming predecessors for efficient 212 // access. 213 std::sort(Preds.begin(), Preds.end()); 214 215 // Now we loop through all BB's which have entries in FirstPHI and remove 216 // them from the Preds list. 217 for (unsigned i = 0, e = FirstPHI->getNumIncomingValues(); i != e; ++i) { 218 // Do a log(n) search of teh Preds list for the entry we want. 219 std::vector<BasicBlock*>::iterator EntIt = 220 std::lower_bound(Preds.begin(), Preds.end(), 221 FirstPHI->getIncomingBlock(i)); 222 assert(EntIt != Preds.end() && *EntIt == FirstPHI->getIncomingBlock(i)&& 223 "PHI node has entry for a block which is not a predecessor!"); 224 225 // Remove the entry 226 Preds.erase(EntIt); 227 } 228 229 // At this point, the blocks left in the preds list must have dummy 230 // entries inserted into every PHI nodes for the block. 231 for (unsigned i = 0, e = PNs.size(); i != e; ++i) { 232 PHINode *PN = PNs[i]; 233 Value *NullVal = Constant::getNullValue(PN->getType()); 234 for (unsigned pred = 0, e = Preds.size(); pred != e; ++pred) 235 PN->addIncoming(NullVal, Preds[pred]); 236 } 237 } 238 } 239} 240 241// PromoteLocallyUsedAlloca - Many allocas are only used within a single basic 242// block. If this is the case, avoid traversing the CFG and inserting a lot of 243// potentially useless PHI nodes by just performing a single linear pass over 244// the basic block using the Alloca. 245// 246void PromoteMem2Reg::PromoteLocallyUsedAlloca(AllocaInst *AI) { 247 assert(!AI->use_empty() && "There are no uses of the alloca!"); 248 249 // Uses of the uninitialized memory location shall get zero... 250 Value *CurVal = Constant::getNullValue(AI->getAllocatedType()); 251 252 BasicBlock *BB = cast<Instruction>(AI->use_back())->getParent(); 253 254 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 255 Instruction *Inst = I++; 256 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 257 if (LI->getOperand(0) == AI) { 258 // Loads just return the "current value"... 259 LI->replaceAllUsesWith(CurVal); 260 BB->getInstList().erase(LI); 261 } 262 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 263 if (SI->getOperand(1) == AI) { 264 // Loads just update the "current value"... 265 CurVal = SI->getOperand(0); 266 BB->getInstList().erase(SI); 267 } 268 } 269 } 270 271 // After traversing the basic block, there should be no more uses of the 272 // alloca, remove it now. 273 assert(AI->use_empty() && "Uses of alloca from more than one BB??"); 274 AI->getParent()->getInstList().erase(AI); 275} 276 277// QueuePhiNode - queues a phi-node to be added to a basic-block for a specific 278// Alloca returns true if there wasn't already a phi-node for that variable 279// 280bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo, 281 unsigned &Version) { 282 // Look up the basic-block in question 283 std::vector<PHINode*> &BBPNs = NewPhiNodes[BB]; 284 if (BBPNs.empty()) BBPNs.resize(Allocas.size()); 285 286 // If the BB already has a phi node added for the i'th alloca then we're done! 287 if (BBPNs[AllocaNo]) return false; 288 289 // Create a PhiNode using the dereferenced type... and add the phi-node to the 290 // BasicBlock. 291 BBPNs[AllocaNo] = new PHINode(Allocas[AllocaNo]->getAllocatedType(), 292 Allocas[AllocaNo]->getName() + "." + 293 utostr(Version++), BB->begin()); 294 return true; 295} 296 297void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred, 298 std::vector<Value*> &IncomingVals) { 299 300 // If this BB needs a PHI node, update the PHI node for each variable we need 301 // PHI nodes for. 302 std::map<BasicBlock*, std::vector<PHINode *> >::iterator 303 BBPNI = NewPhiNodes.find(BB); 304 if (BBPNI != NewPhiNodes.end()) { 305 std::vector<PHINode *> &BBPNs = BBPNI->second; 306 for (unsigned k = 0; k != BBPNs.size(); ++k) 307 if (PHINode *PN = BBPNs[k]) { 308 // Add this incoming value to the PHI node. 309 PN->addIncoming(IncomingVals[k], Pred); 310 311 // The currently active variable for this block is now the PHI. 312 IncomingVals[k] = PN; 313 } 314 } 315 316 // don't revisit nodes 317 if (Visited.count(BB)) return; 318 319 // mark as visited 320 Visited.insert(BB); 321 322 for (BasicBlock::iterator II = BB->begin(); !isa<TerminatorInst>(II); ) { 323 Instruction *I = II++; // get the instruction, increment iterator 324 325 if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 326 if (AllocaInst *Src = dyn_cast<AllocaInst>(LI->getPointerOperand())) { 327 std::map<AllocaInst*, unsigned>::iterator AI = AllocaLookup.find(Src); 328 if (AI != AllocaLookup.end()) { 329 Value *V = IncomingVals[AI->second]; 330 331 // walk the use list of this load and replace all uses with r 332 LI->replaceAllUsesWith(V); 333 BB->getInstList().erase(LI); 334 } 335 } 336 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 337 // Delete this instruction and mark the name as the current holder of the 338 // value 339 if (AllocaInst *Dest = dyn_cast<AllocaInst>(SI->getPointerOperand())) { 340 std::map<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Dest); 341 if (ai != AllocaLookup.end()) { 342 // what value were we writing? 343 IncomingVals[ai->second] = SI->getOperand(0); 344 BB->getInstList().erase(SI); 345 } 346 } 347 } 348 } 349 350 // Recurse to our successors 351 TerminatorInst *TI = BB->getTerminator(); 352 for (unsigned i = 0; i != TI->getNumSuccessors(); i++) { 353 std::vector<Value*> OutgoingVals(IncomingVals); 354 RenamePass(TI->getSuccessor(i), BB, OutgoingVals); 355 } 356} 357 358/// PromoteMemToReg - Promote the specified list of alloca instructions into 359/// scalar registers, inserting PHI nodes as appropriate. This function makes 360/// use of DominanceFrontier information. This function does not modify the CFG 361/// of the function at all. All allocas must be from the same function. 362/// 363void PromoteMemToReg(const std::vector<AllocaInst*> &Allocas, 364 DominatorTree &DT, DominanceFrontier &DF, 365 const TargetData &TD) { 366 // If there is nothing to do, bail out... 367 if (Allocas.empty()) return; 368 PromoteMem2Reg(Allocas, DF, TD).run(); 369} 370