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