lib/Transforms/Scalar/GVNPRE.cpp

   1 //===- GVNPRE.cpp - Eliminate redundant values and expressions ------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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 // Note that this pass does the value numbering itself, it does not use the
  20 // ValueNumbering analysis passes.
  21 //
  22 //===----------------------------------------------------------------------===//
  23
  24 #define DEBUG_TYPE "gvnpre"
  25 #include "llvm/Value.h"
  26 #include "llvm/Transforms/Scalar.h"
  27 #include "llvm/Instructions.h"
  28 #include "llvm/Function.h"
  29 #include "llvm/DerivedTypes.h"
  30 #include "llvm/Analysis/Dominators.h"
  31 #include "llvm/ADT/BitVector.h"
  32 #include "llvm/ADT/DenseMap.h"
  33 #include "llvm/ADT/DepthFirstIterator.h"
  34 #include "llvm/ADT/PostOrderIterator.h"
  35 #include "llvm/ADT/SmallPtrSet.h"
  36 #include "llvm/ADT/SmallVector.h"
  37 #include "llvm/ADT/Statistic.h"
  38 #include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
  39 #include "llvm/Support/CFG.h"
  40 #include "llvm/Support/Debug.h"
  41 #include "llvm/Support/ErrorHandling.h"
  42 #include <algorithm>
  43 #include <deque>
  44 #include <map>
  45 using namespace llvm;
  46
  47 //===----------------------------------------------------------------------===//
  48 //                         ValueTable Class
  49 //===----------------------------------------------------------------------===//
  50
  51 namespace {
  52
  53 /// This class holds the mapping between values and value numbers.  It is used
  54 /// as an efficient mechanism to determine the expression-wise equivalence of
  55 /// two values.
  56
  57 struct Expression {
  58   enum ExpressionOpcode { ADD, FADD, SUB, FSUB, MUL, FMUL,
  59                           UDIV, SDIV, FDIV, UREM, SREM,
  60                           FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
  61                           ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
  62                           ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
  63                           FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
  64                           FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
  65                           FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
  66                           SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
  67                           FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
  68                           PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY,
  69                           TOMBSTONE };
  70
  71   ExpressionOpcode opcode;
  72   const Type* type;
  73   uint32_t firstVN;
  74   uint32_t secondVN;
  75   uint32_t thirdVN;
  76   SmallVector<uint32_t, 4> varargs;
  77
  78   Expression() { }
  79   explicit Expression(ExpressionOpcode o) : opcode(o) { }
  80
  81   bool operator==(const Expression &other) const {
  82     if (opcode != other.opcode)
  83       return false;
  84     else if (opcode == EMPTY || opcode == TOMBSTONE)
  85       return true;
  86     else if (type != other.type)
  87       return false;
  88     else if (firstVN != other.firstVN)
  89       return false;
  90     else if (secondVN != other.secondVN)
  91       return false;
  92     else if (thirdVN != other.thirdVN)
  93       return false;
  94     else {
  95       if (varargs.size() != other.varargs.size())
  96         return false;
  97
  98       for (size_t i = 0; i < varargs.size(); ++i)
  99         if (varargs[i] != other.varargs[i])
 100           return false;
 101
 102       return true;
 103     }
 104   }
 105
 106   bool operator!=(const Expression &other) const {
 107     if (opcode != other.opcode)
 108       return true;
 109     else if (opcode == EMPTY || opcode == TOMBSTONE)
 110       return false;
 111     else if (type != other.type)
 112       return true;
 113     else if (firstVN != other.firstVN)
 114       return true;
 115     else if (secondVN != other.secondVN)
 116       return true;
 117     else if (thirdVN != other.thirdVN)
 118       return true;
 119     else {
 120       if (varargs.size() != other.varargs.size())
 121         return true;
 122
 123       for (size_t i = 0; i < varargs.size(); ++i)
 124         if (varargs[i] != other.varargs[i])
 125           return true;
 126
 127       return false;
 128     }
 129   }
 130 };
 131
 132 }
 133
 134 namespace {
 135   class ValueTable {
 136     private:
 137       DenseMap<Value*, uint32_t> valueNumbering;
 138       DenseMap<Expression, uint32_t> expressionNumbering;
 139
 140       uint32_t nextValueNumber;
 141
 142       Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
 143       Expression::ExpressionOpcode getOpcode(CmpInst* C);
 144       Expression::ExpressionOpcode getOpcode(CastInst* C);
 145       Expression create_expression(BinaryOperator* BO);
 146       Expression create_expression(CmpInst* C);
 147       Expression create_expression(ShuffleVectorInst* V);
 148       Expression create_expression(ExtractElementInst* C);
 149       Expression create_expression(InsertElementInst* V);
 150       Expression create_expression(SelectInst* V);
 151       Expression create_expression(CastInst* C);
 152       Expression create_expression(GetElementPtrInst* G);
 153     public:
 154       ValueTable() { nextValueNumber = 1; }
 155       uint32_t lookup_or_add(Value* V);
 156       uint32_t lookup(Value* V) const;
 157       void add(Value* V, uint32_t num);
 158       void clear();
 159       void erase(Value* v);
 160       unsigned size();
 161   };
 162 }
 163
 164 namespace llvm {
 165 template <> struct DenseMapInfo<Expression> {
 166   static inline Expression getEmptyKey() {
 167     return Expression(Expression::EMPTY);
 168   }
 169
 170   static inline Expression getTombstoneKey() {
 171     return Expression(Expression::TOMBSTONE);
 172   }
 173
 174   static unsigned getHashValue(const Expression e) {
 175     unsigned hash = e.opcode;
 176
 177     hash = e.firstVN + hash * 37;
 178     hash = e.secondVN + hash * 37;
 179     hash = e.thirdVN + hash * 37;
 180
 181     hash = ((unsigned)((uintptr_t)e.type >> 4) ^
 182             (unsigned)((uintptr_t)e.type >> 9)) +
 183            hash * 37;
 184
 185     for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(),
 186          E = e.varargs.end(); I != E; ++I)
 187       hash = *I + hash * 37;
 188
 189     return hash;
 190   }
 191   static bool isEqual(const Expression &LHS, const Expression &RHS) {
 192     return LHS == RHS;
 193   }
 194   static bool isPod() { return true; }
 195 };
 196 }
 197
 198 //===----------------------------------------------------------------------===//
 199 //                     ValueTable Internal Functions
 200 //===----------------------------------------------------------------------===//
 201 Expression::ExpressionOpcode
 202                              ValueTable::getOpcode(BinaryOperator* BO) {
 203   switch(BO->getOpcode()) {
 204     case Instruction::Add:
 205       return Expression::ADD;
 206     case Instruction::FAdd:
 207       return Expression::FADD;
 208     case Instruction::Sub:
 209       return Expression::SUB;
 210     case Instruction::FSub:
 211       return Expression::FSUB;
 212     case Instruction::Mul:
 213       return Expression::MUL;
 214     case Instruction::FMul:
 215       return Expression::FMUL;
 216     case Instruction::UDiv:
 217       return Expression::UDIV;
 218     case Instruction::SDiv:
 219       return Expression::SDIV;
 220     case Instruction::FDiv:
 221       return Expression::FDIV;
 222     case Instruction::URem:
 223       return Expression::UREM;
 224     case Instruction::SRem:
 225       return Expression::SREM;
 226     case Instruction::FRem:
 227       return Expression::FREM;
 228     case Instruction::Shl:
 229       return Expression::SHL;
 230     case Instruction::LShr:
 231       return Expression::LSHR;
 232     case Instruction::AShr:
 233       return Expression::ASHR;
 234     case Instruction::And:
 235       return Expression::AND;
 236     case Instruction::Or:
 237       return Expression::OR;
 238     case Instruction::Xor:
 239       return Expression::XOR;
 240
 241     // THIS SHOULD NEVER HAPPEN
 242     default:
 243       llvm_unreachable("Binary operator with unknown opcode?");
 244       return Expression::ADD;
 245   }
 246 }
 247
 248 Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
 249   if (C->getOpcode() == Instruction::ICmp) {
 250     switch (C->getPredicate()) {
 251       case ICmpInst::ICMP_EQ:
 252         return Expression::ICMPEQ;
 253       case ICmpInst::ICMP_NE:
 254         return Expression::ICMPNE;
 255       case ICmpInst::ICMP_UGT:
 256         return Expression::ICMPUGT;
 257       case ICmpInst::ICMP_UGE:
 258         return Expression::ICMPUGE;
 259       case ICmpInst::ICMP_ULT:
 260         return Expression::ICMPULT;
 261       case ICmpInst::ICMP_ULE:
 262         return Expression::ICMPULE;
 263       case ICmpInst::ICMP_SGT:
 264         return Expression::ICMPSGT;
 265       case ICmpInst::ICMP_SGE:
 266         return Expression::ICMPSGE;
 267       case ICmpInst::ICMP_SLT:
 268         return Expression::ICMPSLT;
 269       case ICmpInst::ICMP_SLE:
 270         return Expression::ICMPSLE;
 271
 272       // THIS SHOULD NEVER HAPPEN
 273       default:
 274         llvm_unreachable("Comparison with unknown predicate?");
 275         return Expression::ICMPEQ;
 276     }
 277   } else {
 278     switch (C->getPredicate()) {
 279       case FCmpInst::FCMP_OEQ:
 280         return Expression::FCMPOEQ;
 281       case FCmpInst::FCMP_OGT:
 282         return Expression::FCMPOGT;
 283       case FCmpInst::FCMP_OGE:
 284         return Expression::FCMPOGE;
 285       case FCmpInst::FCMP_OLT:
 286         return Expression::FCMPOLT;
 287       case FCmpInst::FCMP_OLE:
 288         return Expression::FCMPOLE;
 289       case FCmpInst::FCMP_ONE:
 290         return Expression::FCMPONE;
 291       case FCmpInst::FCMP_ORD:
 292         return Expression::FCMPORD;
 293       case FCmpInst::FCMP_UNO:
 294         return Expression::FCMPUNO;
 295       case FCmpInst::FCMP_UEQ:
 296         return Expression::FCMPUEQ;
 297       case FCmpInst::FCMP_UGT:
 298         return Expression::FCMPUGT;
 299       case FCmpInst::FCMP_UGE:
 300         return Expression::FCMPUGE;
 301       case FCmpInst::FCMP_ULT:
 302         return Expression::FCMPULT;
 303       case FCmpInst::FCMP_ULE:
 304         return Expression::FCMPULE;
 305       case FCmpInst::FCMP_UNE:
 306         return Expression::FCMPUNE;
 307
 308       // THIS SHOULD NEVER HAPPEN
 309       default:
 310         llvm_unreachable("Comparison with unknown predicate?");
 311         return Expression::FCMPOEQ;
 312     }
 313   }
 314 }
 315
 316 Expression::ExpressionOpcode
 317                              ValueTable::getOpcode(CastInst* C) {
 318   switch(C->getOpcode()) {
 319     case Instruction::Trunc:
 320       return Expression::TRUNC;
 321     case Instruction::ZExt:
 322       return Expression::ZEXT;
 323     case Instruction::SExt:
 324       return Expression::SEXT;
 325     case Instruction::FPToUI:
 326       return Expression::FPTOUI;
 327     case Instruction::FPToSI:
 328       return Expression::FPTOSI;
 329     case Instruction::UIToFP:
 330       return Expression::UITOFP;
 331     case Instruction::SIToFP:
 332       return Expression::SITOFP;
 333     case Instruction::FPTrunc:
 334       return Expression::FPTRUNC;
 335     case Instruction::FPExt:
 336       return Expression::FPEXT;
 337     case Instruction::PtrToInt:
 338       return Expression::PTRTOINT;
 339     case Instruction::IntToPtr:
 340       return Expression::INTTOPTR;
 341     case Instruction::BitCast:
 342       return Expression::BITCAST;
 343
 344     // THIS SHOULD NEVER HAPPEN
 345     default:
 346       llvm_unreachable("Cast operator with unknown opcode?");
 347       return Expression::BITCAST;
 348   }
 349 }
 350
 351 Expression ValueTable::create_expression(BinaryOperator* BO) {
 352   Expression e;
 353
 354   e.firstVN = lookup_or_add(BO->getOperand(0));
 355   e.secondVN = lookup_or_add(BO->getOperand(1));
 356   e.thirdVN = 0;
 357   e.type = BO->getType();
 358   e.opcode = getOpcode(BO);
 359
 360   return e;
 361 }
 362
 363 Expression ValueTable::create_expression(CmpInst* C) {
 364   Expression e;
 365
 366   e.firstVN = lookup_or_add(C->getOperand(0));
 367   e.secondVN = lookup_or_add(C->getOperand(1));
 368   e.thirdVN = 0;
 369   e.type = C->getType();
 370   e.opcode = getOpcode(C);
 371
 372   return e;
 373 }
 374
 375 Expression ValueTable::create_expression(CastInst* C) {
 376   Expression e;
 377
 378   e.firstVN = lookup_or_add(C->getOperand(0));
 379   e.secondVN = 0;
 380   e.thirdVN = 0;
 381   e.type = C->getType();
 382   e.opcode = getOpcode(C);
 383
 384   return e;
 385 }
 386
 387 Expression ValueTable::create_expression(ShuffleVectorInst* S) {
 388   Expression e;
 389
 390   e.firstVN = lookup_or_add(S->getOperand(0));
 391   e.secondVN = lookup_or_add(S->getOperand(1));
 392   e.thirdVN = lookup_or_add(S->getOperand(2));
 393   e.type = S->getType();
 394   e.opcode = Expression::SHUFFLE;
 395
 396   return e;
 397 }
 398
 399 Expression ValueTable::create_expression(ExtractElementInst* E) {
 400   Expression e;
 401
 402   e.firstVN = lookup_or_add(E->getOperand(0));
 403   e.secondVN = lookup_or_add(E->getOperand(1));
 404   e.thirdVN = 0;
 405   e.type = E->getType();
 406   e.opcode = Expression::EXTRACT;
 407
 408   return e;
 409 }
 410
 411 Expression ValueTable::create_expression(InsertElementInst* I) {
 412   Expression e;
 413
 414   e.firstVN = lookup_or_add(I->getOperand(0));
 415   e.secondVN = lookup_or_add(I->getOperand(1));
 416   e.thirdVN = lookup_or_add(I->getOperand(2));
 417   e.type = I->getType();
 418   e.opcode = Expression::INSERT;
 419
 420   return e;
 421 }
 422
 423 Expression ValueTable::create_expression(SelectInst* I) {
 424   Expression e;
 425
 426   e.firstVN = lookup_or_add(I->getCondition());
 427   e.secondVN = lookup_or_add(I->getTrueValue());
 428   e.thirdVN = lookup_or_add(I->getFalseValue());
 429   e.type = I->getType();
 430   e.opcode = Expression::SELECT;
 431
 432   return e;
 433 }
 434
 435 Expression ValueTable::create_expression(GetElementPtrInst* G) {
 436   Expression e;
 437
 438   e.firstVN = lookup_or_add(G->getPointerOperand());
 439   e.secondVN = 0;
 440   e.thirdVN = 0;
 441   e.type = G->getType();
 442   e.opcode = Expression::GEP;
 443
 444   for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
 445        I != E; ++I)
 446     e.varargs.push_back(lookup_or_add(*I));
 447
 448   return e;
 449 }
 450
 451 //===----------------------------------------------------------------------===//
 452 //                     ValueTable External Functions
 453 //===----------------------------------------------------------------------===//
 454
 455 /// lookup_or_add - Returns the value number for the specified value, assigning
 456 /// it a new number if it did not have one before.
 457 uint32_t ValueTable::lookup_or_add(Value* V) {
 458   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 459   if (VI != valueNumbering.end())
 460     return VI->second;
 461
 462
 463   if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
 464     Expression e = create_expression(BO);
 465
 466     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 467     if (EI != expressionNumbering.end()) {
 468       valueNumbering.insert(std::make_pair(V, EI->second));
 469       return EI->second;
 470     } else {
 471       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 472       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 473
 474       return nextValueNumber++;
 475     }
 476   } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
 477     Expression e = create_expression(C);
 478
 479     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 480     if (EI != expressionNumbering.end()) {
 481       valueNumbering.insert(std::make_pair(V, EI->second));
 482       return EI->second;
 483     } else {
 484       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 485       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 486
 487       return nextValueNumber++;
 488     }
 489   } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) {
 490     Expression e = create_expression(U);
 491
 492     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 493     if (EI != expressionNumbering.end()) {
 494       valueNumbering.insert(std::make_pair(V, EI->second));
 495       return EI->second;
 496     } else {
 497       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 498       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 499
 500       return nextValueNumber++;
 501     }
 502   } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) {
 503     Expression e = create_expression(U);
 504
 505     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 506     if (EI != expressionNumbering.end()) {
 507       valueNumbering.insert(std::make_pair(V, EI->second));
 508       return EI->second;
 509     } else {
 510       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 511       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 512
 513       return nextValueNumber++;
 514     }
 515   } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) {
 516     Expression e = create_expression(U);
 517
 518     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 519     if (EI != expressionNumbering.end()) {
 520       valueNumbering.insert(std::make_pair(V, EI->second));
 521       return EI->second;
 522     } else {
 523       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 524       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 525
 526       return nextValueNumber++;
 527     }
 528   } else if (SelectInst* U = dyn_cast<SelectInst>(V)) {
 529     Expression e = create_expression(U);
 530
 531     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 532     if (EI != expressionNumbering.end()) {
 533       valueNumbering.insert(std::make_pair(V, EI->second));
 534       return EI->second;
 535     } else {
 536       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 537       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 538
 539       return nextValueNumber++;
 540     }
 541   } else if (CastInst* U = dyn_cast<CastInst>(V)) {
 542     Expression e = create_expression(U);
 543
 544     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 545     if (EI != expressionNumbering.end()) {
 546       valueNumbering.insert(std::make_pair(V, EI->second));
 547       return EI->second;
 548     } else {
 549       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 550       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 551
 552       return nextValueNumber++;
 553     }
 554   } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
 555     Expression e = create_expression(U);
 556
 557     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 558     if (EI != expressionNumbering.end()) {
 559       valueNumbering.insert(std::make_pair(V, EI->second));
 560       return EI->second;
 561     } else {
 562       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 563       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 564
 565       return nextValueNumber++;
 566     }
 567   } else {
 568     valueNumbering.insert(std::make_pair(V, nextValueNumber));
 569     return nextValueNumber++;
 570   }
 571 }
 572
 573 /// lookup - Returns the value number of the specified value. Fails if
 574 /// the value has not yet been numbered.
 575 uint32_t ValueTable::lookup(Value* V) const {
 576   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 577   if (VI != valueNumbering.end())
 578     return VI->second;
 579   else
 580     llvm_unreachable("Value not numbered?");
 581
 582   return 0;
 583 }
 584
 585 /// add - Add the specified value with the given value number, removing
 586 /// its old number, if any
 587 void ValueTable::add(Value* V, uint32_t num) {
 588   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 589   if (VI != valueNumbering.end())
 590     valueNumbering.erase(VI);
 591   valueNumbering.insert(std::make_pair(V, num));
 592 }
 593
 594 /// clear - Remove all entries from the ValueTable
 595 void ValueTable::clear() {
 596   valueNumbering.clear();
 597   expressionNumbering.clear();
 598   nextValueNumber = 1;
 599 }
 600
 601 /// erase - Remove a value from the value numbering
 602 void ValueTable::erase(Value* V) {
 603   valueNumbering.erase(V);
 604 }
 605
 606 /// size - Return the number of assigned value numbers
 607 unsigned ValueTable::size() {
 608   // NOTE: zero is never assigned
 609   return nextValueNumber;
 610 }
 611
 612 namespace {
 613
 614 //===----------------------------------------------------------------------===//
 615 //                       ValueNumberedSet Class
 616 //===----------------------------------------------------------------------===//
 617
 618 class ValueNumberedSet {
 619   private:
 620     SmallPtrSet<Value*, 8> contents;
 621     BitVector numbers;
 622   public:
 623     ValueNumberedSet() { numbers.resize(1); }
 624     ValueNumberedSet(const ValueNumberedSet& other) {
 625       numbers = other.numbers;
 626       contents = other.contents;
 627     }
 628
 629     typedef SmallPtrSet<Value*, 8>::iterator iterator;
 630
 631     iterator begin() { return contents.begin(); }
 632     iterator end() { return contents.end(); }
 633
 634     bool insert(Value* v) { return contents.insert(v); }
 635     void insert(iterator I, iterator E) { contents.insert(I, E); }
 636     void erase(Value* v) { contents.erase(v); }
 637     unsigned count(Value* v) { return contents.count(v); }
 638     size_t size() { return contents.size(); }
 639
 640     void set(unsigned i)  {
 641       if (i >= numbers.size())
 642         numbers.resize(i+1);
 643
 644       numbers.set(i);
 645     }
 646
 647     void operator=(const ValueNumberedSet& other) {
 648       contents = other.contents;
 649       numbers = other.numbers;
 650     }
 651
 652     void reset(unsigned i)  {
 653       if (i < numbers.size())
 654         numbers.reset(i);
 655     }
 656
 657     bool test(unsigned i)  {
 658       if (i >= numbers.size())
 659         return false;
 660
 661       return numbers.test(i);
 662     }
 663
 664     void clear() {
 665       contents.clear();
 666       numbers.clear();
 667     }
 668 };
 669
 670 }
 671
 672 //===----------------------------------------------------------------------===//
 673 //                         GVNPRE Pass
 674 //===----------------------------------------------------------------------===//
 675
 676 namespace {
 677   class GVNPRE : public FunctionPass {
 678     bool runOnFunction(Function &F);
 679   public:
 680     static char ID; // Pass identification, replacement for typeid
 681     GVNPRE() : FunctionPass(&ID) {}
 682
 683   private:
 684     ValueTable VN;
 685     SmallVector<Instruction*, 8> createdExpressions;
 686
 687     DenseMap<BasicBlock*, ValueNumberedSet> availableOut;
 688     DenseMap<BasicBlock*, ValueNumberedSet> anticipatedIn;
 689     DenseMap<BasicBlock*, ValueNumberedSet> generatedPhis;
 690
 691     // This transformation requires dominator postdominator info
 692     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 693       AU.setPreservesCFG();
 694       AU.addRequiredID(BreakCriticalEdgesID);
 695       AU.addRequired<UnifyFunctionExitNodes>();
 696       AU.addRequired<DominatorTree>();
 697     }
 698
 699     // Helper fuctions
 700     // FIXME: eliminate or document these better
 701     void dump(ValueNumberedSet& s) const ;
 702     void clean(ValueNumberedSet& set) ;
 703     Value* find_leader(ValueNumberedSet& vals, uint32_t v) ;
 704     Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) ;
 705     void phi_translate_set(ValueNumberedSet& anticIn, BasicBlock* pred,
 706                            BasicBlock* succ, ValueNumberedSet& out) ;
 707
 708     void topo_sort(ValueNumberedSet& set,
 709                    SmallVector<Value*, 8>& vec) ;
 710
 711     void cleanup() ;
 712     bool elimination() ;
 713
 714     void val_insert(ValueNumberedSet& s, Value* v) ;
 715     void val_replace(ValueNumberedSet& s, Value* v) ;
 716     bool dependsOnInvoke(Value* V) ;
 717     void buildsets_availout(BasicBlock::iterator I,
 718                             ValueNumberedSet& currAvail,
 719                             ValueNumberedSet& currPhis,
 720                             ValueNumberedSet& currExps,
 721                             SmallPtrSet<Value*, 16>& currTemps);
 722     bool buildsets_anticout(BasicBlock* BB,
 723                             ValueNumberedSet& anticOut,
 724                             SmallPtrSet<BasicBlock*, 8>& visited);
 725     unsigned buildsets_anticin(BasicBlock* BB,
 726                            ValueNumberedSet& anticOut,
 727                            ValueNumberedSet& currExps,
 728                            SmallPtrSet<Value*, 16>& currTemps,
 729                            SmallPtrSet<BasicBlock*, 8>& visited);
 730     void buildsets(Function& F) ;
 731
 732     void insertion_pre(Value* e, BasicBlock* BB,
 733                        DenseMap<BasicBlock*, Value*>& avail,
 734                        std::map<BasicBlock*,ValueNumberedSet>& new_set);
 735     unsigned insertion_mergepoint(SmallVector<Value*, 8>& workList,
 736                                   df_iterator<DomTreeNode*>& D,
 737                       std::map<BasicBlock*, ValueNumberedSet>& new_set);
 738     bool insertion(Function& F) ;
 739
 740   };
 741
 742   char GVNPRE::ID = 0;
 743
 744 }
 745
 746 // createGVNPREPass - The public interface to this file...
 747 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
 748
 749 static RegisterPass<GVNPRE> X("gvnpre",
 750                       "Global Value Numbering/Partial Redundancy Elimination");
 751
 752
 753 STATISTIC(NumInsertedVals, "Number of values inserted");
 754 STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
 755 STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
 756
 757 /// find_leader - Given a set and a value number, return the first
 758 /// element of the set with that value number, or 0 if no such element
 759 /// is present
 760 Value* GVNPRE::find_leader(ValueNumberedSet& vals, uint32_t v) {
 761   if (!vals.test(v))
 762     return 0;
 763
 764   for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end();
 765        I != E; ++I)
 766     if (v == VN.lookup(*I))
 767       return *I;
 768
 769   llvm_unreachable("No leader found, but present bit is set?");
 770   return 0;
 771 }
 772
 773 /// val_insert - Insert a value into a set only if there is not a value
 774 /// with the same value number already in the set
 775 void GVNPRE::val_insert(ValueNumberedSet& s, Value* v) {
 776   uint32_t num = VN.lookup(v);
 777   if (!s.test(num))
 778     s.insert(v);
 779 }
 780
 781 /// val_replace - Insert a value into a set, replacing any values already in
 782 /// the set that have the same value number
 783 void GVNPRE::val_replace(ValueNumberedSet& s, Value* v) {
 784   if (s.count(v)) return;
 785
 786   uint32_t num = VN.lookup(v);
 787   Value* leader = find_leader(s, num);
 788   if (leader != 0)
 789     s.erase(leader);
 790   s.insert(v);
 791   s.set(num);
 792 }
 793
 794 /// phi_translate - Given a value, its parent block, and a predecessor of its
 795 /// parent, translate the value into legal for the predecessor block.  This
 796 /// means translating its operands (and recursively, their operands) through
 797 /// any phi nodes in the parent into values available in the predecessor
 798 Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
 799   if (V == 0)
 800     return 0;
 801
 802   // Unary Operations
 803   if (CastInst* U = dyn_cast<CastInst>(V)) {
 804     Value* newOp1 = 0;
 805     if (isa<Instruction>(U->getOperand(0)))
 806       newOp1 = phi_translate(U->getOperand(0), pred, succ);
 807     else
 808       newOp1 = U->getOperand(0);
 809
 810     if (newOp1 == 0)
 811       return 0;
 812
 813     if (newOp1 != U->getOperand(0)) {
 814       Instruction* newVal = 0;
 815       if (CastInst* C = dyn_cast<CastInst>(U))
 816         newVal = CastInst::Create(C->getOpcode(),
 817                                   newOp1, C->getType(),
 818                                   C->getName()+".expr");
 819
 820       uint32_t v = VN.lookup_or_add(newVal);
 821
 822       Value* leader = find_leader(availableOut[pred], v);
 823       if (leader == 0) {
 824         createdExpressions.push_back(newVal);
 825         return newVal;
 826       } else {
 827         VN.erase(newVal);
 828         delete newVal;
 829         return leader;
 830       }
 831     }
 832
 833   // Binary Operations
 834   } if (isa<BinaryOperator>(V) || isa<CmpInst>(V) ||
 835       isa<ExtractElementInst>(V)) {
 836     User* U = cast<User>(V);
 837
 838     Value* newOp1 = 0;
 839     if (isa<Instruction>(U->getOperand(0)))
 840       newOp1 = phi_translate(U->getOperand(0), pred, succ);
 841     else
 842       newOp1 = U->getOperand(0);
 843
 844     if (newOp1 == 0)
 845       return 0;
 846
 847     Value* newOp2 = 0;
 848     if (isa<Instruction>(U->getOperand(1)))
 849       newOp2 = phi_translate(U->getOperand(1), pred, succ);
 850     else
 851       newOp2 = U->getOperand(1);
 852
 853     if (newOp2 == 0)
 854       return 0;
 855
 856     if (newOp1 != U->getOperand(0) || newOp2 != U->getOperand(1)) {
 857       Instruction* newVal = 0;
 858       if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
 859         newVal = BinaryOperator::Create(BO->getOpcode(),
 860                                         newOp1, newOp2,
 861                                         BO->getName()+".expr");
 862       else if (CmpInst* C = dyn_cast<CmpInst>(U))
 863         newVal = CmpInst::Create(C->getOpcode(),
 864                                  C->getPredicate(),
 865                                  newOp1, newOp2,
 866                                  C->getName()+".expr");
 867       else if (ExtractElementInst* E = dyn_cast<ExtractElementInst>(U))
 868         newVal = ExtractElementInst::Create(newOp1, newOp2,
 869                                             E->getName()+".expr");
 870
 871       uint32_t v = VN.lookup_or_add(newVal);
 872
 873       Value* leader = find_leader(availableOut[pred], v);
 874       if (leader == 0) {
 875         createdExpressions.push_back(newVal);
 876         return newVal;
 877       } else {
 878         VN.erase(newVal);
 879         delete newVal;
 880         return leader;
 881       }
 882     }
 883
 884   // Ternary Operations
 885   } else if (isa<ShuffleVectorInst>(V) || isa<InsertElementInst>(V) ||
 886              isa<SelectInst>(V)) {
 887     User* U = cast<User>(V);
 888
 889     Value* newOp1 = 0;
 890     if (isa<Instruction>(U->getOperand(0)))
 891       newOp1 = phi_translate(U->getOperand(0), pred, succ);
 892     else
 893       newOp1 = U->getOperand(0);
 894
 895     if (newOp1 == 0)
 896       return 0;
 897
 898     Value* newOp2 = 0;
 899     if (isa<Instruction>(U->getOperand(1)))
 900       newOp2 = phi_translate(U->getOperand(1), pred, succ);
 901     else
 902       newOp2 = U->getOperand(1);
 903
 904     if (newOp2 == 0)
 905       return 0;
 906
 907     Value* newOp3 = 0;
 908     if (isa<Instruction>(U->getOperand(2)))
 909       newOp3 = phi_translate(U->getOperand(2), pred, succ);
 910     else
 911       newOp3 = U->getOperand(2);
 912
 913     if (newOp3 == 0)
 914       return 0;
 915
 916     if (newOp1 != U->getOperand(0) ||
 917         newOp2 != U->getOperand(1) ||
 918         newOp3 != U->getOperand(2)) {
 919       Instruction* newVal = 0;
 920       if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
 921         newVal = new ShuffleVectorInst(newOp1, newOp2, newOp3,
 922                                        S->getName() + ".expr");
 923       else if (InsertElementInst* I = dyn_cast<InsertElementInst>(U))
 924         newVal = InsertElementInst::Create(newOp1, newOp2, newOp3,
 925                                            I->getName() + ".expr");
 926       else if (SelectInst* I = dyn_cast<SelectInst>(U))
 927         newVal = SelectInst::Create(newOp1, newOp2, newOp3,
 928                                     I->getName() + ".expr");
 929
 930       uint32_t v = VN.lookup_or_add(newVal);
 931
 932       Value* leader = find_leader(availableOut[pred], v);
 933       if (leader == 0) {
 934         createdExpressions.push_back(newVal);
 935         return newVal;
 936       } else {
 937         VN.erase(newVal);
 938         delete newVal;
 939         return leader;
 940       }
 941     }
 942
 943   // Varargs operators
 944   } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
 945     Value* newOp1 = 0;
 946     if (isa<Instruction>(U->getPointerOperand()))
 947       newOp1 = phi_translate(U->getPointerOperand(), pred, succ);
 948     else
 949       newOp1 = U->getPointerOperand();
 950
 951     if (newOp1 == 0)
 952       return 0;
 953
 954     bool changed_idx = false;
 955     SmallVector<Value*, 4> newIdx;
 956     for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
 957          I != E; ++I)
 958       if (isa<Instruction>(*I)) {
 959         Value* newVal = phi_translate(*I, pred, succ);
 960         newIdx.push_back(newVal);
 961         if (newVal != *I)
 962           changed_idx = true;
 963       } else {
 964         newIdx.push_back(*I);
 965       }
 966
 967     if (newOp1 != U->getPointerOperand() || changed_idx) {
 968       Instruction* newVal =
 969           GetElementPtrInst::Create(newOp1,
 970                                     newIdx.begin(), newIdx.end(),
 971                                     U->getName()+".expr");
 972
 973       uint32_t v = VN.lookup_or_add(newVal);
 974
 975       Value* leader = find_leader(availableOut[pred], v);
 976       if (leader == 0) {
 977         createdExpressions.push_back(newVal);
 978         return newVal;
 979       } else {
 980         VN.erase(newVal);
 981         delete newVal;
 982         return leader;
 983       }
 984     }
 985
 986   // PHI Nodes
 987   } else if (PHINode* P = dyn_cast<PHINode>(V)) {
 988     if (P->getParent() == succ)
 989       return P->getIncomingValueForBlock(pred);
 990   }
 991
 992   return V;
 993 }
 994
 995 /// phi_translate_set - Perform phi translation on every element of a set
 996 void GVNPRE::phi_translate_set(ValueNumberedSet& anticIn,
 997                               BasicBlock* pred, BasicBlock* succ,
 998                               ValueNumberedSet& out) {
 999   for (ValueNumberedSet::iterator I = anticIn.begin(),
1000        E = anticIn.end(); I != E; ++I) {
1001     Value* V = phi_translate(*I, pred, succ);
1002     if (V != 0 && !out.test(VN.lookup_or_add(V))) {
1003       out.insert(V);
1004       out.set(VN.lookup(V));
1005     }
1006   }
1007 }
1008
1009 /// dependsOnInvoke - Test if a value has an phi node as an operand, any of
1010 /// whose inputs is an invoke instruction.  If this is true, we cannot safely
1011 /// PRE the instruction or anything that depends on it.
1012 bool GVNPRE::dependsOnInvoke(Value* V) {
1013   if (PHINode* p = dyn_cast<PHINode>(V)) {
1014     for (PHINode::op_iterator I = p->op_begin(), E = p->op_end(); I != E; ++I)
1015       if (isa<InvokeInst>(*I))
1016         return true;
1017     return false;
1018   } else {
1019     return false;
1020   }
1021 }
1022
1023 /// clean - Remove all non-opaque values from the set whose operands are not
1024 /// themselves in the set, as well as all values that depend on invokes (see
1025 /// above)
1026 void GVNPRE::clean(ValueNumberedSet& set) {
1027   SmallVector<Value*, 8> worklist;
1028   worklist.reserve(set.size());
1029   topo_sort(set, worklist);
1030
1031   for (unsigned i = 0; i < worklist.size(); ++i) {
1032     Value* v = worklist[i];
1033
1034     // Handle unary ops
1035     if (CastInst* U = dyn_cast<CastInst>(v)) {
1036       bool lhsValid = !isa<Instruction>(U->getOperand(0));
1037       lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1038       if (lhsValid)
1039         lhsValid = !dependsOnInvoke(U->getOperand(0));
1040
1041       if (!lhsValid) {
1042         set.erase(U);
1043         set.reset(VN.lookup(U));
1044       }
1045
1046     // Handle binary ops
1047     } else if (isa<BinaryOperator>(v) || isa<CmpInst>(v) ||
1048         isa<ExtractElementInst>(v)) {
1049       User* U = cast<User>(v);
1050
1051       bool lhsValid = !isa<Instruction>(U->getOperand(0));
1052       lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1053       if (lhsValid)
1054         lhsValid = !dependsOnInvoke(U->getOperand(0));
1055
1056       bool rhsValid = !isa<Instruction>(U->getOperand(1));
1057       rhsValid |= set.test(VN.lookup(U->getOperand(1)));
1058       if (rhsValid)
1059         rhsValid = !dependsOnInvoke(U->getOperand(1));
1060
1061       if (!lhsValid || !rhsValid) {
1062         set.erase(U);
1063         set.reset(VN.lookup(U));
1064       }
1065
1066     // Handle ternary ops
1067     } else if (isa<ShuffleVectorInst>(v) || isa<InsertElementInst>(v) ||
1068                isa<SelectInst>(v)) {
1069       User* U = cast<User>(v);
1070
1071       bool lhsValid = !isa<Instruction>(U->getOperand(0));
1072       lhsValid |= set.test(VN.lookup(U->getOperand(0)));
1073       if (lhsValid)
1074         lhsValid = !dependsOnInvoke(U->getOperand(0));
1075
1076       bool rhsValid = !isa<Instruction>(U->getOperand(1));
1077       rhsValid |= set.test(VN.lookup(U->getOperand(1)));
1078       if (rhsValid)
1079         rhsValid = !dependsOnInvoke(U->getOperand(1));
1080
1081       bool thirdValid = !isa<Instruction>(U->getOperand(2));
1082       thirdValid |= set.test(VN.lookup(U->getOperand(2)));
1083       if (thirdValid)
1084         thirdValid = !dependsOnInvoke(U->getOperand(2));
1085
1086       if (!lhsValid || !rhsValid || !thirdValid) {
1087         set.erase(U);
1088         set.reset(VN.lookup(U));
1089       }
1090
1091     // Handle varargs ops
1092     } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(v)) {
1093       bool ptrValid = !isa<Instruction>(U->getPointerOperand());
1094       ptrValid |= set.test(VN.lookup(U->getPointerOperand()));
1095       if (ptrValid)
1096         ptrValid = !dependsOnInvoke(U->getPointerOperand());
1097
1098       bool varValid = true;
1099       for (GetElementPtrInst::op_iterator I = U->idx_begin(), E = U->idx_end();
1100            I != E; ++I)
1101         if (varValid) {
1102           varValid &= !isa<Instruction>(*I) || set.test(VN.lookup(*I));
1103           varValid &= !dependsOnInvoke(*I);
1104         }
1105
1106       if (!ptrValid || !varValid) {
1107         set.erase(U);
1108         set.reset(VN.lookup(U));
1109       }
1110     }
1111   }
1112 }
1113
1114 /// topo_sort - Given a set of values, sort them by topological
1115 /// order into the provided vector.
1116 void GVNPRE::topo_sort(ValueNumberedSet& set, SmallVector<Value*, 8>& vec) {
1117   SmallPtrSet<Value*, 16> visited;
1118   SmallVector<Value*, 8> stack;
1119   for (ValueNumberedSet::iterator I = set.begin(), E = set.end();
1120        I != E; ++I) {
1121     if (visited.count(*I) == 0)
1122       stack.push_back(*I);
1123
1124     while (!stack.empty()) {
1125       Value* e = stack.back();
1126
1127       // Handle unary ops
1128       if (CastInst* U = dyn_cast<CastInst>(e)) {
1129         Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1130
1131         if (l != 0 && isa<Instruction>(l) &&
1132             visited.count(l) == 0)
1133           stack.push_back(l);
1134         else {
1135           vec.push_back(e);
1136           visited.insert(e);
1137           stack.pop_back();
1138         }
1139
1140       // Handle binary ops
1141       } else if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1142           isa<ExtractElementInst>(e)) {
1143         User* U = cast<User>(e);
1144         Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1145         Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
1146
1147         if (l != 0 && isa<Instruction>(l) &&
1148             visited.count(l) == 0)
1149           stack.push_back(l);
1150         else if (r != 0 && isa<Instruction>(r) &&
1151                  visited.count(r) == 0)
1152           stack.push_back(r);
1153         else {
1154           vec.push_back(e);
1155           visited.insert(e);
1156           stack.pop_back();
1157         }
1158
1159       // Handle ternary ops
1160       } else if (isa<InsertElementInst>(e) || isa<ShuffleVectorInst>(e) ||
1161                  isa<SelectInst>(e)) {
1162         User* U = cast<User>(e);
1163         Value* l = find_leader(set, VN.lookup(U->getOperand(0)));
1164         Value* r = find_leader(set, VN.lookup(U->getOperand(1)));
1165         Value* m = find_leader(set, VN.lookup(U->getOperand(2)));
1166
1167         if (l != 0 && isa<Instruction>(l) &&
1168             visited.count(l) == 0)
1169           stack.push_back(l);
1170         else if (r != 0 && isa<Instruction>(r) &&
1171                  visited.count(r) == 0)
1172           stack.push_back(r);
1173         else if (m != 0 && isa<Instruction>(m) &&
1174                  visited.count(m) == 0)
1175           stack.push_back(m);
1176         else {
1177           vec.push_back(e);
1178           visited.insert(e);
1179           stack.pop_back();
1180         }
1181
1182       // Handle vararg ops
1183       } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(e)) {
1184         Value* p = find_leader(set, VN.lookup(U->getPointerOperand()));
1185
1186         if (p != 0 && isa<Instruction>(p) &&
1187             visited.count(p) == 0)
1188           stack.push_back(p);
1189         else {
1190           bool push_va = false;
1191           for (GetElementPtrInst::op_iterator I = U->idx_begin(),
1192                E = U->idx_end(); I != E; ++I) {
1193             Value * v = find_leader(set, VN.lookup(*I));
1194             if (v != 0 && isa<Instruction>(v) && visited.count(v) == 0) {
1195               stack.push_back(v);
1196               push_va = true;
1197             }
1198           }
1199
1200           if (!push_va) {
1201             vec.push_back(e);
1202             visited.insert(e);
1203             stack.pop_back();
1204           }
1205         }
1206
1207       // Handle opaque ops
1208       } else {
1209         visited.insert(e);
1210         vec.push_back(e);
1211         stack.pop_back();
1212       }
1213     }
1214
1215     stack.clear();
1216   }
1217 }
1218
1219 /// dump - Dump a set of values to standard error
1220 void GVNPRE::dump(ValueNumberedSet& s) const {
1221   DEBUG(errs() << "{ ");
1222   for (ValueNumberedSet::iterator I = s.begin(), E = s.end();
1223        I != E; ++I) {
1224     DEBUG(errs() << "" << VN.lookup(*I) << ": ");
1225     DEBUG((*I)->dump());
1226   }
1227   DEBUG(errs() << "}\n\n");
1228 }
1229
1230 /// elimination - Phase 3 of the main algorithm.  Perform full redundancy
1231 /// elimination by walking the dominator tree and removing any instruction that
1232 /// is dominated by another instruction with the same value number.
1233 bool GVNPRE::elimination() {
1234   bool changed_function = false;
1235
1236   SmallVector<std::pair<Instruction*, Value*>, 8> replace;
1237   SmallVector<Instruction*, 8> erase;
1238
1239   DominatorTree& DT = getAnalysis<DominatorTree>();
1240
1241   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1242          E = df_end(DT.getRootNode()); DI != E; ++DI) {
1243     BasicBlock* BB = DI->getBlock();
1244
1245     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1246          BI != BE; ++BI) {
1247
1248       if (isa<BinaryOperator>(BI) || isa<CmpInst>(BI) ||
1249           isa<ShuffleVectorInst>(BI) || isa<InsertElementInst>(BI) ||
1250           isa<ExtractElementInst>(BI) || isa<SelectInst>(BI) ||
1251           isa<CastInst>(BI) || isa<GetElementPtrInst>(BI)) {
1252
1253         if (availableOut[BB].test(VN.lookup(BI)) &&
1254             !availableOut[BB].count(BI)) {
1255           Value *leader = find_leader(availableOut[BB], VN.lookup(BI));
1256           if (Instruction* Instr = dyn_cast<Instruction>(leader))
1257             if (Instr->getParent() != 0 && Instr != BI) {
1258               replace.push_back(std::make_pair(BI, leader));
1259               erase.push_back(BI);
1260               ++NumEliminated;
1261             }
1262         }
1263       }
1264     }
1265   }
1266
1267   while (!replace.empty()) {
1268     std::pair<Instruction*, Value*> rep = replace.back();
1269     replace.pop_back();
1270     rep.first->replaceAllUsesWith(rep.second);
1271     changed_function = true;
1272   }
1273
1274   for (SmallVector<Instruction*, 8>::iterator I = erase.begin(),
1275        E = erase.end(); I != E; ++I)
1276      (*I)->eraseFromParent();
1277
1278   return changed_function;
1279 }
1280
1281 /// cleanup - Delete any extraneous values that were created to represent
1282 /// expressions without leaders.
1283 void GVNPRE::cleanup() {
1284   while (!createdExpressions.empty()) {
1285     Instruction* I = createdExpressions.back();
1286     createdExpressions.pop_back();
1287
1288     delete I;
1289   }
1290 }
1291
1292 /// buildsets_availout - When calculating availability, handle an instruction
1293 /// by inserting it into the appropriate sets
1294 void GVNPRE::buildsets_availout(BasicBlock::iterator I,
1295                                 ValueNumberedSet& currAvail,
1296                                 ValueNumberedSet& currPhis,
1297                                 ValueNumberedSet& currExps,
1298                                 SmallPtrSet<Value*, 16>& currTemps) {
1299   // Handle PHI nodes
1300   if (PHINode* p = dyn_cast<PHINode>(I)) {
1301     unsigned num = VN.lookup_or_add(p);
1302
1303     currPhis.insert(p);
1304     currPhis.set(num);
1305
1306   // Handle unary ops
1307   } else if (CastInst* U = dyn_cast<CastInst>(I)) {
1308     Value* leftValue = U->getOperand(0);
1309
1310     unsigned num = VN.lookup_or_add(U);
1311
1312     if (isa<Instruction>(leftValue))
1313       if (!currExps.test(VN.lookup(leftValue))) {
1314         currExps.insert(leftValue);
1315         currExps.set(VN.lookup(leftValue));
1316       }
1317
1318     if (!currExps.test(num)) {
1319       currExps.insert(U);
1320       currExps.set(num);
1321     }
1322
1323   // Handle binary ops
1324   } else if (isa<BinaryOperator>(I) || isa<CmpInst>(I) ||
1325              isa<ExtractElementInst>(I)) {
1326     User* U = cast<User>(I);
1327     Value* leftValue = U->getOperand(0);
1328     Value* rightValue = U->getOperand(1);
1329
1330     unsigned num = VN.lookup_or_add(U);
1331
1332     if (isa<Instruction>(leftValue))
1333       if (!currExps.test(VN.lookup(leftValue))) {
1334         currExps.insert(leftValue);
1335         currExps.set(VN.lookup(leftValue));
1336       }
1337
1338     if (isa<Instruction>(rightValue))
1339       if (!currExps.test(VN.lookup(rightValue))) {
1340         currExps.insert(rightValue);
1341         currExps.set(VN.lookup(rightValue));
1342       }
1343
1344     if (!currExps.test(num)) {
1345       currExps.insert(U);
1346       currExps.set(num);
1347     }
1348
1349   // Handle ternary ops
1350   } else if (isa<InsertElementInst>(I) || isa<ShuffleVectorInst>(I) ||
1351              isa<SelectInst>(I)) {
1352     User* U = cast<User>(I);
1353     Value* leftValue = U->getOperand(0);
1354     Value* rightValue = U->getOperand(1);
1355     Value* thirdValue = U->getOperand(2);
1356
1357     VN.lookup_or_add(U);
1358
1359     unsigned num = VN.lookup_or_add(U);
1360
1361     if (isa<Instruction>(leftValue))
1362       if (!currExps.test(VN.lookup(leftValue))) {
1363         currExps.insert(leftValue);
1364         currExps.set(VN.lookup(leftValue));
1365       }
1366     if (isa<Instruction>(rightValue))
1367       if (!currExps.test(VN.lookup(rightValue))) {
1368         currExps.insert(rightValue);
1369         currExps.set(VN.lookup(rightValue));
1370       }
1371     if (isa<Instruction>(thirdValue))
1372       if (!currExps.test(VN.lookup(thirdValue))) {
1373         currExps.insert(thirdValue);
1374         currExps.set(VN.lookup(thirdValue));
1375       }
1376
1377     if (!currExps.test(num)) {
1378       currExps.insert(U);
1379       currExps.set(num);
1380     }
1381
1382   // Handle vararg ops
1383   } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(I)) {
1384     Value* ptrValue = U->getPointerOperand();
1385
1386     VN.lookup_or_add(U);
1387
1388     unsigned num = VN.lookup_or_add(U);
1389
1390     if (isa<Instruction>(ptrValue))
1391       if (!currExps.test(VN.lookup(ptrValue))) {
1392         currExps.insert(ptrValue);
1393         currExps.set(VN.lookup(ptrValue));
1394       }
1395
1396     for (GetElementPtrInst::op_iterator OI = U->idx_begin(), OE = U->idx_end();
1397          OI != OE; ++OI)
1398       if (isa<Instruction>(*OI) && !currExps.test(VN.lookup(*OI))) {
1399         currExps.insert(*OI);
1400         currExps.set(VN.lookup(*OI));
1401       }
1402
1403     if (!currExps.test(VN.lookup(U))) {
1404       currExps.insert(U);
1405       currExps.set(num);
1406     }
1407
1408   // Handle opaque ops
1409   } else if (!I->isTerminator()){
1410     VN.lookup_or_add(I);
1411
1412     currTemps.insert(I);
1413   }
1414
1415   if (!I->isTerminator())
1416     if (!currAvail.test(VN.lookup(I))) {
1417       currAvail.insert(I);
1418       currAvail.set(VN.lookup(I));
1419     }
1420 }
1421
1422 /// buildsets_anticout - When walking the postdom tree, calculate the ANTIC_OUT
1423 /// set as a function of the ANTIC_IN set of the block's predecessors
1424 bool GVNPRE::buildsets_anticout(BasicBlock* BB,
1425                                 ValueNumberedSet& anticOut,
1426                                 SmallPtrSet<BasicBlock*, 8>& visited) {
1427   if (BB->getTerminator()->getNumSuccessors() == 1) {
1428     if (BB->getTerminator()->getSuccessor(0) != BB &&
1429         visited.count(BB->getTerminator()->getSuccessor(0)) == 0) {
1430       return true;
1431     }
1432     else {
1433       phi_translate_set(anticipatedIn[BB->getTerminator()->getSuccessor(0)],
1434                         BB,  BB->getTerminator()->getSuccessor(0), anticOut);
1435     }
1436   } else if (BB->getTerminator()->getNumSuccessors() > 1) {
1437     BasicBlock* first = BB->getTerminator()->getSuccessor(0);
1438     for (ValueNumberedSet::iterator I = anticipatedIn[first].begin(),
1439          E = anticipatedIn[first].end(); I != E; ++I) {
1440       anticOut.insert(*I);
1441       anticOut.set(VN.lookup(*I));
1442     }
1443
1444     for (unsigned i = 1; i < BB->getTerminator()->getNumSuccessors(); ++i) {
1445       BasicBlock* currSucc = BB->getTerminator()->getSuccessor(i);
1446       ValueNumberedSet& succAnticIn = anticipatedIn[currSucc];
1447
1448       SmallVector<Value*, 16> temp;
1449
1450       for (ValueNumberedSet::iterator I = anticOut.begin(),
1451            E = anticOut.end(); I != E; ++I)
1452         if (!succAnticIn.test(VN.lookup(*I)))
1453           temp.push_back(*I);
1454
1455       for (SmallVector<Value*, 16>::iterator I = temp.begin(), E = temp.end();
1456            I != E; ++I) {
1457         anticOut.erase(*I);
1458         anticOut.reset(VN.lookup(*I));
1459       }
1460     }
1461   }
1462
1463   return false;
1464 }
1465
1466 /// buildsets_anticin - Walk the postdom tree, calculating ANTIC_OUT for
1467 /// each block.  ANTIC_IN is then a function of ANTIC_OUT and the GEN
1468 /// sets populated in buildsets_availout
1469 unsigned GVNPRE::buildsets_anticin(BasicBlock* BB,
1470                                ValueNumberedSet& anticOut,
1471                                ValueNumberedSet& currExps,
1472                                SmallPtrSet<Value*, 16>& currTemps,
1473                                SmallPtrSet<BasicBlock*, 8>& visited) {
1474   ValueNumberedSet& anticIn = anticipatedIn[BB];
1475   unsigned old = anticIn.size();
1476
1477   bool defer = buildsets_anticout(BB, anticOut, visited);
1478   if (defer)
1479     return 0;
1480
1481   anticIn.clear();
1482
1483   for (ValueNumberedSet::iterator I = anticOut.begin(),
1484        E = anticOut.end(); I != E; ++I) {
1485     anticIn.insert(*I);
1486     anticIn.set(VN.lookup(*I));
1487   }
1488   for (ValueNumberedSet::iterator I = currExps.begin(),
1489        E = currExps.end(); I != E; ++I) {
1490     if (!anticIn.test(VN.lookup(*I))) {
1491       anticIn.insert(*I);
1492       anticIn.set(VN.lookup(*I));
1493     }
1494   }
1495
1496   for (SmallPtrSet<Value*, 16>::iterator I = currTemps.begin(),
1497        E = currTemps.end(); I != E; ++I) {
1498     anticIn.erase(*I);
1499     anticIn.reset(VN.lookup(*I));
1500   }
1501
1502   clean(anticIn);
1503   anticOut.clear();
1504
1505   if (old != anticIn.size())
1506     return 2;
1507   else
1508     return 1;
1509 }
1510
1511 /// buildsets - Phase 1 of the main algorithm.  Construct the AVAIL_OUT
1512 /// and the ANTIC_IN sets.
1513 void GVNPRE::buildsets(Function& F) {
1514   DenseMap<BasicBlock*, ValueNumberedSet> generatedExpressions;
1515   DenseMap<BasicBlock*, SmallPtrSet<Value*, 16> > generatedTemporaries;
1516
1517   DominatorTree &DT = getAnalysis<DominatorTree>();
1518
1519   // Phase 1, Part 1: calculate AVAIL_OUT
1520
1521   // Top-down walk of the dominator tree
1522   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1523          E = df_end(DT.getRootNode()); DI != E; ++DI) {
1524
1525     // Get the sets to update for this block
1526     ValueNumberedSet& currExps = generatedExpressions[DI->getBlock()];
1527     ValueNumberedSet& currPhis = generatedPhis[DI->getBlock()];
1528     SmallPtrSet<Value*, 16>& currTemps = generatedTemporaries[DI->getBlock()];
1529     ValueNumberedSet& currAvail = availableOut[DI->getBlock()];
1530
1531     BasicBlock* BB = DI->getBlock();
1532
1533     // A block inherits AVAIL_OUT from its dominator
1534     if (DI->getIDom() != 0)
1535       currAvail = availableOut[DI->getIDom()->getBlock()];
1536
1537     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1538          BI != BE; ++BI)
1539       buildsets_availout(BI, currAvail, currPhis, currExps,
1540                          currTemps);
1541
1542   }
1543
1544   // Phase 1, Part 2: calculate ANTIC_IN
1545
1546   SmallPtrSet<BasicBlock*, 8> visited;
1547   SmallPtrSet<BasicBlock*, 4> block_changed;
1548   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI)
1549     block_changed.insert(FI);
1550
1551   bool changed = true;
1552   unsigned iterations = 0;
1553
1554   while (changed) {
1555     changed = false;
1556     ValueNumberedSet anticOut;
1557
1558     // Postorder walk of the CFG
1559     for (po_iterator<BasicBlock*> BBI = po_begin(&F.getEntryBlock()),
1560          BBE = po_end(&F.getEntryBlock()); BBI != BBE; ++BBI) {
1561       BasicBlock* BB = *BBI;
1562
1563       if (block_changed.count(BB) != 0) {
1564         unsigned ret = buildsets_anticin(BB, anticOut,generatedExpressions[BB],
1565                                          generatedTemporaries[BB], visited);
1566
1567         if (ret == 0) {
1568           changed = true;
1569           continue;
1570         } else {
1571           visited.insert(BB);
1572
1573           if (ret == 2)
1574            for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1575                  PI != PE; ++PI) {
1576               block_changed.insert(*PI);
1577            }
1578           else
1579             block_changed.erase(BB);
1580
1581           changed |= (ret == 2);
1582         }
1583       }
1584     }
1585
1586     iterations++;
1587   }
1588 }
1589
1590 /// insertion_pre - When a partial redundancy has been identified, eliminate it
1591 /// by inserting appropriate values into the predecessors and a phi node in
1592 /// the main block
1593 void GVNPRE::insertion_pre(Value* e, BasicBlock* BB,
1594                            DenseMap<BasicBlock*, Value*>& avail,
1595                     std::map<BasicBlock*, ValueNumberedSet>& new_sets) {
1596   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1597     Value* e2 = avail[*PI];
1598     if (!availableOut[*PI].test(VN.lookup(e2))) {
1599       User* U = cast<User>(e2);
1600
1601       Value* s1 = 0;
1602       if (isa<BinaryOperator>(U->getOperand(0)) ||
1603           isa<CmpInst>(U->getOperand(0)) ||
1604           isa<ShuffleVectorInst>(U->getOperand(0)) ||
1605           isa<ExtractElementInst>(U->getOperand(0)) ||
1606           isa<InsertElementInst>(U->getOperand(0)) ||
1607           isa<SelectInst>(U->getOperand(0)) ||
1608           isa<CastInst>(U->getOperand(0)) ||
1609           isa<GetElementPtrInst>(U->getOperand(0)))
1610         s1 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(0)));
1611       else
1612         s1 = U->getOperand(0);
1613
1614       Value* s2 = 0;
1615
1616       if (isa<BinaryOperator>(U) ||
1617           isa<CmpInst>(U) ||
1618           isa<ShuffleVectorInst>(U) ||
1619           isa<ExtractElementInst>(U) ||
1620           isa<InsertElementInst>(U) ||
1621           isa<SelectInst>(U)) {
1622         if (isa<BinaryOperator>(U->getOperand(1)) ||
1623             isa<CmpInst>(U->getOperand(1)) ||
1624             isa<ShuffleVectorInst>(U->getOperand(1)) ||
1625             isa<ExtractElementInst>(U->getOperand(1)) ||
1626             isa<InsertElementInst>(U->getOperand(1)) ||
1627             isa<SelectInst>(U->getOperand(1)) ||
1628             isa<CastInst>(U->getOperand(1)) ||
1629             isa<GetElementPtrInst>(U->getOperand(1))) {
1630           s2 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(1)));
1631         } else {
1632           s2 = U->getOperand(1);
1633         }
1634       }
1635
1636       // Ternary Operators
1637       Value* s3 = 0;
1638       if (isa<ShuffleVectorInst>(U) ||
1639           isa<InsertElementInst>(U) ||
1640           isa<SelectInst>(U)) {
1641         if (isa<BinaryOperator>(U->getOperand(2)) ||
1642             isa<CmpInst>(U->getOperand(2)) ||
1643             isa<ShuffleVectorInst>(U->getOperand(2)) ||
1644             isa<ExtractElementInst>(U->getOperand(2)) ||
1645             isa<InsertElementInst>(U->getOperand(2)) ||
1646             isa<SelectInst>(U->getOperand(2)) ||
1647             isa<CastInst>(U->getOperand(2)) ||
1648             isa<GetElementPtrInst>(U->getOperand(2))) {
1649           s3 = find_leader(availableOut[*PI], VN.lookup(U->getOperand(2)));
1650         } else {
1651           s3 = U->getOperand(2);
1652         }
1653       }
1654
1655       // Vararg operators
1656       SmallVector<Value*, 4> sVarargs;
1657       if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U)) {
1658         for (GetElementPtrInst::op_iterator OI = G->idx_begin(),
1659              OE = G->idx_end(); OI != OE; ++OI) {
1660           if (isa<BinaryOperator>(*OI) ||
1661               isa<CmpInst>(*OI) ||
1662               isa<ShuffleVectorInst>(*OI) ||
1663               isa<ExtractElementInst>(*OI) ||
1664               isa<InsertElementInst>(*OI) ||
1665               isa<SelectInst>(*OI) ||
1666               isa<CastInst>(*OI) ||
1667               isa<GetElementPtrInst>(*OI)) {
1668             sVarargs.push_back(find_leader(availableOut[*PI],
1669                                VN.lookup(*OI)));
1670           } else {
1671             sVarargs.push_back(*OI);
1672           }
1673         }
1674       }
1675
1676       Value* newVal = 0;
1677       if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
1678         newVal = BinaryOperator::Create(BO->getOpcode(), s1, s2,
1679                                         BO->getName()+".gvnpre",
1680                                         (*PI)->getTerminator());
1681       else if (CmpInst* C = dyn_cast<CmpInst>(U))
1682         newVal = CmpInst::Create(C->getOpcode(),
1683                                  C->getPredicate(), s1, s2,
1684                                  C->getName()+".gvnpre",
1685                                  (*PI)->getTerminator());
1686       else if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
1687         newVal = new ShuffleVectorInst(s1, s2, s3, S->getName()+".gvnpre",
1688                                        (*PI)->getTerminator());
1689       else if (InsertElementInst* S = dyn_cast<InsertElementInst>(U))
1690         newVal = InsertElementInst::Create(s1, s2, s3, S->getName()+".gvnpre",
1691                                            (*PI)->getTerminator());
1692       else if (ExtractElementInst* S = dyn_cast<ExtractElementInst>(U))
1693         newVal = ExtractElementInst::Create(s1, s2, S->getName()+".gvnpre",
1694                                         (*PI)->getTerminator());
1695       else if (SelectInst* S = dyn_cast<SelectInst>(U))
1696         newVal = SelectInst::Create(s1, s2, s3, S->getName()+".gvnpre",
1697                                     (*PI)->getTerminator());
1698       else if (CastInst* C = dyn_cast<CastInst>(U))
1699         newVal = CastInst::Create(C->getOpcode(), s1, C->getType(),
1700                                   C->getName()+".gvnpre",
1701                                   (*PI)->getTerminator());
1702       else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U))
1703         newVal = GetElementPtrInst::Create(s1, sVarargs.begin(), sVarargs.end(),
1704                                            G->getName()+".gvnpre",
1705                                            (*PI)->getTerminator());
1706
1707       VN.add(newVal, VN.lookup(U));
1708
1709       ValueNumberedSet& predAvail = availableOut[*PI];
1710       val_replace(predAvail, newVal);
1711       val_replace(new_sets[*PI], newVal);
1712       predAvail.set(VN.lookup(newVal));
1713
1714       DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1715       if (av != avail.end())
1716         avail.erase(av);
1717       avail.insert(std::make_pair(*PI, newVal));
1718
1719       ++NumInsertedVals;
1720     }
1721   }
1722
1723   PHINode* p = 0;
1724
1725   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1726     if (p == 0)
1727       p = PHINode::Create(avail[*PI]->getType(), "gvnpre-join", BB->begin());
1728
1729     p->addIncoming(avail[*PI], *PI);
1730   }
1731
1732   VN.add(p, VN.lookup(e));
1733   val_replace(availableOut[BB], p);
1734   availableOut[BB].set(VN.lookup(e));
1735   generatedPhis[BB].insert(p);
1736   generatedPhis[BB].set(VN.lookup(e));
1737   new_sets[BB].insert(p);
1738   new_sets[BB].set(VN.lookup(e));
1739
1740   ++NumInsertedPhis;
1741 }
1742
1743 /// insertion_mergepoint - When walking the dom tree, check at each merge
1744 /// block for the possibility of a partial redundancy.  If present, eliminate it
1745 unsigned GVNPRE::insertion_mergepoint(SmallVector<Value*, 8>& workList,
1746                                       df_iterator<DomTreeNode*>& D,
1747                     std::map<BasicBlock*, ValueNumberedSet >& new_sets) {
1748   bool changed_function = false;
1749   bool new_stuff = false;
1750
1751   BasicBlock* BB = D->getBlock();
1752   for (unsigned i = 0; i < workList.size(); ++i) {
1753     Value* e = workList[i];
1754
1755     if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1756         isa<ExtractElementInst>(e) || isa<InsertElementInst>(e) ||
1757         isa<ShuffleVectorInst>(e) || isa<SelectInst>(e) || isa<CastInst>(e) ||
1758         isa<GetElementPtrInst>(e)) {
1759       if (availableOut[D->getIDom()->getBlock()].test(VN.lookup(e)))
1760         continue;
1761
1762       DenseMap<BasicBlock*, Value*> avail;
1763       bool by_some = false;
1764       bool all_same = true;
1765       Value * first_s = 0;
1766
1767       for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1768            ++PI) {
1769         Value *e2 = phi_translate(e, *PI, BB);
1770         Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1771
1772         if (e3 == 0) {
1773           DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1774           if (av != avail.end())
1775             avail.erase(av);
1776           avail.insert(std::make_pair(*PI, e2));
1777           all_same = false;
1778         } else {
1779           DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1780           if (av != avail.end())
1781             avail.erase(av);
1782           avail.insert(std::make_pair(*PI, e3));
1783
1784           by_some = true;
1785           if (first_s == 0)
1786             first_s = e3;
1787           else if (first_s != e3)
1788             all_same = false;
1789         }
1790       }
1791
1792       if (by_some && !all_same &&
1793           !generatedPhis[BB].test(VN.lookup(e))) {
1794         insertion_pre(e, BB, avail, new_sets);
1795
1796         changed_function = true;
1797         new_stuff = true;
1798       }
1799     }
1800   }
1801
1802   unsigned retval = 0;
1803   if (changed_function)
1804     retval += 1;
1805   if (new_stuff)
1806     retval += 2;
1807
1808   return retval;
1809 }
1810
1811 /// insert - Phase 2 of the main algorithm.  Walk the dominator tree looking for
1812 /// merge points.  When one is found, check for a partial redundancy.  If one is
1813 /// present, eliminate it.  Repeat this walk until no changes are made.
1814 bool GVNPRE::insertion(Function& F) {
1815   bool changed_function = false;
1816
1817   DominatorTree &DT = getAnalysis<DominatorTree>();
1818
1819   std::map<BasicBlock*, ValueNumberedSet> new_sets;
1820   bool new_stuff = true;
1821   while (new_stuff) {
1822     new_stuff = false;
1823     for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1824          E = df_end(DT.getRootNode()); DI != E; ++DI) {
1825       BasicBlock* BB = DI->getBlock();
1826
1827       if (BB == 0)
1828         continue;
1829
1830       ValueNumberedSet& availOut = availableOut[BB];
1831       ValueNumberedSet& anticIn = anticipatedIn[BB];
1832
1833       // Replace leaders with leaders inherited from dominator
1834       if (DI->getIDom() != 0) {
1835         ValueNumberedSet& dom_set = new_sets[DI->getIDom()->getBlock()];
1836         for (ValueNumberedSet::iterator I = dom_set.begin(),
1837              E = dom_set.end(); I != E; ++I) {
1838           val_replace(new_sets[BB], *I);
1839           val_replace(availOut, *I);
1840         }
1841       }
1842
1843       // If there is more than one predecessor...
1844       if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
1845         SmallVector<Value*, 8> workList;
1846         workList.reserve(anticIn.size());
1847         topo_sort(anticIn, workList);
1848
1849         unsigned result = insertion_mergepoint(workList, DI, new_sets);
1850         if (result & 1)
1851           changed_function = true;
1852         if (result & 2)
1853           new_stuff = true;
1854       }
1855     }
1856   }
1857
1858   return changed_function;
1859 }
1860
1861 // GVNPRE::runOnFunction - This is the main transformation entry point for a
1862 // function.
1863 //
1864 bool GVNPRE::runOnFunction(Function &F) {
1865   // Clean out global sets from any previous functions
1866   VN.clear();
1867   createdExpressions.clear();
1868   availableOut.clear();
1869   anticipatedIn.clear();
1870   generatedPhis.clear();
1871
1872   bool changed_function = false;
1873
1874   // Phase 1: BuildSets
1875   // This phase calculates the AVAIL_OUT and ANTIC_IN sets
1876   buildsets(F);
1877
1878   // Phase 2: Insert
1879   // This phase inserts values to make partially redundant values
1880   // fully redundant
1881   changed_function |= insertion(F);
1882
1883   // Phase 3: Eliminate
1884   // This phase performs trivial full redundancy elimination
1885   changed_function |= elimination();
1886
1887   // Phase 4: Cleanup
1888   // This phase cleans up values that were created solely
1889   // as leaders for expressions
1890   cleanup();
1891
1892   return changed_function;
1893 }