lib/Transforms/Scalar/GVN.cpp

   1 //===- GVN.cpp - Eliminate redundant values and loads ------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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/Transforms/Scalar.h"
  17 #include "llvm/BasicBlock.h"
  18 #include "llvm/Constants.h"
  19 #include "llvm/DerivedTypes.h"
  20 #include "llvm/Function.h"
  21 #include "llvm/Instructions.h"
  22 #include "llvm/Value.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/SparseBitVector.h"
  28 #include "llvm/ADT/Statistic.h"
  29 #include "llvm/Analysis/Dominators.h"
  30 #include "llvm/Analysis/AliasAnalysis.h"
  31 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
  32 #include "llvm/Support/CFG.h"
  33 #include "llvm/Support/Compiler.h"
  34 #include "llvm/Support/Debug.h"
  35 #include <list>
  36 using namespace llvm;
  37
  38 STATISTIC(NumGVNInstr, "Number of instructions deleted");
  39 STATISTIC(NumGVNLoad, "Number of loads deleted");
  40
  41 //===----------------------------------------------------------------------===//
  42 //                         ValueTable Class
  43 //===----------------------------------------------------------------------===//
  44
  45 /// This class holds the mapping between values and value numbers.  It is used
  46 /// as an efficient mechanism to determine the expression-wise equivalence of
  47 /// two values.
  48 namespace {
  49   struct VISIBILITY_HIDDEN Expression {
  50     enum ExpressionOpcode { ADD, SUB, MUL, UDIV, SDIV, FDIV, UREM, SREM,
  51                             FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
  52                             ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
  53                             ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
  54                             FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
  55                             FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
  56                             FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
  57                             SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
  58                             FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
  59                             PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, EMPTY,
  60                             TOMBSTONE };
  61
  62     ExpressionOpcode opcode;
  63     const Type* type;
  64     uint32_t firstVN;
  65     uint32_t secondVN;
  66     uint32_t thirdVN;
  67     SmallVector<uint32_t, 4> varargs;
  68     Value* function;
  69
  70     Expression() { }
  71     Expression(ExpressionOpcode o) : opcode(o) { }
  72
  73     bool operator==(const Expression &other) const {
  74       if (opcode != other.opcode)
  75         return false;
  76       else if (opcode == EMPTY || opcode == TOMBSTONE)
  77         return true;
  78       else if (type != other.type)
  79         return false;
  80       else if (function != other.function)
  81         return false;
  82       else if (firstVN != other.firstVN)
  83         return false;
  84       else if (secondVN != other.secondVN)
  85         return false;
  86       else if (thirdVN != other.thirdVN)
  87         return false;
  88       else {
  89         if (varargs.size() != other.varargs.size())
  90           return false;
  91
  92         for (size_t i = 0; i < varargs.size(); ++i)
  93           if (varargs[i] != other.varargs[i])
  94             return false;
  95
  96         return true;
  97       }
  98     }
  99
 100     bool operator!=(const Expression &other) const {
 101       if (opcode != other.opcode)
 102         return true;
 103       else if (opcode == EMPTY || opcode == TOMBSTONE)
 104         return false;
 105       else if (type != other.type)
 106         return true;
 107       else if (function != other.function)
 108         return true;
 109       else if (firstVN != other.firstVN)
 110         return true;
 111       else if (secondVN != other.secondVN)
 112         return true;
 113       else if (thirdVN != other.thirdVN)
 114         return true;
 115       else {
 116         if (varargs.size() != other.varargs.size())
 117           return true;
 118
 119         for (size_t i = 0; i < varargs.size(); ++i)
 120           if (varargs[i] != other.varargs[i])
 121             return true;
 122
 123           return false;
 124       }
 125     }
 126   };
 127
 128   class VISIBILITY_HIDDEN ValueTable {
 129     private:
 130       DenseMap<Value*, uint32_t> valueNumbering;
 131       DenseMap<Expression, uint32_t> expressionNumbering;
 132       AliasAnalysis* AA;
 133       MemoryDependenceAnalysis* MD;
 134
 135       uint32_t nextValueNumber;
 136
 137       Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
 138       Expression::ExpressionOpcode getOpcode(CmpInst* C);
 139       Expression::ExpressionOpcode getOpcode(CastInst* C);
 140       Expression create_expression(BinaryOperator* BO);
 141       Expression create_expression(CmpInst* C);
 142       Expression create_expression(ShuffleVectorInst* V);
 143       Expression create_expression(ExtractElementInst* C);
 144       Expression create_expression(InsertElementInst* V);
 145       Expression create_expression(SelectInst* V);
 146       Expression create_expression(CastInst* C);
 147       Expression create_expression(GetElementPtrInst* G);
 148       Expression create_expression(CallInst* C);
 149     public:
 150       ValueTable() : nextValueNumber(1) { }
 151       uint32_t lookup_or_add(Value* V);
 152       uint32_t lookup(Value* V) const;
 153       void add(Value* V, uint32_t num);
 154       void clear();
 155       void erase(Value* v);
 156       unsigned size();
 157       void setAliasAnalysis(AliasAnalysis* A) { AA = A; }
 158       void setMemDep(MemoryDependenceAnalysis* M) { MD = M; }
 159   };
 160 }
 161
 162 namespace llvm {
 163 template <> struct DenseMapInfo<Expression> {
 164   static inline Expression getEmptyKey() {
 165     return Expression(Expression::EMPTY);
 166   }
 167
 168   static inline Expression getTombstoneKey() {
 169     return Expression(Expression::TOMBSTONE);
 170   }
 171
 172   static unsigned getHashValue(const Expression e) {
 173     unsigned hash = e.opcode;
 174
 175     hash = e.firstVN + hash * 37;
 176     hash = e.secondVN + hash * 37;
 177     hash = e.thirdVN + hash * 37;
 178
 179     hash = ((unsigned)((uintptr_t)e.type >> 4) ^
 180             (unsigned)((uintptr_t)e.type >> 9)) +
 181            hash * 37;
 182
 183     for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(),
 184          E = e.varargs.end(); I != E; ++I)
 185       hash = *I + hash * 37;
 186
 187     hash = ((unsigned)((uintptr_t)e.function >> 4) ^
 188             (unsigned)((uintptr_t)e.function >> 9)) +
 189            hash * 37;
 190
 191     return hash;
 192   }
 193   static bool isEqual(const Expression &LHS, const Expression &RHS) {
 194     return LHS == RHS;
 195   }
 196   static bool isPod() { return true; }
 197 };
 198 }
 199
 200 //===----------------------------------------------------------------------===//
 201 //                     ValueTable Internal Functions
 202 //===----------------------------------------------------------------------===//
 203 Expression::ExpressionOpcode ValueTable::getOpcode(BinaryOperator* BO) {
 204   switch(BO->getOpcode()) {
 205   default: // THIS SHOULD NEVER HAPPEN
 206     assert(0 && "Binary operator with unknown opcode?");
 207   case Instruction::Add:  return Expression::ADD;
 208   case Instruction::Sub:  return Expression::SUB;
 209   case Instruction::Mul:  return Expression::MUL;
 210   case Instruction::UDiv: return Expression::UDIV;
 211   case Instruction::SDiv: return Expression::SDIV;
 212   case Instruction::FDiv: return Expression::FDIV;
 213   case Instruction::URem: return Expression::UREM;
 214   case Instruction::SRem: return Expression::SREM;
 215   case Instruction::FRem: return Expression::FREM;
 216   case Instruction::Shl:  return Expression::SHL;
 217   case Instruction::LShr: return Expression::LSHR;
 218   case Instruction::AShr: return Expression::ASHR;
 219   case Instruction::And:  return Expression::AND;
 220   case Instruction::Or:   return Expression::OR;
 221   case Instruction::Xor:  return Expression::XOR;
 222   }
 223 }
 224
 225 Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
 226   if (isa<ICmpInst>(C)) {
 227     switch (C->getPredicate()) {
 228     default:  // THIS SHOULD NEVER HAPPEN
 229       assert(0 && "Comparison with unknown predicate?");
 230     case ICmpInst::ICMP_EQ:  return Expression::ICMPEQ;
 231     case ICmpInst::ICMP_NE:  return Expression::ICMPNE;
 232     case ICmpInst::ICMP_UGT: return Expression::ICMPUGT;
 233     case ICmpInst::ICMP_UGE: return Expression::ICMPUGE;
 234     case ICmpInst::ICMP_ULT: return Expression::ICMPULT;
 235     case ICmpInst::ICMP_ULE: return Expression::ICMPULE;
 236     case ICmpInst::ICMP_SGT: return Expression::ICMPSGT;
 237     case ICmpInst::ICMP_SGE: return Expression::ICMPSGE;
 238     case ICmpInst::ICMP_SLT: return Expression::ICMPSLT;
 239     case ICmpInst::ICMP_SLE: return Expression::ICMPSLE;
 240     }
 241   }
 242   assert(isa<FCmpInst>(C) && "Unknown compare");
 243   switch (C->getPredicate()) {
 244   default: // THIS SHOULD NEVER HAPPEN
 245     assert(0 && "Comparison with unknown predicate?");
 246   case FCmpInst::FCMP_OEQ: return Expression::FCMPOEQ;
 247   case FCmpInst::FCMP_OGT: return Expression::FCMPOGT;
 248   case FCmpInst::FCMP_OGE: return Expression::FCMPOGE;
 249   case FCmpInst::FCMP_OLT: return Expression::FCMPOLT;
 250   case FCmpInst::FCMP_OLE: return Expression::FCMPOLE;
 251   case FCmpInst::FCMP_ONE: return Expression::FCMPONE;
 252   case FCmpInst::FCMP_ORD: return Expression::FCMPORD;
 253   case FCmpInst::FCMP_UNO: return Expression::FCMPUNO;
 254   case FCmpInst::FCMP_UEQ: return Expression::FCMPUEQ;
 255   case FCmpInst::FCMP_UGT: return Expression::FCMPUGT;
 256   case FCmpInst::FCMP_UGE: return Expression::FCMPUGE;
 257   case FCmpInst::FCMP_ULT: return Expression::FCMPULT;
 258   case FCmpInst::FCMP_ULE: return Expression::FCMPULE;
 259   case FCmpInst::FCMP_UNE: return Expression::FCMPUNE;
 260   }
 261 }
 262
 263 Expression::ExpressionOpcode ValueTable::getOpcode(CastInst* C) {
 264   switch(C->getOpcode()) {
 265   default: // THIS SHOULD NEVER HAPPEN
 266     assert(0 && "Cast operator with unknown opcode?");
 267   case Instruction::Trunc:    return Expression::TRUNC;
 268   case Instruction::ZExt:     return Expression::ZEXT;
 269   case Instruction::SExt:     return Expression::SEXT;
 270   case Instruction::FPToUI:   return Expression::FPTOUI;
 271   case Instruction::FPToSI:   return Expression::FPTOSI;
 272   case Instruction::UIToFP:   return Expression::UITOFP;
 273   case Instruction::SIToFP:   return Expression::SITOFP;
 274   case Instruction::FPTrunc:  return Expression::FPTRUNC;
 275   case Instruction::FPExt:    return Expression::FPEXT;
 276   case Instruction::PtrToInt: return Expression::PTRTOINT;
 277   case Instruction::IntToPtr: return Expression::INTTOPTR;
 278   case Instruction::BitCast:  return Expression::BITCAST;
 279   }
 280 }
 281
 282 Expression ValueTable::create_expression(CallInst* C) {
 283   Expression e;
 284
 285   e.type = C->getType();
 286   e.firstVN = 0;
 287   e.secondVN = 0;
 288   e.thirdVN = 0;
 289   e.function = C->getCalledFunction();
 290   e.opcode = Expression::CALL;
 291
 292   for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end();
 293        I != E; ++I)
 294     e.varargs.push_back(lookup_or_add(*I));
 295
 296   return e;
 297 }
 298
 299 Expression ValueTable::create_expression(BinaryOperator* BO) {
 300   Expression e;
 301
 302   e.firstVN = lookup_or_add(BO->getOperand(0));
 303   e.secondVN = lookup_or_add(BO->getOperand(1));
 304   e.thirdVN = 0;
 305   e.function = 0;
 306   e.type = BO->getType();
 307   e.opcode = getOpcode(BO);
 308
 309   return e;
 310 }
 311
 312 Expression ValueTable::create_expression(CmpInst* C) {
 313   Expression e;
 314
 315   e.firstVN = lookup_or_add(C->getOperand(0));
 316   e.secondVN = lookup_or_add(C->getOperand(1));
 317   e.thirdVN = 0;
 318   e.function = 0;
 319   e.type = C->getType();
 320   e.opcode = getOpcode(C);
 321
 322   return e;
 323 }
 324
 325 Expression ValueTable::create_expression(CastInst* C) {
 326   Expression e;
 327
 328   e.firstVN = lookup_or_add(C->getOperand(0));
 329   e.secondVN = 0;
 330   e.thirdVN = 0;
 331   e.function = 0;
 332   e.type = C->getType();
 333   e.opcode = getOpcode(C);
 334
 335   return e;
 336 }
 337
 338 Expression ValueTable::create_expression(ShuffleVectorInst* S) {
 339   Expression e;
 340
 341   e.firstVN = lookup_or_add(S->getOperand(0));
 342   e.secondVN = lookup_or_add(S->getOperand(1));
 343   e.thirdVN = lookup_or_add(S->getOperand(2));
 344   e.function = 0;
 345   e.type = S->getType();
 346   e.opcode = Expression::SHUFFLE;
 347
 348   return e;
 349 }
 350
 351 Expression ValueTable::create_expression(ExtractElementInst* E) {
 352   Expression e;
 353
 354   e.firstVN = lookup_or_add(E->getOperand(0));
 355   e.secondVN = lookup_or_add(E->getOperand(1));
 356   e.thirdVN = 0;
 357   e.function = 0;
 358   e.type = E->getType();
 359   e.opcode = Expression::EXTRACT;
 360
 361   return e;
 362 }
 363
 364 Expression ValueTable::create_expression(InsertElementInst* I) {
 365   Expression e;
 366
 367   e.firstVN = lookup_or_add(I->getOperand(0));
 368   e.secondVN = lookup_or_add(I->getOperand(1));
 369   e.thirdVN = lookup_or_add(I->getOperand(2));
 370   e.function = 0;
 371   e.type = I->getType();
 372   e.opcode = Expression::INSERT;
 373
 374   return e;
 375 }
 376
 377 Expression ValueTable::create_expression(SelectInst* I) {
 378   Expression e;
 379
 380   e.firstVN = lookup_or_add(I->getCondition());
 381   e.secondVN = lookup_or_add(I->getTrueValue());
 382   e.thirdVN = lookup_or_add(I->getFalseValue());
 383   e.function = 0;
 384   e.type = I->getType();
 385   e.opcode = Expression::SELECT;
 386
 387   return e;
 388 }
 389
 390 Expression ValueTable::create_expression(GetElementPtrInst* G) {
 391   Expression e;
 392
 393   e.firstVN = lookup_or_add(G->getPointerOperand());
 394   e.secondVN = 0;
 395   e.thirdVN = 0;
 396   e.function = 0;
 397   e.type = G->getType();
 398   e.opcode = Expression::GEP;
 399
 400   for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
 401        I != E; ++I)
 402     e.varargs.push_back(lookup_or_add(*I));
 403
 404   return e;
 405 }
 406
 407 //===----------------------------------------------------------------------===//
 408 //                     ValueTable External Functions
 409 //===----------------------------------------------------------------------===//
 410
 411 /// lookup_or_add - Returns the value number for the specified value, assigning
 412 /// it a new number if it did not have one before.
 413 uint32_t ValueTable::lookup_or_add(Value* V) {
 414   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 415   if (VI != valueNumbering.end())
 416     return VI->second;
 417
 418   if (CallInst* C = dyn_cast<CallInst>(V)) {
 419     if (AA->doesNotAccessMemory(C)) {
 420       Expression e = create_expression(C);
 421
 422       DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 423       if (EI != expressionNumbering.end()) {
 424         valueNumbering.insert(std::make_pair(V, EI->second));
 425         return EI->second;
 426       } else {
 427         expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 428         valueNumbering.insert(std::make_pair(V, nextValueNumber));
 429
 430         return nextValueNumber++;
 431       }
 432     } else if (AA->onlyReadsMemory(C)) {
 433       Expression e = create_expression(C);
 434
 435       Instruction* dep = MD->getDependency(C);
 436
 437       if (dep == MemoryDependenceAnalysis::NonLocal ||
 438           !isa<CallInst>(dep)) {
 439         expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 440         valueNumbering.insert(std::make_pair(V, nextValueNumber));
 441
 442         return nextValueNumber++;
 443       }
 444
 445       CallInst* cdep = cast<CallInst>(dep);
 446       Expression d_exp = create_expression(cdep);
 447
 448       if (e != d_exp) {
 449         expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 450         valueNumbering.insert(std::make_pair(V, nextValueNumber));
 451
 452         return nextValueNumber++;
 453       } else {
 454         uint32_t v = expressionNumbering[d_exp];
 455         valueNumbering.insert(std::make_pair(V, v));
 456         return v;
 457       }
 458
 459     } else {
 460       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 461       return nextValueNumber++;
 462     }
 463   } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
 464     Expression e = create_expression(BO);
 465
 466     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 467     if (EI != expressionNumbering.end()) {
 468       valueNumbering.insert(std::make_pair(V, EI->second));
 469       return EI->second;
 470     } else {
 471       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 472       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 473
 474       return nextValueNumber++;
 475     }
 476   } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
 477     Expression e = create_expression(C);
 478
 479     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 480     if (EI != expressionNumbering.end()) {
 481       valueNumbering.insert(std::make_pair(V, EI->second));
 482       return EI->second;
 483     } else {
 484       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 485       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 486
 487       return nextValueNumber++;
 488     }
 489   } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) {
 490     Expression e = create_expression(U);
 491
 492     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 493     if (EI != expressionNumbering.end()) {
 494       valueNumbering.insert(std::make_pair(V, EI->second));
 495       return EI->second;
 496     } else {
 497       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 498       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 499
 500       return nextValueNumber++;
 501     }
 502   } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) {
 503     Expression e = create_expression(U);
 504
 505     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 506     if (EI != expressionNumbering.end()) {
 507       valueNumbering.insert(std::make_pair(V, EI->second));
 508       return EI->second;
 509     } else {
 510       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 511       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 512
 513       return nextValueNumber++;
 514     }
 515   } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) {
 516     Expression e = create_expression(U);
 517
 518     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 519     if (EI != expressionNumbering.end()) {
 520       valueNumbering.insert(std::make_pair(V, EI->second));
 521       return EI->second;
 522     } else {
 523       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 524       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 525
 526       return nextValueNumber++;
 527     }
 528   } else if (SelectInst* U = dyn_cast<SelectInst>(V)) {
 529     Expression e = create_expression(U);
 530
 531     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 532     if (EI != expressionNumbering.end()) {
 533       valueNumbering.insert(std::make_pair(V, EI->second));
 534       return EI->second;
 535     } else {
 536       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 537       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 538
 539       return nextValueNumber++;
 540     }
 541   } else if (CastInst* U = dyn_cast<CastInst>(V)) {
 542     Expression e = create_expression(U);
 543
 544     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 545     if (EI != expressionNumbering.end()) {
 546       valueNumbering.insert(std::make_pair(V, EI->second));
 547       return EI->second;
 548     } else {
 549       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 550       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 551
 552       return nextValueNumber++;
 553     }
 554   } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
 555     Expression e = create_expression(U);
 556
 557     DenseMap<Expression, uint32_t>::iterator EI = expressionNumbering.find(e);
 558     if (EI != expressionNumbering.end()) {
 559       valueNumbering.insert(std::make_pair(V, EI->second));
 560       return EI->second;
 561     } else {
 562       expressionNumbering.insert(std::make_pair(e, nextValueNumber));
 563       valueNumbering.insert(std::make_pair(V, nextValueNumber));
 564
 565       return nextValueNumber++;
 566     }
 567   } else {
 568     valueNumbering.insert(std::make_pair(V, nextValueNumber));
 569     return nextValueNumber++;
 570   }
 571 }
 572
 573 /// lookup - Returns the value number of the specified value. Fails if
 574 /// the value has not yet been numbered.
 575 uint32_t ValueTable::lookup(Value* V) const {
 576   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 577   assert(VI != valueNumbering.end() && "Value not numbered?");
 578   return VI->second;
 579 }
 580
 581 /// clear - Remove all entries from the ValueTable
 582 void ValueTable::clear() {
 583   valueNumbering.clear();
 584   expressionNumbering.clear();
 585   nextValueNumber = 1;
 586 }
 587
 588 /// erase - Remove a value from the value numbering
 589 void ValueTable::erase(Value* V) {
 590   valueNumbering.erase(V);
 591 }
 592
 593 //===----------------------------------------------------------------------===//
 594 //                       ValueNumberedSet Class
 595 //===----------------------------------------------------------------------===//
 596 namespace {
 597 class VISIBILITY_HIDDEN ValueNumberedSet {
 598   private:
 599     SmallPtrSet<Value*, 8> contents;
 600     SparseBitVector<64> numbers;
 601   public:
 602     ValueNumberedSet() { }
 603     ValueNumberedSet(const ValueNumberedSet& other) {
 604       numbers = other.numbers;
 605       contents = other.contents;
 606     }
 607
 608     typedef SmallPtrSet<Value*, 8>::iterator iterator;
 609
 610     iterator begin() { return contents.begin(); }
 611     iterator end() { return contents.end(); }
 612
 613     bool insert(Value* v) { return contents.insert(v); }
 614     void insert(iterator I, iterator E) { contents.insert(I, E); }
 615     void erase(Value* v) { contents.erase(v); }
 616     unsigned count(Value* v) { return contents.count(v); }
 617     size_t size() { return contents.size(); }
 618
 619     void set(unsigned i)  {
 620       numbers.set(i);
 621     }
 622
 623     void operator=(const ValueNumberedSet& other) {
 624       contents = other.contents;
 625       numbers = other.numbers;
 626     }
 627
 628     void reset(unsigned i)  {
 629       numbers.reset(i);
 630     }
 631
 632     bool test(unsigned i)  {
 633       return numbers.test(i);
 634     }
 635 };
 636 }
 637
 638 //===----------------------------------------------------------------------===//
 639 //                         GVN Pass
 640 //===----------------------------------------------------------------------===//
 641
 642 namespace {
 643
 644   class VISIBILITY_HIDDEN GVN : public FunctionPass {
 645     bool runOnFunction(Function &F);
 646   public:
 647     static char ID; // Pass identification, replacement for typeid
 648     GVN() : FunctionPass((intptr_t)&ID) { }
 649
 650   private:
 651     ValueTable VN;
 652
 653     DenseMap<BasicBlock*, ValueNumberedSet> availableOut;
 654
 655     typedef DenseMap<Value*, SmallPtrSet<Instruction*, 4> > PhiMapType;
 656     PhiMapType phiMap;
 657
 658
 659     // This transformation requires dominator postdominator info
 660     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 661       AU.setPreservesCFG();
 662       AU.addRequired<DominatorTree>();
 663       AU.addRequired<MemoryDependenceAnalysis>();
 664       AU.addRequired<AliasAnalysis>();
 665       AU.addPreserved<AliasAnalysis>();
 666       AU.addPreserved<MemoryDependenceAnalysis>();
 667     }
 668
 669     // Helper fuctions
 670     // FIXME: eliminate or document these better
 671     Value* find_leader(ValueNumberedSet& vals, uint32_t v) ;
 672     void val_insert(ValueNumberedSet& s, Value* v);
 673     bool processLoad(LoadInst* L,
 674                      DenseMap<Value*, LoadInst*> &lastLoad,
 675                      SmallVectorImpl<Instruction*> &toErase);
 676     bool processInstruction(Instruction* I,
 677                             ValueNumberedSet& currAvail,
 678                             DenseMap<Value*, LoadInst*>& lastSeenLoad,
 679                             SmallVectorImpl<Instruction*> &toErase);
 680     bool processNonLocalLoad(LoadInst* L,
 681                              SmallVectorImpl<Instruction*> &toErase);
 682     Value *GetValueForBlock(BasicBlock *BB, LoadInst* orig,
 683                             DenseMap<BasicBlock*, Value*> &Phis,
 684                             bool top_level = false);
 685     void dump(DenseMap<BasicBlock*, Value*>& d);
 686     bool iterateOnFunction(Function &F);
 687     Value* CollapsePhi(PHINode* p);
 688     bool isSafeReplacement(PHINode* p, Instruction* inst);
 689   };
 690
 691   char GVN::ID = 0;
 692 }
 693
 694 // createGVNPass - The public interface to this file...
 695 FunctionPass *llvm::createGVNPass() { return new GVN(); }
 696
 697 static RegisterPass<GVN> X("gvn",
 698                            "Global Value Numbering");
 699
 700 /// find_leader - Given a set and a value number, return the first
 701 /// element of the set with that value number, or 0 if no such element
 702 /// is present
 703 Value* GVN::find_leader(ValueNumberedSet& vals, uint32_t v) {
 704   if (!vals.test(v))
 705     return 0;
 706
 707   for (ValueNumberedSet::iterator I = vals.begin(), E = vals.end();
 708        I != E; ++I)
 709     if (v == VN.lookup(*I))
 710       return *I;
 711
 712   assert(0 && "No leader found, but present bit is set?");
 713   return 0;
 714 }
 715
 716 /// val_insert - Insert a value into a set only if there is not a value
 717 /// with the same value number already in the set
 718 void GVN::val_insert(ValueNumberedSet& s, Value* v) {
 719   uint32_t num = VN.lookup(v);
 720   if (!s.test(num))
 721     s.insert(v);
 722 }
 723
 724 void GVN::dump(DenseMap<BasicBlock*, Value*>& d) {
 725   printf("{\n");
 726   for (DenseMap<BasicBlock*, Value*>::iterator I = d.begin(),
 727        E = d.end(); I != E; ++I) {
 728     if (I->second == MemoryDependenceAnalysis::None)
 729       printf("None\n");
 730     else
 731       I->second->dump();
 732   }
 733   printf("}\n");
 734 }
 735
 736 Value* GVN::CollapsePhi(PHINode* p) {
 737   DominatorTree &DT = getAnalysis<DominatorTree>();
 738   Value* constVal = p->hasConstantValue();
 739
 740   if (!constVal) return 0;
 741
 742   Instruction* inst = dyn_cast<Instruction>(constVal);
 743   if (!inst)
 744     return constVal;
 745
 746   if (DT.dominates(inst, p))
 747     if (isSafeReplacement(p, inst))
 748       return inst;
 749   return 0;
 750 }
 751
 752 bool GVN::isSafeReplacement(PHINode* p, Instruction* inst) {
 753   if (!isa<PHINode>(inst))
 754     return true;
 755
 756   for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end();
 757        UI != E; ++UI)
 758     if (PHINode* use_phi = dyn_cast<PHINode>(UI))
 759       if (use_phi->getParent() == inst->getParent())
 760         return false;
 761
 762   return true;
 763 }
 764
 765 /// GetValueForBlock - Get the value to use within the specified basic block.
 766 /// available values are in Phis.
 767 Value *GVN::GetValueForBlock(BasicBlock *BB, LoadInst* orig,
 768                              DenseMap<BasicBlock*, Value*> &Phis,
 769                              bool top_level) {
 770
 771   // If we have already computed this value, return the previously computed val.
 772   DenseMap<BasicBlock*, Value*>::iterator V = Phis.find(BB);
 773   if (V != Phis.end() && !top_level) return V->second;
 774
 775   BasicBlock* singlePred = BB->getSinglePredecessor();
 776   if (singlePred) {
 777     Value *ret = GetValueForBlock(singlePred, orig, Phis);
 778     Phis[BB] = ret;
 779     return ret;
 780   }
 781
 782   // Otherwise, the idom is the loop, so we need to insert a PHI node.  Do so
 783   // now, then get values to fill in the incoming values for the PHI.
 784   PHINode *PN = PHINode::Create(orig->getType(), orig->getName()+".rle",
 785                                 BB->begin());
 786   PN->reserveOperandSpace(std::distance(pred_begin(BB), pred_end(BB)));
 787
 788   if (Phis.count(BB) == 0)
 789     Phis.insert(std::make_pair(BB, PN));
 790
 791   // Fill in the incoming values for the block.
 792   for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 793     Value* val = GetValueForBlock(*PI, orig, Phis);
 794     PN->addIncoming(val, *PI);
 795   }
 796
 797   AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
 798   AA.copyValue(orig, PN);
 799
 800   // Attempt to collapse PHI nodes that are trivially redundant
 801   Value* v = CollapsePhi(PN);
 802   if (!v) {
 803     // Cache our phi construction results
 804     phiMap[orig->getPointerOperand()].insert(PN);
 805     return PN;
 806   }
 807
 808   MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
 809
 810   MD.removeInstruction(PN);
 811   PN->replaceAllUsesWith(v);
 812
 813   for (DenseMap<BasicBlock*, Value*>::iterator I = Phis.begin(),
 814        E = Phis.end(); I != E; ++I)
 815     if (I->second == PN)
 816       I->second = v;
 817
 818   PN->eraseFromParent();
 819
 820   Phis[BB] = v;
 821   return v;
 822 }
 823
 824 /// processNonLocalLoad - Attempt to eliminate a load whose dependencies are
 825 /// non-local by performing PHI construction.
 826 bool GVN::processNonLocalLoad(LoadInst* L,
 827                               SmallVectorImpl<Instruction*> &toErase) {
 828   MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
 829
 830   // Find the non-local dependencies of the load
 831   DenseMap<BasicBlock*, Value*> deps;
 832   MD.getNonLocalDependency(L, deps);
 833
 834   DenseMap<BasicBlock*, Value*> repl;
 835
 836   // Filter out useless results (non-locals, etc)
 837   for (DenseMap<BasicBlock*, Value*>::iterator I = deps.begin(), E = deps.end();
 838        I != E; ++I) {
 839     if (I->second == MemoryDependenceAnalysis::None)
 840       return false;
 841
 842     if (I->second == MemoryDependenceAnalysis::NonLocal)
 843       continue;
 844
 845     if (StoreInst* S = dyn_cast<StoreInst>(I->second)) {
 846       if (S->getPointerOperand() != L->getPointerOperand())
 847         return false;
 848       repl[I->first] = S->getOperand(0);
 849     } else if (LoadInst* LD = dyn_cast<LoadInst>(I->second)) {
 850       if (LD->getPointerOperand() != L->getPointerOperand())
 851         return false;
 852       repl[I->first] = LD;
 853     } else {
 854       return false;
 855     }
 856   }
 857
 858   // Use cached PHI construction information from previous runs
 859   SmallPtrSet<Instruction*, 4>& p = phiMap[L->getPointerOperand()];
 860   for (SmallPtrSet<Instruction*, 4>::iterator I = p.begin(), E = p.end();
 861        I != E; ++I) {
 862     if ((*I)->getParent() == L->getParent()) {
 863       MD.removeInstruction(L);
 864       L->replaceAllUsesWith(*I);
 865       toErase.push_back(L);
 866       NumGVNLoad++;
 867       return true;
 868     }
 869
 870     repl.insert(std::make_pair((*I)->getParent(), *I));
 871   }
 872
 873   // Perform PHI construction
 874   SmallPtrSet<BasicBlock*, 4> visited;
 875   Value* v = GetValueForBlock(L->getParent(), L, repl, true);
 876
 877   MD.removeInstruction(L);
 878   L->replaceAllUsesWith(v);
 879   toErase.push_back(L);
 880   NumGVNLoad++;
 881
 882   return true;
 883 }
 884
 885 /// processLoad - Attempt to eliminate a load, first by eliminating it
 886 /// locally, and then attempting non-local elimination if that fails.
 887 bool GVN::processLoad(LoadInst *L, DenseMap<Value*, LoadInst*> &lastLoad,
 888                       SmallVectorImpl<Instruction*> &toErase) {
 889   if (L->isVolatile()) {
 890     lastLoad[L->getPointerOperand()] = L;
 891     return false;
 892   }
 893
 894   Value* pointer = L->getPointerOperand();
 895   LoadInst*& last = lastLoad[pointer];
 896
 897   // ... to a pointer that has been loaded from before...
 898   MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
 899   bool removedNonLocal = false;
 900   Instruction* dep = MD.getDependency(L);
 901   if (dep == MemoryDependenceAnalysis::NonLocal &&
 902       L->getParent() != &L->getParent()->getParent()->getEntryBlock()) {
 903     removedNonLocal = processNonLocalLoad(L, toErase);
 904
 905     if (!removedNonLocal)
 906       last = L;
 907
 908     return removedNonLocal;
 909   }
 910
 911
 912   bool deletedLoad = false;
 913
 914   // Walk up the dependency chain until we either find
 915   // a dependency we can use, or we can't walk any further
 916   while (dep != MemoryDependenceAnalysis::None &&
 917          dep != MemoryDependenceAnalysis::NonLocal &&
 918          (isa<LoadInst>(dep) || isa<StoreInst>(dep))) {
 919     // ... that depends on a store ...
 920     if (StoreInst* S = dyn_cast<StoreInst>(dep)) {
 921       if (S->getPointerOperand() == pointer) {
 922         // Remove it!
 923         MD.removeInstruction(L);
 924
 925         L->replaceAllUsesWith(S->getOperand(0));
 926         toErase.push_back(L);
 927         deletedLoad = true;
 928         NumGVNLoad++;
 929       }
 930
 931       // Whether we removed it or not, we can't
 932       // go any further
 933       break;
 934     } else if (!last) {
 935       // If we don't depend on a store, and we haven't
 936       // been loaded before, bail.
 937       break;
 938     } else if (dep == last) {
 939       // Remove it!
 940       MD.removeInstruction(L);
 941
 942       L->replaceAllUsesWith(last);
 943       toErase.push_back(L);
 944       deletedLoad = true;
 945       NumGVNLoad++;
 946
 947       break;
 948     } else {
 949       dep = MD.getDependency(L, dep);
 950     }
 951   }
 952
 953   if (dep != MemoryDependenceAnalysis::None &&
 954       dep != MemoryDependenceAnalysis::NonLocal &&
 955       isa<AllocationInst>(dep)) {
 956     // Check that this load is actually from the
 957     // allocation we found
 958     Value* v = L->getOperand(0);
 959     while (true) {
 960       if (BitCastInst *BC = dyn_cast<BitCastInst>(v))
 961         v = BC->getOperand(0);
 962       else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(v))
 963         v = GEP->getOperand(0);
 964       else
 965         break;
 966     }
 967     if (v == dep) {
 968       // If this load depends directly on an allocation, there isn't
 969       // anything stored there; therefore, we can optimize this load
 970       // to undef.
 971       MD.removeInstruction(L);
 972
 973       L->replaceAllUsesWith(UndefValue::get(L->getType()));
 974       toErase.push_back(L);
 975       deletedLoad = true;
 976       NumGVNLoad++;
 977     }
 978   }
 979
 980   if (!deletedLoad)
 981     last = L;
 982
 983   return deletedLoad;
 984 }
 985
 986 /// processInstruction - When calculating availability, handle an instruction
 987 /// by inserting it into the appropriate sets
 988 bool GVN::processInstruction(Instruction *I, ValueNumberedSet &currAvail,
 989                              DenseMap<Value*, LoadInst*> &lastSeenLoad,
 990                              SmallVectorImpl<Instruction*> &toErase) {
 991   if (LoadInst* L = dyn_cast<LoadInst>(I))
 992     return processLoad(L, lastSeenLoad, toErase);
 993
 994   // Allocations are always uniquely numbered, so we can save time and memory
 995   // by fast failing them.
 996   if (isa<AllocationInst>(I))
 997     return false;
 998
 999   unsigned num = VN.lookup_or_add(I);
1000
1001   // Collapse PHI nodes
1002   if (PHINode* p = dyn_cast<PHINode>(I)) {
1003     Value* constVal = CollapsePhi(p);
1004
1005     if (constVal) {
1006       for (PhiMapType::iterator PI = phiMap.begin(), PE = phiMap.end();
1007            PI != PE; ++PI)
1008         if (PI->second.count(p))
1009           PI->second.erase(p);
1010
1011       p->replaceAllUsesWith(constVal);
1012       toErase.push_back(p);
1013     }
1014   // Perform value-number based elimination
1015   } else if (currAvail.test(num)) {
1016     Value* repl = find_leader(currAvail, num);
1017
1018     // Remove it!
1019     MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
1020     MD.removeInstruction(I);
1021
1022     VN.erase(I);
1023     I->replaceAllUsesWith(repl);
1024     toErase.push_back(I);
1025     return true;
1026   } else if (!I->isTerminator()) {
1027     currAvail.set(num);
1028     currAvail.insert(I);
1029   }
1030
1031   return false;
1032 }
1033
1034 // GVN::runOnFunction - This is the main transformation entry point for a
1035 // function.
1036 //
1037 bool GVN::runOnFunction(Function& F) {
1038   VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>());
1039   VN.setMemDep(&getAnalysis<MemoryDependenceAnalysis>());
1040
1041   bool changed = false;
1042   bool shouldContinue = true;
1043
1044   while (shouldContinue) {
1045     shouldContinue = iterateOnFunction(F);
1046     changed |= shouldContinue;
1047   }
1048
1049   return changed;
1050 }
1051
1052
1053 // GVN::iterateOnFunction - Executes one iteration of GVN
1054 bool GVN::iterateOnFunction(Function &F) {
1055   // Clean out global sets from any previous functions
1056   VN.clear();
1057   availableOut.clear();
1058   phiMap.clear();
1059
1060   bool changed_function = false;
1061
1062   DominatorTree &DT = getAnalysis<DominatorTree>();
1063
1064   SmallVector<Instruction*, 8> toErase;
1065   DenseMap<Value*, LoadInst*> lastSeenLoad;
1066   DenseMap<DomTreeNode*, size_t> numChildrenVisited;
1067
1068   // Top-down walk of the dominator tree
1069   for (df_iterator<DomTreeNode*> DI = df_begin(DT.getRootNode()),
1070          E = df_end(DT.getRootNode()); DI != E; ++DI) {
1071
1072     // Get the set to update for this block
1073     ValueNumberedSet& currAvail = availableOut[DI->getBlock()];
1074     lastSeenLoad.clear();
1075
1076     BasicBlock* BB = DI->getBlock();
1077
1078     // A block inherits AVAIL_OUT from its dominator
1079     if (DI->getIDom() != 0) {
1080       currAvail = availableOut[DI->getIDom()->getBlock()];
1081
1082       numChildrenVisited[DI->getIDom()]++;
1083
1084       if (numChildrenVisited[DI->getIDom()] == DI->getIDom()->getNumChildren()) {
1085         availableOut.erase(DI->getIDom()->getBlock());
1086         numChildrenVisited.erase(DI->getIDom());
1087       }
1088     }
1089
1090     for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1091          BI != BE;) {
1092       changed_function |= processInstruction(BI, currAvail,
1093                                              lastSeenLoad, toErase);
1094       if (toErase.empty()) {
1095         ++BI;
1096         continue;
1097       }
1098
1099       // If we need some instructions deleted, do it now.
1100       NumGVNInstr += toErase.size();
1101
1102       // Avoid iterator invalidation.
1103       bool AtStart = BI == BB->begin();
1104       if (!AtStart)
1105         --BI;
1106
1107       for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(),
1108            E = toErase.end(); I != E; ++I)
1109         (*I)->eraseFromParent();
1110
1111       if (AtStart)
1112         BI = BB->begin();
1113       else
1114         ++BI;
1115
1116       toErase.clear();
1117     }
1118   }
1119
1120   return changed_function;
1121 }