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