contrib/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp

   1 //===- PromoteMemoryToRegister.cpp - Convert allocas to registers ---------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  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 iterated dominator frontiers to place PHI nodes, then
  13 // traversing the function in depth-first order to rewrite loads and stores as
  14 // appropriate.
  15 //
  16 // The algorithm used here is based on:
  17 //
  18 //   Sreedhar and Gao. A linear time algorithm for placing phi-nodes.
  19 //   In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of
  20 //   Programming Languages
  21 //   POPL '95. ACM, New York, NY, 62-73.
  22 //
  23 // It has been modified to not explicitly use the DJ graph data structure and to
  24 // directly compute pruned SSA using per-variable liveness information.
  25 //
  26 //===----------------------------------------------------------------------===//
  27
  28 #define DEBUG_TYPE "mem2reg"
  29 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
  30 #include "llvm/Constants.h"
  31 #include "llvm/DerivedTypes.h"
  32 #include "llvm/Function.h"
  33 #include "llvm/Instructions.h"
  34 #include "llvm/IntrinsicInst.h"
  35 #include "llvm/Metadata.h"
  36 #include "llvm/Analysis/AliasSetTracker.h"
  37 #include "llvm/Analysis/DebugInfo.h"
  38 #include "llvm/Analysis/DIBuilder.h"
  39 #include "llvm/Analysis/Dominators.h"
  40 #include "llvm/Analysis/InstructionSimplify.h"
  41 #include "llvm/Analysis/ValueTracking.h"
  42 #include "llvm/Transforms/Utils/Local.h"
  43 #include "llvm/ADT/DenseMap.h"
  44 #include "llvm/ADT/SmallPtrSet.h"
  45 #include "llvm/ADT/SmallVector.h"
  46 #include "llvm/ADT/Statistic.h"
  47 #include "llvm/ADT/STLExtras.h"
  48 #include "llvm/Support/CFG.h"
  49 #include <algorithm>
  50 #include <queue>
  51 using namespace llvm;
  52
  53 STATISTIC(NumLocalPromoted, "Number of alloca's promoted within one block");
  54 STATISTIC(NumSingleStore,   "Number of alloca's promoted with a single store");
  55 STATISTIC(NumDeadAlloca,    "Number of dead alloca's removed");
  56 STATISTIC(NumPHIInsert,     "Number of PHI nodes inserted");
  57
  58 namespace llvm {
  59 template<>
  60 struct DenseMapInfo<std::pair<BasicBlock*, unsigned> > {
  61   typedef std::pair<BasicBlock*, unsigned> EltTy;
  62   static inline EltTy getEmptyKey() {
  63     return EltTy(reinterpret_cast<BasicBlock*>(-1), ~0U);
  64   }
  65   static inline EltTy getTombstoneKey() {
  66     return EltTy(reinterpret_cast<BasicBlock*>(-2), 0U);
  67   }
  68   static unsigned getHashValue(const std::pair<BasicBlock*, unsigned> &Val) {
  69     return DenseMapInfo<void*>::getHashValue(Val.first) + Val.second*2;
  70   }
  71   static bool isEqual(const EltTy &LHS, const EltTy &RHS) {
  72     return LHS == RHS;
  73   }
  74 };
  75 }
  76
  77 /// isAllocaPromotable - Return true if this alloca is legal for promotion.
  78 /// This is true if there are only loads and stores to the alloca.
  79 ///
  80 bool llvm::isAllocaPromotable(const AllocaInst *AI) {
  81   // FIXME: If the memory unit is of pointer or integer type, we can permit
  82   // assignments to subsections of the memory unit.
  83
  84   // Only allow direct and non-volatile loads and stores...
  85   for (Value::const_use_iterator UI = AI->use_begin(), UE = AI->use_end();
  86        UI != UE; ++UI) {   // Loop over all of the uses of the alloca
  87     const User *U = *UI;
  88     if (const LoadInst *LI = dyn_cast<LoadInst>(U)) {
  89       if (LI->isVolatile())
  90         return false;
  91     } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) {
  92       if (SI->getOperand(0) == AI)
  93         return false;   // Don't allow a store OF the AI, only INTO the AI.
  94       if (SI->isVolatile())
  95         return false;
  96     } else if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(U)) {
  97       if (II->getIntrinsicID() != Intrinsic::lifetime_start &&
  98           II->getIntrinsicID() != Intrinsic::lifetime_end)
  99         return false;
 100     } else if (const BitCastInst *BCI = dyn_cast<BitCastInst>(U)) {
 101       if (BCI->getType() != Type::getInt8PtrTy(U->getContext()))
 102         return false;
 103       if (!onlyUsedByLifetimeMarkers(BCI))
 104         return false;
 105     } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) {
 106       if (GEPI->getType() != Type::getInt8PtrTy(U->getContext()))
 107         return false;
 108       if (!GEPI->hasAllZeroIndices())
 109         return false;
 110       if (!onlyUsedByLifetimeMarkers(GEPI))
 111         return false;
 112     } else {
 113       return false;
 114     }
 115   }
 116
 117   return true;
 118 }
 119
 120 namespace {
 121   struct AllocaInfo;
 122
 123   // Data package used by RenamePass()
 124   class RenamePassData {
 125   public:
 126     typedef std::vector<Value *> ValVector;
 127
 128     RenamePassData() : BB(NULL), Pred(NULL), Values() {}
 129     RenamePassData(BasicBlock *B, BasicBlock *P,
 130                    const ValVector &V) : BB(B), Pred(P), Values(V) {}
 131     BasicBlock *BB;
 132     BasicBlock *Pred;
 133     ValVector Values;
 134
 135     void swap(RenamePassData &RHS) {
 136       std::swap(BB, RHS.BB);
 137       std::swap(Pred, RHS.Pred);
 138       Values.swap(RHS.Values);
 139     }
 140   };
 141
 142   /// LargeBlockInfo - This assigns and keeps a per-bb relative ordering of
 143   /// load/store instructions in the block that directly load or store an alloca.
 144   ///
 145   /// This functionality is important because it avoids scanning large basic
 146   /// blocks multiple times when promoting many allocas in the same block.
 147   class LargeBlockInfo {
 148     /// InstNumbers - For each instruction that we track, keep the index of the
 149     /// instruction.  The index starts out as the number of the instruction from
 150     /// the start of the block.
 151     DenseMap<const Instruction *, unsigned> InstNumbers;
 152   public:
 153
 154     /// isInterestingInstruction - This code only looks at accesses to allocas.
 155     static bool isInterestingInstruction(const Instruction *I) {
 156       return (isa<LoadInst>(I) && isa<AllocaInst>(I->getOperand(0))) ||
 157              (isa<StoreInst>(I) && isa<AllocaInst>(I->getOperand(1)));
 158     }
 159
 160     /// getInstructionIndex - Get or calculate the index of the specified
 161     /// instruction.
 162     unsigned getInstructionIndex(const Instruction *I) {
 163       assert(isInterestingInstruction(I) &&
 164              "Not a load/store to/from an alloca?");
 165
 166       // If we already have this instruction number, return it.
 167       DenseMap<const Instruction *, unsigned>::iterator It = InstNumbers.find(I);
 168       if (It != InstNumbers.end()) return It->second;
 169
 170       // Scan the whole block to get the instruction.  This accumulates
 171       // information for every interesting instruction in the block, in order to
 172       // avoid gratuitus rescans.
 173       const BasicBlock *BB = I->getParent();
 174       unsigned InstNo = 0;
 175       for (BasicBlock::const_iterator BBI = BB->begin(), E = BB->end();
 176            BBI != E; ++BBI)
 177         if (isInterestingInstruction(BBI))
 178           InstNumbers[BBI] = InstNo++;
 179       It = InstNumbers.find(I);
 180
 181       assert(It != InstNumbers.end() && "Didn't insert instruction?");
 182       return It->second;
 183     }
 184
 185     void deleteValue(const Instruction *I) {
 186       InstNumbers.erase(I);
 187     }
 188
 189     void clear() {
 190       InstNumbers.clear();
 191     }
 192   };
 193
 194   struct PromoteMem2Reg {
 195     /// Allocas - The alloca instructions being promoted.
 196     ///
 197     std::vector<AllocaInst*> Allocas;
 198     DominatorTree &DT;
 199     DIBuilder *DIB;
 200
 201     /// AST - An AliasSetTracker object to update.  If null, don't update it.
 202     ///
 203     AliasSetTracker *AST;
 204
 205     /// AllocaLookup - Reverse mapping of Allocas.
 206     ///
 207     DenseMap<AllocaInst*, unsigned>  AllocaLookup;
 208
 209     /// NewPhiNodes - The PhiNodes we're adding.
 210     ///
 211     DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*> NewPhiNodes;
 212
 213     /// PhiToAllocaMap - For each PHI node, keep track of which entry in Allocas
 214     /// it corresponds to.
 215     DenseMap<PHINode*, unsigned> PhiToAllocaMap;
 216
 217     /// PointerAllocaValues - If we are updating an AliasSetTracker, then for
 218     /// each alloca that is of pointer type, we keep track of what to copyValue
 219     /// to the inserted PHI nodes here.
 220     ///
 221     std::vector<Value*> PointerAllocaValues;
 222
 223     /// AllocaDbgDeclares - For each alloca, we keep track of the dbg.declare
 224     /// intrinsic that describes it, if any, so that we can convert it to a
 225     /// dbg.value intrinsic if the alloca gets promoted.
 226     SmallVector<DbgDeclareInst*, 8> AllocaDbgDeclares;
 227
 228     /// Visited - The set of basic blocks the renamer has already visited.
 229     ///
 230     SmallPtrSet<BasicBlock*, 16> Visited;
 231
 232     /// BBNumbers - Contains a stable numbering of basic blocks to avoid
 233     /// non-determinstic behavior.
 234     DenseMap<BasicBlock*, unsigned> BBNumbers;
 235
 236     /// DomLevels - Maps DomTreeNodes to their level in the dominator tree.
 237     DenseMap<DomTreeNode*, unsigned> DomLevels;
 238
 239     /// BBNumPreds - Lazily compute the number of predecessors a block has.
 240     DenseMap<const BasicBlock*, unsigned> BBNumPreds;
 241   public:
 242     PromoteMem2Reg(const std::vector<AllocaInst*> &A, DominatorTree &dt,
 243                    AliasSetTracker *ast)
 244       : Allocas(A), DT(dt), DIB(0), AST(ast) {}
 245     ~PromoteMem2Reg() {
 246       delete DIB;
 247     }
 248
 249     void run();
 250
 251     /// dominates - Return true if BB1 dominates BB2 using the DominatorTree.
 252     ///
 253     bool dominates(BasicBlock *BB1, BasicBlock *BB2) const {
 254       return DT.dominates(BB1, BB2);
 255     }
 256
 257   private:
 258     void RemoveFromAllocasList(unsigned &AllocaIdx) {
 259       Allocas[AllocaIdx] = Allocas.back();
 260       Allocas.pop_back();
 261       --AllocaIdx;
 262     }
 263
 264     unsigned getNumPreds(const BasicBlock *BB) {
 265       unsigned &NP = BBNumPreds[BB];
 266       if (NP == 0)
 267         NP = std::distance(pred_begin(BB), pred_end(BB))+1;
 268       return NP-1;
 269     }
 270
 271     void DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum,
 272                                  AllocaInfo &Info);
 273     void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info,
 274                              const SmallPtrSet<BasicBlock*, 32> &DefBlocks,
 275                              SmallPtrSet<BasicBlock*, 32> &LiveInBlocks);
 276
 277     void RewriteSingleStoreAlloca(AllocaInst *AI, AllocaInfo &Info,
 278                                   LargeBlockInfo &LBI);
 279     void PromoteSingleBlockAlloca(AllocaInst *AI, AllocaInfo &Info,
 280                                   LargeBlockInfo &LBI);
 281
 282     void RenamePass(BasicBlock *BB, BasicBlock *Pred,
 283                     RenamePassData::ValVector &IncVals,
 284                     std::vector<RenamePassData> &Worklist);
 285     bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version);
 286   };
 287
 288   struct AllocaInfo {
 289     SmallVector<BasicBlock*, 32> DefiningBlocks;
 290     SmallVector<BasicBlock*, 32> UsingBlocks;
 291
 292     StoreInst  *OnlyStore;
 293     BasicBlock *OnlyBlock;
 294     bool OnlyUsedInOneBlock;
 295
 296     Value *AllocaPointerVal;
 297     DbgDeclareInst *DbgDeclare;
 298
 299     void clear() {
 300       DefiningBlocks.clear();
 301       UsingBlocks.clear();
 302       OnlyStore = 0;
 303       OnlyBlock = 0;
 304       OnlyUsedInOneBlock = true;
 305       AllocaPointerVal = 0;
 306       DbgDeclare = 0;
 307     }
 308
 309     /// AnalyzeAlloca - Scan the uses of the specified alloca, filling in our
 310     /// ivars.
 311     void AnalyzeAlloca(AllocaInst *AI) {
 312       clear();
 313
 314       // As we scan the uses of the alloca instruction, keep track of stores,
 315       // and decide whether all of the loads and stores to the alloca are within
 316       // the same basic block.
 317       for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end();
 318            UI != E;)  {
 319         Instruction *User = cast<Instruction>(*UI++);
 320
 321         if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
 322           // Remember the basic blocks which define new values for the alloca
 323           DefiningBlocks.push_back(SI->getParent());
 324           AllocaPointerVal = SI->getOperand(0);
 325           OnlyStore = SI;
 326         } else {
 327           LoadInst *LI = cast<LoadInst>(User);
 328           // Otherwise it must be a load instruction, keep track of variable
 329           // reads.
 330           UsingBlocks.push_back(LI->getParent());
 331           AllocaPointerVal = LI;
 332         }
 333
 334         if (OnlyUsedInOneBlock) {
 335           if (OnlyBlock == 0)
 336             OnlyBlock = User->getParent();
 337           else if (OnlyBlock != User->getParent())
 338             OnlyUsedInOneBlock = false;
 339         }
 340       }
 341
 342       DbgDeclare = FindAllocaDbgDeclare(AI);
 343     }
 344   };
 345
 346   typedef std::pair<DomTreeNode*, unsigned> DomTreeNodePair;
 347
 348   struct DomTreeNodeCompare {
 349     bool operator()(const DomTreeNodePair &LHS, const DomTreeNodePair &RHS) {
 350       return LHS.second < RHS.second;
 351     }
 352   };
 353 }  // end of anonymous namespace
 354
 355 static void removeLifetimeIntrinsicUsers(AllocaInst *AI) {
 356   // Knowing that this alloca is promotable, we know that it's safe to kill all
 357   // instructions except for load and store.
 358
 359   for (Value::use_iterator UI = AI->use_begin(), UE = AI->use_end();
 360        UI != UE;) {
 361     Instruction *I = cast<Instruction>(*UI);
 362     ++UI;
 363     if (isa<LoadInst>(I) || isa<StoreInst>(I))
 364       continue;
 365
 366     if (!I->getType()->isVoidTy()) {
 367       // The only users of this bitcast/GEP instruction are lifetime intrinsics.
 368       // Follow the use/def chain to erase them now instead of leaving it for
 369       // dead code elimination later.
 370       for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
 371            UI != UE;) {
 372         Instruction *Inst = cast<Instruction>(*UI);
 373         ++UI;
 374         Inst->eraseFromParent();
 375       }
 376     }
 377     I->eraseFromParent();
 378   }
 379 }
 380
 381 void PromoteMem2Reg::run() {
 382   Function &F = *DT.getRoot()->getParent();
 383
 384   if (AST) PointerAllocaValues.resize(Allocas.size());
 385   AllocaDbgDeclares.resize(Allocas.size());
 386
 387   AllocaInfo Info;
 388   LargeBlockInfo LBI;
 389
 390   for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
 391     AllocaInst *AI = Allocas[AllocaNum];
 392
 393     assert(isAllocaPromotable(AI) &&
 394            "Cannot promote non-promotable alloca!");
 395     assert(AI->getParent()->getParent() == &F &&
 396            "All allocas should be in the same function, which is same as DF!");
 397
 398     removeLifetimeIntrinsicUsers(AI);
 399
 400     if (AI->use_empty()) {
 401       // If there are no uses of the alloca, just delete it now.
 402       if (AST) AST->deleteValue(AI);
 403       AI->eraseFromParent();
 404
 405       // Remove the alloca from the Allocas list, since it has been processed
 406       RemoveFromAllocasList(AllocaNum);
 407       ++NumDeadAlloca;
 408       continue;
 409     }
 410
 411     // Calculate the set of read and write-locations for each alloca.  This is
 412     // analogous to finding the 'uses' and 'definitions' of each variable.
 413     Info.AnalyzeAlloca(AI);
 414
 415     // If there is only a single store to this value, replace any loads of
 416     // it that are directly dominated by the definition with the value stored.
 417     if (Info.DefiningBlocks.size() == 1) {
 418       RewriteSingleStoreAlloca(AI, Info, LBI);
 419
 420       // Finally, after the scan, check to see if the store is all that is left.
 421       if (Info.UsingBlocks.empty()) {
 422         // Record debuginfo for the store and remove the declaration's debuginfo.
 423         if (DbgDeclareInst *DDI = Info.DbgDeclare) {
 424           if (!DIB)
 425             DIB = new DIBuilder(*DDI->getParent()->getParent()->getParent());
 426           ConvertDebugDeclareToDebugValue(DDI, Info.OnlyStore, *DIB);
 427           DDI->eraseFromParent();
 428         }
 429         // Remove the (now dead) store and alloca.
 430         Info.OnlyStore->eraseFromParent();
 431         LBI.deleteValue(Info.OnlyStore);
 432
 433         if (AST) AST->deleteValue(AI);
 434         AI->eraseFromParent();
 435         LBI.deleteValue(AI);
 436
 437         // The alloca has been processed, move on.
 438         RemoveFromAllocasList(AllocaNum);
 439
 440         ++NumSingleStore;
 441         continue;
 442       }
 443     }
 444
 445     // If the alloca is only read and written in one basic block, just perform a
 446     // linear sweep over the block to eliminate it.
 447     if (Info.OnlyUsedInOneBlock) {
 448       PromoteSingleBlockAlloca(AI, Info, LBI);
 449
 450       // Finally, after the scan, check to see if the stores are all that is
 451       // left.
 452       if (Info.UsingBlocks.empty()) {
 453
 454         // Remove the (now dead) stores and alloca.
 455         while (!AI->use_empty()) {
 456           StoreInst *SI = cast<StoreInst>(AI->use_back());
 457           // Record debuginfo for the store before removing it.
 458           if (DbgDeclareInst *DDI = Info.DbgDeclare) {
 459             if (!DIB)
 460               DIB = new DIBuilder(*SI->getParent()->getParent()->getParent());
 461             ConvertDebugDeclareToDebugValue(DDI, SI, *DIB);
 462           }
 463           SI->eraseFromParent();
 464           LBI.deleteValue(SI);
 465         }
 466
 467         if (AST) AST->deleteValue(AI);
 468         AI->eraseFromParent();
 469         LBI.deleteValue(AI);
 470
 471         // The alloca has been processed, move on.
 472         RemoveFromAllocasList(AllocaNum);
 473
 474         // The alloca's debuginfo can be removed as well.
 475         if (DbgDeclareInst *DDI = Info.DbgDeclare)
 476           DDI->eraseFromParent();
 477
 478         ++NumLocalPromoted;
 479         continue;
 480       }
 481     }
 482
 483     // If we haven't computed dominator tree levels, do so now.
 484     if (DomLevels.empty()) {
 485       SmallVector<DomTreeNode*, 32> Worklist;
 486
 487       DomTreeNode *Root = DT.getRootNode();
 488       DomLevels[Root] = 0;
 489       Worklist.push_back(Root);
 490
 491       while (!Worklist.empty()) {
 492         DomTreeNode *Node = Worklist.pop_back_val();
 493         unsigned ChildLevel = DomLevels[Node] + 1;
 494         for (DomTreeNode::iterator CI = Node->begin(), CE = Node->end();
 495              CI != CE; ++CI) {
 496           DomLevels[*CI] = ChildLevel;
 497           Worklist.push_back(*CI);
 498         }
 499       }
 500     }
 501
 502     // If we haven't computed a numbering for the BB's in the function, do so
 503     // now.
 504     if (BBNumbers.empty()) {
 505       unsigned ID = 0;
 506       for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 507         BBNumbers[I] = ID++;
 508     }
 509
 510     // If we have an AST to keep updated, remember some pointer value that is
 511     // stored into the alloca.
 512     if (AST)
 513       PointerAllocaValues[AllocaNum] = Info.AllocaPointerVal;
 514
 515     // Remember the dbg.declare intrinsic describing this alloca, if any.
 516     if (Info.DbgDeclare) AllocaDbgDeclares[AllocaNum] = Info.DbgDeclare;
 517
 518     // Keep the reverse mapping of the 'Allocas' array for the rename pass.
 519     AllocaLookup[Allocas[AllocaNum]] = AllocaNum;
 520
 521     // At this point, we're committed to promoting the alloca using IDF's, and
 522     // the standard SSA construction algorithm.  Determine which blocks need PHI
 523     // nodes and see if we can optimize out some work by avoiding insertion of
 524     // dead phi nodes.
 525     DetermineInsertionPoint(AI, AllocaNum, Info);
 526   }
 527
 528   if (Allocas.empty())
 529     return; // All of the allocas must have been trivial!
 530
 531   LBI.clear();
 532
 533
 534   // Set the incoming values for the basic block to be null values for all of
 535   // the alloca's.  We do this in case there is a load of a value that has not
 536   // been stored yet.  In this case, it will get this null value.
 537   //
 538   RenamePassData::ValVector Values(Allocas.size());
 539   for (unsigned i = 0, e = Allocas.size(); i != e; ++i)
 540     Values[i] = UndefValue::get(Allocas[i]->getAllocatedType());
 541
 542   // Walks all basic blocks in the function performing the SSA rename algorithm
 543   // and inserting the phi nodes we marked as necessary
 544   //
 545   std::vector<RenamePassData> RenamePassWorkList;
 546   RenamePassWorkList.push_back(RenamePassData(F.begin(), 0, Values));
 547   do {
 548     RenamePassData RPD;
 549     RPD.swap(RenamePassWorkList.back());
 550     RenamePassWorkList.pop_back();
 551     // RenamePass may add new worklist entries.
 552     RenamePass(RPD.BB, RPD.Pred, RPD.Values, RenamePassWorkList);
 553   } while (!RenamePassWorkList.empty());
 554
 555   // The renamer uses the Visited set to avoid infinite loops.  Clear it now.
 556   Visited.clear();
 557
 558   // Remove the allocas themselves from the function.
 559   for (unsigned i = 0, e = Allocas.size(); i != e; ++i) {
 560     Instruction *A = Allocas[i];
 561
 562     // If there are any uses of the alloca instructions left, they must be in
 563     // unreachable basic blocks that were not processed by walking the dominator
 564     // tree. Just delete the users now.
 565     if (!A->use_empty())
 566       A->replaceAllUsesWith(UndefValue::get(A->getType()));
 567     if (AST) AST->deleteValue(A);
 568     A->eraseFromParent();
 569   }
 570
 571   // Remove alloca's dbg.declare instrinsics from the function.
 572   for (unsigned i = 0, e = AllocaDbgDeclares.size(); i != e; ++i)
 573     if (DbgDeclareInst *DDI = AllocaDbgDeclares[i])
 574       DDI->eraseFromParent();
 575
 576   // Loop over all of the PHI nodes and see if there are any that we can get
 577   // rid of because they merge all of the same incoming values.  This can
 578   // happen due to undef values coming into the PHI nodes.  This process is
 579   // iterative, because eliminating one PHI node can cause others to be removed.
 580   bool EliminatedAPHI = true;
 581   while (EliminatedAPHI) {
 582     EliminatedAPHI = false;
 583
 584     for (DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*>::iterator I =
 585            NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E;) {
 586       PHINode *PN = I->second;
 587
 588       // If this PHI node merges one value and/or undefs, get the value.
 589       if (Value *V = SimplifyInstruction(PN, 0, &DT)) {
 590         if (AST && PN->getType()->isPointerTy())
 591           AST->deleteValue(PN);
 592         PN->replaceAllUsesWith(V);
 593         PN->eraseFromParent();
 594         NewPhiNodes.erase(I++);
 595         EliminatedAPHI = true;
 596         continue;
 597       }
 598       ++I;
 599     }
 600   }
 601
 602   // At this point, the renamer has added entries to PHI nodes for all reachable
 603   // code.  Unfortunately, there may be unreachable blocks which the renamer
 604   // hasn't traversed.  If this is the case, the PHI nodes may not
 605   // have incoming values for all predecessors.  Loop over all PHI nodes we have
 606   // created, inserting undef values if they are missing any incoming values.
 607   //
 608   for (DenseMap<std::pair<BasicBlock*, unsigned>, PHINode*>::iterator I =
 609          NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) {
 610     // We want to do this once per basic block.  As such, only process a block
 611     // when we find the PHI that is the first entry in the block.
 612     PHINode *SomePHI = I->second;
 613     BasicBlock *BB = SomePHI->getParent();
 614     if (&BB->front() != SomePHI)
 615       continue;
 616
 617     // Only do work here if there the PHI nodes are missing incoming values.  We
 618     // know that all PHI nodes that were inserted in a block will have the same
 619     // number of incoming values, so we can just check any of them.
 620     if (SomePHI->getNumIncomingValues() == getNumPreds(BB))
 621       continue;
 622
 623     // Get the preds for BB.
 624     SmallVector<BasicBlock*, 16> Preds(pred_begin(BB), pred_end(BB));
 625
 626     // Ok, now we know that all of the PHI nodes are missing entries for some
 627     // basic blocks.  Start by sorting the incoming predecessors for efficient
 628     // access.
 629     std::sort(Preds.begin(), Preds.end());
 630
 631     // Now we loop through all BB's which have entries in SomePHI and remove
 632     // them from the Preds list.
 633     for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) {
 634       // Do a log(n) search of the Preds list for the entry we want.
 635       SmallVector<BasicBlock*, 16>::iterator EntIt =
 636         std::lower_bound(Preds.begin(), Preds.end(),
 637                          SomePHI->getIncomingBlock(i));
 638       assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i)&&
 639              "PHI node has entry for a block which is not a predecessor!");
 640
 641       // Remove the entry
 642       Preds.erase(EntIt);
 643     }
 644
 645     // At this point, the blocks left in the preds list must have dummy
 646     // entries inserted into every PHI nodes for the block.  Update all the phi
 647     // nodes in this block that we are inserting (there could be phis before
 648     // mem2reg runs).
 649     unsigned NumBadPreds = SomePHI->getNumIncomingValues();
 650     BasicBlock::iterator BBI = BB->begin();
 651     while ((SomePHI = dyn_cast<PHINode>(BBI++)) &&
 652            SomePHI->getNumIncomingValues() == NumBadPreds) {
 653       Value *UndefVal = UndefValue::get(SomePHI->getType());
 654       for (unsigned pred = 0, e = Preds.size(); pred != e; ++pred)
 655         SomePHI->addIncoming(UndefVal, Preds[pred]);
 656     }
 657   }
 658
 659   NewPhiNodes.clear();
 660 }
 661
 662
 663 /// ComputeLiveInBlocks - Determine which blocks the value is live in.  These
 664 /// are blocks which lead to uses.  Knowing this allows us to avoid inserting
 665 /// PHI nodes into blocks which don't lead to uses (thus, the inserted phi nodes
 666 /// would be dead).
 667 void PromoteMem2Reg::
 668 ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info,
 669                     const SmallPtrSet<BasicBlock*, 32> &DefBlocks,
 670                     SmallPtrSet<BasicBlock*, 32> &LiveInBlocks) {
 671
 672   // To determine liveness, we must iterate through the predecessors of blocks
 673   // where the def is live.  Blocks are added to the worklist if we need to
 674   // check their predecessors.  Start with all the using blocks.
 675   SmallVector<BasicBlock*, 64> LiveInBlockWorklist(Info.UsingBlocks.begin(),
 676                                                    Info.UsingBlocks.end());
 677
 678   // If any of the using blocks is also a definition block, check to see if the
 679   // definition occurs before or after the use.  If it happens before the use,
 680   // the value isn't really live-in.
 681   for (unsigned i = 0, e = LiveInBlockWorklist.size(); i != e; ++i) {
 682     BasicBlock *BB = LiveInBlockWorklist[i];
 683     if (!DefBlocks.count(BB)) continue;
 684
 685     // Okay, this is a block that both uses and defines the value.  If the first
 686     // reference to the alloca is a def (store), then we know it isn't live-in.
 687     for (BasicBlock::iterator I = BB->begin(); ; ++I) {
 688       if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 689         if (SI->getOperand(1) != AI) continue;
 690
 691         // We found a store to the alloca before a load.  The alloca is not
 692         // actually live-in here.
 693         LiveInBlockWorklist[i] = LiveInBlockWorklist.back();
 694         LiveInBlockWorklist.pop_back();
 695         --i, --e;
 696         break;
 697       }
 698
 699       if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
 700         if (LI->getOperand(0) != AI) continue;
 701
 702         // Okay, we found a load before a store to the alloca.  It is actually
 703         // live into this block.
 704         break;
 705       }
 706     }
 707   }
 708
 709   // Now that we have a set of blocks where the phi is live-in, recursively add
 710   // their predecessors until we find the full region the value is live.
 711   while (!LiveInBlockWorklist.empty()) {
 712     BasicBlock *BB = LiveInBlockWorklist.pop_back_val();
 713
 714     // The block really is live in here, insert it into the set.  If already in
 715     // the set, then it has already been processed.
 716     if (!LiveInBlocks.insert(BB))
 717       continue;
 718
 719     // Since the value is live into BB, it is either defined in a predecessor or
 720     // live into it to.  Add the preds to the worklist unless they are a
 721     // defining block.
 722     for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 723       BasicBlock *P = *PI;
 724
 725       // The value is not live into a predecessor if it defines the value.
 726       if (DefBlocks.count(P))
 727         continue;
 728
 729       // Otherwise it is, add to the worklist.
 730       LiveInBlockWorklist.push_back(P);
 731     }
 732   }
 733 }
 734
 735 /// DetermineInsertionPoint - At this point, we're committed to promoting the
 736 /// alloca using IDF's, and the standard SSA construction algorithm.  Determine
 737 /// which blocks need phi nodes and see if we can optimize out some work by
 738 /// avoiding insertion of dead phi nodes.
 739 void PromoteMem2Reg::DetermineInsertionPoint(AllocaInst *AI, unsigned AllocaNum,
 740                                              AllocaInfo &Info) {
 741   // Unique the set of defining blocks for efficient lookup.
 742   SmallPtrSet<BasicBlock*, 32> DefBlocks;
 743   DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end());
 744
 745   // Determine which blocks the value is live in.  These are blocks which lead
 746   // to uses.
 747   SmallPtrSet<BasicBlock*, 32> LiveInBlocks;
 748   ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks);
 749
 750   // Use a priority queue keyed on dominator tree level so that inserted nodes
 751   // are handled from the bottom of the dominator tree upwards.
 752   typedef std::priority_queue<DomTreeNodePair, SmallVector<DomTreeNodePair, 32>,
 753                               DomTreeNodeCompare> IDFPriorityQueue;
 754   IDFPriorityQueue PQ;
 755
 756   for (SmallPtrSet<BasicBlock*, 32>::const_iterator I = DefBlocks.begin(),
 757        E = DefBlocks.end(); I != E; ++I) {
 758     if (DomTreeNode *Node = DT.getNode(*I))
 759       PQ.push(std::make_pair(Node, DomLevels[Node]));
 760   }
 761
 762   SmallVector<std::pair<unsigned, BasicBlock*>, 32> DFBlocks;
 763   SmallPtrSet<DomTreeNode*, 32> Visited;
 764   SmallVector<DomTreeNode*, 32> Worklist;
 765   while (!PQ.empty()) {
 766     DomTreeNodePair RootPair = PQ.top();
 767     PQ.pop();
 768     DomTreeNode *Root = RootPair.first;
 769     unsigned RootLevel = RootPair.second;
 770
 771     // Walk all dominator tree children of Root, inspecting their CFG edges with
 772     // targets elsewhere on the dominator tree. Only targets whose level is at
 773     // most Root's level are added to the iterated dominance frontier of the
 774     // definition set.
 775
 776     Worklist.clear();
 777     Worklist.push_back(Root);
 778
 779     while (!Worklist.empty()) {
 780       DomTreeNode *Node = Worklist.pop_back_val();
 781       BasicBlock *BB = Node->getBlock();
 782
 783       for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE;
 784            ++SI) {
 785         DomTreeNode *SuccNode = DT.getNode(*SI);
 786
 787         // Quickly skip all CFG edges that are also dominator tree edges instead
 788         // of catching them below.
 789         if (SuccNode->getIDom() == Node)
 790           continue;
 791
 792         unsigned SuccLevel = DomLevels[SuccNode];
 793         if (SuccLevel > RootLevel)
 794           continue;
 795
 796         if (!Visited.insert(SuccNode))
 797           continue;
 798
 799         BasicBlock *SuccBB = SuccNode->getBlock();
 800         if (!LiveInBlocks.count(SuccBB))
 801           continue;
 802
 803         DFBlocks.push_back(std::make_pair(BBNumbers[SuccBB], SuccBB));
 804         if (!DefBlocks.count(SuccBB))
 805           PQ.push(std::make_pair(SuccNode, SuccLevel));
 806       }
 807
 808       for (DomTreeNode::iterator CI = Node->begin(), CE = Node->end(); CI != CE;
 809            ++CI) {
 810         if (!Visited.count(*CI))
 811           Worklist.push_back(*CI);
 812       }
 813     }
 814   }
 815
 816   if (DFBlocks.size() > 1)
 817     std::sort(DFBlocks.begin(), DFBlocks.end());
 818
 819   unsigned CurrentVersion = 0;
 820   for (unsigned i = 0, e = DFBlocks.size(); i != e; ++i)
 821     QueuePhiNode(DFBlocks[i].second, AllocaNum, CurrentVersion);
 822 }
 823
 824 /// RewriteSingleStoreAlloca - If there is only a single store to this value,
 825 /// replace any loads of it that are directly dominated by the definition with
 826 /// the value stored.
 827 void PromoteMem2Reg::RewriteSingleStoreAlloca(AllocaInst *AI,
 828                                               AllocaInfo &Info,
 829                                               LargeBlockInfo &LBI) {
 830   StoreInst *OnlyStore = Info.OnlyStore;
 831   bool StoringGlobalVal = !isa<Instruction>(OnlyStore->getOperand(0));
 832   BasicBlock *StoreBB = OnlyStore->getParent();
 833   int StoreIndex = -1;
 834
 835   // Clear out UsingBlocks.  We will reconstruct it here if needed.
 836   Info.UsingBlocks.clear();
 837
 838   for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E; ) {
 839     Instruction *UserInst = cast<Instruction>(*UI++);
 840     if (!isa<LoadInst>(UserInst)) {
 841       assert(UserInst == OnlyStore && "Should only have load/stores");
 842       continue;
 843     }
 844     LoadInst *LI = cast<LoadInst>(UserInst);
 845
 846     // Okay, if we have a load from the alloca, we want to replace it with the
 847     // only value stored to the alloca.  We can do this if the value is
 848     // dominated by the store.  If not, we use the rest of the mem2reg machinery
 849     // to insert the phi nodes as needed.
 850     if (!StoringGlobalVal) {  // Non-instructions are always dominated.
 851       if (LI->getParent() == StoreBB) {
 852         // If we have a use that is in the same block as the store, compare the
 853         // indices of the two instructions to see which one came first.  If the
 854         // load came before the store, we can't handle it.
 855         if (StoreIndex == -1)
 856           StoreIndex = LBI.getInstructionIndex(OnlyStore);
 857
 858         if (unsigned(StoreIndex) > LBI.getInstructionIndex(LI)) {
 859           // Can't handle this load, bail out.
 860           Info.UsingBlocks.push_back(StoreBB);
 861           continue;
 862         }
 863
 864       } else if (LI->getParent() != StoreBB &&
 865                  !dominates(StoreBB, LI->getParent())) {
 866         // If the load and store are in different blocks, use BB dominance to
 867         // check their relationships.  If the store doesn't dom the use, bail
 868         // out.
 869         Info.UsingBlocks.push_back(LI->getParent());
 870         continue;
 871       }
 872     }
 873
 874     // Otherwise, we *can* safely rewrite this load.
 875     Value *ReplVal = OnlyStore->getOperand(0);
 876     // If the replacement value is the load, this must occur in unreachable
 877     // code.
 878     if (ReplVal == LI)
 879       ReplVal = UndefValue::get(LI->getType());
 880     LI->replaceAllUsesWith(ReplVal);
 881     if (AST && LI->getType()->isPointerTy())
 882       AST->deleteValue(LI);
 883     LI->eraseFromParent();
 884     LBI.deleteValue(LI);
 885   }
 886 }
 887
 888 namespace {
 889
 890 /// StoreIndexSearchPredicate - This is a helper predicate used to search by the
 891 /// first element of a pair.
 892 struct StoreIndexSearchPredicate {
 893   bool operator()(const std::pair<unsigned, StoreInst*> &LHS,
 894                   const std::pair<unsigned, StoreInst*> &RHS) {
 895     return LHS.first < RHS.first;
 896   }
 897 };
 898
 899 }
 900
 901 /// PromoteSingleBlockAlloca - Many allocas are only used within a single basic
 902 /// block.  If this is the case, avoid traversing the CFG and inserting a lot of
 903 /// potentially useless PHI nodes by just performing a single linear pass over
 904 /// the basic block using the Alloca.
 905 ///
 906 /// If we cannot promote this alloca (because it is read before it is written),
 907 /// return true.  This is necessary in cases where, due to control flow, the
 908 /// alloca is potentially undefined on some control flow paths.  e.g. code like
 909 /// this is potentially correct:
 910 ///
 911 ///   for (...) { if (c) { A = undef; undef = B; } }
 912 ///
 913 /// ... so long as A is not used before undef is set.
 914 ///
 915 void PromoteMem2Reg::PromoteSingleBlockAlloca(AllocaInst *AI, AllocaInfo &Info,
 916                                               LargeBlockInfo &LBI) {
 917   // The trickiest case to handle is when we have large blocks. Because of this,
 918   // this code is optimized assuming that large blocks happen.  This does not
 919   // significantly pessimize the small block case.  This uses LargeBlockInfo to
 920   // make it efficient to get the index of various operations in the block.
 921
 922   // Clear out UsingBlocks.  We will reconstruct it here if needed.
 923   Info.UsingBlocks.clear();
 924
 925   // Walk the use-def list of the alloca, getting the locations of all stores.
 926   typedef SmallVector<std::pair<unsigned, StoreInst*>, 64> StoresByIndexTy;
 927   StoresByIndexTy StoresByIndex;
 928
 929   for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end();
 930        UI != E; ++UI)
 931     if (StoreInst *SI = dyn_cast<StoreInst>(*UI))
 932       StoresByIndex.push_back(std::make_pair(LBI.getInstructionIndex(SI), SI));
 933
 934   // If there are no stores to the alloca, just replace any loads with undef.
 935   if (StoresByIndex.empty()) {
 936     for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;)
 937       if (LoadInst *LI = dyn_cast<LoadInst>(*UI++)) {
 938         LI->replaceAllUsesWith(UndefValue::get(LI->getType()));
 939         if (AST && LI->getType()->isPointerTy())
 940           AST->deleteValue(LI);
 941         LBI.deleteValue(LI);
 942         LI->eraseFromParent();
 943       }
 944     return;
 945   }
 946
 947   // Sort the stores by their index, making it efficient to do a lookup with a
 948   // binary search.
 949   std::sort(StoresByIndex.begin(), StoresByIndex.end());
 950
 951   // Walk all of the loads from this alloca, replacing them with the nearest
 952   // store above them, if any.
 953   for (Value::use_iterator UI = AI->use_begin(), E = AI->use_end(); UI != E;) {
 954     LoadInst *LI = dyn_cast<LoadInst>(*UI++);
 955     if (!LI) continue;
 956
 957     unsigned LoadIdx = LBI.getInstructionIndex(LI);
 958
 959     // Find the nearest store that has a lower than this load.
 960     StoresByIndexTy::iterator I =
 961       std::lower_bound(StoresByIndex.begin(), StoresByIndex.end(),
 962                        std::pair<unsigned, StoreInst*>(LoadIdx, static_cast<StoreInst*>(0)),
 963                        StoreIndexSearchPredicate());
 964
 965     // If there is no store before this load, then we can't promote this load.
 966     if (I == StoresByIndex.begin()) {
 967       // Can't handle this load, bail out.
 968       Info.UsingBlocks.push_back(LI->getParent());
 969       continue;
 970     }
 971
 972     // Otherwise, there was a store before this load, the load takes its value.
 973     --I;
 974     LI->replaceAllUsesWith(I->second->getOperand(0));
 975     if (AST && LI->getType()->isPointerTy())
 976       AST->deleteValue(LI);
 977     LI->eraseFromParent();
 978     LBI.deleteValue(LI);
 979   }
 980 }
 981
 982 // QueuePhiNode - queues a phi-node to be added to a basic-block for a specific
 983 // Alloca returns true if there wasn't already a phi-node for that variable
 984 //
 985 bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo,
 986                                   unsigned &Version) {
 987   // Look up the basic-block in question.
 988   PHINode *&PN = NewPhiNodes[std::make_pair(BB, AllocaNo)];
 989
 990   // If the BB already has a phi node added for the i'th alloca then we're done!
 991   if (PN) return false;
 992
 993   // Create a PhiNode using the dereferenced type... and add the phi-node to the
 994   // BasicBlock.
 995   PN = PHINode::Create(Allocas[AllocaNo]->getAllocatedType(), getNumPreds(BB),
 996                        Allocas[AllocaNo]->getName() + "." + Twine(Version++),
 997                        BB->begin());
 998   ++NumPHIInsert;
 999   PhiToAllocaMap[PN] = AllocaNo;
1000
1001   if (AST && PN->getType()->isPointerTy())
1002     AST->copyValue(PointerAllocaValues[AllocaNo], PN);
1003
1004   return true;
1005 }
1006
1007 // RenamePass - Recursively traverse the CFG of the function, renaming loads and
1008 // stores to the allocas which we are promoting.  IncomingVals indicates what
1009 // value each Alloca contains on exit from the predecessor block Pred.
1010 //
1011 void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred,
1012                                 RenamePassData::ValVector &IncomingVals,
1013                                 std::vector<RenamePassData> &Worklist) {
1014 NextIteration:
1015   // If we are inserting any phi nodes into this BB, they will already be in the
1016   // block.
1017   if (PHINode *APN = dyn_cast<PHINode>(BB->begin())) {
1018     // If we have PHI nodes to update, compute the number of edges from Pred to
1019     // BB.
1020     if (PhiToAllocaMap.count(APN)) {
1021       // We want to be able to distinguish between PHI nodes being inserted by
1022       // this invocation of mem2reg from those phi nodes that already existed in
1023       // the IR before mem2reg was run.  We determine that APN is being inserted
1024       // because it is missing incoming edges.  All other PHI nodes being
1025       // inserted by this pass of mem2reg will have the same number of incoming
1026       // operands so far.  Remember this count.
1027       unsigned NewPHINumOperands = APN->getNumOperands();
1028
1029       unsigned NumEdges = 0;
1030       for (succ_iterator I = succ_begin(Pred), E = succ_end(Pred); I != E; ++I)
1031         if (*I == BB)
1032           ++NumEdges;
1033       assert(NumEdges && "Must be at least one edge from Pred to BB!");
1034
1035       // Add entries for all the phis.
1036       BasicBlock::iterator PNI = BB->begin();
1037       do {
1038         unsigned AllocaNo = PhiToAllocaMap[APN];
1039
1040         // Add N incoming values to the PHI node.
1041         for (unsigned i = 0; i != NumEdges; ++i)
1042           APN->addIncoming(IncomingVals[AllocaNo], Pred);
1043
1044         // The currently active variable for this block is now the PHI.
1045         IncomingVals[AllocaNo] = APN;
1046
1047         // Get the next phi node.
1048         ++PNI;
1049         APN = dyn_cast<PHINode>(PNI);
1050         if (APN == 0) break;
1051
1052         // Verify that it is missing entries.  If not, it is not being inserted
1053         // by this mem2reg invocation so we want to ignore it.
1054       } while (APN->getNumOperands() == NewPHINumOperands);
1055     }
1056   }
1057
1058   // Don't revisit blocks.
1059   if (!Visited.insert(BB)) return;
1060
1061   for (BasicBlock::iterator II = BB->begin(); !isa<TerminatorInst>(II); ) {
1062     Instruction *I = II++; // get the instruction, increment iterator
1063
1064     if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
1065       AllocaInst *Src = dyn_cast<AllocaInst>(LI->getPointerOperand());
1066       if (!Src) continue;
1067
1068       DenseMap<AllocaInst*, unsigned>::iterator AI = AllocaLookup.find(Src);
1069       if (AI == AllocaLookup.end()) continue;
1070
1071       Value *V = IncomingVals[AI->second];
1072
1073       // Anything using the load now uses the current value.
1074       LI->replaceAllUsesWith(V);
1075       if (AST && LI->getType()->isPointerTy())
1076         AST->deleteValue(LI);
1077       BB->getInstList().erase(LI);
1078     } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
1079       // Delete this instruction and mark the name as the current holder of the
1080       // value
1081       AllocaInst *Dest = dyn_cast<AllocaInst>(SI->getPointerOperand());
1082       if (!Dest) continue;
1083
1084       DenseMap<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Dest);
1085       if (ai == AllocaLookup.end())
1086         continue;
1087
1088       // what value were we writing?
1089       IncomingVals[ai->second] = SI->getOperand(0);
1090       // Record debuginfo for the store before removing it.
1091       if (DbgDeclareInst *DDI = AllocaDbgDeclares[ai->second]) {
1092         if (!DIB)
1093           DIB = new DIBuilder(*SI->getParent()->getParent()->getParent());
1094         ConvertDebugDeclareToDebugValue(DDI, SI, *DIB);
1095       }
1096       BB->getInstList().erase(SI);
1097     }
1098   }
1099
1100   // 'Recurse' to our successors.
1101   succ_iterator I = succ_begin(BB), E = succ_end(BB);
1102   if (I == E) return;
1103
1104   // Keep track of the successors so we don't visit the same successor twice
1105   SmallPtrSet<BasicBlock*, 8> VisitedSuccs;
1106
1107   // Handle the first successor without using the worklist.
1108   VisitedSuccs.insert(*I);
1109   Pred = BB;
1110   BB = *I;
1111   ++I;
1112
1113   for (; I != E; ++I)
1114     if (VisitedSuccs.insert(*I))
1115       Worklist.push_back(RenamePassData(*I, Pred, IncomingVals));
1116
1117   goto NextIteration;
1118 }
1119
1120 /// PromoteMemToReg - Promote the specified list of alloca instructions into
1121 /// scalar registers, inserting PHI nodes as appropriate.  This function does
1122 /// not modify the CFG of the function at all.  All allocas must be from the
1123 /// same function.
1124 ///
1125 /// If AST is specified, the specified tracker is updated to reflect changes
1126 /// made to the IR.
1127 ///
1128 void llvm::PromoteMemToReg(const std::vector<AllocaInst*> &Allocas,
1129                            DominatorTree &DT, AliasSetTracker *AST) {
1130   // If there is nothing to do, bail out...
1131   if (Allocas.empty()) return;
1132
1133   PromoteMem2Reg(Allocas, DT, AST).run();
1134 }