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