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