lib/Transforms/Scalar/GVN.cpp

   1 //===- GVN.cpp - Eliminate redundant values and loads ------------===//
   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 global value numbering to eliminate fully redundant
  11 // instructions.  It also performs simple dead load elimination.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "gvn"
  16 #include "llvm/Value.h"
  17 #include "llvm/Transforms/Scalar.h"
  18 #include "llvm/Instructions.h"
  19 #include "llvm/Function.h"
  20 #include "llvm/DerivedTypes.h"
  21 #include "llvm/Analysis/Dominators.h"
  22 #include "llvm/ADT/BitVector.h"
  23 #include "llvm/ADT/DenseMap.h"
  24 #include "llvm/ADT/DepthFirstIterator.h"
  25 #include "llvm/ADT/SmallPtrSet.h"
  26 #include "llvm/ADT/SmallVector.h"
  27 #include "llvm/ADT/Statistic.h"
  28 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
  29 #include "llvm/Support/CFG.h"
  30 #include "llvm/Support/Compiler.h"
  31 using namespace llvm;
  32
  33 //===----------------------------------------------------------------------===//
  34 //                         ValueTable Class
  35 //===----------------------------------------------------------------------===//
  36
  37 /// This class holds the mapping between values and value numbers.  It is used
  38 /// as an efficient mechanism to determine the expression-wise equivalence of
  39 /// two values.
  40 namespace {
  41   struct VISIBILITY_HIDDEN Expression {
  42     enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM,
  43                             FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
  44                             ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
  45                             ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
  46                             FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
  47                             FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
  48                             FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
  49                             SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
  50                             FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
  51                             PTRTOINT, INTTOPTR, BITCAST, GEP, EMPTY,
  52                             TOMBSTONE };
  53
  54     ExpressionOpcode opcode;
  55     const Type* type;
  56     uint32_t firstVN;
  57     uint32_t secondVN;
  58     uint32_t thirdVN;
  59     SmallVector<uint32_t, 4> varargs;
  60
  61     Expression() { }
  62     Expression(ExpressionOpcode o) : opcode(o) { }
  63
  64     bool operator==(const Expression &other) const {
  65       if (opcode != other.opcode)
  66         return false;
  67       else if (opcode == EMPTY || opcode == TOMBSTONE)
  68         return true;
  69       else if (type != other.type)
  70         return false;
  71       else if (firstVN != other.firstVN)
  72         return false;
  73       else if (secondVN != other.secondVN)
  74         return false;
  75       else if (thirdVN != other.thirdVN)
  76         return false;
  77       else {
  78         if (varargs.size() != other.varargs.size())
  79           return false;
  80
  81         for (size_t i = 0; i < varargs.size(); ++i)
  82           if (varargs[i] != other.varargs[i])
  83             return false;
  84
  85         return true;
  86       }
  87     }
  88
  89     bool operator!=(const Expression &other) const {
  90       if (opcode != other.opcode)
  91         return true;
  92       else if (opcode == EMPTY || opcode == TOMBSTONE)
  93         return false;
  94       else if (type != other.type)
  95         return true;
  96       else if (firstVN != other.firstVN)
  97         return true;
  98       else if (secondVN != other.secondVN)
  99         return true;
 100       else if (thirdVN != other.thirdVN)
 101         return true;
 102       else {
 103         if (varargs.size() != other.varargs.size())
 104           return true;
 105
 106         for (size_t i = 0; i < varargs.size(); ++i)
 107           if (varargs[i] != other.varargs[i])
 108             return true;
 109
 110           return false;
 111       }
 112     }
 113   };
 114
 115   class VISIBILITY_HIDDEN ValueTable {
 116     private:
 117       DenseMap<Value*, uint32_t> valueNumbering;
 118       DenseMap<Expression, uint32_t> expressionNumbering;
 119
 120       uint32_t nextValueNumber;
 121
 122       Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
 123       Expression::ExpressionOpcode getOpcode(CmpInst* C);
 124       Expression::ExpressionOpcode getOpcode(CastInst* C);
 125       Expression create_expression(BinaryOperator* BO);
 126       Expression create_expression(CmpInst* C);
 127       Expression create_expression(ShuffleVectorInst* V);
 128       Expression create_expression(ExtractElementInst* C);
 129       Expression create_expression(InsertElementInst* V);
 130       Expression create_expression(SelectInst* V);
 131       Expression create_expression(CastInst* C);
 132       Expression create_expression(GetElementPtrInst* G);
 133     public:
 134       ValueTable() { nextValueNumber = 1; }
 135       uint32_t lookup_or_add(Value* V);
 136       uint32_t lookup(Value* V) const;
 137       void add(Value* V, uint32_t num);
 138       void clear();
 139       void erase(Value* v);
 140       unsigned size();
 141   };
 142 }
 143
 144 namespace llvm {
 145 template <> struct DenseMapKeyInfo<Expression> {
 146   static inline Expression getEmptyKey() { return Expression(Expression::EMPTY); }
 147   static inline Expression getTombstoneKey() { return Expression(Expression::TOMBSTONE); }
 148
 149   static unsigned getHashValue(const Expression e) {
 150     unsigned hash = e.opcode;
 151
 152     hash = e.firstVN + hash * 37;
 153     hash = e.secondVN + hash * 37;
 154     hash = e.thirdVN + hash * 37;
 155
 156     hash = (unsigned)((uintptr_t)e.type >> 4) ^
 157             (unsigned)((uintptr_t)e.type >> 9) +
 158             hash * 37;
 159
 160     for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(), E = e.varargs.end();
 161          I != E; ++I)
 162       hash = *I + hash * 37;
 163
 164     return hash;
 165   }
 166   static bool isPod() { return true; }
 167 };
 168 }
 169
 170 //===----------------------------------------------------------------------===//
 171 //                     ValueTable Internal Functions
 172 //===----------------------------------------------------------------------===//
 173 Expression::ExpressionOpcode
 174                              ValueTable::getOpcode(BinaryOperator* BO) {
 175   switch(BO->getOpcode()) {
 176     case Instruction::Add:
 177       return Expression::ADD;
 178     case Instruction::Sub:
 179       return Expression::SUB;
 180     case Instruction::Mul:
 181       return Expression::MUL;
 182     case Instruction::UDiv:
 183       return Expression::UDIV;
 184     case Instruction::SDiv:
 185       return Expression::SDIV;
 186     case Instruction::FDiv:
 187       return Expression::FDIV;
 188     case Instruction::URem:
 189       return Expression::UREM;
 190     case Instruction::SRem:
 191       return Expression::SREM;
 192     case Instruction::FRem:
 193       return Expression::FREM;
 194     case Instruction::Shl:
 195       return Expression::SHL;
 196     case Instruction::LShr:
 197       return Expression::LSHR;
 198     case Instruction::AShr:
 199       return Expression::ASHR;
 200     case Instruction::And:
 201       return Expression::AND;
 202     case Instruction::Or:
 203       return Expression::OR;
 204     case Instruction::Xor:
 205       return Expression::XOR;
 206
 207     // THIS SHOULD NEVER HAPPEN
 208     default:
 209       assert(0 && "Binary operator with unknown opcode?");
 210       return Expression::ADD;
 211   }
 212 }
 213
 214 Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
 215   if (C->getOpcode() == Instruction::ICmp) {
 216     switch (C->getPredicate()) {
 217       case ICmpInst::ICMP_EQ:
 218         return Expression::ICMPEQ;
 219       case ICmpInst::ICMP_NE:
 220         return Expression::ICMPNE;
 221       case ICmpInst::ICMP_UGT:
 222         return Expression::ICMPUGT;
 223       case ICmpInst::ICMP_UGE:
 224         return Expression::ICMPUGE;
 225       case ICmpInst::ICMP_ULT:
 226         return Expression::ICMPULT;
 227       case ICmpInst::ICMP_ULE:
 228         return Expression::ICMPULE;
 229       case ICmpInst::ICMP_SGT:
 230         return Expression::ICMPSGT;
 231       case ICmpInst::ICMP_SGE:
 232         return Expression::ICMPSGE;
 233       case ICmpInst::ICMP_SLT:
 234         return Expression::ICMPSLT;
 235       case ICmpInst::ICMP_SLE:
 236         return Expression::ICMPSLE;
 237
 238       // THIS SHOULD NEVER HAPPEN
 239       default:
 240         assert(0 && "Comparison with unknown predicate?");
 241         return Expression::ICMPEQ;
 242     }
 243   } else {
 244     switch (C->getPredicate()) {
 245       case FCmpInst::FCMP_OEQ:
 246         return Expression::FCMPOEQ;
 247       case FCmpInst::FCMP_OGT:
 248         return Expression::FCMPOGT;
 249       case FCmpInst::FCMP_OGE:
 250         return Expression::FCMPOGE;
 251       case FCmpInst::FCMP_OLT:
 252         return Expression::FCMPOLT;
 253       case FCmpInst::FCMP_OLE:
 254         return Expression::FCMPOLE;
 255       case FCmpInst::FCMP_ONE:
 256         return Expression::FCMPONE;
 257       case FCmpInst::FCMP_ORD:
 258         return Expression::FCMPORD;
 259       case FCmpInst::FCMP_UNO:
 260         return Expression::FCMPUNO;
 261       case FCmpInst::FCMP_UEQ:
 262         return Expression::FCMPUEQ;
 263       case FCmpInst::FCMP_UGT:
 264         return Expression::FCMPUGT;
 265       case FCmpInst::FCMP_UGE:
 266         return Expression::FCMPUGE;
 267       case FCmpInst::FCMP_ULT:
 268         return Expression::FCMPULT;
 269       case FCmpInst::FCMP_ULE:
 270         return Expression::FCMPULE;
 271       case FCmpInst::FCMP_UNE:
 272         return Expression::FCMPUNE;
 273
 274       // THIS SHOULD NEVER HAPPEN
 275       default:
 276         assert(0 && "Comparison with unknown predicate?");
 277         return Expression::FCMPOEQ;
 278     }
 279   }
 280 }
 281
 282 Expression::ExpressionOpcode
 283                              ValueTable::getOpcode(CastInst* C) {
 284   switch(C->getOpcode()) {
 285     case Instruction::Trunc:
 286       return Expression::TRUNC;
 287     case Instruction::ZExt:
 288       return Expression::ZEXT;
 289     case Instruction::SExt:
 290       return Expression::SEXT;
 291     case Instruction::FPToUI:
 292       return Expression::FPTOUI;
 293     case Instruction::FPToSI:
 294       return Expression::FPTOSI;
 295     case Instruction::UIToFP:
 296       return Expression::UITOFP;
 297     case Instruction::SIToFP:
 298       return Expression::SITOFP;
 299     case Instruction::FPTrunc:
 300       return Expression::FPTRUNC;
 301     case Instruction::FPExt:
 302       return Expression::FPEXT;
 303     case Instruction::PtrToInt:
 304       return Expression::PTRTOINT;
 305     case Instruction::IntToPtr:
 306       return Expression::INTTOPTR;
 307     case Instruction::BitCast:
 308       return Expression::BITCAST;
 309
 310     // THIS SHOULD NEVER HAPPEN
 311     default:
 312       assert(0 && "Cast operator with unknown opcode?");
 313       return Expression::BITCAST;
 314   }
 315 }
 316
 317 Expression ValueTable::create_expression(BinaryOperator* BO) {
 318   Expression e;
 319
 320   e.firstVN = lookup_or_add(BO->getOperand(0));
 321   e.secondVN = lookup_or_add(BO->getOperand(1));
 322   e.thirdVN = 0;
 323   e.type = BO->getType();
 324   e.opcode = getOpcode(BO);
 325
 326   return e;
 327 }
 328
 329 Expression ValueTable::create_expression(CmpInst* C) {
 330   Expression e;
 331
 332   e.firstVN = lookup_or_add(C->getOperand(0));
 333   e.secondVN = lookup_or_add(C->getOperand(1));
 334   e.thirdVN = 0;
 335   e.type = C->getType();
 336   e.opcode = getOpcode(C);
 337
 338   return e;
 339 }
 340
 341 Expression ValueTable::create_expression(CastInst* C) {
 342   Expression e;
 343
 344   e.firstVN = lookup_or_add(C->getOperand(0));
 345   e.secondVN = 0;
 346   e.thirdVN = 0;
 347   e.type = C->getType();
 348   e.opcode = getOpcode(C);
 349
 350   return e;
 351 }
 352
 353 Expression ValueTable::create_expression(ShuffleVectorInst* S) {
 354   Expression e;
 355
 356   e.firstVN = lookup_or_add(S->getOperand(0));
 357   e.secondVN = lookup_or_add(S->getOperand(1));
 358   e.thirdVN = lookup_or_add(S->getOperand(2));
 359   e.type = S->getType();
 360   e.opcode = Expression::SHUFFLE;
 361
 362   return e;
 363 }
 364
 365 Expression ValueTable::create_expression(ExtractElementInst* E) {
 366   Expression e;
 367
 368   e.firstVN = lookup_or_add(E->getOperand(0));
 369   e.secondVN = lookup_or_add(E->getOperand(1));
 370   e.thirdVN = 0;
 371   e.type = E->getType();
 372   e.opcode = Expression::EXTRACT;
 373
 374   return e;
 375 }
 376
 377 Expression ValueTable::create_expression(InsertElementInst* I) {
 378   Expression e;
 379
 380   e.firstVN = lookup_or_add(I->getOperand(0));
 381   e.secondVN = lookup_or_add(I->getOperand(1));
 382   e.thirdVN = lookup_or_add(I->getOperand(2));
 383   e.type = I->getType();
 384   e.opcode = Expression::INSERT;
 385
 386   return e;
 387 }
 388
 389 Expression ValueTable::create_expression(SelectInst* I) {
 390   Expression e;
 391
 392   e.firstVN = lookup_or_add(I->getCondition());
 393   e.secondVN = lookup_or_add(I->getTrueValue());
 394   e.thirdVN = lookup_or_add(I->getFalseValue());
 395   e.type = I->getType();
 396   e.opcode = Expression::SELECT;
 397
 398   return e;
 399 }
 400
 401 Expression ValueTable::create_expression(GetElementPtrInst* G) {
 402   Expression e;
 403
 404   e.firstVN = lookup_or_add(G->getPointerOperand());
 405   e.secondVN = 0;
 406   e.thirdVN = 0;
 407   e.type = G->getType();
 408   e.opcode = Expression::GEP;
 409
 410   for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
 411        I != E; ++I)
 412     e.varargs.push_back(lookup_or_add(*I));
 413
 414   return e;
 415 }
 416
 417 //===----------------------------------------------------------------------===//
 418 //                     ValueTable External Functions
 419 //===----------------------------------------------------------------------===//
 420
 421 /// lookup_or_add - Returns the value number for the specified value, assigning
 422 /// it a new number if it did not have one before.
 423 uint32_t ValueTable::lookup_or_add(Value* V) {
 424   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 425   if (VI != valueNumbering.end())
 426     return VI->second;
 427
 428
 429   if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
 430     Expression e = create_expression(BO);
 431
 432     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 433     if (EI != expressionNumbering.end()) {
 434       valueNumbering.insert(std::make_pair(V, EI->second));
 435       return EI->second;
 436     } else {
 437       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 438       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 439
 440       return nextValueNumber++;
 441     }
 442   } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
 443     Expression e = create_expression(C);
 444
 445     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 446     if (EI != expressionNumbering.end()) {
 447       valueNumbering.insert(std::make_pair(V, EI->second));
 448       return EI->second;
 449     } else {
 450       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 451       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 452
 453       return nextValueNumber++;
 454     }
 455   } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) {
 456     Expression e = create_expression(U);
 457
 458     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 459     if (EI != expressionNumbering.end()) {
 460       valueNumbering.insert(std::make_pair(V, EI->second));
 461       return EI->second;
 462     } else {
 463       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 464       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 465
 466       return nextValueNumber++;
 467     }
 468   } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) {
 469     Expression e = create_expression(U);
 470
 471     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 472     if (EI != expressionNumbering.end()) {
 473       valueNumbering.insert(std::make_pair(V, EI->second));
 474       return EI->second;
 475     } else {
 476       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 477       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 478
 479       return nextValueNumber++;
 480     }
 481   } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) {
 482     Expression e = create_expression(U);
 483
 484     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 485     if (EI != expressionNumbering.end()) {
 486       valueNumbering.insert(std::make_pair(V, EI->second));
 487       return EI->second;
 488     } else {
 489       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 490       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 491
 492       return nextValueNumber++;
 493     }
 494   } else if (SelectInst* U = dyn_cast<SelectInst>(V)) {
 495     Expression e = create_expression(U);
 496
 497     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 498     if (EI != expressionNumbering.end()) {
 499       valueNumbering.insert(std::make_pair(V, EI->second));
 500       return EI->second;
 501     } else {
 502       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 503       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 504
 505       return nextValueNumber++;
 506     }
 507   } else if (CastInst* U = dyn_cast<CastInst>(V)) {
 508     Expression e = create_expression(U);
 509
 510     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 511     if (EI != expressionNumbering.end()) {
 512       valueNumbering.insert(std::make_pair(V, EI->second));
 513       return EI->second;
 514     } else {
 515       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 516       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 517
 518       return nextValueNumber++;
 519     }
 520   } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
 521     Expression e = create_expression(U);
 522
 523     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 524     if (EI != expressionNumbering.end()) {
 525       valueNumbering.insert(std::make_pair(V, EI->second));
 526       return EI->second;
 527     } else {
 528       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 529       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 530
 531       return nextValueNumber++;
 532     }
 533   } else {
 534     valueNumbering.insert(std::make_pair(V, nextValueNumber));
 535     return nextValueNumber++;
 536   }
 537 }
 538
 539 /// lookup - Returns the value number of the specified value. Fails if
 540 /// the value has not yet been numbered.
 541 uint32_t ValueTable::lookup(Value* V) const {
 542   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 543   if (VI != valueNumbering.end())
 544     return VI->second;
 545   else
 546     assert(0 && "Value not numbered?");
 547
 548   return 0;
 549 }
 550
 551 /// clear - Remove all entries from the ValueTable
 552 void ValueTable::clear() {
 553   valueNumbering.clear();
 554   expressionNumbering.clear();
 555   nextValueNumber = 1;
 556 }
 557
 558 //===----------------------------------------------------------------------===//
 559 //                       ValueNumberedSet Class
 560 //===----------------------------------------------------------------------===//
 561 namespace {
 562 class ValueNumberedSet {
 563   private:
 564     SmallPtrSet<Value*, 8> contents;
 565     BitVector numbers;
 566   public:
 567     ValueNumberedSet() { numbers.resize(1); }
 568     ValueNumberedSet(const ValueNumberedSet& other) {
 569       numbers = other.numbers;
 570       contents = other.contents;
 571     }
 572
 573     typedef SmallPtrSet<Value*, 8>::iterator iterator;
 574
 575     iterator begin() { return contents.begin(); }
 576     iterator end() { return contents.end(); }
 577
 578     bool insert(Value* v) { return contents.insert(v); }
 579     void insert(iterator I, iterator E) { contents.insert(I, E); }
 580     void erase(Value* v) { contents.erase(v); }
 581     unsigned count(Value* v) { return contents.count(v); }
 582     size_t size() { return contents.size(); }
 583
 584     void set(unsigned i)  {
 585       if (i >= numbers.size())
 586         numbers.resize(i+1);
 587
 588       numbers.set(i);
 589     }
 590
 591     void operator=(const ValueNumberedSet& other) {
 592       contents = other.contents;
 593       numbers = other.numbers;
 594     }
 595
 596     void reset(unsigned i)  {
 597       if (i < numbers.size())
 598         numbers.reset(i);
 599     }
 600
 601     bool test(unsigned i)  {
 602       if (i >= numbers.size())
 603         return false;
 604
 605       return numbers.test(i);
 606     }
 607
 608     void clear() {
 609       contents.clear();
 610       numbers.clear();
 611     }
 612 };
 613 }
 614
 615 //===----------------------------------------------------------------------===//
 616 //                         GVN Pass
 617 //===----------------------------------------------------------------------===//
 618
 619 namespace {
 620
 621   class VISIBILITY_HIDDEN GVN : public FunctionPass {
 622     bool runOnFunction(Function &F);
 623   public:
 624     static char ID; // Pass identification, replacement for typeid
 625     GVN() : FunctionPass((intptr_t)&ID) { }
 626
 627   private:
 628     ValueTable VN;
 629
 630     DenseMap<BasicBlock*, ValueNumberedSet> availableOut;
 631
 632     // This transformation requires dominator postdominator info
 633     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 634       AU.setPreservesCFG();
 635       AU.addRequired<DominatorTree>();
 636       AU.addRequired<MemoryDependenceAnalysis>();
 637       AU.addPreserved<MemoryDependenceAnalysis>();
 638     }
 639
 640     // Helper fuctions
 641     // FIXME: eliminate or document these better
 642     Value* find_leader(ValueNumberedSet& vals, uint32_t v) ;
 643     void val_insert(ValueNumberedSet& s, Value* v);
 644     bool processLoad(LoadInst* L,
 645                      DenseMap<Value*, LoadInst*>& lastLoad,
 646                      SmallVector<Instruction*, 4>& toErase);
 647     bool processInstruction(Instruction* I,
 648                             ValueNumberedSet& currAvail,
 649                             DenseMap<Value*, LoadInst*>& lastSeenLoad,
 650                             SmallVector<Instruction*, 4>& toErase);
 651   };
 652
 653   char GVN::ID = 0;
 654
 655 }
 656
 657 // createGVNPass - The public interface to this file...
 658 FunctionPass *llvm::createGVNPass() { return new GVN(); }
 659
 660 static RegisterPass<GVN> X("gvn",
 661                            "Global Value Numbering");
 662
 663 STATISTIC(NumGVNInstr, "Number of instructions deleted");
 664 STATISTIC(NumGVNLoad, "Number of loads deleted");
 665
 666 /// find_leader - Given a set and a value number, return the first
 667 /// element of the set with that value number, or 0 if no such element
 668 /// is present
 669 Value* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) {
 670   if (!vals.test(v))
 671     return 0;
 672
 673   for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end();
 674        I != E; ++I)
 675     if (v == VN.lookup(*I))
 676       return *I;
 677
 678   assert(0 && "No leader found, but present bit is set?");
 679   return 0;
 680 }
 681
 682 /// val_insert - Insert a value into a set only if there is not a value
 683 /// with the same value number already in the set
 684 void GVN::val_insert(ValueNumberedSet& s, Value* v) {
 685   uint32_t num = VN.lookup(v);
 686   if (!s.test(num))
 687     s.insert(v);
 688 }
 689
 690 bool GVN::processLoad(LoadInst* L,
 691                          DenseMap<Value*, LoadInst*>& lastLoad,
 692                          SmallVector<Instruction*, 4>& toErase) {
 693   if (L->isVolatile()) {
 694     lastLoad[L->getPointerOperand()] = L;
 695     return false;
 696   }
 697
 698   Value* pointer = L->getPointerOperand();
 699   LoadInst*& last = lastLoad[pointer];
 700
 701   // ... to a pointer that has been loaded from before...
 702   MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
 703   Instruction* dep = MD.getDependency(L);
 704   bool deletedLoad = false;
 705
 706   while (dep != MemoryDependenceAnalysis::None &&
 707          dep != MemoryDependenceAnalysis::NonLocal &&
 708          (isa<LoadInst>(dep) || isa<StoreInst>(dep))) {
 709     // ... that depends on a store ...
 710     if (StoreInst* S = dyn_cast<StoreInst>(dep)) {
 711       if (S->getPointerOperand() == pointer) {
 712         // Remove it!
 713         MD.removeInstruction(L);
 714
 715         L->replaceAllUsesWith(S->getOperand(0));
 716         toErase.push_back(L);
 717         deletedLoad = true;
 718         NumGVNLoad++;
 719       }
 720
 721       // Whether we removed it or not, we can't
 722       // go any further
 723       break;
 724     } else if (!last) {
 725       // If we don't depend on a store, and we haven't
 726       // been loaded before, bail.
 727       break;
 728     } else if (dep == last) {
 729       // Remove it!
 730       MD.removeInstruction(L);
 731
 732       L->replaceAllUsesWith(last);
 733       toErase.push_back(L);
 734       deletedLoad = true;
 735       NumGVNLoad++;
 736
 737       break;
 738     } else {
 739       dep = MD.getDependency(L, dep);
 740     }
 741   }
 742
 743   if (!deletedLoad)
 744     last = L;
 745
 746   return deletedLoad;
 747 }
 748
 749 /// buildsets_availout - When calculating availability, handle an instruction
 750 /// by inserting it into the appropriate sets
 751 bool GVN::processInstruction(Instruction* I,
 752                                 ValueNumberedSet& currAvail,
 753                                 DenseMap<Value*, LoadInst*>& lastSeenLoad,
 754                                 SmallVector<Instruction*, 4>& toErase) {
 755   if (LoadInst* L = dyn_cast<LoadInst>(I)) {
 756     return processLoad(L, lastSeenLoad, toErase);
 757   }
 758
 759   unsigned num = VN.lookup_or_add(I);
 760
 761   if (currAvail.test(num)) {
 762     Value* repl = find_leader(currAvail, num);
 763
 764     I->replaceAllUsesWith(repl);
 765     toErase.push_back(I);
 766     return true;
 767   } else if (!I->isTerminator()) {
 768     currAvail.set(num);
 769     currAvail.insert(I);
 770   }
 771
 772   return false;
 773 }
 774
 775 // GVN::runOnFunction - This is the main transformation entry point for a
 776 // function.
 777 //
 778 bool GVN::runOnFunction(Function &F) {
 779   // Clean out global sets from any previous functions
 780   VN.clear();
 781   availableOut.clear();
 782
 783   bool changed_function = false;
 784
 785   DominatorTree &DT = getAnalysis<DominatorTree>();
 786
 787   SmallVector<Instruction*, 4> toErase;
 788
 789   // Top-down walk of the dominator tree
 790   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
 791          E = df_end(DT.getRootNode()); DI != E; ++DI) {
 792
 793     // Get the set to update for this block
 794     ValueNumberedSet& currAvail = availableOut[DI->getBlock()];
 795     DenseMap<Value*, LoadInst*> lastSeenLoad;
 796
 797     BasicBlock* BB = DI->getBlock();
 798
 799     // A block inherits AVAIL_OUT from its dominator
 800     if (DI->getIDom() != 0)
 801       currAvail = availableOut[DI->getIDom()->getBlock()];
 802
 803     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
 804          BI != BE; ++BI) {
 805       processInstruction(BI, currAvail, lastSeenLoad, toErase);
 806     }
 807   }
 808
 809   NumGVNInstr = toErase.size();
 810
 811   for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(),
 812        E = toErase.end(); I != E; ++I)
 813     (*I)->eraseFromParent();
 814
 815   return changed_function;
 816 }