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