lib/Transforms/Scalar/GVNPRE.cpp

   1 //===- GVNPRE.cpp - Eliminate redundant values and expressions ------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the Owen Anderson and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass performs a hybrid of global value numbering and partial redundancy
  11 // elimination, known as GVN-PRE.  It performs partial redundancy elimination on
  12 // values, rather than lexical expressions, allowing a more comprehensive view
  13 // the optimization.  It replaces redundant values with uses of earlier
  14 // occurences of the same value.  While this is beneficial in that it eliminates
  15 // unneeded computation, it also increases register pressure by creating large
  16 // live ranges, and should be used with caution on platforms that a very
  17 // sensitive to register pressure.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #define DEBUG_TYPE "gvnpre"
  22 #include "llvm/Value.h"
  23 #include "llvm/Transforms/Scalar.h"
  24 #include "llvm/Instructions.h"
  25 #include "llvm/Function.h"
  26 #include "llvm/Analysis/Dominators.h"
  27 #include "llvm/Analysis/PostDominators.h"
  28 #include "llvm/ADT/DepthFirstIterator.h"
  29 #include "llvm/ADT/Statistic.h"
  30 #include "llvm/Support/CFG.h"
  31 #include "llvm/Support/Compiler.h"
  32 #include "llvm/Support/Debug.h"
  33 #include <algorithm>
  34 #include <deque>
  35 #include <map>
  36 #include <vector>
  37 #include <set>
  38 using namespace llvm;
  39
  40 struct ExprLT {
  41   bool operator()(Value* left, Value* right) {
  42     if (!isa<BinaryOperator>(left) || !isa<BinaryOperator>(right))
  43       return left < right;
  44
  45     BinaryOperator* BO1 = cast<BinaryOperator>(left);
  46     BinaryOperator* BO2 = cast<BinaryOperator>(right);
  47
  48     if ((*this)(BO1->getOperand(0), BO2->getOperand(0)))
  49       return true;
  50     else if ((*this)(BO2->getOperand(0), BO1->getOperand(0)))
  51       return false;
  52     else
  53       return (*this)(BO1->getOperand(1), BO2->getOperand(1));
  54   }
  55 };
  56
  57 namespace {
  58
  59   class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
  60     bool runOnFunction(Function &F);
  61   public:
  62     static char ID; // Pass identification, replacement for typeid
  63     GVNPRE() : FunctionPass((intptr_t)&ID) { nextValueNumber = 0; }
  64
  65   private:
  66     uint32_t nextValueNumber;
  67     typedef std::map<Value*, uint32_t, ExprLT> ValueTable;
  68     ValueTable VN;
  69     std::set<Value*, ExprLT> MS;
  70     std::set<Instruction*> createdExpressions;
  71
  72     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  73       AU.setPreservesCFG();
  74       AU.addRequired<DominatorTree>();
  75       AU.addRequired<PostDominatorTree>();
  76     }
  77
  78     // Helper fuctions
  79     // FIXME: eliminate or document these better
  80     void dump(std::set<Value*>& s);
  81     void dump_unique(std::set<Value*, ExprLT>& s);
  82     void clean(std::set<Value*, ExprLT>& set);
  83     bool add(Value* V, uint32_t number);
  84     Value* find_leader(std::set<Value*, ExprLT>& vals,
  85                        Value* v);
  86     Value* phi_translate(std::set<Value*, ExprLT>& set,
  87                          Value* V, BasicBlock* pred);
  88     void phi_translate_set(std::set<Value*, ExprLT>& anticIn, BasicBlock* B,
  89                        std::set<Value*, ExprLT>& out);
  90
  91     void topo_sort(std::set<Value*, ExprLT>& set,
  92                    std::vector<Value*>& vec);
  93
  94     // For a given block, calculate the generated expressions, temporaries,
  95     // and the AVAIL_OUT set
  96     void CalculateAvailOut(DomTreeNode* DI,
  97                        std::set<Value*, ExprLT>& currExps,
  98                        std::set<PHINode*>& currPhis,
  99                        std::set<Value*>& currTemps,
 100                        std::set<Value*, ExprLT>& currAvail,
 101                        std::map<BasicBlock*, std::set<Value*, ExprLT> > availOut);
 102
 103   };
 104
 105   char GVNPRE::ID = 0;
 106
 107 }
 108
 109 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
 110
 111 RegisterPass<GVNPRE> X("gvnpre",
 112                        "Global Value Numbering/Partial Redundancy Elimination");
 113
 114
 115
 116 bool GVNPRE::add(Value* V, uint32_t number) {
 117   std::pair<ValueTable::iterator, bool> ret = VN.insert(std::make_pair(V, number));
 118   if (isa<BinaryOperator>(V) || isa<PHINode>(V))
 119     MS.insert(V);
 120   return ret.second;
 121 }
 122
 123 Value* GVNPRE::find_leader(std::set<Value*, ExprLT>& vals, Value* v) {
 124   for (std::set<Value*, ExprLT>::iterator I = vals.begin(), E = vals.end();
 125        I != E; ++I) {
 126     assert(VN.find(v) != VN.end() && "Value not numbered?");
 127     assert(VN.find(*I) != VN.end() && "Value not numbered?");
 128     if (VN[v] == VN[*I])
 129       return *I;
 130   }
 131
 132   return 0;
 133 }
 134
 135 Value* GVNPRE::phi_translate(std::set<Value*, ExprLT>& set,
 136                              Value* V, BasicBlock* pred) {
 137   if (V == 0)
 138     return 0;
 139
 140   if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
 141     Value* newOp1 = isa<Instruction>(BO->getOperand(0))
 142                                 ? phi_translate(set,
 143                                   find_leader(set, BO->getOperand(0)),
 144                                   pred)
 145                                 : BO->getOperand(0);
 146     if (newOp1 == 0)
 147       return 0;
 148
 149     Value* newOp2 = isa<Instruction>(BO->getOperand(1))
 150                                 ? phi_translate(set,
 151                                   find_leader(set, BO->getOperand(1)),
 152                                   pred)
 153                                 : BO->getOperand(1);
 154     if (newOp2 == 0)
 155       return 0;
 156
 157     if (newOp1 != BO->getOperand(0) || newOp2 != BO->getOperand(1)) {
 158       Instruction* newVal = BinaryOperator::create(BO->getOpcode(),
 159                                              newOp1, newOp2,
 160                                              BO->getName()+".gvnpre");
 161       if (add(newVal, nextValueNumber))
 162         nextValueNumber++;
 163       if (!find_leader(set, newVal)) {
 164         DOUT << "Creating value: " << std::hex << newVal << std::dec << "\n";
 165         createdExpressions.insert(newVal);
 166         return newVal;
 167       } else {
 168         delete newVal;
 169         return 0;
 170       }
 171     }
 172   } else if (PHINode* P = dyn_cast<PHINode>(V)) {
 173     if (P->getParent() == pred->getTerminator()->getSuccessor(0))
 174       return P->getIncomingValueForBlock(pred);
 175   }
 176
 177   return V;
 178 }
 179
 180 void GVNPRE::phi_translate_set(std::set<Value*, ExprLT>& anticIn, BasicBlock* B,
 181                            std::set<Value*, ExprLT>& out) {
 182   for (std::set<Value*, ExprLT>::iterator I = anticIn.begin(),
 183        E = anticIn.end(); I != E; ++I) {
 184     Value* V = phi_translate(anticIn, *I, B);
 185     if (V != 0)
 186       out.insert(V);
 187   }
 188 }
 189
 190 // Remove all expressions whose operands are not themselves in the set
 191 void GVNPRE::clean(std::set<Value*, ExprLT>& set) {
 192   std::vector<Value*> worklist;
 193   topo_sort(set, worklist);
 194
 195   for (unsigned i = 0; i < worklist.size(); ++i) {
 196     Value* v = worklist[i];
 197
 198     if (BinaryOperator* BO = dyn_cast<BinaryOperator>(v)) {
 199       bool lhsValid = !isa<Instruction>(BO->getOperand(0));
 200       if (!lhsValid)
 201         for (std::set<Value*, ExprLT>::iterator I = set.begin(), E = set.end();
 202              I != E; ++I)
 203           if (VN[*I] == VN[BO->getOperand(0)]) {
 204             lhsValid = true;
 205             break;
 206           }
 207
 208       bool rhsValid = !isa<Instruction>(BO->getOperand(1));
 209       if (!rhsValid)
 210       for (std::set<Value*, ExprLT>::iterator I = set.begin(), E = set.end();
 211            I != E; ++I)
 212         if (VN[*I] == VN[BO->getOperand(1)]) {
 213           rhsValid = true;
 214           break;
 215         }
 216
 217       if (!lhsValid || !rhsValid)
 218         set.erase(BO);
 219     }
 220   }
 221 }
 222
 223 void GVNPRE::topo_sort(std::set<Value*, ExprLT>& set,
 224                        std::vector<Value*>& vec) {
 225   std::set<Value*, ExprLT> toErase;
 226   for (std::set<Value*, ExprLT>::iterator I = set.begin(), E = set.end();
 227        I != E; ++I) {
 228     if (BinaryOperator* BO = dyn_cast<BinaryOperator>(*I))
 229       for (std::set<Value*, ExprLT>::iterator SI = set.begin(); SI != E; ++SI) {
 230         if (VN[BO->getOperand(0)] == VN[*SI] ||
 231             VN[BO->getOperand(1)] == VN[*SI]) {
 232           toErase.insert(*SI);
 233         }
 234     }
 235   }
 236
 237   std::vector<Value*> Q;
 238   for (std::set<Value*, ExprLT>::iterator I = set.begin(), E = set.end();
 239        I != E; ++I) {
 240     if (toErase.find(*I) == toErase.end())
 241       Q.push_back(*I);
 242   }
 243
 244   std::set<Value*> visited;
 245   while (!Q.empty()) {
 246     Value* e = Q.back();
 247
 248     if (BinaryOperator* BO = dyn_cast<BinaryOperator>(e)) {
 249       Value* l = find_leader(set, BO->getOperand(0));
 250       Value* r = find_leader(set, BO->getOperand(1));
 251
 252       if (l != 0 && isa<Instruction>(l) &&
 253           visited.find(l) == visited.end())
 254         Q.push_back(l);
 255       else if (r != 0 && isa<Instruction>(r) &&
 256                visited.find(r) == visited.end())
 257         Q.push_back(r);
 258       else {
 259         vec.push_back(e);
 260         visited.insert(e);
 261         Q.pop_back();
 262       }
 263     } else {
 264       visited.insert(e);
 265       vec.push_back(e);
 266       Q.pop_back();
 267     }
 268   }
 269 }
 270
 271
 272 void GVNPRE::dump(std::set<Value*>& s) {
 273   DOUT << "{ ";
 274   for (std::set<Value*>::iterator I = s.begin(), E = s.end();
 275        I != E; ++I) {
 276     DEBUG((*I)->dump());
 277   }
 278   DOUT << "}\n\n";
 279 }
 280
 281 void GVNPRE::dump_unique(std::set<Value*, ExprLT>& s) {
 282   DOUT << "{ ";
 283   for (std::set<Value*>::iterator I = s.begin(), E = s.end();
 284        I != E; ++I) {
 285     DEBUG((*I)->dump());
 286   }
 287   DOUT << "}\n\n";
 288 }
 289
 290 void GVNPRE::CalculateAvailOut(DomTreeNode* DI,
 291                        std::set<Value*, ExprLT>& currExps,
 292                        std::set<PHINode*>& currPhis,
 293                        std::set<Value*>& currTemps,
 294                        std::set<Value*, ExprLT>& currAvail,
 295                        std::map<BasicBlock*, std::set<Value*, ExprLT> > availOut) {
 296
 297   BasicBlock* BB = DI->getBlock();
 298
 299   // A block inherits AVAIL_OUT from its dominator
 300   if (DI->getIDom() != 0)
 301   currAvail.insert(availOut[DI->getIDom()->getBlock()].begin(),
 302                    availOut[DI->getIDom()->getBlock()].end());
 303
 304
 305  for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
 306       BI != BE; ++BI) {
 307
 308     // Handle PHI nodes...
 309     if (PHINode* p = dyn_cast<PHINode>(BI)) {
 310       if (add(p, nextValueNumber))
 311         nextValueNumber++;
 312       currPhis.insert(p);
 313
 314     // Handle binary ops...
 315     } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(BI)) {
 316       Value* leftValue = BO->getOperand(0);
 317       Value* rightValue = BO->getOperand(1);
 318
 319       if (add(BO, nextValueNumber))
 320         nextValueNumber++;
 321
 322       if (isa<Instruction>(leftValue))
 323         currExps.insert(leftValue);
 324       if (isa<Instruction>(rightValue))
 325         currExps.insert(rightValue);
 326       currExps.insert(BO);
 327
 328     // Handle unsupported ops
 329     } else if (!BI->isTerminator()){
 330       if (add(BI, nextValueNumber))
 331         nextValueNumber++;
 332       currTemps.insert(BI);
 333     }
 334
 335     if (!BI->isTerminator())
 336       currAvail.insert(BI);
 337   }
 338 }
 339
 340 bool GVNPRE::runOnFunction(Function &F) {
 341   VN.clear();
 342   MS.clear();
 343   createdExpressions.clear();
 344
 345   std::map<BasicBlock*, std::set<Value*, ExprLT> > generatedExpressions;
 346   std::map<BasicBlock*, std::set<PHINode*> > generatedPhis;
 347   std::map<BasicBlock*, std::set<Value*> > generatedTemporaries;
 348   std::map<BasicBlock*, std::set<Value*, ExprLT> > availableOut;
 349   std::map<BasicBlock*, std::set<Value*, ExprLT> > anticipatedIn;
 350
 351   DominatorTree &DT = getAnalysis<DominatorTree>();
 352
 353   // Phase 1: BuildSets
 354
 355   // Phase 1, Part 1: calculate AVAIL_OUT
 356
 357   // Top-down walk of the dominator tree
 358   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
 359          E = df_end(DT.getRootNode()); DI != E; ++DI) {
 360
 361     // Get the sets to update for this block
 362     std::set<Value*, ExprLT>& currExps = generatedExpressions[DI->getBlock()];
 363     std::set<PHINode*>& currPhis = generatedPhis[DI->getBlock()];
 364     std::set<Value*>& currTemps = generatedTemporaries[DI->getBlock()];
 365     std::set<Value*, ExprLT>& currAvail = availableOut[DI->getBlock()];
 366
 367     CalculateAvailOut(*DI, currExps, currPhis,
 368                       currTemps, currAvail, availableOut);
 369   }
 370
 371   DOUT << "Maximal Set: ";
 372   dump_unique(MS);
 373   DOUT << "\n";
 374
 375   PostDominatorTree &PDT = getAnalysis<PostDominatorTree>();
 376
 377   // Phase 1, Part 2: calculate ANTIC_IN
 378
 379   std::set<BasicBlock*> visited;
 380
 381   bool changed = true;
 382   unsigned iterations = 0;
 383   while (changed) {
 384     changed = false;
 385     std::set<Value*, ExprLT> anticOut;
 386
 387     // Top-down walk of the postdominator tree
 388     for (df_iterator<DomTreeNode*> PDI =
 389          df_begin(PDT.getRootNode()), E = df_end(PDT.getRootNode());
 390          PDI != E; ++PDI) {
 391       BasicBlock* BB = PDI->getBlock();
 392       DOUT << "Block: " << BB->getName() << "\n";
 393       DOUT << "TMP_GEN: ";
 394       dump(generatedTemporaries[BB]);
 395       DOUT << "\n";
 396
 397       DOUT << "EXP_GEN: ";
 398       dump_unique(generatedExpressions[BB]);
 399       visited.insert(BB);
 400
 401       std::set<Value*, ExprLT>& anticIn = anticipatedIn[BB];
 402       std::set<Value*, ExprLT> old (anticIn.begin(), anticIn.end());
 403
 404       if (BB->getTerminator()->getNumSuccessors() == 1) {
 405          if (visited.find(BB->getTerminator()->getSuccessor(0)) ==
 406              visited.end())
 407            phi_translate_set(MS, BB, anticOut);
 408          else
 409            phi_translate_set(
 410              anticipatedIn[BB->getTerminator()->getSuccessor(0)], BB, anticOut);
 411       } else if (BB->getTerminator()->getNumSuccessors() > 1) {
 412         BasicBlock* first = BB->getTerminator()->getSuccessor(0);
 413         anticOut.insert(anticipatedIn[first].begin(),
 414                         anticipatedIn[first].end());
 415         for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
 416           BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
 417           std::set<Value*, ExprLT>& succAnticIn = anticipatedIn[currSucc];
 418
 419           std::set<Value*, ExprLT> temp;
 420           std::insert_iterator<std::set<Value*, ExprLT> >  temp_ins(temp,
 421                                                                   temp.begin());
 422           std::set_intersection(anticOut.begin(), anticOut.end(),
 423                                 succAnticIn.begin(), succAnticIn.end(),
 424                                 temp_ins, ExprLT());
 425
 426           anticOut.clear();
 427           anticOut.insert(temp.begin(), temp.end());
 428         }
 429       }
 430
 431       DOUT << "ANTIC_OUT: ";
 432       dump_unique(anticOut);
 433       DOUT << "\n";
 434
 435       std::set<Value*, ExprLT> S;
 436       std::insert_iterator<std::set<Value*, ExprLT> >  s_ins(S, S.begin());
 437       std::set_union(anticOut.begin(), anticOut.end(),
 438                      generatedExpressions[BB].begin(),
 439                      generatedExpressions[BB].end(),
 440                      s_ins, ExprLT());
 441
 442       anticIn.clear();
 443
 444       for (std::set<Value*, ExprLT>::iterator I = S.begin(), E = S.end();
 445            I != E; ++I) {
 446         if (generatedTemporaries[BB].find(*I) == generatedTemporaries[BB].end())
 447           anticIn.insert(*I);
 448       }
 449
 450       clean(anticIn);
 451
 452       DOUT << "ANTIC_IN: ";
 453       dump_unique(anticIn);
 454       DOUT << "\n";
 455
 456       if (old.size() != anticIn.size())
 457         changed = true;
 458
 459       anticOut.clear();
 460     }
 461
 462     iterations++;
 463   }
 464
 465   DOUT << "Iterations: " << iterations << "\n";
 466
 467   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
 468     DOUT << "Name: " << I->getName().c_str() << "\n";
 469
 470     DOUT << "TMP_GEN: ";
 471     dump(generatedTemporaries[I]);
 472     DOUT << "\n";
 473
 474     DOUT << "EXP_GEN: ";
 475     dump_unique(generatedExpressions[I]);
 476     DOUT << "\n";
 477
 478     DOUT << "ANTIC_IN: ";
 479     dump_unique(anticipatedIn[I]);
 480     DOUT << "\n";
 481
 482     DOUT << "AVAIL_OUT: ";
 483     dump_unique(availableOut[I]);
 484     DOUT << "\n";
 485   }
 486
 487
 488   // Phase 2: Insert
 489
 490   DOUT<< "\nPhase 2: Insertion\n";
 491
 492   std::map<BasicBlock*, std::set<Value*, ExprLT> > new_sets;
 493   unsigned i_iterations = 0;
 494   bool new_stuff = true;
 495   while (new_stuff) {
 496     new_stuff = false;
 497     DOUT << "Iteration: " << i_iterations << "\n\n";
 498     for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
 499          E = df_end(DT.getRootNode()); DI != E; ++DI) {
 500       BasicBlock* BB = DI->getBlock();
 501
 502       std::set<Value*, ExprLT>& new_set = new_sets[BB];
 503       std::set<Value*, ExprLT>& availOut = availableOut[BB];
 504       std::set<Value*, ExprLT>& anticIn = anticipatedIn[BB];
 505
 506       // Replace leaders with leaders inherited from dominator
 507       if (DI->getIDom() != 0) {
 508         std::set<Value*, ExprLT>& dom_set = new_sets[DI->getIDom()->getBlock()];
 509         for (std::set<Value*, ExprLT>::iterator I = dom_set.begin(),
 510              E = dom_set.end(); I != E; ++I) {
 511           new_set.insert(*I);
 512
 513           std::set<Value*, ExprLT>::iterator val = availOut.find(*I);
 514           if (val != availOut.end())
 515             new_set.erase(val);
 516           new_set.insert(*I);
 517         }
 518       }
 519
 520       // If there is more than one predecessor...
 521       if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
 522         std::vector<Value*> workList;
 523         topo_sort(anticIn, workList);
 524
 525         DOUT << "Merge Block: " << BB->getName() << "\n";
 526         DOUT << "ANTIC_IN: ";
 527         dump_unique(anticIn);
 528         DOUT << "\n";
 529
 530         while (!workList.empty()) {
 531           Value* e = workList.back();
 532           workList.pop_back();
 533
 534           if (isa<BinaryOperator>(e)) {
 535             if (find_leader(availableOut[DI->getIDom()->getBlock()], e) != 0)
 536               continue;
 537
 538             std::map<BasicBlock*, Value*> avail;
 539             bool by_some = false;
 540             int num_avail = 0;
 541
 542             for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
 543                  ++PI) {
 544               Value *e2 = phi_translate(anticIn, e, *PI);
 545               Value *e3 = find_leader(availableOut[*PI], e2);
 546
 547               if (e3 == 0) {
 548                 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
 549                 if (av != avail.end())
 550                   avail.erase(av);
 551                 avail.insert(std::make_pair(*PI, e2));
 552               } else {
 553                 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
 554                 if (av != avail.end())
 555                   avail.erase(av);
 556                 avail.insert(std::make_pair(*PI, e3));
 557
 558                 by_some = true;
 559                 num_avail++;
 560               }
 561             }
 562
 563             if (by_some &&
 564                 num_avail < std::distance(pred_begin(BB), pred_end(BB))) {
 565               DOUT << "Processing Value: ";
 566               DEBUG(e->dump());
 567               DOUT << "\n\n";
 568
 569               for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 570                    PI != PE; ++PI) {
 571                 Value* e2 = avail[*PI];
 572                 if (!find_leader(availableOut[*PI], e2)) {
 573                   BinaryOperator* BO = cast<BinaryOperator>(e2);
 574
 575                   Value* s1 = 0;
 576                   if (isa<Instruction>(BO->getOperand(0)))
 577                     s1 = find_leader(availableOut[*PI], BO->getOperand(0));
 578                   else
 579                     s1 = BO->getOperand(0);
 580
 581                   Value* s2 = 0;
 582                   if (isa<Instruction>(BO->getOperand(1)))
 583                     s2 = find_leader(availableOut[*PI], BO->getOperand(1));
 584                   else
 585                     s2 = BO->getOperand(1);
 586
 587                   Value* newVal = BinaryOperator::create(BO->getOpcode(),
 588                                              s1, s2,
 589                                              BO->getName()+".gvnpre",
 590                                              (*PI)->getTerminator());
 591                   add(newVal, VN[BO]);
 592                   availableOut[*PI].insert(newVal);
 593
 594                   DOUT << "Creating value: " << std::hex << newVal << std::dec << "\n";
 595
 596                   std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
 597                   if (av != avail.end())
 598                     avail.erase(av);
 599                   avail.insert(std::make_pair(*PI, newVal));
 600                 }
 601               }
 602
 603               PHINode* p = 0;
 604
 605               for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 606                    PI != PE; ++PI) {
 607                 if (p == 0)
 608                   p = new PHINode(avail[*PI]->getType(), "gvnpre-join",
 609                                   BB->begin());
 610
 611                 p->addIncoming(avail[*PI], *PI);
 612               }
 613
 614               add(p, VN[e]);
 615               DOUT << "Creating value: " << std::hex << p << std::dec << "\n";
 616
 617               availOut.insert(p);
 618               new_stuff = true;
 619
 620               DOUT << "Preds After Processing: ";
 621               for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 622                    PI != PE; ++PI)
 623                 DEBUG((*PI)->dump());
 624               DOUT << "\n\n";
 625
 626               DOUT << "Merge Block After Processing: ";
 627               DEBUG(BB->dump());
 628               DOUT << "\n\n";
 629
 630               new_set.insert(p);
 631             }
 632           }
 633         }
 634       }
 635     }
 636     i_iterations++;
 637   }
 638
 639   // Phase 3: Eliminate
 640   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
 641          E = df_end(DT.getRootNode()); DI != E; ++DI) {
 642     BasicBlock* BB = DI->getBlock();
 643
 644     std::vector<Instruction*> erase;
 645
 646     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
 647          BI != BE; ++BI) {
 648       if (!BI->isTerminator()) {
 649         Value* leader = find_leader(availableOut[BB], BI);
 650         if (leader != 0)
 651           if (Instruction* Instr = dyn_cast<Instruction>(leader))
 652             if (Instr->getParent() != 0 && Instr != BI) {
 653               BI->replaceAllUsesWith(leader);
 654               erase.push_back(BI);
 655             }
 656       }
 657     }
 658
 659     for (std::vector<Instruction*>::iterator I = erase.begin(), E = erase.end();
 660          I != E; ++I)
 661       (*I)->eraseFromParent();
 662   }
 663
 664   // Phase 4: Cleanup
 665   for (std::set<Instruction*>::iterator I = createdExpressions.begin(),
 666        E = createdExpressions.end(); I != E; ++I) {
 667     delete *I;
 668   }
 669
 670   return false;
 671 }