1193323Sed//===- 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// 10193323Sed// 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 12218893Sdim// transformed by using iterated dominator frontiers to place PHI nodes, then 13218893Sdim// traversing the function in depth-first order to rewrite loads and stores as 14218893Sdim// appropriate. 15193323Sed// 16193323Sed//===----------------------------------------------------------------------===// 17193323Sed 18193323Sed#include "llvm/Transforms/Utils/PromoteMemToReg.h" 19261991Sdim#include "llvm/ADT/ArrayRef.h" 20193323Sed#include "llvm/ADT/DenseMap.h" 21249423Sdim#include "llvm/ADT/STLExtras.h" 22193323Sed#include "llvm/ADT/SmallPtrSet.h" 23193323Sed#include "llvm/ADT/SmallVector.h" 24193323Sed#include "llvm/ADT/Statistic.h" 25249423Sdim#include "llvm/Analysis/AliasSetTracker.h" 26249423Sdim#include "llvm/Analysis/InstructionSimplify.h" 27288943Sdim#include "llvm/Analysis/IteratedDominanceFrontier.h" 28249423Sdim#include "llvm/Analysis/ValueTracking.h" 29276479Sdim#include "llvm/IR/CFG.h" 30249423Sdim#include "llvm/IR/Constants.h" 31276479Sdim#include "llvm/IR/DIBuilder.h" 32276479Sdim#include "llvm/IR/DebugInfo.h" 33249423Sdim#include "llvm/IR/DerivedTypes.h" 34276479Sdim#include "llvm/IR/Dominators.h" 35249423Sdim#include "llvm/IR/Function.h" 36249423Sdim#include "llvm/IR/Instructions.h" 37249423Sdim#include "llvm/IR/IntrinsicInst.h" 38249423Sdim#include "llvm/IR/Metadata.h" 39288943Sdim#include "llvm/IR/Module.h" 40249423Sdim#include "llvm/Transforms/Utils/Local.h" 41193323Sed#include <algorithm> 42193323Sedusing namespace llvm; 43193323Sed 44276479Sdim#define DEBUG_TYPE "mem2reg" 45276479Sdim 46193323SedSTATISTIC(NumLocalPromoted, "Number of alloca's promoted within one block"); 47193323SedSTATISTIC(NumSingleStore, "Number of alloca's promoted with a single store"); 48193323SedSTATISTIC(NumDeadAlloca, "Number of dead alloca's removed"); 49193323SedSTATISTIC(NumPHIInsert, "Number of PHI nodes inserted"); 50193323Sed 51193323Sedbool llvm::isAllocaPromotable(const AllocaInst *AI) { 52193323Sed // FIXME: If the memory unit is of pointer or integer type, we can permit 53193323Sed // assignments to subsections of the memory unit. 54276479Sdim unsigned AS = AI->getType()->getAddressSpace(); 55193323Sed 56193323Sed // Only allow direct and non-volatile loads and stores... 57276479Sdim for (const User *U : AI->users()) { 58210299Sed if (const LoadInst *LI = dyn_cast<LoadInst>(U)) { 59226633Sdim // Note that atomic loads can be transformed; atomic semantics do 60226633Sdim // not have any meaning for a local alloca. 61193323Sed if (LI->isVolatile()) 62193323Sed return false; 63210299Sed } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) { 64193323Sed if (SI->getOperand(0) == AI) 65261991Sdim return false; // Don't allow a store OF the AI, only INTO the AI. 66226633Sdim // Note that atomic stores can be transformed; atomic semantics do 67226633Sdim // not have any meaning for a local alloca. 68193323Sed if (SI->isVolatile()) 69193323Sed return false; 70224145Sdim } else if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(U)) { 71224145Sdim if (II->getIntrinsicID() != Intrinsic::lifetime_start && 72224145Sdim II->getIntrinsicID() != Intrinsic::lifetime_end) 73224145Sdim return false; 74224145Sdim } else if (const BitCastInst *BCI = dyn_cast<BitCastInst>(U)) { 75276479Sdim if (BCI->getType() != Type::getInt8PtrTy(U->getContext(), AS)) 76224145Sdim return false; 77224145Sdim if (!onlyUsedByLifetimeMarkers(BCI)) 78224145Sdim return false; 79224145Sdim } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) { 80276479Sdim if (GEPI->getType() != Type::getInt8PtrTy(U->getContext(), AS)) 81224145Sdim return false; 82224145Sdim if (!GEPI->hasAllZeroIndices()) 83224145Sdim return false; 84224145Sdim if (!onlyUsedByLifetimeMarkers(GEPI)) 85224145Sdim return false; 86193323Sed } else { 87193323Sed return false; 88193323Sed } 89210299Sed } 90193323Sed 91193323Sed return true; 92193323Sed} 93193323Sed 94193323Sednamespace { 95193323Sed 96261991Sdimstruct AllocaInfo { 97261991Sdim SmallVector<BasicBlock *, 32> DefiningBlocks; 98261991Sdim SmallVector<BasicBlock *, 32> UsingBlocks; 99261991Sdim 100261991Sdim StoreInst *OnlyStore; 101261991Sdim BasicBlock *OnlyBlock; 102261991Sdim bool OnlyUsedInOneBlock; 103261991Sdim 104261991Sdim Value *AllocaPointerVal; 105261991Sdim DbgDeclareInst *DbgDeclare; 106261991Sdim 107261991Sdim void clear() { 108261991Sdim DefiningBlocks.clear(); 109261991Sdim UsingBlocks.clear(); 110276479Sdim OnlyStore = nullptr; 111276479Sdim OnlyBlock = nullptr; 112261991Sdim OnlyUsedInOneBlock = true; 113276479Sdim AllocaPointerVal = nullptr; 114276479Sdim DbgDeclare = nullptr; 115261991Sdim } 116261991Sdim 117261991Sdim /// Scan the uses of the specified alloca, filling in the AllocaInfo used 118261991Sdim /// by the rest of the pass to reason about the uses of this alloca. 119261991Sdim void AnalyzeAlloca(AllocaInst *AI) { 120261991Sdim clear(); 121261991Sdim 122261991Sdim // As we scan the uses of the alloca instruction, keep track of stores, 123261991Sdim // and decide whether all of the loads and stores to the alloca are within 124261991Sdim // the same basic block. 125276479Sdim for (auto UI = AI->user_begin(), E = AI->user_end(); UI != E;) { 126261991Sdim Instruction *User = cast<Instruction>(*UI++); 127261991Sdim 128261991Sdim if (StoreInst *SI = dyn_cast<StoreInst>(User)) { 129261991Sdim // Remember the basic blocks which define new values for the alloca 130261991Sdim DefiningBlocks.push_back(SI->getParent()); 131261991Sdim AllocaPointerVal = SI->getOperand(0); 132261991Sdim OnlyStore = SI; 133261991Sdim } else { 134261991Sdim LoadInst *LI = cast<LoadInst>(User); 135261991Sdim // Otherwise it must be a load instruction, keep track of variable 136261991Sdim // reads. 137261991Sdim UsingBlocks.push_back(LI->getParent()); 138261991Sdim AllocaPointerVal = LI; 139261991Sdim } 140261991Sdim 141261991Sdim if (OnlyUsedInOneBlock) { 142276479Sdim if (!OnlyBlock) 143261991Sdim OnlyBlock = User->getParent(); 144261991Sdim else if (OnlyBlock != User->getParent()) 145261991Sdim OnlyUsedInOneBlock = false; 146261991Sdim } 147193323Sed } 148261991Sdim 149261991Sdim DbgDeclare = FindAllocaDbgDeclare(AI); 150261991Sdim } 151261991Sdim}; 152261991Sdim 153261991Sdim// Data package used by RenamePass() 154261991Sdimclass RenamePassData { 155261991Sdimpublic: 156261991Sdim typedef std::vector<Value *> ValVector; 157261991Sdim 158276479Sdim RenamePassData() : BB(nullptr), Pred(nullptr), Values() {} 159261991Sdim RenamePassData(BasicBlock *B, BasicBlock *P, const ValVector &V) 160261991Sdim : BB(B), Pred(P), Values(V) {} 161261991Sdim BasicBlock *BB; 162261991Sdim BasicBlock *Pred; 163261991Sdim ValVector Values; 164261991Sdim 165261991Sdim void swap(RenamePassData &RHS) { 166261991Sdim std::swap(BB, RHS.BB); 167261991Sdim std::swap(Pred, RHS.Pred); 168261991Sdim Values.swap(RHS.Values); 169261991Sdim } 170261991Sdim}; 171261991Sdim 172261991Sdim/// \brief This assigns and keeps a per-bb relative ordering of load/store 173261991Sdim/// instructions in the block that directly load or store an alloca. 174261991Sdim/// 175261991Sdim/// This functionality is important because it avoids scanning large basic 176261991Sdim/// blocks multiple times when promoting many allocas in the same block. 177261991Sdimclass LargeBlockInfo { 178261991Sdim /// \brief For each instruction that we track, keep the index of the 179261991Sdim /// instruction. 180193323Sed /// 181261991Sdim /// The index starts out as the number of the instruction from the start of 182261991Sdim /// the block. 183261991Sdim DenseMap<const Instruction *, unsigned> InstNumbers; 184261991Sdim 185261991Sdimpublic: 186261991Sdim 187261991Sdim /// This code only looks at accesses to allocas. 188261991Sdim static bool isInterestingInstruction(const Instruction *I) { 189261991Sdim return (isa<LoadInst>(I) && isa<AllocaInst>(I->getOperand(0))) || 190261991Sdim (isa<StoreInst>(I) && isa<AllocaInst>(I->getOperand(1))); 191261991Sdim } 192261991Sdim 193261991Sdim /// Get or calculate the index of the specified instruction. 194261991Sdim unsigned getInstructionIndex(const Instruction *I) { 195261991Sdim assert(isInterestingInstruction(I) && 196261991Sdim "Not a load/store to/from an alloca?"); 197261991Sdim 198261991Sdim // If we already have this instruction number, return it. 199261991Sdim DenseMap<const Instruction *, unsigned>::iterator It = InstNumbers.find(I); 200261991Sdim if (It != InstNumbers.end()) 201193323Sed return It->second; 202193323Sed 203261991Sdim // Scan the whole block to get the instruction. This accumulates 204261991Sdim // information for every interesting instruction in the block, in order to 205261991Sdim // avoid gratuitus rescans. 206261991Sdim const BasicBlock *BB = I->getParent(); 207261991Sdim unsigned InstNo = 0; 208296417Sdim for (const Instruction &BBI : *BB) 209296417Sdim if (isInterestingInstruction(&BBI)) 210296417Sdim InstNumbers[&BBI] = InstNo++; 211261991Sdim It = InstNumbers.find(I); 212193323Sed 213261991Sdim assert(It != InstNumbers.end() && "Didn't insert instruction?"); 214261991Sdim return It->second; 215261991Sdim } 216193323Sed 217261991Sdim void deleteValue(const Instruction *I) { InstNumbers.erase(I); } 218193323Sed 219261991Sdim void clear() { InstNumbers.clear(); } 220261991Sdim}; 221203954Srdivacky 222261991Sdimstruct PromoteMem2Reg { 223261991Sdim /// The alloca instructions being promoted. 224261991Sdim std::vector<AllocaInst *> Allocas; 225261991Sdim DominatorTree &DT; 226261991Sdim DIBuilder DIB; 227193323Sed 228261991Sdim /// An AliasSetTracker object to update. If null, don't update it. 229261991Sdim AliasSetTracker *AST; 230193323Sed 231280031Sdim /// A cache of @llvm.assume intrinsics used by SimplifyInstruction. 232280031Sdim AssumptionCache *AC; 233280031Sdim 234261991Sdim /// Reverse mapping of Allocas. 235261991Sdim DenseMap<AllocaInst *, unsigned> AllocaLookup; 236218893Sdim 237261991Sdim /// \brief The PhiNodes we're adding. 238261991Sdim /// 239261991Sdim /// That map is used to simplify some Phi nodes as we iterate over it, so 240261991Sdim /// it should have deterministic iterators. We could use a MapVector, but 241261991Sdim /// since we already maintain a map from BasicBlock* to a stable numbering 242261991Sdim /// (BBNumbers), the DenseMap is more efficient (also supports removal). 243261991Sdim DenseMap<std::pair<unsigned, unsigned>, PHINode *> NewPhiNodes; 244193323Sed 245261991Sdim /// For each PHI node, keep track of which entry in Allocas it corresponds 246261991Sdim /// to. 247261991Sdim DenseMap<PHINode *, unsigned> PhiToAllocaMap; 248193323Sed 249261991Sdim /// If we are updating an AliasSetTracker, then for each alloca that is of 250261991Sdim /// pointer type, we keep track of what to copyValue to the inserted PHI 251261991Sdim /// nodes here. 252261991Sdim std::vector<Value *> PointerAllocaValues; 253193323Sed 254261991Sdim /// For each alloca, we keep track of the dbg.declare intrinsic that 255261991Sdim /// describes it, if any, so that we can convert it to a dbg.value 256261991Sdim /// intrinsic if the alloca gets promoted. 257261991Sdim SmallVector<DbgDeclareInst *, 8> AllocaDbgDeclares; 258193323Sed 259261991Sdim /// The set of basic blocks the renamer has already visited. 260261991Sdim /// 261261991Sdim SmallPtrSet<BasicBlock *, 16> Visited; 262193323Sed 263261991Sdim /// Contains a stable numbering of basic blocks to avoid non-determinstic 264261991Sdim /// behavior. 265261991Sdim DenseMap<BasicBlock *, unsigned> BBNumbers; 266193323Sed 267261991Sdim /// Lazily compute the number of predecessors a block has. 268261991Sdim DenseMap<const BasicBlock *, unsigned> BBNumPreds; 269218893Sdim 270261991Sdimpublic: 271261991Sdim PromoteMem2Reg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT, 272280031Sdim AliasSetTracker *AST, AssumptionCache *AC) 273261991Sdim : Allocas(Allocas.begin(), Allocas.end()), DT(DT), 274280031Sdim DIB(*DT.getRoot()->getParent()->getParent(), /*AllowUnresolved*/ false), 275280031Sdim AST(AST), AC(AC) {} 276218893Sdim 277261991Sdim void run(); 278193323Sed 279261991Sdimprivate: 280261991Sdim void RemoveFromAllocasList(unsigned &AllocaIdx) { 281261991Sdim Allocas[AllocaIdx] = Allocas.back(); 282261991Sdim Allocas.pop_back(); 283261991Sdim --AllocaIdx; 284261991Sdim } 285261991Sdim 286261991Sdim unsigned getNumPreds(const BasicBlock *BB) { 287261991Sdim unsigned &NP = BBNumPreds[BB]; 288261991Sdim if (NP == 0) 289261991Sdim NP = std::distance(pred_begin(BB), pred_end(BB)) + 1; 290261991Sdim return NP - 1; 291261991Sdim } 292261991Sdim 293261991Sdim void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info, 294280031Sdim const SmallPtrSetImpl<BasicBlock *> &DefBlocks, 295280031Sdim SmallPtrSetImpl<BasicBlock *> &LiveInBlocks); 296261991Sdim void RenamePass(BasicBlock *BB, BasicBlock *Pred, 297261991Sdim RenamePassData::ValVector &IncVals, 298261991Sdim std::vector<RenamePassData> &Worklist); 299261991Sdim bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version); 300261991Sdim}; 301261991Sdim 302261991Sdim} // end of anonymous namespace 303261991Sdim 304224145Sdimstatic void removeLifetimeIntrinsicUsers(AllocaInst *AI) { 305224145Sdim // Knowing that this alloca is promotable, we know that it's safe to kill all 306224145Sdim // instructions except for load and store. 307193323Sed 308276479Sdim for (auto UI = AI->user_begin(), UE = AI->user_end(); UI != UE;) { 309224145Sdim Instruction *I = cast<Instruction>(*UI); 310224145Sdim ++UI; 311224145Sdim if (isa<LoadInst>(I) || isa<StoreInst>(I)) 312224145Sdim continue; 313224145Sdim 314224145Sdim if (!I->getType()->isVoidTy()) { 315224145Sdim // The only users of this bitcast/GEP instruction are lifetime intrinsics. 316224145Sdim // Follow the use/def chain to erase them now instead of leaving it for 317224145Sdim // dead code elimination later. 318276479Sdim for (auto UUI = I->user_begin(), UUE = I->user_end(); UUI != UUE;) { 319276479Sdim Instruction *Inst = cast<Instruction>(*UUI); 320276479Sdim ++UUI; 321224145Sdim Inst->eraseFromParent(); 322224145Sdim } 323224145Sdim } 324224145Sdim I->eraseFromParent(); 325224145Sdim } 326224145Sdim} 327224145Sdim 328261991Sdim/// \brief Rewrite as many loads as possible given a single store. 329261991Sdim/// 330261991Sdim/// When there is only a single store, we can use the domtree to trivially 331261991Sdim/// replace all of the dominated loads with the stored value. Do so, and return 332261991Sdim/// true if this has successfully promoted the alloca entirely. If this returns 333261991Sdim/// false there were some loads which were not dominated by the single store 334261991Sdim/// and thus must be phi-ed with undef. We fall back to the standard alloca 335261991Sdim/// promotion algorithm in that case. 336261991Sdimstatic bool rewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info, 337261991Sdim LargeBlockInfo &LBI, 338261991Sdim DominatorTree &DT, 339261991Sdim AliasSetTracker *AST) { 340261991Sdim StoreInst *OnlyStore = Info.OnlyStore; 341261991Sdim bool StoringGlobalVal = !isa<Instruction>(OnlyStore->getOperand(0)); 342261991Sdim BasicBlock *StoreBB = OnlyStore->getParent(); 343261991Sdim int StoreIndex = -1; 344261991Sdim 345261991Sdim // Clear out UsingBlocks. We will reconstruct it here if needed. 346261991Sdim Info.UsingBlocks.clear(); 347261991Sdim 348276479Sdim for (auto UI = AI->user_begin(), E = AI->user_end(); UI != E;) { 349261991Sdim Instruction *UserInst = cast<Instruction>(*UI++); 350261991Sdim if (!isa<LoadInst>(UserInst)) { 351261991Sdim assert(UserInst == OnlyStore && "Should only have load/stores"); 352261991Sdim continue; 353261991Sdim } 354261991Sdim LoadInst *LI = cast<LoadInst>(UserInst); 355261991Sdim 356261991Sdim // Okay, if we have a load from the alloca, we want to replace it with the 357261991Sdim // only value stored to the alloca. We can do this if the value is 358261991Sdim // dominated by the store. If not, we use the rest of the mem2reg machinery 359261991Sdim // to insert the phi nodes as needed. 360261991Sdim if (!StoringGlobalVal) { // Non-instructions are always dominated. 361261991Sdim if (LI->getParent() == StoreBB) { 362261991Sdim // If we have a use that is in the same block as the store, compare the 363261991Sdim // indices of the two instructions to see which one came first. If the 364261991Sdim // load came before the store, we can't handle it. 365261991Sdim if (StoreIndex == -1) 366261991Sdim StoreIndex = LBI.getInstructionIndex(OnlyStore); 367261991Sdim 368261991Sdim if (unsigned(StoreIndex) > LBI.getInstructionIndex(LI)) { 369261991Sdim // Can't handle this load, bail out. 370261991Sdim Info.UsingBlocks.push_back(StoreBB); 371261991Sdim continue; 372261991Sdim } 373261991Sdim 374261991Sdim } else if (LI->getParent() != StoreBB && 375261991Sdim !DT.dominates(StoreBB, LI->getParent())) { 376261991Sdim // If the load and store are in different blocks, use BB dominance to 377261991Sdim // check their relationships. If the store doesn't dom the use, bail 378261991Sdim // out. 379261991Sdim Info.UsingBlocks.push_back(LI->getParent()); 380261991Sdim continue; 381261991Sdim } 382261991Sdim } 383261991Sdim 384261991Sdim // Otherwise, we *can* safely rewrite this load. 385261991Sdim Value *ReplVal = OnlyStore->getOperand(0); 386261991Sdim // If the replacement value is the load, this must occur in unreachable 387261991Sdim // code. 388261991Sdim if (ReplVal == LI) 389261991Sdim ReplVal = UndefValue::get(LI->getType()); 390261991Sdim LI->replaceAllUsesWith(ReplVal); 391261991Sdim if (AST && LI->getType()->isPointerTy()) 392261991Sdim AST->deleteValue(LI); 393261991Sdim LI->eraseFromParent(); 394261991Sdim LBI.deleteValue(LI); 395261991Sdim } 396261991Sdim 397261991Sdim // Finally, after the scan, check to see if the store is all that is left. 398261991Sdim if (!Info.UsingBlocks.empty()) 399261991Sdim return false; // If not, we'll have to fall back for the remainder. 400261991Sdim 401261991Sdim // Record debuginfo for the store and remove the declaration's 402261991Sdim // debuginfo. 403261991Sdim if (DbgDeclareInst *DDI = Info.DbgDeclare) { 404296417Sdim DIBuilder DIB(*AI->getModule(), /*AllowUnresolved*/ false); 405261991Sdim ConvertDebugDeclareToDebugValue(DDI, Info.OnlyStore, DIB); 406261991Sdim DDI->eraseFromParent(); 407261991Sdim LBI.deleteValue(DDI); 408261991Sdim } 409261991Sdim // Remove the (now dead) store and alloca. 410261991Sdim Info.OnlyStore->eraseFromParent(); 411261991Sdim LBI.deleteValue(Info.OnlyStore); 412261991Sdim 413261991Sdim if (AST) 414261991Sdim AST->deleteValue(AI); 415261991Sdim AI->eraseFromParent(); 416261991Sdim LBI.deleteValue(AI); 417261991Sdim return true; 418261991Sdim} 419261991Sdim 420261991Sdim/// Many allocas are only used within a single basic block. If this is the 421261991Sdim/// case, avoid traversing the CFG and inserting a lot of potentially useless 422261991Sdim/// PHI nodes by just performing a single linear pass over the basic block 423261991Sdim/// using the Alloca. 424261991Sdim/// 425261991Sdim/// If we cannot promote this alloca (because it is read before it is written), 426296417Sdim/// return false. This is necessary in cases where, due to control flow, the 427296417Sdim/// alloca is undefined only on some control flow paths. e.g. code like 428296417Sdim/// this is correct in LLVM IR: 429296417Sdim/// // A is an alloca with no stores so far 430296417Sdim/// for (...) { 431296417Sdim/// int t = *A; 432296417Sdim/// if (!first_iteration) 433296417Sdim/// use(t); 434296417Sdim/// *A = 42; 435296417Sdim/// } 436296417Sdimstatic bool promoteSingleBlockAlloca(AllocaInst *AI, const AllocaInfo &Info, 437261991Sdim LargeBlockInfo &LBI, 438261991Sdim AliasSetTracker *AST) { 439261991Sdim // The trickiest case to handle is when we have large blocks. Because of this, 440261991Sdim // this code is optimized assuming that large blocks happen. This does not 441261991Sdim // significantly pessimize the small block case. This uses LargeBlockInfo to 442261991Sdim // make it efficient to get the index of various operations in the block. 443261991Sdim 444261991Sdim // Walk the use-def list of the alloca, getting the locations of all stores. 445261991Sdim typedef SmallVector<std::pair<unsigned, StoreInst *>, 64> StoresByIndexTy; 446261991Sdim StoresByIndexTy StoresByIndex; 447261991Sdim 448276479Sdim for (User *U : AI->users()) 449276479Sdim if (StoreInst *SI = dyn_cast<StoreInst>(U)) 450261991Sdim StoresByIndex.push_back(std::make_pair(LBI.getInstructionIndex(SI), SI)); 451261991Sdim 452261991Sdim // Sort the stores by their index, making it efficient to do a lookup with a 453261991Sdim // binary search. 454261991Sdim std::sort(StoresByIndex.begin(), StoresByIndex.end(), less_first()); 455261991Sdim 456261991Sdim // Walk all of the loads from this alloca, replacing them with the nearest 457261991Sdim // store above them, if any. 458276479Sdim for (auto UI = AI->user_begin(), E = AI->user_end(); UI != E;) { 459261991Sdim LoadInst *LI = dyn_cast<LoadInst>(*UI++); 460261991Sdim if (!LI) 461261991Sdim continue; 462261991Sdim 463261991Sdim unsigned LoadIdx = LBI.getInstructionIndex(LI); 464261991Sdim 465261991Sdim // Find the nearest store that has a lower index than this load. 466261991Sdim StoresByIndexTy::iterator I = 467261991Sdim std::lower_bound(StoresByIndex.begin(), StoresByIndex.end(), 468276479Sdim std::make_pair(LoadIdx, 469276479Sdim static_cast<StoreInst *>(nullptr)), 470261991Sdim less_first()); 471296417Sdim if (I == StoresByIndex.begin()) { 472296417Sdim if (StoresByIndex.empty()) 473296417Sdim // If there are no stores, the load takes the undef value. 474296417Sdim LI->replaceAllUsesWith(UndefValue::get(LI->getType())); 475296417Sdim else 476296417Sdim // There is no store before this load, bail out (load may be affected 477296417Sdim // by the following stores - see main comment). 478296417Sdim return false; 479296417Sdim } 480261991Sdim else 481261991Sdim // Otherwise, there was a store before this load, the load takes its value. 482276479Sdim LI->replaceAllUsesWith(std::prev(I)->second->getOperand(0)); 483261991Sdim 484261991Sdim if (AST && LI->getType()->isPointerTy()) 485261991Sdim AST->deleteValue(LI); 486261991Sdim LI->eraseFromParent(); 487261991Sdim LBI.deleteValue(LI); 488261991Sdim } 489261991Sdim 490261991Sdim // Remove the (now dead) stores and alloca. 491261991Sdim while (!AI->use_empty()) { 492276479Sdim StoreInst *SI = cast<StoreInst>(AI->user_back()); 493261991Sdim // Record debuginfo for the store before removing it. 494261991Sdim if (DbgDeclareInst *DDI = Info.DbgDeclare) { 495296417Sdim DIBuilder DIB(*AI->getModule(), /*AllowUnresolved*/ false); 496261991Sdim ConvertDebugDeclareToDebugValue(DDI, SI, DIB); 497261991Sdim } 498261991Sdim SI->eraseFromParent(); 499261991Sdim LBI.deleteValue(SI); 500261991Sdim } 501261991Sdim 502261991Sdim if (AST) 503261991Sdim AST->deleteValue(AI); 504261991Sdim AI->eraseFromParent(); 505261991Sdim LBI.deleteValue(AI); 506261991Sdim 507261991Sdim // The alloca's debuginfo can be removed as well. 508261991Sdim if (DbgDeclareInst *DDI = Info.DbgDeclare) { 509261991Sdim DDI->eraseFromParent(); 510261991Sdim LBI.deleteValue(DDI); 511261991Sdim } 512261991Sdim 513261991Sdim ++NumLocalPromoted; 514296417Sdim return true; 515261991Sdim} 516261991Sdim 517193323Sedvoid PromoteMem2Reg::run() { 518218893Sdim Function &F = *DT.getRoot()->getParent(); 519193323Sed 520261991Sdim if (AST) 521261991Sdim PointerAllocaValues.resize(Allocas.size()); 522203954Srdivacky AllocaDbgDeclares.resize(Allocas.size()); 523193323Sed 524193323Sed AllocaInfo Info; 525193323Sed LargeBlockInfo LBI; 526288943Sdim IDFCalculator IDF(DT); 527193323Sed 528193323Sed for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) { 529193323Sed AllocaInst *AI = Allocas[AllocaNum]; 530193323Sed 531261991Sdim assert(isAllocaPromotable(AI) && "Cannot promote non-promotable alloca!"); 532193323Sed assert(AI->getParent()->getParent() == &F && 533193323Sed "All allocas should be in the same function, which is same as DF!"); 534193323Sed 535224145Sdim removeLifetimeIntrinsicUsers(AI); 536224145Sdim 537193323Sed if (AI->use_empty()) { 538193323Sed // If there are no uses of the alloca, just delete it now. 539261991Sdim if (AST) 540261991Sdim AST->deleteValue(AI); 541193323Sed AI->eraseFromParent(); 542193323Sed 543193323Sed // Remove the alloca from the Allocas list, since it has been processed 544193323Sed RemoveFromAllocasList(AllocaNum); 545193323Sed ++NumDeadAlloca; 546193323Sed continue; 547193323Sed } 548261991Sdim 549193323Sed // Calculate the set of read and write-locations for each alloca. This is 550193323Sed // analogous to finding the 'uses' and 'definitions' of each variable. 551193323Sed Info.AnalyzeAlloca(AI); 552193323Sed 553193323Sed // If there is only a single store to this value, replace any loads of 554193323Sed // it that are directly dominated by the definition with the value stored. 555193323Sed if (Info.DefiningBlocks.size() == 1) { 556261991Sdim if (rewriteSingleStoreAlloca(AI, Info, LBI, DT, AST)) { 557193323Sed // The alloca has been processed, move on. 558193323Sed RemoveFromAllocasList(AllocaNum); 559193323Sed ++NumSingleStore; 560193323Sed continue; 561193323Sed } 562193323Sed } 563261991Sdim 564193323Sed // If the alloca is only read and written in one basic block, just perform a 565193323Sed // linear sweep over the block to eliminate it. 566296417Sdim if (Info.OnlyUsedInOneBlock && 567296417Sdim promoteSingleBlockAlloca(AI, Info, LBI, AST)) { 568261991Sdim // The alloca has been processed, move on. 569261991Sdim RemoveFromAllocasList(AllocaNum); 570261991Sdim continue; 571193323Sed } 572218893Sdim 573193323Sed // If we haven't computed a numbering for the BB's in the function, do so 574193323Sed // now. 575193323Sed if (BBNumbers.empty()) { 576193323Sed unsigned ID = 0; 577288943Sdim for (auto &BB : F) 578288943Sdim BBNumbers[&BB] = ID++; 579193323Sed } 580193323Sed 581193323Sed // If we have an AST to keep updated, remember some pointer value that is 582193323Sed // stored into the alloca. 583193323Sed if (AST) 584193323Sed PointerAllocaValues[AllocaNum] = Info.AllocaPointerVal; 585261991Sdim 586203954Srdivacky // Remember the dbg.declare intrinsic describing this alloca, if any. 587261991Sdim if (Info.DbgDeclare) 588261991Sdim AllocaDbgDeclares[AllocaNum] = Info.DbgDeclare; 589261991Sdim 590193323Sed // Keep the reverse mapping of the 'Allocas' array for the rename pass. 591193323Sed AllocaLookup[Allocas[AllocaNum]] = AllocaNum; 592193323Sed 593193323Sed // At this point, we're committed to promoting the alloca using IDF's, and 594193323Sed // the standard SSA construction algorithm. Determine which blocks need PHI 595193323Sed // nodes and see if we can optimize out some work by avoiding insertion of 596193323Sed // dead phi nodes. 597288943Sdim 598288943Sdim 599288943Sdim // Unique the set of defining blocks for efficient lookup. 600288943Sdim SmallPtrSet<BasicBlock *, 32> DefBlocks; 601288943Sdim DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end()); 602288943Sdim 603288943Sdim // Determine which blocks the value is live in. These are blocks which lead 604288943Sdim // to uses. 605288943Sdim SmallPtrSet<BasicBlock *, 32> LiveInBlocks; 606288943Sdim ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks); 607288943Sdim 608288943Sdim // At this point, we're committed to promoting the alloca using IDF's, and 609288943Sdim // the standard SSA construction algorithm. Determine which blocks need phi 610288943Sdim // nodes and see if we can optimize out some work by avoiding insertion of 611288943Sdim // dead phi nodes. 612288943Sdim IDF.setLiveInBlocks(LiveInBlocks); 613288943Sdim IDF.setDefiningBlocks(DefBlocks); 614288943Sdim SmallVector<BasicBlock *, 32> PHIBlocks; 615288943Sdim IDF.calculate(PHIBlocks); 616288943Sdim if (PHIBlocks.size() > 1) 617288943Sdim std::sort(PHIBlocks.begin(), PHIBlocks.end(), 618288943Sdim [this](BasicBlock *A, BasicBlock *B) { 619288943Sdim return BBNumbers.lookup(A) < BBNumbers.lookup(B); 620288943Sdim }); 621288943Sdim 622288943Sdim unsigned CurrentVersion = 0; 623288943Sdim for (unsigned i = 0, e = PHIBlocks.size(); i != e; ++i) 624288943Sdim QueuePhiNode(PHIBlocks[i], AllocaNum, CurrentVersion); 625193323Sed } 626193323Sed 627193323Sed if (Allocas.empty()) 628193323Sed return; // All of the allocas must have been trivial! 629193323Sed 630193323Sed LBI.clear(); 631261991Sdim 632193323Sed // Set the incoming values for the basic block to be null values for all of 633193323Sed // the alloca's. We do this in case there is a load of a value that has not 634193323Sed // been stored yet. In this case, it will get this null value. 635193323Sed // 636193323Sed RenamePassData::ValVector Values(Allocas.size()); 637193323Sed for (unsigned i = 0, e = Allocas.size(); i != e; ++i) 638193323Sed Values[i] = UndefValue::get(Allocas[i]->getAllocatedType()); 639193323Sed 640193323Sed // Walks all basic blocks in the function performing the SSA rename algorithm 641193323Sed // and inserting the phi nodes we marked as necessary 642193323Sed // 643193323Sed std::vector<RenamePassData> RenamePassWorkList; 644296417Sdim RenamePassWorkList.emplace_back(&F.front(), nullptr, std::move(Values)); 645202375Srdivacky do { 646193323Sed RenamePassData RPD; 647193323Sed RPD.swap(RenamePassWorkList.back()); 648193323Sed RenamePassWorkList.pop_back(); 649193323Sed // RenamePass may add new worklist entries. 650193323Sed RenamePass(RPD.BB, RPD.Pred, RPD.Values, RenamePassWorkList); 651202375Srdivacky } while (!RenamePassWorkList.empty()); 652261991Sdim 653193323Sed // The renamer uses the Visited set to avoid infinite loops. Clear it now. 654193323Sed Visited.clear(); 655193323Sed 656193323Sed // Remove the allocas themselves from the function. 657193323Sed for (unsigned i = 0, e = Allocas.size(); i != e; ++i) { 658193323Sed Instruction *A = Allocas[i]; 659193323Sed 660193323Sed // If there are any uses of the alloca instructions left, they must be in 661218893Sdim // unreachable basic blocks that were not processed by walking the dominator 662218893Sdim // tree. Just delete the users now. 663193323Sed if (!A->use_empty()) 664193323Sed A->replaceAllUsesWith(UndefValue::get(A->getType())); 665261991Sdim if (AST) 666261991Sdim AST->deleteValue(A); 667193323Sed A->eraseFromParent(); 668193323Sed } 669193323Sed 670288943Sdim const DataLayout &DL = F.getParent()->getDataLayout(); 671288943Sdim 672203954Srdivacky // Remove alloca's dbg.declare instrinsics from the function. 673203954Srdivacky for (unsigned i = 0, e = AllocaDbgDeclares.size(); i != e; ++i) 674203954Srdivacky if (DbgDeclareInst *DDI = AllocaDbgDeclares[i]) 675203954Srdivacky DDI->eraseFromParent(); 676203954Srdivacky 677193323Sed // Loop over all of the PHI nodes and see if there are any that we can get 678193323Sed // rid of because they merge all of the same incoming values. This can 679193323Sed // happen due to undef values coming into the PHI nodes. This process is 680193323Sed // iterative, because eliminating one PHI node can cause others to be removed. 681193323Sed bool EliminatedAPHI = true; 682193323Sed while (EliminatedAPHI) { 683193323Sed EliminatedAPHI = false; 684261991Sdim 685243830Sdim // Iterating over NewPhiNodes is deterministic, so it is safe to try to 686243830Sdim // simplify and RAUW them as we go. If it was not, we could add uses to 687276479Sdim // the values we replace with in a non-deterministic order, thus creating 688276479Sdim // non-deterministic def->use chains. 689261991Sdim for (DenseMap<std::pair<unsigned, unsigned>, PHINode *>::iterator 690261991Sdim I = NewPhiNodes.begin(), 691261991Sdim E = NewPhiNodes.end(); 692261991Sdim I != E;) { 693193323Sed PHINode *PN = I->second; 694218893Sdim 695193323Sed // If this PHI node merges one value and/or undefs, get the value. 696288943Sdim if (Value *V = SimplifyInstruction(PN, DL, nullptr, &DT, AC)) { 697204642Srdivacky if (AST && PN->getType()->isPointerTy()) 698198090Srdivacky AST->deleteValue(PN); 699198090Srdivacky PN->replaceAllUsesWith(V); 700198090Srdivacky PN->eraseFromParent(); 701198090Srdivacky NewPhiNodes.erase(I++); 702198090Srdivacky EliminatedAPHI = true; 703198090Srdivacky continue; 704193323Sed } 705193323Sed ++I; 706193323Sed } 707193323Sed } 708261991Sdim 709193323Sed // At this point, the renamer has added entries to PHI nodes for all reachable 710193323Sed // code. Unfortunately, there may be unreachable blocks which the renamer 711193323Sed // hasn't traversed. If this is the case, the PHI nodes may not 712193323Sed // have incoming values for all predecessors. Loop over all PHI nodes we have 713193323Sed // created, inserting undef values if they are missing any incoming values. 714193323Sed // 715261991Sdim for (DenseMap<std::pair<unsigned, unsigned>, PHINode *>::iterator 716261991Sdim I = NewPhiNodes.begin(), 717261991Sdim E = NewPhiNodes.end(); 718261991Sdim I != E; ++I) { 719193323Sed // We want to do this once per basic block. As such, only process a block 720193323Sed // when we find the PHI that is the first entry in the block. 721193323Sed PHINode *SomePHI = I->second; 722193323Sed BasicBlock *BB = SomePHI->getParent(); 723193323Sed if (&BB->front() != SomePHI) 724193323Sed continue; 725193323Sed 726193323Sed // Only do work here if there the PHI nodes are missing incoming values. We 727193323Sed // know that all PHI nodes that were inserted in a block will have the same 728193323Sed // number of incoming values, so we can just check any of them. 729193323Sed if (SomePHI->getNumIncomingValues() == getNumPreds(BB)) 730193323Sed continue; 731193323Sed 732193323Sed // Get the preds for BB. 733261991Sdim SmallVector<BasicBlock *, 16> Preds(pred_begin(BB), pred_end(BB)); 734261991Sdim 735193323Sed // Ok, now we know that all of the PHI nodes are missing entries for some 736193323Sed // basic blocks. Start by sorting the incoming predecessors for efficient 737193323Sed // access. 738193323Sed std::sort(Preds.begin(), Preds.end()); 739261991Sdim 740193323Sed // Now we loop through all BB's which have entries in SomePHI and remove 741193323Sed // them from the Preds list. 742193323Sed for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) { 743193323Sed // Do a log(n) search of the Preds list for the entry we want. 744261991Sdim SmallVectorImpl<BasicBlock *>::iterator EntIt = std::lower_bound( 745261991Sdim Preds.begin(), Preds.end(), SomePHI->getIncomingBlock(i)); 746261991Sdim assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i) && 747193323Sed "PHI node has entry for a block which is not a predecessor!"); 748193323Sed 749193323Sed // Remove the entry 750193323Sed Preds.erase(EntIt); 751193323Sed } 752193323Sed 753193323Sed // At this point, the blocks left in the preds list must have dummy 754193323Sed // entries inserted into every PHI nodes for the block. Update all the phi 755193323Sed // nodes in this block that we are inserting (there could be phis before 756193323Sed // mem2reg runs). 757193323Sed unsigned NumBadPreds = SomePHI->getNumIncomingValues(); 758193323Sed BasicBlock::iterator BBI = BB->begin(); 759193323Sed while ((SomePHI = dyn_cast<PHINode>(BBI++)) && 760193323Sed SomePHI->getNumIncomingValues() == NumBadPreds) { 761193323Sed Value *UndefVal = UndefValue::get(SomePHI->getType()); 762193323Sed for (unsigned pred = 0, e = Preds.size(); pred != e; ++pred) 763193323Sed SomePHI->addIncoming(UndefVal, Preds[pred]); 764193323Sed } 765193323Sed } 766261991Sdim 767193323Sed NewPhiNodes.clear(); 768193323Sed} 769193323Sed 770261991Sdim/// \brief Determine which blocks the value is live in. 771261991Sdim/// 772261991Sdim/// These are blocks which lead to uses. Knowing this allows us to avoid 773261991Sdim/// inserting PHI nodes into blocks which don't lead to uses (thus, the 774261991Sdim/// inserted phi nodes would be dead). 775261991Sdimvoid PromoteMem2Reg::ComputeLiveInBlocks( 776261991Sdim AllocaInst *AI, AllocaInfo &Info, 777280031Sdim const SmallPtrSetImpl<BasicBlock *> &DefBlocks, 778280031Sdim SmallPtrSetImpl<BasicBlock *> &LiveInBlocks) { 779193323Sed 780193323Sed // To determine liveness, we must iterate through the predecessors of blocks 781193323Sed // where the def is live. Blocks are added to the worklist if we need to 782193323Sed // check their predecessors. Start with all the using blocks. 783261991Sdim SmallVector<BasicBlock *, 64> LiveInBlockWorklist(Info.UsingBlocks.begin(), 784261991Sdim Info.UsingBlocks.end()); 785261991Sdim 786193323Sed // If any of the using blocks is also a definition block, check to see if the 787193323Sed // definition occurs before or after the use. If it happens before the use, 788193323Sed // the value isn't really live-in. 789193323Sed for (unsigned i = 0, e = LiveInBlockWorklist.size(); i != e; ++i) { 790193323Sed BasicBlock *BB = LiveInBlockWorklist[i]; 791261991Sdim if (!DefBlocks.count(BB)) 792261991Sdim continue; 793261991Sdim 794193323Sed // Okay, this is a block that both uses and defines the value. If the first 795193323Sed // reference to the alloca is a def (store), then we know it isn't live-in. 796261991Sdim for (BasicBlock::iterator I = BB->begin();; ++I) { 797193323Sed if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 798261991Sdim if (SI->getOperand(1) != AI) 799261991Sdim continue; 800261991Sdim 801193323Sed // We found a store to the alloca before a load. The alloca is not 802193323Sed // actually live-in here. 803193323Sed LiveInBlockWorklist[i] = LiveInBlockWorklist.back(); 804193323Sed LiveInBlockWorklist.pop_back(); 805193323Sed --i, --e; 806193323Sed break; 807198090Srdivacky } 808261991Sdim 809198090Srdivacky if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 810261991Sdim if (LI->getOperand(0) != AI) 811261991Sdim continue; 812261991Sdim 813193323Sed // Okay, we found a load before a store to the alloca. It is actually 814193323Sed // live into this block. 815193323Sed break; 816193323Sed } 817193323Sed } 818193323Sed } 819261991Sdim 820193323Sed // Now that we have a set of blocks where the phi is live-in, recursively add 821193323Sed // their predecessors until we find the full region the value is live. 822193323Sed while (!LiveInBlockWorklist.empty()) { 823193323Sed BasicBlock *BB = LiveInBlockWorklist.pop_back_val(); 824261991Sdim 825193323Sed // The block really is live in here, insert it into the set. If already in 826193323Sed // the set, then it has already been processed. 827280031Sdim if (!LiveInBlocks.insert(BB).second) 828193323Sed continue; 829261991Sdim 830193323Sed // Since the value is live into BB, it is either defined in a predecessor or 831193323Sed // live into it to. Add the preds to the worklist unless they are a 832193323Sed // defining block. 833193323Sed for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { 834193323Sed BasicBlock *P = *PI; 835261991Sdim 836193323Sed // The value is not live into a predecessor if it defines the value. 837193323Sed if (DefBlocks.count(P)) 838193323Sed continue; 839261991Sdim 840193323Sed // Otherwise it is, add to the worklist. 841193323Sed LiveInBlockWorklist.push_back(P); 842193323Sed } 843193323Sed } 844193323Sed} 845193323Sed 846261991Sdim/// \brief Queue a phi-node to be added to a basic-block for a specific Alloca. 847193323Sed/// 848261991Sdim/// Returns true if there wasn't already a phi-node for that variable 849193323Sedbool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo, 850218893Sdim unsigned &Version) { 851193323Sed // Look up the basic-block in question. 852243830Sdim PHINode *&PN = NewPhiNodes[std::make_pair(BBNumbers[BB], AllocaNo)]; 853193323Sed 854193323Sed // If the BB already has a phi node added for the i'th alloca then we're done! 855261991Sdim if (PN) 856261991Sdim return false; 857193323Sed 858193323Sed // Create a PhiNode using the dereferenced type... and add the phi-node to the 859193323Sed // BasicBlock. 860221345Sdim PN = PHINode::Create(Allocas[AllocaNo]->getAllocatedType(), getNumPreds(BB), 861261991Sdim Allocas[AllocaNo]->getName() + "." + Twine(Version++), 862296417Sdim &BB->front()); 863193323Sed ++NumPHIInsert; 864193323Sed PhiToAllocaMap[PN] = AllocaNo; 865193323Sed 866204642Srdivacky if (AST && PN->getType()->isPointerTy()) 867193323Sed AST->copyValue(PointerAllocaValues[AllocaNo], PN); 868193323Sed 869193323Sed return true; 870193323Sed} 871193323Sed 872261991Sdim/// \brief Recursively traverse the CFG of the function, renaming loads and 873261991Sdim/// stores to the allocas which we are promoting. 874261991Sdim/// 875261991Sdim/// IncomingVals indicates what value each Alloca contains on exit from the 876261991Sdim/// predecessor block Pred. 877193323Sedvoid PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred, 878193323Sed RenamePassData::ValVector &IncomingVals, 879193323Sed std::vector<RenamePassData> &Worklist) { 880193323SedNextIteration: 881193323Sed // If we are inserting any phi nodes into this BB, they will already be in the 882193323Sed // block. 883193323Sed if (PHINode *APN = dyn_cast<PHINode>(BB->begin())) { 884193323Sed // If we have PHI nodes to update, compute the number of edges from Pred to 885193323Sed // BB. 886193323Sed if (PhiToAllocaMap.count(APN)) { 887193323Sed // We want to be able to distinguish between PHI nodes being inserted by 888193323Sed // this invocation of mem2reg from those phi nodes that already existed in 889193323Sed // the IR before mem2reg was run. We determine that APN is being inserted 890193323Sed // because it is missing incoming edges. All other PHI nodes being 891193323Sed // inserted by this pass of mem2reg will have the same number of incoming 892193323Sed // operands so far. Remember this count. 893193323Sed unsigned NewPHINumOperands = APN->getNumOperands(); 894261991Sdim 895261991Sdim unsigned NumEdges = std::count(succ_begin(Pred), succ_end(Pred), BB); 896193323Sed assert(NumEdges && "Must be at least one edge from Pred to BB!"); 897261991Sdim 898193323Sed // Add entries for all the phis. 899193323Sed BasicBlock::iterator PNI = BB->begin(); 900193323Sed do { 901193323Sed unsigned AllocaNo = PhiToAllocaMap[APN]; 902261991Sdim 903193323Sed // Add N incoming values to the PHI node. 904193323Sed for (unsigned i = 0; i != NumEdges; ++i) 905193323Sed APN->addIncoming(IncomingVals[AllocaNo], Pred); 906261991Sdim 907193323Sed // The currently active variable for this block is now the PHI. 908193323Sed IncomingVals[AllocaNo] = APN; 909261991Sdim 910193323Sed // Get the next phi node. 911193323Sed ++PNI; 912193323Sed APN = dyn_cast<PHINode>(PNI); 913276479Sdim if (!APN) 914261991Sdim break; 915261991Sdim 916193323Sed // Verify that it is missing entries. If not, it is not being inserted 917193323Sed // by this mem2reg invocation so we want to ignore it. 918193323Sed } while (APN->getNumOperands() == NewPHINumOperands); 919193323Sed } 920193323Sed } 921261991Sdim 922193323Sed // Don't revisit blocks. 923280031Sdim if (!Visited.insert(BB).second) 924261991Sdim return; 925193323Sed 926261991Sdim for (BasicBlock::iterator II = BB->begin(); !isa<TerminatorInst>(II);) { 927296417Sdim Instruction *I = &*II++; // get the instruction, increment iterator 928193323Sed 929193323Sed if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 930193323Sed AllocaInst *Src = dyn_cast<AllocaInst>(LI->getPointerOperand()); 931261991Sdim if (!Src) 932261991Sdim continue; 933193323Sed 934261991Sdim DenseMap<AllocaInst *, unsigned>::iterator AI = AllocaLookup.find(Src); 935261991Sdim if (AI == AllocaLookup.end()) 936261991Sdim continue; 937261991Sdim 938193323Sed Value *V = IncomingVals[AI->second]; 939193323Sed 940193323Sed // Anything using the load now uses the current value. 941193323Sed LI->replaceAllUsesWith(V); 942204642Srdivacky if (AST && LI->getType()->isPointerTy()) 943193323Sed AST->deleteValue(LI); 944193323Sed BB->getInstList().erase(LI); 945193323Sed } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 946193323Sed // Delete this instruction and mark the name as the current holder of the 947193323Sed // value 948193323Sed AllocaInst *Dest = dyn_cast<AllocaInst>(SI->getPointerOperand()); 949261991Sdim if (!Dest) 950261991Sdim continue; 951261991Sdim 952218893Sdim DenseMap<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Dest); 953193323Sed if (ai == AllocaLookup.end()) 954193323Sed continue; 955261991Sdim 956193323Sed // what value were we writing? 957193323Sed IncomingVals[ai->second] = SI->getOperand(0); 958202878Srdivacky // Record debuginfo for the store before removing it. 959261991Sdim if (DbgDeclareInst *DDI = AllocaDbgDeclares[ai->second]) 960261991Sdim ConvertDebugDeclareToDebugValue(DDI, SI, DIB); 961193323Sed BB->getInstList().erase(SI); 962193323Sed } 963193323Sed } 964193323Sed 965193323Sed // 'Recurse' to our successors. 966193323Sed succ_iterator I = succ_begin(BB), E = succ_end(BB); 967261991Sdim if (I == E) 968261991Sdim return; 969193323Sed 970193323Sed // Keep track of the successors so we don't visit the same successor twice 971261991Sdim SmallPtrSet<BasicBlock *, 8> VisitedSuccs; 972193323Sed 973193323Sed // Handle the first successor without using the worklist. 974193323Sed VisitedSuccs.insert(*I); 975193323Sed Pred = BB; 976193323Sed BB = *I; 977193323Sed ++I; 978193323Sed 979193323Sed for (; I != E; ++I) 980280031Sdim if (VisitedSuccs.insert(*I).second) 981288943Sdim Worklist.emplace_back(*I, Pred, IncomingVals); 982193323Sed 983193323Sed goto NextIteration; 984193323Sed} 985193323Sed 986261991Sdimvoid llvm::PromoteMemToReg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT, 987280031Sdim AliasSetTracker *AST, AssumptionCache *AC) { 988193323Sed // If there is nothing to do, bail out... 989261991Sdim if (Allocas.empty()) 990261991Sdim return; 991193323Sed 992280031Sdim PromoteMem2Reg(Allocas, DT, AST, AC).run(); 993193323Sed} 994