LLVM API Documentation
00001 //===- PromoteMemoryToRegister.cpp - Convert allocas to registers ---------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file promote memory references to be register references. It promotes 00011 // alloca instructions which only have loads and stores as uses. An alloca is 00012 // transformed by using dominator frontiers to place PHI nodes, then traversing 00013 // the function in depth-first order to rewrite loads and stores as appropriate. 00014 // This is just the standard SSA construction algorithm to construct "pruned" 00015 // SSA form. 00016 // 00017 //===----------------------------------------------------------------------===// 00018 00019 #include "llvm/Transforms/Utils/PromoteMemToReg.h" 00020 #include "llvm/Constants.h" 00021 #include "llvm/DerivedTypes.h" 00022 #include "llvm/Function.h" 00023 #include "llvm/Instructions.h" 00024 #include "llvm/Analysis/Dominators.h" 00025 #include "llvm/Analysis/AliasSetTracker.h" 00026 #include "llvm/ADT/StringExtras.h" 00027 #include "llvm/Support/CFG.h" 00028 #include "llvm/Support/StableBasicBlockNumbering.h" 00029 #include "llvm/Support/Visibility.h" 00030 #include <algorithm> 00031 using namespace llvm; 00032 00033 /// isAllocaPromotable - Return true if this alloca is legal for promotion. 00034 /// This is true if there are only loads and stores to the alloca. 00035 /// 00036 bool llvm::isAllocaPromotable(const AllocaInst *AI, const TargetData &TD) { 00037 // FIXME: If the memory unit is of pointer or integer type, we can permit 00038 // assignments to subsections of the memory unit. 00039 00040 // Only allow direct loads and stores... 00041 for (Value::use_const_iterator UI = AI->use_begin(), UE = AI->use_end(); 00042 UI != UE; ++UI) // Loop over all of the uses of the alloca 00043 if (isa<LoadInst>(*UI)) { 00044 // noop 00045 } else if (const StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 00046 if (SI->getOperand(0) == AI) 00047 return false; // Don't allow a store OF the AI, only INTO the AI. 00048 } else { 00049 return false; // Not a load or store. 00050 } 00051 00052 return true; 00053 } 00054 00055 namespace { 00056 struct VISIBILITY_HIDDEN PromoteMem2Reg { 00057 /// Allocas - The alloca instructions being promoted. 00058 /// 00059 std::vector<AllocaInst*> Allocas; 00060 std::vector<AllocaInst*> &RetryList; 00061 DominatorTree &DT; 00062 DominanceFrontier &DF; 00063 const TargetData &TD; 00064 00065 /// AST - An AliasSetTracker object to update. If null, don't update it. 00066 /// 00067 AliasSetTracker *AST; 00068 00069 /// AllocaLookup - Reverse mapping of Allocas. 00070 /// 00071 std::map<AllocaInst*, unsigned> AllocaLookup; 00072 00073 /// NewPhiNodes - The PhiNodes we're adding. 00074 /// 00075 std::map<BasicBlock*, std::vector<PHINode*> > NewPhiNodes; 00076 00077 /// PointerAllocaValues - If we are updating an AliasSetTracker, then for 00078 /// each alloca that is of pointer type, we keep track of what to copyValue 00079 /// to the inserted PHI nodes here. 00080 /// 00081 std::vector<Value*> PointerAllocaValues; 00082 00083 /// Visited - The set of basic blocks the renamer has already visited. 00084 /// 00085 std::set<BasicBlock*> Visited; 00086 00087 /// BBNumbers - Contains a stable numbering of basic blocks to avoid 00088 /// non-determinstic behavior. 00089 StableBasicBlockNumbering BBNumbers; 00090 00091 public: 00092 PromoteMem2Reg(const std::vector<AllocaInst*> &A, 00093 std::vector<AllocaInst*> &Retry, DominatorTree &dt, 00094 DominanceFrontier &df, const TargetData &td, 00095 AliasSetTracker *ast) 00096 : Allocas(A), RetryList(Retry), DT(dt), DF(df), TD(td), AST(ast) {} 00097 00098 void run(); 00099 00100 /// properlyDominates - Return true if I1 properly dominates I2. 00101 /// 00102 bool properlyDominates(Instruction *I1, Instruction *I2) const { 00103 if (InvokeInst *II = dyn_cast<InvokeInst>(I1)) 00104 I1 = II->getNormalDest()->begin(); 00105 return DT[I1->getParent()]->properlyDominates(DT[I2->getParent()]); 00106 } 00107 00108 /// dominates - Return true if BB1 dominates BB2 using the DominatorTree. 00109 /// 00110 bool dominates(BasicBlock *BB1, BasicBlock *BB2) const { 00111 return DT[BB1]->dominates(DT[BB2]); 00112 } 00113 00114 private: 00115 void MarkDominatingPHILive(BasicBlock *BB, unsigned AllocaNum, 00116 std::set<PHINode*> &DeadPHINodes); 00117 bool PromoteLocallyUsedAlloca(BasicBlock *BB, AllocaInst *AI); 00118 void PromoteLocallyUsedAllocas(BasicBlock *BB, 00119 const std::vector<AllocaInst*> &AIs); 00120 00121 void RenamePass(BasicBlock *BB, BasicBlock *Pred, 00122 std::vector<Value*> &IncVals); 00123 bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version, 00124 std::set<PHINode*> &InsertedPHINodes); 00125 }; 00126 } // end of anonymous namespace 00127 00128 void PromoteMem2Reg::run() { 00129 Function &F = *DF.getRoot()->getParent(); 00130 00131 // LocallyUsedAllocas - Keep track of all of the alloca instructions which are 00132 // only used in a single basic block. These instructions can be efficiently 00133 // promoted by performing a single linear scan over that one block. Since 00134 // individual basic blocks are sometimes large, we group together all allocas 00135 // that are live in a single basic block by the basic block they are live in. 00136 std::map<BasicBlock*, std::vector<AllocaInst*> > LocallyUsedAllocas; 00137 00138 if (AST) PointerAllocaValues.resize(Allocas.size()); 00139 00140 for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) { 00141 AllocaInst *AI = Allocas[AllocaNum]; 00142 00143 assert(isAllocaPromotable(AI, TD) && 00144 "Cannot promote non-promotable alloca!"); 00145 assert(AI->getParent()->getParent() == &F && 00146 "All allocas should be in the same function, which is same as DF!"); 00147 00148 if (AI->use_empty()) { 00149 // If there are no uses of the alloca, just delete it now. 00150 if (AST) AST->deleteValue(AI); 00151 AI->eraseFromParent(); 00152 00153 // Remove the alloca from the Allocas list, since it has been processed 00154 Allocas[AllocaNum] = Allocas.back(); 00155 Allocas.pop_back(); 00156 --AllocaNum; 00157 continue; 00158 } 00159 00160 // Calculate the set of read and write-locations for each alloca. This is 00161 // analogous to finding the 'uses' and 'definitions' of each variable. 00162 std::vector<BasicBlock*> DefiningBlocks; 00163 std::vector<BasicBlock*> UsingBlocks; 00164 00165 StoreInst *OnlyStore = 0; 00166 BasicBlock *OnlyBlock = 0; 00167 bool OnlyUsedInOneBlock = true; 00168 00169 // As we scan the uses of the alloca instruction, keep track of stores, and 00170 // decide whether all of the loads and stores to the alloca are within the 00171 // same basic block. 00172 Value *AllocaPointerVal = 0; 00173 for (Value::use_iterator U =AI->use_begin(), E = AI->use_end(); U != E;++U){ 00174 Instruction *User = cast<Instruction>(*U); 00175 if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 00176 // Remember the basic blocks which define new values for the alloca 00177 DefiningBlocks.push_back(SI->getParent()); 00178 AllocaPointerVal = SI->getOperand(0); 00179 OnlyStore = SI; 00180 } else { 00181 LoadInst *LI = cast<LoadInst>(User); 00182 // Otherwise it must be a load instruction, keep track of variable reads 00183 UsingBlocks.push_back(LI->getParent()); 00184 AllocaPointerVal = LI; 00185 } 00186 00187 if (OnlyUsedInOneBlock) { 00188 if (OnlyBlock == 0) 00189 OnlyBlock = User->getParent(); 00190 else if (OnlyBlock != User->getParent()) 00191 OnlyUsedInOneBlock = false; 00192 } 00193 } 00194 00195 // If the alloca is only read and written in one basic block, just perform a 00196 // linear sweep over the block to eliminate it. 00197 if (OnlyUsedInOneBlock) { 00198 LocallyUsedAllocas[OnlyBlock].push_back(AI); 00199 00200 // Remove the alloca from the Allocas list, since it will be processed. 00201 Allocas[AllocaNum] = Allocas.back(); 00202 Allocas.pop_back(); 00203 --AllocaNum; 00204 continue; 00205 } 00206 00207 // If there is only a single store to this value, replace any loads of 00208 // it that are directly dominated by the definition with the value stored. 00209 if (DefiningBlocks.size() == 1) { 00210 // Be aware of loads before the store. 00211 std::set<BasicBlock*> ProcessedBlocks; 00212 for (unsigned i = 0, e = UsingBlocks.size(); i != e; ++i) 00213 // If the store dominates the block and if we haven't processed it yet, 00214 // do so now. 00215 if (dominates(OnlyStore->getParent(), UsingBlocks[i])) 00216 if (ProcessedBlocks.insert(UsingBlocks[i]).second) { 00217 BasicBlock *UseBlock = UsingBlocks[i]; 00218 00219 // If the use and store are in the same block, do a quick scan to 00220 // verify that there are no uses before the store. 00221 if (UseBlock == OnlyStore->getParent()) { 00222 BasicBlock::iterator I = UseBlock->begin(); 00223 for (; &*I != OnlyStore; ++I) { // scan block for store. 00224 if (isa<LoadInst>(I) && I->getOperand(0) == AI) 00225 break; 00226 } 00227 if (&*I != OnlyStore) break; // Do not handle this case. 00228 } 00229 00230 // Otherwise, if this is a different block or if all uses happen 00231 // after the store, do a simple linear scan to replace loads with 00232 // the stored value. 00233 for (BasicBlock::iterator I = UseBlock->begin(),E = UseBlock->end(); 00234 I != E; ) { 00235 if (LoadInst *LI = dyn_cast<LoadInst>(I++)) { 00236 if (LI->getOperand(0) == AI) { 00237 LI->replaceAllUsesWith(OnlyStore->getOperand(0)); 00238 if (AST && isa<PointerType>(LI->getType())) 00239 AST->deleteValue(LI); 00240 LI->eraseFromParent(); 00241 } 00242 } 00243 } 00244 00245 // Finally, remove this block from the UsingBlock set. 00246 UsingBlocks[i] = UsingBlocks.back(); 00247 --i; --e; 00248 } 00249 00250 // Finally, after the scan, check to see if the store is all that is left. 00251 if (UsingBlocks.empty()) { 00252 // The alloca has been processed, move on. 00253 Allocas[AllocaNum] = Allocas.back(); 00254 Allocas.pop_back(); 00255 --AllocaNum; 00256 continue; 00257 } 00258 } 00259 00260 00261 if (AST) 00262 PointerAllocaValues[AllocaNum] = AllocaPointerVal; 00263 00264 // If we haven't computed a numbering for the BB's in the function, do so 00265 // now. 00266 BBNumbers.compute(F); 00267 00268 // Compute the locations where PhiNodes need to be inserted. Look at the 00269 // dominance frontier of EACH basic-block we have a write in. 00270 // 00271 unsigned CurrentVersion = 0; 00272 std::set<PHINode*> InsertedPHINodes; 00273 std::vector<unsigned> DFBlocks; 00274 while (!DefiningBlocks.empty()) { 00275 BasicBlock *BB = DefiningBlocks.back(); 00276 DefiningBlocks.pop_back(); 00277 00278 // Look up the DF for this write, add it to PhiNodes 00279 DominanceFrontier::const_iterator it = DF.find(BB); 00280 if (it != DF.end()) { 00281 const DominanceFrontier::DomSetType &S = it->second; 00282 00283 // In theory we don't need the indirection through the DFBlocks vector. 00284 // In practice, the order of calling QueuePhiNode would depend on the 00285 // (unspecified) ordering of basic blocks in the dominance frontier, 00286 // which would give PHI nodes non-determinstic subscripts. Fix this by 00287 // processing blocks in order of the occurance in the function. 00288 for (DominanceFrontier::DomSetType::const_iterator P = S.begin(), 00289 PE = S.end(); P != PE; ++P) 00290 DFBlocks.push_back(BBNumbers.getNumber(*P)); 00291 00292 // Sort by which the block ordering in the function. 00293 std::sort(DFBlocks.begin(), DFBlocks.end()); 00294 00295 for (unsigned i = 0, e = DFBlocks.size(); i != e; ++i) { 00296 BasicBlock *BB = BBNumbers.getBlock(DFBlocks[i]); 00297 if (QueuePhiNode(BB, AllocaNum, CurrentVersion, InsertedPHINodes)) 00298 DefiningBlocks.push_back(BB); 00299 } 00300 DFBlocks.clear(); 00301 } 00302 } 00303 00304 // Now that we have inserted PHI nodes along the Iterated Dominance Frontier 00305 // of the writes to the variable, scan through the reads of the variable, 00306 // marking PHI nodes which are actually necessary as alive (by removing them 00307 // from the InsertedPHINodes set). This is not perfect: there may PHI 00308 // marked alive because of loads which are dominated by stores, but there 00309 // will be no unmarked PHI nodes which are actually used. 00310 // 00311 for (unsigned i = 0, e = UsingBlocks.size(); i != e; ++i) 00312 MarkDominatingPHILive(UsingBlocks[i], AllocaNum, InsertedPHINodes); 00313 UsingBlocks.clear(); 00314 00315 // If there are any PHI nodes which are now known to be dead, remove them! 00316 for (std::set<PHINode*>::iterator I = InsertedPHINodes.begin(), 00317 E = InsertedPHINodes.end(); I != E; ++I) { 00318 PHINode *PN = *I; 00319 std::vector<PHINode*> &BBPNs = NewPhiNodes[PN->getParent()]; 00320 BBPNs[AllocaNum] = 0; 00321 00322 // Check to see if we just removed the last inserted PHI node from this 00323 // basic block. If so, remove the entry for the basic block. 00324 bool HasOtherPHIs = false; 00325 for (unsigned i = 0, e = BBPNs.size(); i != e; ++i) 00326 if (BBPNs[i]) { 00327 HasOtherPHIs = true; 00328 break; 00329 } 00330 if (!HasOtherPHIs) 00331 NewPhiNodes.erase(PN->getParent()); 00332 00333 if (AST && isa<PointerType>(PN->getType())) 00334 AST->deleteValue(PN); 00335 PN->eraseFromParent(); 00336 } 00337 00338 // Keep the reverse mapping of the 'Allocas' array. 00339 AllocaLookup[Allocas[AllocaNum]] = AllocaNum; 00340 } 00341 00342 // Process all allocas which are only used in a single basic block. 00343 for (std::map<BasicBlock*, std::vector<AllocaInst*> >::iterator I = 00344 LocallyUsedAllocas.begin(), E = LocallyUsedAllocas.end(); I != E; ++I){ 00345 const std::vector<AllocaInst*> &LocAllocas = I->second; 00346 assert(!LocAllocas.empty() && "empty alloca list??"); 00347 00348 // It's common for there to only be one alloca in the list. Handle it 00349 // efficiently. 00350 if (LocAllocas.size() == 1) { 00351 // If we can do the quick promotion pass, do so now. 00352 if (PromoteLocallyUsedAlloca(I->first, LocAllocas[0])) 00353 RetryList.push_back(LocAllocas[0]); // Failed, retry later. 00354 } else { 00355 // Locally promote anything possible. Note that if this is unable to 00356 // promote a particular alloca, it puts the alloca onto the Allocas vector 00357 // for global processing. 00358 PromoteLocallyUsedAllocas(I->first, LocAllocas); 00359 } 00360 } 00361 00362 if (Allocas.empty()) 00363 return; // All of the allocas must have been trivial! 00364 00365 // Set the incoming values for the basic block to be null values for all of 00366 // the alloca's. We do this in case there is a load of a value that has not 00367 // been stored yet. In this case, it will get this null value. 00368 // 00369 std::vector<Value *> Values(Allocas.size()); 00370 for (unsigned i = 0, e = Allocas.size(); i != e; ++i) 00371 Values[i] = UndefValue::get(Allocas[i]->getAllocatedType()); 00372 00373 // Walks all basic blocks in the function performing the SSA rename algorithm 00374 // and inserting the phi nodes we marked as necessary 00375 // 00376 RenamePass(F.begin(), 0, Values); 00377 00378 // The renamer uses the Visited set to avoid infinite loops. Clear it now. 00379 Visited.clear(); 00380 00381 // Remove the allocas themselves from the function. 00382 for (unsigned i = 0, e = Allocas.size(); i != e; ++i) { 00383 Instruction *A = Allocas[i]; 00384 00385 // If there are any uses of the alloca instructions left, they must be in 00386 // sections of dead code that were not processed on the dominance frontier. 00387 // Just delete the users now. 00388 // 00389 if (!A->use_empty()) 00390 A->replaceAllUsesWith(UndefValue::get(A->getType())); 00391 if (AST) AST->deleteValue(A); 00392 A->eraseFromParent(); 00393 } 00394 00395 00396 // Loop over all of the PHI nodes and see if there are any that we can get 00397 // rid of because they merge all of the same incoming values. This can 00398 // happen due to undef values coming into the PHI nodes. This process is 00399 // iterative, because eliminating one PHI node can cause others to be removed. 00400 bool EliminatedAPHI = true; 00401 while (EliminatedAPHI) { 00402 EliminatedAPHI = false; 00403 00404 for (std::map<BasicBlock*, std::vector<PHINode *> >::iterator I = 00405 NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) { 00406 std::vector<PHINode*> &PNs = I->second; 00407 for (unsigned i = 0, e = PNs.size(); i != e; ++i) { 00408 if (!PNs[i]) continue; 00409 00410 // If this PHI node merges one value and/or undefs, get the value. 00411 if (Value *V = PNs[i]->hasConstantValue(true)) { 00412 if (!isa<Instruction>(V) || 00413 properlyDominates(cast<Instruction>(V), PNs[i])) { 00414 if (AST && isa<PointerType>(PNs[i]->getType())) 00415 AST->deleteValue(PNs[i]); 00416 PNs[i]->replaceAllUsesWith(V); 00417 PNs[i]->eraseFromParent(); 00418 PNs[i] = 0; 00419 EliminatedAPHI = true; 00420 continue; 00421 } 00422 } 00423 } 00424 } 00425 } 00426 00427 // At this point, the renamer has added entries to PHI nodes for all reachable 00428 // code. Unfortunately, there may be blocks which are not reachable, which 00429 // the renamer hasn't traversed. If this is the case, the PHI nodes may not 00430 // have incoming values for all predecessors. Loop over all PHI nodes we have 00431 // created, inserting undef values if they are missing any incoming values. 00432 // 00433 for (std::map<BasicBlock*, std::vector<PHINode *> >::iterator I = 00434 NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) { 00435 00436 std::vector<BasicBlock*> Preds(pred_begin(I->first), pred_end(I->first)); 00437 std::vector<PHINode*> &PNs = I->second; 00438 assert(!PNs.empty() && "Empty PHI node list??"); 00439 PHINode *SomePHI = 0; 00440 for (unsigned i = 0, e = PNs.size(); i != e; ++i) 00441 if (PNs[i]) { 00442 SomePHI = PNs[i]; 00443 break; 00444 } 00445 00446 // Only do work here if there the PHI nodes are missing incoming values. We 00447 // know that all PHI nodes that were inserted in a block will have the same 00448 // number of incoming values, so we can just check any PHI node. 00449 if (SomePHI && Preds.size() != SomePHI->getNumIncomingValues()) { 00450 // Ok, now we know that all of the PHI nodes are missing entries for some 00451 // basic blocks. Start by sorting the incoming predecessors for efficient 00452 // access. 00453 std::sort(Preds.begin(), Preds.end()); 00454 00455 // Now we loop through all BB's which have entries in SomePHI and remove 00456 // them from the Preds list. 00457 for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) { 00458 // Do a log(n) search of the Preds list for the entry we want. 00459 std::vector<BasicBlock*>::iterator EntIt = 00460 std::lower_bound(Preds.begin(), Preds.end(), 00461 SomePHI->getIncomingBlock(i)); 00462 assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i)&& 00463 "PHI node has entry for a block which is not a predecessor!"); 00464 00465 // Remove the entry 00466 Preds.erase(EntIt); 00467 } 00468 00469 // At this point, the blocks left in the preds list must have dummy 00470 // entries inserted into every PHI nodes for the block. 00471 for (unsigned i = 0, e = PNs.size(); i != e; ++i) 00472 if (PHINode *PN = PNs[i]) { 00473 Value *UndefVal = UndefValue::get(PN->getType()); 00474 for (unsigned pred = 0, e = Preds.size(); pred != e; ++pred) 00475 PN->addIncoming(UndefVal, Preds[pred]); 00476 } 00477 } 00478 } 00479 } 00480 00481 // MarkDominatingPHILive - Mem2Reg wants to construct "pruned" SSA form, not 00482 // "minimal" SSA form. To do this, it inserts all of the PHI nodes on the IDF 00483 // as usual (inserting the PHI nodes in the DeadPHINodes set), then processes 00484 // each read of the variable. For each block that reads the variable, this 00485 // function is called, which removes used PHI nodes from the DeadPHINodes set. 00486 // After all of the reads have been processed, any PHI nodes left in the 00487 // DeadPHINodes set are removed. 00488 // 00489 void PromoteMem2Reg::MarkDominatingPHILive(BasicBlock *BB, unsigned AllocaNum, 00490 std::set<PHINode*> &DeadPHINodes) { 00491 // Scan the immediate dominators of this block looking for a block which has a 00492 // PHI node for Alloca num. If we find it, mark the PHI node as being alive! 00493 for (DominatorTree::Node *N = DT[BB]; N; N = N->getIDom()) { 00494 BasicBlock *DomBB = N->getBlock(); 00495 std::map<BasicBlock*, std::vector<PHINode*> >::iterator 00496 I = NewPhiNodes.find(DomBB); 00497 if (I != NewPhiNodes.end() && I->second[AllocaNum]) { 00498 // Ok, we found an inserted PHI node which dominates this value. 00499 PHINode *DominatingPHI = I->second[AllocaNum]; 00500 00501 // Find out if we previously thought it was dead. 00502 std::set<PHINode*>::iterator DPNI = DeadPHINodes.find(DominatingPHI); 00503 if (DPNI != DeadPHINodes.end()) { 00504 // Ok, until now, we thought this PHI node was dead. Mark it as being 00505 // alive/needed. 00506 DeadPHINodes.erase(DPNI); 00507 00508 // Now that we have marked the PHI node alive, also mark any PHI nodes 00509 // which it might use as being alive as well. 00510 for (pred_iterator PI = pred_begin(DomBB), PE = pred_end(DomBB); 00511 PI != PE; ++PI) 00512 MarkDominatingPHILive(*PI, AllocaNum, DeadPHINodes); 00513 } 00514 } 00515 } 00516 } 00517 00518 /// PromoteLocallyUsedAlloca - Many allocas are only used within a single basic 00519 /// block. If this is the case, avoid traversing the CFG and inserting a lot of 00520 /// potentially useless PHI nodes by just performing a single linear pass over 00521 /// the basic block using the Alloca. 00522 /// 00523 /// If we cannot promote this alloca (because it is read before it is written), 00524 /// return true. This is necessary in cases where, due to control flow, the 00525 /// alloca is potentially undefined on some control flow paths. e.g. code like 00526 /// this is potentially correct: 00527 /// 00528 /// for (...) { if (c) { A = undef; undef = B; } } 00529 /// 00530 /// ... so long as A is not used before undef is set. 00531 /// 00532 bool PromoteMem2Reg::PromoteLocallyUsedAlloca(BasicBlock *BB, AllocaInst *AI) { 00533 assert(!AI->use_empty() && "There are no uses of the alloca!"); 00534 00535 // Handle degenerate cases quickly. 00536 if (AI->hasOneUse()) { 00537 Instruction *U = cast<Instruction>(AI->use_back()); 00538 if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 00539 // Must be a load of uninitialized value. 00540 LI->replaceAllUsesWith(UndefValue::get(AI->getAllocatedType())); 00541 if (AST && isa<PointerType>(LI->getType())) 00542 AST->deleteValue(LI); 00543 } else { 00544 // Otherwise it must be a store which is never read. 00545 assert(isa<StoreInst>(U)); 00546 } 00547 BB->getInstList().erase(U); 00548 } else { 00549 // Uses of the uninitialized memory location shall get undef. 00550 Value *CurVal = 0; 00551 00552 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 00553 Instruction *Inst = I++; 00554 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 00555 if (LI->getOperand(0) == AI) { 00556 if (!CurVal) return true; // Could not locally promote! 00557 00558 // Loads just returns the "current value"... 00559 LI->replaceAllUsesWith(CurVal); 00560 if (AST && isa<PointerType>(LI->getType())) 00561 AST->deleteValue(LI); 00562 BB->getInstList().erase(LI); 00563 } 00564 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 00565 if (SI->getOperand(1) == AI) { 00566 // Store updates the "current value"... 00567 CurVal = SI->getOperand(0); 00568 BB->getInstList().erase(SI); 00569 } 00570 } 00571 } 00572 } 00573 00574 // After traversing the basic block, there should be no more uses of the 00575 // alloca, remove it now. 00576 assert(AI->use_empty() && "Uses of alloca from more than one BB??"); 00577 if (AST) AST->deleteValue(AI); 00578 AI->getParent()->getInstList().erase(AI); 00579 return false; 00580 } 00581 00582 /// PromoteLocallyUsedAllocas - This method is just like 00583 /// PromoteLocallyUsedAlloca, except that it processes multiple alloca 00584 /// instructions in parallel. This is important in cases where we have large 00585 /// basic blocks, as we don't want to rescan the entire basic block for each 00586 /// alloca which is locally used in it (which might be a lot). 00587 void PromoteMem2Reg:: 00588 PromoteLocallyUsedAllocas(BasicBlock *BB, const std::vector<AllocaInst*> &AIs) { 00589 std::map<AllocaInst*, Value*> CurValues; 00590 for (unsigned i = 0, e = AIs.size(); i != e; ++i) 00591 CurValues[AIs[i]] = 0; // Insert with null value 00592 00593 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 00594 Instruction *Inst = I++; 00595 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 00596 // Is this a load of an alloca we are tracking? 00597 if (AllocaInst *AI = dyn_cast<AllocaInst>(LI->getOperand(0))) { 00598 std::map<AllocaInst*, Value*>::iterator AIt = CurValues.find(AI); 00599 if (AIt != CurValues.end()) { 00600 // If loading an uninitialized value, allow the inter-block case to 00601 // handle it. Due to control flow, this might actually be ok. 00602 if (AIt->second == 0) { // Use of locally uninitialized value?? 00603 RetryList.push_back(AI); // Retry elsewhere. 00604 CurValues.erase(AIt); // Stop tracking this here. 00605 if (CurValues.empty()) return; 00606 } else { 00607 // Loads just returns the "current value"... 00608 LI->replaceAllUsesWith(AIt->second); 00609 if (AST && isa<PointerType>(LI->getType())) 00610 AST->deleteValue(LI); 00611 BB->getInstList().erase(LI); 00612 } 00613 } 00614 } 00615 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 00616 if (AllocaInst *AI = dyn_cast<AllocaInst>(SI->getOperand(1))) { 00617 std::map<AllocaInst*, Value*>::iterator AIt = CurValues.find(AI); 00618 if (AIt != CurValues.end()) { 00619 // Store updates the "current value"... 00620 AIt->second = SI->getOperand(0); 00621 BB->getInstList().erase(SI); 00622 } 00623 } 00624 } 00625 } 00626 } 00627 00628 00629 00630 // QueuePhiNode - queues a phi-node to be added to a basic-block for a specific 00631 // Alloca returns true if there wasn't already a phi-node for that variable 00632 // 00633 bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo, 00634 unsigned &Version, 00635 std::set<PHINode*> &InsertedPHINodes) { 00636 // Look up the basic-block in question. 00637 std::vector<PHINode*> &BBPNs = NewPhiNodes[BB]; 00638 if (BBPNs.empty()) BBPNs.resize(Allocas.size()); 00639 00640 // If the BB already has a phi node added for the i'th alloca then we're done! 00641 if (BBPNs[AllocaNo]) return false; 00642 00643 // Create a PhiNode using the dereferenced type... and add the phi-node to the 00644 // BasicBlock. 00645 PHINode *PN = new PHINode(Allocas[AllocaNo]->getAllocatedType(), 00646 Allocas[AllocaNo]->getName() + "." + 00647 utostr(Version++), BB->begin()); 00648 BBPNs[AllocaNo] = PN; 00649 InsertedPHINodes.insert(PN); 00650 00651 if (AST && isa<PointerType>(PN->getType())) 00652 AST->copyValue(PointerAllocaValues[AllocaNo], PN); 00653 00654 return true; 00655 } 00656 00657 00658 // RenamePass - Recursively traverse the CFG of the function, renaming loads and 00659 // stores to the allocas which we are promoting. IncomingVals indicates what 00660 // value each Alloca contains on exit from the predecessor block Pred. 00661 // 00662 void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred, 00663 std::vector<Value*> &IncomingVals) { 00664 00665 // If this BB needs a PHI node, update the PHI node for each variable we need 00666 // PHI nodes for. 00667 std::map<BasicBlock*, std::vector<PHINode *> >::iterator 00668 BBPNI = NewPhiNodes.find(BB); 00669 if (BBPNI != NewPhiNodes.end()) { 00670 std::vector<PHINode *> &BBPNs = BBPNI->second; 00671 for (unsigned k = 0; k != BBPNs.size(); ++k) 00672 if (PHINode *PN = BBPNs[k]) { 00673 // Add this incoming value to the PHI node. 00674 PN->addIncoming(IncomingVals[k], Pred); 00675 00676 // The currently active variable for this block is now the PHI. 00677 IncomingVals[k] = PN; 00678 } 00679 } 00680 00681 // don't revisit nodes 00682 if (Visited.count(BB)) return; 00683 00684 // mark as visited 00685 Visited.insert(BB); 00686 00687 for (BasicBlock::iterator II = BB->begin(); !isa<TerminatorInst>(II); ) { 00688 Instruction *I = II++; // get the instruction, increment iterator 00689 00690 if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 00691 if (AllocaInst *Src = dyn_cast<AllocaInst>(LI->getPointerOperand())) { 00692 std::map<AllocaInst*, unsigned>::iterator AI = AllocaLookup.find(Src); 00693 if (AI != AllocaLookup.end()) { 00694 Value *V = IncomingVals[AI->second]; 00695 00696 // walk the use list of this load and replace all uses with r 00697 LI->replaceAllUsesWith(V); 00698 if (AST && isa<PointerType>(LI->getType())) 00699 AST->deleteValue(LI); 00700 BB->getInstList().erase(LI); 00701 } 00702 } 00703 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 00704 // Delete this instruction and mark the name as the current holder of the 00705 // value 00706 if (AllocaInst *Dest = dyn_cast<AllocaInst>(SI->getPointerOperand())) { 00707 std::map<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Dest); 00708 if (ai != AllocaLookup.end()) { 00709 // what value were we writing? 00710 IncomingVals[ai->second] = SI->getOperand(0); 00711 BB->getInstList().erase(SI); 00712 } 00713 } 00714 } 00715 } 00716 00717 // Recurse to our successors. 00718 TerminatorInst *TI = BB->getTerminator(); 00719 for (unsigned i = 0; i != TI->getNumSuccessors(); i++) { 00720 std::vector<Value*> OutgoingVals(IncomingVals); 00721 RenamePass(TI->getSuccessor(i), BB, OutgoingVals); 00722 } 00723 } 00724 00725 /// PromoteMemToReg - Promote the specified list of alloca instructions into 00726 /// scalar registers, inserting PHI nodes as appropriate. This function makes 00727 /// use of DominanceFrontier information. This function does not modify the CFG 00728 /// of the function at all. All allocas must be from the same function. 00729 /// 00730 /// If AST is specified, the specified tracker is updated to reflect changes 00731 /// made to the IR. 00732 /// 00733 void llvm::PromoteMemToReg(const std::vector<AllocaInst*> &Allocas, 00734 DominatorTree &DT, DominanceFrontier &DF, 00735 const TargetData &TD, AliasSetTracker *AST) { 00736 // If there is nothing to do, bail out... 00737 if (Allocas.empty()) return; 00738 00739 std::vector<AllocaInst*> RetryList; 00740 PromoteMem2Reg(Allocas, RetryList, DT, DF, TD, AST).run(); 00741 00742 // PromoteMem2Reg may not have been able to promote all of the allocas in one 00743 // pass, run it again if needed. 00744 while (!RetryList.empty()) { 00745 // If we need to retry some allocas, this is due to there being no store 00746 // before a read in a local block. To counteract this, insert a store of 00747 // undef into the alloca right after the alloca itself. 00748 for (unsigned i = 0, e = RetryList.size(); i != e; ++i) { 00749 BasicBlock::iterator BBI = RetryList[i]; 00750 00751 new StoreInst(UndefValue::get(RetryList[i]->getAllocatedType()), 00752 RetryList[i], ++BBI); 00753 } 00754 00755 std::vector<AllocaInst*> NewAllocas; 00756 std::swap(NewAllocas, RetryList); 00757 PromoteMem2Reg(NewAllocas, RetryList, DT, DF, TD, AST).run(); 00758 } 00759 }