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
 333       // Check for dependency on invoke insts
 334       // NOTE: This check is expensive, so don't do it if we
 335       // don't have to
 336       if (lhsValid)
 337         lhsValid = !dependsOnInvoke(BO->getOperand(0));
 338
 339       bool rhsValid = !isa<Instruction>(BO->getOperand(1));
 340       if (!rhsValid)
 341       for (std::set<Value*, ExprLT>::iterator I = set.begin(), E = set.end();
 342            I != E; ++I)
 343         if (VN[*I] == VN[BO->getOperand(1)]) {
 344           rhsValid = true;
 345           break;
 346         }
 347
 348       // Check for dependency on invoke insts
 349       // NOTE: This check is expensive, so don't do it if we
 350       // don't have to
 351       if (rhsValid)
 352         rhsValid = !dependsOnInvoke(BO->getOperand(1));
 353
 354       if (!lhsValid || !rhsValid)
 355         set.erase(BO);
 356     } else if (CmpInst* C = dyn_cast<CmpInst>(v)) {
 357       bool lhsValid = !isa<Instruction>(C->getOperand(0));
 358       if (!lhsValid)
 359         for (std::set<Value*, ExprLT>::iterator I = set.begin(), E = set.end();
 360              I != E; ++I)
 361           if (VN[*I] == VN[C->getOperand(0)]) {
 362             lhsValid = true;
 363             break;
 364           }
 365       lhsValid &= !dependsOnInvoke(C->getOperand(0));
 366
 367       bool rhsValid = !isa<Instruction>(C->getOperand(1));
 368       if (!rhsValid)
 369       for (std::set<Value*, ExprLT>::iterator I = set.begin(), E = set.end();
 370            I != E; ++I)
 371         if (VN[*I] == VN[C->getOperand(1)]) {
 372           rhsValid = true;
 373           break;
 374         }
 375       rhsValid &= !dependsOnInvoke(C->getOperand(1));
 376
 377       if (!lhsValid || !rhsValid)
 378         set.erase(C);
 379     }
 380   }
 381 }
 382
 383 void GVNPRE::topo_sort(std::set<Value*, ExprLT>& set,
 384                        std::vector<Value*>& vec) {
 385   std::set<Value*, ExprLT> toErase;
 386   for (std::set<Value*, ExprLT>::iterator I = set.begin(), E = set.end();
 387        I != E; ++I) {
 388     if (BinaryOperator* BO = dyn_cast<BinaryOperator>(*I))
 389       for (std::set<Value*, ExprLT>::iterator SI = set.begin(); SI != E; ++SI) {
 390         if (VN[BO->getOperand(0)] == VN[*SI] ||
 391             VN[BO->getOperand(1)] == VN[*SI]) {
 392           toErase.insert(*SI);
 393         }
 394       }
 395     else if (CmpInst* C = dyn_cast<CmpInst>(*I))
 396       for (std::set<Value*, ExprLT>::iterator SI = set.begin(); SI != E; ++SI) {
 397         if (VN[C->getOperand(0)] == VN[*SI] ||
 398             VN[C->getOperand(1)] == VN[*SI]) {
 399           toErase.insert(*SI);
 400         }
 401       }
 402   }
 403
 404   std::vector<Value*> Q;
 405   for (std::set<Value*, ExprLT>::iterator I = set.begin(), E = set.end();
 406        I != E; ++I) {
 407     if (toErase.find(*I) == toErase.end())
 408       Q.push_back(*I);
 409   }
 410
 411   std::set<Value*> visited;
 412   while (!Q.empty()) {
 413     Value* e = Q.back();
 414
 415     if (BinaryOperator* BO = dyn_cast<BinaryOperator>(e)) {
 416       Value* l = find_leader(set, BO->getOperand(0));
 417       Value* r = find_leader(set, BO->getOperand(1));
 418
 419       if (l != 0 && isa<Instruction>(l) &&
 420           visited.find(l) == visited.end())
 421         Q.push_back(l);
 422       else if (r != 0 && isa<Instruction>(r) &&
 423                visited.find(r) == visited.end())
 424         Q.push_back(r);
 425       else {
 426         vec.push_back(e);
 427         visited.insert(e);
 428         Q.pop_back();
 429       }
 430     } else if (CmpInst* C = dyn_cast<CmpInst>(e)) {
 431       Value* l = find_leader(set, C->getOperand(0));
 432       Value* r = find_leader(set, C->getOperand(1));
 433
 434       if (l != 0 && isa<Instruction>(l) &&
 435           visited.find(l) == visited.end())
 436         Q.push_back(l);
 437       else if (r != 0 && isa<Instruction>(r) &&
 438                visited.find(r) == visited.end())
 439         Q.push_back(r);
 440       else {
 441         vec.push_back(e);
 442         visited.insert(e);
 443         Q.pop_back();
 444       }
 445     } else {
 446       visited.insert(e);
 447       vec.push_back(e);
 448       Q.pop_back();
 449     }
 450   }
 451 }
 452
 453
 454 void GVNPRE::dump(const std::set<Value*>& s) const {
 455   DOUT << "{ ";
 456   for (std::set<Value*>::iterator I = s.begin(), E = s.end();
 457        I != E; ++I) {
 458     DEBUG((*I)->dump());
 459   }
 460   DOUT << "}\n\n";
 461 }
 462
 463 void GVNPRE::dump_unique(const std::set<Value*, ExprLT>& s) const {
 464   DOUT << "{ ";
 465   for (std::set<Value*>::iterator I = s.begin(), E = s.end();
 466        I != E; ++I) {
 467     DEBUG((*I)->dump());
 468   }
 469   DOUT << "}\n\n";
 470 }
 471
 472 void GVNPRE::CalculateAvailOut(DomTreeNode* DI,
 473                        std::set<Value*, ExprLT>& currExps,
 474                        std::set<PHINode*>& currPhis,
 475                        std::set<Value*>& currTemps,
 476                        std::set<Value*, ExprLT>& currAvail,
 477                        std::map<BasicBlock*, std::set<Value*, ExprLT> > availOut) {
 478
 479   BasicBlock* BB = DI->getBlock();
 480
 481   // A block inherits AVAIL_OUT from its dominator
 482   if (DI->getIDom() != 0)
 483   currAvail.insert(availOut[DI->getIDom()->getBlock()].begin(),
 484                    availOut[DI->getIDom()->getBlock()].end());
 485
 486
 487  for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
 488       BI != BE; ++BI) {
 489
 490     // Handle PHI nodes...
 491     if (PHINode* p = dyn_cast<PHINode>(BI)) {
 492       if (add(p, nextValueNumber))
 493         nextValueNumber++;
 494       currPhis.insert(p);
 495
 496     // Handle binary ops...
 497     } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(BI)) {
 498       Value* leftValue = BO->getOperand(0);
 499       Value* rightValue = BO->getOperand(1);
 500
 501       if (add(BO, nextValueNumber))
 502         nextValueNumber++;
 503
 504       if (isa<Instruction>(leftValue))
 505         currExps.insert(leftValue);
 506       if (isa<Instruction>(rightValue))
 507         currExps.insert(rightValue);
 508       currExps.insert(BO);
 509
 510     // Handle cmp ops...
 511     } else if (CmpInst* C = dyn_cast<CmpInst>(BI)) {
 512       Value* leftValue = C->getOperand(0);
 513       Value* rightValue = C->getOperand(1);
 514
 515       if (add(C, nextValueNumber))
 516         nextValueNumber++;
 517
 518       if (isa<Instruction>(leftValue))
 519         currExps.insert(leftValue);
 520       if (isa<Instruction>(rightValue))
 521         currExps.insert(rightValue);
 522       currExps.insert(C);
 523
 524     // Handle unsupported ops
 525     } else if (!BI->isTerminator()){
 526       if (add(BI, nextValueNumber))
 527         nextValueNumber++;
 528       currTemps.insert(BI);
 529     }
 530
 531     if (!BI->isTerminator())
 532       currAvail.insert(BI);
 533   }
 534 }
 535
 536 void GVNPRE::elimination() {
 537   DOUT << "\n\nPhase 3: Elimination\n\n";
 538
 539   std::vector<std::pair<Instruction*, Value*> > replace;
 540   std::vector<Instruction*> erase;
 541
 542   DominatorTree& DT = getAnalysis<DominatorTree>();
 543
 544   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
 545          E = df_end(DT.getRootNode()); DI != E; ++DI) {
 546     BasicBlock* BB = DI->getBlock();
 547
 548     DOUT << "Block: " << BB->getName() << "\n";
 549     dump_unique(availableOut[BB]);
 550     DOUT << "\n\n";
 551
 552     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
 553          BI != BE; ++BI) {
 554
 555       if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI)) {
 556          Value *leader = find_leader(availableOut[BB], BI);
 557
 558         if (leader != 0)
 559           if (Instruction* Instr = dyn_cast<Instruction>(leader))
 560             if (Instr->getParent() != 0 && Instr != BI) {
 561               replace.push_back(std::make_pair(BI, leader));
 562               erase.push_back(BI);
 563               ++NumEliminated;
 564             }
 565       }
 566     }
 567   }
 568
 569   while (!replace.empty()) {
 570     std::pair<Instruction*, Value*> rep = replace.back();
 571     replace.pop_back();
 572     rep.first->replaceAllUsesWith(rep.second);
 573   }
 574
 575   for (std::vector<Instruction*>::iterator I = erase.begin(), E = erase.end();
 576        I != E; ++I)
 577      (*I)->eraseFromParent();
 578 }
 579
 580
 581 void GVNPRE::cleanup() {
 582   while (!createdExpressions.empty()) {
 583     Instruction* I = createdExpressions.back();
 584     createdExpressions.pop_back();
 585
 586     delete I;
 587   }
 588 }
 589
 590 bool GVNPRE::runOnFunction(Function &F) {
 591   VN.clear();
 592   MS.clear();
 593   createdExpressions.clear();
 594   availableOut.clear();
 595   anticipatedIn.clear();
 596
 597   std::map<BasicBlock*, std::set<Value*, ExprLT> > generatedExpressions;
 598   std::map<BasicBlock*, std::set<PHINode*> > generatedPhis;
 599   std::map<BasicBlock*, std::set<Value*> > generatedTemporaries;
 600
 601
 602   DominatorTree &DT = getAnalysis<DominatorTree>();
 603
 604   // Phase 1: BuildSets
 605
 606   // Phase 1, Part 1: calculate AVAIL_OUT
 607
 608   // Top-down walk of the dominator tree
 609   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
 610          E = df_end(DT.getRootNode()); DI != E; ++DI) {
 611
 612     // Get the sets to update for this block
 613     std::set<Value*, ExprLT>& currExps = generatedExpressions[DI->getBlock()];
 614     std::set<PHINode*>& currPhis = generatedPhis[DI->getBlock()];
 615     std::set<Value*>& currTemps = generatedTemporaries[DI->getBlock()];
 616     std::set<Value*, ExprLT>& currAvail = availableOut[DI->getBlock()];
 617
 618     CalculateAvailOut(*DI, currExps, currPhis,
 619                       currTemps, currAvail, availableOut);
 620   }
 621
 622   DOUT << "Maximal Set: ";
 623   dump_unique(MS);
 624   DOUT << "\n";
 625
 626   // If function has no exit blocks, only perform GVN
 627   PostDominatorTree &PDT = getAnalysis<PostDominatorTree>();
 628   if (PDT[&F.getEntryBlock()] == 0) {
 629     elimination();
 630     cleanup();
 631
 632     return true;
 633   }
 634
 635
 636   // Phase 1, Part 2: calculate ANTIC_IN
 637
 638   std::set<BasicBlock*> visited;
 639
 640   bool changed = true;
 641   unsigned iterations = 0;
 642   while (changed) {
 643     changed = false;
 644     std::set<Value*, ExprLT> anticOut;
 645
 646     // Top-down walk of the postdominator tree
 647     for (df_iterator<DomTreeNode*> PDI =
 648          df_begin(PDT.getRootNode()), E = df_end(PDT.getRootNode());
 649          PDI != E; ++PDI) {
 650       BasicBlock* BB = PDI->getBlock();
 651       if (BB == 0)
 652         continue;
 653
 654       DOUT << "Block: " << BB->getName() << "\n";
 655       DOUT << "TMP_GEN: ";
 656       dump(generatedTemporaries[BB]);
 657       DOUT << "\n";
 658
 659       DOUT << "EXP_GEN: ";
 660       dump_unique(generatedExpressions[BB]);
 661       visited.insert(BB);
 662
 663       std::set<Value*, ExprLT>& anticIn = anticipatedIn[BB];
 664       std::set<Value*, ExprLT> old (anticIn.begin(), anticIn.end());
 665
 666       if (BB->getTerminator()->getNumSuccessors() == 1) {
 667          if (visited.find(BB->getTerminator()->getSuccessor(0)) ==
 668              visited.end())
 669            phi_translate_set(MS, BB, BB->getTerminator()->getSuccessor(0),
 670                              anticOut);
 671          else
 672            phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
 673                              BB,  BB->getTerminator()->getSuccessor(0),
 674                              anticOut);
 675       } else if (BB->getTerminator()->getNumSuccessors() > 1) {
 676         BasicBlock* first = BB->getTerminator()->getSuccessor(0);
 677         anticOut.insert(anticipatedIn[first].begin(),
 678                         anticipatedIn[first].end());
 679         for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
 680           BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
 681           std::set<Value*, ExprLT>& succAnticIn = anticipatedIn[currSucc];
 682
 683           std::set<Value*, ExprLT> temp;
 684           std::insert_iterator<std::set<Value*, ExprLT> >  temp_ins(temp,
 685                                                                   temp.begin());
 686           std::set_intersection(anticOut.begin(), anticOut.end(),
 687                                 succAnticIn.begin(), succAnticIn.end(),
 688                                 temp_ins, ExprLT());
 689
 690           anticOut.clear();
 691           anticOut.insert(temp.begin(), temp.end());
 692         }
 693       }
 694
 695       DOUT << "ANTIC_OUT: ";
 696       dump_unique(anticOut);
 697       DOUT << "\n";
 698
 699       std::set<Value*, ExprLT> S;
 700       std::insert_iterator<std::set<Value*, ExprLT> >  s_ins(S, S.begin());
 701       std::set_union(anticOut.begin(), anticOut.end(),
 702                      generatedExpressions[BB].begin(),
 703                      generatedExpressions[BB].end(),
 704                      s_ins, ExprLT());
 705
 706       anticIn.clear();
 707
 708       for (std::set<Value*, ExprLT>::iterator I = S.begin(), E = S.end();
 709            I != E; ++I) {
 710         if (generatedTemporaries[BB].find(*I) == generatedTemporaries[BB].end())
 711           anticIn.insert(*I);
 712       }
 713
 714       clean(anticIn);
 715
 716       DOUT << "ANTIC_IN: ";
 717       dump_unique(anticIn);
 718       DOUT << "\n";
 719
 720       if (old.size() != anticIn.size())
 721         changed = true;
 722
 723       anticOut.clear();
 724     }
 725
 726     iterations++;
 727   }
 728
 729   DOUT << "Iterations: " << iterations << "\n";
 730
 731   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
 732     DOUT << "Name: " << I->getName().c_str() << "\n";
 733
 734     DOUT << "TMP_GEN: ";
 735     dump(generatedTemporaries[I]);
 736     DOUT << "\n";
 737
 738     DOUT << "EXP_GEN: ";
 739     dump_unique(generatedExpressions[I]);
 740     DOUT << "\n";
 741
 742     DOUT << "ANTIC_IN: ";
 743     dump_unique(anticipatedIn[I]);
 744     DOUT << "\n";
 745
 746     DOUT << "AVAIL_OUT: ";
 747     dump_unique(availableOut[I]);
 748     DOUT << "\n";
 749   }
 750
 751   // Phase 2: Insert
 752   DOUT<< "\nPhase 2: Insertion\n";
 753
 754   std::map<BasicBlock*, std::set<Value*, ExprLT> > new_sets;
 755   unsigned i_iterations = 0;
 756   bool new_stuff = true;
 757   while (new_stuff) {
 758     new_stuff = false;
 759     DOUT << "Iteration: " << i_iterations << "\n\n";
 760     for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
 761          E = df_end(DT.getRootNode()); DI != E; ++DI) {
 762       BasicBlock* BB = DI->getBlock();
 763
 764       if (BB == 0)
 765         continue;
 766
 767       std::set<Value*, ExprLT>& new_set = new_sets[BB];
 768       std::set<Value*, ExprLT>& availOut = availableOut[BB];
 769       std::set<Value*, ExprLT>& anticIn = anticipatedIn[BB];
 770
 771       new_set.clear();
 772
 773       // Replace leaders with leaders inherited from dominator
 774       if (DI->getIDom() != 0) {
 775         std::set<Value*, ExprLT>& dom_set = new_sets[DI->getIDom()->getBlock()];
 776         for (std::set<Value*, ExprLT>::iterator I = dom_set.begin(),
 777              E = dom_set.end(); I != E; ++I) {
 778           new_set.insert(*I);
 779
 780           Value* val = find_leader(availOut, *I);
 781           while (val != 0) {
 782             availOut.erase(val);
 783             val = find_leader(availOut, *I);
 784           }
 785           availOut.insert(*I);
 786         }
 787       }
 788
 789       // If there is more than one predecessor...
 790       if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
 791         std::vector<Value*> workList;
 792         topo_sort(anticIn, workList);
 793
 794         DOUT << "Merge Block: " << BB->getName() << "\n";
 795         DOUT << "ANTIC_IN: ";
 796         dump_unique(anticIn);
 797         DOUT << "\n";
 798
 799         for (unsigned i = 0; i < workList.size(); ++i) {
 800           Value* e = workList[i];
 801
 802           if (isa<BinaryOperator>(e) || isa<CmpInst>(e)) {
 803             if (find_leader(availableOut[DI->getIDom()->getBlock()], e) != 0)
 804               continue;
 805
 806             std::map<BasicBlock*, Value*> avail;
 807             bool by_some = false;
 808             int num_avail = 0;
 809
 810             for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
 811                  ++PI) {
 812               Value *e2 = phi_translate(e, *PI, BB);
 813               Value *e3 = find_leader(availableOut[*PI], e2);
 814
 815               if (e3 == 0) {
 816                 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
 817                 if (av != avail.end())
 818                   avail.erase(av);
 819                 avail.insert(std::make_pair(*PI, e2));
 820               } else {
 821                 std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
 822                 if (av != avail.end())
 823                   avail.erase(av);
 824                 avail.insert(std::make_pair(*PI, e3));
 825
 826                 by_some = true;
 827                 num_avail++;
 828               }
 829             }
 830
 831             if (by_some &&
 832                 num_avail < std::distance(pred_begin(BB), pred_end(BB))) {
 833               DOUT << "Processing Value: ";
 834               DEBUG(e->dump());
 835               DOUT << "\n\n";
 836
 837               for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 838                    PI != PE; ++PI) {
 839                 Value* e2 = avail[*PI];
 840                 if (!find_leader(availableOut[*PI], e2)) {
 841                   User* U = cast<User>(e2);
 842
 843                   Value* s1 = 0;
 844                   if (isa<BinaryOperator>(U->getOperand(0)) ||
 845                       isa<CmpInst>(U->getOperand(0)))
 846                     s1 = find_leader(availableOut[*PI], U->getOperand(0));
 847                   else
 848                     s1 = U->getOperand(0);
 849
 850                   Value* s2 = 0;
 851                   if (isa<BinaryOperator>(U->getOperand(1)) ||
 852                       isa<CmpInst>(U->getOperand(1)))
 853                     s2 = find_leader(availableOut[*PI], U->getOperand(1));
 854                   else
 855                     s2 = U->getOperand(1);
 856
 857                   Value* newVal = 0;
 858                   if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
 859                     newVal = BinaryOperator::create(BO->getOpcode(),
 860                                              s1, s2,
 861                                              BO->getName()+".gvnpre",
 862                                              (*PI)->getTerminator());
 863                   else if (CmpInst* C = dyn_cast<CmpInst>(U))
 864                     newVal = CmpInst::create(C->getOpcode(),
 865                                              C->getPredicate(),
 866                                              s1, s2,
 867                                              C->getName()+".gvnpre",
 868                                              (*PI)->getTerminator());
 869
 870                   add(newVal, VN[U]);
 871
 872                   std::set<Value*, ExprLT>& predAvail = availableOut[*PI];
 873                   Value* val = find_leader(predAvail, newVal);
 874                   while (val != 0) {
 875                     predAvail.erase(val);
 876                     val = find_leader(predAvail, newVal);
 877                   }
 878                   predAvail.insert(newVal);
 879
 880                   DOUT << "Creating value: " << std::hex << newVal << std::dec << "\n";
 881
 882                   std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
 883                   if (av != avail.end())
 884                     avail.erase(av);
 885                   avail.insert(std::make_pair(*PI, newVal));
 886
 887                   ++NumInsertedVals;
 888                 }
 889               }
 890
 891               PHINode* p = 0;
 892
 893               for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 894                    PI != PE; ++PI) {
 895                 if (p == 0)
 896                   p = new PHINode(avail[*PI]->getType(), "gvnpre-join",
 897                                   BB->begin());
 898
 899                 p->addIncoming(avail[*PI], *PI);
 900               }
 901
 902               add(p, VN[e]);
 903               DOUT << "Creating value: " << std::hex << p << std::dec << "\n";
 904
 905               Value* val = find_leader(availOut, p);
 906               while (val != 0) {
 907                 availOut.erase(val);
 908                 val = find_leader(availOut, p);
 909               }
 910               availOut.insert(p);
 911
 912               new_stuff = true;
 913
 914               DOUT << "Preds After Processing: ";
 915               for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 916                    PI != PE; ++PI)
 917                 DEBUG((*PI)->dump());
 918               DOUT << "\n\n";
 919
 920               DOUT << "Merge Block After Processing: ";
 921               DEBUG(BB->dump());
 922               DOUT << "\n\n";
 923
 924               new_set.insert(p);
 925
 926               ++NumInsertedPhis;
 927             }
 928           }
 929         }
 930       }
 931     }
 932     i_iterations++;
 933   }
 934
 935   // Phase 3: Eliminate
 936   elimination();
 937
 938   // Phase 4: Cleanup
 939   cleanup();
 940
 941   return true;
 942 }