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/BitVector.h"
  29 #include "llvm/ADT/DenseMap.h"
  30 #include "llvm/ADT/DepthFirstIterator.h"
  31 #include "llvm/ADT/SmallPtrSet.h"
  32 #include "llvm/ADT/Statistic.h"
  33 #include "llvm/Support/CFG.h"
  34 #include "llvm/Support/Compiler.h"
  35 #include "llvm/Support/Debug.h"
  36 #include <algorithm>
  37 #include <deque>
  38 #include <map>
  39 #include <vector>
  40 #include <set>
  41 using namespace llvm;
  42
  43 //===----------------------------------------------------------------------===//
  44 //                         ValueTable Class
  45 //===----------------------------------------------------------------------===//
  46
  47 /// This class holds the mapping between values and value numbers.  It is used
  48 /// as an efficient mechanism to determine the expression-wise equivalence of
  49 /// two values.
  50
  51 namespace {
  52   class VISIBILITY_HIDDEN ValueTable {
  53     public:
  54       struct Expression {
  55         enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM,
  56                               FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
  57                               ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
  58                               ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
  59                               FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
  60                               FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
  61                               FCMPULT, FCMPULE, FCMPUNE };
  62
  63         ExpressionOpcode opcode;
  64         uint32_t leftVN;
  65         uint32_t rightVN;
  66
  67         bool operator< (const Expression& other) const {
  68           if (opcode < other.opcode)
  69             return true;
  70           else if (opcode > other.opcode)
  71             return false;
  72           else if (leftVN < other.leftVN)
  73             return true;
  74           else if (leftVN > other.leftVN)
  75             return false;
  76           else if (rightVN < other.rightVN)
  77             return true;
  78           else if (rightVN > other.rightVN)
  79             return false;
  80           else
  81             return false;
  82         }
  83       };
  84
  85     private:
  86       DenseMap<Value*, uint32_t> valueNumbering;
  87       std::map<Expression, uint32_t> expressionNumbering;
  88
  89       std::set<Expression> maximalExpressions;
  90       SmallPtrSet<Value*, 32> maximalValues;
  91
  92       uint32_t nextValueNumber;
  93
  94       Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
  95       Expression::ExpressionOpcode getOpcode(CmpInst* C);
  96       Expression create_expression(BinaryOperator* BO);
  97       Expression create_expression(CmpInst* C);
  98     public:
  99       ValueTable() { nextValueNumber = 1; }
 100       uint32_t lookup_or_add(Value* V);
 101       uint32_t lookup(Value* V);
 102       void add(Value* V, uint32_t num);
 103       void clear();
 104       std::set<Expression>& getMaximalExpressions() {
 105         return maximalExpressions;
 106
 107       }
 108       SmallPtrSet<Value*, 32>& getMaximalValues() { return maximalValues; }
 109       void erase(Value* v);
 110       unsigned size();
 111   };
 112 }
 113
 114 //===----------------------------------------------------------------------===//
 115 //                     ValueTable Internal Functions
 116 //===----------------------------------------------------------------------===//
 117 ValueTable::Expression::ExpressionOpcode
 118                              ValueTable::getOpcode(BinaryOperator* BO) {
 119   switch(BO->getOpcode()) {
 120     case Instruction::Add:
 121       return Expression::ADD;
 122     case Instruction::Sub:
 123       return Expression::SUB;
 124     case Instruction::Mul:
 125       return Expression::MUL;
 126     case Instruction::UDiv:
 127       return Expression::UDIV;
 128     case Instruction::SDiv:
 129       return Expression::SDIV;
 130     case Instruction::FDiv:
 131       return Expression::FDIV;
 132     case Instruction::URem:
 133       return Expression::UREM;
 134     case Instruction::SRem:
 135       return Expression::SREM;
 136     case Instruction::FRem:
 137       return Expression::FREM;
 138     case Instruction::Shl:
 139       return Expression::SHL;
 140     case Instruction::LShr:
 141       return Expression::LSHR;
 142     case Instruction::AShr:
 143       return Expression::ASHR;
 144     case Instruction::And:
 145       return Expression::AND;
 146     case Instruction::Or:
 147       return Expression::OR;
 148     case Instruction::Xor:
 149       return Expression::XOR;
 150
 151     // THIS SHOULD NEVER HAPPEN
 152     default:
 153       assert(0 && "Binary operator with unknown opcode?");
 154       return Expression::ADD;
 155   }
 156 }
 157
 158 ValueTable::Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
 159   if (C->getOpcode() == Instruction::ICmp) {
 160     switch (C->getPredicate()) {
 161       case ICmpInst::ICMP_EQ:
 162         return Expression::ICMPEQ;
 163       case ICmpInst::ICMP_NE:
 164         return Expression::ICMPNE;
 165       case ICmpInst::ICMP_UGT:
 166         return Expression::ICMPUGT;
 167       case ICmpInst::ICMP_UGE:
 168         return Expression::ICMPUGE;
 169       case ICmpInst::ICMP_ULT:
 170         return Expression::ICMPULT;
 171       case ICmpInst::ICMP_ULE:
 172         return Expression::ICMPULE;
 173       case ICmpInst::ICMP_SGT:
 174         return Expression::ICMPSGT;
 175       case ICmpInst::ICMP_SGE:
 176         return Expression::ICMPSGE;
 177       case ICmpInst::ICMP_SLT:
 178         return Expression::ICMPSLT;
 179       case ICmpInst::ICMP_SLE:
 180         return Expression::ICMPSLE;
 181
 182       // THIS SHOULD NEVER HAPPEN
 183       default:
 184         assert(0 && "Comparison with unknown predicate?");
 185         return Expression::ICMPEQ;
 186     }
 187   } else {
 188     switch (C->getPredicate()) {
 189       case FCmpInst::FCMP_OEQ:
 190         return Expression::FCMPOEQ;
 191       case FCmpInst::FCMP_OGT:
 192         return Expression::FCMPOGT;
 193       case FCmpInst::FCMP_OGE:
 194         return Expression::FCMPOGE;
 195       case FCmpInst::FCMP_OLT:
 196         return Expression::FCMPOLT;
 197       case FCmpInst::FCMP_OLE:
 198         return Expression::FCMPOLE;
 199       case FCmpInst::FCMP_ONE:
 200         return Expression::FCMPONE;
 201       case FCmpInst::FCMP_ORD:
 202         return Expression::FCMPORD;
 203       case FCmpInst::FCMP_UNO:
 204         return Expression::FCMPUNO;
 205       case FCmpInst::FCMP_UEQ:
 206         return Expression::FCMPUEQ;
 207       case FCmpInst::FCMP_UGT:
 208         return Expression::FCMPUGT;
 209       case FCmpInst::FCMP_UGE:
 210         return Expression::FCMPUGE;
 211       case FCmpInst::FCMP_ULT:
 212         return Expression::FCMPULT;
 213       case FCmpInst::FCMP_ULE:
 214         return Expression::FCMPULE;
 215       case FCmpInst::FCMP_UNE:
 216         return Expression::FCMPUNE;
 217
 218       // THIS SHOULD NEVER HAPPEN
 219       default:
 220         assert(0 && "Comparison with unknown predicate?");
 221         return Expression::FCMPOEQ;
 222     }
 223   }
 224 }
 225
 226 ValueTable::Expression ValueTable::create_expression(BinaryOperator* BO) {
 227   Expression e;
 228
 229   e.leftVN = lookup_or_add(BO->getOperand(0));
 230   e.rightVN = lookup_or_add(BO->getOperand(1));
 231   e.opcode = getOpcode(BO);
 232
 233   maximalExpressions.insert(e);
 234
 235   return e;
 236 }
 237
 238 ValueTable::Expression ValueTable::create_expression(CmpInst* C) {
 239   Expression e;
 240
 241   e.leftVN = lookup_or_add(C->getOperand(0));
 242   e.rightVN = lookup_or_add(C->getOperand(1));
 243   e.opcode = getOpcode(C);
 244
 245   maximalExpressions.insert(e);
 246
 247   return e;
 248 }
 249
 250 //===----------------------------------------------------------------------===//
 251 //                     ValueTable External Functions
 252 //===----------------------------------------------------------------------===//
 253
 254 /// lookup_or_add - Returns the value number for the specified value, assigning
 255 /// it a new number if it did not have one before.
 256 uint32_t ValueTable::lookup_or_add(Value* V) {
 257   maximalValues.insert(V);
 258
 259   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 260   if (VI != valueNumbering.end())
 261     return VI->second;
 262
 263
 264   if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
 265     Expression e = create_expression(BO);
 266
 267     std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 268     if (EI != expressionNumbering.end()) {
 269       valueNumbering.insert(std::make_pair(V, EI->second));
 270       return EI->second;
 271     } else {
 272       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 273       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 274
 275       return nextValueNumber++;
 276     }
 277   } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
 278     Expression e = create_expression(C);
 279
 280     std::map<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 281     if (EI != expressionNumbering.end()) {
 282       valueNumbering.insert(std::make_pair(V, EI->second));
 283       return EI->second;
 284     } else {
 285       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 286       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 287
 288       return nextValueNumber++;
 289     }
 290   } else {
 291     valueNumbering.insert(std::make_pair(V, nextValueNumber));
 292     return nextValueNumber++;
 293   }
 294 }
 295
 296 /// lookup - Returns the value number of the specified value. Fails if
 297 /// the value has not yet been numbered.
 298 uint32_t ValueTable::lookup(Value* V) {
 299   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 300   if (VI != valueNumbering.end())
 301     return VI->second;
 302   else
 303     assert(0 && "Value not numbered?");
 304
 305   return 0;
 306 }
 307
 308 /// add - Add the specified value with the given value number, removing
 309 /// its old number, if any
 310 void ValueTable::add(Value* V, uint32_t num) {
 311   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 312   if (VI != valueNumbering.end())
 313     valueNumbering.erase(VI);
 314   valueNumbering.insert(std::make_pair(V, num));
 315 }
 316
 317 /// clear - Remove all entries from the ValueTable and the maximal sets
 318 void ValueTable::clear() {
 319   valueNumbering.clear();
 320   expressionNumbering.clear();
 321   maximalExpressions.clear();
 322   maximalValues.clear();
 323   nextValueNumber = 1;
 324 }
 325
 326 /// erase - Remove a value from the value numbering and maximal sets
 327 void ValueTable::erase(Value* V) {
 328   maximalValues.erase(V);
 329   valueNumbering.erase(V);
 330   if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V))
 331     maximalExpressions.erase(create_expression(BO));
 332   else if (CmpInst* C = dyn_cast<CmpInst>(V))
 333     maximalExpressions.erase(create_expression(C));
 334 }
 335
 336 /// size - Return the number of assigned value numbers
 337 unsigned ValueTable::size() {
 338   // NOTE: zero is never assigned
 339   return nextValueNumber;
 340 }
 341
 342 //===----------------------------------------------------------------------===//
 343 //                         GVNPRE Pass
 344 //===----------------------------------------------------------------------===//
 345
 346 namespace {
 347
 348   class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
 349     bool runOnFunction(Function &F);
 350   public:
 351     static char ID; // Pass identification, replacement for typeid
 352     GVNPRE() : FunctionPass((intptr_t)&ID) { }
 353
 354   private:
 355     ValueTable VN;
 356     std::vector<Instruction*> createdExpressions;
 357
 358     std::map<BasicBlock*, SmallPtrSet<Value*, 32> > availableOut;
 359     std::map<BasicBlock*, SmallPtrSet<Value*, 32> > anticipatedIn;
 360
 361     // This transformation requires dominator postdominator info
 362     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 363       AU.setPreservesCFG();
 364       AU.addRequired<DominatorTree>();
 365       AU.addRequired<PostDominatorTree>();
 366     }
 367
 368     // Helper fuctions
 369     // FIXME: eliminate or document these better
 370     void dump(const SmallPtrSet<Value*, 32>& s) const;
 371     void clean(SmallPtrSet<Value*, 32>& set);
 372     Value* find_leader(SmallPtrSet<Value*, 32>& vals,
 373                        uint32_t v);
 374     Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ);
 375     void phi_translate_set(SmallPtrSet<Value*, 32>& anticIn, BasicBlock* pred,
 376                            BasicBlock* succ, SmallPtrSet<Value*, 32>& out);
 377
 378     void topo_sort(SmallPtrSet<Value*, 32>& set,
 379                    std::vector<Value*>& vec);
 380
 381     void cleanup();
 382     bool elimination();
 383
 384     void val_insert(SmallPtrSet<Value*, 32>& s, Value* v);
 385     void val_replace(SmallPtrSet<Value*, 32>& s, Value* v);
 386     bool dependsOnInvoke(Value* V);
 387     void buildsets_availout(BasicBlock::iterator I,
 388                             SmallPtrSet<Value*, 32>& currAvail,
 389                             SmallPtrSet<PHINode*, 32>& currPhis,
 390                             SmallPtrSet<Value*, 32>& currExps,
 391                             SmallPtrSet<Value*, 32>& currTemps,
 392                             BitVector& availNumbers,
 393                             BitVector& expNumbers);
 394     bool buildsets_anticout(BasicBlock* BB,
 395                             SmallPtrSet<Value*, 32>& anticOut,
 396                             std::set<BasicBlock*>& visited);
 397     unsigned buildsets_anticin(BasicBlock* BB,
 398                            SmallPtrSet<Value*, 32>& anticOut,
 399                            SmallPtrSet<Value*, 32>& currExps,
 400                            SmallPtrSet<Value*, 32>& currTemps,
 401                            std::set<BasicBlock*>& visited);
 402     unsigned buildsets(Function& F);
 403
 404     void insertion_pre(Value* e, BasicBlock* BB,
 405                        std::map<BasicBlock*, Value*>& avail,
 406                        SmallPtrSet<Value*, 32>& new_set);
 407     unsigned insertion_mergepoint(std::vector<Value*>& workList,
 408                                   df_iterator<DomTreeNode*>& D,
 409                                   SmallPtrSet<Value*, 32>& new_set);
 410     bool insertion(Function& F);
 411
 412   };
 413
 414   char GVNPRE::ID = 0;
 415
 416 }
 417
 418 // createGVNPREPass - The public interface to this file...
 419 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
 420
 421 RegisterPass<GVNPRE> X("gvnpre",
 422                        "Global Value Numbering/Partial Redundancy Elimination");
 423
 424
 425 STATISTIC(NumInsertedVals, "Number of values inserted");
 426 STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
 427 STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
 428
 429 /// find_leader - Given a set and a value number, return the first
 430 /// element of the set with that value number, or 0 if no such element
 431 /// is present
 432 Value* GVNPRE::find_leader(SmallPtrSet<Value*, 32>& vals, uint32_t v) {
 433   for (SmallPtrSet<Value*, 32>::iterator I = vals.begin(), E = vals.end();
 434        I != E; ++I)
 435     if (v == VN.lookup(*I))
 436       return *I;
 437
 438   return 0;
 439 }
 440
 441 /// val_insert - Insert a value into a set only if there is not a value
 442 /// with the same value number already in the set
 443 void GVNPRE::val_insert(SmallPtrSet<Value*, 32>& s, Value* v) {
 444   uint32_t num = VN.lookup(v);
 445   Value* leader = find_leader(s, num);
 446   if (leader == 0)
 447     s.insert(v);
 448 }
 449
 450 /// val_replace - Insert a value into a set, replacing any values already in
 451 /// the set that have the same value number
 452 void GVNPRE::val_replace(SmallPtrSet<Value*, 32>& s, Value* v) {
 453   uint32_t num = VN.lookup(v);
 454   Value* leader = find_leader(s, num);
 455   while (leader != 0) {
 456     s.erase(leader);
 457     leader = find_leader(s, num);
 458   }
 459   s.insert(v);
 460 }
 461
 462 /// phi_translate - Given a value, its parent block, and a predecessor of its
 463 /// parent, translate the value into legal for the predecessor block.  This
 464 /// means translating its operands (and recursively, their operands) through
 465 /// any phi nodes in the parent into values available in the predecessor
 466 Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
 467   if (V == 0)
 468     return 0;
 469
 470   if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
 471     Value* newOp1 = 0;
 472     if (isa<Instruction>(BO->getOperand(0)))
 473       newOp1 = phi_translate(find_leader(anticipatedIn[succ],
 474                                          VN.lookup(BO->getOperand(0))),
 475                              pred, succ);
 476     else
 477       newOp1 = BO->getOperand(0);
 478
 479     if (newOp1 == 0)
 480       return 0;
 481
 482     Value* newOp2 = 0;
 483     if (isa<Instruction>(BO->getOperand(1)))
 484       newOp2 = phi_translate(find_leader(anticipatedIn[succ],
 485                                          VN.lookup(BO->getOperand(1))),
 486                              pred, succ);
 487     else
 488       newOp2 = BO->getOperand(1);
 489
 490     if (newOp2 == 0)
 491       return 0;
 492
 493     if (newOp1 != BO->getOperand(0) || newOp2 != BO->getOperand(1)) {
 494       Instruction* newVal = BinaryOperator::create(BO->getOpcode(),
 495                                              newOp1, newOp2,
 496                                              BO->getName()+".expr");
 497
 498       uint32_t v = VN.lookup_or_add(newVal);
 499
 500       Value* leader = find_leader(availableOut[pred], v);
 501       if (leader == 0) {
 502         createdExpressions.push_back(newVal);
 503         return newVal;
 504       } else {
 505         VN.erase(newVal);
 506         delete newVal;
 507         return leader;
 508       }
 509     }
 510   } else if (PHINode* P = dyn_cast<PHINode>(V)) {
 511     if (P->getParent() == succ)
 512       return P->getIncomingValueForBlock(pred);
 513   } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
 514     Value* newOp1 = 0;
 515     if (isa<Instruction>(C->getOperand(0)))
 516       newOp1 = phi_translate(find_leader(anticipatedIn[succ],
 517                                          VN.lookup(C->getOperand(0))),
 518                              pred, succ);
 519     else
 520       newOp1 = C->getOperand(0);
 521
 522     if (newOp1 == 0)
 523       return 0;
 524
 525     Value* newOp2 = 0;
 526     if (isa<Instruction>(C->getOperand(1)))
 527       newOp2 = phi_translate(find_leader(anticipatedIn[succ],
 528                                          VN.lookup(C->getOperand(1))),
 529                              pred, succ);
 530     else
 531       newOp2 = C->getOperand(1);
 532
 533     if (newOp2 == 0)
 534       return 0;
 535
 536     if (newOp1 != C->getOperand(0) || newOp2 != C->getOperand(1)) {
 537       Instruction* newVal = CmpInst::create(C->getOpcode(),
 538                                             C->getPredicate(),
 539                                              newOp1, newOp2,
 540                                              C->getName()+".expr");
 541
 542       uint32_t v = VN.lookup_or_add(newVal);
 543
 544       Value* leader = find_leader(availableOut[pred], v);
 545       if (leader == 0) {
 546         createdExpressions.push_back(newVal);
 547         return newVal;
 548       } else {
 549         VN.erase(newVal);
 550         delete newVal;
 551         return leader;
 552       }
 553     }
 554   }
 555
 556   return V;
 557 }
 558
 559 /// phi_translate_set - Perform phi translation on every element of a set
 560 void GVNPRE::phi_translate_set(SmallPtrSet<Value*, 32>& anticIn,
 561                               BasicBlock* pred, BasicBlock* succ,
 562                               SmallPtrSet<Value*, 32>& out) {
 563   for (SmallPtrSet<Value*, 32>::iterator I = anticIn.begin(),
 564        E = anticIn.end(); I != E; ++I) {
 565     Value* V = phi_translate(*I, pred, succ);
 566     if (V != 0)
 567       out.insert(V);
 568   }
 569 }
 570
 571 /// dependsOnInvoke - Test if a value has an phi node as an operand, any of
 572 /// whose inputs is an invoke instruction.  If this is true, we cannot safely
 573 /// PRE the instruction or anything that depends on it.
 574 bool GVNPRE::dependsOnInvoke(Value* V) {
 575   if (PHINode* p = dyn_cast<PHINode>(V)) {
 576     for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
 577       if (isa<InvokeInst>(*I))
 578         return true;
 579     return false;
 580   } else {
 581     return false;
 582   }
 583 }
 584
 585 /// clean - Remove all non-opaque values from the set whose operands are not
 586 /// themselves in the set, as well as all values that depend on invokes (see
 587 /// above)
 588 void GVNPRE::clean(SmallPtrSet<Value*, 32>& set) {
 589   std::vector<Value*> worklist;
 590   worklist.reserve(set.size());
 591   topo_sort(set, worklist);
 592
 593   for (unsigned i = 0; i < worklist.size(); ++i) {
 594     Value* v = worklist[i];
 595
 596     if (BinaryOperator* BO = dyn_cast<BinaryOperator>(v)) {
 597       bool lhsValid = !isa<Instruction>(BO->getOperand(0));
 598       if (!lhsValid)
 599         for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
 600              I != E; ++I)
 601           if (VN.lookup(*I) == VN.lookup(BO->getOperand(0))) {
 602             lhsValid = true;
 603             break;
 604           }
 605       if (lhsValid)
 606         lhsValid = !dependsOnInvoke(BO->getOperand(0));
 607
 608       bool rhsValid = !isa<Instruction>(BO->getOperand(1));
 609       if (!rhsValid)
 610         for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
 611              I != E; ++I)
 612           if (VN.lookup(*I) == VN.lookup(BO->getOperand(1))) {
 613             rhsValid = true;
 614             break;
 615           }
 616       if (rhsValid)
 617         rhsValid = !dependsOnInvoke(BO->getOperand(1));
 618
 619       if (!lhsValid || !rhsValid)
 620         set.erase(BO);
 621     } else if (CmpInst* C = dyn_cast<CmpInst>(v)) {
 622       bool lhsValid = !isa<Instruction>(C->getOperand(0));
 623       if (!lhsValid)
 624         for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
 625              I != E; ++I)
 626           if (VN.lookup(*I) == VN.lookup(C->getOperand(0))) {
 627             lhsValid = true;
 628             break;
 629           }
 630       if (lhsValid)
 631         lhsValid = !dependsOnInvoke(C->getOperand(0));
 632
 633       bool rhsValid = !isa<Instruction>(C->getOperand(1));
 634       if (!rhsValid)
 635       for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
 636            I != E; ++I)
 637         if (VN.lookup(*I) == VN.lookup(C->getOperand(1))) {
 638           rhsValid = true;
 639           break;
 640         }
 641       if (rhsValid)
 642         rhsValid = !dependsOnInvoke(C->getOperand(1));
 643
 644       if (!lhsValid || !rhsValid)
 645         set.erase(C);
 646     }
 647   }
 648 }
 649
 650 /// topo_sort - Given a set of values, sort them by topological
 651 /// order into the provided vector.
 652 void GVNPRE::topo_sort(SmallPtrSet<Value*, 32>& set, std::vector<Value*>& vec) {
 653   SmallPtrSet<Value*, 32> toErase;
 654   for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
 655        I != E; ++I) {
 656     if (BinaryOperator* BO = dyn_cast<BinaryOperator>(*I))
 657       for (SmallPtrSet<Value*, 32>::iterator SI = set.begin(); SI != E; ++SI) {
 658         if (VN.lookup(BO->getOperand(0)) == VN.lookup(*SI) ||
 659             VN.lookup(BO->getOperand(1)) == VN.lookup(*SI)) {
 660           toErase.insert(*SI);
 661         }
 662       }
 663     else if (CmpInst* C = dyn_cast<CmpInst>(*I))
 664       for (SmallPtrSet<Value*, 32>::iterator SI = set.begin(); SI != E; ++SI) {
 665         if (VN.lookup(C->getOperand(0)) == VN.lookup(*SI) ||
 666             VN.lookup(C->getOperand(1)) == VN.lookup(*SI)) {
 667           toErase.insert(*SI);
 668         }
 669       }
 670   }
 671
 672   std::vector<Value*> Q;
 673   for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
 674        I != E; ++I) {
 675     if (toErase.count(*I) == 0)
 676       Q.push_back(*I);
 677   }
 678
 679   SmallPtrSet<Value*, 32> visited;
 680   while (!Q.empty()) {
 681     Value* e = Q.back();
 682
 683     if (BinaryOperator* BO = dyn_cast<BinaryOperator>(e)) {
 684       Value* l = find_leader(set, VN.lookup(BO->getOperand(0)));
 685       Value* r = find_leader(set, VN.lookup(BO->getOperand(1)));
 686
 687       if (l != 0 && isa<Instruction>(l) &&
 688           visited.count(l) == 0)
 689         Q.push_back(l);
 690       else if (r != 0 && isa<Instruction>(r) &&
 691                visited.count(r) == 0)
 692         Q.push_back(r);
 693       else {
 694         vec.push_back(e);
 695         visited.insert(e);
 696         Q.pop_back();
 697       }
 698     } else if (CmpInst* C = dyn_cast<CmpInst>(e)) {
 699       Value* l = find_leader(set, VN.lookup(C->getOperand(0)));
 700       Value* r = find_leader(set, VN.lookup(C->getOperand(1)));
 701
 702       if (l != 0 && isa<Instruction>(l) &&
 703           visited.count(l) == 0)
 704         Q.push_back(l);
 705       else if (r != 0 && isa<Instruction>(r) &&
 706                visited.count(r) == 0)
 707         Q.push_back(r);
 708       else {
 709         vec.push_back(e);
 710         visited.insert(e);
 711         Q.pop_back();
 712       }
 713     } else {
 714       visited.insert(e);
 715       vec.push_back(e);
 716       Q.pop_back();
 717     }
 718   }
 719 }
 720
 721 /// dump - Dump a set of values to standard error
 722 void GVNPRE::dump(const SmallPtrSet<Value*, 32>& s) const {
 723   DOUT << "{ ";
 724   for (SmallPtrSet<Value*, 32>::iterator I = s.begin(), E = s.end();
 725        I != E; ++I) {
 726     DEBUG((*I)->dump());
 727   }
 728   DOUT << "}\n\n";
 729 }
 730
 731 /// elimination - Phase 3 of the main algorithm.  Perform full redundancy
 732 /// elimination by walking the dominator tree and removing any instruction that
 733 /// is dominated by another instruction with the same value number.
 734 bool GVNPRE::elimination() {
 735   DOUT << "\n\nPhase 3: Elimination\n\n";
 736
 737   bool changed_function = false;
 738
 739   std::vector<std::pair<Instruction*, Value*> > replace;
 740   std::vector<Instruction*> erase;
 741
 742   DominatorTree& DT = getAnalysis<DominatorTree>();
 743
 744   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
 745          E = df_end(DT.getRootNode()); DI != E; ++DI) {
 746     BasicBlock* BB = DI->getBlock();
 747
 748     DOUT << "Block: " << BB->getName() << "\n";
 749     dump(availableOut[BB]);
 750     DOUT << "\n\n";
 751
 752     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
 753          BI != BE; ++BI) {
 754
 755       if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI)) {
 756          Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
 757
 758         if (leader != 0)
 759           if (Instruction* Instr = dyn_cast<Instruction>(leader))
 760             if (Instr->getParent() != 0 && Instr != BI) {
 761               replace.push_back(std::make_pair(BI, leader));
 762               erase.push_back(BI);
 763               ++NumEliminated;
 764             }
 765       }
 766     }
 767   }
 768
 769   while (!replace.empty()) {
 770     std::pair<Instruction*, Value*> rep = replace.back();
 771     replace.pop_back();
 772     rep.first->replaceAllUsesWith(rep.second);
 773     changed_function = true;
 774   }
 775
 776   for (std::vector<Instruction*>::iterator I = erase.begin(), E = erase.end();
 777        I != E; ++I)
 778      (*I)->eraseFromParent();
 779
 780   return changed_function;
 781 }
 782
 783 /// cleanup - Delete any extraneous values that were created to represent
 784 /// expressions without leaders.
 785 void GVNPRE::cleanup() {
 786   while (!createdExpressions.empty()) {
 787     Instruction* I = createdExpressions.back();
 788     createdExpressions.pop_back();
 789
 790     delete I;
 791   }
 792 }
 793
 794 /// buildsets_availout - When calculating availability, handle an instruction
 795 /// by inserting it into the appropriate sets
 796 void GVNPRE::buildsets_availout(BasicBlock::iterator I,
 797                                 SmallPtrSet<Value*, 32>& currAvail,
 798                                 SmallPtrSet<PHINode*, 32>& currPhis,
 799                                 SmallPtrSet<Value*, 32>& currExps,
 800                                 SmallPtrSet<Value*, 32>& currTemps,
 801                                 BitVector& availNumbers,
 802                                 BitVector& expNumbers) {
 803   // Handle PHI nodes...
 804   if (PHINode* p = dyn_cast<PHINode>(I)) {
 805     VN.lookup_or_add(p);
 806     expNumbers.resize(VN.size());
 807     availNumbers.resize(VN.size());
 808
 809     currPhis.insert(p);
 810
 811   // Handle binary ops...
 812   } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(I)) {
 813     Value* leftValue = BO->getOperand(0);
 814     Value* rightValue = BO->getOperand(1);
 815
 816     unsigned num = VN.lookup_or_add(BO);
 817     expNumbers.resize(VN.size());
 818     availNumbers.resize(VN.size());
 819
 820     if (isa<Instruction>(leftValue))
 821       if (!expNumbers.test(VN.lookup(leftValue))) {
 822         currExps.insert(leftValue);
 823         expNumbers.set(VN.lookup(leftValue));
 824       }
 825
 826     if (isa<Instruction>(rightValue))
 827       if (!expNumbers.test(VN.lookup(rightValue))) {
 828         currExps.insert(rightValue);
 829         expNumbers.set(VN.lookup(rightValue));
 830       }
 831
 832     if (!expNumbers.test(VN.lookup(BO))) {
 833       currExps.insert(BO);
 834       expNumbers.set(num);
 835     }
 836
 837   // Handle cmp ops...
 838   } else if (CmpInst* C = dyn_cast<CmpInst>(I)) {
 839     Value* leftValue = C->getOperand(0);
 840     Value* rightValue = C->getOperand(1);
 841
 842     VN.lookup_or_add(C);
 843
 844     unsigned num = VN.lookup_or_add(C);
 845     expNumbers.resize(VN.size());
 846     availNumbers.resize(VN.size());
 847
 848     if (isa<Instruction>(leftValue))
 849       if (!expNumbers.test(VN.lookup(leftValue))) {
 850         currExps.insert(leftValue);
 851         expNumbers.set(VN.lookup(leftValue));
 852       }
 853     if (isa<Instruction>(rightValue))
 854       if (!expNumbers.test(VN.lookup(rightValue))) {
 855         currExps.insert(rightValue);
 856         expNumbers.set(VN.lookup(rightValue));
 857       }
 858
 859     if (!expNumbers.test(VN.lookup(C))) {
 860       currExps.insert(C);
 861       expNumbers.set(num);
 862     }
 863
 864   // Handle unsupported ops
 865   } else if (!I->isTerminator()){
 866     VN.lookup_or_add(I);
 867     expNumbers.resize(VN.size());
 868     availNumbers.resize(VN.size());
 869
 870     currTemps.insert(I);
 871   }
 872
 873   if (!I->isTerminator())
 874     if (!availNumbers.test(VN.lookup(I))) {
 875       currAvail.insert(I);
 876       availNumbers.set(VN.lookup(I));
 877     }
 878 }
 879
 880 /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
 881 /// set as a function of the ANTIC_IN set of the block's predecessors
 882 bool GVNPRE::buildsets_anticout(BasicBlock* BB,
 883                                 SmallPtrSet<Value*, 32>& anticOut,
 884                                 std::set<BasicBlock*>& visited) {
 885   if (BB->getTerminator()->getNumSuccessors() == 1) {
 886     if (visited.count(BB->getTerminator()->getSuccessor(0)) == 0)
 887       return true;
 888     else
 889       phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
 890                         BB,  BB->getTerminator()->getSuccessor(0), anticOut);
 891   } else if (BB->getTerminator()->getNumSuccessors() > 1) {
 892     BasicBlock* first = BB->getTerminator()->getSuccessor(0);
 893     anticOut.insert(anticipatedIn[first].begin(), anticipatedIn[first].end());
 894
 895     for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
 896       BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
 897       SmallPtrSet<Value*, 32>& succAnticIn = anticipatedIn[currSucc];
 898
 899       std::vector<Value*> temp;
 900
 901       for (SmallPtrSet<Value*, 32>::iterator I = anticOut.begin(),
 902            E = anticOut.end(); I != E; ++I)
 903         if (succAnticIn.count(*I) == 0)
 904           temp.push_back(*I);
 905
 906       for (std::vector<Value*>::iterator I = temp.begin(), E = temp.end();
 907            I != E; ++I)
 908         anticOut.erase(*I);
 909     }
 910   }
 911
 912   return false;
 913 }
 914
 915 /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
 916 /// each block.  ANTIC_IN is then a function of ANTIC_OUT and the GEN
 917 /// sets populated in buildsets_availout
 918 unsigned GVNPRE::buildsets_anticin(BasicBlock* BB,
 919                                SmallPtrSet<Value*, 32>& anticOut,
 920                                SmallPtrSet<Value*, 32>& currExps,
 921                                SmallPtrSet<Value*, 32>& currTemps,
 922                                std::set<BasicBlock*>& visited) {
 923   SmallPtrSet<Value*, 32>& anticIn = anticipatedIn[BB];
 924   unsigned old = anticIn.size();
 925
 926   bool defer = buildsets_anticout(BB, anticOut, visited);
 927   if (defer)
 928     return 0;
 929
 930   anticIn.clear();
 931
 932   BitVector numbers(VN.size());
 933   for (SmallPtrSet<Value*, 32>::iterator I = anticOut.begin(),
 934        E = anticOut.end(); I != E; ++I) {
 935     anticIn.insert(*I);
 936     numbers.set(VN.lookup_or_add(*I));
 937   }
 938   for (SmallPtrSet<Value*, 32>::iterator I = currExps.begin(),
 939        E = currExps.end(); I != E; ++I) {
 940     if (!numbers.test(VN.lookup_or_add(*I))) {
 941       anticIn.insert(*I);
 942       numbers.set(VN.lookup(*I));
 943     }
 944   }
 945
 946   for (SmallPtrSet<Value*, 32>::iterator I = currTemps.begin(),
 947        E = currTemps.end(); I != E; ++I)
 948     anticIn.erase(*I);
 949
 950   clean(anticIn);
 951   anticOut.clear();
 952
 953   if (old != anticIn.size())
 954     return 2;
 955   else
 956     return 1;
 957 }
 958
 959 /// buildsets - Phase 1 of the main algorithm.  Construct the AVAIL_OUT
 960 /// and the ANTIC_IN sets.
 961 unsigned GVNPRE::buildsets(Function& F) {
 962   std::map<BasicBlock*, SmallPtrSet<Value*, 32> > generatedExpressions;
 963   std::map<BasicBlock*, SmallPtrSet<PHINode*, 32> > generatedPhis;
 964   std::map<BasicBlock*, SmallPtrSet<Value*, 32> > generatedTemporaries;
 965
 966   DominatorTree &DT = getAnalysis<DominatorTree>();
 967
 968   // Phase 1, Part 1: calculate AVAIL_OUT
 969
 970   // Top-down walk of the dominator tree
 971   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
 972          E = df_end(DT.getRootNode()); DI != E; ++DI) {
 973
 974     // Get the sets to update for this block
 975     SmallPtrSet<Value*, 32>& currExps = generatedExpressions[DI->getBlock()];
 976     SmallPtrSet<PHINode*, 32>& currPhis = generatedPhis[DI->getBlock()];
 977     SmallPtrSet<Value*, 32>& currTemps = generatedTemporaries[DI->getBlock()];
 978     SmallPtrSet<Value*, 32>& currAvail = availableOut[DI->getBlock()];
 979
 980     BasicBlock* BB = DI->getBlock();
 981
 982     // A block inherits AVAIL_OUT from its dominator
 983     if (DI->getIDom() != 0)
 984     currAvail.insert(availableOut[DI->getIDom()->getBlock()].begin(),
 985                      availableOut[DI->getIDom()->getBlock()].end());
 986
 987     BitVector availNumbers(VN.size());
 988     for (SmallPtrSet<Value*, 32>::iterator I = currAvail.begin(),
 989         E = currAvail.end(); I != E; ++I)
 990       availNumbers.set(VN.lookup(*I));
 991
 992     BitVector expNumbers(VN.size());
 993     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
 994          BI != BE; ++BI)
 995       buildsets_availout(BI, currAvail, currPhis, currExps,
 996                          currTemps, availNumbers, expNumbers);
 997
 998   }
 999
1000   // If function has no exit blocks, only perform GVN
1001   PostDominatorTree &PDT = getAnalysis<PostDominatorTree>();
1002   if (PDT[&F.getEntryBlock()] == 0) {
1003     bool changed_function = elimination();
1004     cleanup();
1005
1006     if (changed_function)
1007       return 2;  // Bailed early, made changes
1008     else
1009       return 1;  // Bailed early, no changes
1010   }
1011
1012
1013   // Phase 1, Part 2: calculate ANTIC_IN
1014
1015   std::set<BasicBlock*> visited;
1016
1017   bool changed = true;
1018   unsigned iterations = 0;
1019   while (changed) {
1020     changed = false;
1021     SmallPtrSet<Value*, 32> anticOut;
1022
1023     // Top-down walk of the postdominator tree
1024     for (df_iterator<DomTreeNode*> PDI =
1025          df_begin(PDT.getRootNode()), E = df_end(PDT.getRootNode());
1026          PDI != E; ++PDI) {
1027       BasicBlock* BB = PDI->getBlock();
1028       if (BB == 0)
1029         continue;
1030
1031
1032
1033       unsigned ret = buildsets_anticin(BB, anticOut, generatedTemporaries[BB],
1034                                    generatedExpressions[BB], visited);
1035
1036       if (ret == 0) {
1037         changed = true;
1038         break;
1039       } else {
1040         visited.insert(BB);
1041         changed |= (ret == 2);
1042       }
1043     }
1044
1045     iterations++;
1046   }
1047
1048   return 0; // No bail, no changes
1049 }
1050
1051 /// insertion_pre - When a partial redundancy has been identified, eliminate it
1052 /// by inserting appropriate values into the predecessors and a phi node in
1053 /// the main block
1054 void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
1055                            std::map<BasicBlock*, Value*>& avail,
1056                            SmallPtrSet<Value*, 32>& new_set) {
1057   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1058     Value* e2 = avail[*PI];
1059     if (!find_leader(availableOut[*PI], VN.lookup(e2))) {
1060       User* U = cast<User>(e2);
1061
1062       Value* s1 = 0;
1063       if (isa<BinaryOperator>(U->getOperand(0)) ||
1064           isa<CmpInst>(U->getOperand(0)))
1065         s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1066       else
1067         s1 = U->getOperand(0);
1068
1069       Value* s2 = 0;
1070       if (isa<BinaryOperator>(U->getOperand(1)) ||
1071           isa<CmpInst>(U->getOperand(1)))
1072         s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1073       else
1074         s2 = U->getOperand(1);
1075
1076       Value* newVal = 0;
1077       if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1078         newVal = BinaryOperator::create(BO->getOpcode(), s1, s2,
1079                                         BO->getName()+".gvnpre",
1080                                         (*PI)->getTerminator());
1081       else if (CmpInst* C = dyn_cast<CmpInst>(U))
1082         newVal = CmpInst::create(C->getOpcode(), C->getPredicate(), s1, s2,
1083                                  C->getName()+".gvnpre",
1084                                  (*PI)->getTerminator());
1085
1086       VN.add(newVal, VN.lookup(U));
1087
1088       SmallPtrSet<Value*, 32>& predAvail = availableOut[*PI];
1089       val_replace(predAvail, newVal);
1090
1091       std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1092       if (av != avail.end())
1093         avail.erase(av);
1094       avail.insert(std::make_pair(*PI, newVal));
1095
1096       ++NumInsertedVals;
1097     }
1098   }
1099
1100   PHINode* p = 0;
1101
1102   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1103     if (p == 0)
1104       p = new PHINode(avail[*PI]->getType(), "gvnpre-join", BB->begin());
1105
1106     p->addIncoming(avail[*PI], *PI);
1107   }
1108
1109   VN.add(p, VN.lookup(e));
1110   val_replace(availableOut[BB], p);
1111   new_set.insert(p);
1112
1113   ++NumInsertedPhis;
1114 }
1115
1116 /// insertion_mergepoint - When walking the dom tree, check at each merge
1117 /// block for the possibility of a partial redundancy.  If present, eliminate it
1118 unsigned GVNPRE::insertion_mergepoint(std::vector<Value*>& workList,
1119                                       df_iterator<DomTreeNode*>& D,
1120                                       SmallPtrSet<Value*, 32>& new_set) {
1121   bool changed_function = false;
1122   bool new_stuff = false;
1123
1124   BasicBlock* BB = D->getBlock();
1125   for (unsigned i = 0; i < workList.size(); ++i) {
1126     Value* e = workList[i];
1127
1128     if (isa<BinaryOperator>(e) || isa<CmpInst>(e)) {
1129       if (find_leader(availableOut[D->getIDom()->getBlock()],
1130                       VN.lookup(e)) != 0)
1131         continue;
1132
1133       std::map<BasicBlock*, Value*> avail;
1134       bool by_some = false;
1135       int num_avail = 0;
1136
1137       for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1138            ++PI) {
1139         Value *e2 = phi_translate(e, *PI, BB);
1140         Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1141
1142         if (e3 == 0) {
1143           std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1144           if (av != avail.end())
1145             avail.erase(av);
1146           avail.insert(std::make_pair(*PI, e2));
1147         } else {
1148           std::map<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1149           if (av != avail.end())
1150             avail.erase(av);
1151           avail.insert(std::make_pair(*PI, e3));
1152
1153           by_some = true;
1154           num_avail++;
1155         }
1156       }
1157
1158       if (by_some && num_avail < std::distance(pred_begin(BB), pred_end(BB))) {
1159         insertion_pre(e, BB, avail, new_set);
1160
1161         changed_function = true;
1162         new_stuff = true;
1163       }
1164     }
1165   }
1166
1167   unsigned retval = 0;
1168   if (changed_function)
1169     retval += 1;
1170   if (new_stuff)
1171     retval += 2;
1172
1173   return retval;
1174 }
1175
1176 /// insert - Phase 2 of the main algorithm.  Walk the dominator tree looking for
1177 /// merge points.  When one is found, check for a partial redundancy.  If one is
1178 /// present, eliminate it.  Repeat this walk until no changes are made.
1179 bool GVNPRE::insertion(Function& F) {
1180   bool changed_function = false;
1181
1182   DominatorTree &DT = getAnalysis<DominatorTree>();
1183
1184   std::map<BasicBlock*, SmallPtrSet<Value*, 32> > new_sets;
1185   bool new_stuff = true;
1186   while (new_stuff) {
1187     new_stuff = false;
1188     for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1189          E = df_end(DT.getRootNode()); DI != E; ++DI) {
1190       BasicBlock* BB = DI->getBlock();
1191
1192       if (BB == 0)
1193         continue;
1194
1195       SmallPtrSet<Value*, 32>& new_set = new_sets[BB];
1196       SmallPtrSet<Value*, 32>& availOut = availableOut[BB];
1197       SmallPtrSet<Value*, 32>& anticIn = anticipatedIn[BB];
1198
1199       new_set.clear();
1200
1201       // Replace leaders with leaders inherited from dominator
1202       if (DI->getIDom() != 0) {
1203         SmallPtrSet<Value*, 32>& dom_set = new_sets[DI->getIDom()->getBlock()];
1204         for (SmallPtrSet<Value*, 32>::iterator I = dom_set.begin(),
1205              E = dom_set.end(); I != E; ++I) {
1206           new_set.insert(*I);
1207           val_replace(availOut, *I);
1208         }
1209       }
1210
1211       // If there is more than one predecessor...
1212       if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
1213         std::vector<Value*> workList;
1214         workList.reserve(anticIn.size());
1215         topo_sort(anticIn, workList);
1216
1217         DOUT << "Merge Block: " << BB->getName() << "\n";
1218         DOUT << "ANTIC_IN: ";
1219         dump(anticIn);
1220         DOUT << "\n";
1221
1222         unsigned result = insertion_mergepoint(workList, DI, new_set);
1223         if (result & 1)
1224           changed_function = true;
1225         if (result & 2)
1226           new_stuff = true;
1227       }
1228     }
1229   }
1230
1231   return changed_function;
1232 }
1233
1234 // GVNPRE::runOnFunction - This is the main transformation entry point for a
1235 // function.
1236 //
1237 bool GVNPRE::runOnFunction(Function &F) {
1238   // Clean out global sets from any previous functions
1239   VN.clear();
1240   createdExpressions.clear();
1241   availableOut.clear();
1242   anticipatedIn.clear();
1243
1244   bool changed_function = false;
1245
1246   // Phase 1: BuildSets
1247   // This phase calculates the AVAIL_OUT and ANTIC_IN sets
1248   // NOTE: If full postdom information is no available, this will bail
1249   // early, performing GVN but not PRE
1250   unsigned bail = buildsets(F);
1251   //If a bail occurred, terminate early
1252   if (bail != 0)
1253     return (bail == 2);
1254
1255   // Phase 2: Insert
1256   // This phase inserts values to make partially redundant values
1257   // fully redundant
1258   changed_function |= insertion(F);
1259
1260   // Phase 3: Eliminate
1261   // This phase performs trivial full redundancy elimination
1262   changed_function |= elimination();
1263
1264   // Phase 4: Cleanup
1265   // This phase cleans up values that were created solely
1266   // as leaders for expressions
1267   cleanup();
1268
1269   return changed_function;
1270 }