lib/Transforms/Scalar/PRE.cpp

   1 //===- PRE.cpp - Partial Redundancy Elimination ---------------------------===//
   2 //
   3 // This file implements the well-known Partial Redundancy Elimination
   4 // optimization, using an SSA formulation based on e-paths.  See this paper for
   5 // more information:
   6 //
   7 //  E-path_PRE: partial redundancy elimination made easy
   8 //  By: Dhananjay M. Dhamdhere   In: ACM SIGPLAN Notices. Vol 37, #8, 2002
   9 //    http://doi.acm.org/10.1145/596992.597004
  10 //
  11 // This file actually implements a sparse version of the algorithm, using SSA
  12 // and CFG properties instead of bit-vectors.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Pass.h"
  17 #include "llvm/Function.h"
  18 #include "llvm/Type.h"
  19 #include "llvm/iPHINode.h"
  20 #include "llvm/iMemory.h"
  21 #include "llvm/Support/CFG.h"
  22 #include "llvm/Analysis/Dominators.h"
  23 #include "llvm/Analysis/PostDominators.h"
  24 #include "llvm/Analysis/ValueNumbering.h"
  25 #include "llvm/Transforms/Scalar.h"
  26 #include "Support/Debug.h"
  27 #include "Support/DepthFirstIterator.h"
  28 #include "Support/PostOrderIterator.h"
  29 #include "Support/Statistic.h"
  30 #include "Support/hash_set"
  31
  32 namespace {
  33   Statistic<> NumExprsEliminated("pre", "Number of expressions constantified");
  34   Statistic<> NumRedundant      ("pre", "Number of redundant exprs eliminated");
  35   Statistic<> NumInserted       ("pre", "Number of expressions inserted");
  36
  37   struct PRE : public FunctionPass {
  38     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  39       AU.addRequiredID(BreakCriticalEdgesID);  // No critical edges for now!
  40       AU.addRequired<PostDominatorTree>();
  41       AU.addRequired<PostDominanceFrontier>();
  42       AU.addRequired<DominatorSet>();
  43       AU.addRequired<DominatorTree>();
  44       AU.addRequired<DominanceFrontier>();
  45       AU.addRequired<ValueNumbering>();
  46     }
  47     virtual bool runOnFunction(Function &F);
  48
  49   private:
  50     // Block information - Map basic blocks in a function back and forth to
  51     // unsigned integers.
  52     std::vector<BasicBlock*> BlockMapping;
  53     hash_map<BasicBlock*, unsigned> BlockNumbering;
  54
  55     // ProcessedExpressions - Keep track of which expressions have already been
  56     // processed.
  57     hash_set<Instruction*> ProcessedExpressions;
  58
  59     // Provide access to the various analyses used...
  60     DominatorSet      *DS;
  61     DominatorTree     *DT; PostDominatorTree *PDT;
  62     DominanceFrontier *DF; PostDominanceFrontier *PDF;
  63     ValueNumbering    *VN;
  64
  65     // AvailableBlocks - Contain a mapping of blocks with available expression
  66     // values to the expression value itself.  This can be used as an efficient
  67     // way to find out if the expression is available in the block, and if so,
  68     // which version to use.  This map is only used while processing a single
  69     // expression.
  70     //
  71     typedef hash_map<BasicBlock*, Instruction*> AvailableBlocksTy;
  72     AvailableBlocksTy AvailableBlocks;
  73
  74     bool ProcessBlock(BasicBlock *BB);
  75
  76     // Anticipatibility calculation...
  77     void MarkPostDominatingBlocksAnticipatible(PostDominatorTree::Node *N,
  78                                                std::vector<char> &AntBlocks,
  79                                                Instruction *Occurrence);
  80     void CalculateAnticipatiblityForOccurrence(unsigned BlockNo,
  81                                               std::vector<char> &AntBlocks,
  82                                               Instruction *Occurrence);
  83     void CalculateAnticipatibleBlocks(const std::map<unsigned, Instruction*> &D,
  84                                       std::vector<char> &AnticipatibleBlocks);
  85
  86     // PRE for an expression
  87     void MarkOccurrenceAvailableInAllDominatedBlocks(Instruction *Occurrence,
  88                                                      BasicBlock *StartBlock);
  89     void ReplaceDominatedAvailableOccurrencesWith(Instruction *NewOcc,
  90                                                   DominatorTree::Node *N);
  91     bool ProcessExpression(Instruction *I);
  92   };
  93
  94   RegisterOpt<PRE> Z("pre", "Partial Redundancy Elimination");
  95 }
  96
  97
  98 bool PRE::runOnFunction(Function &F) {
  99   VN  = &getAnalysis<ValueNumbering>();
 100   DS  = &getAnalysis<DominatorSet>();
 101   DT  = &getAnalysis<DominatorTree>();
 102   DF  = &getAnalysis<DominanceFrontier>();
 103   PDT = &getAnalysis<PostDominatorTree>();
 104   PDF = &getAnalysis<PostDominanceFrontier>();
 105
 106   DEBUG(std::cerr << "\n*** Running PRE on func '" << F.getName() << "'...\n");
 107
 108   // Number the basic blocks based on a reverse post-order traversal of the CFG
 109   // so that all predecessors of a block (ignoring back edges) are visited
 110   // before a block is visited.
 111   //
 112   BlockMapping.reserve(F.size());
 113   {
 114     ReversePostOrderTraversal<Function*> RPOT(&F);
 115     DEBUG(std::cerr << "Block order: ");
 116     for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
 117            E = RPOT.end(); I != E; ++I) {
 118       // Keep track of mapping...
 119       BasicBlock *BB = *I;
 120       BlockNumbering.insert(std::make_pair(BB, BlockMapping.size()));
 121       BlockMapping.push_back(BB);
 122       DEBUG(std::cerr << BB->getName() << " ");
 123     }
 124     DEBUG(std::cerr << "\n");
 125   }
 126
 127   // Traverse the current function depth-first in dominator-tree order.  This
 128   // ensures that we see all definitions before their uses (except for PHI
 129   // nodes), allowing us to hoist dependent expressions correctly.
 130   bool Changed = false;
 131   for (unsigned i = 0, e = BlockMapping.size(); i != e; ++i)
 132     Changed |= ProcessBlock(BlockMapping[i]);
 133
 134   // Free memory
 135   BlockMapping.clear();
 136   BlockNumbering.clear();
 137   ProcessedExpressions.clear();
 138   return Changed;
 139 }
 140
 141
 142 // ProcessBlock - Process any expressions first seen in this block...
 143 //
 144 bool PRE::ProcessBlock(BasicBlock *BB) {
 145   bool Changed = false;
 146
 147   // PRE expressions first defined in this block...
 148   Instruction *PrevInst = 0;
 149   for (BasicBlock::iterator I = BB->begin(); I != BB->end(); )
 150     if (ProcessExpression(I)) {
 151       // The current instruction may have been deleted, make sure to back up to
 152       // PrevInst instead.
 153       if (PrevInst)
 154         I = PrevInst;
 155       else
 156         I = BB->begin();
 157       Changed = true;
 158     } else {
 159       PrevInst = I++;
 160     }
 161
 162   return Changed;
 163 }
 164
 165 void PRE::MarkPostDominatingBlocksAnticipatible(PostDominatorTree::Node *N,
 166                                                 std::vector<char> &AntBlocks,
 167                                                 Instruction *Occurrence) {
 168   unsigned BlockNo = BlockNumbering[N->getNode()];
 169
 170   if (AntBlocks[BlockNo]) return;  // Already known to be anticipatible??
 171
 172   // Check to see if any of the operands are defined in this block, if so, the
 173   // entry of this block does not anticipate the expression.  This computes
 174   // "transparency".
 175   for (unsigned i = 0, e = Occurrence->getNumOperands(); i != e; ++i)
 176     if (Instruction *I = dyn_cast<Instruction>(Occurrence->getOperand(i)))
 177       if (I->getParent() == N->getNode())  // Operand is defined in this block!
 178         return;
 179
 180   if (isa<LoadInst>(Occurrence))
 181     return;        // FIXME: compute transparency for load instructions using AA
 182
 183   // Insert block into AntBlocks list...
 184   AntBlocks[BlockNo] = true;
 185
 186   for (PostDominatorTree::Node::iterator I = N->begin(), E = N->end(); I != E;
 187        ++I)
 188     MarkPostDominatingBlocksAnticipatible(*I, AntBlocks, Occurrence);
 189 }
 190
 191 void PRE::CalculateAnticipatiblityForOccurrence(unsigned BlockNo,
 192                                                 std::vector<char> &AntBlocks,
 193                                                 Instruction *Occurrence) {
 194   if (AntBlocks[BlockNo]) return;  // Block already anticipatible!
 195
 196   BasicBlock *BB = BlockMapping[BlockNo];
 197
 198   // For each occurrence, mark all post-dominated blocks as anticipatible...
 199   MarkPostDominatingBlocksAnticipatible(PDT->getNode(BB), AntBlocks,
 200                                         Occurrence);
 201
 202   // Next, mark any blocks in the post-dominance frontier as anticipatible iff
 203   // all successors are anticipatible.
 204   //
 205   PostDominanceFrontier::iterator PDFI = PDF->find(BB);
 206   if (PDFI != DF->end())
 207     for (std::set<BasicBlock*>::iterator DI = PDFI->second.begin();
 208          DI != PDFI->second.end(); ++DI) {
 209       BasicBlock *PDFBlock = *DI;
 210       bool AllSuccessorsAnticipatible = true;
 211       for (succ_iterator SI = succ_begin(PDFBlock), SE = succ_end(PDFBlock);
 212            SI != SE; ++SI)
 213         if (!AntBlocks[BlockNumbering[*SI]]) {
 214           AllSuccessorsAnticipatible = false;
 215           break;
 216         }
 217
 218       if (AllSuccessorsAnticipatible)
 219         CalculateAnticipatiblityForOccurrence(BlockNumbering[PDFBlock],
 220                                               AntBlocks, Occurrence);
 221     }
 222 }
 223
 224
 225 void PRE::CalculateAnticipatibleBlocks(const std::map<unsigned,
 226                                                       Instruction*> &Defs,
 227                                        std::vector<char> &AntBlocks) {
 228   // Initialize to zeros...
 229   AntBlocks.resize(BlockMapping.size());
 230
 231   // Loop over all of the expressions...
 232   for (std::map<unsigned, Instruction*>::const_iterator I = Defs.begin(),
 233          E = Defs.end(); I != E; ++I)
 234     CalculateAnticipatiblityForOccurrence(I->first, AntBlocks, I->second);
 235 }
 236
 237 /// MarkOccurrenceAvailableInAllDominatedBlocks - Add entries to AvailableBlocks
 238 /// for all nodes dominated by the occurrence to indicate that it is now the
 239 /// available occurrence to use in any of these blocks.
 240 ///
 241 void PRE::MarkOccurrenceAvailableInAllDominatedBlocks(Instruction *Occurrence,
 242                                                       BasicBlock *BB) {
 243   // FIXME: There are much more efficient ways to get the blocks dominated
 244   // by a block.  Use them.
 245   //
 246   DominatorTree::Node *N = DT->getNode(Occurrence->getParent());
 247   for (df_iterator<DominatorTree::Node*> DI = df_begin(N), E = df_end(N);
 248        DI != E; ++DI)
 249     AvailableBlocks[(*DI)->getNode()] = Occurrence;
 250 }
 251
 252 /// ReplaceDominatedAvailableOccurrencesWith - This loops over the region
 253 /// dominated by N, replacing any available expressions with NewOcc.
 254 void PRE::ReplaceDominatedAvailableOccurrencesWith(Instruction *NewOcc,
 255                                                    DominatorTree::Node *N) {
 256   BasicBlock *BB = N->getNode();
 257   Instruction *&ExistingAvailableVal = AvailableBlocks[BB];
 258
 259   // If there isn't a definition already active in this node, make this the new
 260   // active definition...
 261   if (ExistingAvailableVal == 0) {
 262     ExistingAvailableVal = NewOcc;
 263
 264     for (DominatorTree::Node::iterator I = N->begin(), E = N->end(); I != E;++I)
 265       ReplaceDominatedAvailableOccurrencesWith(NewOcc, *I);
 266   } else {
 267     // If there is already an active definition in this block, replace it with
 268     // NewOcc, and force it into all dominated blocks.
 269     DEBUG(std::cerr << "  Replacing dominated occ %"
 270           << ExistingAvailableVal->getName() << " with %" << NewOcc->getName()
 271           << "\n");
 272     assert(ExistingAvailableVal != NewOcc && "NewOcc already inserted??");
 273     ExistingAvailableVal->replaceAllUsesWith(NewOcc);
 274     ++NumRedundant;
 275
 276     assert(ExistingAvailableVal->getParent() == BB &&
 277            "OldOcc not defined in current block?");
 278     BB->getInstList().erase(ExistingAvailableVal);
 279
 280     // Mark NewOCC as the Available expression in all blocks dominated by BB
 281     for (df_iterator<DominatorTree::Node*> DI = df_begin(N), E = df_end(N);
 282          DI != E; ++DI)
 283       AvailableBlocks[(*DI)->getNode()] = NewOcc;
 284   }
 285 }
 286
 287
 288 /// ProcessExpression - Given an expression (instruction) process the
 289 /// instruction to remove any partial redundancies induced by equivalent
 290 /// computations.  Note that we only need to PRE each expression once, so we
 291 /// keep track of whether an expression has been PRE'd already, and don't PRE an
 292 /// expression again.  Expressions may be seen multiple times because process
 293 /// the entire equivalence class at once, which may leave expressions later in
 294 /// the control path.
 295 ///
 296 bool PRE::ProcessExpression(Instruction *Expr) {
 297   if (Expr->mayWriteToMemory() || Expr->getType() == Type::VoidTy ||
 298       isa<PHINode>(Expr))
 299     return false;         // Cannot move expression
 300   if (ProcessedExpressions.count(Expr)) return false; // Already processed.
 301
 302   // Ok, this is the first time we have seen the expression.  Build a set of
 303   // equivalent expressions using SSA def/use information.  We consider
 304   // expressions to be equivalent if they are the same opcode and have
 305   // equivalent operands.  As a special case for SSA, values produced by PHI
 306   // nodes are considered to be equivalent to all of their operands.
 307   //
 308   std::vector<Value*> Values;
 309   VN->getEqualNumberNodes(Expr, Values);
 310
 311 #if 0
 312   // FIXME: This should handle PHI nodes correctly.  To do this, we need to
 313   // consider expressions of the following form equivalent to this set of
 314   // expressions:
 315   //
 316   // If an operand is a PHI node, add any occurrences of the expression with the
 317   // PHI operand replaced with the PHI node operands.  This is only valid if the
 318   // PHI operand occurrences exist in blocks post-dominated by the incoming edge
 319   // of the PHI node.
 320 #endif
 321
 322   // We have to be careful to handle expression definitions which dominated by
 323   // other expressions.  These can be directly eliminated in favor of their
 324   // dominating value.  Keep track of which blocks contain definitions (the key)
 325   // and if a block contains a definition, which instruction it is.
 326   //
 327   std::map<unsigned, Instruction*> Definitions;
 328   Definitions.insert(std::make_pair(BlockNumbering[Expr->getParent()], Expr));
 329
 330   bool Changed = false;
 331
 332   // Look at all of the equal values.  If any of the values is not an
 333   // instruction, replace all other expressions immediately with it (it must be
 334   // an argument or a constant or something). Otherwise, convert the list of
 335   // values into a list of expression (instruction) definitions ordering
 336   // according to their dominator tree ordering.
 337   //
 338   Value *NonInstValue = 0;
 339   for (unsigned i = 0, e = Values.size(); i != e; ++i)
 340     if (Instruction *I = dyn_cast<Instruction>(Values[i])) {
 341       Instruction *&BlockInst = Definitions[BlockNumbering[I->getParent()]];
 342       if (BlockInst && BlockInst != I) {    // Eliminate direct redundancy
 343         if (DS->dominates(I, BlockInst)) {  // I dom BlockInst
 344           BlockInst->replaceAllUsesWith(I);
 345           BlockInst->getParent()->getInstList().erase(BlockInst);
 346         } else {                            // BlockInst dom I
 347           I->replaceAllUsesWith(BlockInst);
 348           I->getParent()->getInstList().erase(I);
 349           I = BlockInst;
 350         }
 351         ++NumRedundant;
 352       }
 353       BlockInst = I;
 354     } else {
 355       NonInstValue = Values[i];
 356     }
 357
 358   std::vector<Value*>().swap(Values);  // Done with the values list
 359
 360   if (NonInstValue) {
 361     // This is the good, though unlikely, case where we find out that this
 362     // expression is equal to a constant or argument directly.  We can replace
 363     // this and all of the other equivalent instructions with the value
 364     // directly.
 365     //
 366     for (std::map<unsigned, Instruction*>::iterator I = Definitions.begin(),
 367            E = Definitions.end(); I != E; ++I) {
 368       Instruction *Inst = I->second;
 369       // Replace the value with the specified non-instruction value.
 370       Inst->replaceAllUsesWith(NonInstValue);       // Fixup any uses
 371       Inst->getParent()->getInstList().erase(Inst); // Erase the instruction
 372     }
 373     NumExprsEliminated += Definitions.size();
 374     return true;   // Program modified!
 375   }
 376
 377   // There are no expressions equal to this one.  Exit early.
 378   assert(!Definitions.empty() && "no equal expressions??");
 379 #if 0
 380   if (Definitions.size() == 1) {
 381     ProcessedExpressions.insert(Definitions.begin()->second);
 382     return Changed;
 383   }
 384 #endif
 385   DEBUG(std::cerr << "\n====--- Expression: " << Expr);
 386   const Type *ExprType = Expr->getType();
 387
 388   // AnticipatibleBlocks - Blocks where the current expression is anticipatible.
 389   // This is logically std::vector<bool> but using 'char' for performance.
 390   std::vector<char> AnticipatibleBlocks;
 391
 392   // Calculate all of the blocks which the current expression is anticipatible.
 393   CalculateAnticipatibleBlocks(Definitions, AnticipatibleBlocks);
 394
 395   // Print out anticipatible blocks...
 396   DEBUG(std::cerr << "AntBlocks: ";
 397         for (unsigned i = 0, e = AnticipatibleBlocks.size(); i != e; ++i)
 398           if (AnticipatibleBlocks[i])
 399             std::cerr << BlockMapping[i]->getName() <<" ";
 400         std::cerr << "\n";);
 401
 402
 403
 404   // AvailabilityFrontier - Calculates the availability frontier for the current
 405   // expression.  The availability frontier contains the blocks on the dominance
 406   // frontier of the current available expressions, iff they anticipate a
 407   // definition of the expression.
 408   hash_set<unsigned> AvailabilityFrontier;
 409
 410   Instruction *NonPHIOccurrence = 0;
 411
 412   while (!Definitions.empty() || !AvailabilityFrontier.empty()) {
 413     if (!Definitions.empty() &&
 414         (AvailabilityFrontier.empty() ||
 415          Definitions.begin()->first < *AvailabilityFrontier.begin())) {
 416       Instruction *Occurrence = Definitions.begin()->second;
 417       BasicBlock *BB = Occurrence->getParent();
 418       Definitions.erase(Definitions.begin());
 419
 420       DEBUG(std::cerr << "PROCESSING Occurrence: " << Occurrence);
 421
 422       // Check to see if there is already an incoming value for this block...
 423       AvailableBlocksTy::iterator LBI = AvailableBlocks.find(BB);
 424       if (LBI != AvailableBlocks.end()) {
 425         // Yes, there is a dominating definition for this block.  Replace this
 426         // occurrence with the incoming value.
 427         if (LBI->second != Occurrence) {
 428           DEBUG(std::cerr << "  replacing with: " << LBI->second);
 429           Occurrence->replaceAllUsesWith(LBI->second);
 430           BB->getInstList().erase(Occurrence);   // Delete instruction
 431           ++NumRedundant;
 432         }
 433       } else {
 434         ProcessedExpressions.insert(Occurrence);
 435         if (!isa<PHINode>(Occurrence))
 436           NonPHIOccurrence = Occurrence;  // Keep an occurrence of this expr
 437
 438         // Okay, there is no incoming value for this block, so this expression
 439         // is a new definition that is good for this block and all blocks
 440         // dominated by it.  Add this information to the AvailableBlocks map.
 441         //
 442         MarkOccurrenceAvailableInAllDominatedBlocks(Occurrence, BB);
 443
 444         // Update the dominance frontier for the definitions so far... if a node
 445         // in the dominator frontier now has all of its predecessors available,
 446         // and the block is in an anticipatible region, we can insert a PHI node
 447         // in that block.
 448         DominanceFrontier::iterator DFI = DF->find(BB);
 449         if (DFI != DF->end()) {
 450           for (std::set<BasicBlock*>::iterator DI = DFI->second.begin();
 451                DI != DFI->second.end(); ++DI) {
 452             BasicBlock *DFBlock = *DI;
 453             unsigned DFBlockID = BlockNumbering[DFBlock];
 454             if (AnticipatibleBlocks[DFBlockID]) {
 455               // Check to see if any of the predecessors of this block on the
 456               // frontier are not available...
 457               bool AnyNotAvailable = false;
 458               for (pred_iterator PI = pred_begin(DFBlock),
 459                      PE = pred_end(DFBlock); PI != PE; ++PI)
 460                 if (!AvailableBlocks.count(*PI)) {
 461                   AnyNotAvailable = true;
 462                   break;
 463                 }
 464
 465               // If any predecessor blocks are not available, add the node to
 466               // the current expression dominance frontier.
 467               if (AnyNotAvailable) {
 468                 AvailabilityFrontier.insert(DFBlockID);
 469               } else {
 470                 // This block is no longer in the availability frontier, it IS
 471                 // available.
 472                 AvailabilityFrontier.erase(DFBlockID);
 473
 474                 // If all of the predecessor blocks are available (and the block
 475                 // anticipates a definition along the path to the exit), we need
 476                 // to insert a new PHI node in this block.  This block serves as
 477                 // a new definition for the expression, extending the available
 478                 // region.
 479                 //
 480                 PHINode *PN = new PHINode(ExprType, Expr->getName()+".pre",
 481                                           DFBlock->begin());
 482                 ProcessedExpressions.insert(PN);
 483
 484                 DEBUG(std::cerr << "  INSERTING PHI on frontier: " << PN);
 485
 486                 // Add the incoming blocks for the PHI node
 487                 for (pred_iterator PI = pred_begin(DFBlock),
 488                        PE = pred_end(DFBlock); PI != PE; ++PI)
 489                   if (*PI != DFBlock)
 490                     PN->addIncoming(AvailableBlocks[*PI], *PI);
 491                   else                          // edge from the current block
 492                     PN->addIncoming(PN, DFBlock);
 493
 494                 Instruction *&BlockOcc = Definitions[DFBlockID];
 495                 if (BlockOcc) {
 496                   DEBUG(std::cerr <<"    PHI superceeds occurrence: "<<BlockOcc);
 497                   BlockOcc->replaceAllUsesWith(PN);
 498                   BlockOcc->getParent()->getInstList().erase(BlockOcc);
 499                   ++NumRedundant;
 500                 }
 501                 BlockOcc = PN;
 502               }
 503             }
 504           }
 505         }
 506       }
 507
 508     } else {
 509       // Otherwise we must be looking at a node in the availability frontier!
 510       unsigned AFBlockID = *AvailabilityFrontier.begin();
 511       AvailabilityFrontier.erase(AvailabilityFrontier.begin());
 512       BasicBlock *AFBlock = BlockMapping[AFBlockID];
 513
 514       // We eliminate the partial redundancy on this frontier by inserting a PHI
 515       // node into this block, merging any incoming available versions into the
 516       // PHI and inserting a new computation into predecessors without an
 517       // incoming value.  Note that we would have to insert the expression on
 518       // the edge if the predecessor didn't anticipate the expression and we
 519       // didn't break critical edges.
 520       //
 521       PHINode *PN = new PHINode(ExprType, Expr->getName()+".PRE",
 522                                 AFBlock->begin());
 523       DEBUG(std::cerr << "INSERTING PHI for PR: " << PN);
 524
 525       // If there is a pending occurrence in this block, make sure to replace it
 526       // with the PHI node...
 527       std::map<unsigned, Instruction*>::iterator EDFI =
 528         Definitions.find(AFBlockID);
 529       if (EDFI != Definitions.end()) {
 530         // There is already an occurrence in this block.  Replace it with PN and
 531         // remove it.
 532         Instruction *OldOcc = EDFI->second;
 533         DEBUG(std::cerr << "  Replaces occurrence: " << OldOcc);
 534         OldOcc->replaceAllUsesWith(PN);
 535         AFBlock->getInstList().erase(OldOcc);
 536         Definitions.erase(EDFI);
 537         ++NumRedundant;
 538       }
 539
 540       for (pred_iterator PI = pred_begin(AFBlock), PE = pred_end(AFBlock);
 541            PI != PE; ++PI) {
 542         BasicBlock *Pred = *PI;
 543         AvailableBlocksTy::iterator LBI = AvailableBlocks.find(Pred);
 544         if (LBI != AvailableBlocks.end()) {    // If there is a available value
 545           PN->addIncoming(LBI->second, Pred);  // for this pred, use it.
 546         } else {                         // No available value yet...
 547           unsigned PredID = BlockNumbering[Pred];
 548
 549           // Is the predecessor the same block that we inserted the PHI into?
 550           // (self loop)
 551           if (Pred == AFBlock) {
 552             // Yes, reuse the incoming value here...
 553             PN->addIncoming(PN, Pred);
 554           } else {
 555             // No, we must insert a new computation into this block and add it
 556             // to the definitions list...
 557             assert(NonPHIOccurrence && "No non-phi occurrences seen so far???");
 558             Instruction *New = NonPHIOccurrence->clone();
 559             New->setName(NonPHIOccurrence->getName() + ".PRE-inserted");
 560             ProcessedExpressions.insert(New);
 561
 562             DEBUG(std::cerr << "  INSERTING OCCURRRENCE: " << New);
 563
 564             // Insert it into the bottom of the predecessor, right before the
 565             // terminator instruction...
 566             Pred->getInstList().insert(Pred->getTerminator(), New);
 567
 568             // Make this block be the available definition for any blocks it
 569             // dominates.  The ONLY case that this can affect more than just the
 570             // block itself is when we are moving a computation to a loop
 571             // header.  In all other cases, because we don't have critical
 572             // edges, the node is guaranteed to only dominate itself.
 573             //
 574             ReplaceDominatedAvailableOccurrencesWith(New, DT->getNode(Pred));
 575
 576             // Add it as an incoming value on this edge to the PHI node
 577             PN->addIncoming(New, Pred);
 578             NonPHIOccurrence = New;
 579             NumInserted++;
 580           }
 581         }
 582       }
 583
 584       // Find out if there is already an available value in this block.  If so,
 585       // we need to replace the available value with the PHI node.  This can
 586       // only happen when we just inserted a PHI node on a backedge.
 587       //
 588       AvailableBlocksTy::iterator LBBlockAvailableValIt =
 589         AvailableBlocks.find(AFBlock);
 590       if (LBBlockAvailableValIt != AvailableBlocks.end()) {
 591         if (LBBlockAvailableValIt->second->getParent() == AFBlock) {
 592           Instruction *OldVal = LBBlockAvailableValIt->second;
 593           OldVal->replaceAllUsesWith(PN);        // Use the new PHI node now
 594           ++NumRedundant;
 595           DEBUG(std::cerr << "  PHI replaces available value: %"
 596                 << OldVal->getName() << "\n");
 597
 598           // Loop over all of the blocks dominated by this PHI node, and change
 599           // the AvailableBlocks entries to be the PHI node instead of the old
 600           // instruction.
 601           MarkOccurrenceAvailableInAllDominatedBlocks(PN, AFBlock);
 602
 603           AFBlock->getInstList().erase(OldVal);  // Delete old instruction!
 604
 605           // The resultant PHI node is a new definition of the value!
 606           Definitions.insert(std::make_pair(AFBlockID, PN));
 607         } else {
 608           // If the value is not defined in this block, that means that an
 609           // inserted occurrence in a predecessor is now the live value for the
 610           // region (occurs when hoisting loop invariants, f.e.).  In this case,
 611           // the PHI node should actually just be removed.
 612           assert(PN->use_empty() && "No uses should exist for dead PHI node!");
 613           PN->getParent()->getInstList().erase(PN);
 614         }
 615       } else {
 616         // The resultant PHI node is a new definition of the value!
 617         Definitions.insert(std::make_pair(AFBlockID, PN));
 618       }
 619     }
 620   }
 621
 622   AvailableBlocks.clear();
 623
 624   return Changed;
 625 }