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