LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

PRE.cpp

Go to the documentation of this file.
00001 //===- PRE.cpp - Partial Redundancy Elimination ---------------------------===//
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 implements the well-known Partial Redundancy Elimination
00011 // optimization, using an SSA formulation based on e-paths.  See this paper for
00012 // more information:
00013 //
00014 //  E-path_PRE: partial redundancy elimination made easy
00015 //  By: Dhananjay M. Dhamdhere   In: ACM SIGPLAN Notices. Vol 37, #8, 2002
00016 //    http://doi.acm.org/10.1145/596992.597004
00017 //
00018 // This file actually implements a sparse version of the algorithm, using SSA
00019 // and CFG properties instead of bit-vectors.
00020 //
00021 //===----------------------------------------------------------------------===//
00022 
00023 #include "llvm/Pass.h"
00024 #include "llvm/Function.h"
00025 #include "llvm/Type.h"
00026 #include "llvm/Instructions.h"
00027 #include "llvm/Support/CFG.h"
00028 #include "llvm/Analysis/Dominators.h"
00029 #include "llvm/Analysis/PostDominators.h"
00030 #include "llvm/Analysis/ValueNumbering.h"
00031 #include "llvm/Transforms/Scalar.h"
00032 #include "llvm/Support/Debug.h"
00033 #include "llvm/ADT/DepthFirstIterator.h"
00034 #include "llvm/ADT/PostOrderIterator.h"
00035 #include "llvm/ADT/Statistic.h"
00036 #include "llvm/ADT/hash_set"
00037 #include "llvm/ADT/hash_map"
00038 using namespace llvm;
00039 
00040 namespace {
00041   Statistic<> NumExprsEliminated("pre", "Number of expressions constantified");
00042   Statistic<> NumRedundant      ("pre", "Number of redundant exprs eliminated");
00043   Statistic<> NumInserted       ("pre", "Number of expressions inserted");
00044 
00045   struct PRE : public FunctionPass {
00046     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00047       AU.addRequiredID(BreakCriticalEdgesID);  // No critical edges for now!
00048       AU.addRequired<PostDominatorTree>();
00049       AU.addRequired<PostDominanceFrontier>();
00050       AU.addRequired<DominatorSet>();
00051       AU.addRequired<DominatorTree>();
00052       AU.addRequired<DominanceFrontier>();
00053       AU.addRequired<ValueNumbering>();
00054     }
00055     virtual bool runOnFunction(Function &F);
00056 
00057   private:
00058     // Block information - Map basic blocks in a function back and forth to
00059     // unsigned integers.
00060     std::vector<BasicBlock*> BlockMapping;
00061     hash_map<BasicBlock*, unsigned> BlockNumbering;
00062 
00063     // ProcessedExpressions - Keep track of which expressions have already been
00064     // processed.
00065     hash_set<Instruction*> ProcessedExpressions;
00066 
00067     // Provide access to the various analyses used...
00068     DominatorSet      *DS;
00069     DominatorTree     *DT; PostDominatorTree *PDT;
00070     DominanceFrontier *DF; PostDominanceFrontier *PDF;
00071     ValueNumbering    *VN;
00072 
00073     // AvailableBlocks - Contain a mapping of blocks with available expression
00074     // values to the expression value itself.  This can be used as an efficient
00075     // way to find out if the expression is available in the block, and if so,
00076     // which version to use.  This map is only used while processing a single
00077     // expression.
00078     //
00079     typedef hash_map<BasicBlock*, Instruction*> AvailableBlocksTy;
00080     AvailableBlocksTy AvailableBlocks;
00081 
00082     bool ProcessBlock(BasicBlock *BB);
00083     
00084     // Anticipatibility calculation...
00085     void MarkPostDominatingBlocksAnticipatible(PostDominatorTree::Node *N,
00086                                                std::vector<char> &AntBlocks,
00087                                                Instruction *Occurrence);
00088     void CalculateAnticipatiblityForOccurrence(unsigned BlockNo,
00089                                               std::vector<char> &AntBlocks,
00090                                               Instruction *Occurrence);
00091     void CalculateAnticipatibleBlocks(const std::map<unsigned, Instruction*> &D,
00092                                       std::vector<char> &AnticipatibleBlocks);
00093 
00094     // PRE for an expression
00095     void MarkOccurrenceAvailableInAllDominatedBlocks(Instruction *Occurrence,
00096                                                      BasicBlock *StartBlock);
00097     void ReplaceDominatedAvailableOccurrencesWith(Instruction *NewOcc,
00098                                                   DominatorTree::Node *N);
00099     bool ProcessExpression(Instruction *I);
00100   };
00101 
00102   RegisterOpt<PRE> Z("pre", "Partial Redundancy Elimination");
00103 }
00104 
00105 
00106 bool PRE::runOnFunction(Function &F) {
00107   VN  = &getAnalysis<ValueNumbering>();
00108   DS  = &getAnalysis<DominatorSet>();
00109   DT  = &getAnalysis<DominatorTree>();
00110   DF  = &getAnalysis<DominanceFrontier>();
00111   PDT = &getAnalysis<PostDominatorTree>();
00112   PDF = &getAnalysis<PostDominanceFrontier>();
00113 
00114   DEBUG(std::cerr << "\n*** Running PRE on func '" << F.getName() << "'...\n");
00115 
00116   // Number the basic blocks based on a reverse post-order traversal of the CFG
00117   // so that all predecessors of a block (ignoring back edges) are visited
00118   // before a block is visited.
00119   //
00120   BlockMapping.reserve(F.size());
00121   {
00122     ReversePostOrderTraversal<Function*> RPOT(&F);
00123     DEBUG(std::cerr << "Block order: ");
00124     for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
00125            E = RPOT.end(); I != E; ++I) {
00126       // Keep track of mapping...
00127       BasicBlock *BB = *I;
00128       BlockNumbering.insert(std::make_pair(BB, BlockMapping.size()));
00129       BlockMapping.push_back(BB);
00130       DEBUG(std::cerr << BB->getName() << " ");
00131     }
00132     DEBUG(std::cerr << "\n");
00133   }
00134 
00135   // Traverse the current function depth-first in dominator-tree order.  This
00136   // ensures that we see all definitions before their uses (except for PHI
00137   // nodes), allowing us to hoist dependent expressions correctly.
00138   bool Changed = false;
00139   for (unsigned i = 0, e = BlockMapping.size(); i != e; ++i)
00140     Changed |= ProcessBlock(BlockMapping[i]);
00141 
00142   // Free memory
00143   BlockMapping.clear();
00144   BlockNumbering.clear();
00145   ProcessedExpressions.clear();
00146   return Changed;
00147 }
00148 
00149 
00150 // ProcessBlock - Process any expressions first seen in this block...
00151 //
00152 bool PRE::ProcessBlock(BasicBlock *BB) {
00153   bool Changed = false;
00154 
00155   // DISABLED: This pass invalidates iterators and then uses them.
00156   return false;
00157 
00158   // PRE expressions first defined in this block...
00159   for (BasicBlock::iterator I = BB->begin(); I != BB->end(); )
00160     if (ProcessExpression(I++))
00161       Changed = true;
00162 
00163   return Changed;
00164 }
00165 
00166 void PRE::MarkPostDominatingBlocksAnticipatible(PostDominatorTree::Node *N,
00167                                                 std::vector<char> &AntBlocks,
00168                                                 Instruction *Occurrence) {
00169   unsigned BlockNo = BlockNumbering[N->getBlock()];
00170 
00171   if (AntBlocks[BlockNo]) return;  // Already known to be anticipatible??
00172 
00173   // Check to see if any of the operands are defined in this block, if so, the
00174   // entry of this block does not anticipate the expression.  This computes
00175   // "transparency".
00176   for (unsigned i = 0, e = Occurrence->getNumOperands(); i != e; ++i)
00177     if (Instruction *I = dyn_cast<Instruction>(Occurrence->getOperand(i)))
00178       if (I->getParent() == N->getBlock())  // Operand is defined in this block!
00179         return;
00180 
00181   if (isa<LoadInst>(Occurrence))
00182     return;        // FIXME: compute transparency for load instructions using AA
00183 
00184   // Insert block into AntBlocks list...
00185   AntBlocks[BlockNo] = true;
00186 
00187   for (PostDominatorTree::Node::iterator I = N->begin(), E = N->end(); I != E;
00188        ++I)
00189     MarkPostDominatingBlocksAnticipatible(*I, AntBlocks, Occurrence);
00190 }
00191 
00192 void PRE::CalculateAnticipatiblityForOccurrence(unsigned BlockNo,
00193                                                 std::vector<char> &AntBlocks,
00194                                                 Instruction *Occurrence) {
00195   if (AntBlocks[BlockNo]) return;  // Block already anticipatible!
00196 
00197   BasicBlock *BB = BlockMapping[BlockNo];
00198 
00199   // For each occurrence, mark all post-dominated blocks as anticipatible...
00200   MarkPostDominatingBlocksAnticipatible(PDT->getNode(BB), AntBlocks,
00201                                         Occurrence);
00202 
00203   // Next, mark any blocks in the post-dominance frontier as anticipatible iff
00204   // all successors are anticipatible.
00205   //
00206   PostDominanceFrontier::iterator PDFI = PDF->find(BB);
00207   if (PDFI != DF->end())
00208     for (std::set<BasicBlock*>::iterator DI = PDFI->second.begin();
00209          DI != PDFI->second.end(); ++DI) {
00210       BasicBlock *PDFBlock = *DI;
00211       bool AllSuccessorsAnticipatible = true;
00212       for (succ_iterator SI = succ_begin(PDFBlock), SE = succ_end(PDFBlock);
00213            SI != SE; ++SI)
00214         if (!AntBlocks[BlockNumbering[*SI]]) {
00215           AllSuccessorsAnticipatible = false;
00216           break;
00217         }
00218 
00219       if (AllSuccessorsAnticipatible)
00220         CalculateAnticipatiblityForOccurrence(BlockNumbering[PDFBlock],
00221                                               AntBlocks, Occurrence);
00222     }
00223 }
00224 
00225 
00226 void PRE::CalculateAnticipatibleBlocks(const std::map<unsigned,
00227                                                       Instruction*> &Defs,
00228                                        std::vector<char> &AntBlocks) {
00229   // Initialize to zeros...
00230   AntBlocks.resize(BlockMapping.size());
00231 
00232   // Loop over all of the expressions...
00233   for (std::map<unsigned, Instruction*>::const_iterator I = Defs.begin(),
00234          E = Defs.end(); I != E; ++I)
00235     CalculateAnticipatiblityForOccurrence(I->first, AntBlocks, I->second);
00236 }
00237 
00238 /// MarkOccurrenceAvailableInAllDominatedBlocks - Add entries to AvailableBlocks
00239 /// for all nodes dominated by the occurrence to indicate that it is now the
00240 /// available occurrence to use in any of these blocks.
00241 ///
00242 void PRE::MarkOccurrenceAvailableInAllDominatedBlocks(Instruction *Occurrence,
00243                                                       BasicBlock *BB) {
00244   // FIXME: There are much more efficient ways to get the blocks dominated
00245   // by a block.  Use them.
00246   //
00247   DominatorTree::Node *N = DT->getNode(Occurrence->getParent());
00248   for (df_iterator<DominatorTree::Node*> DI = df_begin(N), E = df_end(N);
00249        DI != E; ++DI)
00250     AvailableBlocks[(*DI)->getBlock()] = Occurrence;
00251 }
00252 
00253 /// ReplaceDominatedAvailableOccurrencesWith - This loops over the region
00254 /// dominated by N, replacing any available expressions with NewOcc.
00255 void PRE::ReplaceDominatedAvailableOccurrencesWith(Instruction *NewOcc,
00256                                                    DominatorTree::Node *N) {
00257   BasicBlock *BB = N->getBlock();
00258   Instruction *&ExistingAvailableVal = AvailableBlocks[BB];
00259 
00260   // If there isn't a definition already active in this node, make this the new
00261   // active definition...
00262   if (ExistingAvailableVal == 0) {
00263     ExistingAvailableVal = NewOcc;
00264     
00265     for (DominatorTree::Node::iterator I = N->begin(), E = N->end(); I != E;++I)
00266       ReplaceDominatedAvailableOccurrencesWith(NewOcc, *I);
00267   } else {
00268     // If there is already an active definition in this block, replace it with
00269     // NewOcc, and force it into all dominated blocks.
00270     DEBUG(std::cerr << "  Replacing dominated occ %"
00271           << ExistingAvailableVal->getName() << " with %" << NewOcc->getName()
00272           << "\n");
00273     assert(ExistingAvailableVal != NewOcc && "NewOcc already inserted??");
00274     ExistingAvailableVal->replaceAllUsesWith(NewOcc);
00275     ++NumRedundant;
00276 
00277     assert(ExistingAvailableVal->getParent() == BB &&
00278            "OldOcc not defined in current block?");
00279     BB->getInstList().erase(ExistingAvailableVal);
00280 
00281     // Mark NewOCC as the Available expression in all blocks dominated by BB
00282     for (df_iterator<DominatorTree::Node*> DI = df_begin(N), E = df_end(N);
00283          DI != E; ++DI)
00284       AvailableBlocks[(*DI)->getBlock()] = NewOcc;
00285   }  
00286 }
00287 
00288 
00289 /// ProcessExpression - Given an expression (instruction) process the
00290 /// instruction to remove any partial redundancies induced by equivalent
00291 /// computations.  Note that we only need to PRE each expression once, so we
00292 /// keep track of whether an expression has been PRE'd already, and don't PRE an
00293 /// expression again.  Expressions may be seen multiple times because process
00294 /// the entire equivalence class at once, which may leave expressions later in
00295 /// the control path.
00296 ///
00297 bool PRE::ProcessExpression(Instruction *Expr) {
00298   if (Expr->mayWriteToMemory() || Expr->getType() == Type::VoidTy ||
00299       isa<PHINode>(Expr))
00300     return false;         // Cannot move expression
00301   if (ProcessedExpressions.count(Expr)) return false; // Already processed.
00302 
00303   // Ok, this is the first time we have seen the expression.  Build a set of
00304   // equivalent expressions using SSA def/use information.  We consider
00305   // expressions to be equivalent if they are the same opcode and have
00306   // equivalent operands.  As a special case for SSA, values produced by PHI
00307   // nodes are considered to be equivalent to all of their operands.
00308   //
00309   std::vector<Value*> Values;
00310   VN->getEqualNumberNodes(Expr, Values);
00311 
00312 #if 0
00313   // FIXME: This should handle PHI nodes correctly.  To do this, we need to
00314   // consider expressions of the following form equivalent to this set of
00315   // expressions:
00316   //
00317   // If an operand is a PHI node, add any occurrences of the expression with the
00318   // PHI operand replaced with the PHI node operands.  This is only valid if the
00319   // PHI operand occurrences exist in blocks post-dominated by the incoming edge
00320   // of the PHI node.
00321 #endif
00322 
00323   // We have to be careful to handle expression definitions which dominated by
00324   // other expressions.  These can be directly eliminated in favor of their
00325   // dominating value.  Keep track of which blocks contain definitions (the key)
00326   // and if a block contains a definition, which instruction it is.
00327   //
00328   std::map<unsigned, Instruction*> Definitions;
00329   Definitions.insert(std::make_pair(BlockNumbering[Expr->getParent()], Expr));
00330 
00331   bool Changed = false;
00332 
00333   // Look at all of the equal values.  If any of the values is not an
00334   // instruction, replace all other expressions immediately with it (it must be
00335   // an argument or a constant or something). Otherwise, convert the list of
00336   // values into a list of expression (instruction) definitions ordering
00337   // according to their dominator tree ordering.
00338   //
00339   Value *NonInstValue = 0;
00340   for (unsigned i = 0, e = Values.size(); i != e; ++i)
00341     if (Instruction *I = dyn_cast<Instruction>(Values[i])) {
00342       Instruction *&BlockInst = Definitions[BlockNumbering[I->getParent()]];
00343       if (BlockInst && BlockInst != I) {    // Eliminate direct redundancy
00344         if (DS->dominates(I, BlockInst)) {  // I dom BlockInst
00345           BlockInst->replaceAllUsesWith(I);
00346           BlockInst->getParent()->getInstList().erase(BlockInst);
00347         } else {                            // BlockInst dom I
00348           I->replaceAllUsesWith(BlockInst);
00349           I->getParent()->getInstList().erase(I);
00350           I = BlockInst;
00351         }
00352         ++NumRedundant;
00353       }
00354       BlockInst = I;
00355     } else {
00356       NonInstValue = Values[i];
00357     }
00358 
00359   std::vector<Value*>().swap(Values);  // Done with the values list
00360 
00361   if (NonInstValue) {
00362     // This is the good, though unlikely, case where we find out that this
00363     // expression is equal to a constant or argument directly.  We can replace
00364     // this and all of the other equivalent instructions with the value
00365     // directly.
00366     //
00367     for (std::map<unsigned, Instruction*>::iterator I = Definitions.begin(),
00368            E = Definitions.end(); I != E; ++I) {
00369       Instruction *Inst = I->second;
00370       // Replace the value with the specified non-instruction value.
00371       Inst->replaceAllUsesWith(NonInstValue);       // Fixup any uses
00372       Inst->getParent()->getInstList().erase(Inst); // Erase the instruction
00373     }
00374     NumExprsEliminated += Definitions.size();
00375     return true;   // Program modified!
00376   }
00377 
00378   // There are no expressions equal to this one.  Exit early.
00379   assert(!Definitions.empty() && "no equal expressions??");
00380 #if 0
00381   if (Definitions.size() == 1) {
00382     ProcessedExpressions.insert(Definitions.begin()->second);
00383     return Changed;
00384   }
00385 #endif
00386   DEBUG(std::cerr << "\n====--- Expression: " << *Expr);
00387   const Type *ExprType = Expr->getType();
00388 
00389   // AnticipatibleBlocks - Blocks where the current expression is anticipatible.
00390   // This is logically std::vector<bool> but using 'char' for performance.
00391   std::vector<char> AnticipatibleBlocks;
00392 
00393   // Calculate all of the blocks which the current expression is anticipatible.
00394   CalculateAnticipatibleBlocks(Definitions, AnticipatibleBlocks);
00395 
00396   // Print out anticipatible blocks...
00397   DEBUG(std::cerr << "AntBlocks: ";
00398         for (unsigned i = 0, e = AnticipatibleBlocks.size(); i != e; ++i)
00399           if (AnticipatibleBlocks[i])
00400             std::cerr << BlockMapping[i]->getName() <<" ";
00401         std::cerr << "\n";);
00402   
00403 
00404 
00405   // AvailabilityFrontier - Calculates the availability frontier for the current
00406   // expression.  The availability frontier contains the blocks on the dominance
00407   // frontier of the current available expressions, iff they anticipate a
00408   // definition of the expression.
00409   hash_set<unsigned> AvailabilityFrontier;
00410 
00411   Instruction *NonPHIOccurrence = 0;
00412 
00413   while (!Definitions.empty() || !AvailabilityFrontier.empty()) {
00414     if (!Definitions.empty() &&
00415         (AvailabilityFrontier.empty() ||
00416          Definitions.begin()->first < *AvailabilityFrontier.begin())) {
00417       Instruction *Occurrence = Definitions.begin()->second;
00418       BasicBlock *BB = Occurrence->getParent();
00419       Definitions.erase(Definitions.begin());
00420 
00421       DEBUG(std::cerr << "PROCESSING Occurrence: " << *Occurrence);
00422 
00423       // Check to see if there is already an incoming value for this block...
00424       AvailableBlocksTy::iterator LBI = AvailableBlocks.find(BB);
00425       if (LBI != AvailableBlocks.end()) {
00426         // Yes, there is a dominating definition for this block.  Replace this
00427         // occurrence with the incoming value.
00428         if (LBI->second != Occurrence) {
00429           DEBUG(std::cerr << "  replacing with: " << *LBI->second);
00430           Occurrence->replaceAllUsesWith(LBI->second);
00431           BB->getInstList().erase(Occurrence);   // Delete instruction
00432           ++NumRedundant;
00433         }
00434       } else {
00435         ProcessedExpressions.insert(Occurrence);
00436         if (!isa<PHINode>(Occurrence))
00437           NonPHIOccurrence = Occurrence;  // Keep an occurrence of this expr
00438 
00439         // Okay, there is no incoming value for this block, so this expression
00440         // is a new definition that is good for this block and all blocks
00441         // dominated by it.  Add this information to the AvailableBlocks map.
00442         //
00443         MarkOccurrenceAvailableInAllDominatedBlocks(Occurrence, BB);
00444 
00445         // Update the dominance frontier for the definitions so far... if a node
00446         // in the dominator frontier now has all of its predecessors available,
00447         // and the block is in an anticipatible region, we can insert a PHI node
00448         // in that block.
00449         DominanceFrontier::iterator DFI = DF->find(BB);
00450         if (DFI != DF->end()) {
00451           for (std::set<BasicBlock*>::iterator DI = DFI->second.begin();
00452                DI != DFI->second.end(); ++DI) {
00453             BasicBlock *DFBlock = *DI;
00454             unsigned DFBlockID = BlockNumbering[DFBlock];
00455             if (AnticipatibleBlocks[DFBlockID]) {
00456               // Check to see if any of the predecessors of this block on the
00457               // frontier are not available...
00458               bool AnyNotAvailable = false;
00459               for (pred_iterator PI = pred_begin(DFBlock),
00460                      PE = pred_end(DFBlock); PI != PE; ++PI)
00461                 if (!AvailableBlocks.count(*PI)) {
00462                   AnyNotAvailable = true;
00463                   break;
00464                 }
00465             
00466               // If any predecessor blocks are not available, add the node to
00467               // the current expression dominance frontier.
00468               if (AnyNotAvailable) {
00469                 AvailabilityFrontier.insert(DFBlockID);
00470               } else {
00471                 // This block is no longer in the availability frontier, it IS
00472                 // available.
00473                 AvailabilityFrontier.erase(DFBlockID);
00474 
00475                 // If all of the predecessor blocks are available (and the block
00476                 // anticipates a definition along the path to the exit), we need
00477                 // to insert a new PHI node in this block.  This block serves as
00478                 // a new definition for the expression, extending the available
00479                 // region.
00480                 //
00481                 PHINode *PN = new PHINode(ExprType, Expr->getName()+".pre",
00482                                           DFBlock->begin());
00483                 ProcessedExpressions.insert(PN);
00484 
00485                 DEBUG(std::cerr << "  INSERTING PHI on frontier: " << *PN);
00486 
00487                 // Add the incoming blocks for the PHI node
00488                 for (pred_iterator PI = pred_begin(DFBlock),
00489                        PE = pred_end(DFBlock); PI != PE; ++PI)
00490                   if (*PI != DFBlock)
00491                     PN->addIncoming(AvailableBlocks[*PI], *PI);
00492                   else                          // edge from the current block
00493                     PN->addIncoming(PN, DFBlock);
00494 
00495                 Instruction *&BlockOcc = Definitions[DFBlockID];
00496                 if (BlockOcc) {
00497                   DEBUG(std::cerr <<"    PHI superceeds occurrence: "<<
00498                         *BlockOcc);
00499                   BlockOcc->replaceAllUsesWith(PN);
00500                   BlockOcc->getParent()->getInstList().erase(BlockOcc);
00501                   ++NumRedundant;
00502                 }
00503                 BlockOcc = PN;
00504               }
00505             }
00506           }
00507         }
00508       }
00509 
00510     } else {
00511       // Otherwise we must be looking at a node in the availability frontier!
00512       unsigned AFBlockID = *AvailabilityFrontier.begin();
00513       AvailabilityFrontier.erase(AvailabilityFrontier.begin());
00514       BasicBlock *AFBlock = BlockMapping[AFBlockID];
00515 
00516       // We eliminate the partial redundancy on this frontier by inserting a PHI
00517       // node into this block, merging any incoming available versions into the
00518       // PHI and inserting a new computation into predecessors without an
00519       // incoming value.  Note that we would have to insert the expression on
00520       // the edge if the predecessor didn't anticipate the expression and we
00521       // didn't break critical edges.
00522       //
00523       PHINode *PN = new PHINode(ExprType, Expr->getName()+".PRE",
00524                                 AFBlock->begin());
00525       DEBUG(std::cerr << "INSERTING PHI for PR: " << *PN);
00526 
00527       // If there is a pending occurrence in this block, make sure to replace it
00528       // with the PHI node...
00529       std::map<unsigned, Instruction*>::iterator EDFI =
00530         Definitions.find(AFBlockID);
00531       if (EDFI != Definitions.end()) {
00532         // There is already an occurrence in this block.  Replace it with PN and
00533         // remove it.
00534         Instruction *OldOcc = EDFI->second;
00535         DEBUG(std::cerr << "  Replaces occurrence: " << *OldOcc);
00536         OldOcc->replaceAllUsesWith(PN);
00537         AFBlock->getInstList().erase(OldOcc);
00538         Definitions.erase(EDFI);
00539         ++NumRedundant;
00540       }
00541 
00542       for (pred_iterator PI = pred_begin(AFBlock), PE = pred_end(AFBlock);
00543            PI != PE; ++PI) {
00544         BasicBlock *Pred = *PI;
00545         AvailableBlocksTy::iterator LBI = AvailableBlocks.find(Pred);
00546         if (LBI != AvailableBlocks.end()) {    // If there is a available value
00547           PN->addIncoming(LBI->second, Pred);  // for this pred, use it.
00548         } else {                         // No available value yet...
00549           unsigned PredID = BlockNumbering[Pred];
00550 
00551           // Is the predecessor the same block that we inserted the PHI into?
00552           // (self loop)
00553           if (Pred == AFBlock) {
00554             // Yes, reuse the incoming value here...
00555             PN->addIncoming(PN, Pred);
00556           } else {
00557             // No, we must insert a new computation into this block and add it
00558             // to the definitions list...
00559             assert(NonPHIOccurrence && "No non-phi occurrences seen so far???");
00560             Instruction *New = NonPHIOccurrence->clone();
00561             New->setName(NonPHIOccurrence->getName() + ".PRE-inserted");
00562             ProcessedExpressions.insert(New);
00563 
00564             DEBUG(std::cerr << "  INSERTING OCCURRRENCE: " << *New);
00565 
00566             // Insert it into the bottom of the predecessor, right before the
00567             // terminator instruction...
00568             Pred->getInstList().insert(Pred->getTerminator(), New);
00569 
00570             // Make this block be the available definition for any blocks it
00571             // dominates.  The ONLY case that this can affect more than just the
00572             // block itself is when we are moving a computation to a loop
00573             // header.  In all other cases, because we don't have critical
00574             // edges, the node is guaranteed to only dominate itself.
00575             //
00576             ReplaceDominatedAvailableOccurrencesWith(New, DT->getNode(Pred));
00577 
00578             // Add it as an incoming value on this edge to the PHI node
00579             PN->addIncoming(New, Pred);
00580             NonPHIOccurrence = New;
00581             NumInserted++;
00582           }
00583         }
00584       }
00585 
00586       // Find out if there is already an available value in this block.  If so,
00587       // we need to replace the available value with the PHI node.  This can
00588       // only happen when we just inserted a PHI node on a backedge.
00589       //
00590       AvailableBlocksTy::iterator LBBlockAvailableValIt =
00591         AvailableBlocks.find(AFBlock);
00592       if (LBBlockAvailableValIt != AvailableBlocks.end()) {
00593         if (LBBlockAvailableValIt->second->getParent() == AFBlock) {
00594           Instruction *OldVal = LBBlockAvailableValIt->second;
00595           OldVal->replaceAllUsesWith(PN);        // Use the new PHI node now
00596           ++NumRedundant;
00597           DEBUG(std::cerr << "  PHI replaces available value: %"
00598                 << OldVal->getName() << "\n");
00599           
00600           // Loop over all of the blocks dominated by this PHI node, and change
00601           // the AvailableBlocks entries to be the PHI node instead of the old
00602           // instruction.
00603           MarkOccurrenceAvailableInAllDominatedBlocks(PN, AFBlock);
00604           
00605           AFBlock->getInstList().erase(OldVal);  // Delete old instruction!
00606 
00607           // The resultant PHI node is a new definition of the value!
00608           Definitions.insert(std::make_pair(AFBlockID, PN));
00609         } else {
00610           // If the value is not defined in this block, that means that an
00611           // inserted occurrence in a predecessor is now the live value for the
00612           // region (occurs when hoisting loop invariants, f.e.).  In this case,
00613           // the PHI node should actually just be removed.
00614           assert(PN->use_empty() && "No uses should exist for dead PHI node!");
00615           PN->getParent()->getInstList().erase(PN);            
00616         }
00617       } else {
00618         // The resultant PHI node is a new definition of the value!
00619         Definitions.insert(std::make_pair(AFBlockID, PN));
00620       }
00621     }
00622   }
00623 
00624   AvailableBlocks.clear();
00625 
00626   return Changed;
00627 }
00628