1 //===- PromoteMemoryToRegister.cpp - Convert allocas to registers ---------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file promotes memory references to be register references. It promotes
11 // alloca instructions which only have loads and stores as uses. An alloca is
12 // transformed by using dominator frontiers to place PHI nodes, then traversing
13 // the function in depth-first order to rewrite loads and stores as appropriate.
14 // This is just the standard SSA construction algorithm to construct "pruned"
17 //===----------------------------------------------------------------------===//
19 #define DEBUG_TYPE "mem2reg"
20 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
21 #include "llvm/Constants.h"
22 #include "llvm/DerivedTypes.h"
23 #include "llvm/Function.h"
24 #include "llvm/Instructions.h"
25 #include "llvm/IntrinsicInst.h"
26 #include "llvm/Metadata.h"
27 #include "llvm/Analysis/DebugInfo.h"
28 #include "llvm/Analysis/Dominators.h"
29 #include "llvm/Analysis/AliasSetTracker.h"
30 #include "llvm/ADT/DenseMap.h"
31 #include "llvm/ADT/SmallPtrSet.h"
32 #include "llvm/ADT/SmallVector.h"
33 #include "llvm/ADT/Statistic.h"
34 #include "llvm/ADT/STLExtras.h"
35 #include "llvm/Support/CFG.h"
39 STATISTIC(NumLocalPromoted, "Number of alloca's promoted within one block");
40 STATISTIC(NumSingleStore, "Number of alloca's promoted with a single store");
41 STATISTIC(NumDeadAlloca, "Number of dead alloca's removed");
42 STATISTIC(NumPHIInsert, "Number of PHI nodes inserted");
46 struct DenseMapInfo<std::pair<BasicBlock*, unsigned> > {
47 typedef std::pair<BasicBlock*, unsigned> EltTy;
48 static inline EltTy getEmptyKey() {
49 return EltTy(reinterpret_cast<BasicBlock*>(-1), ~0U);
51 static inline EltTy getTombstoneKey() {
52 return EltTy(reinterpret_cast<BasicBlock*>(-2), 0U);
54 static unsigned getHashValue(const std::pair<BasicBlock*, unsigned> &Val) {
55 return DenseMapInfo<void*>::getHashValue(Val.first) + Val.second*2;
57 static bool isEqual(const EltTy &LHS, const EltTy &RHS) {
63 /// isAllocaPromotable - Return true if this alloca is legal for promotion.
64 /// This is true if there are only loads and stores to the alloca.
66 bool llvm::isAllocaPromotable(const AllocaInst *AI) {
67 // FIXME: If the memory unit is of pointer or integer type, we can permit
68 // assignments to subsections of the memory unit.
70 // Only allow direct and non-volatile loads and stores...
71 for (Value::use_const_iterator UI = AI->use_begin(), UE = AI->use_end();
72 UI != UE; ++UI) // Loop over all of the uses of the alloca
73 if (const LoadInst *LI = dyn_cast<LoadInst>(*UI)) {
76 } else if (const StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
77 if (SI->getOperand(0) == AI)
78 return false; // Don't allow a store OF the AI, only INTO the AI.
88 /// Finds the llvm.dbg.declare intrinsic describing V, if any.
89 static DbgDeclareInst *findDbgDeclare(Value *V) {
90 if (MDNode *DebugNode = MDNode::getIfExists(V->getContext(), &V, 1))
91 for (Value::use_iterator UI = DebugNode->use_begin(),
92 E = DebugNode->use_end(); UI != E; ++UI)
93 if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(*UI))
102 // Data package used by RenamePass()
103 class RenamePassData {
105 typedef std::vector<Value *> ValVector;
107 RenamePassData() : BB(NULL), Pred(NULL), Values() {}
108 RenamePassData(BasicBlock *B, BasicBlock *P,
109 const ValVector &V) : BB(B), Pred(P), Values(V) {}
114 void swap(RenamePassData &RHS) {
115 std::swap(BB, RHS.BB);
116 std::swap(Pred, RHS.Pred);
117 Values.swap(RHS.Values);
121 /// LargeBlockInfo - This assigns and keeps a per-bb relative ordering of
122 /// load/store instructions in the block that directly load or store an alloca.
124 /// This functionality is important because it avoids scanning large basic
125 /// blocks multiple times when promoting many allocas in the same block.
126 class LargeBlockInfo {
127 /// InstNumbers - For each instruction that we track, keep the index of the
128 /// instruction. The index starts out as the number of the instruction from
129 /// the start of the block.
130 DenseMap<const Instruction *, unsigned> InstNumbers;
133 /// isInterestingInstruction - This code only looks at accesses to allocas.
134 static bool isInterestingInstruction(const Instruction *I) {
135 return (isa<LoadInst>(I) && isa<AllocaInst>(I->getOperand(0))) ||
136 (isa<StoreInst>(I) && isa<AllocaInst>(I->getOperand(1)));
139 /// getInstructionIndex - Get or calculate the index of the specified
141 unsigned getInstructionIndex(const Instruction *I) {
142 assert(isInterestingInstruction(I) &&
143 "Not a load/store to/from an alloca?");
145 // If we already have this instruction number, return it.
146 DenseMap<const Instruction *, unsigned>::iterator It = InstNumbers.find(I);
147 if (It != InstNumbers.end()) return It->second;
149 // Scan the whole block to get the instruction. This accumulates
150 // information for every interesting instruction in the block, in order to
151 // avoid gratuitus rescans.
152 const BasicBlock *BB = I->getParent();
154 for (BasicBlock::const_iterator BBI = BB->begin(), E = BB->end();
156 if (isInterestingInstruction(BBI))
157 InstNumbers[BBI] = InstNo++;
158 It = InstNumbers.find(I);
160 assert(It != InstNumbers.end() && "Didn't insert instruction?");
164 void deleteValue(const Instruction *I) {
165 InstNumbers.erase(I);
173 struct PromoteMem2Reg {
174 /// Allocas - The alloca instructions being promoted.
176 std::vector<AllocaInst*> Allocas;
178 DominanceFrontier &DF;
181 /// AST - An AliasSetTracker object to update. If null, don't update it.
183 AliasSetTracker *AST;
185 /// AllocaLookup - Reverse mapping of Allocas.
187 std::map<AllocaInst*, unsigned> AllocaLookup;
189 /// NewPhiNodes - The PhiNodes we're adding.
191 DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*> NewPhiNodes;
193 /// PhiToAllocaMap - For each PHI node, keep track of which entry in Allocas
194 /// it corresponds to.
195 DenseMap<PHINode*, unsigned> PhiToAllocaMap;
197 /// PointerAllocaValues - If we are updating an AliasSetTracker, then for
198 /// each alloca that is of pointer type, we keep track of what to copyValue
199 /// to the inserted PHI nodes here.
201 std::vector<Value*> PointerAllocaValues;
203 /// AllocaDbgDeclares - For each alloca, we keep track of the dbg.declare
204 /// intrinsic that describes it, if any, so that we can convert it to a
205 /// dbg.value intrinsic if the alloca gets promoted.
206 SmallVector<DbgDeclareInst*, 8> AllocaDbgDeclares;
208 /// Visited - The set of basic blocks the renamer has already visited.
210 SmallPtrSet<BasicBlock*, 16> Visited;
212 /// BBNumbers - Contains a stable numbering of basic blocks to avoid
213 /// non-determinstic behavior.
214 DenseMap<BasicBlock*, unsigned> BBNumbers;
216 /// BBNumPreds - Lazily compute the number of predecessors a block has.
217 DenseMap<const BasicBlock*, unsigned> BBNumPreds;
219 PromoteMem2Reg(const std::vector<AllocaInst*> &A, DominatorTree &dt,
220 DominanceFrontier &df, AliasSetTracker *ast)
221 : Allocas(A), DT(dt), DF(df), DIF(0), AST(ast) {}
228 /// properlyDominates - Return true if I1 properly dominates I2.
230 bool properlyDominates(Instruction *I1, Instruction *I2) const {
231 if (InvokeInst *II = dyn_cast<InvokeInst>(I1))
232 I1 = II->getNormalDest()->begin();
233 return DT.properlyDominates(I1->getParent(), I2->getParent());
236 /// dominates - Return true if BB1 dominates BB2 using the DominatorTree.
238 bool dominates(BasicBlock *BB1, BasicBlock *BB2) const {
239 return DT.dominates(BB1, BB2);
243 void RemoveFromAllocasList(unsigned &AllocaIdx) {
244 Allocas[AllocaIdx] = Allocas.back();
249 unsigned getNumPreds(const BasicBlock *BB) {
250 unsigned &NP = BBNumPreds[BB];
252 NP = std::distance(pred_begin(BB), pred_end(BB))+1;
256 void DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum,
258 void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info,
259 const SmallPtrSet<BasicBlock*, 32> &DefBlocks,
260 SmallPtrSet<BasicBlock*, 32> &LiveInBlocks);
262 void RewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info,
263 LargeBlockInfo &LBI);
264 void PromoteSingleBlockAlloca(AllocaInst *AI, AllocaInfo &Info,
265 LargeBlockInfo &LBI);
266 void ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI, StoreInst *SI,
270 void RenamePass(BasicBlock *BB, BasicBlock *Pred,
271 RenamePassData::ValVector &IncVals,
272 std::vector<RenamePassData> &Worklist);
273 bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version,
274 SmallPtrSet<PHINode*, 16> &InsertedPHINodes);
278 std::vector<BasicBlock*> DefiningBlocks;
279 std::vector<BasicBlock*> UsingBlocks;
281 StoreInst *OnlyStore;
282 BasicBlock *OnlyBlock;
283 bool OnlyUsedInOneBlock;
285 Value *AllocaPointerVal;
286 DbgDeclareInst *DbgDeclare;
289 DefiningBlocks.clear();
293 OnlyUsedInOneBlock = true;
294 AllocaPointerVal = 0;
298 /// AnalyzeAlloca - Scan the uses of the specified alloca, filling in our
300 void AnalyzeAlloca(AllocaInst *AI) {
303 // As we scan the uses of the alloca instruction, keep track of stores,
304 // and decide whether all of the loads and stores to the alloca are within
305 // the same basic block.
306 for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end();
308 Instruction *User = cast<Instruction>(*UI++);
310 if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
311 // Remember the basic blocks which define new values for the alloca
312 DefiningBlocks.push_back(SI->getParent());
313 AllocaPointerVal = SI->getOperand(0);
316 LoadInst *LI = cast<LoadInst>(User);
317 // Otherwise it must be a load instruction, keep track of variable
319 UsingBlocks.push_back(LI->getParent());
320 AllocaPointerVal = LI;
323 if (OnlyUsedInOneBlock) {
325 OnlyBlock = User->getParent();
326 else if (OnlyBlock != User->getParent())
327 OnlyUsedInOneBlock = false;
331 DbgDeclare = findDbgDeclare(AI);
334 } // end of anonymous namespace
337 void PromoteMem2Reg::run() {
338 Function &F = *DF.getRoot()->getParent();
340 if (AST) PointerAllocaValues.resize(Allocas.size());
341 AllocaDbgDeclares.resize(Allocas.size());
346 for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
347 AllocaInst *AI = Allocas[AllocaNum];
349 assert(isAllocaPromotable(AI) &&
350 "Cannot promote non-promotable alloca!");
351 assert(AI->getParent()->getParent() == &F &&
352 "All allocas should be in the same function, which is same as DF!");
354 if (AI->use_empty()) {
355 // If there are no uses of the alloca, just delete it now.
356 if (AST) AST->deleteValue(AI);
357 AI->eraseFromParent();
359 // Remove the alloca from the Allocas list, since it has been processed
360 RemoveFromAllocasList(AllocaNum);
365 // Calculate the set of read and write-locations for each alloca. This is
366 // analogous to finding the 'uses' and 'definitions' of each variable.
367 Info.AnalyzeAlloca(AI);
369 // If there is only a single store to this value, replace any loads of
370 // it that are directly dominated by the definition with the value stored.
371 if (Info.DefiningBlocks.size() == 1) {
372 RewriteSingleStoreAlloca(AI, Info, LBI);
374 // Finally, after the scan, check to see if the store is all that is left.
375 if (Info.UsingBlocks.empty()) {
376 // Record debuginfo for the store before removing it.
377 ConvertDebugDeclareToDebugValue(Info.DbgDeclare, Info.OnlyStore, 0);
378 // Remove the (now dead) store and alloca.
379 Info.OnlyStore->eraseFromParent();
380 LBI.deleteValue(Info.OnlyStore);
382 if (AST) AST->deleteValue(AI);
383 AI->eraseFromParent();
386 // The alloca has been processed, move on.
387 RemoveFromAllocasList(AllocaNum);
394 // If the alloca is only read and written in one basic block, just perform a
395 // linear sweep over the block to eliminate it.
396 if (Info.OnlyUsedInOneBlock) {
397 PromoteSingleBlockAlloca(AI, Info, LBI);
399 // Finally, after the scan, check to see if the stores are all that is
401 if (Info.UsingBlocks.empty()) {
403 // Remove the (now dead) stores and alloca.
404 while (!AI->use_empty()) {
405 StoreInst *SI = cast<StoreInst>(AI->use_back());
406 // Record debuginfo for the store before removing it.
407 ConvertDebugDeclareToDebugValue(Info.DbgDeclare, SI, 0);
408 SI->eraseFromParent();
412 if (AST) AST->deleteValue(AI);
413 AI->eraseFromParent();
416 // The alloca has been processed, move on.
417 RemoveFromAllocasList(AllocaNum);
424 // If we haven't computed a numbering for the BB's in the function, do so
426 if (BBNumbers.empty()) {
428 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
432 // If we have an AST to keep updated, remember some pointer value that is
433 // stored into the alloca.
435 PointerAllocaValues[AllocaNum] = Info.AllocaPointerVal;
437 // Remember the dbg.declare intrinsic describing this alloca, if any.
438 if (Info.DbgDeclare) AllocaDbgDeclares[AllocaNum] = Info.DbgDeclare;
440 // Keep the reverse mapping of the 'Allocas' array for the rename pass.
441 AllocaLookup[Allocas[AllocaNum]] = AllocaNum;
443 // At this point, we're committed to promoting the alloca using IDF's, and
444 // the standard SSA construction algorithm. Determine which blocks need PHI
445 // nodes and see if we can optimize out some work by avoiding insertion of
447 DetermineInsertionPoint(AI, AllocaNum, Info);
451 return; // All of the allocas must have been trivial!
456 // Set the incoming values for the basic block to be null values for all of
457 // the alloca's. We do this in case there is a load of a value that has not
458 // been stored yet. In this case, it will get this null value.
460 RenamePassData::ValVector Values(Allocas.size());
461 for (unsigned i = 0, e = Allocas.size(); i != e; ++i)
462 Values[i] = UndefValue::get(Allocas[i]->getAllocatedType());
464 // Walks all basic blocks in the function performing the SSA rename algorithm
465 // and inserting the phi nodes we marked as necessary
467 std::vector<RenamePassData> RenamePassWorkList;
468 RenamePassWorkList.push_back(RenamePassData(F.begin(), 0, Values));
471 RPD.swap(RenamePassWorkList.back());
472 RenamePassWorkList.pop_back();
473 // RenamePass may add new worklist entries.
474 RenamePass(RPD.BB, RPD.Pred, RPD.Values, RenamePassWorkList);
475 } while (!RenamePassWorkList.empty());
477 // The renamer uses the Visited set to avoid infinite loops. Clear it now.
480 // Remove the allocas themselves from the function.
481 for (unsigned i = 0, e = Allocas.size(); i != e; ++i) {
482 Instruction *A = Allocas[i];
484 // If there are any uses of the alloca instructions left, they must be in
485 // sections of dead code that were not processed on the dominance frontier.
486 // Just delete the users now.
489 A->replaceAllUsesWith(UndefValue::get(A->getType()));
490 if (AST) AST->deleteValue(A);
491 A->eraseFromParent();
495 // Loop over all of the PHI nodes and see if there are any that we can get
496 // rid of because they merge all of the same incoming values. This can
497 // happen due to undef values coming into the PHI nodes. This process is
498 // iterative, because eliminating one PHI node can cause others to be removed.
499 bool EliminatedAPHI = true;
500 while (EliminatedAPHI) {
501 EliminatedAPHI = false;
503 for (DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*>::iterator I =
504 NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E;) {
505 PHINode *PN = I->second;
507 // If this PHI node merges one value and/or undefs, get the value.
508 if (Value *V = PN->hasConstantValue(&DT)) {
509 if (AST && isa<PointerType>(PN->getType()))
510 AST->deleteValue(PN);
511 PN->replaceAllUsesWith(V);
512 PN->eraseFromParent();
513 NewPhiNodes.erase(I++);
514 EliminatedAPHI = true;
521 // At this point, the renamer has added entries to PHI nodes for all reachable
522 // code. Unfortunately, there may be unreachable blocks which the renamer
523 // hasn't traversed. If this is the case, the PHI nodes may not
524 // have incoming values for all predecessors. Loop over all PHI nodes we have
525 // created, inserting undef values if they are missing any incoming values.
527 for (DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*>::iterator I =
528 NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) {
529 // We want to do this once per basic block. As such, only process a block
530 // when we find the PHI that is the first entry in the block.
531 PHINode *SomePHI = I->second;
532 BasicBlock *BB = SomePHI->getParent();
533 if (&BB->front() != SomePHI)
536 // Only do work here if there the PHI nodes are missing incoming values. We
537 // know that all PHI nodes that were inserted in a block will have the same
538 // number of incoming values, so we can just check any of them.
539 if (SomePHI->getNumIncomingValues() == getNumPreds(BB))
542 // Get the preds for BB.
543 SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB));
545 // Ok, now we know that all of the PHI nodes are missing entries for some
546 // basic blocks. Start by sorting the incoming predecessors for efficient
548 std::sort(Preds.begin(), Preds.end());
550 // Now we loop through all BB's which have entries in SomePHI and remove
551 // them from the Preds list.
552 for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) {
553 // Do a log(n) search of the Preds list for the entry we want.
554 SmallVector<BasicBlock*, 16>::iterator EntIt =
555 std::lower_bound(Preds.begin(), Preds.end(),
556 SomePHI->getIncomingBlock(i));
557 assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i)&&
558 "PHI node has entry for a block which is not a predecessor!");
564 // At this point, the blocks left in the preds list must have dummy
565 // entries inserted into every PHI nodes for the block. Update all the phi
566 // nodes in this block that we are inserting (there could be phis before
568 unsigned NumBadPreds = SomePHI->getNumIncomingValues();
569 BasicBlock::iterator BBI = BB->begin();
570 while ((SomePHI = dyn_cast<PHINode>(BBI++)) &&
571 SomePHI->getNumIncomingValues() == NumBadPreds) {
572 Value *UndefVal = UndefValue::get(SomePHI->getType());
573 for (unsigned pred = 0, e = Preds.size(); pred != e; ++pred)
574 SomePHI->addIncoming(UndefVal, Preds[pred]);
582 /// ComputeLiveInBlocks - Determine which blocks the value is live in. These
583 /// are blocks which lead to uses. Knowing this allows us to avoid inserting
584 /// PHI nodes into blocks which don't lead to uses (thus, the inserted phi nodes
586 void PromoteMem2Reg::
587 ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info,
588 const SmallPtrSet<BasicBlock*, 32> &DefBlocks,
589 SmallPtrSet<BasicBlock*, 32> &LiveInBlocks) {
591 // To determine liveness, we must iterate through the predecessors of blocks
592 // where the def is live. Blocks are added to the worklist if we need to
593 // check their predecessors. Start with all the using blocks.
594 SmallVector<BasicBlock*, 64> LiveInBlockWorklist;
595 LiveInBlockWorklist.insert(LiveInBlockWorklist.end(),
596 Info.UsingBlocks.begin(), Info.UsingBlocks.end());
598 // If any of the using blocks is also a definition block, check to see if the
599 // definition occurs before or after the use. If it happens before the use,
600 // the value isn't really live-in.
601 for (unsigned i = 0, e = LiveInBlockWorklist.size(); i != e; ++i) {
602 BasicBlock *BB = LiveInBlockWorklist[i];
603 if (!DefBlocks.count(BB)) continue;
605 // Okay, this is a block that both uses and defines the value. If the first
606 // reference to the alloca is a def (store), then we know it isn't live-in.
607 for (BasicBlock::iterator I = BB->begin(); ; ++I) {
608 if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
609 if (SI->getOperand(1) != AI) continue;
611 // We found a store to the alloca before a load. The alloca is not
612 // actually live-in here.
613 LiveInBlockWorklist[i] = LiveInBlockWorklist.back();
614 LiveInBlockWorklist.pop_back();
619 if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
620 if (LI->getOperand(0) != AI) continue;
622 // Okay, we found a load before a store to the alloca. It is actually
623 // live into this block.
629 // Now that we have a set of blocks where the phi is live-in, recursively add
630 // their predecessors until we find the full region the value is live.
631 while (!LiveInBlockWorklist.empty()) {
632 BasicBlock *BB = LiveInBlockWorklist.pop_back_val();
634 // The block really is live in here, insert it into the set. If already in
635 // the set, then it has already been processed.
636 if (!LiveInBlocks.insert(BB))
639 // Since the value is live into BB, it is either defined in a predecessor or
640 // live into it to. Add the preds to the worklist unless they are a
642 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
645 // The value is not live into a predecessor if it defines the value.
646 if (DefBlocks.count(P))
649 // Otherwise it is, add to the worklist.
650 LiveInBlockWorklist.push_back(P);
655 /// DetermineInsertionPoint - At this point, we're committed to promoting the
656 /// alloca using IDF's, and the standard SSA construction algorithm. Determine
657 /// which blocks need phi nodes and see if we can optimize out some work by
658 /// avoiding insertion of dead phi nodes.
659 void PromoteMem2Reg::DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum,
662 // Unique the set of defining blocks for efficient lookup.
663 SmallPtrSet<BasicBlock*, 32> DefBlocks;
664 DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end());
666 // Determine which blocks the value is live in. These are blocks which lead
668 SmallPtrSet<BasicBlock*, 32> LiveInBlocks;
669 ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks);
671 // Compute the locations where PhiNodes need to be inserted. Look at the
672 // dominance frontier of EACH basic-block we have a write in.
673 unsigned CurrentVersion = 0;
674 SmallPtrSet<PHINode*, 16> InsertedPHINodes;
675 std::vector<std::pair<unsigned, BasicBlock*> > DFBlocks;
676 while (!Info.DefiningBlocks.empty()) {
677 BasicBlock *BB = Info.DefiningBlocks.back();
678 Info.DefiningBlocks.pop_back();
680 // Look up the DF for this write, add it to defining blocks.
681 DominanceFrontier::const_iterator it = DF.find(BB);
682 if (it == DF.end()) continue;
684 const DominanceFrontier::DomSetType &S = it->second;
686 // In theory we don't need the indirection through the DFBlocks vector.
687 // In practice, the order of calling QueuePhiNode would depend on the
688 // (unspecified) ordering of basic blocks in the dominance frontier,
689 // which would give PHI nodes non-determinstic subscripts. Fix this by
690 // processing blocks in order of the occurance in the function.
691 for (DominanceFrontier::DomSetType::const_iterator P = S.begin(),
692 PE = S.end(); P != PE; ++P) {
693 // If the frontier block is not in the live-in set for the alloca, don't
694 // bother processing it.
695 if (!LiveInBlocks.count(*P))
698 DFBlocks.push_back(std::make_pair(BBNumbers[*P], *P));
701 // Sort by which the block ordering in the function.
702 if (DFBlocks.size() > 1)
703 std::sort(DFBlocks.begin(), DFBlocks.end());
705 for (unsigned i = 0, e = DFBlocks.size(); i != e; ++i) {
706 BasicBlock *BB = DFBlocks[i].second;
707 if (QueuePhiNode(BB, AllocaNum, CurrentVersion, InsertedPHINodes))
708 Info.DefiningBlocks.push_back(BB);
714 /// RewriteSingleStoreAlloca - If there is only a single store to this value,
715 /// replace any loads of it that are directly dominated by the definition with
716 /// the value stored.
717 void PromoteMem2Reg::RewriteSingleStoreAlloca(AllocaInst *AI,
719 LargeBlockInfo &LBI) {
720 StoreInst *OnlyStore = Info.OnlyStore;
721 bool StoringGlobalVal = !isa<Instruction>(OnlyStore->getOperand(0));
722 BasicBlock *StoreBB = OnlyStore->getParent();
725 // Clear out UsingBlocks. We will reconstruct it here if needed.
726 Info.UsingBlocks.clear();
728 for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E; ) {
729 Instruction *UserInst = cast<Instruction>(*UI++);
730 if (!isa<LoadInst>(UserInst)) {
731 assert(UserInst == OnlyStore && "Should only have load/stores");
734 LoadInst *LI = cast<LoadInst>(UserInst);
736 // Okay, if we have a load from the alloca, we want to replace it with the
737 // only value stored to the alloca. We can do this if the value is
738 // dominated by the store. If not, we use the rest of the mem2reg machinery
739 // to insert the phi nodes as needed.
740 if (!StoringGlobalVal) { // Non-instructions are always dominated.
741 if (LI->getParent() == StoreBB) {
742 // If we have a use that is in the same block as the store, compare the
743 // indices of the two instructions to see which one came first. If the
744 // load came before the store, we can't handle it.
745 if (StoreIndex == -1)
746 StoreIndex = LBI.getInstructionIndex(OnlyStore);
748 if (unsigned(StoreIndex) > LBI.getInstructionIndex(LI)) {
749 // Can't handle this load, bail out.
750 Info.UsingBlocks.push_back(StoreBB);
754 } else if (LI->getParent() != StoreBB &&
755 !dominates(StoreBB, LI->getParent())) {
756 // If the load and store are in different blocks, use BB dominance to
757 // check their relationships. If the store doesn't dom the use, bail
759 Info.UsingBlocks.push_back(LI->getParent());
764 // Otherwise, we *can* safely rewrite this load.
765 Value *ReplVal = OnlyStore->getOperand(0);
766 // If the replacement value is the load, this must occur in unreachable
769 ReplVal = UndefValue::get(LI->getType());
770 LI->replaceAllUsesWith(ReplVal);
771 if (AST && isa<PointerType>(LI->getType()))
772 AST->deleteValue(LI);
773 LI->eraseFromParent();
780 /// StoreIndexSearchPredicate - This is a helper predicate used to search by the
781 /// first element of a pair.
782 struct StoreIndexSearchPredicate {
783 bool operator()(const std::pair<unsigned, StoreInst*> &LHS,
784 const std::pair<unsigned, StoreInst*> &RHS) {
785 return LHS.first < RHS.first;
791 /// PromoteSingleBlockAlloca - Many allocas are only used within a single basic
792 /// block. If this is the case, avoid traversing the CFG and inserting a lot of
793 /// potentially useless PHI nodes by just performing a single linear pass over
794 /// the basic block using the Alloca.
796 /// If we cannot promote this alloca (because it is read before it is written),
797 /// return true. This is necessary in cases where, due to control flow, the
798 /// alloca is potentially undefined on some control flow paths. e.g. code like
799 /// this is potentially correct:
801 /// for (...) { if (c) { A = undef; undef = B; } }
803 /// ... so long as A is not used before undef is set.
805 void PromoteMem2Reg::PromoteSingleBlockAlloca(AllocaInst *AI, AllocaInfo &Info,
806 LargeBlockInfo &LBI) {
807 // The trickiest case to handle is when we have large blocks. Because of this,
808 // this code is optimized assuming that large blocks happen. This does not
809 // significantly pessimize the small block case. This uses LargeBlockInfo to
810 // make it efficient to get the index of various operations in the block.
812 // Clear out UsingBlocks. We will reconstruct it here if needed.
813 Info.UsingBlocks.clear();
815 // Walk the use-def list of the alloca, getting the locations of all stores.
816 typedef SmallVector<std::pair<unsigned, StoreInst*>, 64> StoresByIndexTy;
817 StoresByIndexTy StoresByIndex;
819 for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end();
821 if (StoreInst *SI = dyn_cast<StoreInst>(*UI))
822 StoresByIndex.push_back(std::make_pair(LBI.getInstructionIndex(SI), SI));
824 // If there are no stores to the alloca, just replace any loads with undef.
825 if (StoresByIndex.empty()) {
826 for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;)
827 if (LoadInst *LI = dyn_cast<LoadInst>(*UI++)) {
828 LI->replaceAllUsesWith(UndefValue::get(LI->getType()));
829 if (AST && isa<PointerType>(LI->getType()))
830 AST->deleteValue(LI);
832 LI->eraseFromParent();
837 // Sort the stores by their index, making it efficient to do a lookup with a
839 std::sort(StoresByIndex.begin(), StoresByIndex.end());
841 // Walk all of the loads from this alloca, replacing them with the nearest
842 // store above them, if any.
843 for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;) {
844 LoadInst *LI = dyn_cast<LoadInst>(*UI++);
847 unsigned LoadIdx = LBI.getInstructionIndex(LI);
849 // Find the nearest store that has a lower than this load.
850 StoresByIndexTy::iterator I =
851 std::lower_bound(StoresByIndex.begin(), StoresByIndex.end(),
852 std::pair<unsigned, StoreInst*>(LoadIdx, 0),
853 StoreIndexSearchPredicate());
855 // If there is no store before this load, then we can't promote this load.
856 if (I == StoresByIndex.begin()) {
857 // Can't handle this load, bail out.
858 Info.UsingBlocks.push_back(LI->getParent());
862 // Otherwise, there was a store before this load, the load takes its value.
864 LI->replaceAllUsesWith(I->second->getOperand(0));
865 if (AST && isa<PointerType>(LI->getType()))
866 AST->deleteValue(LI);
867 LI->eraseFromParent();
872 // Inserts a llvm.dbg.value instrinsic before the stores to an alloca'd value
873 // that has an associated llvm.dbg.decl intrinsic.
874 void PromoteMem2Reg::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
880 DIVariable DIVar(DDI->getVariable());
881 if (!DIVar.getNode())
885 DIF = new DIFactory(*SI->getParent()->getParent()->getParent());
886 Instruction *DbgVal = DIF->InsertDbgValueIntrinsic(SI->getOperand(0), Offset,
888 if (MDNode *SIMD = SI->getMetadata("dbg"))
889 DbgVal->setMetadata("dbg", SIMD);
892 // QueuePhiNode - queues a phi-node to be added to a basic-block for a specific
893 // Alloca returns true if there wasn't already a phi-node for that variable
895 bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo,
897 SmallPtrSet<PHINode*, 16> &InsertedPHINodes) {
898 // Look up the basic-block in question.
899 PHINode *&PN = NewPhiNodes[std::make_pair(BB, AllocaNo)];
901 // If the BB already has a phi node added for the i'th alloca then we're done!
902 if (PN) return false;
904 // Create a PhiNode using the dereferenced type... and add the phi-node to the
906 PN = PHINode::Create(Allocas[AllocaNo]->getAllocatedType(),
907 Allocas[AllocaNo]->getName() + "." + Twine(Version++),
910 PhiToAllocaMap[PN] = AllocaNo;
911 PN->reserveOperandSpace(getNumPreds(BB));
913 InsertedPHINodes.insert(PN);
915 if (AST && isa<PointerType>(PN->getType()))
916 AST->copyValue(PointerAllocaValues[AllocaNo], PN);
921 // RenamePass - Recursively traverse the CFG of the function, renaming loads and
922 // stores to the allocas which we are promoting. IncomingVals indicates what
923 // value each Alloca contains on exit from the predecessor block Pred.
925 void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred,
926 RenamePassData::ValVector &IncomingVals,
927 std::vector<RenamePassData> &Worklist) {
929 // If we are inserting any phi nodes into this BB, they will already be in the
931 if (PHINode *APN = dyn_cast<PHINode>(BB->begin())) {
932 // If we have PHI nodes to update, compute the number of edges from Pred to
934 if (PhiToAllocaMap.count(APN)) {
935 // We want to be able to distinguish between PHI nodes being inserted by
936 // this invocation of mem2reg from those phi nodes that already existed in
937 // the IR before mem2reg was run. We determine that APN is being inserted
938 // because it is missing incoming edges. All other PHI nodes being
939 // inserted by this pass of mem2reg will have the same number of incoming
940 // operands so far. Remember this count.
941 unsigned NewPHINumOperands = APN->getNumOperands();
943 unsigned NumEdges = 0;
944 for (succ_iterator I = succ_begin(Pred), E = succ_end(Pred); I != E; ++I)
947 assert(NumEdges && "Must be at least one edge from Pred to BB!");
949 // Add entries for all the phis.
950 BasicBlock::iterator PNI = BB->begin();
952 unsigned AllocaNo = PhiToAllocaMap[APN];
954 // Add N incoming values to the PHI node.
955 for (unsigned i = 0; i != NumEdges; ++i)
956 APN->addIncoming(IncomingVals[AllocaNo], Pred);
958 // The currently active variable for this block is now the PHI.
959 IncomingVals[AllocaNo] = APN;
961 // Get the next phi node.
963 APN = dyn_cast<PHINode>(PNI);
966 // Verify that it is missing entries. If not, it is not being inserted
967 // by this mem2reg invocation so we want to ignore it.
968 } while (APN->getNumOperands() == NewPHINumOperands);
972 // Don't revisit blocks.
973 if (!Visited.insert(BB)) return;
975 for (BasicBlock::iterator II = BB->begin(); !isa<TerminatorInst>(II); ) {
976 Instruction *I = II++; // get the instruction, increment iterator
978 if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
979 AllocaInst *Src = dyn_cast<AllocaInst>(LI->getPointerOperand());
982 std::map<AllocaInst*, unsigned>::iterator AI = AllocaLookup.find(Src);
983 if (AI == AllocaLookup.end()) continue;
985 Value *V = IncomingVals[AI->second];
987 // Anything using the load now uses the current value.
988 LI->replaceAllUsesWith(V);
989 if (AST && isa<PointerType>(LI->getType()))
990 AST->deleteValue(LI);
991 BB->getInstList().erase(LI);
992 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
993 // Delete this instruction and mark the name as the current holder of the
995 AllocaInst *Dest = dyn_cast<AllocaInst>(SI->getPointerOperand());
998 std::map<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Dest);
999 if (ai == AllocaLookup.end())
1002 // what value were we writing?
1003 IncomingVals[ai->second] = SI->getOperand(0);
1004 // Record debuginfo for the store before removing it.
1005 ConvertDebugDeclareToDebugValue(AllocaDbgDeclares[ai->second], SI, 0);
1006 BB->getInstList().erase(SI);
1010 // 'Recurse' to our successors.
1011 succ_iterator I = succ_begin(BB), E = succ_end(BB);
1014 // Keep track of the successors so we don't visit the same successor twice
1015 SmallPtrSet<BasicBlock*, 8> VisitedSuccs;
1017 // Handle the first successor without using the worklist.
1018 VisitedSuccs.insert(*I);
1024 if (VisitedSuccs.insert(*I))
1025 Worklist.push_back(RenamePassData(*I, Pred, IncomingVals));
1030 /// PromoteMemToReg - Promote the specified list of alloca instructions into
1031 /// scalar registers, inserting PHI nodes as appropriate. This function makes
1032 /// use of DominanceFrontier information. This function does not modify the CFG
1033 /// of the function at all. All allocas must be from the same function.
1035 /// If AST is specified, the specified tracker is updated to reflect changes
1038 void llvm::PromoteMemToReg(const std::vector<AllocaInst*> &Allocas,
1039 DominatorTree &DT, DominanceFrontier &DF,
1040 AliasSetTracker *AST) {
1041 // If there is nothing to do, bail out...
1042 if (Allocas.empty()) return;
1044 PromoteMem2Reg(Allocas, DT, DF, AST).run();