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