LLVM API Documentation
00001 //===- PromoteMemoryToRegister.cpp - Convert allocas to registers ---------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file promotes 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 #define DEBUG_TYPE "mem2reg" 00020 #include "llvm/Transforms/Utils/PromoteMemToReg.h" 00021 #include "llvm/Constants.h" 00022 #include "llvm/DerivedTypes.h" 00023 #include "llvm/Function.h" 00024 #include "llvm/Instructions.h" 00025 #include "llvm/IntrinsicInst.h" 00026 #include "llvm/LLVMContext.h" 00027 #include "llvm/Analysis/Dominators.h" 00028 #include "llvm/Analysis/AliasSetTracker.h" 00029 #include "llvm/ADT/DenseMap.h" 00030 #include "llvm/ADT/SmallPtrSet.h" 00031 #include "llvm/ADT/SmallVector.h" 00032 #include "llvm/ADT/Statistic.h" 00033 #include "llvm/ADT/STLExtras.h" 00034 #include "llvm/Support/CFG.h" 00035 #include "llvm/Support/Compiler.h" 00036 #include <algorithm> 00037 using namespace llvm; 00038 00039 STATISTIC(NumLocalPromoted, "Number of alloca's promoted within one block"); 00040 STATISTIC(NumSingleStore, "Number of alloca's promoted with a single store"); 00041 STATISTIC(NumDeadAlloca, "Number of dead alloca's removed"); 00042 STATISTIC(NumPHIInsert, "Number of PHI nodes inserted"); 00043 00044 // Provide DenseMapInfo for all pointers. 00045 namespace llvm { 00046 template<> 00047 struct DenseMapInfo<std::pair<BasicBlock*, unsigned> > { 00048 typedef std::pair<BasicBlock*, unsigned> EltTy; 00049 static inline EltTy getEmptyKey() { 00050 return EltTy(reinterpret_cast<BasicBlock*>(-1), ~0U); 00051 } 00052 static inline EltTy getTombstoneKey() { 00053 return EltTy(reinterpret_cast<BasicBlock*>(-2), 0U); 00054 } 00055 static unsigned getHashValue(const std::pair<BasicBlock*, unsigned> &Val) { 00056 return DenseMapInfo<void*>::getHashValue(Val.first) + Val.second*2; 00057 } 00058 static bool isEqual(const EltTy &LHS, const EltTy &RHS) { 00059 return LHS == RHS; 00060 } 00061 static bool isPod() { return true; } 00062 }; 00063 } 00064 00065 /// isAllocaPromotable - Return true if this alloca is legal for promotion. 00066 /// This is true if there are only loads and stores to the alloca. 00067 /// 00068 bool llvm::isAllocaPromotable(const AllocaInst *AI) { 00069 // FIXME: If the memory unit is of pointer or integer type, we can permit 00070 // assignments to subsections of the memory unit. 00071 00072 // Only allow direct and non-volatile loads and stores... 00073 for (Value::use_const_iterator UI = AI->use_begin(), UE = AI->use_end(); 00074 UI != UE; ++UI) // Loop over all of the uses of the alloca 00075 if (const LoadInst *LI = dyn_cast<LoadInst>(*UI)) { 00076 if (LI->isVolatile()) 00077 return false; 00078 } else if (const StoreInst *SI = dyn_cast<StoreInst>(*UI)) { 00079 if (SI->getOperand(0) == AI) 00080 return false; // Don't allow a store OF the AI, only INTO the AI. 00081 if (SI->isVolatile()) 00082 return false; 00083 } else if (const BitCastInst *BC = dyn_cast<BitCastInst>(*UI)) { 00084 // A bitcast that does not feed into debug info inhibits promotion. 00085 if (!BC->hasOneUse() || !isa<DbgInfoIntrinsic>(*BC->use_begin())) 00086 return false; 00087 // If the only use is by debug info, this alloca will not exist in 00088 // non-debug code, so don't try to promote; this ensures the same 00089 // codegen with debug info. Otherwise, debug info should not 00090 // inhibit promotion (but we must examine other uses). 00091 if (AI->hasOneUse()) 00092 return false; 00093 } else { 00094 return false; 00095 } 00096 00097 return true; 00098 } 00099 00100 namespace { 00101 struct AllocaInfo; 00102 00103 // Data package used by RenamePass() 00104 class VISIBILITY_HIDDEN RenamePassData { 00105 public: 00106 typedef std::vector<Value *> ValVector; 00107 00108 RenamePassData() {} 00109 RenamePassData(BasicBlock *B, BasicBlock *P, 00110 const ValVector &V) : BB(B), Pred(P), Values(V) {} 00111 BasicBlock *BB; 00112 BasicBlock *Pred; 00113 ValVector Values; 00114 00115 void swap(RenamePassData &RHS) { 00116 std::swap(BB, RHS.BB); 00117 std::swap(Pred, RHS.Pred); 00118 Values.swap(RHS.Values); 00119 } 00120 }; 00121 00122 /// LargeBlockInfo - This assigns and keeps a per-bb relative ordering of 00123 /// load/store instructions in the block that directly load or store an alloca. 00124 /// 00125 /// This functionality is important because it avoids scanning large basic 00126 /// blocks multiple times when promoting many allocas in the same block. 00127 class VISIBILITY_HIDDEN LargeBlockInfo { 00128 /// InstNumbers - For each instruction that we track, keep the index of the 00129 /// instruction. The index starts out as the number of the instruction from 00130 /// the start of the block. 00131 DenseMap<const Instruction *, unsigned> InstNumbers; 00132 public: 00133 00134 /// isInterestingInstruction - This code only looks at accesses to allocas. 00135 static bool isInterestingInstruction(const Instruction *I) { 00136 return (isa<LoadInst>(I) && isa<AllocaInst>(I->getOperand(0))) || 00137 (isa<StoreInst>(I) && isa<AllocaInst>(I->getOperand(1))); 00138 } 00139 00140 /// getInstructionIndex - Get or calculate the index of the specified 00141 /// instruction. 00142 unsigned getInstructionIndex(const Instruction *I) { 00143 assert(isInterestingInstruction(I) && 00144 "Not a load/store to/from an alloca?"); 00145 00146 // If we already have this instruction number, return it. 00147 DenseMap<const Instruction *, unsigned>::iterator It = InstNumbers.find(I); 00148 if (It != InstNumbers.end()) return It->second; 00149 00150 // Scan the whole block to get the instruction. This accumulates 00151 // information for every interesting instruction in the block, in order to 00152 // avoid gratuitus rescans. 00153 const BasicBlock *BB = I->getParent(); 00154 unsigned InstNo = 0; 00155 for (BasicBlock::const_iterator BBI = BB->begin(), E = BB->end(); 00156 BBI != E; ++BBI) 00157 if (isInterestingInstruction(BBI)) 00158 InstNumbers[BBI] = InstNo++; 00159 It = InstNumbers.find(I); 00160 00161 assert(It != InstNumbers.end() && "Didn't insert instruction?"); 00162 return It->second; 00163 } 00164 00165 void deleteValue(const Instruction *I) { 00166 InstNumbers.erase(I); 00167 } 00168 00169 void clear() { 00170 InstNumbers.clear(); 00171 } 00172 }; 00173 00174 struct VISIBILITY_HIDDEN PromoteMem2Reg { 00175 /// Allocas - The alloca instructions being promoted. 00176 /// 00177 std::vector<AllocaInst*> Allocas; 00178 DominatorTree &DT; 00179 DominanceFrontier &DF; 00180 00181 /// AST - An AliasSetTracker object to update. If null, don't update it. 00182 /// 00183 AliasSetTracker *AST; 00184 00185 LLVMContext &Context; 00186 00187 /// AllocaLookup - Reverse mapping of Allocas. 00188 /// 00189 std::map<AllocaInst*, unsigned> AllocaLookup; 00190 00191 /// NewPhiNodes - The PhiNodes we're adding. 00192 /// 00193 DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*> NewPhiNodes; 00194 00195 /// PhiToAllocaMap - For each PHI node, keep track of which entry in Allocas 00196 /// it corresponds to. 00197 DenseMap<PHINode*, unsigned> PhiToAllocaMap; 00198 00199 /// PointerAllocaValues - If we are updating an AliasSetTracker, then for 00200 /// each alloca that is of pointer type, we keep track of what to copyValue 00201 /// to the inserted PHI nodes here. 00202 /// 00203 std::vector<Value*> PointerAllocaValues; 00204 00205 /// Visited - The set of basic blocks the renamer has already visited. 00206 /// 00207 SmallPtrSet<BasicBlock*, 16> Visited; 00208 00209 /// BBNumbers - Contains a stable numbering of basic blocks to avoid 00210 /// non-determinstic behavior. 00211 DenseMap<BasicBlock*, unsigned> BBNumbers; 00212 00213 /// BBNumPreds - Lazily compute the number of predecessors a block has. 00214 DenseMap<const BasicBlock*, unsigned> BBNumPreds; 00215 public: 00216 PromoteMem2Reg(const std::vector<AllocaInst*> &A, DominatorTree &dt, 00217 DominanceFrontier &df, AliasSetTracker *ast, 00218 LLVMContext &C) 00219 : Allocas(A), DT(dt), DF(df), AST(ast), Context(C) {} 00220 00221 void run(); 00222 00223 /// properlyDominates - Return true if I1 properly dominates I2. 00224 /// 00225 bool properlyDominates(Instruction *I1, Instruction *I2) const { 00226 if (InvokeInst *II = dyn_cast<InvokeInst>(I1)) 00227 I1 = II->getNormalDest()->begin(); 00228 return DT.properlyDominates(I1->getParent(), I2->getParent()); 00229 } 00230 00231 /// dominates - Return true if BB1 dominates BB2 using the DominatorTree. 00232 /// 00233 bool dominates(BasicBlock *BB1, BasicBlock *BB2) const { 00234 return DT.dominates(BB1, BB2); 00235 } 00236 00237 private: 00238 void RemoveFromAllocasList(unsigned &AllocaIdx) { 00239 Allocas[AllocaIdx] = Allocas.back(); 00240 Allocas.pop_back(); 00241 --AllocaIdx; 00242 } 00243 00244 unsigned getNumPreds(const BasicBlock *BB) { 00245 unsigned &NP = BBNumPreds[BB]; 00246 if (NP == 0) 00247 NP = std::distance(pred_begin(BB), pred_end(BB))+1; 00248 return NP-1; 00249 } 00250 00251 void DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum, 00252 AllocaInfo &Info); 00253 void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info, 00254 const SmallPtrSet<BasicBlock*, 32> &DefBlocks, 00255 SmallPtrSet<BasicBlock*, 32> &LiveInBlocks); 00256 00257 void RewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info, 00258 LargeBlockInfo &LBI); 00259 void PromoteSingleBlockAlloca(AllocaInst *AI, AllocaInfo &Info, 00260 LargeBlockInfo &LBI); 00261 00262 00263 void RenamePass(BasicBlock *BB, BasicBlock *Pred, 00264 RenamePassData::ValVector &IncVals, 00265 std::vector<RenamePassData> &Worklist); 00266 bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version, 00267 SmallPtrSet<PHINode*, 16> &InsertedPHINodes); 00268 }; 00269 00270 struct AllocaInfo { 00271 std::vector<BasicBlock*> DefiningBlocks; 00272 std::vector<BasicBlock*> UsingBlocks; 00273 00274 StoreInst *OnlyStore; 00275 BasicBlock *OnlyBlock; 00276 bool OnlyUsedInOneBlock; 00277 00278 Value *AllocaPointerVal; 00279 00280 void clear() { 00281 DefiningBlocks.clear(); 00282 UsingBlocks.clear(); 00283 OnlyStore = 0; 00284 OnlyBlock = 0; 00285 OnlyUsedInOneBlock = true; 00286 AllocaPointerVal = 0; 00287 } 00288 00289 /// AnalyzeAlloca - Scan the uses of the specified alloca, filling in our 00290 /// ivars. 00291 void AnalyzeAlloca(AllocaInst *AI) { 00292 clear(); 00293 00294 // As we scan the uses of the alloca instruction, keep track of stores, 00295 // and decide whether all of the loads and stores to the alloca are within 00296 // the same basic block. 00297 for (Value::use_iterator U = AI->use_begin(), E = AI->use_end(); 00298 U != E;) { 00299 Instruction *User = cast<Instruction>(*U); 00300 ++U; 00301 if (BitCastInst *BC = dyn_cast<BitCastInst>(User)) { 00302 // Remove any uses of this alloca in DbgInfoInstrinsics. 00303 assert(BC->hasOneUse() && "Unexpected alloca uses!"); 00304 DbgInfoIntrinsic *DI = cast<DbgInfoIntrinsic>(*BC->use_begin()); 00305 DI->eraseFromParent(); 00306 BC->eraseFromParent(); 00307 continue; 00308 } 00309 else if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 00310 // Remember the basic blocks which define new values for the alloca 00311 DefiningBlocks.push_back(SI->getParent()); 00312 AllocaPointerVal = SI->getOperand(0); 00313 OnlyStore = SI; 00314 } else { 00315 LoadInst *LI = cast<LoadInst>(User); 00316 // Otherwise it must be a load instruction, keep track of variable 00317 // reads. 00318 UsingBlocks.push_back(LI->getParent()); 00319 AllocaPointerVal = LI; 00320 } 00321 00322 if (OnlyUsedInOneBlock) { 00323 if (OnlyBlock == 0) 00324 OnlyBlock = User->getParent(); 00325 else if (OnlyBlock != User->getParent()) 00326 OnlyUsedInOneBlock = false; 00327 } 00328 } 00329 } 00330 }; 00331 } // end of anonymous namespace 00332 00333 00334 void PromoteMem2Reg::run() { 00335 Function &F = *DF.getRoot()->getParent(); 00336 00337 if (AST) PointerAllocaValues.resize(Allocas.size()); 00338 00339 AllocaInfo Info; 00340 LargeBlockInfo LBI; 00341 00342 for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) { 00343 AllocaInst *AI = Allocas[AllocaNum]; 00344 00345 assert(isAllocaPromotable(AI) && 00346 "Cannot promote non-promotable alloca!"); 00347 assert(AI->getParent()->getParent() == &F && 00348 "All allocas should be in the same function, which is same as DF!"); 00349 00350 if (AI->use_empty()) { 00351 // If there are no uses of the alloca, just delete it now. 00352 if (AST) AST->deleteValue(AI); 00353 AI->eraseFromParent(); 00354 00355 // Remove the alloca from the Allocas list, since it has been processed 00356 RemoveFromAllocasList(AllocaNum); 00357 ++NumDeadAlloca; 00358 continue; 00359 } 00360 00361 // Calculate the set of read and write-locations for each alloca. This is 00362 // analogous to finding the 'uses' and 'definitions' of each variable. 00363 Info.AnalyzeAlloca(AI); 00364 00365 // If there is only a single store to this value, replace any loads of 00366 // it that are directly dominated by the definition with the value stored. 00367 if (Info.DefiningBlocks.size() == 1) { 00368 RewriteSingleStoreAlloca(AI, Info, LBI); 00369 00370 // Finally, after the scan, check to see if the store is all that is left. 00371 if (Info.UsingBlocks.empty()) { 00372 // Remove the (now dead) store and alloca. 00373 Info.OnlyStore->eraseFromParent(); 00374 LBI.deleteValue(Info.OnlyStore); 00375 00376 if (AST) AST->deleteValue(AI); 00377 AI->eraseFromParent(); 00378 LBI.deleteValue(AI); 00379 00380 // The alloca has been processed, move on. 00381 RemoveFromAllocasList(AllocaNum); 00382 00383 ++NumSingleStore; 00384 continue; 00385 } 00386 } 00387 00388 // If the alloca is only read and written in one basic block, just perform a 00389 // linear sweep over the block to eliminate it. 00390 if (Info.OnlyUsedInOneBlock) { 00391 PromoteSingleBlockAlloca(AI, Info, LBI); 00392 00393 // Finally, after the scan, check to see if the stores are all that is 00394 // left. 00395 if (Info.UsingBlocks.empty()) { 00396 00397 // Remove the (now dead) stores and alloca. 00398 while (!AI->use_empty()) { 00399 StoreInst *SI = cast<StoreInst>(AI->use_back()); 00400 SI->eraseFromParent(); 00401 LBI.deleteValue(SI); 00402 } 00403 00404 if (AST) AST->deleteValue(AI); 00405 AI->eraseFromParent(); 00406 LBI.deleteValue(AI); 00407 00408 // The alloca has been processed, move on. 00409 RemoveFromAllocasList(AllocaNum); 00410 00411 ++NumLocalPromoted; 00412 continue; 00413 } 00414 } 00415 00416 // If we haven't computed a numbering for the BB's in the function, do so 00417 // now. 00418 if (BBNumbers.empty()) { 00419 unsigned ID = 0; 00420 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 00421 BBNumbers[I] = ID++; 00422 } 00423 00424 // If we have an AST to keep updated, remember some pointer value that is 00425 // stored into the alloca. 00426 if (AST) 00427 PointerAllocaValues[AllocaNum] = Info.AllocaPointerVal; 00428 00429 // Keep the reverse mapping of the 'Allocas' array for the rename pass. 00430 AllocaLookup[Allocas[AllocaNum]] = AllocaNum; 00431 00432 // At this point, we're committed to promoting the alloca using IDF's, and 00433 // the standard SSA construction algorithm. Determine which blocks need PHI 00434 // nodes and see if we can optimize out some work by avoiding insertion of 00435 // dead phi nodes. 00436 DetermineInsertionPoint(AI, AllocaNum, Info); 00437 } 00438 00439 if (Allocas.empty()) 00440 return; // All of the allocas must have been trivial! 00441 00442 LBI.clear(); 00443 00444 00445 // Set the incoming values for the basic block to be null values for all of 00446 // the alloca's. We do this in case there is a load of a value that has not 00447 // been stored yet. In this case, it will get this null value. 00448 // 00449 RenamePassData::ValVector Values(Allocas.size()); 00450 for (unsigned i = 0, e = Allocas.size(); i != e; ++i) 00451 Values[i] = UndefValue::get(Allocas[i]->getAllocatedType()); 00452 00453 // Walks all basic blocks in the function performing the SSA rename algorithm 00454 // and inserting the phi nodes we marked as necessary 00455 // 00456 std::vector<RenamePassData> RenamePassWorkList; 00457 RenamePassWorkList.push_back(RenamePassData(F.begin(), 0, Values)); 00458 while (!RenamePassWorkList.empty()) { 00459 RenamePassData RPD; 00460 RPD.swap(RenamePassWorkList.back()); 00461 RenamePassWorkList.pop_back(); 00462 // RenamePass may add new worklist entries. 00463 RenamePass(RPD.BB, RPD.Pred, RPD.Values, RenamePassWorkList); 00464 } 00465 00466 // The renamer uses the Visited set to avoid infinite loops. Clear it now. 00467 Visited.clear(); 00468 00469 // Remove the allocas themselves from the function. 00470 for (unsigned i = 0, e = Allocas.size(); i != e; ++i) { 00471 Instruction *A = Allocas[i]; 00472 00473 // If there are any uses of the alloca instructions left, they must be in 00474 // sections of dead code that were not processed on the dominance frontier. 00475 // Just delete the users now. 00476 // 00477 if (!A->use_empty()) 00478 A->replaceAllUsesWith(UndefValue::get(A->getType())); 00479 if (AST) AST->deleteValue(A); 00480 A->eraseFromParent(); 00481 } 00482 00483 00484 // Loop over all of the PHI nodes and see if there are any that we can get 00485 // rid of because they merge all of the same incoming values. This can 00486 // happen due to undef values coming into the PHI nodes. This process is 00487 // iterative, because eliminating one PHI node can cause others to be removed. 00488 bool EliminatedAPHI = true; 00489 while (EliminatedAPHI) { 00490 EliminatedAPHI = false; 00491 00492 for (DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*>::iterator I = 00493 NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E;) { 00494 PHINode *PN = I->second; 00495 00496 // If this PHI node merges one value and/or undefs, get the value. 00497 if (Value *V = PN->hasConstantValue(true)) { 00498 if (!isa<Instruction>(V) || 00499 properlyDominates(cast<Instruction>(V), PN)) { 00500 if (AST && isa<PointerType>(PN->getType())) 00501 AST->deleteValue(PN); 00502 PN->replaceAllUsesWith(V); 00503 PN->eraseFromParent(); 00504 NewPhiNodes.erase(I++); 00505 EliminatedAPHI = true; 00506 continue; 00507 } 00508 } 00509 ++I; 00510 } 00511 } 00512 00513 // At this point, the renamer has added entries to PHI nodes for all reachable 00514 // code. Unfortunately, there may be unreachable blocks which the renamer 00515 // hasn't traversed. If this is the case, the PHI nodes may not 00516 // have incoming values for all predecessors. Loop over all PHI nodes we have 00517 // created, inserting undef values if they are missing any incoming values. 00518 // 00519 for (DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*>::iterator I = 00520 NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) { 00521 // We want to do this once per basic block. As such, only process a block 00522 // when we find the PHI that is the first entry in the block. 00523 PHINode *SomePHI = I->second; 00524 BasicBlock *BB = SomePHI->getParent(); 00525 if (&BB->front() != SomePHI) 00526 continue; 00527 00528 // Only do work here if there the PHI nodes are missing incoming values. We 00529 // know that all PHI nodes that were inserted in a block will have the same 00530 // number of incoming values, so we can just check any of them. 00531 if (SomePHI->getNumIncomingValues() == getNumPreds(BB)) 00532 continue; 00533 00534 // Get the preds for BB. 00535 SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB)); 00536 00537 // Ok, now we know that all of the PHI nodes are missing entries for some 00538 // basic blocks. Start by sorting the incoming predecessors for efficient 00539 // access. 00540 std::sort(Preds.begin(), Preds.end()); 00541 00542 // Now we loop through all BB's which have entries in SomePHI and remove 00543 // them from the Preds list. 00544 for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) { 00545 // Do a log(n) search of the Preds list for the entry we want. 00546 SmallVector<BasicBlock*, 16>::iterator EntIt = 00547 std::lower_bound(Preds.begin(), Preds.end(), 00548 SomePHI->getIncomingBlock(i)); 00549 assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i)&& 00550 "PHI node has entry for a block which is not a predecessor!"); 00551 00552 // Remove the entry 00553 Preds.erase(EntIt); 00554 } 00555 00556 // At this point, the blocks left in the preds list must have dummy 00557 // entries inserted into every PHI nodes for the block. Update all the phi 00558 // nodes in this block that we are inserting (there could be phis before 00559 // mem2reg runs). 00560 unsigned NumBadPreds = SomePHI->getNumIncomingValues(); 00561 BasicBlock::iterator BBI = BB->begin(); 00562 while ((SomePHI = dyn_cast<PHINode>(BBI++)) && 00563 SomePHI->getNumIncomingValues() == NumBadPreds) { 00564 Value *UndefVal = UndefValue::get(SomePHI->getType()); 00565 for (unsigned pred = 0, e = Preds.size(); pred != e; ++pred) 00566 SomePHI->addIncoming(UndefVal, Preds[pred]); 00567 } 00568 } 00569 00570 NewPhiNodes.clear(); 00571 } 00572 00573 00574 /// ComputeLiveInBlocks - Determine which blocks the value is live in. These 00575 /// are blocks which lead to uses. Knowing this allows us to avoid inserting 00576 /// PHI nodes into blocks which don't lead to uses (thus, the inserted phi nodes 00577 /// would be dead). 00578 void PromoteMem2Reg:: 00579 ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info, 00580 const SmallPtrSet<BasicBlock*, 32> &DefBlocks, 00581 SmallPtrSet<BasicBlock*, 32> &LiveInBlocks) { 00582 00583 // To determine liveness, we must iterate through the predecessors of blocks 00584 // where the def is live. Blocks are added to the worklist if we need to 00585 // check their predecessors. Start with all the using blocks. 00586 SmallVector<BasicBlock*, 64> LiveInBlockWorklist; 00587 LiveInBlockWorklist.insert(LiveInBlockWorklist.end(), 00588 Info.UsingBlocks.begin(), Info.UsingBlocks.end()); 00589 00590 // If any of the using blocks is also a definition block, check to see if the 00591 // definition occurs before or after the use. If it happens before the use, 00592 // the value isn't really live-in. 00593 for (unsigned i = 0, e = LiveInBlockWorklist.size(); i != e; ++i) { 00594 BasicBlock *BB = LiveInBlockWorklist[i]; 00595 if (!DefBlocks.count(BB)) continue; 00596 00597 // Okay, this is a block that both uses and defines the value. If the first 00598 // reference to the alloca is a def (store), then we know it isn't live-in. 00599 for (BasicBlock::iterator I = BB->begin(); ; ++I) { 00600 if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 00601 if (SI->getOperand(1) != AI) continue; 00602 00603 // We found a store to the alloca before a load. The alloca is not 00604 // actually live-in here. 00605 LiveInBlockWorklist[i] = LiveInBlockWorklist.back(); 00606 LiveInBlockWorklist.pop_back(); 00607 --i, --e; 00608 break; 00609 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 00610 if (LI->getOperand(0) != AI) continue; 00611 00612 // Okay, we found a load before a store to the alloca. It is actually 00613 // live into this block. 00614 break; 00615 } 00616 } 00617 } 00618 00619 // Now that we have a set of blocks where the phi is live-in, recursively add 00620 // their predecessors until we find the full region the value is live. 00621 while (!LiveInBlockWorklist.empty()) { 00622 BasicBlock *BB = LiveInBlockWorklist.pop_back_val(); 00623 00624 // The block really is live in here, insert it into the set. If already in 00625 // the set, then it has already been processed. 00626 if (!LiveInBlocks.insert(BB)) 00627 continue; 00628 00629 // Since the value is live into BB, it is either defined in a predecessor or 00630 // live into it to. Add the preds to the worklist unless they are a 00631 // defining block. 00632 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 00633 BasicBlock *P = *PI; 00634 00635 // The value is not live into a predecessor if it defines the value. 00636 if (DefBlocks.count(P)) 00637 continue; 00638 00639 // Otherwise it is, add to the worklist. 00640 LiveInBlockWorklist.push_back(P); 00641 } 00642 } 00643 } 00644 00645 /// DetermineInsertionPoint - At this point, we're committed to promoting the 00646 /// alloca using IDF's, and the standard SSA construction algorithm. Determine 00647 /// which blocks need phi nodes and see if we can optimize out some work by 00648 /// avoiding insertion of dead phi nodes. 00649 void PromoteMem2Reg::DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum, 00650 AllocaInfo &Info) { 00651 00652 // Unique the set of defining blocks for efficient lookup. 00653 SmallPtrSet<BasicBlock*, 32> DefBlocks; 00654 DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end()); 00655 00656 // Determine which blocks the value is live in. These are blocks which lead 00657 // to uses. 00658 SmallPtrSet<BasicBlock*, 32> LiveInBlocks; 00659 ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks); 00660 00661 // Compute the locations where PhiNodes need to be inserted. Look at the 00662 // dominance frontier of EACH basic-block we have a write in. 00663 unsigned CurrentVersion = 0; 00664 SmallPtrSet<PHINode*, 16> InsertedPHINodes; 00665 std::vector<std::pair<unsigned, BasicBlock*> > DFBlocks; 00666 while (!Info.DefiningBlocks.empty()) { 00667 BasicBlock *BB = Info.DefiningBlocks.back(); 00668 Info.DefiningBlocks.pop_back(); 00669 00670 // Look up the DF for this write, add it to defining blocks. 00671 DominanceFrontier::const_iterator it = DF.find(BB); 00672 if (it == DF.end()) continue; 00673 00674 const DominanceFrontier::DomSetType &S = it->second; 00675 00676 // In theory we don't need the indirection through the DFBlocks vector. 00677 // In practice, the order of calling QueuePhiNode would depend on the 00678 // (unspecified) ordering of basic blocks in the dominance frontier, 00679 // which would give PHI nodes non-determinstic subscripts. Fix this by 00680 // processing blocks in order of the occurance in the function. 00681 for (DominanceFrontier::DomSetType::const_iterator P = S.begin(), 00682 PE = S.end(); P != PE; ++P) { 00683 // If the frontier block is not in the live-in set for the alloca, don't 00684 // bother processing it. 00685 if (!LiveInBlocks.count(*P)) 00686 continue; 00687 00688 DFBlocks.push_back(std::make_pair(BBNumbers[*P], *P)); 00689 } 00690 00691 // Sort by which the block ordering in the function. 00692 if (DFBlocks.size() > 1) 00693 std::sort(DFBlocks.begin(), DFBlocks.end()); 00694 00695 for (unsigned i = 0, e = DFBlocks.size(); i != e; ++i) { 00696 BasicBlock *BB = DFBlocks[i].second; 00697 if (QueuePhiNode(BB, AllocaNum, CurrentVersion, InsertedPHINodes)) 00698 Info.DefiningBlocks.push_back(BB); 00699 } 00700 DFBlocks.clear(); 00701 } 00702 } 00703 00704 /// RewriteSingleStoreAlloca - If there is only a single store to this value, 00705 /// replace any loads of it that are directly dominated by the definition with 00706 /// the value stored. 00707 void PromoteMem2Reg::RewriteSingleStoreAlloca(AllocaInst *AI, 00708 AllocaInfo &Info, 00709 LargeBlockInfo &LBI) { 00710 StoreInst *OnlyStore = Info.OnlyStore; 00711 bool StoringGlobalVal = !isa<Instruction>(OnlyStore->getOperand(0)); 00712 BasicBlock *StoreBB = OnlyStore->getParent(); 00713 int StoreIndex = -1; 00714 00715 // Clear out UsingBlocks. We will reconstruct it here if needed. 00716 Info.UsingBlocks.clear(); 00717 00718 for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E; ) { 00719 Instruction *UserInst = cast<Instruction>(*UI++); 00720 if (!isa<LoadInst>(UserInst)) { 00721 assert(UserInst == OnlyStore && "Should only have load/stores"); 00722 continue; 00723 } 00724 LoadInst *LI = cast<LoadInst>(UserInst); 00725 00726 // Okay, if we have a load from the alloca, we want to replace it with the 00727 // only value stored to the alloca. We can do this if the value is 00728 // dominated by the store. If not, we use the rest of the mem2reg machinery 00729 // to insert the phi nodes as needed. 00730 if (!StoringGlobalVal) { // Non-instructions are always dominated. 00731 if (LI->getParent() == StoreBB) { 00732 // If we have a use that is in the same block as the store, compare the 00733 // indices of the two instructions to see which one came first. If the 00734 // load came before the store, we can't handle it. 00735 if (StoreIndex == -1) 00736 StoreIndex = LBI.getInstructionIndex(OnlyStore); 00737 00738 if (unsigned(StoreIndex) > LBI.getInstructionIndex(LI)) { 00739 // Can't handle this load, bail out. 00740 Info.UsingBlocks.push_back(StoreBB); 00741 continue; 00742 } 00743 00744 } else if (LI->getParent() != StoreBB && 00745 !dominates(StoreBB, LI->getParent())) { 00746 // If the load and store are in different blocks, use BB dominance to 00747 // check their relationships. If the store doesn't dom the use, bail 00748 // out. 00749 Info.UsingBlocks.push_back(LI->getParent()); 00750 continue; 00751 } 00752 } 00753 00754 // Otherwise, we *can* safely rewrite this load. 00755 LI->replaceAllUsesWith(OnlyStore->getOperand(0)); 00756 if (AST && isa<PointerType>(LI->getType())) 00757 AST->deleteValue(LI); 00758 LI->eraseFromParent(); 00759 LBI.deleteValue(LI); 00760 } 00761 } 00762 00763 namespace { 00764 00765 /// StoreIndexSearchPredicate - This is a helper predicate used to search by the 00766 /// first element of a pair. 00767 struct StoreIndexSearchPredicate { 00768 bool operator()(const std::pair<unsigned, StoreInst*> &LHS, 00769 const std::pair<unsigned, StoreInst*> &RHS) { 00770 return LHS.first < RHS.first; 00771 } 00772 }; 00773 00774 } 00775 00776 /// PromoteSingleBlockAlloca - Many allocas are only used within a single basic 00777 /// block. If this is the case, avoid traversing the CFG and inserting a lot of 00778 /// potentially useless PHI nodes by just performing a single linear pass over 00779 /// the basic block using the Alloca. 00780 /// 00781 /// If we cannot promote this alloca (because it is read before it is written), 00782 /// return true. This is necessary in cases where, due to control flow, the 00783 /// alloca is potentially undefined on some control flow paths. e.g. code like 00784 /// this is potentially correct: 00785 /// 00786 /// for (...) { if (c) { A = undef; undef = B; } } 00787 /// 00788 /// ... so long as A is not used before undef is set. 00789 /// 00790 void PromoteMem2Reg::PromoteSingleBlockAlloca(AllocaInst *AI, AllocaInfo &Info, 00791 LargeBlockInfo &LBI) { 00792 // The trickiest case to handle is when we have large blocks. Because of this, 00793 // this code is optimized assuming that large blocks happen. This does not 00794 // significantly pessimize the small block case. This uses LargeBlockInfo to 00795 // make it efficient to get the index of various operations in the block. 00796 00797 // Clear out UsingBlocks. We will reconstruct it here if needed. 00798 Info.UsingBlocks.clear(); 00799 00800 // Walk the use-def list of the alloca, getting the locations of all stores. 00801 typedef SmallVector<std::pair<unsigned, StoreInst*>, 64> StoresByIndexTy; 00802 StoresByIndexTy StoresByIndex; 00803 00804 for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 00805 UI != E; ++UI) 00806 if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) 00807 StoresByIndex.push_back(std::make_pair(LBI.getInstructionIndex(SI), SI)); 00808 00809 // If there are no stores to the alloca, just replace any loads with undef. 00810 if (StoresByIndex.empty()) { 00811 for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;) 00812 if (LoadInst *LI = dyn_cast<LoadInst>(*UI++)) { 00813 LI->replaceAllUsesWith(UndefValue::get(LI->getType())); 00814 if (AST && isa<PointerType>(LI->getType())) 00815 AST->deleteValue(LI); 00816 LBI.deleteValue(LI); 00817 LI->eraseFromParent(); 00818 } 00819 return; 00820 } 00821 00822 // Sort the stores by their index, making it efficient to do a lookup with a 00823 // binary search. 00824 std::sort(StoresByIndex.begin(), StoresByIndex.end()); 00825 00826 // Walk all of the loads from this alloca, replacing them with the nearest 00827 // store above them, if any. 00828 for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;) { 00829 LoadInst *LI = dyn_cast<LoadInst>(*UI++); 00830 if (!LI) continue; 00831 00832 unsigned LoadIdx = LBI.getInstructionIndex(LI); 00833 00834 // Find the nearest store that has a lower than this load. 00835 StoresByIndexTy::iterator I = 00836 std::lower_bound(StoresByIndex.begin(), StoresByIndex.end(), 00837 std::pair<unsigned, StoreInst*>(LoadIdx, 0), 00838 StoreIndexSearchPredicate()); 00839 00840 // If there is no store before this load, then we can't promote this load. 00841 if (I == StoresByIndex.begin()) { 00842 // Can't handle this load, bail out. 00843 Info.UsingBlocks.push_back(LI->getParent()); 00844 continue; 00845 } 00846 00847 // Otherwise, there was a store before this load, the load takes its value. 00848 --I; 00849 LI->replaceAllUsesWith(I->second->getOperand(0)); 00850 if (AST && isa<PointerType>(LI->getType())) 00851 AST->deleteValue(LI); 00852 LI->eraseFromParent(); 00853 LBI.deleteValue(LI); 00854 } 00855 } 00856 00857 00858 // QueuePhiNode - queues a phi-node to be added to a basic-block for a specific 00859 // Alloca returns true if there wasn't already a phi-node for that variable 00860 // 00861 bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo, 00862 unsigned &Version, 00863 SmallPtrSet<PHINode*, 16> &InsertedPHINodes) { 00864 // Look up the basic-block in question. 00865 PHINode *&PN = NewPhiNodes[std::make_pair(BB, AllocaNo)]; 00866 00867 // If the BB already has a phi node added for the i'th alloca then we're done! 00868 if (PN) return false; 00869 00870 // Create a PhiNode using the dereferenced type... and add the phi-node to the 00871 // BasicBlock. 00872 PN = PHINode::Create(Allocas[AllocaNo]->getAllocatedType(), 00873 Allocas[AllocaNo]->getName() + "." + Twine(Version++), 00874 BB->begin()); 00875 ++NumPHIInsert; 00876 PhiToAllocaMap[PN] = AllocaNo; 00877 PN->reserveOperandSpace(getNumPreds(BB)); 00878 00879 InsertedPHINodes.insert(PN); 00880 00881 if (AST && isa<PointerType>(PN->getType())) 00882 AST->copyValue(PointerAllocaValues[AllocaNo], PN); 00883 00884 return true; 00885 } 00886 00887 // RenamePass - Recursively traverse the CFG of the function, renaming loads and 00888 // stores to the allocas which we are promoting. IncomingVals indicates what 00889 // value each Alloca contains on exit from the predecessor block Pred. 00890 // 00891 void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred, 00892 RenamePassData::ValVector &IncomingVals, 00893 std::vector<RenamePassData> &Worklist) { 00894 NextIteration: 00895 // If we are inserting any phi nodes into this BB, they will already be in the 00896 // block. 00897 if (PHINode *APN = dyn_cast<PHINode>(BB->begin())) { 00898 // If we have PHI nodes to update, compute the number of edges from Pred to 00899 // BB. 00900 if (PhiToAllocaMap.count(APN)) { 00901 // We want to be able to distinguish between PHI nodes being inserted by 00902 // this invocation of mem2reg from those phi nodes that already existed in 00903 // the IR before mem2reg was run. We determine that APN is being inserted 00904 // because it is missing incoming edges. All other PHI nodes being 00905 // inserted by this pass of mem2reg will have the same number of incoming 00906 // operands so far. Remember this count. 00907 unsigned NewPHINumOperands = APN->getNumOperands(); 00908 00909 unsigned NumEdges = 0; 00910 for (succ_iterator I = succ_begin(Pred), E = succ_end(Pred); I != E; ++I) 00911 if (*I == BB) 00912 ++NumEdges; 00913 assert(NumEdges && "Must be at least one edge from Pred to BB!"); 00914 00915 // Add entries for all the phis. 00916 BasicBlock::iterator PNI = BB->begin(); 00917 do { 00918 unsigned AllocaNo = PhiToAllocaMap[APN]; 00919 00920 // Add N incoming values to the PHI node. 00921 for (unsigned i = 0; i != NumEdges; ++i) 00922 APN->addIncoming(IncomingVals[AllocaNo], Pred); 00923 00924 // The currently active variable for this block is now the PHI. 00925 IncomingVals[AllocaNo] = APN; 00926 00927 // Get the next phi node. 00928 ++PNI; 00929 APN = dyn_cast<PHINode>(PNI); 00930 if (APN == 0) break; 00931 00932 // Verify that it is missing entries. If not, it is not being inserted 00933 // by this mem2reg invocation so we want to ignore it. 00934 } while (APN->getNumOperands() == NewPHINumOperands); 00935 } 00936 } 00937 00938 // Don't revisit blocks. 00939 if (!Visited.insert(BB)) return; 00940 00941 for (BasicBlock::iterator II = BB->begin(); !isa<TerminatorInst>(II); ) { 00942 Instruction *I = II++; // get the instruction, increment iterator 00943 00944 if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 00945 AllocaInst *Src = dyn_cast<AllocaInst>(LI->getPointerOperand()); 00946 if (!Src) continue; 00947 00948 std::map<AllocaInst*, unsigned>::iterator AI = AllocaLookup.find(Src); 00949 if (AI == AllocaLookup.end()) continue; 00950 00951 Value *V = IncomingVals[AI->second]; 00952 00953 // Anything using the load now uses the current value. 00954 LI->replaceAllUsesWith(V); 00955 if (AST && isa<PointerType>(LI->getType())) 00956 AST->deleteValue(LI); 00957 BB->getInstList().erase(LI); 00958 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 00959 // Delete this instruction and mark the name as the current holder of the 00960 // value 00961 AllocaInst *Dest = dyn_cast<AllocaInst>(SI->getPointerOperand()); 00962 if (!Dest) continue; 00963 00964 std::map<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Dest); 00965 if (ai == AllocaLookup.end()) 00966 continue; 00967 00968 // what value were we writing? 00969 IncomingVals[ai->second] = SI->getOperand(0); 00970 BB->getInstList().erase(SI); 00971 } 00972 } 00973 00974 // 'Recurse' to our successors. 00975 succ_iterator I = succ_begin(BB), E = succ_end(BB); 00976 if (I == E) return; 00977 00978 // Keep track of the successors so we don't visit the same successor twice 00979 SmallPtrSet<BasicBlock*, 8> VisitedSuccs; 00980 00981 // Handle the first successor without using the worklist. 00982 VisitedSuccs.insert(*I); 00983 Pred = BB; 00984 BB = *I; 00985 ++I; 00986 00987 for (; I != E; ++I) 00988 if (VisitedSuccs.insert(*I)) 00989 Worklist.push_back(RenamePassData(*I, Pred, IncomingVals)); 00990 00991 goto NextIteration; 00992 } 00993 00994 /// PromoteMemToReg - Promote the specified list of alloca instructions into 00995 /// scalar registers, inserting PHI nodes as appropriate. This function makes 00996 /// use of DominanceFrontier information. This function does not modify the CFG 00997 /// of the function at all. All allocas must be from the same function. 00998 /// 00999 /// If AST is specified, the specified tracker is updated to reflect changes 01000 /// made to the IR. 01001 /// 01002 void llvm::PromoteMemToReg(const std::vector<AllocaInst*> &Allocas, 01003 DominatorTree &DT, DominanceFrontier &DF, 01004 LLVMContext &Context, AliasSetTracker *AST) { 01005 // If there is nothing to do, bail out... 01006 if (Allocas.empty()) return; 01007 01008 PromoteMem2Reg(Allocas, DT, DF, AST, Context).run(); 01009 }