lib/Transforms/Scalar/GVNPRE.cpp

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