PromoteMemoryToRegister.cpp revision 226633
1198090Srdivacky//===- PromoteMemoryToRegister.cpp - Convert allocas to registers ---------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10198090Srdivacky// This file promotes memory references to be register references. It promotes 11193323Sed// alloca instructions which only have loads and stores as uses. An alloca is 12198090Srdivacky// transformed by using iterated dominator frontiers to place PHI nodes, then 13198090Srdivacky// traversing the function in depth-first order to rewrite loads and stores as 14198090Srdivacky// appropriate. 15198090Srdivacky// 16198090Srdivacky// The algorithm used here is based on: 17193323Sed// 18193323Sed// Sreedhar and Gao. A linear time algorithm for placing phi-nodes. 19193323Sed// In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of 20193323Sed// Programming Languages 21193323Sed// POPL '95. ACM, New York, NY, 62-73. 22193323Sed// 23193323Sed// It has been modified to not explicitly use the DJ graph data structure and to 24193323Sed// directly compute pruned SSA using per-variable liveness information. 25193323Sed// 26198396Srdivacky//===----------------------------------------------------------------------===// 27198396Srdivacky 28193323Sed#define DEBUG_TYPE "mem2reg" 29193323Sed#include "llvm/Transforms/Utils/PromoteMemToReg.h" 30198090Srdivacky#include "llvm/Constants.h" 31193323Sed#include "llvm/DerivedTypes.h" 32193323Sed#include "llvm/Function.h" 33193323Sed#include "llvm/Instructions.h" 34193323Sed#include "llvm/IntrinsicInst.h" 35193323Sed#include "llvm/Metadata.h" 36193323Sed#include "llvm/Analysis/AliasSetTracker.h" 37193323Sed#include "llvm/Analysis/DebugInfo.h" 38193323Sed#include "llvm/Analysis/DIBuilder.h" 39193323Sed#include "llvm/Analysis/Dominators.h" 40193323Sed#include "llvm/Analysis/InstructionSimplify.h" 41198892Srdivacky#include "llvm/Analysis/ValueTracking.h" 42198892Srdivacky#include "llvm/Transforms/Utils/Local.h" 43198892Srdivacky#include "llvm/ADT/DenseMap.h" 44198892Srdivacky#include "llvm/ADT/SmallPtrSet.h" 45198892Srdivacky#include "llvm/ADT/SmallVector.h" 46198892Srdivacky#include "llvm/ADT/Statistic.h" 47198892Srdivacky#include "llvm/ADT/STLExtras.h" 48198892Srdivacky#include "llvm/Support/CFG.h" 49198892Srdivacky#include <algorithm> 50198892Srdivacky#include <queue> 51198892Srdivackyusing namespace llvm; 52198892Srdivacky 53198892SrdivackySTATISTIC(NumLocalPromoted, "Number of alloca's promoted within one block"); 54198892SrdivackySTATISTIC(NumSingleStore, "Number of alloca's promoted with a single store"); 55198892SrdivackySTATISTIC(NumDeadAlloca, "Number of dead alloca's removed"); 56198892SrdivackySTATISTIC(NumPHIInsert, "Number of PHI nodes inserted"); 57198892Srdivacky 58198892Srdivackynamespace llvm { 59198892Srdivackytemplate<> 60198892Srdivackystruct DenseMapInfo<std::pair<BasicBlock*, unsigned> > { 61198892Srdivacky typedef std::pair<BasicBlock*, unsigned> EltTy; 62198892Srdivacky static inline EltTy getEmptyKey() { 63198892Srdivacky return EltTy(reinterpret_cast<BasicBlock*>(-1), ~0U); 64198892Srdivacky } 65198892Srdivacky static inline EltTy getTombstoneKey() { 66198892Srdivacky return EltTy(reinterpret_cast<BasicBlock*>(-2), 0U); 67198892Srdivacky } 68198892Srdivacky static unsigned getHashValue(const std::pair<BasicBlock*, unsigned> &Val) { 69198892Srdivacky return DenseMapInfo<void*>::getHashValue(Val.first) + Val.second*2; 70198892Srdivacky } 71198892Srdivacky static bool isEqual(const EltTy &LHS, const EltTy &RHS) { 72198892Srdivacky return LHS == RHS; 73198892Srdivacky } 74198892Srdivacky}; 75198892Srdivacky} 76198892Srdivacky 77198892Srdivacky/// isAllocaPromotable - Return true if this alloca is legal for promotion. 78198892Srdivacky/// This is true if there are only loads and stores to the alloca. 79198892Srdivacky/// 80198892Srdivackybool llvm::isAllocaPromotable(const AllocaInst *AI) { 81198892Srdivacky // FIXME: If the memory unit is of pointer or integer type, we can permit 82198892Srdivacky // assignments to subsections of the memory unit. 83203954Srdivacky 84198892Srdivacky // Only allow direct and non-volatile loads and stores... 85198892Srdivacky for (Value::const_use_iterator UI = AI->use_begin(), UE = AI->use_end(); 86198892Srdivacky UI != UE; ++UI) { // Loop over all of the uses of the alloca 87198892Srdivacky const User *U = *UI; 88198892Srdivacky if (const LoadInst *LI = dyn_cast<LoadInst>(U)) { 89198892Srdivacky // Note that atomic loads can be transformed; atomic semantics do 90198892Srdivacky // not have any meaning for a local alloca. 91198892Srdivacky if (LI->isVolatile()) 92198892Srdivacky return false; 93198892Srdivacky } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) { 94198892Srdivacky if (SI->getOperand(0) == AI) 95198892Srdivacky return false; // Don't allow a store OF the AI, only INTO the AI. 96198892Srdivacky // Note that atomic stores can be transformed; atomic semantics do 97198892Srdivacky // not have any meaning for a local alloca. 98203954Srdivacky if (SI->isVolatile()) 99198892Srdivacky return false; 100198892Srdivacky } else if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(U)) { 101198892Srdivacky if (II->getIntrinsicID() != Intrinsic::lifetime_start && 102198892Srdivacky II->getIntrinsicID() != Intrinsic::lifetime_end) 103198892Srdivacky return false; 104198892Srdivacky } else if (const BitCastInst *BCI = dyn_cast<BitCastInst>(U)) { 105198892Srdivacky if (BCI->getType() != Type::getInt8PtrTy(U->getContext())) 106198892Srdivacky return false; 107198892Srdivacky if (!onlyUsedByLifetimeMarkers(BCI)) 108198892Srdivacky return false; 109198892Srdivacky } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) { 110198892Srdivacky if (GEPI->getType() != Type::getInt8PtrTy(U->getContext())) 111198892Srdivacky return false; 112198892Srdivacky if (!GEPI->hasAllZeroIndices()) 113198892Srdivacky return false; 114198892Srdivacky if (!onlyUsedByLifetimeMarkers(GEPI)) 115198892Srdivacky return false; 116198892Srdivacky } else { 117198892Srdivacky return false; 118198892Srdivacky } 119198892Srdivacky } 120198892Srdivacky 121198892Srdivacky return true; 122198892Srdivacky} 123198892Srdivacky 124198892Srdivackynamespace { 125198892Srdivacky struct AllocaInfo; 126198892Srdivacky 127198892Srdivacky // Data package used by RenamePass() 128198892Srdivacky class RenamePassData { 129198892Srdivacky public: 130198892Srdivacky typedef std::vector<Value *> ValVector; 131198892Srdivacky 132198892Srdivacky RenamePassData() : BB(NULL), Pred(NULL), Values() {} 133198892Srdivacky RenamePassData(BasicBlock *B, BasicBlock *P, 134198892Srdivacky const ValVector &V) : BB(B), Pred(P), Values(V) {} 135198892Srdivacky BasicBlock *BB; 136198892Srdivacky BasicBlock *Pred; 137198892Srdivacky ValVector Values; 138198892Srdivacky 139198892Srdivacky void swap(RenamePassData &RHS) { 140198892Srdivacky std::swap(BB, RHS.BB); 141198892Srdivacky std::swap(Pred, RHS.Pred); 142198892Srdivacky Values.swap(RHS.Values); 143198892Srdivacky } 144198892Srdivacky }; 145198892Srdivacky 146198892Srdivacky /// LargeBlockInfo - This assigns and keeps a per-bb relative ordering of 147198892Srdivacky /// load/store instructions in the block that directly load or store an alloca. 148198892Srdivacky /// 149198892Srdivacky /// This functionality is important because it avoids scanning large basic 150198892Srdivacky /// blocks multiple times when promoting many allocas in the same block. 151198892Srdivacky class LargeBlockInfo { 152198892Srdivacky /// InstNumbers - For each instruction that we track, keep the index of the 153198892Srdivacky /// instruction. The index starts out as the number of the instruction from 154198892Srdivacky /// the start of the block. 155198892Srdivacky DenseMap<const Instruction *, unsigned> InstNumbers; 156198892Srdivacky public: 157198892Srdivacky 158198892Srdivacky /// isInterestingInstruction - This code only looks at accesses to allocas. 159198892Srdivacky static bool isInterestingInstruction(const Instruction *I) { 160198892Srdivacky return (isa<LoadInst>(I) && isa<AllocaInst>(I->getOperand(0))) || 161198892Srdivacky (isa<StoreInst>(I) && isa<AllocaInst>(I->getOperand(1))); 162198892Srdivacky } 163198892Srdivacky 164198892Srdivacky /// getInstructionIndex - Get or calculate the index of the specified 165198892Srdivacky /// instruction. 166198892Srdivacky unsigned getInstructionIndex(const Instruction *I) { 167198892Srdivacky assert(isInterestingInstruction(I) && 168198892Srdivacky "Not a load/store to/from an alloca?"); 169198892Srdivacky 170198892Srdivacky // If we already have this instruction number, return it. 171198892Srdivacky DenseMap<const Instruction *, unsigned>::iterator It = InstNumbers.find(I); 172198892Srdivacky if (It != InstNumbers.end()) return It->second; 173193323Sed 174193323Sed // Scan the whole block to get the instruction. This accumulates 175193323Sed // information for every interesting instruction in the block, in order to 176193323Sed // avoid gratuitus rescans. 177193323Sed const BasicBlock *BB = I->getParent(); 178193323Sed unsigned InstNo = 0; 179193323Sed for (BasicBlock::const_iterator BBI = BB->begin(), E = BB->end(); 180193323Sed BBI != E; ++BBI) 181193323Sed if (isInterestingInstruction(BBI)) 182193323Sed InstNumbers[BBI] = InstNo++; 183193323Sed It = InstNumbers.find(I); 184193323Sed 185193323Sed assert(It != InstNumbers.end() && "Didn't insert instruction?"); 186193323Sed return It->second; 187193323Sed } 188193323Sed 189193323Sed void deleteValue(const Instruction *I) { 190193323Sed InstNumbers.erase(I); 191193323Sed } 192193323Sed 193193323Sed void clear() { 194193323Sed InstNumbers.clear(); 195193323Sed } 196193323Sed }; 197193323Sed 198193323Sed struct PromoteMem2Reg { 199193323Sed /// Allocas - The alloca instructions being promoted. 200193323Sed /// 201193323Sed std::vector<AllocaInst*> Allocas; 202193323Sed DominatorTree &DT; 203193323Sed DIBuilder *DIB; 204193323Sed 205193323Sed /// AST - An AliasSetTracker object to update. If null, don't update it. 206193323Sed /// 207193323Sed AliasSetTracker *AST; 208193323Sed 209193323Sed /// AllocaLookup - Reverse mapping of Allocas. 210193323Sed /// 211193323Sed DenseMap<AllocaInst*, unsigned> AllocaLookup; 212193323Sed 213193323Sed /// NewPhiNodes - The PhiNodes we're adding. 214193323Sed /// 215193323Sed DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*> NewPhiNodes; 216193323Sed 217193323Sed /// PhiToAllocaMap - For each PHI node, keep track of which entry in Allocas 218193323Sed /// it corresponds to. 219193323Sed DenseMap<PHINode*, unsigned> PhiToAllocaMap; 220193323Sed 221193323Sed /// PointerAllocaValues - If we are updating an AliasSetTracker, then for 222193323Sed /// each alloca that is of pointer type, we keep track of what to copyValue 223193323Sed /// to the inserted PHI nodes here. 224193323Sed /// 225193323Sed std::vector<Value*> PointerAllocaValues; 226193323Sed 227198396Srdivacky /// AllocaDbgDeclares - For each alloca, we keep track of the dbg.declare 228198396Srdivacky /// intrinsic that describes it, if any, so that we can convert it to a 229198396Srdivacky /// dbg.value intrinsic if the alloca gets promoted. 230198396Srdivacky SmallVector<DbgDeclareInst*, 8> AllocaDbgDeclares; 231198396Srdivacky 232198396Srdivacky /// Visited - The set of basic blocks the renamer has already visited. 233198396Srdivacky /// 234198396Srdivacky SmallPtrSet<BasicBlock*, 16> Visited; 235198396Srdivacky 236198396Srdivacky /// BBNumbers - Contains a stable numbering of basic blocks to avoid 237198892Srdivacky /// non-determinstic behavior. 238198892Srdivacky DenseMap<BasicBlock*, unsigned> BBNumbers; 239198396Srdivacky 240198396Srdivacky /// DomLevels - Maps DomTreeNodes to their level in the dominator tree. 241198396Srdivacky DenseMap<DomTreeNode*, unsigned> DomLevels; 242198396Srdivacky 243198396Srdivacky /// BBNumPreds - Lazily compute the number of predecessors a block has. 244198396Srdivacky DenseMap<const BasicBlock*, unsigned> BBNumPreds; 245198396Srdivacky public: 246198396Srdivacky PromoteMem2Reg(const std::vector<AllocaInst*> &A, DominatorTree &dt, 247198396Srdivacky AliasSetTracker *ast) 248198396Srdivacky : Allocas(A), DT(dt), DIB(0), AST(ast) {} 249198396Srdivacky ~PromoteMem2Reg() { 250198396Srdivacky delete DIB; 251198892Srdivacky } 252198396Srdivacky 253198396Srdivacky void run(); 254198396Srdivacky 255198396Srdivacky /// dominates - Return true if BB1 dominates BB2 using the DominatorTree. 256198396Srdivacky /// 257198396Srdivacky bool dominates(BasicBlock *BB1, BasicBlock *BB2) const { 258198396Srdivacky return DT.dominates(BB1, BB2); 259198892Srdivacky } 260198396Srdivacky 261198396Srdivacky private: 262198396Srdivacky void RemoveFromAllocasList(unsigned &AllocaIdx) { 263198892Srdivacky Allocas[AllocaIdx] = Allocas.back(); 264198396Srdivacky Allocas.pop_back(); 265198396Srdivacky --AllocaIdx; 266198892Srdivacky } 267198396Srdivacky 268193323Sed unsigned getNumPreds(const BasicBlock *BB) { 269198396Srdivacky unsigned &NP = BBNumPreds[BB]; 270198396Srdivacky if (NP == 0) 271198396Srdivacky NP = std::distance(pred_begin(BB), pred_end(BB))+1; 272198396Srdivacky return NP-1; 273198396Srdivacky } 274198396Srdivacky 275198396Srdivacky void DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum, 276198396Srdivacky AllocaInfo &Info); 277198396Srdivacky void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info, 278198396Srdivacky const SmallPtrSet<BasicBlock*, 32> &DefBlocks, 279198396Srdivacky SmallPtrSet<BasicBlock*, 32> &LiveInBlocks); 280198396Srdivacky 281198396Srdivacky void RewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info, 282198396Srdivacky LargeBlockInfo &LBI); 283198396Srdivacky void PromoteSingleBlockAlloca(AllocaInst *AI, AllocaInfo &Info, 284198396Srdivacky LargeBlockInfo &LBI); 285198396Srdivacky 286198396Srdivacky void RenamePass(BasicBlock *BB, BasicBlock *Pred, 287198396Srdivacky RenamePassData::ValVector &IncVals, 288198396Srdivacky std::vector<RenamePassData> &Worklist); 289198396Srdivacky bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version); 290198396Srdivacky }; 291198396Srdivacky 292198396Srdivacky struct AllocaInfo { 293198396Srdivacky SmallVector<BasicBlock*, 32> DefiningBlocks; 294198396Srdivacky SmallVector<BasicBlock*, 32> UsingBlocks; 295198396Srdivacky 296198396Srdivacky StoreInst *OnlyStore; 297198396Srdivacky BasicBlock *OnlyBlock; 298198892Srdivacky bool OnlyUsedInOneBlock; 299198396Srdivacky 300198396Srdivacky Value *AllocaPointerVal; 301198396Srdivacky DbgDeclareInst *DbgDeclare; 302198396Srdivacky 303198396Srdivacky void clear() { 304198396Srdivacky DefiningBlocks.clear(); 305198396Srdivacky UsingBlocks.clear(); 306198396Srdivacky OnlyStore = 0; 307198396Srdivacky OnlyBlock = 0; 308198396Srdivacky OnlyUsedInOneBlock = true; 309198396Srdivacky AllocaPointerVal = 0; 310198396Srdivacky DbgDeclare = 0; 311198396Srdivacky } 312198396Srdivacky 313198396Srdivacky /// AnalyzeAlloca - Scan the uses of the specified alloca, filling in our 314198396Srdivacky /// ivars. 315198396Srdivacky void AnalyzeAlloca(AllocaInst *AI) { 316198396Srdivacky clear(); 317198396Srdivacky 318198396Srdivacky // As we scan the uses of the alloca instruction, keep track of stores, 319198396Srdivacky // and decide whether all of the loads and stores to the alloca are within 320198396Srdivacky // the same basic block. 321198396Srdivacky for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 322198396Srdivacky UI != E;) { 323198396Srdivacky Instruction *User = cast<Instruction>(*UI++); 324198396Srdivacky 325198396Srdivacky if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 326198396Srdivacky // Remember the basic blocks which define new values for the alloca 327198396Srdivacky DefiningBlocks.push_back(SI->getParent()); 328198396Srdivacky AllocaPointerVal = SI->getOperand(0); 329198396Srdivacky OnlyStore = SI; 330198396Srdivacky } else { 331198396Srdivacky LoadInst *LI = cast<LoadInst>(User); 332198396Srdivacky // Otherwise it must be a load instruction, keep track of variable 333198396Srdivacky // reads. 334198396Srdivacky UsingBlocks.push_back(LI->getParent()); 335198396Srdivacky AllocaPointerVal = LI; 336198396Srdivacky } 337198396Srdivacky 338198396Srdivacky if (OnlyUsedInOneBlock) { 339198396Srdivacky if (OnlyBlock == 0) 340198396Srdivacky OnlyBlock = User->getParent(); 341198396Srdivacky else if (OnlyBlock != User->getParent()) 342198396Srdivacky OnlyUsedInOneBlock = false; 343198396Srdivacky } 344198396Srdivacky } 345198396Srdivacky 346198396Srdivacky DbgDeclare = FindAllocaDbgDeclare(AI); 347198396Srdivacky } 348198396Srdivacky }; 349198396Srdivacky 350198396Srdivacky typedef std::pair<DomTreeNode*, unsigned> DomTreeNodePair; 351198396Srdivacky 352198396Srdivacky struct DomTreeNodeCompare { 353198396Srdivacky bool operator()(const DomTreeNodePair &LHS, const DomTreeNodePair &RHS) { 354198396Srdivacky return LHS.second < RHS.second; 355198396Srdivacky } 356198396Srdivacky }; 357198396Srdivacky} // end of anonymous namespace 358198396Srdivacky 359198396Srdivackystatic void removeLifetimeIntrinsicUsers(AllocaInst *AI) { 360198396Srdivacky // Knowing that this alloca is promotable, we know that it's safe to kill all 361198396Srdivacky // instructions except for load and store. 362198396Srdivacky 363198396Srdivacky for (Value::use_iterator UI = AI->use_begin(), UE = AI->use_end(); 364198396Srdivacky UI != UE;) { 365198396Srdivacky Instruction *I = cast<Instruction>(*UI); 366198396Srdivacky ++UI; 367198396Srdivacky if (isa<LoadInst>(I) || isa<StoreInst>(I)) 368198396Srdivacky continue; 369198892Srdivacky 370198396Srdivacky if (!I->getType()->isVoidTy()) { 371198892Srdivacky // The only users of this bitcast/GEP instruction are lifetime intrinsics. 372198396Srdivacky // Follow the use/def chain to erase them now instead of leaving it for 373198396Srdivacky // dead code elimination later. 374198396Srdivacky for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 375198396Srdivacky UI != UE;) { 376198396Srdivacky Instruction *Inst = cast<Instruction>(*UI); 377198396Srdivacky ++UI; 378198396Srdivacky Inst->eraseFromParent(); 379198396Srdivacky } 380198396Srdivacky } 381198396Srdivacky I->eraseFromParent(); 382198396Srdivacky } 383198396Srdivacky} 384198892Srdivacky 385198396Srdivackyvoid PromoteMem2Reg::run() { 386198396Srdivacky Function &F = *DT.getRoot()->getParent(); 387198396Srdivacky 388198396Srdivacky if (AST) PointerAllocaValues.resize(Allocas.size()); 389198396Srdivacky AllocaDbgDeclares.resize(Allocas.size()); 390198396Srdivacky 391198396Srdivacky AllocaInfo Info; 392198396Srdivacky LargeBlockInfo LBI; 393198396Srdivacky 394198396Srdivacky for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) { 395198396Srdivacky AllocaInst *AI = Allocas[AllocaNum]; 396198396Srdivacky 397198396Srdivacky assert(isAllocaPromotable(AI) && 398198396Srdivacky "Cannot promote non-promotable alloca!"); 399198396Srdivacky assert(AI->getParent()->getParent() == &F && 400198396Srdivacky "All allocas should be in the same function, which is same as DF!"); 401202375Srdivacky 402202375Srdivacky removeLifetimeIntrinsicUsers(AI); 403198396Srdivacky 404198396Srdivacky if (AI->use_empty()) { 405198396Srdivacky // If there are no uses of the alloca, just delete it now. 406198396Srdivacky if (AST) AST->deleteValue(AI); 407198396Srdivacky AI->eraseFromParent(); 408198396Srdivacky 409198396Srdivacky // Remove the alloca from the Allocas list, since it has been processed 410198396Srdivacky RemoveFromAllocasList(AllocaNum); 411198396Srdivacky ++NumDeadAlloca; 412198396Srdivacky continue; 413198396Srdivacky } 414198396Srdivacky 415198396Srdivacky // Calculate the set of read and write-locations for each alloca. This is 416198396Srdivacky // analogous to finding the 'uses' and 'definitions' of each variable. 417198396Srdivacky Info.AnalyzeAlloca(AI); 418198396Srdivacky 419198396Srdivacky // If there is only a single store to this value, replace any loads of 420198396Srdivacky // it that are directly dominated by the definition with the value stored. 421198396Srdivacky if (Info.DefiningBlocks.size() == 1) { 422198396Srdivacky RewriteSingleStoreAlloca(AI, Info, LBI); 423198396Srdivacky 424198396Srdivacky // Finally, after the scan, check to see if the store is all that is left. 425198396Srdivacky if (Info.UsingBlocks.empty()) { 426198396Srdivacky // Record debuginfo for the store and remove the declaration's debuginfo. 427198396Srdivacky if (DbgDeclareInst *DDI = Info.DbgDeclare) { 428198396Srdivacky if (!DIB) 429198396Srdivacky DIB = new DIBuilder(*DDI->getParent()->getParent()->getParent()); 430198396Srdivacky ConvertDebugDeclareToDebugValue(DDI, Info.OnlyStore, *DIB); 431198396Srdivacky DDI->eraseFromParent(); 432198396Srdivacky } 433198396Srdivacky // Remove the (now dead) store and alloca. 434198396Srdivacky Info.OnlyStore->eraseFromParent(); 435200581Srdivacky LBI.deleteValue(Info.OnlyStore); 436198396Srdivacky 437198396Srdivacky if (AST) AST->deleteValue(AI); 438198396Srdivacky AI->eraseFromParent(); 439198396Srdivacky LBI.deleteValue(AI); 440198396Srdivacky 441198396Srdivacky // The alloca has been processed, move on. 442198396Srdivacky RemoveFromAllocasList(AllocaNum); 443198396Srdivacky 444198396Srdivacky ++NumSingleStore; 445198396Srdivacky continue; 446198396Srdivacky } 447198396Srdivacky } 448198396Srdivacky 449198396Srdivacky // If the alloca is only read and written in one basic block, just perform a 450198396Srdivacky // linear sweep over the block to eliminate it. 451198396Srdivacky if (Info.OnlyUsedInOneBlock) { 452198396Srdivacky PromoteSingleBlockAlloca(AI, Info, LBI); 453198396Srdivacky 454198396Srdivacky // Finally, after the scan, check to see if the stores are all that is 455198396Srdivacky // left. 456198396Srdivacky if (Info.UsingBlocks.empty()) { 457198396Srdivacky 458198396Srdivacky // Remove the (now dead) stores and alloca. 459198396Srdivacky while (!AI->use_empty()) { 460198396Srdivacky StoreInst *SI = cast<StoreInst>(AI->use_back()); 461198396Srdivacky // Record debuginfo for the store before removing it. 462198396Srdivacky if (DbgDeclareInst *DDI = Info.DbgDeclare) { 463198396Srdivacky if (!DIB) 464198396Srdivacky DIB = new DIBuilder(*SI->getParent()->getParent()->getParent()); 465198396Srdivacky ConvertDebugDeclareToDebugValue(DDI, SI, *DIB); 466198396Srdivacky } 467198396Srdivacky SI->eraseFromParent(); 468198396Srdivacky LBI.deleteValue(SI); 469198396Srdivacky } 470198396Srdivacky 471198396Srdivacky if (AST) AST->deleteValue(AI); 472198396Srdivacky AI->eraseFromParent(); 473198396Srdivacky LBI.deleteValue(AI); 474198396Srdivacky 475198396Srdivacky // The alloca has been processed, move on. 476198396Srdivacky RemoveFromAllocasList(AllocaNum); 477198396Srdivacky 478198396Srdivacky // The alloca's debuginfo can be removed as well. 479198396Srdivacky if (DbgDeclareInst *DDI = Info.DbgDeclare) 480198396Srdivacky DDI->eraseFromParent(); 481198396Srdivacky 482198396Srdivacky ++NumLocalPromoted; 483198396Srdivacky continue; 484198396Srdivacky } 485198396Srdivacky } 486198396Srdivacky 487198396Srdivacky // If we haven't computed dominator tree levels, do so now. 488198396Srdivacky if (DomLevels.empty()) { 489198396Srdivacky SmallVector<DomTreeNode*, 32> Worklist; 490193323Sed 491193323Sed DomTreeNode *Root = DT.getRootNode(); 492193323Sed DomLevels[Root] = 0; 493193323Sed Worklist.push_back(Root); 494193323Sed 495199481Srdivacky while (!Worklist.empty()) { 496193323Sed DomTreeNode *Node = Worklist.pop_back_val(); 497193323Sed unsigned ChildLevel = DomLevels[Node] + 1; 498193323Sed for (DomTreeNode::iterator CI = Node->begin(), CE = Node->end(); 499193323Sed CI != CE; ++CI) { 500193323Sed DomLevels[*CI] = ChildLevel; 501193323Sed Worklist.push_back(*CI); 502193323Sed } 503193323Sed } 504193323Sed } 505193323Sed 506193323Sed // If we haven't computed a numbering for the BB's in the function, do so 507193323Sed // now. 508193323Sed if (BBNumbers.empty()) { 509193323Sed unsigned ID = 0; 510193323Sed for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 511193323Sed BBNumbers[I] = ID++; 512193323Sed } 513193323Sed 514193323Sed // If we have an AST to keep updated, remember some pointer value that is 515193323Sed // stored into the alloca. 516193323Sed if (AST) 517193323Sed PointerAllocaValues[AllocaNum] = Info.AllocaPointerVal; 518193323Sed 519193323Sed // Remember the dbg.declare intrinsic describing this alloca, if any. 520203954Srdivacky if (Info.DbgDeclare) AllocaDbgDeclares[AllocaNum] = Info.DbgDeclare; 521203954Srdivacky 522203954Srdivacky // Keep the reverse mapping of the 'Allocas' array for the rename pass. 523203954Srdivacky AllocaLookup[Allocas[AllocaNum]] = AllocaNum; 524203954Srdivacky 525203954Srdivacky // At this point, we're committed to promoting the alloca using IDF's, and 526203954Srdivacky // the standard SSA construction algorithm. Determine which blocks need PHI 527203954Srdivacky // nodes and see if we can optimize out some work by avoiding insertion of 528203954Srdivacky // dead phi nodes. 529203954Srdivacky DetermineInsertionPoint(AI, AllocaNum, Info); 530203954Srdivacky } 531203954Srdivacky 532203954Srdivacky if (Allocas.empty()) 533203954Srdivacky return; // All of the allocas must have been trivial! 534203954Srdivacky 535203954Srdivacky LBI.clear(); 536203954Srdivacky 537203954Srdivacky 538203954Srdivacky // Set the incoming values for the basic block to be null values for all of 539203954Srdivacky // the alloca's. We do this in case there is a load of a value that has not 540203954Srdivacky // been stored yet. In this case, it will get this null value. 541203954Srdivacky // 542203954Srdivacky RenamePassData::ValVector Values(Allocas.size()); 543203954Srdivacky for (unsigned i = 0, e = Allocas.size(); i != e; ++i) 544203954Srdivacky Values[i] = UndefValue::get(Allocas[i]->getAllocatedType()); 545203954Srdivacky 546203954Srdivacky // Walks all basic blocks in the function performing the SSA rename algorithm 547203954Srdivacky // and inserting the phi nodes we marked as necessary 548203954Srdivacky // 549203954Srdivacky std::vector<RenamePassData> RenamePassWorkList; 550203954Srdivacky RenamePassWorkList.push_back(RenamePassData(F.begin(), 0, Values)); 551203954Srdivacky do { 552203954Srdivacky RenamePassData RPD; 553203954Srdivacky RPD.swap(RenamePassWorkList.back()); 554203954Srdivacky RenamePassWorkList.pop_back(); 555203954Srdivacky // RenamePass may add new worklist entries. 556193323Sed RenamePass(RPD.BB, RPD.Pred, RPD.Values, RenamePassWorkList); 557193323Sed } while (!RenamePassWorkList.empty()); 558199481Srdivacky 559193323Sed // The renamer uses the Visited set to avoid infinite loops. Clear it now. 560193323Sed Visited.clear(); 561193323Sed 562193323Sed // Remove the allocas themselves from the function. 563193323Sed for (unsigned i = 0, e = Allocas.size(); i != e; ++i) { 564198090Srdivacky Instruction *A = Allocas[i]; 565199481Srdivacky 566199481Srdivacky // If there are any uses of the alloca instructions left, they must be in 567198090Srdivacky // unreachable basic blocks that were not processed by walking the dominator 568198090Srdivacky // tree. Just delete the users now. 569193323Sed if (!A->use_empty()) 570193323Sed A->replaceAllUsesWith(UndefValue::get(A->getType())); 571193323Sed if (AST) AST->deleteValue(A); 572193323Sed A->eraseFromParent(); 573193323Sed } 574198090Srdivacky 575198090Srdivacky // Remove alloca's dbg.declare instrinsics from the function. 576198090Srdivacky for (unsigned i = 0, e = AllocaDbgDeclares.size(); i != e; ++i) 577198090Srdivacky if (DbgDeclareInst *DDI = AllocaDbgDeclares[i]) 578193323Sed DDI->eraseFromParent(); 579193323Sed 580198090Srdivacky // Loop over all of the PHI nodes and see if there are any that we can get 581193323Sed // rid of because they merge all of the same incoming values. This can 582193323Sed // happen due to undef values coming into the PHI nodes. This process is 583193323Sed // iterative, because eliminating one PHI node can cause others to be removed. 584193323Sed bool EliminatedAPHI = true; 585193323Sed while (EliminatedAPHI) { 586193323Sed EliminatedAPHI = false; 587198090Srdivacky 588193323Sed for (DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*>::iterator I = 589198090Srdivacky NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E;) { 590198090Srdivacky PHINode *PN = I->second; 591198090Srdivacky 592198090Srdivacky // If this PHI node merges one value and/or undefs, get the value. 593198090Srdivacky if (Value *V = SimplifyInstruction(PN, 0, &DT)) { 594198090Srdivacky if (AST && PN->getType()->isPointerTy()) 595199481Srdivacky AST->deleteValue(PN); 596198090Srdivacky PN->replaceAllUsesWith(V); 597198090Srdivacky PN->eraseFromParent(); 598198090Srdivacky NewPhiNodes.erase(I++); 599198090Srdivacky EliminatedAPHI = true; 600198090Srdivacky continue; 601198090Srdivacky } 602198090Srdivacky ++I; 603199989Srdivacky } 604198090Srdivacky } 605198090Srdivacky 606198090Srdivacky // At this point, the renamer has added entries to PHI nodes for all reachable 607198090Srdivacky // code. Unfortunately, there may be unreachable blocks which the renamer 608200581Srdivacky // hasn't traversed. If this is the case, the PHI nodes may not 609200581Srdivacky // have incoming values for all predecessors. Loop over all PHI nodes we have 610200581Srdivacky // created, inserting undef values if they are missing any incoming values. 611200581Srdivacky // 612200581Srdivacky for (DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*>::iterator I = 613200581Srdivacky NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) { 614200581Srdivacky // We want to do this once per basic block. As such, only process a block 615200581Srdivacky // when we find the PHI that is the first entry in the block. 616200581Srdivacky PHINode *SomePHI = I->second; 617200581Srdivacky BasicBlock *BB = SomePHI->getParent(); 618198090Srdivacky if (&BB->front() != SomePHI) 619198090Srdivacky continue; 620198090Srdivacky 621198090Srdivacky // Only do work here if there the PHI nodes are missing incoming values. We 622198090Srdivacky // know that all PHI nodes that were inserted in a block will have the same 623198090Srdivacky // number of incoming values, so we can just check any of them. 624199481Srdivacky if (SomePHI->getNumIncomingValues() == getNumPreds(BB)) 625199481Srdivacky continue; 626198090Srdivacky 627198090Srdivacky // Get the preds for BB. 628198090Srdivacky SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB)); 629198090Srdivacky 630198090Srdivacky // Ok, now we know that all of the PHI nodes are missing entries for some 631198090Srdivacky // basic blocks. Start by sorting the incoming predecessors for efficient 632198090Srdivacky // access. 633199481Srdivacky std::sort(Preds.begin(), Preds.end()); 634199481Srdivacky 635198090Srdivacky // Now we loop through all BB's which have entries in SomePHI and remove 636198090Srdivacky // them from the Preds list. 637198090Srdivacky for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) { 638198090Srdivacky // Do a log(n) search of the Preds list for the entry we want. 639198090Srdivacky SmallVector<BasicBlock*, 16>::iterator EntIt = 640198090Srdivacky std::lower_bound(Preds.begin(), Preds.end(), 641198090Srdivacky SomePHI->getIncomingBlock(i)); 642198090Srdivacky assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i)&& 643198090Srdivacky "PHI node has entry for a block which is not a predecessor!"); 644198090Srdivacky 645198090Srdivacky // Remove the entry 646198090Srdivacky Preds.erase(EntIt); 647198090Srdivacky } 648198090Srdivacky 649198090Srdivacky // At this point, the blocks left in the preds list must have dummy 650198090Srdivacky // entries inserted into every PHI nodes for the block. Update all the phi 651198090Srdivacky // nodes in this block that we are inserting (there could be phis before 652198090Srdivacky // mem2reg runs). 653198090Srdivacky unsigned NumBadPreds = SomePHI->getNumIncomingValues(); 654198090Srdivacky BasicBlock::iterator BBI = BB->begin(); 655198090Srdivacky while ((SomePHI = dyn_cast<PHINode>(BBI++)) && 656198090Srdivacky SomePHI->getNumIncomingValues() == NumBadPreds) { 657198090Srdivacky Value *UndefVal = UndefValue::get(SomePHI->getType()); 658198892Srdivacky for (unsigned pred = 0, e = Preds.size(); pred != e; ++pred) 659198090Srdivacky SomePHI->addIncoming(UndefVal, Preds[pred]); 660198090Srdivacky } 661193323Sed } 662193323Sed 663193323Sed NewPhiNodes.clear(); 664193323Sed} 665193323Sed 666193323Sed 667193323Sed/// ComputeLiveInBlocks - Determine which blocks the value is live in. These 668193323Sed/// are blocks which lead to uses. Knowing this allows us to avoid inserting 669193323Sed/// PHI nodes into blocks which don't lead to uses (thus, the inserted phi nodes 670193323Sed/// would be dead). 671193323Sedvoid PromoteMem2Reg:: 672193323SedComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info, 673193323Sed const SmallPtrSet<BasicBlock*, 32> &DefBlocks, 674193323Sed SmallPtrSet<BasicBlock*, 32> &LiveInBlocks) { 675199481Srdivacky 676193323Sed // To determine liveness, we must iterate through the predecessors of blocks 677193323Sed // where the def is live. Blocks are added to the worklist if we need to 678193323Sed // check their predecessors. Start with all the using blocks. 679193323Sed SmallVector<BasicBlock*, 64> LiveInBlockWorklist(Info.UsingBlocks.begin(), 680193323Sed Info.UsingBlocks.end()); 681193323Sed 682193323Sed // If any of the using blocks is also a definition block, check to see if the 683193323Sed // definition occurs before or after the use. If it happens before the use, 684193323Sed // the value isn't really live-in. 685193323Sed for (unsigned i = 0, e = LiveInBlockWorklist.size(); i != e; ++i) { 686193323Sed BasicBlock *BB = LiveInBlockWorklist[i]; 687193323Sed if (!DefBlocks.count(BB)) continue; 688193323Sed 689193323Sed // Okay, this is a block that both uses and defines the value. If the first 690193323Sed // reference to the alloca is a def (store), then we know it isn't live-in. 691193323Sed for (BasicBlock::iterator I = BB->begin(); ; ++I) { 692193323Sed if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 693193323Sed if (SI->getOperand(1) != AI) continue; 694193323Sed 695193323Sed // We found a store to the alloca before a load. The alloca is not 696193323Sed // actually live-in here. 697193323Sed LiveInBlockWorklist[i] = LiveInBlockWorklist.back(); 698193323Sed LiveInBlockWorklist.pop_back(); 699193323Sed --i, --e; 700193323Sed break; 701193323Sed } 702199481Srdivacky 703199481Srdivacky if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 704198090Srdivacky if (LI->getOperand(0) != AI) continue; 705198396Srdivacky 706198396Srdivacky // Okay, we found a load before a store to the alloca. It is actually 707198396Srdivacky // live into this block. 708198090Srdivacky break; 709199481Srdivacky } 710193323Sed } 711193323Sed } 712193323Sed 713193323Sed // Now that we have a set of blocks where the phi is live-in, recursively add 714193323Sed // their predecessors until we find the full region the value is live. 715203954Srdivacky while (!LiveInBlockWorklist.empty()) { 716193323Sed BasicBlock *BB = LiveInBlockWorklist.pop_back_val(); 717193323Sed 718203954Srdivacky // The block really is live in here, insert it into the set. If already in 719199989Srdivacky // the set, then it has already been processed. 720199989Srdivacky if (!LiveInBlocks.insert(BB)) 721199989Srdivacky continue; 722199989Srdivacky 723199989Srdivacky // Since the value is live into BB, it is either defined in a predecessor or 724199989Srdivacky // live into it to. Add the preds to the worklist unless they are a 725193323Sed // defining block. 726193323Sed for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 727199481Srdivacky BasicBlock *P = *PI; 728199481Srdivacky 729198090Srdivacky // The value is not live into a predecessor if it defines the value. 730199481Srdivacky if (DefBlocks.count(P)) 731193323Sed continue; 732193323Sed 733193323Sed // Otherwise it is, add to the worklist. 734193323Sed LiveInBlockWorklist.push_back(P); 735193323Sed } 736193323Sed } 737193323Sed} 738193323Sed 739199989Srdivacky/// DetermineInsertionPoint - At this point, we're committed to promoting the 740199989Srdivacky/// alloca using IDF's, and the standard SSA construction algorithm. Determine 741199989Srdivacky/// which blocks need phi nodes and see if we can optimize out some work by 742199989Srdivacky/// avoiding insertion of dead phi nodes. 743193323Sedvoid PromoteMem2Reg::DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum, 744193323Sed AllocaInfo &Info) { 745193323Sed // Unique the set of defining blocks for efficient lookup. 746193323Sed SmallPtrSet<BasicBlock*, 32> DefBlocks; 747193323Sed DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end()); 748193323Sed 749199481Srdivacky // Determine which blocks the value is live in. These are blocks which lead 750193323Sed // to uses. 751193323Sed SmallPtrSet<BasicBlock*, 32> LiveInBlocks; 752193323Sed ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks); 753193323Sed 754193323Sed // Use a priority queue keyed on dominator tree level so that inserted nodes 755193323Sed // are handled from the bottom of the dominator tree upwards. 756193323Sed typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>, 757202375Srdivacky DomTreeNodeCompare> IDFPriorityQueue; 758202375Srdivacky IDFPriorityQueue PQ; 759193323Sed 760193323Sed for (SmallPtrSet<BasicBlock*, 32>::const_iterator I = DefBlocks.begin(), 761193323Sed E = DefBlocks.end(); I != E; ++I) { 762193323Sed if (DomTreeNode *Node = DT.getNode(*I)) 763193323Sed PQ.push(std::make_pair(Node, DomLevels[Node])); 764193323Sed } 765193323Sed 766193323Sed SmallVector<std::pair<unsigned, BasicBlock*>, 32> DFBlocks; 767193323Sed SmallPtrSet<DomTreeNode*, 32> Visited; 768193323Sed SmallVector<DomTreeNode*, 32> Worklist; 769193323Sed while (!PQ.empty()) { 770194612Sed DomTreeNodePair RootPair = PQ.top(); 771193323Sed PQ.pop(); 772193323Sed DomTreeNode *Root = RootPair.first; 773199481Srdivacky unsigned RootLevel = RootPair.second; 774193323Sed 775193323Sed // Walk all dominator tree children of Root, inspecting their CFG edges with 776193323Sed // targets elsewhere on the dominator tree. Only targets whose level is at 777193323Sed // most Root's level are added to the iterated dominance frontier of the 778193323Sed // definition set. 779193323Sed 780193323Sed Worklist.clear(); 781193323Sed Worklist.push_back(Root); 782193323Sed 783193323Sed while (!Worklist.empty()) { 784193323Sed DomTreeNode *Node = Worklist.pop_back_val(); 785193323Sed BasicBlock *BB = Node->getBlock(); 786193323Sed 787193323Sed for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; 788193323Sed ++SI) { 789194612Sed DomTreeNode *SuccNode = DT.getNode(*SI); 790198892Srdivacky 791198892Srdivacky // Quickly skip all CFG edges that are also dominator tree edges instead 792198892Srdivacky // of catching them below. 793193323Sed if (SuccNode->getIDom() == Node) 794193323Sed continue; 795193323Sed 796193323Sed unsigned SuccLevel = DomLevels[SuccNode]; 797193323Sed if (SuccLevel > RootLevel) 798193323Sed continue; 799193323Sed 800193323Sed if (!Visited.insert(SuccNode)) 801193323Sed continue; 802193323Sed 803193323Sed BasicBlock *SuccBB = SuccNode->getBlock(); 804193323Sed if (!LiveInBlocks.count(SuccBB)) 805193323Sed continue; 806193323Sed 807193323Sed DFBlocks.push_back(std::make_pair(BBNumbers[SuccBB], SuccBB)); 808193323Sed if (!DefBlocks.count(SuccBB)) 809193323Sed PQ.push(std::make_pair(SuccNode, SuccLevel)); 810193323Sed } 811193323Sed 812193323Sed for (DomTreeNode::iterator CI = Node->begin(), CE = Node->end(); CI != CE; 813193323Sed ++CI) { 814193323Sed if (!Visited.count(*CI)) 815199481Srdivacky Worklist.push_back(*CI); 816193323Sed } 817198090Srdivacky } 818198090Srdivacky } 819193323Sed 820193323Sed if (DFBlocks.size() > 1) 821193323Sed std::sort(DFBlocks.begin(), DFBlocks.end()); 822193323Sed 823193323Sed unsigned CurrentVersion = 0; 824193323Sed for (unsigned i = 0, e = DFBlocks.size(); i != e; ++i) 825193323Sed QueuePhiNode(DFBlocks[i].second, AllocaNum, CurrentVersion); 826193323Sed} 827193323Sed 828193323Sed/// RewriteSingleStoreAlloca - If there is only a single store to this value, 829193323Sed/// replace any loads of it that are directly dominated by the definition with 830193323Sed/// the value stored. 831193323Sedvoid PromoteMem2Reg::RewriteSingleStoreAlloca(AllocaInst *AI, 832193323Sed AllocaInfo &Info, 833193323Sed LargeBlockInfo &LBI) { 834193323Sed StoreInst *OnlyStore = Info.OnlyStore; 835193323Sed bool StoringGlobalVal = !isa<Instruction>(OnlyStore->getOperand(0)); 836193323Sed BasicBlock *StoreBB = OnlyStore->getParent(); 837193323Sed int StoreIndex = -1; 838198892Srdivacky 839193323Sed // Clear out UsingBlocks. We will reconstruct it here if needed. 840193323Sed Info.UsingBlocks.clear(); 841193323Sed 842193323Sed for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E; ) { 843193323Sed Instruction *UserInst = cast<Instruction>(*UI++); 844193323Sed if (!isa<LoadInst>(UserInst)) { 845193323Sed assert(UserInst == OnlyStore && "Should only have load/stores"); 846193323Sed continue; 847193323Sed } 848193323Sed LoadInst *LI = cast<LoadInst>(UserInst); 849203954Srdivacky 850203954Srdivacky // Okay, if we have a load from the alloca, we want to replace it with the 851199481Srdivacky // only value stored to the alloca. We can do this if the value is 852193323Sed // dominated by the store. If not, we use the rest of the mem2reg machinery 853193323Sed // to insert the phi nodes as needed. 854193323Sed if (!StoringGlobalVal) { // Non-instructions are always dominated. 855193323Sed if (LI->getParent() == StoreBB) { 856193323Sed // If we have a use that is in the same block as the store, compare the 857193323Sed // indices of the two instructions to see which one came first. If the 858193323Sed // load came before the store, we can't handle it. 859193323Sed if (StoreIndex == -1) 860193323Sed StoreIndex = LBI.getInstructionIndex(OnlyStore); 861193323Sed 862193323Sed if (unsigned(StoreIndex) > LBI.getInstructionIndex(LI)) { 863199481Srdivacky // Can't handle this load, bail out. 864193323Sed Info.UsingBlocks.push_back(StoreBB); 865193323Sed continue; 866193323Sed } 867193323Sed 868193323Sed } else if (LI->getParent() != StoreBB && 869193323Sed !dominates(StoreBB, LI->getParent())) { 870193323Sed // If the load and store are in different blocks, use BB dominance to 871193323Sed // check their relationships. If the store doesn't dom the use, bail 872199481Srdivacky // out. 873199481Srdivacky Info.UsingBlocks.push_back(LI->getParent()); 874199481Srdivacky continue; 875193323Sed } 876193323Sed } 877193323Sed 878193323Sed // Otherwise, we *can* safely rewrite this load. 879193323Sed Value *ReplVal = OnlyStore->getOperand(0); 880199481Srdivacky // If the replacement value is the load, this must occur in unreachable 881199481Srdivacky // code. 882193323Sed if (ReplVal == LI) 883193323Sed ReplVal = UndefValue::get(LI->getType()); 884193323Sed LI->replaceAllUsesWith(ReplVal); 885193323Sed if (AST && LI->getType()->isPointerTy()) 886193323Sed AST->deleteValue(LI); 887193323Sed LI->eraseFromParent(); 888193323Sed LBI.deleteValue(LI); 889199481Srdivacky } 890199481Srdivacky} 891193323Sed 892193323Sednamespace { 893193323Sed 894199481Srdivacky/// StoreIndexSearchPredicate - This is a helper predicate used to search by the 895193323Sed/// first element of a pair. 896199481Srdivackystruct StoreIndexSearchPredicate { 897193323Sed bool operator()(const std::pair<unsigned, StoreInst*> &LHS, 898193323Sed const std::pair<unsigned, StoreInst*> &RHS) { 899193323Sed return LHS.first < RHS.first; 900193323Sed } 901193323Sed}; 902193323Sed 903193323Sed} 904193323Sed 905199481Srdivacky/// PromoteSingleBlockAlloca - Many allocas are only used within a single basic 906193323Sed/// block. If this is the case, avoid traversing the CFG and inserting a lot of 907193323Sed/// potentially useless PHI nodes by just performing a single linear pass over 908193323Sed/// the basic block using the Alloca. 909193323Sed/// 910193323Sed/// If we cannot promote this alloca (because it is read before it is written), 911193323Sed/// return true. This is necessary in cases where, due to control flow, the 912199481Srdivacky/// alloca is potentially undefined on some control flow paths. e.g. code like 913199481Srdivacky/// this is potentially correct: 914199481Srdivacky/// 915193323Sed/// for (...) { if (c) { A = undef; undef = B; } } 916193323Sed/// 917202375Srdivacky/// ... so long as A is not used before undef is set. 918202375Srdivacky/// 919202375Srdivackyvoid PromoteMem2Reg::PromoteSingleBlockAlloca(AllocaInst *AI, AllocaInfo &Info, 920202375Srdivacky LargeBlockInfo &LBI) { 921202375Srdivacky // The trickiest case to handle is when we have large blocks. Because of this, 922202375Srdivacky // this code is optimized assuming that large blocks happen. This does not 923202375Srdivacky // significantly pessimize the small block case. This uses LargeBlockInfo to 924202375Srdivacky // make it efficient to get the index of various operations in the block. 925202375Srdivacky 926202375Srdivacky // Clear out UsingBlocks. We will reconstruct it here if needed. 927202375Srdivacky Info.UsingBlocks.clear(); 928202375Srdivacky 929202375Srdivacky // Walk the use-def list of the alloca, getting the locations of all stores. 930202375Srdivacky typedef SmallVector<std::pair<unsigned, StoreInst*>, 64> StoresByIndexTy; 931193323Sed StoresByIndexTy StoresByIndex; 932199481Srdivacky 933199481Srdivacky for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); 934193323Sed UI != E; ++UI) 935193323Sed if (StoreInst *SI = dyn_cast<StoreInst>(*UI)) 936193323Sed StoresByIndex.push_back(std::make_pair(LBI.getInstructionIndex(SI), SI)); 937193323Sed 938193323Sed // If there are no stores to the alloca, just replace any loads with undef. 939193323Sed if (StoresByIndex.empty()) { 940193323Sed for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;) 941193323Sed if (LoadInst *LI = dyn_cast<LoadInst>(*UI++)) { 942193323Sed LI->replaceAllUsesWith(UndefValue::get(LI->getType())); 943193323Sed if (AST && LI->getType()->isPointerTy()) 944193323Sed AST->deleteValue(LI); 945193323Sed LBI.deleteValue(LI); 946193323Sed LI->eraseFromParent(); 947193323Sed } 948193323Sed return; 949193323Sed } 950193323Sed 951193323Sed // Sort the stores by their index, making it efficient to do a lookup with a 952193323Sed // binary search. 953193323Sed std::sort(StoresByIndex.begin(), StoresByIndex.end()); 954193323Sed 955193323Sed // Walk all of the loads from this alloca, replacing them with the nearest 956193323Sed // store above them, if any. 957193323Sed for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;) { 958193323Sed LoadInst *LI = dyn_cast<LoadInst>(*UI++); 959193323Sed if (!LI) continue; 960193323Sed 961193323Sed unsigned LoadIdx = LBI.getInstructionIndex(LI); 962193323Sed 963193323Sed // Find the nearest store that has a lower than this load. 964193323Sed StoresByIndexTy::iterator I = 965193323Sed std::lower_bound(StoresByIndex.begin(), StoresByIndex.end(), 966193323Sed std::pair<unsigned, StoreInst*>(LoadIdx, static_cast<StoreInst*>(0)), 967193323Sed StoreIndexSearchPredicate()); 968193323Sed 969193323Sed // If there is no store before this load, then we can't promote this load. 970193323Sed if (I == StoresByIndex.begin()) { 971193323Sed // Can't handle this load, bail out. 972193323Sed Info.UsingBlocks.push_back(LI->getParent()); 973193323Sed continue; 974193323Sed } 975198396Srdivacky 976198396Srdivacky // Otherwise, there was a store before this load, the load takes its value. 977193323Sed --I; 978193323Sed LI->replaceAllUsesWith(I->second->getOperand(0)); 979193323Sed if (AST && LI->getType()->isPointerTy()) 980193323Sed AST->deleteValue(LI); 981198396Srdivacky LI->eraseFromParent(); 982193323Sed LBI.deleteValue(LI); 983198396Srdivacky } 984193323Sed} 985193323Sed 986193323Sed// QueuePhiNode - queues a phi-node to be added to a basic-block for a specific 987193323Sed// Alloca returns true if there wasn't already a phi-node for that variable 988193323Sed// 989193323Sedbool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo, 990193323Sed unsigned &Version) { 991193323Sed // Look up the basic-block in question. 992193323Sed PHINode *&PN = NewPhiNodes[std::make_pair(BB, AllocaNo)]; 993193323Sed 994193323Sed // If the BB already has a phi node added for the i'th alloca then we're done! 995193323Sed if (PN) return false; 996193323Sed 997193323Sed // Create a PhiNode using the dereferenced type... and add the phi-node to the 998193323Sed // BasicBlock. 999193323Sed PN = PHINode::Create(Allocas[AllocaNo]->getAllocatedType(), getNumPreds(BB), 1000193323Sed Allocas[AllocaNo]->getName() + "." + Twine(Version++), 1001193323Sed BB->begin()); 1002193323Sed ++NumPHIInsert; 1003193323Sed PhiToAllocaMap[PN] = AllocaNo; 1004193323Sed 1005193323Sed if (AST && PN->getType()->isPointerTy()) 1006193323Sed AST->copyValue(PointerAllocaValues[AllocaNo], PN); 1007193323Sed 1008193323Sed return true; 1009193323Sed} 1010193323Sed 1011198090Srdivacky// RenamePass - Recursively traverse the CFG of the function, renaming loads and 1012198090Srdivacky// stores to the allocas which we are promoting. IncomingVals indicates what 1013198090Srdivacky// value each Alloca contains on exit from the predecessor block Pred. 1014198090Srdivacky// 1015193323Sedvoid PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred, 1016198090Srdivacky RenamePassData::ValVector &IncomingVals, 1017198090Srdivacky std::vector<RenamePassData> &Worklist) { 1018198090SrdivackyNextIteration: 1019193323Sed // If we are inserting any phi nodes into this BB, they will already be in the 1020193323Sed // block. 1021193323Sed if (PHINode *APN = dyn_cast<PHINode>(BB->begin())) { 1022198090Srdivacky // If we have PHI nodes to update, compute the number of edges from Pred to 1023193323Sed // BB. 1024193323Sed if (PhiToAllocaMap.count(APN)) { 1025193323Sed // We want to be able to distinguish between PHI nodes being inserted by 1026193323Sed // this invocation of mem2reg from those phi nodes that already existed in 1027198090Srdivacky // the IR before mem2reg was run. We determine that APN is being inserted 1028193323Sed // because it is missing incoming edges. All other PHI nodes being 1029193323Sed // inserted by this pass of mem2reg will have the same number of incoming 1030198090Srdivacky // operands so far. Remember this count. 1031198090Srdivacky unsigned NewPHINumOperands = APN->getNumOperands(); 1032193323Sed 1033198090Srdivacky unsigned NumEdges = 0; 1034193323Sed for (succ_iterator I = succ_begin(Pred), E = succ_end(Pred); I != E; ++I) 1035198090Srdivacky if (*I == BB) 1036193323Sed ++NumEdges; 1037198090Srdivacky assert(NumEdges && "Must be at least one edge from Pred to BB!"); 1038193323Sed 1039198090Srdivacky // Add entries for all the phis. 1040193323Sed BasicBlock::iterator PNI = BB->begin(); 1041198090Srdivacky do { 1042193323Sed unsigned AllocaNo = PhiToAllocaMap[APN]; 1043198090Srdivacky 1044198090Srdivacky // Add N incoming values to the PHI node. 1045193323Sed for (unsigned i = 0; i != NumEdges; ++i) 1046198090Srdivacky APN->addIncoming(IncomingVals[AllocaNo], Pred); 1047193323Sed 1048193323Sed // The currently active variable for this block is now the PHI. 1049193323Sed IncomingVals[AllocaNo] = APN; 1050193323Sed 1051199481Srdivacky // Get the next phi node. 1052193323Sed ++PNI; 1053193323Sed APN = dyn_cast<PHINode>(PNI); 1054193323Sed if (APN == 0) break; 1055193323Sed 1056193323Sed // Verify that it is missing entries. If not, it is not being inserted 1057193323Sed // by this mem2reg invocation so we want to ignore it. 1058193323Sed } while (APN->getNumOperands() == NewPHINumOperands); 1059198090Srdivacky } 1060199481Srdivacky } 1061198090Srdivacky 1062199481Srdivacky // Don't revisit blocks. 1063198090Srdivacky if (!Visited.insert(BB)) return; 1064193323Sed 1065193323Sed for (BasicBlock::iterator II = BB->begin(); !isa<TerminatorInst>(II); ) { 1066193323Sed Instruction *I = II++; // get the instruction, increment iterator 1067193323Sed 1068199481Srdivacky if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 1069193323Sed AllocaInst *Src = dyn_cast<AllocaInst>(LI->getPointerOperand()); 1070193323Sed if (!Src) continue; 1071193323Sed 1072193323Sed DenseMap<AllocaInst*, unsigned>::iterator AI = AllocaLookup.find(Src); 1073193323Sed if (AI == AllocaLookup.end()) continue; 1074193323Sed 1075193323Sed Value *V = IncomingVals[AI->second]; 1076198090Srdivacky 1077199481Srdivacky // Anything using the load now uses the current value. 1078198090Srdivacky LI->replaceAllUsesWith(V); 1079199481Srdivacky if (AST && LI->getType()->isPointerTy()) 1080198090Srdivacky AST->deleteValue(LI); 1081193323Sed BB->getInstList().erase(LI); 1082193323Sed } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 1083193323Sed // Delete this instruction and mark the name as the current holder of the 1084193323Sed // value 1085193323Sed AllocaInst *Dest = dyn_cast<AllocaInst>(SI->getPointerOperand()); 1086193323Sed if (!Dest) continue; 1087193323Sed 1088198090Srdivacky DenseMap<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Dest); 1089193323Sed if (ai == AllocaLookup.end()) 1090198090Srdivacky continue; 1091198090Srdivacky 1092193323Sed // what value were we writing? 1093193323Sed IncomingVals[ai->second] = SI->getOperand(0); 1094193323Sed // Record debuginfo for the store before removing it. 1095198090Srdivacky if (DbgDeclareInst *DDI = AllocaDbgDeclares[ai->second]) { 1096193323Sed if (!DIB) 1097193323Sed DIB = new DIBuilder(*SI->getParent()->getParent()->getParent()); 1098193323Sed ConvertDebugDeclareToDebugValue(DDI, SI, *DIB); 1099193323Sed } 1100193323Sed BB->getInstList().erase(SI); 1101198090Srdivacky } 1102193323Sed } 1103198090Srdivacky 1104193323Sed // 'Recurse' to our successors. 1105198090Srdivacky succ_iterator I = succ_begin(BB), E = succ_end(BB); 1106199481Srdivacky if (I == E) return; 1107198090Srdivacky 1108199481Srdivacky // Keep track of the successors so we don't visit the same successor twice 1109198090Srdivacky SmallPtrSet<BasicBlock*, 8> VisitedSuccs; 1110199481Srdivacky 1111193323Sed // Handle the first successor without using the worklist. 1112193323Sed VisitedSuccs.insert(*I); 1113198090Srdivacky Pred = BB; 1114199481Srdivacky BB = *I; 1115198090Srdivacky ++I; 1116199481Srdivacky 1117198090Srdivacky for (; I != E; ++I) 1118199481Srdivacky if (VisitedSuccs.insert(*I)) 1119198090Srdivacky Worklist.push_back(RenamePassData(*I, Pred, IncomingVals)); 1120199481Srdivacky 1121193323Sed goto NextIteration; 1122193323Sed} 1123198090Srdivacky 1124199481Srdivacky/// PromoteMemToReg - Promote the specified list of alloca instructions into 1125193323Sed/// scalar registers, inserting PHI nodes as appropriate. This function does 1126193323Sed/// not modify the CFG of the function at all. All allocas must be from the 1127198090Srdivacky/// same function. 1128199481Srdivacky/// 1129198090Srdivacky/// If AST is specified, the specified tracker is updated to reflect changes 1130199481Srdivacky/// made to the IR. 1131193323Sed/// 1132193323Sedvoid llvm::PromoteMemToReg(const std::vector<AllocaInst*> &Allocas, 1133198090Srdivacky DominatorTree &DT, AliasSetTracker *AST) { 1134199481Srdivacky // If there is nothing to do, bail out... 1135198090Srdivacky if (Allocas.empty()) return; 1136199481Srdivacky 1137198090Srdivacky PromoteMem2Reg(Allocas, DT, AST).run(); 1138198090Srdivacky} 1139193323Sed