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/Compiler.h"
  41 #include "llvm/Support/Debug.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 VISIBILITY_HIDDEN 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       assert(0 && "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         assert(0 && "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         assert(0 && "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       assert(0 && "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     assert(0 && "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
 678   class VISIBILITY_HIDDEN GVNPRE : public FunctionPass {
 679     bool runOnFunction(Function &F);
 680   public:
 681     static char ID; // Pass identification, replacement for typeid
 682     GVNPRE() : FunctionPass(&ID) {}
 683
 684   private:
 685     ValueTable VN;
 686     SmallVector<Instruction*, 8> createdExpressions;
 687
 688     DenseMap<BasicBlock*, ValueNumberedSet> availableOut;
 689     DenseMap<BasicBlock*, ValueNumberedSet> anticipatedIn;
 690     DenseMap<BasicBlock*, ValueNumberedSet> generatedPhis;
 691
 692     // This transformation requires dominator postdominator info
 693     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 694       AU.setPreservesCFG();
 695       AU.addRequiredID(BreakCriticalEdgesID);
 696       AU.addRequired<UnifyFunctionExitNodes>();
 697       AU.addRequired<DominatorTree>();
 698     }
 699
 700     // Helper fuctions
 701     // FIXME: eliminate or document these better
 702     void dump(ValueNumberedSet& s) const ;
 703     void clean(ValueNumberedSet& set) ;
 704     Value* find_leader(ValueNumberedSet& vals, uint32_t v) ;
 705     Value* phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) ;
 706     void phi_translate_set(ValueNumberedSet& anticIn, BasicBlock* pred,
 707                            BasicBlock* succ, ValueNumberedSet& out) ;
 708
 709     void topo_sort(ValueNumberedSet& set,
 710                    SmallVector<Value*, 8>& vec) ;
 711
 712     void cleanup() ;
 713     bool elimination() ;
 714
 715     void val_insert(ValueNumberedSet& s, Value* v) ;
 716     void val_replace(ValueNumberedSet& s, Value* v) ;
 717     bool dependsOnInvoke(Value* V) ;
 718     void buildsets_availout(BasicBlock::iterator I,
 719                             ValueNumberedSet& currAvail,
 720                             ValueNumberedSet& currPhis,
 721                             ValueNumberedSet& currExps,
 722                             SmallPtrSet<Value*, 16>& currTemps);
 723     bool buildsets_anticout(BasicBlock* BB,
 724                             ValueNumberedSet& anticOut,
 725                             SmallPtrSet<BasicBlock*, 8>& visited);
 726     unsigned buildsets_anticin(BasicBlock* BB,
 727                            ValueNumberedSet& anticOut,
 728                            ValueNumberedSet& currExps,
 729                            SmallPtrSet<Value*, 16>& currTemps,
 730                            SmallPtrSet<BasicBlock*, 8>& visited);
 731     void buildsets(Function& F) ;
 732
 733     void insertion_pre(Value* e, BasicBlock* BB,
 734                        DenseMap<BasicBlock*, Value*>& avail,
 735                        std::map<BasicBlock*,ValueNumberedSet>& new_set);
 736     unsigned insertion_mergepoint(SmallVector<Value*, 8>& workList,
 737                                   df_iterator<DomTreeNode*>& D,
 738                       std::map<BasicBlock*, ValueNumberedSet>& new_set);
 739     bool insertion(Function& F) ;
 740
 741   };
 742
 743   char GVNPRE::ID = 0;
 744
 745 }
 746
 747 // createGVNPREPass - The public interface to this file...
 748 FunctionPass *llvm::createGVNPREPass() { return new GVNPRE(); }
 749
 750 static RegisterPass<GVNPRE> X("gvnpre",
 751                       "Global Value Numbering/Partial Redundancy Elimination");
 752
 753
 754 STATISTIC(NumInsertedVals, "Number of values inserted");
 755 STATISTIC(NumInsertedPhis, "Number of PHI nodes inserted");
 756 STATISTIC(NumEliminated, "Number of redundant instructions eliminated");
 757
 758 /// find_leader - Given a set and a value number, return the first
 759 /// element of the set with that value number, or 0 if no such element
 760 /// is present
 761 Value* GVNPRE::find_leader(ValueNumberedSet& vals, uint32_t v) {
 762   if (!vals.test(v))
 763     return 0;
 764
 765   for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end();
 766        I != E; ++I)
 767     if (v == VN.lookup(*I))
 768       return *I;
 769
 770   assert(0 && "No leader found, but present bit is set?");
 771   return 0;
 772 }
 773
 774 /// val_insert - Insert a value into a set only if there is not a value
 775 /// with the same value number already in the set
 776 void GVNPRE::val_insert(ValueNumberedSet& s, Value* v) {
 777   uint32_t num = VN.lookup(v);
 778   if (!s.test(num))
 779     s.insert(v);
 780 }
 781
 782 /// val_replace - Insert a value into a set, replacing any values already in
 783 /// the set that have the same value number
 784 void GVNPRE::val_replace(ValueNumberedSet& s, Value* v) {
 785   if (s.count(v)) return;
 786
 787   uint32_t num = VN.lookup(v);
 788   Value* leader = find_leader(s, num);
 789   if (leader != 0)
 790     s.erase(leader);
 791   s.insert(v);
 792   s.set(num);
 793 }
 794
 795 /// phi_translate - Given a value, its parent block, and a predecessor of its
 796 /// parent, translate the value into legal for the predecessor block.  This
 797 /// means translating its operands (and recursively, their operands) through
 798 /// any phi nodes in the parent into values available in the predecessor
 799 Value* GVNPRE::phi_translate(Value* V, BasicBlock* pred, BasicBlock* succ) {
 800   if (V == 0)
 801     return 0;
 802
 803   // Unary Operations
 804   if (CastInst* U = dyn_cast<CastInst>(V)) {
 805     Value* newOp1 = 0;
 806     if (isa<Instruction>(U->getOperand(0)))
 807       newOp1 = phi_translate(U->getOperand(0), pred, succ);
 808     else
 809       newOp1 = U->getOperand(0);
 810
 811     if (newOp1 == 0)
 812       return 0;
 813
 814     if (newOp1 != U->getOperand(0)) {
 815       Instruction* newVal = 0;
 816       if (CastInst* C = dyn_cast<CastInst>(U))
 817         newVal = CastInst::Create(C->getOpcode(),
 818                                   newOp1, C->getType(),
 819                                   C->getName()+".expr");
 820
 821       uint32_t v = VN.lookup_or_add(newVal);
 822
 823       Value* leader = find_leader(availableOut[pred], v);
 824       if (leader == 0) {
 825         createdExpressions.push_back(newVal);
 826         return newVal;
 827       } else {
 828         VN.erase(newVal);
 829         delete newVal;
 830         return leader;
 831       }
 832     }
 833
 834   // Binary Operations
 835   } if (isa<BinaryOperator>(V) || isa<CmpInst>(V) ||
 836       isa<ExtractElementInst>(V)) {
 837     User* U = cast<User>(V);
 838
 839     Value* newOp1 = 0;
 840     if (isa<Instruction>(U->getOperand(0)))
 841       newOp1 = phi_translate(U->getOperand(0), pred, succ);
 842     else
 843       newOp1 = U->getOperand(0);
 844
 845     if (newOp1 == 0)
 846       return 0;
 847
 848     Value* newOp2 = 0;
 849     if (isa<Instruction>(U->getOperand(1)))
 850       newOp2 = phi_translate(U->getOperand(1), pred, succ);
 851     else
 852       newOp2 = U->getOperand(1);
 853
 854     if (newOp2 == 0)
 855       return 0;
 856
 857     if (newOp1 != U->getOperand(0) || newOp2 != U->getOperand(1)) {
 858       Instruction* newVal = 0;
 859       if (BinaryOperator* BO = dyn_cast<BinaryOperator>(U))
 860         newVal = BinaryOperator::Create(BO->getOpcode(),
 861                                         newOp1, newOp2,
 862                                         BO->getName()+".expr");
 863       else if (CmpInst* C = dyn_cast<CmpInst>(U))
 864         newVal = CmpInst::Create(C->getOpcode(),
 865                                  C->getPredicate(),
 866                                  newOp1, newOp2,
 867                                  C->getName()+".expr");
 868       else if (ExtractElementInst* E = dyn_cast<ExtractElementInst>(U))
 869         newVal = new ExtractElementInst(newOp1, newOp2, 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   DOUT << "{ ";
1222   for (ValueNumberedSet::iterator I = s.begin(), E = s.end();
1223        I != E; ++I) {
1224     DOUT << "" << VN.lookup(*I) << ": ";
1225     DEBUG((*I)->dump());
1226   }
1227   DOUT << "}\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(), C->getPredicate(), s1, s2,
1683                                  C->getName()+".gvnpre",
1684                                  (*PI)->getTerminator());
1685       else if (ShuffleVectorInst* S = dyn_cast<ShuffleVectorInst>(U))
1686         newVal = new ShuffleVectorInst(s1, s2, s3, S->getName()+".gvnpre",
1687                                        (*PI)->getTerminator());
1688       else if (InsertElementInst* S = dyn_cast<InsertElementInst>(U))
1689         newVal = InsertElementInst::Create(s1, s2, s3, S->getName()+".gvnpre",
1690                                            (*PI)->getTerminator());
1691       else if (ExtractElementInst* S = dyn_cast<ExtractElementInst>(U))
1692         newVal = new ExtractElementInst(s1, s2, S->getName()+".gvnpre",
1693                                         (*PI)->getTerminator());
1694       else if (SelectInst* S = dyn_cast<SelectInst>(U))
1695         newVal = SelectInst::Create(s1, s2, s3, S->getName()+".gvnpre",
1696                                     (*PI)->getTerminator());
1697       else if (CastInst* C = dyn_cast<CastInst>(U))
1698         newVal = CastInst::Create(C->getOpcode(), s1, C->getType(),
1699                                   C->getName()+".gvnpre",
1700                                   (*PI)->getTerminator());
1701       else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(U))
1702         newVal = GetElementPtrInst::Create(s1, sVarargs.begin(), sVarargs.end(),
1703                                            G->getName()+".gvnpre",
1704                                            (*PI)->getTerminator());
1705
1706       VN.add(newVal, VN.lookup(U));
1707
1708       ValueNumberedSet& predAvail = availableOut[*PI];
1709       val_replace(predAvail, newVal);
1710       val_replace(new_sets[*PI], newVal);
1711       predAvail.set(VN.lookup(newVal));
1712
1713       DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1714       if (av != avail.end())
1715         avail.erase(av);
1716       avail.insert(std::make_pair(*PI, newVal));
1717
1718       ++NumInsertedVals;
1719     }
1720   }
1721
1722   PHINode* p = 0;
1723
1724   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
1725     if (p == 0)
1726       p = PHINode::Create(avail[*PI]->getType(), "gvnpre-join", BB->begin());
1727
1728     p->addIncoming(avail[*PI], *PI);
1729   }
1730
1731   VN.add(p, VN.lookup(e));
1732   val_replace(availableOut[BB], p);
1733   availableOut[BB].set(VN.lookup(e));
1734   generatedPhis[BB].insert(p);
1735   generatedPhis[BB].set(VN.lookup(e));
1736   new_sets[BB].insert(p);
1737   new_sets[BB].set(VN.lookup(e));
1738
1739   ++NumInsertedPhis;
1740 }
1741
1742 /// insertion_mergepoint - When walking the dom tree, check at each merge
1743 /// block for the possibility of a partial redundancy.  If present, eliminate it
1744 unsigned GVNPRE::insertion_mergepoint(SmallVector<Value*, 8>& workList,
1745                                       df_iterator<DomTreeNode*>& D,
1746                     std::map<BasicBlock*, ValueNumberedSet >& new_sets) {
1747   bool changed_function = false;
1748   bool new_stuff = false;
1749
1750   BasicBlock* BB = D->getBlock();
1751   for (unsigned i = 0; i < workList.size(); ++i) {
1752     Value* e = workList[i];
1753
1754     if (isa<BinaryOperator>(e) || isa<CmpInst>(e) ||
1755         isa<ExtractElementInst>(e) || isa<InsertElementInst>(e) ||
1756         isa<ShuffleVectorInst>(e) || isa<SelectInst>(e) || isa<CastInst>(e) ||
1757         isa<GetElementPtrInst>(e)) {
1758       if (availableOut[D->getIDom()->getBlock()].test(VN.lookup(e)))
1759         continue;
1760
1761       DenseMap<BasicBlock*, Value*> avail;
1762       bool by_some = false;
1763       bool all_same = true;
1764       Value * first_s = 0;
1765
1766       for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE;
1767            ++PI) {
1768         Value *e2 = phi_translate(e, *PI, BB);
1769         Value *e3 = find_leader(availableOut[*PI], VN.lookup(e2));
1770
1771         if (e3 == 0) {
1772           DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1773           if (av != avail.end())
1774             avail.erase(av);
1775           avail.insert(std::make_pair(*PI, e2));
1776           all_same = false;
1777         } else {
1778           DenseMap<BasicBlock*, Value*>::iterator av = avail.find(*PI);
1779           if (av != avail.end())
1780             avail.erase(av);
1781           avail.insert(std::make_pair(*PI, e3));
1782
1783           by_some = true;
1784           if (first_s == 0)
1785             first_s = e3;
1786           else if (first_s != e3)
1787             all_same = false;
1788         }
1789       }
1790
1791       if (by_some && !all_same &&
1792           !generatedPhis[BB].test(VN.lookup(e))) {
1793         insertion_pre(e, BB, avail, new_sets);
1794
1795         changed_function = true;
1796         new_stuff = true;
1797       }
1798     }
1799   }
1800
1801   unsigned retval = 0;
1802   if (changed_function)
1803     retval += 1;
1804   if (new_stuff)
1805     retval += 2;
1806
1807   return retval;
1808 }
1809
1810 /// insert - Phase 2 of the main algorithm.  Walk the dominator tree looking for
1811 /// merge points.  When one is found, check for a partial redundancy.  If one is
1812 /// present, eliminate it.  Repeat this walk until no changes are made.
1813 bool GVNPRE::insertion(Function& F) {
1814   bool changed_function = false;
1815
1816   DominatorTree &DT = getAnalysis<DominatorTree>();
1817
1818   std::map<BasicBlock*, ValueNumberedSet> new_sets;
1819   bool new_stuff = true;
1820   while (new_stuff) {
1821     new_stuff = false;
1822     for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1823          E = df_end(DT.getRootNode()); DI != E; ++DI) {
1824       BasicBlock* BB = DI->getBlock();
1825
1826       if (BB == 0)
1827         continue;
1828
1829       ValueNumberedSet& availOut = availableOut[BB];
1830       ValueNumberedSet& anticIn = anticipatedIn[BB];
1831
1832       // Replace leaders with leaders inherited from dominator
1833       if (DI->getIDom() != 0) {
1834         ValueNumberedSet& dom_set = new_sets[DI->getIDom()->getBlock()];
1835         for (ValueNumberedSet::iterator I = dom_set.begin(),
1836              E = dom_set.end(); I != E; ++I) {
1837           val_replace(new_sets[BB], *I);
1838           val_replace(availOut, *I);
1839         }
1840       }
1841
1842       // If there is more than one predecessor...
1843       if (pred_begin(BB) != pred_end(BB) && ++pred_begin(BB) != pred_end(BB)) {
1844         SmallVector<Value*, 8> workList;
1845         workList.reserve(anticIn.size());
1846         topo_sort(anticIn, workList);
1847
1848         unsigned result = insertion_mergepoint(workList, DI, new_sets);
1849         if (result & 1)
1850           changed_function = true;
1851         if (result & 2)
1852           new_stuff = true;
1853       }
1854     }
1855   }
1856
1857   return changed_function;
1858 }
1859
1860 // GVNPRE::runOnFunction - This is the main transformation entry point for a
1861 // function.
1862 //
1863 bool GVNPRE::runOnFunction(Function &F) {
1864   // Clean out global sets from any previous functions
1865   VN.clear();
1866   createdExpressions.clear();
1867   availableOut.clear();
1868   anticipatedIn.clear();
1869   generatedPhis.clear();
1870
1871   bool changed_function = false;
1872
1873   // Phase 1: BuildSets
1874   // This phase calculates the AVAIL_OUT and ANTIC_IN sets
1875   buildsets(F);
1876
1877   // Phase 2: Insert
1878   // This phase inserts values to make partially redundant values
1879   // fully redundant
1880   changed_function |= insertion(F);
1881
1882   // Phase 3: Eliminate
1883   // This phase performs trivial full redundancy elimination
1884   changed_function |= elimination();
1885
1886   // Phase 4: Cleanup
1887   // This phase cleans up values that were created solely
1888   // as leaders for expressions
1889   cleanup();
1890
1891   return changed_function;
1892 }