lib/Transforms/Scalar/GVNPRE.cpp

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