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/Transforms/Utils/Local.h" 00028 #include "llvm/Support/CFG.h" 00029 #include "llvm/Support/StableBasicBlockNumbering.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 PromoteMem2Reg { 00057 /// Allocas - The alloca instructions being promoted. 00058 /// 00059 std::vector<AllocaInst*> Allocas; 00060 DominatorTree &DT; 00061 DominanceFrontier &DF; 00062 const TargetData &TD; 00063 00064 /// AST - An AliasSetTracker object to update. If null, don't update it. 00065 /// 00066 AliasSetTracker *AST; 00067 00068 /// AllocaLookup - Reverse mapping of Allocas. 00069 /// 00070 std::map<AllocaInst*, unsigned> AllocaLookup; 00071 00072 /// NewPhiNodes - The PhiNodes we're adding. 00073 /// 00074 std::map<BasicBlock*, std::vector<PHINode*> > NewPhiNodes; 00075 00076 /// PointerAllocaValues - If we are updating an AliasSetTracker, then for 00077 /// each alloca that is of pointer type, we keep track of what to copyValue 00078 /// to the inserted PHI nodes here. 00079 /// 00080 std::vector<Value*> PointerAllocaValues; 00081 00082 /// Visited - The set of basic blocks the renamer has already visited. 00083 /// 00084 std::set<BasicBlock*> Visited; 00085 00086 /// BBNumbers - Contains a stable numbering of basic blocks to avoid 00087 /// non-determinstic behavior. 00088 StableBasicBlockNumbering BBNumbers; 00089 00090 public: 00091 PromoteMem2Reg(const std::vector<AllocaInst*> &A, DominatorTree &dt, 00092 DominanceFrontier &df, const TargetData &td, 00093 AliasSetTracker *ast) 00094 : Allocas(A), DT(dt), DF(df), TD(td), AST(ast) {} 00095 00096 void run(); 00097 00098 /// dominates - Return true if I1 dominates I2 using the DominatorTree. 00099 /// 00100 bool dominates(Instruction *I1, Instruction *I2) const { 00101 if (InvokeInst *II = dyn_cast<InvokeInst>(I1)) 00102 I1 = II->getNormalDest()->begin(); 00103 return DT[I1->getParent()]->dominates(DT[I2->getParent()]); 00104 } 00105 00106 private: 00107 void MarkDominatingPHILive(BasicBlock *BB, unsigned AllocaNum, 00108 std::set<PHINode*> &DeadPHINodes); 00109 void PromoteLocallyUsedAlloca(BasicBlock *BB, AllocaInst *AI); 00110 void PromoteLocallyUsedAllocas(BasicBlock *BB, 00111 const std::vector<AllocaInst*> &AIs); 00112 00113 void RenamePass(BasicBlock *BB, BasicBlock *Pred, 00114 std::vector<Value*> &IncVals); 00115 bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version, 00116 std::set<PHINode*> &InsertedPHINodes); 00117 }; 00118 } // end of anonymous namespace 00119 00120 void PromoteMem2Reg::run() { 00121 Function &F = *DF.getRoot()->getParent(); 00122 00123 // LocallyUsedAllocas - Keep track of all of the alloca instructions which are 00124 // only used in a single basic block. These instructions can be efficiently 00125 // promoted by performing a single linear scan over that one block. Since 00126 // individual basic blocks are sometimes large, we group together all allocas 00127 // that are live in a single basic block by the basic block they are live in. 00128 std::map<BasicBlock*, std::vector<AllocaInst*> > LocallyUsedAllocas; 00129 00130 if (AST) PointerAllocaValues.resize(Allocas.size()); 00131 00132 for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) { 00133 AllocaInst *AI = Allocas[AllocaNum]; 00134 00135 assert(isAllocaPromotable(AI, TD) && 00136 "Cannot promote non-promotable alloca!"); 00137 assert(AI->getParent()->getParent() == &F && 00138 "All allocas should be in the same function, which is same as DF!"); 00139 00140 if (AI->use_empty()) { 00141 // If there are no uses of the alloca, just delete it now. 00142 if (AST) AST->deleteValue(AI); 00143 AI->getParent()->getInstList().erase(AI); 00144 00145 // Remove the alloca from the Allocas list, since it has been processed 00146 Allocas[AllocaNum] = Allocas.back(); 00147 Allocas.pop_back(); 00148 --AllocaNum; 00149 continue; 00150 } 00151 00152 // Calculate the set of read and write-locations for each alloca. This is 00153 // analogous to finding the 'uses' and 'definitions' of each variable. 00154 std::vector<BasicBlock*> DefiningBlocks; 00155 std::vector<BasicBlock*> UsingBlocks; 00156 00157 BasicBlock *OnlyBlock = 0; 00158 bool OnlyUsedInOneBlock = true; 00159 00160 // As we scan the uses of the alloca instruction, keep track of stores, and 00161 // decide whether all of the loads and stores to the alloca are within the 00162 // same basic block. 00163 Value *AllocaPointerVal = 0; 00164 for (Value::use_iterator U =AI->use_begin(), E = AI->use_end(); U != E;++U){ 00165 Instruction *User = cast<Instruction>(*U); 00166 if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 00167 // Remember the basic blocks which define new values for the alloca 00168 DefiningBlocks.push_back(SI->getParent()); 00169 AllocaPointerVal = SI->getOperand(0); 00170 } else if (LoadInst *LI = dyn_cast<LoadInst>(User)) { 00171 // Otherwise it must be a load instruction, keep track of variable reads 00172 UsingBlocks.push_back(LI->getParent()); 00173 AllocaPointerVal = LI; 00174 } 00175 00176 if (OnlyUsedInOneBlock) { 00177 if (OnlyBlock == 0) 00178 OnlyBlock = User->getParent(); 00179 else if (OnlyBlock != User->getParent()) 00180 OnlyUsedInOneBlock = false; 00181 } 00182 } 00183 00184 // If the alloca is only read and written in one basic block, just perform a 00185 // linear sweep over the block to eliminate it. 00186 if (OnlyUsedInOneBlock) { 00187 LocallyUsedAllocas[OnlyBlock].push_back(AI); 00188 00189 // Remove the alloca from the Allocas list, since it will be processed. 00190 Allocas[AllocaNum] = Allocas.back(); 00191 Allocas.pop_back(); 00192 --AllocaNum; 00193 continue; 00194 } 00195 00196 if (AST) 00197 PointerAllocaValues[AllocaNum] = AllocaPointerVal; 00198 00199 // If we haven't computed a numbering for the BB's in the function, do so 00200 // now. 00201 BBNumbers.compute(F); 00202 00203 // Compute the locations where PhiNodes need to be inserted. Look at the 00204 // dominance frontier of EACH basic-block we have a write in. 00205 // 00206 unsigned CurrentVersion = 0; 00207 std::set<PHINode*> InsertedPHINodes; 00208 std::vector<unsigned> DFBlocks; 00209 while (!DefiningBlocks.empty()) { 00210 BasicBlock *BB = DefiningBlocks.back(); 00211 DefiningBlocks.pop_back(); 00212 00213 // Look up the DF for this write, add it to PhiNodes 00214 DominanceFrontier::const_iterator it = DF.find(BB); 00215 if (it != DF.end()) { 00216 const DominanceFrontier::DomSetType &S = it->second; 00217 00218 // In theory we don't need the indirection through the DFBlocks vector. 00219 // In practice, the order of calling QueuePhiNode would depend on the 00220 // (unspecified) ordering of basic blocks in the dominance frontier, 00221 // which would give PHI nodes non-determinstic subscripts. Fix this by 00222 // processing blocks in order of the occurance in the function. 00223 for (DominanceFrontier::DomSetType::const_iterator P = S.begin(), 00224 PE = S.end(); P != PE; ++P) 00225 DFBlocks.push_back(BBNumbers.getNumber(*P)); 00226 00227 // Sort by which the block ordering in the function. 00228 std::sort(DFBlocks.begin(), DFBlocks.end()); 00229 00230 for (unsigned i = 0, e = DFBlocks.size(); i != e; ++i) { 00231 BasicBlock *BB = BBNumbers.getBlock(DFBlocks[i]); 00232 if (QueuePhiNode(BB, AllocaNum, CurrentVersion, InsertedPHINodes)) 00233 DefiningBlocks.push_back(BB); 00234 } 00235 DFBlocks.clear(); 00236 } 00237 } 00238 00239 // Now that we have inserted PHI nodes along the Iterated Dominance Frontier 00240 // of the writes to the variable, scan through the reads of the variable, 00241 // marking PHI nodes which are actually necessary as alive (by removing them 00242 // from the InsertedPHINodes set). This is not perfect: there may PHI 00243 // marked alive because of loads which are dominated by stores, but there 00244 // will be no unmarked PHI nodes which are actually used. 00245 // 00246 for (unsigned i = 0, e = UsingBlocks.size(); i != e; ++i) 00247 MarkDominatingPHILive(UsingBlocks[i], AllocaNum, InsertedPHINodes); 00248 UsingBlocks.clear(); 00249 00250 // If there are any PHI nodes which are now known to be dead, remove them! 00251 for (std::set<PHINode*>::iterator I = InsertedPHINodes.begin(), 00252 E = InsertedPHINodes.end(); I != E; ++I) { 00253 PHINode *PN = *I; 00254 std::vector<PHINode*> &BBPNs = NewPhiNodes[PN->getParent()]; 00255 BBPNs[AllocaNum] = 0; 00256 00257 // Check to see if we just removed the last inserted PHI node from this 00258 // basic block. If so, remove the entry for the basic block. 00259 bool HasOtherPHIs = false; 00260 for (unsigned i = 0, e = BBPNs.size(); i != e; ++i) 00261 if (BBPNs[i]) { 00262 HasOtherPHIs = true; 00263 break; 00264 } 00265 if (!HasOtherPHIs) 00266 NewPhiNodes.erase(PN->getParent()); 00267 00268 if (AST && isa<PointerType>(PN->getType())) 00269 AST->deleteValue(PN); 00270 PN->getParent()->getInstList().erase(PN); 00271 } 00272 00273 // Keep the reverse mapping of the 'Allocas' array. 00274 AllocaLookup[Allocas[AllocaNum]] = AllocaNum; 00275 } 00276 00277 // Process all allocas which are only used in a single basic block. 00278 for (std::map<BasicBlock*, std::vector<AllocaInst*> >::iterator I = 00279 LocallyUsedAllocas.begin(), E = LocallyUsedAllocas.end(); I != E; ++I){ 00280 const std::vector<AllocaInst*> &Allocas = I->second; 00281 assert(!Allocas.empty() && "empty alloca list??"); 00282 00283 // It's common for there to only be one alloca in the list. Handle it 00284 // efficiently. 00285 if (Allocas.size() == 1) 00286 PromoteLocallyUsedAlloca(I->first, Allocas[0]); 00287 else 00288 PromoteLocallyUsedAllocas(I->first, Allocas); 00289 } 00290 00291 if (Allocas.empty()) 00292 return; // All of the allocas must have been trivial! 00293 00294 // Set the incoming values for the basic block to be null values for all of 00295 // the alloca's. We do this in case there is a load of a value that has not 00296 // been stored yet. In this case, it will get this null value. 00297 // 00298 std::vector<Value *> Values(Allocas.size()); 00299 for (unsigned i = 0, e = Allocas.size(); i != e; ++i) 00300 Values[i] = UndefValue::get(Allocas[i]->getAllocatedType()); 00301 00302 // Walks all basic blocks in the function performing the SSA rename algorithm 00303 // and inserting the phi nodes we marked as necessary 00304 // 00305 RenamePass(F.begin(), 0, Values); 00306 00307 // The renamer uses the Visited set to avoid infinite loops. Clear it now. 00308 Visited.clear(); 00309 00310 // Remove the allocas themselves from the function... 00311 for (unsigned i = 0, e = Allocas.size(); i != e; ++i) { 00312 Instruction *A = Allocas[i]; 00313 00314 // If there are any uses of the alloca instructions left, they must be in 00315 // sections of dead code that were not processed on the dominance frontier. 00316 // Just delete the users now. 00317 // 00318 if (!A->use_empty()) 00319 A->replaceAllUsesWith(UndefValue::get(A->getType())); 00320 if (AST) AST->deleteValue(A); 00321 A->getParent()->getInstList().erase(A); 00322 } 00323 00324 // At this point, the renamer has added entries to PHI nodes for all reachable 00325 // code. Unfortunately, there may be blocks which are not reachable, which 00326 // the renamer hasn't traversed. If this is the case, the PHI nodes may not 00327 // have incoming values for all predecessors. Loop over all PHI nodes we have 00328 // created, inserting undef values if they are missing any incoming values. 00329 // 00330 for (std::map<BasicBlock*, std::vector<PHINode *> >::iterator I = 00331 NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) { 00332 00333 std::vector<BasicBlock*> Preds(pred_begin(I->first), pred_end(I->first)); 00334 std::vector<PHINode*> &PNs = I->second; 00335 assert(!PNs.empty() && "Empty PHI node list??"); 00336 00337 // Loop over all of the PHI nodes and see if there are any that we can get 00338 // rid of because they merge all of the same incoming values. This can 00339 // happen due to undef values coming into the PHI nodes. 00340 PHINode *SomePHI = 0; 00341 for (unsigned i = 0, e = PNs.size(); i != e; ++i) 00342 if (PNs[i]) { 00343 if (Value *V = hasConstantValue(PNs[i])) { 00344 if (!isa<Instruction>(V) || dominates(cast<Instruction>(V), PNs[i])) { 00345 if (AST && isa<PointerType>(PNs[i]->getType())) 00346 AST->deleteValue(PNs[i]); 00347 PNs[i]->replaceAllUsesWith(V); 00348 PNs[i]->eraseFromParent(); 00349 PNs[i] = 0; 00350 } 00351 } 00352 if (PNs[i]) 00353 SomePHI = PNs[i]; 00354 } 00355 00356 // Only do work here if there the PHI nodes are missing incoming values. We 00357 // know that all PHI nodes that were inserted in a block will have the same 00358 // number of incoming values, so we can just check any PHI node. 00359 if (SomePHI && Preds.size() != SomePHI->getNumIncomingValues()) { 00360 // Ok, now we know that all of the PHI nodes are missing entries for some 00361 // basic blocks. Start by sorting the incoming predecessors for efficient 00362 // access. 00363 std::sort(Preds.begin(), Preds.end()); 00364 00365 // Now we loop through all BB's which have entries in SomePHI and remove 00366 // them from the Preds list. 00367 for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) { 00368 // Do a log(n) search of the Preds list for the entry we want. 00369 std::vector<BasicBlock*>::iterator EntIt = 00370 std::lower_bound(Preds.begin(), Preds.end(), 00371 SomePHI->getIncomingBlock(i)); 00372 assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i)&& 00373 "PHI node has entry for a block which is not a predecessor!"); 00374 00375 // Remove the entry 00376 Preds.erase(EntIt); 00377 } 00378 00379 // At this point, the blocks left in the preds list must have dummy 00380 // entries inserted into every PHI nodes for the block. 00381 for (unsigned i = 0, e = PNs.size(); i != e; ++i) 00382 if (PHINode *PN = PNs[i]) { 00383 Value *UndefVal = UndefValue::get(PN->getType()); 00384 for (unsigned pred = 0, e = Preds.size(); pred != e; ++pred) 00385 PN->addIncoming(UndefVal, Preds[pred]); 00386 } 00387 } 00388 } 00389 } 00390 00391 // MarkDominatingPHILive - Mem2Reg wants to construct "pruned" SSA form, not 00392 // "minimal" SSA form. To do this, it inserts all of the PHI nodes on the IDF 00393 // as usual (inserting the PHI nodes in the DeadPHINodes set), then processes 00394 // each read of the variable. For each block that reads the variable, this 00395 // function is called, which removes used PHI nodes from the DeadPHINodes set. 00396 // After all of the reads have been processed, any PHI nodes left in the 00397 // DeadPHINodes set are removed. 00398 // 00399 void PromoteMem2Reg::MarkDominatingPHILive(BasicBlock *BB, unsigned AllocaNum, 00400 std::set<PHINode*> &DeadPHINodes) { 00401 // Scan the immediate dominators of this block looking for a block which has a 00402 // PHI node for Alloca num. If we find it, mark the PHI node as being alive! 00403 for (DominatorTree::Node *N = DT[BB]; N; N = N->getIDom()) { 00404 BasicBlock *DomBB = N->getBlock(); 00405 std::map<BasicBlock*, std::vector<PHINode*> >::iterator 00406 I = NewPhiNodes.find(DomBB); 00407 if (I != NewPhiNodes.end() && I->second[AllocaNum]) { 00408 // Ok, we found an inserted PHI node which dominates this value. 00409 PHINode *DominatingPHI = I->second[AllocaNum]; 00410 00411 // Find out if we previously thought it was dead. 00412 std::set<PHINode*>::iterator DPNI = DeadPHINodes.find(DominatingPHI); 00413 if (DPNI != DeadPHINodes.end()) { 00414 // Ok, until now, we thought this PHI node was dead. Mark it as being 00415 // alive/needed. 00416 DeadPHINodes.erase(DPNI); 00417 00418 // Now that we have marked the PHI node alive, also mark any PHI nodes 00419 // which it might use as being alive as well. 00420 for (pred_iterator PI = pred_begin(DomBB), PE = pred_end(DomBB); 00421 PI != PE; ++PI) 00422 MarkDominatingPHILive(*PI, AllocaNum, DeadPHINodes); 00423 } 00424 } 00425 } 00426 } 00427 00428 /// PromoteLocallyUsedAlloca - Many allocas are only used within a single basic 00429 /// block. If this is the case, avoid traversing the CFG and inserting a lot of 00430 /// potentially useless PHI nodes by just performing a single linear pass over 00431 /// the basic block using the Alloca. 00432 /// 00433 void PromoteMem2Reg::PromoteLocallyUsedAlloca(BasicBlock *BB, AllocaInst *AI) { 00434 assert(!AI->use_empty() && "There are no uses of the alloca!"); 00435 00436 // Handle degenerate cases quickly. 00437 if (AI->hasOneUse()) { 00438 Instruction *U = cast<Instruction>(AI->use_back()); 00439 if (LoadInst *LI = dyn_cast<LoadInst>(U)) { 00440 // Must be a load of uninitialized value. 00441 LI->replaceAllUsesWith(UndefValue::get(AI->getAllocatedType())); 00442 if (AST && isa<PointerType>(LI->getType())) 00443 AST->deleteValue(LI); 00444 } else { 00445 // Otherwise it must be a store which is never read. 00446 assert(isa<StoreInst>(U)); 00447 } 00448 BB->getInstList().erase(U); 00449 } else { 00450 // Uses of the uninitialized memory location shall get undef. 00451 Value *CurVal = UndefValue::get(AI->getAllocatedType()); 00452 00453 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 00454 Instruction *Inst = I++; 00455 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 00456 if (LI->getOperand(0) == AI) { 00457 // Loads just returns the "current value"... 00458 LI->replaceAllUsesWith(CurVal); 00459 if (AST && isa<PointerType>(LI->getType())) 00460 AST->deleteValue(LI); 00461 BB->getInstList().erase(LI); 00462 } 00463 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 00464 if (SI->getOperand(1) == AI) { 00465 // Store updates the "current value"... 00466 CurVal = SI->getOperand(0); 00467 BB->getInstList().erase(SI); 00468 } 00469 } 00470 } 00471 } 00472 00473 // After traversing the basic block, there should be no more uses of the 00474 // alloca, remove it now. 00475 assert(AI->use_empty() && "Uses of alloca from more than one BB??"); 00476 if (AST) AST->deleteValue(AI); 00477 AI->getParent()->getInstList().erase(AI); 00478 } 00479 00480 /// PromoteLocallyUsedAllocas - This method is just like 00481 /// PromoteLocallyUsedAlloca, except that it processes multiple alloca 00482 /// instructions in parallel. This is important in cases where we have large 00483 /// basic blocks, as we don't want to rescan the entire basic block for each 00484 /// alloca which is locally used in it (which might be a lot). 00485 void PromoteMem2Reg:: 00486 PromoteLocallyUsedAllocas(BasicBlock *BB, const std::vector<AllocaInst*> &AIs) { 00487 std::map<AllocaInst*, Value*> CurValues; 00488 for (unsigned i = 0, e = AIs.size(); i != e; ++i) 00489 CurValues[AIs[i]] = 0; // Insert with null value 00490 00491 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) { 00492 Instruction *Inst = I++; 00493 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) { 00494 // Is this a load of an alloca we are tracking? 00495 if (AllocaInst *AI = dyn_cast<AllocaInst>(LI->getOperand(0))) { 00496 std::map<AllocaInst*, Value*>::iterator AIt = CurValues.find(AI); 00497 if (AIt != CurValues.end()) { 00498 // Loads just returns the "current value"... 00499 if (AIt->second == 0) // Uninitialized value?? 00500 AIt->second = UndefValue::get(AIt->first->getAllocatedType()); 00501 LI->replaceAllUsesWith(AIt->second); 00502 if (AST && isa<PointerType>(LI->getType())) 00503 AST->deleteValue(LI); 00504 BB->getInstList().erase(LI); 00505 } 00506 } 00507 } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 00508 if (AllocaInst *AI = dyn_cast<AllocaInst>(SI->getOperand(1))) { 00509 std::map<AllocaInst*, Value*>::iterator AIt = CurValues.find(AI); 00510 if (AIt != CurValues.end()) { 00511 // Store updates the "current value"... 00512 AIt->second = SI->getOperand(0); 00513 BB->getInstList().erase(SI); 00514 } 00515 } 00516 } 00517 } 00518 } 00519 00520 00521 00522 // QueuePhiNode - queues a phi-node to be added to a basic-block for a specific 00523 // Alloca returns true if there wasn't already a phi-node for that variable 00524 // 00525 bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo, 00526 unsigned &Version, 00527 std::set<PHINode*> &InsertedPHINodes) { 00528 // Look up the basic-block in question. 00529 std::vector<PHINode*> &BBPNs = NewPhiNodes[BB]; 00530 if (BBPNs.empty()) BBPNs.resize(Allocas.size()); 00531 00532 // If the BB already has a phi node added for the i'th alloca then we're done! 00533 if (BBPNs[AllocaNo]) return false; 00534 00535 // Create a PhiNode using the dereferenced type... and add the phi-node to the 00536 // BasicBlock. 00537 PHINode *PN = new PHINode(Allocas[AllocaNo]->getAllocatedType(), 00538 Allocas[AllocaNo]->getName() + "." + 00539 utostr(Version++), BB->begin()); 00540 BBPNs[AllocaNo] = PN; 00541 InsertedPHINodes.insert(PN); 00542 00543 if (AST && isa<PointerType>(PN->getType())) 00544 AST->copyValue(PointerAllocaValues[AllocaNo], PN); 00545 00546 return true; 00547 } 00548 00549 00550 // RenamePass - Recursively traverse the CFG of the function, renaming loads and 00551 // stores to the allocas which we are promoting. IncomingVals indicates what 00552 // value each Alloca contains on exit from the predecessor block Pred. 00553 // 00554 void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred, 00555 std::vector<Value*> &IncomingVals) { 00556 00557 // If this BB needs a PHI node, update the PHI node for each variable we need 00558 // PHI nodes for. 00559 std::map<BasicBlock*, std::vector<PHINode *> >::iterator 00560 BBPNI = NewPhiNodes.find(BB); 00561 if (BBPNI != NewPhiNodes.end()) { 00562 std::vector<PHINode *> &BBPNs = BBPNI->second; 00563 for (unsigned k = 0; k != BBPNs.size(); ++k) 00564 if (PHINode *PN = BBPNs[k]) { 00565 // Add this incoming value to the PHI node. 00566 PN->addIncoming(IncomingVals[k], Pred); 00567 00568 // The currently active variable for this block is now the PHI. 00569 IncomingVals[k] = PN; 00570 } 00571 } 00572 00573 // don't revisit nodes 00574 if (Visited.count(BB)) return; 00575 00576 // mark as visited 00577 Visited.insert(BB); 00578 00579 for (BasicBlock::iterator II = BB->begin(); !isa<TerminatorInst>(II); ) { 00580 Instruction *I = II++; // get the instruction, increment iterator 00581 00582 if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 00583 if (AllocaInst *Src = dyn_cast<AllocaInst>(LI->getPointerOperand())) { 00584 std::map<AllocaInst*, unsigned>::iterator AI = AllocaLookup.find(Src); 00585 if (AI != AllocaLookup.end()) { 00586 Value *V = IncomingVals[AI->second]; 00587 00588 // walk the use list of this load and replace all uses with r 00589 LI->replaceAllUsesWith(V); 00590 if (AST && isa<PointerType>(LI->getType())) 00591 AST->deleteValue(LI); 00592 BB->getInstList().erase(LI); 00593 } 00594 } 00595 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 00596 // Delete this instruction and mark the name as the current holder of the 00597 // value 00598 if (AllocaInst *Dest = dyn_cast<AllocaInst>(SI->getPointerOperand())) { 00599 std::map<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Dest); 00600 if (ai != AllocaLookup.end()) { 00601 // what value were we writing? 00602 IncomingVals[ai->second] = SI->getOperand(0); 00603 BB->getInstList().erase(SI); 00604 } 00605 } 00606 } 00607 } 00608 00609 // Recurse to our successors. 00610 TerminatorInst *TI = BB->getTerminator(); 00611 for (unsigned i = 0; i != TI->getNumSuccessors(); i++) { 00612 std::vector<Value*> OutgoingVals(IncomingVals); 00613 RenamePass(TI->getSuccessor(i), BB, OutgoingVals); 00614 } 00615 } 00616 00617 /// PromoteMemToReg - Promote the specified list of alloca instructions into 00618 /// scalar registers, inserting PHI nodes as appropriate. This function makes 00619 /// use of DominanceFrontier information. This function does not modify the CFG 00620 /// of the function at all. All allocas must be from the same function. 00621 /// 00622 /// If AST is specified, the specified tracker is updated to reflect changes 00623 /// made to the IR. 00624 /// 00625 void llvm::PromoteMemToReg(const std::vector<AllocaInst*> &Allocas, 00626 DominatorTree &DT, DominanceFrontier &DF, 00627 const TargetData &TD, AliasSetTracker *AST) { 00628 // If there is nothing to do, bail out... 00629 if (Allocas.empty()) return; 00630 PromoteMem2Reg(Allocas, DT, DF, TD, AST).run(); 00631 }