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