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 // Note that this pass does the value numbering itself; it does not use the
  14 // ValueNumbering analysis passes.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #define DEBUG_TYPE "gvn"
  19 #include "llvm/Transforms/Scalar.h"
  20 #include "llvm/BasicBlock.h"
  21 #include "llvm/Constants.h"
  22 #include "llvm/DerivedTypes.h"
  23 #include "llvm/Function.h"
  24 #include "llvm/IntrinsicInst.h"
  25 #include "llvm/LLVMContext.h"
  26 #include "llvm/Operator.h"
  27 #include "llvm/Value.h"
  28 #include "llvm/ADT/DenseMap.h"
  29 #include "llvm/ADT/DepthFirstIterator.h"
  30 #include "llvm/ADT/PostOrderIterator.h"
  31 #include "llvm/ADT/SmallPtrSet.h"
  32 #include "llvm/ADT/SmallVector.h"
  33 #include "llvm/ADT/Statistic.h"
  34 #include "llvm/Analysis/Dominators.h"
  35 #include "llvm/Analysis/AliasAnalysis.h"
  36 #include "llvm/Analysis/MallocHelper.h"
  37 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
  38 #include "llvm/Support/CFG.h"
  39 #include "llvm/Support/CommandLine.h"
  40 #include "llvm/Support/Debug.h"
  41 #include "llvm/Support/ErrorHandling.h"
  42 #include "llvm/Support/GetElementPtrTypeIterator.h"
  43 #include "llvm/Support/raw_ostream.h"
  44 #include "llvm/Target/TargetData.h"
  45 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  46 #include "llvm/Transforms/Utils/Local.h"
  47 #include "llvm/Transforms/Utils/SSAUpdater.h"
  48 #include <cstdio>
  49 using namespace llvm;
  50
  51 STATISTIC(NumGVNInstr,  "Number of instructions deleted");
  52 STATISTIC(NumGVNLoad,   "Number of loads deleted");
  53 STATISTIC(NumGVNPRE,    "Number of instructions PRE'd");
  54 STATISTIC(NumGVNBlocks, "Number of blocks merged");
  55 STATISTIC(NumPRELoad,   "Number of loads PRE'd");
  56
  57 static cl::opt<bool> EnablePRE("enable-pre",
  58                                cl::init(true), cl::Hidden);
  59 static cl::opt<bool> EnableLoadPRE("enable-load-pre", cl::init(true));
  60
  61 //===----------------------------------------------------------------------===//
  62 //                         ValueTable Class
  63 //===----------------------------------------------------------------------===//
  64
  65 /// This class holds the mapping between values and value numbers.  It is used
  66 /// as an efficient mechanism to determine the expression-wise equivalence of
  67 /// two values.
  68 namespace {
  69   struct Expression {
  70     enum ExpressionOpcode { ADD, FADD, SUB, FSUB, MUL, FMUL,
  71                             UDIV, SDIV, FDIV, UREM, SREM,
  72                             FREM, SHL, LSHR, ASHR, AND, OR, XOR, ICMPEQ,
  73                             ICMPNE, ICMPUGT, ICMPUGE, ICMPULT, ICMPULE,
  74                             ICMPSGT, ICMPSGE, ICMPSLT, ICMPSLE, FCMPOEQ,
  75                             FCMPOGT, FCMPOGE, FCMPOLT, FCMPOLE, FCMPONE,
  76                             FCMPORD, FCMPUNO, FCMPUEQ, FCMPUGT, FCMPUGE,
  77                             FCMPULT, FCMPULE, FCMPUNE, EXTRACT, INSERT,
  78                             SHUFFLE, SELECT, TRUNC, ZEXT, SEXT, FPTOUI,
  79                             FPTOSI, UITOFP, SITOFP, FPTRUNC, FPEXT,
  80                             PTRTOINT, INTTOPTR, BITCAST, GEP, CALL, CONSTANT,
  81                             EMPTY, TOMBSTONE };
  82
  83     ExpressionOpcode opcode;
  84     const Type* type;
  85     uint32_t firstVN;
  86     uint32_t secondVN;
  87     uint32_t thirdVN;
  88     SmallVector<uint32_t, 4> varargs;
  89     Value *function;
  90
  91     Expression() { }
  92     Expression(ExpressionOpcode o) : opcode(o) { }
  93
  94     bool operator==(const Expression &other) const {
  95       if (opcode != other.opcode)
  96         return false;
  97       else if (opcode == EMPTY || opcode == TOMBSTONE)
  98         return true;
  99       else if (type != other.type)
 100         return false;
 101       else if (function != other.function)
 102         return false;
 103       else if (firstVN != other.firstVN)
 104         return false;
 105       else if (secondVN != other.secondVN)
 106         return false;
 107       else if (thirdVN != other.thirdVN)
 108         return false;
 109       else {
 110         if (varargs.size() != other.varargs.size())
 111           return false;
 112
 113         for (size_t i = 0; i < varargs.size(); ++i)
 114           if (varargs[i] != other.varargs[i])
 115             return false;
 116
 117         return true;
 118       }
 119     }
 120
 121     bool operator!=(const Expression &other) const {
 122       return !(*this == other);
 123     }
 124   };
 125
 126   class ValueTable {
 127     private:
 128       DenseMap<Value*, uint32_t> valueNumbering;
 129       DenseMap<Expression, uint32_t> expressionNumbering;
 130       AliasAnalysis* AA;
 131       MemoryDependenceAnalysis* MD;
 132       DominatorTree* DT;
 133
 134       uint32_t nextValueNumber;
 135
 136       Expression::ExpressionOpcode getOpcode(BinaryOperator* BO);
 137       Expression::ExpressionOpcode getOpcode(CmpInst* C);
 138       Expression::ExpressionOpcode getOpcode(CastInst* C);
 139       Expression create_expression(BinaryOperator* BO);
 140       Expression create_expression(CmpInst* C);
 141       Expression create_expression(ShuffleVectorInst* V);
 142       Expression create_expression(ExtractElementInst* C);
 143       Expression create_expression(InsertElementInst* V);
 144       Expression create_expression(SelectInst* V);
 145       Expression create_expression(CastInst* C);
 146       Expression create_expression(GetElementPtrInst* G);
 147       Expression create_expression(CallInst* C);
 148       Expression create_expression(Constant* 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       AliasAnalysis *getAliasAnalysis() const { return AA; }
 159       void setMemDep(MemoryDependenceAnalysis* M) { MD = M; }
 160       void setDomTree(DominatorTree* D) { DT = D; }
 161       uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
 162       void verifyRemoved(const Value *) const;
 163   };
 164 }
 165
 166 namespace llvm {
 167 template <> struct DenseMapInfo<Expression> {
 168   static inline Expression getEmptyKey() {
 169     return Expression(Expression::EMPTY);
 170   }
 171
 172   static inline Expression getTombstoneKey() {
 173     return Expression(Expression::TOMBSTONE);
 174   }
 175
 176   static unsigned getHashValue(const Expression e) {
 177     unsigned hash = e.opcode;
 178
 179     hash = e.firstVN + hash * 37;
 180     hash = e.secondVN + hash * 37;
 181     hash = e.thirdVN + hash * 37;
 182
 183     hash = ((unsigned)((uintptr_t)e.type >> 4) ^
 184             (unsigned)((uintptr_t)e.type >> 9)) +
 185            hash * 37;
 186
 187     for (SmallVector<uint32_t, 4>::const_iterator I = e.varargs.begin(),
 188          E = e.varargs.end(); I != E; ++I)
 189       hash = *I + hash * 37;
 190
 191     hash = ((unsigned)((uintptr_t)e.function >> 4) ^
 192             (unsigned)((uintptr_t)e.function >> 9)) +
 193            hash * 37;
 194
 195     return hash;
 196   }
 197   static bool isEqual(const Expression &LHS, const Expression &RHS) {
 198     return LHS == RHS;
 199   }
 200   static bool isPod() { return true; }
 201 };
 202 }
 203
 204 //===----------------------------------------------------------------------===//
 205 //                     ValueTable Internal Functions
 206 //===----------------------------------------------------------------------===//
 207 Expression::ExpressionOpcode ValueTable::getOpcode(BinaryOperator* BO) {
 208   switch(BO->getOpcode()) {
 209   default: // THIS SHOULD NEVER HAPPEN
 210     llvm_unreachable("Binary operator with unknown opcode?");
 211   case Instruction::Add:  return Expression::ADD;
 212   case Instruction::FAdd: return Expression::FADD;
 213   case Instruction::Sub:  return Expression::SUB;
 214   case Instruction::FSub: return Expression::FSUB;
 215   case Instruction::Mul:  return Expression::MUL;
 216   case Instruction::FMul: return Expression::FMUL;
 217   case Instruction::UDiv: return Expression::UDIV;
 218   case Instruction::SDiv: return Expression::SDIV;
 219   case Instruction::FDiv: return Expression::FDIV;
 220   case Instruction::URem: return Expression::UREM;
 221   case Instruction::SRem: return Expression::SREM;
 222   case Instruction::FRem: return Expression::FREM;
 223   case Instruction::Shl:  return Expression::SHL;
 224   case Instruction::LShr: return Expression::LSHR;
 225   case Instruction::AShr: return Expression::ASHR;
 226   case Instruction::And:  return Expression::AND;
 227   case Instruction::Or:   return Expression::OR;
 228   case Instruction::Xor:  return Expression::XOR;
 229   }
 230 }
 231
 232 Expression::ExpressionOpcode ValueTable::getOpcode(CmpInst* C) {
 233   if (isa<ICmpInst>(C)) {
 234     switch (C->getPredicate()) {
 235     default:  // THIS SHOULD NEVER HAPPEN
 236       llvm_unreachable("Comparison with unknown predicate?");
 237     case ICmpInst::ICMP_EQ:  return Expression::ICMPEQ;
 238     case ICmpInst::ICMP_NE:  return Expression::ICMPNE;
 239     case ICmpInst::ICMP_UGT: return Expression::ICMPUGT;
 240     case ICmpInst::ICMP_UGE: return Expression::ICMPUGE;
 241     case ICmpInst::ICMP_ULT: return Expression::ICMPULT;
 242     case ICmpInst::ICMP_ULE: return Expression::ICMPULE;
 243     case ICmpInst::ICMP_SGT: return Expression::ICMPSGT;
 244     case ICmpInst::ICMP_SGE: return Expression::ICMPSGE;
 245     case ICmpInst::ICMP_SLT: return Expression::ICMPSLT;
 246     case ICmpInst::ICMP_SLE: return Expression::ICMPSLE;
 247     }
 248   } else {
 249     switch (C->getPredicate()) {
 250     default: // THIS SHOULD NEVER HAPPEN
 251       llvm_unreachable("Comparison with unknown predicate?");
 252     case FCmpInst::FCMP_OEQ: return Expression::FCMPOEQ;
 253     case FCmpInst::FCMP_OGT: return Expression::FCMPOGT;
 254     case FCmpInst::FCMP_OGE: return Expression::FCMPOGE;
 255     case FCmpInst::FCMP_OLT: return Expression::FCMPOLT;
 256     case FCmpInst::FCMP_OLE: return Expression::FCMPOLE;
 257     case FCmpInst::FCMP_ONE: return Expression::FCMPONE;
 258     case FCmpInst::FCMP_ORD: return Expression::FCMPORD;
 259     case FCmpInst::FCMP_UNO: return Expression::FCMPUNO;
 260     case FCmpInst::FCMP_UEQ: return Expression::FCMPUEQ;
 261     case FCmpInst::FCMP_UGT: return Expression::FCMPUGT;
 262     case FCmpInst::FCMP_UGE: return Expression::FCMPUGE;
 263     case FCmpInst::FCMP_ULT: return Expression::FCMPULT;
 264     case FCmpInst::FCMP_ULE: return Expression::FCMPULE;
 265     case FCmpInst::FCMP_UNE: return Expression::FCMPUNE;
 266     }
 267   }
 268 }
 269
 270 Expression::ExpressionOpcode ValueTable::getOpcode(CastInst* C) {
 271   switch(C->getOpcode()) {
 272   default: // THIS SHOULD NEVER HAPPEN
 273     llvm_unreachable("Cast operator with unknown opcode?");
 274   case Instruction::Trunc:    return Expression::TRUNC;
 275   case Instruction::ZExt:     return Expression::ZEXT;
 276   case Instruction::SExt:     return Expression::SEXT;
 277   case Instruction::FPToUI:   return Expression::FPTOUI;
 278   case Instruction::FPToSI:   return Expression::FPTOSI;
 279   case Instruction::UIToFP:   return Expression::UITOFP;
 280   case Instruction::SIToFP:   return Expression::SITOFP;
 281   case Instruction::FPTrunc:  return Expression::FPTRUNC;
 282   case Instruction::FPExt:    return Expression::FPEXT;
 283   case Instruction::PtrToInt: return Expression::PTRTOINT;
 284   case Instruction::IntToPtr: return Expression::INTTOPTR;
 285   case Instruction::BitCast:  return Expression::BITCAST;
 286   }
 287 }
 288
 289 Expression ValueTable::create_expression(CallInst* C) {
 290   Expression e;
 291
 292   e.type = C->getType();
 293   e.firstVN = 0;
 294   e.secondVN = 0;
 295   e.thirdVN = 0;
 296   e.function = C->getCalledFunction();
 297   e.opcode = Expression::CALL;
 298
 299   for (CallInst::op_iterator I = C->op_begin()+1, E = C->op_end();
 300        I != E; ++I)
 301     e.varargs.push_back(lookup_or_add(*I));
 302
 303   return e;
 304 }
 305
 306 Expression ValueTable::create_expression(BinaryOperator* BO) {
 307   Expression e;
 308
 309   e.firstVN = lookup_or_add(BO->getOperand(0));
 310   e.secondVN = lookup_or_add(BO->getOperand(1));
 311   e.thirdVN = 0;
 312   e.function = 0;
 313   e.type = BO->getType();
 314   e.opcode = getOpcode(BO);
 315
 316   return e;
 317 }
 318
 319 Expression ValueTable::create_expression(CmpInst* C) {
 320   Expression e;
 321
 322   e.firstVN = lookup_or_add(C->getOperand(0));
 323   e.secondVN = lookup_or_add(C->getOperand(1));
 324   e.thirdVN = 0;
 325   e.function = 0;
 326   e.type = C->getType();
 327   e.opcode = getOpcode(C);
 328
 329   return e;
 330 }
 331
 332 Expression ValueTable::create_expression(CastInst* C) {
 333   Expression e;
 334
 335   e.firstVN = lookup_or_add(C->getOperand(0));
 336   e.secondVN = 0;
 337   e.thirdVN = 0;
 338   e.function = 0;
 339   e.type = C->getType();
 340   e.opcode = getOpcode(C);
 341
 342   return e;
 343 }
 344
 345 Expression ValueTable::create_expression(ShuffleVectorInst* S) {
 346   Expression e;
 347
 348   e.firstVN = lookup_or_add(S->getOperand(0));
 349   e.secondVN = lookup_or_add(S->getOperand(1));
 350   e.thirdVN = lookup_or_add(S->getOperand(2));
 351   e.function = 0;
 352   e.type = S->getType();
 353   e.opcode = Expression::SHUFFLE;
 354
 355   return e;
 356 }
 357
 358 Expression ValueTable::create_expression(ExtractElementInst* E) {
 359   Expression e;
 360
 361   e.firstVN = lookup_or_add(E->getOperand(0));
 362   e.secondVN = lookup_or_add(E->getOperand(1));
 363   e.thirdVN = 0;
 364   e.function = 0;
 365   e.type = E->getType();
 366   e.opcode = Expression::EXTRACT;
 367
 368   return e;
 369 }
 370
 371 Expression ValueTable::create_expression(InsertElementInst* I) {
 372   Expression e;
 373
 374   e.firstVN = lookup_or_add(I->getOperand(0));
 375   e.secondVN = lookup_or_add(I->getOperand(1));
 376   e.thirdVN = lookup_or_add(I->getOperand(2));
 377   e.function = 0;
 378   e.type = I->getType();
 379   e.opcode = Expression::INSERT;
 380
 381   return e;
 382 }
 383
 384 Expression ValueTable::create_expression(SelectInst* I) {
 385   Expression e;
 386
 387   e.firstVN = lookup_or_add(I->getCondition());
 388   e.secondVN = lookup_or_add(I->getTrueValue());
 389   e.thirdVN = lookup_or_add(I->getFalseValue());
 390   e.function = 0;
 391   e.type = I->getType();
 392   e.opcode = Expression::SELECT;
 393
 394   return e;
 395 }
 396
 397 Expression ValueTable::create_expression(GetElementPtrInst* G) {
 398   Expression e;
 399
 400   e.firstVN = lookup_or_add(G->getPointerOperand());
 401   e.secondVN = 0;
 402   e.thirdVN = 0;
 403   e.function = 0;
 404   e.type = G->getType();
 405   e.opcode = Expression::GEP;
 406
 407   for (GetElementPtrInst::op_iterator I = G->idx_begin(), E = G->idx_end();
 408        I != E; ++I)
 409     e.varargs.push_back(lookup_or_add(*I));
 410
 411   return e;
 412 }
 413
 414 //===----------------------------------------------------------------------===//
 415 //                     ValueTable External Functions
 416 //===----------------------------------------------------------------------===//
 417
 418 /// add - Insert a value into the table with a specified value number.
 419 void ValueTable::add(Value *V, uint32_t num) {
 420   valueNumbering.insert(std::make_pair(V, num));
 421 }
 422
 423 /// lookup_or_add - Returns the value number for the specified value, assigning
 424 /// it a new number if it did not have one before.
 425 uint32_t ValueTable::lookup_or_add(Value *V) {
 426   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 427   if (VI != valueNumbering.end())
 428     return VI->second;
 429
 430   if (CallInst* C = dyn_cast<CallInst>(V)) {
 431     if (AA->doesNotAccessMemory(C)) {
 432       Expression exp = create_expression(C);
 433       uint32_t& e = expressionNumbering[exp];
 434       if (!e) e = nextValueNumber++;
 435       valueNumbering[V] = e;
 436       return e;
 437     } else if (AA->onlyReadsMemory(C)) {
 438       Expression exp = create_expression(C);
 439       uint32_t& e = expressionNumbering[exp];
 440       if (!e) {
 441         e = nextValueNumber++;
 442         valueNumbering[V] = e;
 443         return e;
 444       }
 445
 446       MemDepResult local_dep = MD->getDependency(C);
 447
 448       if (!local_dep.isDef() && !local_dep.isNonLocal()) {
 449         valueNumbering[V] =  nextValueNumber;
 450         return nextValueNumber++;
 451       }
 452
 453       if (local_dep.isDef()) {
 454         CallInst* local_cdep = cast<CallInst>(local_dep.getInst());
 455
 456         if (local_cdep->getNumOperands() != C->getNumOperands()) {
 457           valueNumbering[V] = nextValueNumber;
 458           return nextValueNumber++;
 459         }
 460
 461         for (unsigned i = 1; i < C->getNumOperands(); ++i) {
 462           uint32_t c_vn = lookup_or_add(C->getOperand(i));
 463           uint32_t cd_vn = lookup_or_add(local_cdep->getOperand(i));
 464           if (c_vn != cd_vn) {
 465             valueNumbering[V] = nextValueNumber;
 466             return nextValueNumber++;
 467           }
 468         }
 469
 470         uint32_t v = lookup_or_add(local_cdep);
 471         valueNumbering[V] = v;
 472         return v;
 473       }
 474
 475       // Non-local case.
 476       const MemoryDependenceAnalysis::NonLocalDepInfo &deps =
 477         MD->getNonLocalCallDependency(CallSite(C));
 478       // FIXME: call/call dependencies for readonly calls should return def, not
 479       // clobber!  Move the checking logic to MemDep!
 480       CallInst* cdep = 0;
 481
 482       // Check to see if we have a single dominating call instruction that is
 483       // identical to C.
 484       for (unsigned i = 0, e = deps.size(); i != e; ++i) {
 485         const MemoryDependenceAnalysis::NonLocalDepEntry *I = &deps[i];
 486         // Ignore non-local dependencies.
 487         if (I->second.isNonLocal())
 488           continue;
 489
 490         // We don't handle non-depedencies.  If we already have a call, reject
 491         // instruction dependencies.
 492         if (I->second.isClobber() || cdep != 0) {
 493           cdep = 0;
 494           break;
 495         }
 496
 497         CallInst *NonLocalDepCall = dyn_cast<CallInst>(I->second.getInst());
 498         // FIXME: All duplicated with non-local case.
 499         if (NonLocalDepCall && DT->properlyDominates(I->first, C->getParent())){
 500           cdep = NonLocalDepCall;
 501           continue;
 502         }
 503
 504         cdep = 0;
 505         break;
 506       }
 507
 508       if (!cdep) {
 509         valueNumbering[V] = nextValueNumber;
 510         return nextValueNumber++;
 511       }
 512
 513       if (cdep->getNumOperands() != C->getNumOperands()) {
 514         valueNumbering[V] = nextValueNumber;
 515         return nextValueNumber++;
 516       }
 517       for (unsigned i = 1; i < C->getNumOperands(); ++i) {
 518         uint32_t c_vn = lookup_or_add(C->getOperand(i));
 519         uint32_t cd_vn = lookup_or_add(cdep->getOperand(i));
 520         if (c_vn != cd_vn) {
 521           valueNumbering[V] = nextValueNumber;
 522           return nextValueNumber++;
 523         }
 524       }
 525
 526       uint32_t v = lookup_or_add(cdep);
 527       valueNumbering[V] = v;
 528       return v;
 529
 530     } else {
 531       valueNumbering[V] = nextValueNumber;
 532       return nextValueNumber++;
 533     }
 534   } else if (BinaryOperator* BO = dyn_cast<BinaryOperator>(V)) {
 535     Expression exp = create_expression(BO);
 536     uint32_t& e = expressionNumbering[exp];
 537     if (!e) e = nextValueNumber++;
 538     valueNumbering[V] = e;
 539     return e;
 540   } else if (CmpInst* C = dyn_cast<CmpInst>(V)) {
 541     Expression exp = create_expression(C);
 542     uint32_t& e = expressionNumbering[exp];
 543     if (!e) e = nextValueNumber++;
 544     valueNumbering[V] = e;
 545     return e;
 546   } else if (ShuffleVectorInst* U = dyn_cast<ShuffleVectorInst>(V)) {
 547     Expression exp = create_expression(U);
 548     uint32_t& e = expressionNumbering[exp];
 549     if (!e) e = nextValueNumber++;
 550     valueNumbering[V] = e;
 551     return e;
 552   } else if (ExtractElementInst* U = dyn_cast<ExtractElementInst>(V)) {
 553     Expression exp = create_expression(U);
 554     uint32_t& e = expressionNumbering[exp];
 555     if (!e) e = nextValueNumber++;
 556     valueNumbering[V] = e;
 557     return e;
 558   } else if (InsertElementInst* U = dyn_cast<InsertElementInst>(V)) {
 559     Expression exp = create_expression(U);
 560     uint32_t& e = expressionNumbering[exp];
 561     if (!e) e = nextValueNumber++;
 562     valueNumbering[V] = e;
 563     return e;
 564   } else if (SelectInst* U = dyn_cast<SelectInst>(V)) {
 565     Expression exp = create_expression(U);
 566     uint32_t& e = expressionNumbering[exp];
 567     if (!e) e = nextValueNumber++;
 568     valueNumbering[V] = e;
 569     return e;
 570   } else if (CastInst* U = dyn_cast<CastInst>(V)) {
 571     Expression exp = create_expression(U);
 572     uint32_t& e = expressionNumbering[exp];
 573     if (!e) e = nextValueNumber++;
 574     valueNumbering[V] = e;
 575     return e;
 576   } else if (GetElementPtrInst* U = dyn_cast<GetElementPtrInst>(V)) {
 577     Expression exp = create_expression(U);
 578     uint32_t& e = expressionNumbering[exp];
 579     if (!e) e = nextValueNumber++;
 580     valueNumbering[V] = e;
 581     return e;
 582   } else {
 583     valueNumbering[V] = nextValueNumber;
 584     return nextValueNumber++;
 585   }
 586 }
 587
 588 /// lookup - Returns the value number of the specified value. Fails if
 589 /// the value has not yet been numbered.
 590 uint32_t ValueTable::lookup(Value *V) const {
 591   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 592   assert(VI != valueNumbering.end() && "Value not numbered?");
 593   return VI->second;
 594 }
 595
 596 /// clear - Remove all entries from the ValueTable
 597 void ValueTable::clear() {
 598   valueNumbering.clear();
 599   expressionNumbering.clear();
 600   nextValueNumber = 1;
 601 }
 602
 603 /// erase - Remove a value from the value numbering
 604 void ValueTable::erase(Value *V) {
 605   valueNumbering.erase(V);
 606 }
 607
 608 /// verifyRemoved - Verify that the value is removed from all internal data
 609 /// structures.
 610 void ValueTable::verifyRemoved(const Value *V) const {
 611   for (DenseMap<Value*, uint32_t>::iterator
 612          I = valueNumbering.begin(), E = valueNumbering.end(); I != E; ++I) {
 613     assert(I->first != V && "Inst still occurs in value numbering map!");
 614   }
 615 }
 616
 617 //===----------------------------------------------------------------------===//
 618 //                                GVN Pass
 619 //===----------------------------------------------------------------------===//
 620
 621 namespace {
 622   struct ValueNumberScope {
 623     ValueNumberScope* parent;
 624     DenseMap<uint32_t, Value*> table;
 625
 626     ValueNumberScope(ValueNumberScope* p) : parent(p) { }
 627   };
 628 }
 629
 630 namespace {
 631
 632   class GVN : public FunctionPass {
 633     bool runOnFunction(Function &F);
 634   public:
 635     static char ID; // Pass identification, replacement for typeid
 636     GVN() : FunctionPass(&ID) { }
 637
 638   private:
 639     MemoryDependenceAnalysis *MD;
 640     DominatorTree *DT;
 641
 642     ValueTable VN;
 643     DenseMap<BasicBlock*, ValueNumberScope*> localAvail;
 644
 645     // This transformation requires dominator postdominator info
 646     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 647       AU.addRequired<DominatorTree>();
 648       AU.addRequired<MemoryDependenceAnalysis>();
 649       AU.addRequired<AliasAnalysis>();
 650
 651       AU.addPreserved<DominatorTree>();
 652       AU.addPreserved<AliasAnalysis>();
 653     }
 654
 655     // Helper fuctions
 656     // FIXME: eliminate or document these better
 657     bool processLoad(LoadInst* L,
 658                      SmallVectorImpl<Instruction*> &toErase);
 659     bool processInstruction(Instruction *I,
 660                             SmallVectorImpl<Instruction*> &toErase);
 661     bool processNonLocalLoad(LoadInst* L,
 662                              SmallVectorImpl<Instruction*> &toErase);
 663     bool processBlock(BasicBlock *BB);
 664     void dump(DenseMap<uint32_t, Value*>& d);
 665     bool iterateOnFunction(Function &F);
 666     Value *CollapsePhi(PHINode* p);
 667     bool performPRE(Function& F);
 668     Value *lookupNumber(BasicBlock *BB, uint32_t num);
 669     void cleanupGlobalSets();
 670     void verifyRemoved(const Instruction *I) const;
 671   };
 672
 673   char GVN::ID = 0;
 674 }
 675
 676 // createGVNPass - The public interface to this file...
 677 FunctionPass *llvm::createGVNPass() { return new GVN(); }
 678
 679 static RegisterPass<GVN> X("gvn",
 680                            "Global Value Numbering");
 681
 682 void GVN::dump(DenseMap<uint32_t, Value*>& d) {
 683   printf("{\n");
 684   for (DenseMap<uint32_t, Value*>::iterator I = d.begin(),
 685        E = d.end(); I != E; ++I) {
 686       printf("%d\n", I->first);
 687       I->second->dump();
 688   }
 689   printf("}\n");
 690 }
 691
 692 static bool isSafeReplacement(PHINode* p, Instruction *inst) {
 693   if (!isa<PHINode>(inst))
 694     return true;
 695
 696   for (Instruction::use_iterator UI = p->use_begin(), E = p->use_end();
 697        UI != E; ++UI)
 698     if (PHINode* use_phi = dyn_cast<PHINode>(UI))
 699       if (use_phi->getParent() == inst->getParent())
 700         return false;
 701
 702   return true;
 703 }
 704
 705 Value *GVN::CollapsePhi(PHINode *PN) {
 706   Value *ConstVal = PN->hasConstantValue(DT);
 707   if (!ConstVal) return 0;
 708
 709   Instruction *Inst = dyn_cast<Instruction>(ConstVal);
 710   if (!Inst)
 711     return ConstVal;
 712
 713   if (DT->dominates(Inst, PN))
 714     if (isSafeReplacement(PN, Inst))
 715       return Inst;
 716   return 0;
 717 }
 718
 719 /// IsValueFullyAvailableInBlock - Return true if we can prove that the value
 720 /// we're analyzing is fully available in the specified block.  As we go, keep
 721 /// track of which blocks we know are fully alive in FullyAvailableBlocks.  This
 722 /// map is actually a tri-state map with the following values:
 723 ///   0) we know the block *is not* fully available.
 724 ///   1) we know the block *is* fully available.
 725 ///   2) we do not know whether the block is fully available or not, but we are
 726 ///      currently speculating that it will be.
 727 ///   3) we are speculating for this block and have used that to speculate for
 728 ///      other blocks.
 729 static bool IsValueFullyAvailableInBlock(BasicBlock *BB,
 730                             DenseMap<BasicBlock*, char> &FullyAvailableBlocks) {
 731   // Optimistically assume that the block is fully available and check to see
 732   // if we already know about this block in one lookup.
 733   std::pair<DenseMap<BasicBlock*, char>::iterator, char> IV =
 734     FullyAvailableBlocks.insert(std::make_pair(BB, 2));
 735
 736   // If the entry already existed for this block, return the precomputed value.
 737   if (!IV.second) {
 738     // If this is a speculative "available" value, mark it as being used for
 739     // speculation of other blocks.
 740     if (IV.first->second == 2)
 741       IV.first->second = 3;
 742     return IV.first->second != 0;
 743   }
 744
 745   // Otherwise, see if it is fully available in all predecessors.
 746   pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 747
 748   // If this block has no predecessors, it isn't live-in here.
 749   if (PI == PE)
 750     goto SpeculationFailure;
 751
 752   for (; PI != PE; ++PI)
 753     // If the value isn't fully available in one of our predecessors, then it
 754     // isn't fully available in this block either.  Undo our previous
 755     // optimistic assumption and bail out.
 756     if (!IsValueFullyAvailableInBlock(*PI, FullyAvailableBlocks))
 757       goto SpeculationFailure;
 758
 759   return true;
 760
 761 // SpeculationFailure - If we get here, we found out that this is not, after
 762 // all, a fully-available block.  We have a problem if we speculated on this and
 763 // used the speculation to mark other blocks as available.
 764 SpeculationFailure:
 765   char &BBVal = FullyAvailableBlocks[BB];
 766
 767   // If we didn't speculate on this, just return with it set to false.
 768   if (BBVal == 2) {
 769     BBVal = 0;
 770     return false;
 771   }
 772
 773   // If we did speculate on this value, we could have blocks set to 1 that are
 774   // incorrect.  Walk the (transitive) successors of this block and mark them as
 775   // 0 if set to one.
 776   SmallVector<BasicBlock*, 32> BBWorklist;
 777   BBWorklist.push_back(BB);
 778
 779   while (!BBWorklist.empty()) {
 780     BasicBlock *Entry = BBWorklist.pop_back_val();
 781     // Note that this sets blocks to 0 (unavailable) if they happen to not
 782     // already be in FullyAvailableBlocks.  This is safe.
 783     char &EntryVal = FullyAvailableBlocks[Entry];
 784     if (EntryVal == 0) continue;  // Already unavailable.
 785
 786     // Mark as unavailable.
 787     EntryVal = 0;
 788
 789     for (succ_iterator I = succ_begin(Entry), E = succ_end(Entry); I != E; ++I)
 790       BBWorklist.push_back(*I);
 791   }
 792
 793   return false;
 794 }
 795
 796
 797 /// CanCoerceMustAliasedValueToLoad - Return true if
 798 /// CoerceAvailableValueToLoadType will succeed.
 799 static bool CanCoerceMustAliasedValueToLoad(Value *StoredVal,
 800                                             const Type *LoadTy,
 801                                             const TargetData &TD) {
 802   // If the loaded or stored value is an first class array or struct, don't try
 803   // to transform them.  We need to be able to bitcast to integer.
 804   if (isa<StructType>(LoadTy) || isa<ArrayType>(LoadTy) ||
 805       isa<StructType>(StoredVal->getType()) ||
 806       isa<ArrayType>(StoredVal->getType()))
 807     return false;
 808
 809   // The store has to be at least as big as the load.
 810   if (TD.getTypeSizeInBits(StoredVal->getType()) <
 811         TD.getTypeSizeInBits(LoadTy))
 812     return false;
 813
 814   return true;
 815 }
 816
 817
 818 /// CoerceAvailableValueToLoadType - If we saw a store of a value to memory, and
 819 /// then a load from a must-aliased pointer of a different type, try to coerce
 820 /// the stored value.  LoadedTy is the type of the load we want to replace and
 821 /// InsertPt is the place to insert new instructions.
 822 ///
 823 /// If we can't do it, return null.
 824 static Value *CoerceAvailableValueToLoadType(Value *StoredVal,
 825                                              const Type *LoadedTy,
 826                                              Instruction *InsertPt,
 827                                              const TargetData &TD) {
 828   if (!CanCoerceMustAliasedValueToLoad(StoredVal, LoadedTy, TD))
 829     return 0;
 830
 831   const Type *StoredValTy = StoredVal->getType();
 832
 833   uint64_t StoreSize = TD.getTypeSizeInBits(StoredValTy);
 834   uint64_t LoadSize = TD.getTypeSizeInBits(LoadedTy);
 835
 836   // If the store and reload are the same size, we can always reuse it.
 837   if (StoreSize == LoadSize) {
 838     if (isa<PointerType>(StoredValTy) && isa<PointerType>(LoadedTy)) {
 839       // Pointer to Pointer -> use bitcast.
 840       return new BitCastInst(StoredVal, LoadedTy, "", InsertPt);
 841     }
 842
 843     // Convert source pointers to integers, which can be bitcast.
 844     if (isa<PointerType>(StoredValTy)) {
 845       StoredValTy = TD.getIntPtrType(StoredValTy->getContext());
 846       StoredVal = new PtrToIntInst(StoredVal, StoredValTy, "", InsertPt);
 847     }
 848
 849     const Type *TypeToCastTo = LoadedTy;
 850     if (isa<PointerType>(TypeToCastTo))
 851       TypeToCastTo = TD.getIntPtrType(StoredValTy->getContext());
 852
 853     if (StoredValTy != TypeToCastTo)
 854       StoredVal = new BitCastInst(StoredVal, TypeToCastTo, "", InsertPt);
 855
 856     // Cast to pointer if the load needs a pointer type.
 857     if (isa<PointerType>(LoadedTy))
 858       StoredVal = new IntToPtrInst(StoredVal, LoadedTy, "", InsertPt);
 859
 860     return StoredVal;
 861   }
 862
 863   // If the loaded value is smaller than the available value, then we can
 864   // extract out a piece from it.  If the available value is too small, then we
 865   // can't do anything.
 866   assert(StoreSize >= LoadSize && "CanCoerceMustAliasedValueToLoad fail");
 867
 868   // Convert source pointers to integers, which can be manipulated.
 869   if (isa<PointerType>(StoredValTy)) {
 870     StoredValTy = TD.getIntPtrType(StoredValTy->getContext());
 871     StoredVal = new PtrToIntInst(StoredVal, StoredValTy, "", InsertPt);
 872   }
 873
 874   // Convert vectors and fp to integer, which can be manipulated.
 875   if (!isa<IntegerType>(StoredValTy)) {
 876     StoredValTy = IntegerType::get(StoredValTy->getContext(), StoreSize);
 877     StoredVal = new BitCastInst(StoredVal, StoredValTy, "", InsertPt);
 878   }
 879
 880   // If this is a big-endian system, we need to shift the value down to the low
 881   // bits so that a truncate will work.
 882   if (TD.isBigEndian()) {
 883     Constant *Val = ConstantInt::get(StoredVal->getType(), StoreSize-LoadSize);
 884     StoredVal = BinaryOperator::CreateLShr(StoredVal, Val, "tmp", InsertPt);
 885   }
 886
 887   // Truncate the integer to the right size now.
 888   const Type *NewIntTy = IntegerType::get(StoredValTy->getContext(), LoadSize);
 889   StoredVal = new TruncInst(StoredVal, NewIntTy, "trunc", InsertPt);
 890
 891   if (LoadedTy == NewIntTy)
 892     return StoredVal;
 893
 894   // If the result is a pointer, inttoptr.
 895   if (isa<PointerType>(LoadedTy))
 896     return new IntToPtrInst(StoredVal, LoadedTy, "inttoptr", InsertPt);
 897
 898   // Otherwise, bitcast.
 899   return new BitCastInst(StoredVal, LoadedTy, "bitcast", InsertPt);
 900 }
 901
 902 /// GetBaseWithConstantOffset - Analyze the specified pointer to see if it can
 903 /// be expressed as a base pointer plus a constant offset.  Return the base and
 904 /// offset to the caller.
 905 static Value *GetBaseWithConstantOffset(Value *Ptr, int64_t &Offset,
 906                                         const TargetData &TD) {
 907   Operator *PtrOp = dyn_cast<Operator>(Ptr);
 908   if (PtrOp == 0) return Ptr;
 909
 910   // Just look through bitcasts.
 911   if (PtrOp->getOpcode() == Instruction::BitCast)
 912     return GetBaseWithConstantOffset(PtrOp->getOperand(0), Offset, TD);
 913
 914   // If this is a GEP with constant indices, we can look through it.
 915   GEPOperator *GEP = dyn_cast<GEPOperator>(PtrOp);
 916   if (GEP == 0 || !GEP->hasAllConstantIndices()) return Ptr;
 917
 918   gep_type_iterator GTI = gep_type_begin(GEP);
 919   for (User::op_iterator I = GEP->idx_begin(), E = GEP->idx_end(); I != E;
 920        ++I, ++GTI) {
 921     ConstantInt *OpC = cast<ConstantInt>(*I);
 922     if (OpC->isZero()) continue;
 923
 924     // Handle a struct and array indices which add their offset to the pointer.
 925     if (const StructType *STy = dyn_cast<StructType>(*GTI)) {
 926       Offset += TD.getStructLayout(STy)->getElementOffset(OpC->getZExtValue());
 927     } else {
 928       uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType());
 929       Offset += OpC->getSExtValue()*Size;
 930     }
 931   }
 932
 933   // Re-sign extend from the pointer size if needed to get overflow edge cases
 934   // right.
 935   unsigned PtrSize = TD.getPointerSizeInBits();
 936   if (PtrSize < 64)
 937     Offset = (Offset << (64-PtrSize)) >> (64-PtrSize);
 938
 939   return GetBaseWithConstantOffset(GEP->getPointerOperand(), Offset, TD);
 940 }
 941
 942
 943 /// AnalyzeLoadFromClobberingStore - This function is called when we have a
 944 /// memdep query of a load that ends up being a clobbering store.  This means
 945 /// that the store *may* provide bits used by the load but we can't be sure
 946 /// because the pointers don't mustalias.  Check this case to see if there is
 947 /// anything more we can do before we give up.  This returns -1 if we have to
 948 /// give up, or a byte number in the stored value of the piece that feeds the
 949 /// load.
 950 static int AnalyzeLoadFromClobberingStore(LoadInst *L, StoreInst *DepSI,
 951                                           const TargetData &TD) {
 952   // If the loaded or stored value is an first class array or struct, don't try
 953   // to transform them.  We need to be able to bitcast to integer.
 954   if (isa<StructType>(L->getType()) || isa<ArrayType>(L->getType()) ||
 955       isa<StructType>(DepSI->getOperand(0)->getType()) ||
 956       isa<ArrayType>(DepSI->getOperand(0)->getType()))
 957     return -1;
 958
 959   int64_t StoreOffset = 0, LoadOffset = 0;
 960   Value *StoreBase =
 961     GetBaseWithConstantOffset(DepSI->getPointerOperand(), StoreOffset, TD);
 962   Value *LoadBase =
 963     GetBaseWithConstantOffset(L->getPointerOperand(), LoadOffset, TD);
 964   if (StoreBase != LoadBase)
 965     return -1;
 966
 967   // If the load and store are to the exact same address, they should have been
 968   // a must alias.  AA must have gotten confused.
 969   // FIXME: Study to see if/when this happens.
 970   if (LoadOffset == StoreOffset) {
 971 #if 0
 972     errs() << "STORE/LOAD DEP WITH COMMON POINTER MISSED:\n"
 973     << "Base       = " << *StoreBase << "\n"
 974     << "Store Ptr  = " << *DepSI->getPointerOperand() << "\n"
 975     << "Store Offs = " << StoreOffset << " - " << *DepSI << "\n"
 976     << "Load Ptr   = " << *L->getPointerOperand() << "\n"
 977     << "Load Offs  = " << LoadOffset << " - " << *L << "\n\n";
 978     errs() << "'" << L->getParent()->getParent()->getName() << "'"
 979     << *L->getParent();
 980 #endif
 981     return -1;
 982   }
 983
 984   // If the load and store don't overlap at all, the store doesn't provide
 985   // anything to the load.  In this case, they really don't alias at all, AA
 986   // must have gotten confused.
 987   // FIXME: Investigate cases where this bails out, e.g. rdar://7238614. Then
 988   // remove this check, as it is duplicated with what we have below.
 989   uint64_t StoreSize = TD.getTypeSizeInBits(DepSI->getOperand(0)->getType());
 990   uint64_t LoadSize = TD.getTypeSizeInBits(L->getType());
 991
 992   if ((StoreSize & 7) | (LoadSize & 7))
 993     return -1;
 994   StoreSize >>= 3;  // Convert to bytes.
 995   LoadSize >>= 3;
 996
 997
 998   bool isAAFailure = false;
 999   if (StoreOffset < LoadOffset) {
1000     isAAFailure = StoreOffset+int64_t(StoreSize) <= LoadOffset;
1001   } else {
1002     isAAFailure = LoadOffset+int64_t(LoadSize) <= StoreOffset;
1003   }
1004   if (isAAFailure) {
1005 #if 0
1006     errs() << "STORE LOAD DEP WITH COMMON BASE:\n"
1007     << "Base       = " << *StoreBase << "\n"
1008     << "Store Ptr  = " << *DepSI->getPointerOperand() << "\n"
1009     << "Store Offs = " << StoreOffset << " - " << *DepSI << "\n"
1010     << "Load Ptr   = " << *L->getPointerOperand() << "\n"
1011     << "Load Offs  = " << LoadOffset << " - " << *L << "\n\n";
1012     errs() << "'" << L->getParent()->getParent()->getName() << "'"
1013     << *L->getParent();
1014 #endif
1015     return -1;
1016   }
1017
1018   // If the Load isn't completely contained within the stored bits, we don't
1019   // have all the bits to feed it.  We could do something crazy in the future
1020   // (issue a smaller load then merge the bits in) but this seems unlikely to be
1021   // valuable.
1022   if (StoreOffset > LoadOffset ||
1023       StoreOffset+StoreSize < LoadOffset+LoadSize)
1024     return -1;
1025
1026   // Okay, we can do this transformation.  Return the number of bytes into the
1027   // store that the load is.
1028   return LoadOffset-StoreOffset;
1029 }
1030
1031
1032 /// GetStoreValueForLoad - This function is called when we have a
1033 /// memdep query of a load that ends up being a clobbering store.  This means
1034 /// that the store *may* provide bits used by the load but we can't be sure
1035 /// because the pointers don't mustalias.  Check this case to see if there is
1036 /// anything more we can do before we give up.
1037 static Value *GetStoreValueForLoad(Value *SrcVal, unsigned Offset,
1038                                    const Type *LoadTy,
1039                                    Instruction *InsertPt, const TargetData &TD){
1040   LLVMContext &Ctx = SrcVal->getType()->getContext();
1041
1042   uint64_t StoreSize = TD.getTypeSizeInBits(SrcVal->getType())/8;
1043   uint64_t LoadSize = TD.getTypeSizeInBits(LoadTy)/8;
1044
1045
1046   // Compute which bits of the stored value are being used by the load.  Convert
1047   // to an integer type to start with.
1048   if (isa<PointerType>(SrcVal->getType()))
1049     SrcVal = new PtrToIntInst(SrcVal, TD.getIntPtrType(Ctx), "tmp", InsertPt);
1050   if (!isa<IntegerType>(SrcVal->getType()))
1051     SrcVal = new BitCastInst(SrcVal, IntegerType::get(Ctx, StoreSize*8),
1052                              "tmp", InsertPt);
1053
1054   // Shift the bits to the least significant depending on endianness.
1055   unsigned ShiftAmt;
1056   if (TD.isLittleEndian()) {
1057     ShiftAmt = Offset*8;
1058   } else {
1059     ShiftAmt = (StoreSize-LoadSize-Offset)*8;
1060   }
1061
1062   if (ShiftAmt)
1063     SrcVal = BinaryOperator::CreateLShr(SrcVal,
1064                 ConstantInt::get(SrcVal->getType(), ShiftAmt), "tmp", InsertPt);
1065
1066   if (LoadSize != StoreSize)
1067     SrcVal = new TruncInst(SrcVal, IntegerType::get(Ctx, LoadSize*8),
1068                            "tmp", InsertPt);
1069
1070   return CoerceAvailableValueToLoadType(SrcVal, LoadTy, InsertPt, TD);
1071 }
1072
1073 struct AvailableValueInBlock {
1074   /// BB - The basic block in question.
1075   BasicBlock *BB;
1076   /// V - The value that is live out of the block.
1077   Value *V;
1078   /// Offset - The byte offset in V that is interesting for the load query.
1079   unsigned Offset;
1080
1081   static AvailableValueInBlock get(BasicBlock *BB, Value *V,
1082                                    unsigned Offset = 0) {
1083     AvailableValueInBlock Res;
1084     Res.BB = BB;
1085     Res.V = V;
1086     Res.Offset = Offset;
1087     return Res;
1088   }
1089 };
1090
1091 /// ConstructSSAForLoadSet - Given a set of loads specified by ValuesPerBlock,
1092 /// construct SSA form, allowing us to eliminate LI.  This returns the value
1093 /// that should be used at LI's definition site.
1094 static Value *ConstructSSAForLoadSet(LoadInst *LI,
1095                          SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock,
1096                                      const TargetData *TD,
1097                                      AliasAnalysis *AA) {
1098   SmallVector<PHINode*, 8> NewPHIs;
1099   SSAUpdater SSAUpdate(&NewPHIs);
1100   SSAUpdate.Initialize(LI);
1101
1102   const Type *LoadTy = LI->getType();
1103
1104   for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i) {
1105     BasicBlock *BB = ValuesPerBlock[i].BB;
1106     Value *AvailableVal = ValuesPerBlock[i].V;
1107     unsigned Offset = ValuesPerBlock[i].Offset;
1108
1109     if (SSAUpdate.HasValueForBlock(BB))
1110       continue;
1111
1112     if (AvailableVal->getType() != LoadTy) {
1113       assert(TD && "Need target data to handle type mismatch case");
1114       AvailableVal = GetStoreValueForLoad(AvailableVal, Offset, LoadTy,
1115                                           BB->getTerminator(), *TD);
1116
1117       if (Offset) {
1118         DEBUG(errs() << "GVN COERCED NONLOCAL VAL:\n"
1119               << *ValuesPerBlock[i].V << '\n'
1120               << *AvailableVal << '\n' << "\n\n\n");
1121       }
1122
1123
1124       DEBUG(errs() << "GVN COERCED NONLOCAL VAL:\n"
1125             << *ValuesPerBlock[i].V << '\n'
1126             << *AvailableVal << '\n' << "\n\n\n");
1127     }
1128
1129     SSAUpdate.AddAvailableValue(BB, AvailableVal);
1130   }
1131
1132   // Perform PHI construction.
1133   Value *V = SSAUpdate.GetValueInMiddleOfBlock(LI->getParent());
1134
1135   // If new PHI nodes were created, notify alias analysis.
1136   if (isa<PointerType>(V->getType()))
1137     for (unsigned i = 0, e = NewPHIs.size(); i != e; ++i)
1138       AA->copyValue(LI, NewPHIs[i]);
1139
1140   return V;
1141 }
1142
1143 /// processNonLocalLoad - Attempt to eliminate a load whose dependencies are
1144 /// non-local by performing PHI construction.
1145 bool GVN::processNonLocalLoad(LoadInst *LI,
1146                               SmallVectorImpl<Instruction*> &toErase) {
1147   // Find the non-local dependencies of the load.
1148   SmallVector<MemoryDependenceAnalysis::NonLocalDepEntry, 64> Deps;
1149   MD->getNonLocalPointerDependency(LI->getOperand(0), true, LI->getParent(),
1150                                    Deps);
1151   //DEBUG(errs() << "INVESTIGATING NONLOCAL LOAD: "
1152   //             << Deps.size() << *LI << '\n');
1153
1154   // If we had to process more than one hundred blocks to find the
1155   // dependencies, this load isn't worth worrying about.  Optimizing
1156   // it will be too expensive.
1157   if (Deps.size() > 100)
1158     return false;
1159
1160   // If we had a phi translation failure, we'll have a single entry which is a
1161   // clobber in the current block.  Reject this early.
1162   if (Deps.size() == 1 && Deps[0].second.isClobber()) {
1163     DEBUG(
1164       errs() << "GVN: non-local load ";
1165       WriteAsOperand(errs(), LI);
1166       errs() << " is clobbered by " << *Deps[0].second.getInst() << '\n';
1167     );
1168     return false;
1169   }
1170
1171   // Filter out useless results (non-locals, etc).  Keep track of the blocks
1172   // where we have a value available in repl, also keep track of whether we see
1173   // dependencies that produce an unknown value for the load (such as a call
1174   // that could potentially clobber the load).
1175   SmallVector<AvailableValueInBlock, 16> ValuesPerBlock;
1176   SmallVector<BasicBlock*, 16> UnavailableBlocks;
1177
1178   const TargetData *TD = 0;
1179
1180   for (unsigned i = 0, e = Deps.size(); i != e; ++i) {
1181     BasicBlock *DepBB = Deps[i].first;
1182     MemDepResult DepInfo = Deps[i].second;
1183
1184     if (DepInfo.isClobber()) {
1185       // If the dependence is to a store that writes to a superset of the bits
1186       // read by the load, we can extract the bits we need for the load from the
1187       // stored value.
1188       if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInfo.getInst())) {
1189         if (TD == 0)
1190           TD = getAnalysisIfAvailable<TargetData>();
1191         if (TD) {
1192           int Offset = AnalyzeLoadFromClobberingStore(LI, DepSI, *TD);
1193           if (Offset != -1) {
1194             ValuesPerBlock.push_back(AvailableValueInBlock::get(DepBB,
1195                                                            DepSI->getOperand(0),
1196                                                                 Offset));
1197             continue;
1198           }
1199         }
1200       }
1201
1202       // FIXME: Handle memset/memcpy.
1203       UnavailableBlocks.push_back(DepBB);
1204       continue;
1205     }
1206
1207     Instruction *DepInst = DepInfo.getInst();
1208
1209     // Loading the allocation -> undef.
1210     if (isa<AllocationInst>(DepInst) || isMalloc(DepInst)) {
1211       ValuesPerBlock.push_back(AvailableValueInBlock::get(DepBB,
1212                                              UndefValue::get(LI->getType())));
1213       continue;
1214     }
1215
1216     if (StoreInst *S = dyn_cast<StoreInst>(DepInst)) {
1217       // Reject loads and stores that are to the same address but are of
1218       // different types if we have to.
1219       if (S->getOperand(0)->getType() != LI->getType()) {
1220         if (TD == 0)
1221           TD = getAnalysisIfAvailable<TargetData>();
1222
1223         // If the stored value is larger or equal to the loaded value, we can
1224         // reuse it.
1225         if (TD == 0 || !CanCoerceMustAliasedValueToLoad(S->getOperand(0),
1226                                                         LI->getType(), *TD)) {
1227           UnavailableBlocks.push_back(DepBB);
1228           continue;
1229         }
1230       }
1231
1232       ValuesPerBlock.push_back(AvailableValueInBlock::get(DepBB,
1233                                                           S->getOperand(0)));
1234       continue;
1235     }
1236
1237     if (LoadInst *LD = dyn_cast<LoadInst>(DepInst)) {
1238       // If the types mismatch and we can't handle it, reject reuse of the load.
1239       if (LD->getType() != LI->getType()) {
1240         if (TD == 0)
1241           TD = getAnalysisIfAvailable<TargetData>();
1242
1243         // If the stored value is larger or equal to the loaded value, we can
1244         // reuse it.
1245         if (TD == 0 || !CanCoerceMustAliasedValueToLoad(LD, LI->getType(),*TD)){
1246           UnavailableBlocks.push_back(DepBB);
1247           continue;
1248         }
1249       }
1250       ValuesPerBlock.push_back(AvailableValueInBlock::get(DepBB, LD));
1251       continue;
1252     }
1253
1254     UnavailableBlocks.push_back(DepBB);
1255     continue;
1256   }
1257
1258   // If we have no predecessors that produce a known value for this load, exit
1259   // early.
1260   if (ValuesPerBlock.empty()) return false;
1261
1262   // If all of the instructions we depend on produce a known value for this
1263   // load, then it is fully redundant and we can use PHI insertion to compute
1264   // its value.  Insert PHIs and remove the fully redundant value now.
1265   if (UnavailableBlocks.empty()) {
1266     DEBUG(errs() << "GVN REMOVING NONLOCAL LOAD: " << *LI << '\n');
1267
1268     // Perform PHI construction.
1269     Value *V = ConstructSSAForLoadSet(LI, ValuesPerBlock, TD,
1270                                       VN.getAliasAnalysis());
1271     LI->replaceAllUsesWith(V);
1272
1273     if (isa<PHINode>(V))
1274       V->takeName(LI);
1275     if (isa<PointerType>(V->getType()))
1276       MD->invalidateCachedPointerInfo(V);
1277     toErase.push_back(LI);
1278     NumGVNLoad++;
1279     return true;
1280   }
1281
1282   if (!EnablePRE || !EnableLoadPRE)
1283     return false;
1284
1285   // Okay, we have *some* definitions of the value.  This means that the value
1286   // is available in some of our (transitive) predecessors.  Lets think about
1287   // doing PRE of this load.  This will involve inserting a new load into the
1288   // predecessor when it's not available.  We could do this in general, but
1289   // prefer to not increase code size.  As such, we only do this when we know
1290   // that we only have to insert *one* load (which means we're basically moving
1291   // the load, not inserting a new one).
1292
1293   SmallPtrSet<BasicBlock *, 4> Blockers;
1294   for (unsigned i = 0, e = UnavailableBlocks.size(); i != e; ++i)
1295     Blockers.insert(UnavailableBlocks[i]);
1296
1297   // Lets find first basic block with more than one predecessor.  Walk backwards
1298   // through predecessors if needed.
1299   BasicBlock *LoadBB = LI->getParent();
1300   BasicBlock *TmpBB = LoadBB;
1301
1302   bool isSinglePred = false;
1303   bool allSingleSucc = true;
1304   while (TmpBB->getSinglePredecessor()) {
1305     isSinglePred = true;
1306     TmpBB = TmpBB->getSinglePredecessor();
1307     if (!TmpBB) // If haven't found any, bail now.
1308       return false;
1309     if (TmpBB == LoadBB) // Infinite (unreachable) loop.
1310       return false;
1311     if (Blockers.count(TmpBB))
1312       return false;
1313     if (TmpBB->getTerminator()->getNumSuccessors() != 1)
1314       allSingleSucc = false;
1315   }
1316
1317   assert(TmpBB);
1318   LoadBB = TmpBB;
1319
1320   // If we have a repl set with LI itself in it, this means we have a loop where
1321   // at least one of the values is LI.  Since this means that we won't be able
1322   // to eliminate LI even if we insert uses in the other predecessors, we will
1323   // end up increasing code size.  Reject this by scanning for LI.
1324   for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i)
1325     if (ValuesPerBlock[i].V == LI)
1326       return false;
1327
1328   if (isSinglePred) {
1329     bool isHot = false;
1330     for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i)
1331       if (Instruction *I = dyn_cast<Instruction>(ValuesPerBlock[i].V))
1332         // "Hot" Instruction is in some loop (because it dominates its dep.
1333         // instruction).
1334         if (DT->dominates(LI, I)) {
1335           isHot = true;
1336           break;
1337         }
1338
1339     // We are interested only in "hot" instructions. We don't want to do any
1340     // mis-optimizations here.
1341     if (!isHot)
1342       return false;
1343   }
1344
1345   // Okay, we have some hope :).  Check to see if the loaded value is fully
1346   // available in all but one predecessor.
1347   // FIXME: If we could restructure the CFG, we could make a common pred with
1348   // all the preds that don't have an available LI and insert a new load into
1349   // that one block.
1350   BasicBlock *UnavailablePred = 0;
1351
1352   DenseMap<BasicBlock*, char> FullyAvailableBlocks;
1353   for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i)
1354     FullyAvailableBlocks[ValuesPerBlock[i].BB] = true;
1355   for (unsigned i = 0, e = UnavailableBlocks.size(); i != e; ++i)
1356     FullyAvailableBlocks[UnavailableBlocks[i]] = false;
1357
1358   for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB);
1359        PI != E; ++PI) {
1360     if (IsValueFullyAvailableInBlock(*PI, FullyAvailableBlocks))
1361       continue;
1362
1363     // If this load is not available in multiple predecessors, reject it.
1364     if (UnavailablePred && UnavailablePred != *PI)
1365       return false;
1366     UnavailablePred = *PI;
1367   }
1368
1369   assert(UnavailablePred != 0 &&
1370          "Fully available value should be eliminated above!");
1371
1372   // If the loaded pointer is PHI node defined in this block, do PHI translation
1373   // to get its value in the predecessor.
1374   Value *LoadPtr = LI->getOperand(0)->DoPHITranslation(LoadBB, UnavailablePred);
1375
1376   // Make sure the value is live in the predecessor.  If it was defined by a
1377   // non-PHI instruction in this block, we don't know how to recompute it above.
1378   if (Instruction *LPInst = dyn_cast<Instruction>(LoadPtr))
1379     if (!DT->dominates(LPInst->getParent(), UnavailablePred)) {
1380       DEBUG(errs() << "COULDN'T PRE LOAD BECAUSE PTR IS UNAVAILABLE IN PRED: "
1381                    << *LPInst << '\n' << *LI << "\n");
1382       return false;
1383     }
1384
1385   // We don't currently handle critical edges :(
1386   if (UnavailablePred->getTerminator()->getNumSuccessors() != 1) {
1387     DEBUG(errs() << "COULD NOT PRE LOAD BECAUSE OF CRITICAL EDGE '"
1388                  << UnavailablePred->getName() << "': " << *LI << '\n');
1389     return false;
1390   }
1391
1392   // Make sure it is valid to move this load here.  We have to watch out for:
1393   //  @1 = getelementptr (i8* p, ...
1394   //  test p and branch if == 0
1395   //  load @1
1396   // It is valid to have the getelementptr before the test, even if p can be 0,
1397   // as getelementptr only does address arithmetic.
1398   // If we are not pushing the value through any multiple-successor blocks
1399   // we do not have this case.  Otherwise, check that the load is safe to
1400   // put anywhere; this can be improved, but should be conservatively safe.
1401   if (!allSingleSucc &&
1402       !isSafeToLoadUnconditionally(LoadPtr, UnavailablePred->getTerminator()))
1403     return false;
1404
1405   // Okay, we can eliminate this load by inserting a reload in the predecessor
1406   // and using PHI construction to get the value in the other predecessors, do
1407   // it.
1408   DEBUG(errs() << "GVN REMOVING PRE LOAD: " << *LI << '\n');
1409
1410   Value *NewLoad = new LoadInst(LoadPtr, LI->getName()+".pre", false,
1411                                 LI->getAlignment(),
1412                                 UnavailablePred->getTerminator());
1413
1414   // Add the newly created load.
1415   ValuesPerBlock.push_back(AvailableValueInBlock::get(UnavailablePred,NewLoad));
1416
1417   // Perform PHI construction.
1418   Value *V = ConstructSSAForLoadSet(LI, ValuesPerBlock, TD,
1419                                     VN.getAliasAnalysis());
1420   LI->replaceAllUsesWith(V);
1421   if (isa<PHINode>(V))
1422     V->takeName(LI);
1423   if (isa<PointerType>(V->getType()))
1424     MD->invalidateCachedPointerInfo(V);
1425   toErase.push_back(LI);
1426   NumPRELoad++;
1427   return true;
1428 }
1429
1430 /// processLoad - Attempt to eliminate a load, first by eliminating it
1431 /// locally, and then attempting non-local elimination if that fails.
1432 bool GVN::processLoad(LoadInst *L, SmallVectorImpl<Instruction*> &toErase) {
1433   if (L->isVolatile())
1434     return false;
1435
1436   // ... to a pointer that has been loaded from before...
1437   MemDepResult Dep = MD->getDependency(L);
1438
1439   // If the value isn't available, don't do anything!
1440   if (Dep.isClobber()) {
1441     // FIXME: We should handle memset/memcpy/memmove as dependent instructions
1442     // to forward the value if available.
1443     //if (isa<MemIntrinsic>(Dep.getInst()))
1444     //errs() << "LOAD DEPENDS ON MEM: " << *L << "\n" << *Dep.getInst()<<"\n\n";
1445
1446     // Check to see if we have something like this:
1447     //   store i32 123, i32* %P
1448     //   %A = bitcast i32* %P to i8*
1449     //   %B = gep i8* %A, i32 1
1450     //   %C = load i8* %B
1451     //
1452     // We could do that by recognizing if the clobber instructions are obviously
1453     // a common base + constant offset, and if the previous store (or memset)
1454     // completely covers this load.  This sort of thing can happen in bitfield
1455     // access code.
1456     if (StoreInst *DepSI = dyn_cast<StoreInst>(Dep.getInst()))
1457       if (const TargetData *TD = getAnalysisIfAvailable<TargetData>()) {
1458         int Offset = AnalyzeLoadFromClobberingStore(L, DepSI, *TD);
1459         if (Offset != -1) {
1460           Value *AvailVal = GetStoreValueForLoad(DepSI->getOperand(0), Offset,
1461                                                  L->getType(), L, *TD);
1462           DEBUG(errs() << "GVN COERCED STORE BITS:\n" << *DepSI << '\n'
1463                        << *AvailVal << '\n' << *L << "\n\n\n");
1464
1465           // Replace the load!
1466           L->replaceAllUsesWith(AvailVal);
1467           if (isa<PointerType>(AvailVal->getType()))
1468             MD->invalidateCachedPointerInfo(AvailVal);
1469           toErase.push_back(L);
1470           NumGVNLoad++;
1471           return true;
1472         }
1473       }
1474
1475     DEBUG(
1476       // fast print dep, using operator<< on instruction would be too slow
1477       errs() << "GVN: load ";
1478       WriteAsOperand(errs(), L);
1479       Instruction *I = Dep.getInst();
1480       errs() << " is clobbered by " << *I << '\n';
1481     );
1482     return false;
1483   }
1484
1485   // If it is defined in another block, try harder.
1486   if (Dep.isNonLocal())
1487     return processNonLocalLoad(L, toErase);
1488
1489   Instruction *DepInst = Dep.getInst();
1490   if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) {
1491     Value *StoredVal = DepSI->getOperand(0);
1492
1493     // The store and load are to a must-aliased pointer, but they may not
1494     // actually have the same type.  See if we know how to reuse the stored
1495     // value (depending on its type).
1496     const TargetData *TD = 0;
1497     if (StoredVal->getType() != L->getType() &&
1498         (TD = getAnalysisIfAvailable<TargetData>())) {
1499       StoredVal = CoerceAvailableValueToLoadType(StoredVal, L->getType(),
1500                                                  L, *TD);
1501       if (StoredVal == 0)
1502         return false;
1503
1504       DEBUG(errs() << "GVN COERCED STORE:\n" << *DepSI << '\n' << *StoredVal
1505                    << '\n' << *L << "\n\n\n");
1506     }
1507
1508     // Remove it!
1509     L->replaceAllUsesWith(StoredVal);
1510     if (isa<PointerType>(StoredVal->getType()))
1511       MD->invalidateCachedPointerInfo(StoredVal);
1512     toErase.push_back(L);
1513     NumGVNLoad++;
1514     return true;
1515   }
1516
1517   if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInst)) {
1518     Value *AvailableVal = DepLI;
1519
1520     // The loads are of a must-aliased pointer, but they may not actually have
1521     // the same type.  See if we know how to reuse the previously loaded value
1522     // (depending on its type).
1523     const TargetData *TD = 0;
1524     if (DepLI->getType() != L->getType() &&
1525         (TD = getAnalysisIfAvailable<TargetData>())) {
1526       AvailableVal = CoerceAvailableValueToLoadType(DepLI, L->getType(), L,*TD);
1527       if (AvailableVal == 0)
1528         return false;
1529
1530       DEBUG(errs() << "GVN COERCED LOAD:\n" << *DepLI << "\n" << *AvailableVal
1531                    << "\n" << *L << "\n\n\n");
1532     }
1533
1534     // Remove it!
1535     L->replaceAllUsesWith(AvailableVal);
1536     if (isa<PointerType>(DepLI->getType()))
1537       MD->invalidateCachedPointerInfo(DepLI);
1538     toErase.push_back(L);
1539     NumGVNLoad++;
1540     return true;
1541   }
1542
1543   // If this load really doesn't depend on anything, then we must be loading an
1544   // undef value.  This can happen when loading for a fresh allocation with no
1545   // intervening stores, for example.
1546   if (isa<AllocationInst>(DepInst) || isMalloc(DepInst)) {
1547     L->replaceAllUsesWith(UndefValue::get(L->getType()));
1548     toErase.push_back(L);
1549     NumGVNLoad++;
1550     return true;
1551   }
1552
1553   return false;
1554 }
1555
1556 Value *GVN::lookupNumber(BasicBlock *BB, uint32_t num) {
1557   DenseMap<BasicBlock*, ValueNumberScope*>::iterator I = localAvail.find(BB);
1558   if (I == localAvail.end())
1559     return 0;
1560
1561   ValueNumberScope *Locals = I->second;
1562   while (Locals) {
1563     DenseMap<uint32_t, Value*>::iterator I = Locals->table.find(num);
1564     if (I != Locals->table.end())
1565       return I->second;
1566     Locals = Locals->parent;
1567   }
1568
1569   return 0;
1570 }
1571
1572
1573 /// processInstruction - When calculating availability, handle an instruction
1574 /// by inserting it into the appropriate sets
1575 bool GVN::processInstruction(Instruction *I,
1576                              SmallVectorImpl<Instruction*> &toErase) {
1577   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
1578     bool Changed = processLoad(LI, toErase);
1579
1580     if (!Changed) {
1581       unsigned Num = VN.lookup_or_add(LI);
1582       localAvail[I->getParent()]->table.insert(std::make_pair(Num, LI));
1583     }
1584
1585     return Changed;
1586   }
1587
1588   uint32_t NextNum = VN.getNextUnusedValueNumber();
1589   unsigned Num = VN.lookup_or_add(I);
1590
1591   if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
1592     localAvail[I->getParent()]->table.insert(std::make_pair(Num, I));
1593
1594     if (!BI->isConditional() || isa<Constant>(BI->getCondition()))
1595       return false;
1596
1597     Value *BranchCond = BI->getCondition();
1598     uint32_t CondVN = VN.lookup_or_add(BranchCond);
1599
1600     BasicBlock *TrueSucc = BI->getSuccessor(0);
1601     BasicBlock *FalseSucc = BI->getSuccessor(1);
1602
1603     if (TrueSucc->getSinglePredecessor())
1604       localAvail[TrueSucc]->table[CondVN] =
1605         ConstantInt::getTrue(TrueSucc->getContext());
1606     if (FalseSucc->getSinglePredecessor())
1607       localAvail[FalseSucc]->table[CondVN] =
1608         ConstantInt::getFalse(TrueSucc->getContext());
1609
1610     return false;
1611
1612   // Allocations are always uniquely numbered, so we can save time and memory
1613   // by fast failing them.
1614   } else if (isa<AllocationInst>(I) || isa<TerminatorInst>(I)) {
1615     localAvail[I->getParent()]->table.insert(std::make_pair(Num, I));
1616     return false;
1617   }
1618
1619   // Collapse PHI nodes
1620   if (PHINode* p = dyn_cast<PHINode>(I)) {
1621     Value *constVal = CollapsePhi(p);
1622
1623     if (constVal) {
1624       p->replaceAllUsesWith(constVal);
1625       if (isa<PointerType>(constVal->getType()))
1626         MD->invalidateCachedPointerInfo(constVal);
1627       VN.erase(p);
1628
1629       toErase.push_back(p);
1630     } else {
1631       localAvail[I->getParent()]->table.insert(std::make_pair(Num, I));
1632     }
1633
1634   // If the number we were assigned was a brand new VN, then we don't
1635   // need to do a lookup to see if the number already exists
1636   // somewhere in the domtree: it can't!
1637   } else if (Num == NextNum) {
1638     localAvail[I->getParent()]->table.insert(std::make_pair(Num, I));
1639
1640   // Perform fast-path value-number based elimination of values inherited from
1641   // dominators.
1642   } else if (Value *repl = lookupNumber(I->getParent(), Num)) {
1643     // Remove it!
1644     VN.erase(I);
1645     I->replaceAllUsesWith(repl);
1646     if (isa<PointerType>(repl->getType()))
1647       MD->invalidateCachedPointerInfo(repl);
1648     toErase.push_back(I);
1649     return true;
1650
1651   } else {
1652     localAvail[I->getParent()]->table.insert(std::make_pair(Num, I));
1653   }
1654
1655   return false;
1656 }
1657
1658 /// runOnFunction - This is the main transformation entry point for a function.
1659 bool GVN::runOnFunction(Function& F) {
1660   MD = &getAnalysis<MemoryDependenceAnalysis>();
1661   DT = &getAnalysis<DominatorTree>();
1662   VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>());
1663   VN.setMemDep(MD);
1664   VN.setDomTree(DT);
1665
1666   bool Changed = false;
1667   bool ShouldContinue = true;
1668
1669   // Merge unconditional branches, allowing PRE to catch more
1670   // optimization opportunities.
1671   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) {
1672     BasicBlock *BB = FI;
1673     ++FI;
1674     bool removedBlock = MergeBlockIntoPredecessor(BB, this);
1675     if (removedBlock) NumGVNBlocks++;
1676
1677     Changed |= removedBlock;
1678   }
1679
1680   unsigned Iteration = 0;
1681
1682   while (ShouldContinue) {
1683     DEBUG(errs() << "GVN iteration: " << Iteration << "\n");
1684     ShouldContinue = iterateOnFunction(F);
1685     Changed |= ShouldContinue;
1686     ++Iteration;
1687   }
1688
1689   if (EnablePRE) {
1690     bool PREChanged = true;
1691     while (PREChanged) {
1692       PREChanged = performPRE(F);
1693       Changed |= PREChanged;
1694     }
1695   }
1696   // FIXME: Should perform GVN again after PRE does something.  PRE can move
1697   // computations into blocks where they become fully redundant.  Note that
1698   // we can't do this until PRE's critical edge splitting updates memdep.
1699   // Actually, when this happens, we should just fully integrate PRE into GVN.
1700
1701   cleanupGlobalSets();
1702
1703   return Changed;
1704 }
1705
1706
1707 bool GVN::processBlock(BasicBlock *BB) {
1708   // FIXME: Kill off toErase by doing erasing eagerly in a helper function (and
1709   // incrementing BI before processing an instruction).
1710   SmallVector<Instruction*, 8> toErase;
1711   bool ChangedFunction = false;
1712
1713   for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
1714        BI != BE;) {
1715     ChangedFunction |= processInstruction(BI, toErase);
1716     if (toErase.empty()) {
1717       ++BI;
1718       continue;
1719     }
1720
1721     // If we need some instructions deleted, do it now.
1722     NumGVNInstr += toErase.size();
1723
1724     // Avoid iterator invalidation.
1725     bool AtStart = BI == BB->begin();
1726     if (!AtStart)
1727       --BI;
1728
1729     for (SmallVector<Instruction*, 4>::iterator I = toErase.begin(),
1730          E = toErase.end(); I != E; ++I) {
1731       DEBUG(errs() << "GVN removed: " << **I << '\n');
1732       MD->removeInstruction(*I);
1733       (*I)->eraseFromParent();
1734       DEBUG(verifyRemoved(*I));
1735     }
1736     toErase.clear();
1737
1738     if (AtStart)
1739       BI = BB->begin();
1740     else
1741       ++BI;
1742   }
1743
1744   return ChangedFunction;
1745 }
1746
1747 /// performPRE - Perform a purely local form of PRE that looks for diamond
1748 /// control flow patterns and attempts to perform simple PRE at the join point.
1749 bool GVN::performPRE(Function& F) {
1750   bool Changed = false;
1751   SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit;
1752   DenseMap<BasicBlock*, Value*> predMap;
1753   for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()),
1754        DE = df_end(&F.getEntryBlock()); DI != DE; ++DI) {
1755     BasicBlock *CurrentBlock = *DI;
1756
1757     // Nothing to PRE in the entry block.
1758     if (CurrentBlock == &F.getEntryBlock()) continue;
1759
1760     for (BasicBlock::iterator BI = CurrentBlock->begin(),
1761          BE = CurrentBlock->end(); BI != BE; ) {
1762       Instruction *CurInst = BI++;
1763
1764       if (isa<AllocationInst>(CurInst) ||
1765           isa<TerminatorInst>(CurInst) || isa<PHINode>(CurInst) ||
1766           CurInst->getType()->isVoidTy() ||
1767           CurInst->mayReadFromMemory() || CurInst->mayHaveSideEffects() ||
1768           isa<DbgInfoIntrinsic>(CurInst))
1769         continue;
1770
1771       uint32_t ValNo = VN.lookup(CurInst);
1772
1773       // Look for the predecessors for PRE opportunities.  We're
1774       // only trying to solve the basic diamond case, where
1775       // a value is computed in the successor and one predecessor,
1776       // but not the other.  We also explicitly disallow cases
1777       // where the successor is its own predecessor, because they're
1778       // more complicated to get right.
1779       unsigned NumWith = 0;
1780       unsigned NumWithout = 0;
1781       BasicBlock *PREPred = 0;
1782       predMap.clear();
1783
1784       for (pred_iterator PI = pred_begin(CurrentBlock),
1785            PE = pred_end(CurrentBlock); PI != PE; ++PI) {
1786         // We're not interested in PRE where the block is its
1787         // own predecessor, on in blocks with predecessors
1788         // that are not reachable.
1789         if (*PI == CurrentBlock) {
1790           NumWithout = 2;
1791           break;
1792         } else if (!localAvail.count(*PI))  {
1793           NumWithout = 2;
1794           break;
1795         }
1796
1797         DenseMap<uint32_t, Value*>::iterator predV =
1798                                             localAvail[*PI]->table.find(ValNo);
1799         if (predV == localAvail[*PI]->table.end()) {
1800           PREPred = *PI;
1801           NumWithout++;
1802         } else if (predV->second == CurInst) {
1803           NumWithout = 2;
1804         } else {
1805           predMap[*PI] = predV->second;
1806           NumWith++;
1807         }
1808       }
1809
1810       // Don't do PRE when it might increase code size, i.e. when
1811       // we would need to insert instructions in more than one pred.
1812       if (NumWithout != 1 || NumWith == 0)
1813         continue;
1814
1815       // We can't do PRE safely on a critical edge, so instead we schedule
1816       // the edge to be split and perform the PRE the next time we iterate
1817       // on the function.
1818       unsigned SuccNum = 0;
1819       for (unsigned i = 0, e = PREPred->getTerminator()->getNumSuccessors();
1820            i != e; ++i)
1821         if (PREPred->getTerminator()->getSuccessor(i) == CurrentBlock) {
1822           SuccNum = i;
1823           break;
1824         }
1825
1826       if (isCriticalEdge(PREPred->getTerminator(), SuccNum)) {
1827         toSplit.push_back(std::make_pair(PREPred->getTerminator(), SuccNum));
1828         continue;
1829       }
1830
1831       // Instantiate the expression the in predecessor that lacked it.
1832       // Because we are going top-down through the block, all value numbers
1833       // will be available in the predecessor by the time we need them.  Any
1834       // that weren't original present will have been instantiated earlier
1835       // in this loop.
1836       Instruction *PREInstr = CurInst->clone();
1837       bool success = true;
1838       for (unsigned i = 0, e = CurInst->getNumOperands(); i != e; ++i) {
1839         Value *Op = PREInstr->getOperand(i);
1840         if (isa<Argument>(Op) || isa<Constant>(Op) || isa<GlobalValue>(Op))
1841           continue;
1842
1843         if (Value *V = lookupNumber(PREPred, VN.lookup(Op))) {
1844           PREInstr->setOperand(i, V);
1845         } else {
1846           success = false;
1847           break;
1848         }
1849       }
1850
1851       // Fail out if we encounter an operand that is not available in
1852       // the PRE predecessor.  This is typically because of loads which
1853       // are not value numbered precisely.
1854       if (!success) {
1855         delete PREInstr;
1856         DEBUG(verifyRemoved(PREInstr));
1857         continue;
1858       }
1859
1860       PREInstr->insertBefore(PREPred->getTerminator());
1861       PREInstr->setName(CurInst->getName() + ".pre");
1862       predMap[PREPred] = PREInstr;
1863       VN.add(PREInstr, ValNo);
1864       NumGVNPRE++;
1865
1866       // Update the availability map to include the new instruction.
1867       localAvail[PREPred]->table.insert(std::make_pair(ValNo, PREInstr));
1868
1869       // Create a PHI to make the value available in this block.
1870       PHINode* Phi = PHINode::Create(CurInst->getType(),
1871                                      CurInst->getName() + ".pre-phi",
1872                                      CurrentBlock->begin());
1873       for (pred_iterator PI = pred_begin(CurrentBlock),
1874            PE = pred_end(CurrentBlock); PI != PE; ++PI)
1875         Phi->addIncoming(predMap[*PI], *PI);
1876
1877       VN.add(Phi, ValNo);
1878       localAvail[CurrentBlock]->table[ValNo] = Phi;
1879
1880       CurInst->replaceAllUsesWith(Phi);
1881       if (isa<PointerType>(Phi->getType()))
1882         MD->invalidateCachedPointerInfo(Phi);
1883       VN.erase(CurInst);
1884
1885       DEBUG(errs() << "GVN PRE removed: " << *CurInst << '\n');
1886       MD->removeInstruction(CurInst);
1887       CurInst->eraseFromParent();
1888       DEBUG(verifyRemoved(CurInst));
1889       Changed = true;
1890     }
1891   }
1892
1893   for (SmallVector<std::pair<TerminatorInst*, unsigned>, 4>::iterator
1894        I = toSplit.begin(), E = toSplit.end(); I != E; ++I)
1895     SplitCriticalEdge(I->first, I->second, this);
1896
1897   return Changed || toSplit.size();
1898 }
1899
1900 /// iterateOnFunction - Executes one iteration of GVN
1901 bool GVN::iterateOnFunction(Function &F) {
1902   cleanupGlobalSets();
1903
1904   for (df_iterator<DomTreeNode*> DI = df_begin(DT->getRootNode()),
1905        DE = df_end(DT->getRootNode()); DI != DE; ++DI) {
1906     if (DI->getIDom())
1907       localAvail[DI->getBlock()] =
1908                    new ValueNumberScope(localAvail[DI->getIDom()->getBlock()]);
1909     else
1910       localAvail[DI->getBlock()] = new ValueNumberScope(0);
1911   }
1912
1913   // Top-down walk of the dominator tree
1914   bool Changed = false;
1915 #if 0
1916   // Needed for value numbering with phi construction to work.
1917   ReversePostOrderTraversal<Function*> RPOT(&F);
1918   for (ReversePostOrderTraversal<Function*>::rpo_iterator RI = RPOT.begin(),
1919        RE = RPOT.end(); RI != RE; ++RI)
1920     Changed |= processBlock(*RI);
1921 #else
1922   for (df_iterator<DomTreeNode*> DI = df_begin(DT->getRootNode()),
1923        DE = df_end(DT->getRootNode()); DI != DE; ++DI)
1924     Changed |= processBlock(DI->getBlock());
1925 #endif
1926
1927   return Changed;
1928 }
1929
1930 void GVN::cleanupGlobalSets() {
1931   VN.clear();
1932
1933   for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator
1934        I = localAvail.begin(), E = localAvail.end(); I != E; ++I)
1935     delete I->second;
1936   localAvail.clear();
1937 }
1938
1939 /// verifyRemoved - Verify that the specified instruction does not occur in our
1940 /// internal data structures.
1941 void GVN::verifyRemoved(const Instruction *Inst) const {
1942   VN.verifyRemoved(Inst);
1943
1944   // Walk through the value number scope to make sure the instruction isn't
1945   // ferreted away in it.
1946   for (DenseMap<BasicBlock*, ValueNumberScope*>::iterator
1947          I = localAvail.begin(), E = localAvail.end(); I != E; ++I) {
1948     const ValueNumberScope *VNS = I->second;
1949
1950     while (VNS) {
1951       for (DenseMap<uint32_t, Value*>::iterator
1952              II = VNS->table.begin(), IE = VNS->table.end(); II != IE; ++II) {
1953         assert(II->second != Inst && "Inst still in value numbering scope!");
1954       }
1955
1956       VNS = VNS->parent;
1957     }
1958   }
1959 }