LLVM API Documentation

PromoteMemoryToRegister.cpp

Go to the documentation of this file.
00001 //===- PromoteMemoryToRegister.cpp - Convert allocas to registers ---------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file promote memory references to be register references.  It promotes
00011 // alloca instructions which only have loads and stores as uses.  An alloca is
00012 // transformed by using dominator frontiers to place PHI nodes, then traversing
00013 // the function in depth-first order to rewrite loads and stores as appropriate.
00014 // This is just the standard SSA construction algorithm to construct "pruned"
00015 // SSA form.
00016 //
00017 //===----------------------------------------------------------------------===//
00018 
00019 #include "llvm/Transforms/Utils/PromoteMemToReg.h"
00020 #include "llvm/Constants.h"
00021 #include "llvm/DerivedTypes.h"
00022 #include "llvm/Function.h"
00023 #include "llvm/Instructions.h"
00024 #include "llvm/Analysis/Dominators.h"
00025 #include "llvm/Analysis/AliasSetTracker.h"
00026 #include "llvm/ADT/StringExtras.h"
00027 #include "llvm/Support/CFG.h"
00028 #include "llvm/Support/StableBasicBlockNumbering.h"
00029 #include <algorithm>
00030 using namespace llvm;
00031 
00032 /// isAllocaPromotable - Return true if this alloca is legal for promotion.
00033 /// This is true if there are only loads and stores to the alloca.
00034 ///
00035 bool llvm::isAllocaPromotable(const AllocaInst *AI, const TargetData &TD) {
00036   // FIXME: If the memory unit is of pointer or integer type, we can permit
00037   // assignments to subsections of the memory unit.
00038 
00039   // Only allow direct loads and stores...
00040   for (Value::use_const_iterator UI = AI->use_begin(), UE = AI->use_end();
00041        UI != UE; ++UI)     // Loop over all of the uses of the alloca
00042     if (isa<LoadInst>(*UI)) {
00043       // noop
00044     } else if (const StoreInst *SI = dyn_cast<StoreInst>(*UI)) {
00045       if (SI->getOperand(0) == AI)
00046         return false;   // Don't allow a store OF the AI, only INTO the AI.
00047     } else {
00048       return false;   // Not a load or store.
00049     }
00050 
00051   return true;
00052 }
00053 
00054 namespace {
00055   struct PromoteMem2Reg {
00056     /// Allocas - The alloca instructions being promoted.
00057     ///
00058     std::vector<AllocaInst*> Allocas;
00059     std::vector<AllocaInst*> &RetryList;
00060     DominatorTree &DT;
00061     DominanceFrontier &DF;
00062     const TargetData &TD;
00063 
00064     /// AST - An AliasSetTracker object to update.  If null, don't update it.
00065     ///
00066     AliasSetTracker *AST;
00067 
00068     /// AllocaLookup - Reverse mapping of Allocas.
00069     ///
00070     std::map<AllocaInst*, unsigned>  AllocaLookup;
00071 
00072     /// NewPhiNodes - The PhiNodes we're adding.
00073     ///
00074     std::map<BasicBlock*, std::vector<PHINode*> > NewPhiNodes;
00075 
00076     /// PointerAllocaValues - If we are updating an AliasSetTracker, then for
00077     /// each alloca that is of pointer type, we keep track of what to copyValue
00078     /// to the inserted PHI nodes here.
00079     ///
00080     std::vector<Value*> PointerAllocaValues;
00081 
00082     /// Visited - The set of basic blocks the renamer has already visited.
00083     ///
00084     std::set<BasicBlock*> Visited;
00085 
00086     /// BBNumbers - Contains a stable numbering of basic blocks to avoid
00087     /// non-determinstic behavior.
00088     StableBasicBlockNumbering BBNumbers;
00089 
00090   public:
00091     PromoteMem2Reg(const std::vector<AllocaInst*> &A,
00092                    std::vector<AllocaInst*> &Retry, DominatorTree &dt,
00093                    DominanceFrontier &df, const TargetData &td,
00094                    AliasSetTracker *ast)
00095       : Allocas(A), RetryList(Retry), DT(dt), DF(df), TD(td), AST(ast) {}
00096 
00097     void run();
00098 
00099     /// properlyDominates - Return true if I1 properly dominates I2.
00100     ///
00101     bool properlyDominates(Instruction *I1, Instruction *I2) const {
00102       if (InvokeInst *II = dyn_cast<InvokeInst>(I1))
00103         I1 = II->getNormalDest()->begin();
00104       return DT[I1->getParent()]->properlyDominates(DT[I2->getParent()]);
00105     }
00106     
00107     /// dominates - Return true if BB1 dominates BB2 using the DominatorTree.
00108     ///
00109     bool dominates(BasicBlock *BB1, BasicBlock *BB2) const {
00110       return DT[BB1]->dominates(DT[BB2]);
00111     }
00112 
00113   private:
00114     void MarkDominatingPHILive(BasicBlock *BB, unsigned AllocaNum,
00115                                std::set<PHINode*> &DeadPHINodes);
00116     bool PromoteLocallyUsedAlloca(BasicBlock *BB, AllocaInst *AI);
00117     void PromoteLocallyUsedAllocas(BasicBlock *BB,
00118                                    const std::vector<AllocaInst*> &AIs);
00119 
00120     void RenamePass(BasicBlock *BB, BasicBlock *Pred,
00121                     std::vector<Value*> &IncVals);
00122     bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version,
00123                       std::set<PHINode*> &InsertedPHINodes);
00124   };
00125 }  // end of anonymous namespace
00126 
00127 void PromoteMem2Reg::run() {
00128   Function &F = *DF.getRoot()->getParent();
00129 
00130   // LocallyUsedAllocas - Keep track of all of the alloca instructions which are
00131   // only used in a single basic block.  These instructions can be efficiently
00132   // promoted by performing a single linear scan over that one block.  Since
00133   // individual basic blocks are sometimes large, we group together all allocas
00134   // that are live in a single basic block by the basic block they are live in.
00135   std::map<BasicBlock*, std::vector<AllocaInst*> > LocallyUsedAllocas;
00136 
00137   if (AST) PointerAllocaValues.resize(Allocas.size());
00138 
00139   for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
00140     AllocaInst *AI = Allocas[AllocaNum];
00141 
00142     assert(isAllocaPromotable(AI, TD) &&
00143            "Cannot promote non-promotable alloca!");
00144     assert(AI->getParent()->getParent() == &F &&
00145            "All allocas should be in the same function, which is same as DF!");
00146 
00147     if (AI->use_empty()) {
00148       // If there are no uses of the alloca, just delete it now.
00149       if (AST) AST->deleteValue(AI);
00150       AI->getParent()->getInstList().erase(AI);
00151 
00152       // Remove the alloca from the Allocas list, since it has been processed
00153       Allocas[AllocaNum] = Allocas.back();
00154       Allocas.pop_back();
00155       --AllocaNum;
00156       continue;
00157     }
00158 
00159     // Calculate the set of read and write-locations for each alloca.  This is
00160     // analogous to finding the 'uses' and 'definitions' of each variable.
00161     std::vector<BasicBlock*> DefiningBlocks;
00162     std::vector<BasicBlock*> UsingBlocks;
00163 
00164     StoreInst  *OnlyStore = 0;
00165     BasicBlock *OnlyBlock = 0;
00166     bool OnlyUsedInOneBlock = true;
00167 
00168     // As we scan the uses of the alloca instruction, keep track of stores, and
00169     // decide whether all of the loads and stores to the alloca are within the
00170     // same basic block.
00171     Value *AllocaPointerVal = 0;
00172     for (Value::use_iterator U =AI->use_begin(), E = AI->use_end(); U != E;++U){
00173       Instruction *User = cast<Instruction>(*U);
00174       if (StoreInst *SI = dyn_cast<StoreInst>(User)) {
00175         // Remember the basic blocks which define new values for the alloca
00176         DefiningBlocks.push_back(SI->getParent());
00177         AllocaPointerVal = SI->getOperand(0);
00178         OnlyStore = SI;
00179       } else {
00180         LoadInst *LI = cast<LoadInst>(User);
00181         // Otherwise it must be a load instruction, keep track of variable reads
00182         UsingBlocks.push_back(LI->getParent());
00183         AllocaPointerVal = LI;
00184       }
00185 
00186       if (OnlyUsedInOneBlock) {
00187         if (OnlyBlock == 0)
00188           OnlyBlock = User->getParent();
00189         else if (OnlyBlock != User->getParent())
00190           OnlyUsedInOneBlock = false;
00191       }
00192     }
00193 
00194     // If the alloca is only read and written in one basic block, just perform a
00195     // linear sweep over the block to eliminate it.
00196     if (OnlyUsedInOneBlock) {
00197       LocallyUsedAllocas[OnlyBlock].push_back(AI);
00198 
00199       // Remove the alloca from the Allocas list, since it will be processed.
00200       Allocas[AllocaNum] = Allocas.back();
00201       Allocas.pop_back();
00202       --AllocaNum;
00203       continue;
00204     }
00205 
00206     // If there is only a single store to this value, replace any loads of
00207     // it that are directly dominated by the definition with the value stored.
00208     if (DefiningBlocks.size() == 1) {
00209       // Be aware of loads before the store.
00210       std::set<BasicBlock*> ProcessedBlocks;
00211       for (unsigned i = 0, e = UsingBlocks.size(); i != e; ++i)
00212         // If the store dominates the block and if we haven't processed it yet,
00213         // do so now.
00214         if (dominates(OnlyStore->getParent(), UsingBlocks[i]))
00215           if (ProcessedBlocks.insert(UsingBlocks[i]).second) {
00216             BasicBlock *UseBlock = UsingBlocks[i];
00217             
00218             // If the use and store are in the same block, do a quick scan to
00219             // verify that there are no uses before the store.
00220             if (UseBlock == OnlyStore->getParent()) {
00221               BasicBlock::iterator I = UseBlock->begin();
00222               for (; &*I != OnlyStore; ++I) { // scan block for store.
00223                 if (isa<LoadInst>(I) && I->getOperand(0) == AI)
00224                   break;
00225               }
00226               if (&*I != OnlyStore) break;  // Do not handle this case.
00227             }
00228         
00229             // Otherwise, if this is a different block or if all uses happen
00230             // after the store, do a simple linear scan to replace loads with
00231             // the stored value.
00232             for (BasicBlock::iterator I = UseBlock->begin(),E = UseBlock->end();
00233                  I != E; ) {
00234               if (LoadInst *LI = dyn_cast<LoadInst>(I++)) {
00235                 if (LI->getOperand(0) == AI) {
00236                   LI->replaceAllUsesWith(OnlyStore->getOperand(0));
00237                   if (AST && isa<PointerType>(LI->getType()))
00238                     AST->deleteValue(LI);
00239                   LI->eraseFromParent();
00240                 }
00241               }
00242             }
00243             
00244             // Finally, remove this block from the UsingBlock set.
00245             UsingBlocks[i] = UsingBlocks.back();
00246             --i; --e;
00247           }
00248 
00249       // Finally, after the scan, check to see if the store is all that is left.
00250       if (UsingBlocks.empty()) {
00251         // The alloca has been processed, move on.
00252         Allocas[AllocaNum] = Allocas.back();
00253         Allocas.pop_back();
00254         --AllocaNum;
00255         continue;
00256       }
00257     }
00258     
00259     
00260     if (AST)
00261       PointerAllocaValues[AllocaNum] = AllocaPointerVal;
00262 
00263     // If we haven't computed a numbering for the BB's in the function, do so
00264     // now.
00265     BBNumbers.compute(F);
00266 
00267     // Compute the locations where PhiNodes need to be inserted.  Look at the
00268     // dominance frontier of EACH basic-block we have a write in.
00269     //
00270     unsigned CurrentVersion = 0;
00271     std::set<PHINode*> InsertedPHINodes;
00272     std::vector<unsigned> DFBlocks;
00273     while (!DefiningBlocks.empty()) {
00274       BasicBlock *BB = DefiningBlocks.back();
00275       DefiningBlocks.pop_back();
00276 
00277       // Look up the DF for this write, add it to PhiNodes
00278       DominanceFrontier::const_iterator it = DF.find(BB);
00279       if (it != DF.end()) {
00280         const DominanceFrontier::DomSetType &S = it->second;
00281 
00282         // In theory we don't need the indirection through the DFBlocks vector.
00283         // In practice, the order of calling QueuePhiNode would depend on the
00284         // (unspecified) ordering of basic blocks in the dominance frontier,
00285         // which would give PHI nodes non-determinstic subscripts.  Fix this by
00286         // processing blocks in order of the occurance in the function.
00287         for (DominanceFrontier::DomSetType::const_iterator P = S.begin(),
00288              PE = S.end(); P != PE; ++P)
00289           DFBlocks.push_back(BBNumbers.getNumber(*P));
00290 
00291         // Sort by which the block ordering in the function.
00292         std::sort(DFBlocks.begin(), DFBlocks.end());
00293 
00294         for (unsigned i = 0, e = DFBlocks.size(); i != e; ++i) {
00295           BasicBlock *BB = BBNumbers.getBlock(DFBlocks[i]);
00296           if (QueuePhiNode(BB, AllocaNum, CurrentVersion, InsertedPHINodes))
00297             DefiningBlocks.push_back(BB);
00298         }
00299         DFBlocks.clear();
00300       }
00301     }
00302 
00303     // Now that we have inserted PHI nodes along the Iterated Dominance Frontier
00304     // of the writes to the variable, scan through the reads of the variable,
00305     // marking PHI nodes which are actually necessary as alive (by removing them
00306     // from the InsertedPHINodes set).  This is not perfect: there may PHI
00307     // marked alive because of loads which are dominated by stores, but there
00308     // will be no unmarked PHI nodes which are actually used.
00309     //
00310     for (unsigned i = 0, e = UsingBlocks.size(); i != e; ++i)
00311       MarkDominatingPHILive(UsingBlocks[i], AllocaNum, InsertedPHINodes);
00312     UsingBlocks.clear();
00313 
00314     // If there are any PHI nodes which are now known to be dead, remove them!
00315     for (std::set<PHINode*>::iterator I = InsertedPHINodes.begin(),
00316            E = InsertedPHINodes.end(); I != E; ++I) {
00317       PHINode *PN = *I;
00318       std::vector<PHINode*> &BBPNs = NewPhiNodes[PN->getParent()];
00319       BBPNs[AllocaNum] = 0;
00320 
00321       // Check to see if we just removed the last inserted PHI node from this
00322       // basic block.  If so, remove the entry for the basic block.
00323       bool HasOtherPHIs = false;
00324       for (unsigned i = 0, e = BBPNs.size(); i != e; ++i)
00325         if (BBPNs[i]) {
00326           HasOtherPHIs = true;
00327           break;
00328         }
00329       if (!HasOtherPHIs)
00330         NewPhiNodes.erase(PN->getParent());
00331 
00332       if (AST && isa<PointerType>(PN->getType()))
00333         AST->deleteValue(PN);
00334       PN->getParent()->getInstList().erase(PN);
00335     }
00336 
00337     // Keep the reverse mapping of the 'Allocas' array.
00338     AllocaLookup[Allocas[AllocaNum]] = AllocaNum;
00339   }
00340 
00341   // Process all allocas which are only used in a single basic block.
00342   for (std::map<BasicBlock*, std::vector<AllocaInst*> >::iterator I =
00343          LocallyUsedAllocas.begin(), E = LocallyUsedAllocas.end(); I != E; ++I){
00344     const std::vector<AllocaInst*> &LocAllocas = I->second;
00345     assert(!LocAllocas.empty() && "empty alloca list??");
00346 
00347     // It's common for there to only be one alloca in the list.  Handle it
00348     // efficiently.
00349     if (LocAllocas.size() == 1) {
00350       // If we can do the quick promotion pass, do so now.
00351       if (PromoteLocallyUsedAlloca(I->first, LocAllocas[0]))
00352         RetryList.push_back(LocAllocas[0]);  // Failed, retry later.
00353     } else {
00354       // Locally promote anything possible.  Note that if this is unable to
00355       // promote a particular alloca, it puts the alloca onto the Allocas vector
00356       // for global processing.
00357       PromoteLocallyUsedAllocas(I->first, LocAllocas);
00358     }
00359   }
00360 
00361   if (Allocas.empty())
00362     return; // All of the allocas must have been trivial!
00363 
00364   // Set the incoming values for the basic block to be null values for all of
00365   // the alloca's.  We do this in case there is a load of a value that has not
00366   // been stored yet.  In this case, it will get this null value.
00367   //
00368   std::vector<Value *> Values(Allocas.size());
00369   for (unsigned i = 0, e = Allocas.size(); i != e; ++i)
00370     Values[i] = UndefValue::get(Allocas[i]->getAllocatedType());
00371 
00372   // Walks all basic blocks in the function performing the SSA rename algorithm
00373   // and inserting the phi nodes we marked as necessary
00374   //
00375   RenamePass(F.begin(), 0, Values);
00376 
00377   // The renamer uses the Visited set to avoid infinite loops.  Clear it now.
00378   Visited.clear();
00379 
00380   // Remove the allocas themselves from the function...
00381   for (unsigned i = 0, e = Allocas.size(); i != e; ++i) {
00382     Instruction *A = Allocas[i];
00383 
00384     // If there are any uses of the alloca instructions left, they must be in
00385     // sections of dead code that were not processed on the dominance frontier.
00386     // Just delete the users now.
00387     //
00388     if (!A->use_empty())
00389       A->replaceAllUsesWith(UndefValue::get(A->getType()));
00390     if (AST) AST->deleteValue(A);
00391     A->getParent()->getInstList().erase(A);
00392   }
00393 
00394   // At this point, the renamer has added entries to PHI nodes for all reachable
00395   // code.  Unfortunately, there may be blocks which are not reachable, which
00396   // the renamer hasn't traversed.  If this is the case, the PHI nodes may not
00397   // have incoming values for all predecessors.  Loop over all PHI nodes we have
00398   // created, inserting undef values if they are missing any incoming values.
00399   //
00400   for (std::map<BasicBlock*, std::vector<PHINode *> >::iterator I =
00401          NewPhiNodes.begin(), E = NewPhiNodes.end(); I != E; ++I) {
00402 
00403     std::vector<BasicBlock*> Preds(pred_begin(I->first), pred_end(I->first));
00404     std::vector<PHINode*> &PNs = I->second;
00405     assert(!PNs.empty() && "Empty PHI node list??");
00406 
00407     // Loop over all of the PHI nodes and see if there are any that we can get
00408     // rid of because they merge all of the same incoming values.  This can
00409     // happen due to undef values coming into the PHI nodes.
00410     PHINode *SomePHI = 0;
00411     for (unsigned i = 0, e = PNs.size(); i != e; ++i)
00412       if (PNs[i]) {
00413         if (Value *V = PNs[i]->hasConstantValue(true)) {
00414           if (!isa<Instruction>(V) ||
00415               properlyDominates(cast<Instruction>(V), PNs[i])) {
00416             if (AST && isa<PointerType>(PNs[i]->getType()))
00417               AST->deleteValue(PNs[i]);
00418             PNs[i]->replaceAllUsesWith(V);
00419             PNs[i]->eraseFromParent();
00420             PNs[i] = 0;
00421           }
00422         }
00423         if (PNs[i])
00424           SomePHI = PNs[i];
00425       }
00426 
00427     // Only do work here if there the PHI nodes are missing incoming values.  We
00428     // know that all PHI nodes that were inserted in a block will have the same
00429     // number of incoming values, so we can just check any PHI node.
00430     if (SomePHI && Preds.size() != SomePHI->getNumIncomingValues()) {
00431       // Ok, now we know that all of the PHI nodes are missing entries for some
00432       // basic blocks.  Start by sorting the incoming predecessors for efficient
00433       // access.
00434       std::sort(Preds.begin(), Preds.end());
00435 
00436       // Now we loop through all BB's which have entries in SomePHI and remove
00437       // them from the Preds list.
00438       for (unsigned i = 0, e = SomePHI->getNumIncomingValues(); i != e; ++i) {
00439         // Do a log(n) search of the Preds list for the entry we want.
00440         std::vector<BasicBlock*>::iterator EntIt =
00441           std::lower_bound(Preds.begin(), Preds.end(),
00442                            SomePHI->getIncomingBlock(i));
00443         assert(EntIt != Preds.end() && *EntIt == SomePHI->getIncomingBlock(i)&&
00444                "PHI node has entry for a block which is not a predecessor!");
00445 
00446         // Remove the entry
00447         Preds.erase(EntIt);
00448       }
00449 
00450       // At this point, the blocks left in the preds list must have dummy
00451       // entries inserted into every PHI nodes for the block.
00452       for (unsigned i = 0, e = PNs.size(); i != e; ++i)
00453         if (PHINode *PN = PNs[i]) {
00454           Value *UndefVal = UndefValue::get(PN->getType());
00455           for (unsigned pred = 0, e = Preds.size(); pred != e; ++pred)
00456             PN->addIncoming(UndefVal, Preds[pred]);
00457         }
00458     }
00459   }
00460 }
00461 
00462 // MarkDominatingPHILive - Mem2Reg wants to construct "pruned" SSA form, not
00463 // "minimal" SSA form.  To do this, it inserts all of the PHI nodes on the IDF
00464 // as usual (inserting the PHI nodes in the DeadPHINodes set), then processes
00465 // each read of the variable.  For each block that reads the variable, this
00466 // function is called, which removes used PHI nodes from the DeadPHINodes set.
00467 // After all of the reads have been processed, any PHI nodes left in the
00468 // DeadPHINodes set are removed.
00469 //
00470 void PromoteMem2Reg::MarkDominatingPHILive(BasicBlock *BB, unsigned AllocaNum,
00471                                            std::set<PHINode*> &DeadPHINodes) {
00472   // Scan the immediate dominators of this block looking for a block which has a
00473   // PHI node for Alloca num.  If we find it, mark the PHI node as being alive!
00474   for (DominatorTree::Node *N = DT[BB]; N; N = N->getIDom()) {
00475     BasicBlock *DomBB = N->getBlock();
00476     std::map<BasicBlock*, std::vector<PHINode*> >::iterator
00477       I = NewPhiNodes.find(DomBB);
00478     if (I != NewPhiNodes.end() && I->second[AllocaNum]) {
00479       // Ok, we found an inserted PHI node which dominates this value.
00480       PHINode *DominatingPHI = I->second[AllocaNum];
00481 
00482       // Find out if we previously thought it was dead.
00483       std::set<PHINode*>::iterator DPNI = DeadPHINodes.find(DominatingPHI);
00484       if (DPNI != DeadPHINodes.end()) {
00485         // Ok, until now, we thought this PHI node was dead.  Mark it as being
00486         // alive/needed.
00487         DeadPHINodes.erase(DPNI);
00488 
00489         // Now that we have marked the PHI node alive, also mark any PHI nodes
00490         // which it might use as being alive as well.
00491         for (pred_iterator PI = pred_begin(DomBB), PE = pred_end(DomBB);
00492              PI != PE; ++PI)
00493           MarkDominatingPHILive(*PI, AllocaNum, DeadPHINodes);
00494       }
00495     }
00496   }
00497 }
00498 
00499 /// PromoteLocallyUsedAlloca - Many allocas are only used within a single basic
00500 /// block.  If this is the case, avoid traversing the CFG and inserting a lot of
00501 /// potentially useless PHI nodes by just performing a single linear pass over
00502 /// the basic block using the Alloca.
00503 ///
00504 /// If we cannot promote this alloca (because it is read before it is written),
00505 /// return true.  This is necessary in cases where, due to control flow, the
00506 /// alloca is potentially undefined on some control flow paths.  e.g. code like
00507 /// this is potentially correct:
00508 ///
00509 ///   for (...) { if (c) { A = undef; undef = B; } }
00510 ///
00511 /// ... so long as A is not used before undef is set.
00512 ///
00513 bool PromoteMem2Reg::PromoteLocallyUsedAlloca(BasicBlock *BB, AllocaInst *AI) {
00514   assert(!AI->use_empty() && "There are no uses of the alloca!");
00515 
00516   // Handle degenerate cases quickly.
00517   if (AI->hasOneUse()) {
00518     Instruction *U = cast<Instruction>(AI->use_back());
00519     if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
00520       // Must be a load of uninitialized value.
00521       LI->replaceAllUsesWith(UndefValue::get(AI->getAllocatedType()));
00522       if (AST && isa<PointerType>(LI->getType()))
00523         AST->deleteValue(LI);
00524     } else {
00525       // Otherwise it must be a store which is never read.
00526       assert(isa<StoreInst>(U));
00527     }
00528     BB->getInstList().erase(U);
00529   } else {
00530     // Uses of the uninitialized memory location shall get undef.
00531     Value *CurVal = 0;
00532 
00533     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
00534       Instruction *Inst = I++;
00535       if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
00536         if (LI->getOperand(0) == AI) {
00537           if (!CurVal) return true;  // Could not locally promote!
00538 
00539           // Loads just returns the "current value"...
00540           LI->replaceAllUsesWith(CurVal);
00541           if (AST && isa<PointerType>(LI->getType()))
00542             AST->deleteValue(LI);
00543           BB->getInstList().erase(LI);
00544         }
00545       } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
00546         if (SI->getOperand(1) == AI) {
00547           // Store updates the "current value"...
00548           CurVal = SI->getOperand(0);
00549           BB->getInstList().erase(SI);
00550         }
00551       }
00552     }
00553   }
00554 
00555   // After traversing the basic block, there should be no more uses of the
00556   // alloca, remove it now.
00557   assert(AI->use_empty() && "Uses of alloca from more than one BB??");
00558   if (AST) AST->deleteValue(AI);
00559   AI->getParent()->getInstList().erase(AI);
00560   return false;
00561 }
00562 
00563 /// PromoteLocallyUsedAllocas - This method is just like
00564 /// PromoteLocallyUsedAlloca, except that it processes multiple alloca
00565 /// instructions in parallel.  This is important in cases where we have large
00566 /// basic blocks, as we don't want to rescan the entire basic block for each
00567 /// alloca which is locally used in it (which might be a lot).
00568 void PromoteMem2Reg::
00569 PromoteLocallyUsedAllocas(BasicBlock *BB, const std::vector<AllocaInst*> &AIs) {
00570   std::map<AllocaInst*, Value*> CurValues;
00571   for (unsigned i = 0, e = AIs.size(); i != e; ++i)
00572     CurValues[AIs[i]] = 0; // Insert with null value
00573 
00574   for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ) {
00575     Instruction *Inst = I++;
00576     if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
00577       // Is this a load of an alloca we are tracking?
00578       if (AllocaInst *AI = dyn_cast<AllocaInst>(LI->getOperand(0))) {
00579         std::map<AllocaInst*, Value*>::iterator AIt = CurValues.find(AI);
00580         if (AIt != CurValues.end()) {
00581           // If loading an uninitialized value, allow the inter-block case to
00582           // handle it.  Due to control flow, this might actually be ok.
00583           if (AIt->second == 0) {  // Use of locally uninitialized value??
00584             RetryList.push_back(AI);   // Retry elsewhere.
00585             CurValues.erase(AIt);   // Stop tracking this here.
00586             if (CurValues.empty()) return;
00587           } else {
00588             // Loads just returns the "current value"...
00589             LI->replaceAllUsesWith(AIt->second);
00590             if (AST && isa<PointerType>(LI->getType()))
00591               AST->deleteValue(LI);
00592             BB->getInstList().erase(LI);
00593           }
00594         }
00595       }
00596     } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
00597       if (AllocaInst *AI = dyn_cast<AllocaInst>(SI->getOperand(1))) {
00598         std::map<AllocaInst*, Value*>::iterator AIt = CurValues.find(AI);
00599         if (AIt != CurValues.end()) {
00600           // Store updates the "current value"...
00601           AIt->second = SI->getOperand(0);
00602           BB->getInstList().erase(SI);
00603         }
00604       }
00605     }
00606   }
00607 }
00608 
00609 
00610 
00611 // QueuePhiNode - queues a phi-node to be added to a basic-block for a specific
00612 // Alloca returns true if there wasn't already a phi-node for that variable
00613 //
00614 bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo,
00615                                   unsigned &Version,
00616                                   std::set<PHINode*> &InsertedPHINodes) {
00617   // Look up the basic-block in question.
00618   std::vector<PHINode*> &BBPNs = NewPhiNodes[BB];
00619   if (BBPNs.empty()) BBPNs.resize(Allocas.size());
00620 
00621   // If the BB already has a phi node added for the i'th alloca then we're done!
00622   if (BBPNs[AllocaNo]) return false;
00623 
00624   // Create a PhiNode using the dereferenced type... and add the phi-node to the
00625   // BasicBlock.
00626   PHINode *PN = new PHINode(Allocas[AllocaNo]->getAllocatedType(),
00627                             Allocas[AllocaNo]->getName() + "." +
00628                                         utostr(Version++), BB->begin());
00629   BBPNs[AllocaNo] = PN;
00630   InsertedPHINodes.insert(PN);
00631 
00632   if (AST && isa<PointerType>(PN->getType()))
00633     AST->copyValue(PointerAllocaValues[AllocaNo], PN);
00634 
00635   return true;
00636 }
00637 
00638 
00639 // RenamePass - Recursively traverse the CFG of the function, renaming loads and
00640 // stores to the allocas which we are promoting.  IncomingVals indicates what
00641 // value each Alloca contains on exit from the predecessor block Pred.
00642 //
00643 void PromoteMem2Reg::RenamePass(BasicBlock *BB, BasicBlock *Pred,
00644                                 std::vector<Value*> &IncomingVals) {
00645 
00646   // If this BB needs a PHI node, update the PHI node for each variable we need
00647   // PHI nodes for.
00648   std::map<BasicBlock*, std::vector<PHINode *> >::iterator
00649     BBPNI = NewPhiNodes.find(BB);
00650   if (BBPNI != NewPhiNodes.end()) {
00651     std::vector<PHINode *> &BBPNs = BBPNI->second;
00652     for (unsigned k = 0; k != BBPNs.size(); ++k)
00653       if (PHINode *PN = BBPNs[k]) {
00654         // Add this incoming value to the PHI node.
00655         PN->addIncoming(IncomingVals[k], Pred);
00656 
00657         // The currently active variable for this block is now the PHI.
00658         IncomingVals[k] = PN;
00659       }
00660   }
00661 
00662   // don't revisit nodes
00663   if (Visited.count(BB)) return;
00664 
00665   // mark as visited
00666   Visited.insert(BB);
00667 
00668   for (BasicBlock::iterator II = BB->begin(); !isa<TerminatorInst>(II); ) {
00669     Instruction *I = II++; // get the instruction, increment iterator
00670 
00671     if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
00672       if (AllocaInst *Src = dyn_cast<AllocaInst>(LI->getPointerOperand())) {
00673         std::map<AllocaInst*, unsigned>::iterator AI = AllocaLookup.find(Src);
00674         if (AI != AllocaLookup.end()) {
00675           Value *V = IncomingVals[AI->second];
00676 
00677           // walk the use list of this load and replace all uses with r
00678           LI->replaceAllUsesWith(V);
00679           if (AST && isa<PointerType>(LI->getType()))
00680             AST->deleteValue(LI);
00681           BB->getInstList().erase(LI);
00682         }
00683       }
00684     } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
00685       // Delete this instruction and mark the name as the current holder of the
00686       // value
00687       if (AllocaInst *Dest = dyn_cast<AllocaInst>(SI->getPointerOperand())) {
00688         std::map<AllocaInst *, unsigned>::iterator ai = AllocaLookup.find(Dest);
00689         if (ai != AllocaLookup.end()) {
00690           // what value were we writing?
00691           IncomingVals[ai->second] = SI->getOperand(0);
00692           BB->getInstList().erase(SI);
00693         }
00694       }
00695     }
00696   }
00697 
00698   // Recurse to our successors.
00699   TerminatorInst *TI = BB->getTerminator();
00700   for (unsigned i = 0; i != TI->getNumSuccessors(); i++) {
00701     std::vector<Value*> OutgoingVals(IncomingVals);
00702     RenamePass(TI->getSuccessor(i), BB, OutgoingVals);
00703   }
00704 }
00705 
00706 /// PromoteMemToReg - Promote the specified list of alloca instructions into
00707 /// scalar registers, inserting PHI nodes as appropriate.  This function makes
00708 /// use of DominanceFrontier information.  This function does not modify the CFG
00709 /// of the function at all.  All allocas must be from the same function.
00710 ///
00711 /// If AST is specified, the specified tracker is updated to reflect changes
00712 /// made to the IR.
00713 ///
00714 void llvm::PromoteMemToReg(const std::vector<AllocaInst*> &Allocas,
00715                            DominatorTree &DT, DominanceFrontier &DF,
00716                            const TargetData &TD, AliasSetTracker *AST) {
00717   // If there is nothing to do, bail out...
00718   if (Allocas.empty()) return;
00719 
00720   std::vector<AllocaInst*> RetryList;
00721   PromoteMem2Reg(Allocas, RetryList, DT, DF, TD, AST).run();
00722 
00723   // PromoteMem2Reg may not have been able to promote all of the allocas in one
00724   // pass, run it again if needed.
00725   while (!RetryList.empty()) {
00726     // If we need to retry some allocas, this is due to there being no store
00727     // before a read in a local block.  To counteract this, insert a store of
00728     // undef into the alloca right after the alloca itself.
00729     for (unsigned i = 0, e = RetryList.size(); i != e; ++i) {
00730       BasicBlock::iterator BBI = RetryList[i];
00731 
00732       new StoreInst(UndefValue::get(RetryList[i]->getAllocatedType()),
00733                     RetryList[i], ++BBI);
00734     }
00735 
00736     std::vector<AllocaInst*> NewAllocas;
00737     std::swap(NewAllocas, RetryList);
00738     PromoteMem2Reg(NewAllocas, RetryList, DT, DF, TD, AST).run();
00739   }
00740 }