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 #include "llvm/Transforms/Scalar.h"
  19 #include "llvm/ADT/DenseMap.h"
  20 #include "llvm/ADT/DepthFirstIterator.h"
  21 #include "llvm/ADT/Hashing.h"
  22 #include "llvm/ADT/MapVector.h"
  23 #include "llvm/ADT/PostOrderIterator.h"
  24 #include "llvm/ADT/SetVector.h"
  25 #include "llvm/ADT/SmallPtrSet.h"
  26 #include "llvm/ADT/Statistic.h"
  27 #include "llvm/Analysis/AliasAnalysis.h"
  28 #include "llvm/Analysis/AssumptionCache.h"
  29 #include "llvm/Analysis/CFG.h"
  30 #include "llvm/Analysis/ConstantFolding.h"
  31 #include "llvm/Analysis/InstructionSimplify.h"
  32 #include "llvm/Analysis/Loads.h"
  33 #include "llvm/Analysis/MemoryBuiltins.h"
  34 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
  35 #include "llvm/Analysis/PHITransAddr.h"
  36 #include "llvm/Analysis/ValueTracking.h"
  37 #include "llvm/IR/DataLayout.h"
  38 #include "llvm/IR/Dominators.h"
  39 #include "llvm/IR/GlobalVariable.h"
  40 #include "llvm/IR/IRBuilder.h"
  41 #include "llvm/IR/IntrinsicInst.h"
  42 #include "llvm/IR/LLVMContext.h"
  43 #include "llvm/IR/Metadata.h"
  44 #include "llvm/IR/PatternMatch.h"
  45 #include "llvm/Support/Allocator.h"
  46 #include "llvm/Support/CommandLine.h"
  47 #include "llvm/Support/Debug.h"
  48 #include "llvm/Analysis/TargetLibraryInfo.h"
  49 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  50 #include "llvm/Transforms/Utils/Local.h"
  51 #include "llvm/Transforms/Utils/SSAUpdater.h"
  52 #include <vector>
  53 using namespace llvm;
  54 using namespace PatternMatch;
  55
  56 #define DEBUG_TYPE "gvn"
  57
  58 STATISTIC(NumGVNInstr,  "Number of instructions deleted");
  59 STATISTIC(NumGVNLoad,   "Number of loads deleted");
  60 STATISTIC(NumGVNPRE,    "Number of instructions PRE'd");
  61 STATISTIC(NumGVNBlocks, "Number of blocks merged");
  62 STATISTIC(NumGVNSimpl,  "Number of instructions simplified");
  63 STATISTIC(NumGVNEqProp, "Number of equalities propagated");
  64 STATISTIC(NumPRELoad,   "Number of loads PRE'd");
  65
  66 static cl::opt<bool> EnablePRE("enable-pre",
  67                                cl::init(true), cl::Hidden);
  68 static cl::opt<bool> EnableLoadPRE("enable-load-pre", cl::init(true));
  69
  70 // Maximum allowed recursion depth.
  71 static cl::opt<uint32_t>
  72 MaxRecurseDepth("max-recurse-depth", cl::Hidden, cl::init(1000), cl::ZeroOrMore,
  73                 cl::desc("Max recurse depth (default = 1000)"));
  74
  75 //===----------------------------------------------------------------------===//
  76 //                         ValueTable Class
  77 //===----------------------------------------------------------------------===//
  78
  79 /// This class holds the mapping between values and value numbers.  It is used
  80 /// as an efficient mechanism to determine the expression-wise equivalence of
  81 /// two values.
  82 namespace {
  83   struct Expression {
  84     uint32_t opcode;
  85     Type *type;
  86     SmallVector<uint32_t, 4> varargs;
  87
  88     Expression(uint32_t o = ~2U) : opcode(o) { }
  89
  90     bool operator==(const Expression &other) const {
  91       if (opcode != other.opcode)
  92         return false;
  93       if (opcode == ~0U || opcode == ~1U)
  94         return true;
  95       if (type != other.type)
  96         return false;
  97       if (varargs != other.varargs)
  98         return false;
  99       return true;
 100     }
 101
 102     friend hash_code hash_value(const Expression &Value) {
 103       return hash_combine(Value.opcode, Value.type,
 104                           hash_combine_range(Value.varargs.begin(),
 105                                              Value.varargs.end()));
 106     }
 107   };
 108
 109   class ValueTable {
 110     DenseMap<Value*, uint32_t> valueNumbering;
 111     DenseMap<Expression, uint32_t> expressionNumbering;
 112     AliasAnalysis *AA;
 113     MemoryDependenceAnalysis *MD;
 114     DominatorTree *DT;
 115
 116     uint32_t nextValueNumber;
 117
 118     Expression create_expression(Instruction* I);
 119     Expression create_cmp_expression(unsigned Opcode,
 120                                      CmpInst::Predicate Predicate,
 121                                      Value *LHS, Value *RHS);
 122     Expression create_extractvalue_expression(ExtractValueInst* EI);
 123     uint32_t lookup_or_add_call(CallInst* C);
 124   public:
 125     ValueTable() : nextValueNumber(1) { }
 126     uint32_t lookup_or_add(Value *V);
 127     uint32_t lookup(Value *V) const;
 128     uint32_t lookup_or_add_cmp(unsigned Opcode, CmpInst::Predicate Pred,
 129                                Value *LHS, Value *RHS);
 130     void add(Value *V, uint32_t num);
 131     void clear();
 132     void erase(Value *v);
 133     void setAliasAnalysis(AliasAnalysis* A) { AA = A; }
 134     AliasAnalysis *getAliasAnalysis() const { return AA; }
 135     void setMemDep(MemoryDependenceAnalysis* M) { MD = M; }
 136     void setDomTree(DominatorTree* D) { DT = D; }
 137     uint32_t getNextUnusedValueNumber() { return nextValueNumber; }
 138     void verifyRemoved(const Value *) const;
 139   };
 140 }
 141
 142 namespace llvm {
 143 template <> struct DenseMapInfo<Expression> {
 144   static inline Expression getEmptyKey() {
 145     return ~0U;
 146   }
 147
 148   static inline Expression getTombstoneKey() {
 149     return ~1U;
 150   }
 151
 152   static unsigned getHashValue(const Expression e) {
 153     using llvm::hash_value;
 154     return static_cast<unsigned>(hash_value(e));
 155   }
 156   static bool isEqual(const Expression &LHS, const Expression &RHS) {
 157     return LHS == RHS;
 158   }
 159 };
 160
 161 }
 162
 163 //===----------------------------------------------------------------------===//
 164 //                     ValueTable Internal Functions
 165 //===----------------------------------------------------------------------===//
 166
 167 Expression ValueTable::create_expression(Instruction *I) {
 168   Expression e;
 169   e.type = I->getType();
 170   e.opcode = I->getOpcode();
 171   for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end();
 172        OI != OE; ++OI)
 173     e.varargs.push_back(lookup_or_add(*OI));
 174   if (I->isCommutative()) {
 175     // Ensure that commutative instructions that only differ by a permutation
 176     // of their operands get the same value number by sorting the operand value
 177     // numbers.  Since all commutative instructions have two operands it is more
 178     // efficient to sort by hand rather than using, say, std::sort.
 179     assert(I->getNumOperands() == 2 && "Unsupported commutative instruction!");
 180     if (e.varargs[0] > e.varargs[1])
 181       std::swap(e.varargs[0], e.varargs[1]);
 182   }
 183
 184   if (CmpInst *C = dyn_cast<CmpInst>(I)) {
 185     // Sort the operand value numbers so x<y and y>x get the same value number.
 186     CmpInst::Predicate Predicate = C->getPredicate();
 187     if (e.varargs[0] > e.varargs[1]) {
 188       std::swap(e.varargs[0], e.varargs[1]);
 189       Predicate = CmpInst::getSwappedPredicate(Predicate);
 190     }
 191     e.opcode = (C->getOpcode() << 8) | Predicate;
 192   } else if (InsertValueInst *E = dyn_cast<InsertValueInst>(I)) {
 193     for (InsertValueInst::idx_iterator II = E->idx_begin(), IE = E->idx_end();
 194          II != IE; ++II)
 195       e.varargs.push_back(*II);
 196   }
 197
 198   return e;
 199 }
 200
 201 Expression ValueTable::create_cmp_expression(unsigned Opcode,
 202                                              CmpInst::Predicate Predicate,
 203                                              Value *LHS, Value *RHS) {
 204   assert((Opcode == Instruction::ICmp || Opcode == Instruction::FCmp) &&
 205          "Not a comparison!");
 206   Expression e;
 207   e.type = CmpInst::makeCmpResultType(LHS->getType());
 208   e.varargs.push_back(lookup_or_add(LHS));
 209   e.varargs.push_back(lookup_or_add(RHS));
 210
 211   // Sort the operand value numbers so x<y and y>x get the same value number.
 212   if (e.varargs[0] > e.varargs[1]) {
 213     std::swap(e.varargs[0], e.varargs[1]);
 214     Predicate = CmpInst::getSwappedPredicate(Predicate);
 215   }
 216   e.opcode = (Opcode << 8) | Predicate;
 217   return e;
 218 }
 219
 220 Expression ValueTable::create_extractvalue_expression(ExtractValueInst *EI) {
 221   assert(EI && "Not an ExtractValueInst?");
 222   Expression e;
 223   e.type = EI->getType();
 224   e.opcode = 0;
 225
 226   IntrinsicInst *I = dyn_cast<IntrinsicInst>(EI->getAggregateOperand());
 227   if (I != nullptr && EI->getNumIndices() == 1 && *EI->idx_begin() == 0 ) {
 228     // EI might be an extract from one of our recognised intrinsics. If it
 229     // is we'll synthesize a semantically equivalent expression instead on
 230     // an extract value expression.
 231     switch (I->getIntrinsicID()) {
 232       case Intrinsic::sadd_with_overflow:
 233       case Intrinsic::uadd_with_overflow:
 234         e.opcode = Instruction::Add;
 235         break;
 236       case Intrinsic::ssub_with_overflow:
 237       case Intrinsic::usub_with_overflow:
 238         e.opcode = Instruction::Sub;
 239         break;
 240       case Intrinsic::smul_with_overflow:
 241       case Intrinsic::umul_with_overflow:
 242         e.opcode = Instruction::Mul;
 243         break;
 244       default:
 245         break;
 246     }
 247
 248     if (e.opcode != 0) {
 249       // Intrinsic recognized. Grab its args to finish building the expression.
 250       assert(I->getNumArgOperands() == 2 &&
 251              "Expect two args for recognised intrinsics.");
 252       e.varargs.push_back(lookup_or_add(I->getArgOperand(0)));
 253       e.varargs.push_back(lookup_or_add(I->getArgOperand(1)));
 254       return e;
 255     }
 256   }
 257
 258   // Not a recognised intrinsic. Fall back to producing an extract value
 259   // expression.
 260   e.opcode = EI->getOpcode();
 261   for (Instruction::op_iterator OI = EI->op_begin(), OE = EI->op_end();
 262        OI != OE; ++OI)
 263     e.varargs.push_back(lookup_or_add(*OI));
 264
 265   for (ExtractValueInst::idx_iterator II = EI->idx_begin(), IE = EI->idx_end();
 266          II != IE; ++II)
 267     e.varargs.push_back(*II);
 268
 269   return e;
 270 }
 271
 272 //===----------------------------------------------------------------------===//
 273 //                     ValueTable External Functions
 274 //===----------------------------------------------------------------------===//
 275
 276 /// add - Insert a value into the table with a specified value number.
 277 void ValueTable::add(Value *V, uint32_t num) {
 278   valueNumbering.insert(std::make_pair(V, num));
 279 }
 280
 281 uint32_t ValueTable::lookup_or_add_call(CallInst *C) {
 282   if (AA->doesNotAccessMemory(C)) {
 283     Expression exp = create_expression(C);
 284     uint32_t &e = expressionNumbering[exp];
 285     if (!e) e = nextValueNumber++;
 286     valueNumbering[C] = e;
 287     return e;
 288   } else if (AA->onlyReadsMemory(C)) {
 289     Expression exp = create_expression(C);
 290     uint32_t &e = expressionNumbering[exp];
 291     if (!e) {
 292       e = nextValueNumber++;
 293       valueNumbering[C] = e;
 294       return e;
 295     }
 296     if (!MD) {
 297       e = nextValueNumber++;
 298       valueNumbering[C] = e;
 299       return e;
 300     }
 301
 302     MemDepResult local_dep = MD->getDependency(C);
 303
 304     if (!local_dep.isDef() && !local_dep.isNonLocal()) {
 305       valueNumbering[C] =  nextValueNumber;
 306       return nextValueNumber++;
 307     }
 308
 309     if (local_dep.isDef()) {
 310       CallInst* local_cdep = cast<CallInst>(local_dep.getInst());
 311
 312       if (local_cdep->getNumArgOperands() != C->getNumArgOperands()) {
 313         valueNumbering[C] = nextValueNumber;
 314         return nextValueNumber++;
 315       }
 316
 317       for (unsigned i = 0, e = C->getNumArgOperands(); i < e; ++i) {
 318         uint32_t c_vn = lookup_or_add(C->getArgOperand(i));
 319         uint32_t cd_vn = lookup_or_add(local_cdep->getArgOperand(i));
 320         if (c_vn != cd_vn) {
 321           valueNumbering[C] = nextValueNumber;
 322           return nextValueNumber++;
 323         }
 324       }
 325
 326       uint32_t v = lookup_or_add(local_cdep);
 327       valueNumbering[C] = v;
 328       return v;
 329     }
 330
 331     // Non-local case.
 332     const MemoryDependenceAnalysis::NonLocalDepInfo &deps =
 333       MD->getNonLocalCallDependency(CallSite(C));
 334     // FIXME: Move the checking logic to MemDep!
 335     CallInst* cdep = nullptr;
 336
 337     // Check to see if we have a single dominating call instruction that is
 338     // identical to C.
 339     for (unsigned i = 0, e = deps.size(); i != e; ++i) {
 340       const NonLocalDepEntry *I = &deps[i];
 341       if (I->getResult().isNonLocal())
 342         continue;
 343
 344       // We don't handle non-definitions.  If we already have a call, reject
 345       // instruction dependencies.
 346       if (!I->getResult().isDef() || cdep != nullptr) {
 347         cdep = nullptr;
 348         break;
 349       }
 350
 351       CallInst *NonLocalDepCall = dyn_cast<CallInst>(I->getResult().getInst());
 352       // FIXME: All duplicated with non-local case.
 353       if (NonLocalDepCall && DT->properlyDominates(I->getBB(), C->getParent())){
 354         cdep = NonLocalDepCall;
 355         continue;
 356       }
 357
 358       cdep = nullptr;
 359       break;
 360     }
 361
 362     if (!cdep) {
 363       valueNumbering[C] = nextValueNumber;
 364       return nextValueNumber++;
 365     }
 366
 367     if (cdep->getNumArgOperands() != C->getNumArgOperands()) {
 368       valueNumbering[C] = nextValueNumber;
 369       return nextValueNumber++;
 370     }
 371     for (unsigned i = 0, e = C->getNumArgOperands(); i < e; ++i) {
 372       uint32_t c_vn = lookup_or_add(C->getArgOperand(i));
 373       uint32_t cd_vn = lookup_or_add(cdep->getArgOperand(i));
 374       if (c_vn != cd_vn) {
 375         valueNumbering[C] = nextValueNumber;
 376         return nextValueNumber++;
 377       }
 378     }
 379
 380     uint32_t v = lookup_or_add(cdep);
 381     valueNumbering[C] = v;
 382     return v;
 383
 384   } else {
 385     valueNumbering[C] = nextValueNumber;
 386     return nextValueNumber++;
 387   }
 388 }
 389
 390 /// lookup_or_add - Returns the value number for the specified value, assigning
 391 /// it a new number if it did not have one before.
 392 uint32_t ValueTable::lookup_or_add(Value *V) {
 393   DenseMap<Value*, uint32_t>::iterator VI = valueNumbering.find(V);
 394   if (VI != valueNumbering.end())
 395     return VI->second;
 396
 397   if (!isa<Instruction>(V)) {
 398     valueNumbering[V] = nextValueNumber;
 399     return nextValueNumber++;
 400   }
 401
 402   Instruction* I = cast<Instruction>(V);
 403   Expression exp;
 404   switch (I->getOpcode()) {
 405     case Instruction::Call:
 406       return lookup_or_add_call(cast<CallInst>(I));
 407     case Instruction::Add:
 408     case Instruction::FAdd:
 409     case Instruction::Sub:
 410     case Instruction::FSub:
 411     case Instruction::Mul:
 412     case Instruction::FMul:
 413     case Instruction::UDiv:
 414     case Instruction::SDiv:
 415     case Instruction::FDiv:
 416     case Instruction::URem:
 417     case Instruction::SRem:
 418     case Instruction::FRem:
 419     case Instruction::Shl:
 420     case Instruction::LShr:
 421     case Instruction::AShr:
 422     case Instruction::And:
 423     case Instruction::Or:
 424     case Instruction::Xor:
 425     case Instruction::ICmp:
 426     case Instruction::FCmp:
 427     case Instruction::Trunc:
 428     case Instruction::ZExt:
 429     case Instruction::SExt:
 430     case Instruction::FPToUI:
 431     case Instruction::FPToSI:
 432     case Instruction::UIToFP:
 433     case Instruction::SIToFP:
 434     case Instruction::FPTrunc:
 435     case Instruction::FPExt:
 436     case Instruction::PtrToInt:
 437     case Instruction::IntToPtr:
 438     case Instruction::BitCast:
 439     case Instruction::Select:
 440     case Instruction::ExtractElement:
 441     case Instruction::InsertElement:
 442     case Instruction::ShuffleVector:
 443     case Instruction::InsertValue:
 444     case Instruction::GetElementPtr:
 445       exp = create_expression(I);
 446       break;
 447     case Instruction::ExtractValue:
 448       exp = create_extractvalue_expression(cast<ExtractValueInst>(I));
 449       break;
 450     default:
 451       valueNumbering[V] = nextValueNumber;
 452       return nextValueNumber++;
 453   }
 454
 455   uint32_t& e = expressionNumbering[exp];
 456   if (!e) e = nextValueNumber++;
 457   valueNumbering[V] = e;
 458   return e;
 459 }
 460
 461 /// lookup - Returns the value number of the specified value. Fails if
 462 /// the value has not yet been numbered.
 463 uint32_t ValueTable::lookup(Value *V) const {
 464   DenseMap<Value*, uint32_t>::const_iterator VI = valueNumbering.find(V);
 465   assert(VI != valueNumbering.end() && "Value not numbered?");
 466   return VI->second;
 467 }
 468
 469 /// lookup_or_add_cmp - Returns the value number of the given comparison,
 470 /// assigning it a new number if it did not have one before.  Useful when
 471 /// we deduced the result of a comparison, but don't immediately have an
 472 /// instruction realizing that comparison to hand.
 473 uint32_t ValueTable::lookup_or_add_cmp(unsigned Opcode,
 474                                        CmpInst::Predicate Predicate,
 475                                        Value *LHS, Value *RHS) {
 476   Expression exp = create_cmp_expression(Opcode, Predicate, LHS, RHS);
 477   uint32_t& e = expressionNumbering[exp];
 478   if (!e) e = nextValueNumber++;
 479   return e;
 480 }
 481
 482 /// clear - Remove all entries from the ValueTable.
 483 void ValueTable::clear() {
 484   valueNumbering.clear();
 485   expressionNumbering.clear();
 486   nextValueNumber = 1;
 487 }
 488
 489 /// erase - Remove a value from the value numbering.
 490 void ValueTable::erase(Value *V) {
 491   valueNumbering.erase(V);
 492 }
 493
 494 /// verifyRemoved - Verify that the value is removed from all internal data
 495 /// structures.
 496 void ValueTable::verifyRemoved(const Value *V) const {
 497   for (DenseMap<Value*, uint32_t>::const_iterator
 498          I = valueNumbering.begin(), E = valueNumbering.end(); I != E; ++I) {
 499     assert(I->first != V && "Inst still occurs in value numbering map!");
 500   }
 501 }
 502
 503 //===----------------------------------------------------------------------===//
 504 //                                GVN Pass
 505 //===----------------------------------------------------------------------===//
 506
 507 namespace {
 508   class GVN;
 509   struct AvailableValueInBlock {
 510     /// BB - The basic block in question.
 511     BasicBlock *BB;
 512     enum ValType {
 513       SimpleVal,  // A simple offsetted value that is accessed.
 514       LoadVal,    // A value produced by a load.
 515       MemIntrin,  // A memory intrinsic which is loaded from.
 516       UndefVal    // A UndefValue representing a value from dead block (which
 517                   // is not yet physically removed from the CFG).
 518     };
 519
 520     /// V - The value that is live out of the block.
 521     PointerIntPair<Value *, 2, ValType> Val;
 522
 523     /// Offset - The byte offset in Val that is interesting for the load query.
 524     unsigned Offset;
 525
 526     static AvailableValueInBlock get(BasicBlock *BB, Value *V,
 527                                      unsigned Offset = 0) {
 528       AvailableValueInBlock Res;
 529       Res.BB = BB;
 530       Res.Val.setPointer(V);
 531       Res.Val.setInt(SimpleVal);
 532       Res.Offset = Offset;
 533       return Res;
 534     }
 535
 536     static AvailableValueInBlock getMI(BasicBlock *BB, MemIntrinsic *MI,
 537                                        unsigned Offset = 0) {
 538       AvailableValueInBlock Res;
 539       Res.BB = BB;
 540       Res.Val.setPointer(MI);
 541       Res.Val.setInt(MemIntrin);
 542       Res.Offset = Offset;
 543       return Res;
 544     }
 545
 546     static AvailableValueInBlock getLoad(BasicBlock *BB, LoadInst *LI,
 547                                          unsigned Offset = 0) {
 548       AvailableValueInBlock Res;
 549       Res.BB = BB;
 550       Res.Val.setPointer(LI);
 551       Res.Val.setInt(LoadVal);
 552       Res.Offset = Offset;
 553       return Res;
 554     }
 555
 556     static AvailableValueInBlock getUndef(BasicBlock *BB) {
 557       AvailableValueInBlock Res;
 558       Res.BB = BB;
 559       Res.Val.setPointer(nullptr);
 560       Res.Val.setInt(UndefVal);
 561       Res.Offset = 0;
 562       return Res;
 563     }
 564
 565     bool isSimpleValue() const { return Val.getInt() == SimpleVal; }
 566     bool isCoercedLoadValue() const { return Val.getInt() == LoadVal; }
 567     bool isMemIntrinValue() const { return Val.getInt() == MemIntrin; }
 568     bool isUndefValue() const { return Val.getInt() == UndefVal; }
 569
 570     Value *getSimpleValue() const {
 571       assert(isSimpleValue() && "Wrong accessor");
 572       return Val.getPointer();
 573     }
 574
 575     LoadInst *getCoercedLoadValue() const {
 576       assert(isCoercedLoadValue() && "Wrong accessor");
 577       return cast<LoadInst>(Val.getPointer());
 578     }
 579
 580     MemIntrinsic *getMemIntrinValue() const {
 581       assert(isMemIntrinValue() && "Wrong accessor");
 582       return cast<MemIntrinsic>(Val.getPointer());
 583     }
 584
 585     /// MaterializeAdjustedValue - Emit code into this block to adjust the value
 586     /// defined here to the specified type.  This handles various coercion cases.
 587     Value *MaterializeAdjustedValue(Type *LoadTy, GVN &gvn) const;
 588   };
 589
 590   class GVN : public FunctionPass {
 591     bool NoLoads;
 592     MemoryDependenceAnalysis *MD;
 593     DominatorTree *DT;
 594     const DataLayout *DL;
 595     const TargetLibraryInfo *TLI;
 596     AssumptionCache *AC;
 597     SetVector<BasicBlock *> DeadBlocks;
 598
 599     ValueTable VN;
 600
 601     /// LeaderTable - A mapping from value numbers to lists of Value*'s that
 602     /// have that value number.  Use findLeader to query it.
 603     struct LeaderTableEntry {
 604       Value *Val;
 605       const BasicBlock *BB;
 606       LeaderTableEntry *Next;
 607     };
 608     DenseMap<uint32_t, LeaderTableEntry> LeaderTable;
 609     BumpPtrAllocator TableAllocator;
 610
 611     SmallVector<Instruction*, 8> InstrsToErase;
 612
 613     typedef SmallVector<NonLocalDepResult, 64> LoadDepVect;
 614     typedef SmallVector<AvailableValueInBlock, 64> AvailValInBlkVect;
 615     typedef SmallVector<BasicBlock*, 64> UnavailBlkVect;
 616
 617   public:
 618     static char ID; // Pass identification, replacement for typeid
 619     explicit GVN(bool noloads = false)
 620         : FunctionPass(ID), NoLoads(noloads), MD(nullptr) {
 621       initializeGVNPass(*PassRegistry::getPassRegistry());
 622     }
 623
 624     bool runOnFunction(Function &F) override;
 625
 626     /// markInstructionForDeletion - This removes the specified instruction from
 627     /// our various maps and marks it for deletion.
 628     void markInstructionForDeletion(Instruction *I) {
 629       VN.erase(I);
 630       InstrsToErase.push_back(I);
 631     }
 632
 633     const DataLayout *getDataLayout() const { return DL; }
 634     DominatorTree &getDominatorTree() const { return *DT; }
 635     AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); }
 636     MemoryDependenceAnalysis &getMemDep() const { return *MD; }
 637   private:
 638     /// addToLeaderTable - Push a new Value to the LeaderTable onto the list for
 639     /// its value number.
 640     void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) {
 641       LeaderTableEntry &Curr = LeaderTable[N];
 642       if (!Curr.Val) {
 643         Curr.Val = V;
 644         Curr.BB = BB;
 645         return;
 646       }
 647
 648       LeaderTableEntry *Node = TableAllocator.Allocate<LeaderTableEntry>();
 649       Node->Val = V;
 650       Node->BB = BB;
 651       Node->Next = Curr.Next;
 652       Curr.Next = Node;
 653     }
 654
 655     /// removeFromLeaderTable - Scan the list of values corresponding to a given
 656     /// value number, and remove the given instruction if encountered.
 657     void removeFromLeaderTable(uint32_t N, Instruction *I, BasicBlock *BB) {
 658       LeaderTableEntry* Prev = nullptr;
 659       LeaderTableEntry* Curr = &LeaderTable[N];
 660
 661       while (Curr->Val != I || Curr->BB != BB) {
 662         Prev = Curr;
 663         Curr = Curr->Next;
 664       }
 665
 666       if (Prev) {
 667         Prev->Next = Curr->Next;
 668       } else {
 669         if (!Curr->Next) {
 670           Curr->Val = nullptr;
 671           Curr->BB = nullptr;
 672         } else {
 673           LeaderTableEntry* Next = Curr->Next;
 674           Curr->Val = Next->Val;
 675           Curr->BB = Next->BB;
 676           Curr->Next = Next->Next;
 677         }
 678       }
 679     }
 680
 681     // List of critical edges to be split between iterations.
 682     SmallVector<std::pair<TerminatorInst*, unsigned>, 4> toSplit;
 683
 684     // This transformation requires dominator postdominator info
 685     void getAnalysisUsage(AnalysisUsage &AU) const override {
 686       AU.addRequired<AssumptionCacheTracker>();
 687       AU.addRequired<DominatorTreeWrapperPass>();
 688       AU.addRequired<TargetLibraryInfoWrapperPass>();
 689       if (!NoLoads)
 690         AU.addRequired<MemoryDependenceAnalysis>();
 691       AU.addRequired<AliasAnalysis>();
 692
 693       AU.addPreserved<DominatorTreeWrapperPass>();
 694       AU.addPreserved<AliasAnalysis>();
 695     }
 696
 697
 698     // Helper fuctions of redundant load elimination
 699     bool processLoad(LoadInst *L);
 700     bool processNonLocalLoad(LoadInst *L);
 701     void AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
 702                                  AvailValInBlkVect &ValuesPerBlock,
 703                                  UnavailBlkVect &UnavailableBlocks);
 704     bool PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
 705                         UnavailBlkVect &UnavailableBlocks);
 706
 707     // Other helper routines
 708     bool processInstruction(Instruction *I);
 709     bool processBlock(BasicBlock *BB);
 710     void dump(DenseMap<uint32_t, Value*> &d);
 711     bool iterateOnFunction(Function &F);
 712     bool performPRE(Function &F);
 713     bool performScalarPRE(Instruction *I);
 714     bool performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
 715                                    unsigned int ValNo);
 716     Value *findLeader(const BasicBlock *BB, uint32_t num);
 717     void cleanupGlobalSets();
 718     void verifyRemoved(const Instruction *I) const;
 719     bool splitCriticalEdges();
 720     BasicBlock *splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ);
 721     unsigned replaceAllDominatedUsesWith(Value *From, Value *To,
 722                                          const BasicBlockEdge &Root);
 723     bool propagateEquality(Value *LHS, Value *RHS, const BasicBlockEdge &Root);
 724     bool processFoldableCondBr(BranchInst *BI);
 725     void addDeadBlock(BasicBlock *BB);
 726     void assignValNumForDeadCode();
 727   };
 728
 729   char GVN::ID = 0;
 730 }
 731
 732 // createGVNPass - The public interface to this file...
 733 FunctionPass *llvm::createGVNPass(bool NoLoads) {
 734   return new GVN(NoLoads);
 735 }
 736
 737 INITIALIZE_PASS_BEGIN(GVN, "gvn", "Global Value Numbering", false, false)
 738 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 739 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis)
 740 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 741 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 742 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 743 INITIALIZE_PASS_END(GVN, "gvn", "Global Value Numbering", false, false)
 744
 745 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 746 void GVN::dump(DenseMap<uint32_t, Value*>& d) {
 747   errs() << "{\n";
 748   for (DenseMap<uint32_t, Value*>::iterator I = d.begin(),
 749        E = d.end(); I != E; ++I) {
 750       errs() << I->first << "\n";
 751       I->second->dump();
 752   }
 753   errs() << "}\n";
 754 }
 755 #endif
 756
 757 /// IsValueFullyAvailableInBlock - Return true if we can prove that the value
 758 /// we're analyzing is fully available in the specified block.  As we go, keep
 759 /// track of which blocks we know are fully alive in FullyAvailableBlocks.  This
 760 /// map is actually a tri-state map with the following values:
 761 ///   0) we know the block *is not* fully available.
 762 ///   1) we know the block *is* fully available.
 763 ///   2) we do not know whether the block is fully available or not, but we are
 764 ///      currently speculating that it will be.
 765 ///   3) we are speculating for this block and have used that to speculate for
 766 ///      other blocks.
 767 static bool IsValueFullyAvailableInBlock(BasicBlock *BB,
 768                             DenseMap<BasicBlock*, char> &FullyAvailableBlocks,
 769                             uint32_t RecurseDepth) {
 770   if (RecurseDepth > MaxRecurseDepth)
 771     return false;
 772
 773   // Optimistically assume that the block is fully available and check to see
 774   // if we already know about this block in one lookup.
 775   std::pair<DenseMap<BasicBlock*, char>::iterator, char> IV =
 776     FullyAvailableBlocks.insert(std::make_pair(BB, 2));
 777
 778   // If the entry already existed for this block, return the precomputed value.
 779   if (!IV.second) {
 780     // If this is a speculative "available" value, mark it as being used for
 781     // speculation of other blocks.
 782     if (IV.first->second == 2)
 783       IV.first->second = 3;
 784     return IV.first->second != 0;
 785   }
 786
 787   // Otherwise, see if it is fully available in all predecessors.
 788   pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 789
 790   // If this block has no predecessors, it isn't live-in here.
 791   if (PI == PE)
 792     goto SpeculationFailure;
 793
 794   for (; PI != PE; ++PI)
 795     // If the value isn't fully available in one of our predecessors, then it
 796     // isn't fully available in this block either.  Undo our previous
 797     // optimistic assumption and bail out.
 798     if (!IsValueFullyAvailableInBlock(*PI, FullyAvailableBlocks,RecurseDepth+1))
 799       goto SpeculationFailure;
 800
 801   return true;
 802
 803 // SpeculationFailure - If we get here, we found out that this is not, after
 804 // all, a fully-available block.  We have a problem if we speculated on this and
 805 // used the speculation to mark other blocks as available.
 806 SpeculationFailure:
 807   char &BBVal = FullyAvailableBlocks[BB];
 808
 809   // If we didn't speculate on this, just return with it set to false.
 810   if (BBVal == 2) {
 811     BBVal = 0;
 812     return false;
 813   }
 814
 815   // If we did speculate on this value, we could have blocks set to 1 that are
 816   // incorrect.  Walk the (transitive) successors of this block and mark them as
 817   // 0 if set to one.
 818   SmallVector<BasicBlock*, 32> BBWorklist;
 819   BBWorklist.push_back(BB);
 820
 821   do {
 822     BasicBlock *Entry = BBWorklist.pop_back_val();
 823     // Note that this sets blocks to 0 (unavailable) if they happen to not
 824     // already be in FullyAvailableBlocks.  This is safe.
 825     char &EntryVal = FullyAvailableBlocks[Entry];
 826     if (EntryVal == 0) continue;  // Already unavailable.
 827
 828     // Mark as unavailable.
 829     EntryVal = 0;
 830
 831     BBWorklist.append(succ_begin(Entry), succ_end(Entry));
 832   } while (!BBWorklist.empty());
 833
 834   return false;
 835 }
 836
 837
 838 /// CanCoerceMustAliasedValueToLoad - Return true if
 839 /// CoerceAvailableValueToLoadType will succeed.
 840 static bool CanCoerceMustAliasedValueToLoad(Value *StoredVal,
 841                                             Type *LoadTy,
 842                                             const DataLayout &DL) {
 843   // If the loaded or stored value is an first class array or struct, don't try
 844   // to transform them.  We need to be able to bitcast to integer.
 845   if (LoadTy->isStructTy() || LoadTy->isArrayTy() ||
 846       StoredVal->getType()->isStructTy() ||
 847       StoredVal->getType()->isArrayTy())
 848     return false;
 849
 850   // The store has to be at least as big as the load.
 851   if (DL.getTypeSizeInBits(StoredVal->getType()) <
 852         DL.getTypeSizeInBits(LoadTy))
 853     return false;
 854
 855   return true;
 856 }
 857
 858 /// CoerceAvailableValueToLoadType - If we saw a store of a value to memory, and
 859 /// then a load from a must-aliased pointer of a different type, try to coerce
 860 /// the stored value.  LoadedTy is the type of the load we want to replace and
 861 /// InsertPt is the place to insert new instructions.
 862 ///
 863 /// If we can't do it, return null.
 864 static Value *CoerceAvailableValueToLoadType(Value *StoredVal,
 865                                              Type *LoadedTy,
 866                                              Instruction *InsertPt,
 867                                              const DataLayout &DL) {
 868   if (!CanCoerceMustAliasedValueToLoad(StoredVal, LoadedTy, DL))
 869     return nullptr;
 870
 871   // If this is already the right type, just return it.
 872   Type *StoredValTy = StoredVal->getType();
 873
 874   uint64_t StoreSize = DL.getTypeSizeInBits(StoredValTy);
 875   uint64_t LoadSize = DL.getTypeSizeInBits(LoadedTy);
 876
 877   // If the store and reload are the same size, we can always reuse it.
 878   if (StoreSize == LoadSize) {
 879     // Pointer to Pointer -> use bitcast.
 880     if (StoredValTy->getScalarType()->isPointerTy() &&
 881         LoadedTy->getScalarType()->isPointerTy())
 882       return new BitCastInst(StoredVal, LoadedTy, "", InsertPt);
 883
 884     // Convert source pointers to integers, which can be bitcast.
 885     if (StoredValTy->getScalarType()->isPointerTy()) {
 886       StoredValTy = DL.getIntPtrType(StoredValTy);
 887       StoredVal = new PtrToIntInst(StoredVal, StoredValTy, "", InsertPt);
 888     }
 889
 890     Type *TypeToCastTo = LoadedTy;
 891     if (TypeToCastTo->getScalarType()->isPointerTy())
 892       TypeToCastTo = DL.getIntPtrType(TypeToCastTo);
 893
 894     if (StoredValTy != TypeToCastTo)
 895       StoredVal = new BitCastInst(StoredVal, TypeToCastTo, "", InsertPt);
 896
 897     // Cast to pointer if the load needs a pointer type.
 898     if (LoadedTy->getScalarType()->isPointerTy())
 899       StoredVal = new IntToPtrInst(StoredVal, LoadedTy, "", InsertPt);
 900
 901     return StoredVal;
 902   }
 903
 904   // If the loaded value is smaller than the available value, then we can
 905   // extract out a piece from it.  If the available value is too small, then we
 906   // can't do anything.
 907   assert(StoreSize >= LoadSize && "CanCoerceMustAliasedValueToLoad fail");
 908
 909   // Convert source pointers to integers, which can be manipulated.
 910   if (StoredValTy->getScalarType()->isPointerTy()) {
 911     StoredValTy = DL.getIntPtrType(StoredValTy);
 912     StoredVal = new PtrToIntInst(StoredVal, StoredValTy, "", InsertPt);
 913   }
 914
 915   // Convert vectors and fp to integer, which can be manipulated.
 916   if (!StoredValTy->isIntegerTy()) {
 917     StoredValTy = IntegerType::get(StoredValTy->getContext(), StoreSize);
 918     StoredVal = new BitCastInst(StoredVal, StoredValTy, "", InsertPt);
 919   }
 920
 921   // If this is a big-endian system, we need to shift the value down to the low
 922   // bits so that a truncate will work.
 923   if (DL.isBigEndian()) {
 924     Constant *Val = ConstantInt::get(StoredVal->getType(), StoreSize-LoadSize);
 925     StoredVal = BinaryOperator::CreateLShr(StoredVal, Val, "tmp", InsertPt);
 926   }
 927
 928   // Truncate the integer to the right size now.
 929   Type *NewIntTy = IntegerType::get(StoredValTy->getContext(), LoadSize);
 930   StoredVal = new TruncInst(StoredVal, NewIntTy, "trunc", InsertPt);
 931
 932   if (LoadedTy == NewIntTy)
 933     return StoredVal;
 934
 935   // If the result is a pointer, inttoptr.
 936   if (LoadedTy->getScalarType()->isPointerTy())
 937     return new IntToPtrInst(StoredVal, LoadedTy, "inttoptr", InsertPt);
 938
 939   // Otherwise, bitcast.
 940   return new BitCastInst(StoredVal, LoadedTy, "bitcast", InsertPt);
 941 }
 942
 943 /// AnalyzeLoadFromClobberingWrite - This function is called when we have a
 944 /// memdep query of a load that ends up being a clobbering memory write (store,
 945 /// memset, memcpy, memmove).  This means that the write *may* provide bits used
 946 /// by the load but we can't be sure because the pointers don't mustalias.
 947 ///
 948 /// Check this case to see if there is anything more we can do before we give
 949 /// up.  This returns -1 if we have to give up, or a byte number in the stored
 950 /// value of the piece that feeds the load.
 951 static int AnalyzeLoadFromClobberingWrite(Type *LoadTy, Value *LoadPtr,
 952                                           Value *WritePtr,
 953                                           uint64_t WriteSizeInBits,
 954                                           const DataLayout &DL) {
 955   // If the loaded or stored value is a first class array or struct, don't try
 956   // to transform them.  We need to be able to bitcast to integer.
 957   if (LoadTy->isStructTy() || LoadTy->isArrayTy())
 958     return -1;
 959
 960   int64_t StoreOffset = 0, LoadOffset = 0;
 961   Value *StoreBase = GetPointerBaseWithConstantOffset(WritePtr,StoreOffset,&DL);
 962   Value *LoadBase = GetPointerBaseWithConstantOffset(LoadPtr, LoadOffset, &DL);
 963   if (StoreBase != LoadBase)
 964     return -1;
 965
 966   // If the load and store are to the exact same address, they should have been
 967   // a must alias.  AA must have gotten confused.
 968   // FIXME: Study to see if/when this happens.  One case is forwarding a memset
 969   // to a load from the base of the memset.
 970 #if 0
 971   if (LoadOffset == StoreOffset) {
 972     dbgs() << "STORE/LOAD DEP WITH COMMON POINTER MISSED:\n"
 973     << "Base       = " << *StoreBase << "\n"
 974     << "Store Ptr  = " << *WritePtr << "\n"
 975     << "Store Offs = " << StoreOffset << "\n"
 976     << "Load Ptr   = " << *LoadPtr << "\n";
 977     abort();
 978   }
 979 #endif
 980
 981   // If the load and store don't overlap at all, the store doesn't provide
 982   // anything to the load.  In this case, they really don't alias at all, AA
 983   // must have gotten confused.
 984   uint64_t LoadSize = DL.getTypeSizeInBits(LoadTy);
 985
 986   if ((WriteSizeInBits & 7) | (LoadSize & 7))
 987     return -1;
 988   uint64_t StoreSize = WriteSizeInBits >> 3;  // Convert to bytes.
 989   LoadSize >>= 3;
 990
 991
 992   bool isAAFailure = false;
 993   if (StoreOffset < LoadOffset)
 994     isAAFailure = StoreOffset+int64_t(StoreSize) <= LoadOffset;
 995   else
 996     isAAFailure = LoadOffset+int64_t(LoadSize) <= StoreOffset;
 997
 998   if (isAAFailure) {
 999 #if 0
1000     dbgs() << "STORE LOAD DEP WITH COMMON BASE:\n"
1001     << "Base       = " << *StoreBase << "\n"
1002     << "Store Ptr  = " << *WritePtr << "\n"
1003     << "Store Offs = " << StoreOffset << "\n"
1004     << "Load Ptr   = " << *LoadPtr << "\n";
1005     abort();
1006 #endif
1007     return -1;
1008   }
1009
1010   // If the Load isn't completely contained within the stored bits, we don't
1011   // have all the bits to feed it.  We could do something crazy in the future
1012   // (issue a smaller load then merge the bits in) but this seems unlikely to be
1013   // valuable.
1014   if (StoreOffset > LoadOffset ||
1015       StoreOffset+StoreSize < LoadOffset+LoadSize)
1016     return -1;
1017
1018   // Okay, we can do this transformation.  Return the number of bytes into the
1019   // store that the load is.
1020   return LoadOffset-StoreOffset;
1021 }
1022
1023 /// AnalyzeLoadFromClobberingStore - This function is called when we have a
1024 /// memdep query of a load that ends up being a clobbering store.
1025 static int AnalyzeLoadFromClobberingStore(Type *LoadTy, Value *LoadPtr,
1026                                           StoreInst *DepSI,
1027                                           const DataLayout &DL) {
1028   // Cannot handle reading from store of first-class aggregate yet.
1029   if (DepSI->getValueOperand()->getType()->isStructTy() ||
1030       DepSI->getValueOperand()->getType()->isArrayTy())
1031     return -1;
1032
1033   Value *StorePtr = DepSI->getPointerOperand();
1034   uint64_t StoreSize =DL.getTypeSizeInBits(DepSI->getValueOperand()->getType());
1035   return AnalyzeLoadFromClobberingWrite(LoadTy, LoadPtr,
1036                                         StorePtr, StoreSize, DL);
1037 }
1038
1039 /// AnalyzeLoadFromClobberingLoad - This function is called when we have a
1040 /// memdep query of a load that ends up being clobbered by another load.  See if
1041 /// the other load can feed into the second load.
1042 static int AnalyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr,
1043                                          LoadInst *DepLI, const DataLayout &DL){
1044   // Cannot handle reading from store of first-class aggregate yet.
1045   if (DepLI->getType()->isStructTy() || DepLI->getType()->isArrayTy())
1046     return -1;
1047
1048   Value *DepPtr = DepLI->getPointerOperand();
1049   uint64_t DepSize = DL.getTypeSizeInBits(DepLI->getType());
1050   int R = AnalyzeLoadFromClobberingWrite(LoadTy, LoadPtr, DepPtr, DepSize, DL);
1051   if (R != -1) return R;
1052
1053   // If we have a load/load clobber an DepLI can be widened to cover this load,
1054   // then we should widen it!
1055   int64_t LoadOffs = 0;
1056   const Value *LoadBase =
1057     GetPointerBaseWithConstantOffset(LoadPtr, LoadOffs, &DL);
1058   unsigned LoadSize = DL.getTypeStoreSize(LoadTy);
1059
1060   unsigned Size = MemoryDependenceAnalysis::
1061     getLoadLoadClobberFullWidthSize(LoadBase, LoadOffs, LoadSize, DepLI, DL);
1062   if (Size == 0) return -1;
1063
1064   return AnalyzeLoadFromClobberingWrite(LoadTy, LoadPtr, DepPtr, Size*8, DL);
1065 }
1066
1067
1068
1069 static int AnalyzeLoadFromClobberingMemInst(Type *LoadTy, Value *LoadPtr,
1070                                             MemIntrinsic *MI,
1071                                             const DataLayout &DL) {
1072   // If the mem operation is a non-constant size, we can't handle it.
1073   ConstantInt *SizeCst = dyn_cast<ConstantInt>(MI->getLength());
1074   if (!SizeCst) return -1;
1075   uint64_t MemSizeInBits = SizeCst->getZExtValue()*8;
1076
1077   // If this is memset, we just need to see if the offset is valid in the size
1078   // of the memset..
1079   if (MI->getIntrinsicID() == Intrinsic::memset)
1080     return AnalyzeLoadFromClobberingWrite(LoadTy, LoadPtr, MI->getDest(),
1081                                           MemSizeInBits, DL);
1082
1083   // If we have a memcpy/memmove, the only case we can handle is if this is a
1084   // copy from constant memory.  In that case, we can read directly from the
1085   // constant memory.
1086   MemTransferInst *MTI = cast<MemTransferInst>(MI);
1087
1088   Constant *Src = dyn_cast<Constant>(MTI->getSource());
1089   if (!Src) return -1;
1090
1091   GlobalVariable *GV = dyn_cast<GlobalVariable>(GetUnderlyingObject(Src, &DL));
1092   if (!GV || !GV->isConstant()) return -1;
1093
1094   // See if the access is within the bounds of the transfer.
1095   int Offset = AnalyzeLoadFromClobberingWrite(LoadTy, LoadPtr,
1096                                               MI->getDest(), MemSizeInBits, DL);
1097   if (Offset == -1)
1098     return Offset;
1099
1100   unsigned AS = Src->getType()->getPointerAddressSpace();
1101   // Otherwise, see if we can constant fold a load from the constant with the
1102   // offset applied as appropriate.
1103   Src = ConstantExpr::getBitCast(Src,
1104                                  Type::getInt8PtrTy(Src->getContext(), AS));
1105   Constant *OffsetCst =
1106     ConstantInt::get(Type::getInt64Ty(Src->getContext()), (unsigned)Offset);
1107   Src = ConstantExpr::getGetElementPtr(Src, OffsetCst);
1108   Src = ConstantExpr::getBitCast(Src, PointerType::get(LoadTy, AS));
1109   if (ConstantFoldLoadFromConstPtr(Src, &DL))
1110     return Offset;
1111   return -1;
1112 }
1113
1114
1115 /// GetStoreValueForLoad - This function is called when we have a
1116 /// memdep query of a load that ends up being a clobbering store.  This means
1117 /// that the store provides bits used by the load but we the pointers don't
1118 /// mustalias.  Check this case to see if there is anything more we can do
1119 /// before we give up.
1120 static Value *GetStoreValueForLoad(Value *SrcVal, unsigned Offset,
1121                                    Type *LoadTy,
1122                                    Instruction *InsertPt, const DataLayout &DL){
1123   LLVMContext &Ctx = SrcVal->getType()->getContext();
1124
1125   uint64_t StoreSize = (DL.getTypeSizeInBits(SrcVal->getType()) + 7) / 8;
1126   uint64_t LoadSize = (DL.getTypeSizeInBits(LoadTy) + 7) / 8;
1127
1128   IRBuilder<> Builder(InsertPt->getParent(), InsertPt);
1129
1130   // Compute which bits of the stored value are being used by the load.  Convert
1131   // to an integer type to start with.
1132   if (SrcVal->getType()->getScalarType()->isPointerTy())
1133     SrcVal = Builder.CreatePtrToInt(SrcVal,
1134         DL.getIntPtrType(SrcVal->getType()));
1135   if (!SrcVal->getType()->isIntegerTy())
1136     SrcVal = Builder.CreateBitCast(SrcVal, IntegerType::get(Ctx, StoreSize*8));
1137
1138   // Shift the bits to the least significant depending on endianness.
1139   unsigned ShiftAmt;
1140   if (DL.isLittleEndian())
1141     ShiftAmt = Offset*8;
1142   else
1143     ShiftAmt = (StoreSize-LoadSize-Offset)*8;
1144
1145   if (ShiftAmt)
1146     SrcVal = Builder.CreateLShr(SrcVal, ShiftAmt);
1147
1148   if (LoadSize != StoreSize)
1149     SrcVal = Builder.CreateTrunc(SrcVal, IntegerType::get(Ctx, LoadSize*8));
1150
1151   return CoerceAvailableValueToLoadType(SrcVal, LoadTy, InsertPt, DL);
1152 }
1153
1154 /// GetLoadValueForLoad - This function is called when we have a
1155 /// memdep query of a load that ends up being a clobbering load.  This means
1156 /// that the load *may* provide bits used by the load but we can't be sure
1157 /// because the pointers don't mustalias.  Check this case to see if there is
1158 /// anything more we can do before we give up.
1159 static Value *GetLoadValueForLoad(LoadInst *SrcVal, unsigned Offset,
1160                                   Type *LoadTy, Instruction *InsertPt,
1161                                   GVN &gvn) {
1162   const DataLayout &DL = *gvn.getDataLayout();
1163   // If Offset+LoadTy exceeds the size of SrcVal, then we must be wanting to
1164   // widen SrcVal out to a larger load.
1165   unsigned SrcValSize = DL.getTypeStoreSize(SrcVal->getType());
1166   unsigned LoadSize = DL.getTypeStoreSize(LoadTy);
1167   if (Offset+LoadSize > SrcValSize) {
1168     assert(SrcVal->isSimple() && "Cannot widen volatile/atomic load!");
1169     assert(SrcVal->getType()->isIntegerTy() && "Can't widen non-integer load");
1170     // If we have a load/load clobber an DepLI can be widened to cover this
1171     // load, then we should widen it to the next power of 2 size big enough!
1172     unsigned NewLoadSize = Offset+LoadSize;
1173     if (!isPowerOf2_32(NewLoadSize))
1174       NewLoadSize = NextPowerOf2(NewLoadSize);
1175
1176     Value *PtrVal = SrcVal->getPointerOperand();
1177
1178     // Insert the new load after the old load.  This ensures that subsequent
1179     // memdep queries will find the new load.  We can't easily remove the old
1180     // load completely because it is already in the value numbering table.
1181     IRBuilder<> Builder(SrcVal->getParent(), ++BasicBlock::iterator(SrcVal));
1182     Type *DestPTy =
1183       IntegerType::get(LoadTy->getContext(), NewLoadSize*8);
1184     DestPTy = PointerType::get(DestPTy,
1185                                PtrVal->getType()->getPointerAddressSpace());
1186     Builder.SetCurrentDebugLocation(SrcVal->getDebugLoc());
1187     PtrVal = Builder.CreateBitCast(PtrVal, DestPTy);
1188     LoadInst *NewLoad = Builder.CreateLoad(PtrVal);
1189     NewLoad->takeName(SrcVal);
1190     NewLoad->setAlignment(SrcVal->getAlignment());
1191
1192     DEBUG(dbgs() << "GVN WIDENED LOAD: " << *SrcVal << "\n");
1193     DEBUG(dbgs() << "TO: " << *NewLoad << "\n");
1194
1195     // Replace uses of the original load with the wider load.  On a big endian
1196     // system, we need to shift down to get the relevant bits.
1197     Value *RV = NewLoad;
1198     if (DL.isBigEndian())
1199       RV = Builder.CreateLShr(RV,
1200                     NewLoadSize*8-SrcVal->getType()->getPrimitiveSizeInBits());
1201     RV = Builder.CreateTrunc(RV, SrcVal->getType());
1202     SrcVal->replaceAllUsesWith(RV);
1203
1204     // We would like to use gvn.markInstructionForDeletion here, but we can't
1205     // because the load is already memoized into the leader map table that GVN
1206     // tracks.  It is potentially possible to remove the load from the table,
1207     // but then there all of the operations based on it would need to be
1208     // rehashed.  Just leave the dead load around.
1209     gvn.getMemDep().removeInstruction(SrcVal);
1210     SrcVal = NewLoad;
1211   }
1212
1213   return GetStoreValueForLoad(SrcVal, Offset, LoadTy, InsertPt, DL);
1214 }
1215
1216
1217 /// GetMemInstValueForLoad - This function is called when we have a
1218 /// memdep query of a load that ends up being a clobbering mem intrinsic.
1219 static Value *GetMemInstValueForLoad(MemIntrinsic *SrcInst, unsigned Offset,
1220                                      Type *LoadTy, Instruction *InsertPt,
1221                                      const DataLayout &DL){
1222   LLVMContext &Ctx = LoadTy->getContext();
1223   uint64_t LoadSize = DL.getTypeSizeInBits(LoadTy)/8;
1224
1225   IRBuilder<> Builder(InsertPt->getParent(), InsertPt);
1226
1227   // We know that this method is only called when the mem transfer fully
1228   // provides the bits for the load.
1229   if (MemSetInst *MSI = dyn_cast<MemSetInst>(SrcInst)) {
1230     // memset(P, 'x', 1234) -> splat('x'), even if x is a variable, and
1231     // independently of what the offset is.
1232     Value *Val = MSI->getValue();
1233     if (LoadSize != 1)
1234       Val = Builder.CreateZExt(Val, IntegerType::get(Ctx, LoadSize*8));
1235
1236     Value *OneElt = Val;
1237
1238     // Splat the value out to the right number of bits.
1239     for (unsigned NumBytesSet = 1; NumBytesSet != LoadSize; ) {
1240       // If we can double the number of bytes set, do it.
1241       if (NumBytesSet*2 <= LoadSize) {
1242         Value *ShVal = Builder.CreateShl(Val, NumBytesSet*8);
1243         Val = Builder.CreateOr(Val, ShVal);
1244         NumBytesSet <<= 1;
1245         continue;
1246       }
1247
1248       // Otherwise insert one byte at a time.
1249       Value *ShVal = Builder.CreateShl(Val, 1*8);
1250       Val = Builder.CreateOr(OneElt, ShVal);
1251       ++NumBytesSet;
1252     }
1253
1254     return CoerceAvailableValueToLoadType(Val, LoadTy, InsertPt, DL);
1255   }
1256
1257   // Otherwise, this is a memcpy/memmove from a constant global.
1258   MemTransferInst *MTI = cast<MemTransferInst>(SrcInst);
1259   Constant *Src = cast<Constant>(MTI->getSource());
1260   unsigned AS = Src->getType()->getPointerAddressSpace();
1261
1262   // Otherwise, see if we can constant fold a load from the constant with the
1263   // offset applied as appropriate.
1264   Src = ConstantExpr::getBitCast(Src,
1265                                  Type::getInt8PtrTy(Src->getContext(), AS));
1266   Constant *OffsetCst =
1267     ConstantInt::get(Type::getInt64Ty(Src->getContext()), (unsigned)Offset);
1268   Src = ConstantExpr::getGetElementPtr(Src, OffsetCst);
1269   Src = ConstantExpr::getBitCast(Src, PointerType::get(LoadTy, AS));
1270   return ConstantFoldLoadFromConstPtr(Src, &DL);
1271 }
1272
1273
1274 /// ConstructSSAForLoadSet - Given a set of loads specified by ValuesPerBlock,
1275 /// construct SSA form, allowing us to eliminate LI.  This returns the value
1276 /// that should be used at LI's definition site.
1277 static Value *ConstructSSAForLoadSet(LoadInst *LI,
1278                          SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock,
1279                                      GVN &gvn) {
1280   // Check for the fully redundant, dominating load case.  In this case, we can
1281   // just use the dominating value directly.
1282   if (ValuesPerBlock.size() == 1 &&
1283       gvn.getDominatorTree().properlyDominates(ValuesPerBlock[0].BB,
1284                                                LI->getParent())) {
1285     assert(!ValuesPerBlock[0].isUndefValue() && "Dead BB dominate this block");
1286     return ValuesPerBlock[0].MaterializeAdjustedValue(LI->getType(), gvn);
1287   }
1288
1289   // Otherwise, we have to construct SSA form.
1290   SmallVector<PHINode*, 8> NewPHIs;
1291   SSAUpdater SSAUpdate(&NewPHIs);
1292   SSAUpdate.Initialize(LI->getType(), LI->getName());
1293
1294   Type *LoadTy = LI->getType();
1295
1296   for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i) {
1297     const AvailableValueInBlock &AV = ValuesPerBlock[i];
1298     BasicBlock *BB = AV.BB;
1299
1300     if (SSAUpdate.HasValueForBlock(BB))
1301       continue;
1302
1303     SSAUpdate.AddAvailableValue(BB, AV.MaterializeAdjustedValue(LoadTy, gvn));
1304   }
1305
1306   // Perform PHI construction.
1307   Value *V = SSAUpdate.GetValueInMiddleOfBlock(LI->getParent());
1308
1309   // If new PHI nodes were created, notify alias analysis.
1310   if (V->getType()->getScalarType()->isPointerTy()) {
1311     AliasAnalysis *AA = gvn.getAliasAnalysis();
1312
1313     for (unsigned i = 0, e = NewPHIs.size(); i != e; ++i)
1314       AA->copyValue(LI, NewPHIs[i]);
1315
1316     // Now that we've copied information to the new PHIs, scan through
1317     // them again and inform alias analysis that we've added potentially
1318     // escaping uses to any values that are operands to these PHIs.
1319     for (unsigned i = 0, e = NewPHIs.size(); i != e; ++i) {
1320       PHINode *P = NewPHIs[i];
1321       for (unsigned ii = 0, ee = P->getNumIncomingValues(); ii != ee; ++ii) {
1322         unsigned jj = PHINode::getOperandNumForIncomingValue(ii);
1323         AA->addEscapingUse(P->getOperandUse(jj));
1324       }
1325     }
1326   }
1327
1328   return V;
1329 }
1330
1331 Value *AvailableValueInBlock::MaterializeAdjustedValue(Type *LoadTy, GVN &gvn) const {
1332   Value *Res;
1333   if (isSimpleValue()) {
1334     Res = getSimpleValue();
1335     if (Res->getType() != LoadTy) {
1336       const DataLayout *DL = gvn.getDataLayout();
1337       assert(DL && "Need target data to handle type mismatch case");
1338       Res = GetStoreValueForLoad(Res, Offset, LoadTy, BB->getTerminator(),
1339                                  *DL);
1340
1341       DEBUG(dbgs() << "GVN COERCED NONLOCAL VAL:\nOffset: " << Offset << "  "
1342                    << *getSimpleValue() << '\n'
1343                    << *Res << '\n' << "\n\n\n");
1344     }
1345   } else if (isCoercedLoadValue()) {
1346     LoadInst *Load = getCoercedLoadValue();
1347     if (Load->getType() == LoadTy && Offset == 0) {
1348       Res = Load;
1349     } else {
1350       Res = GetLoadValueForLoad(Load, Offset, LoadTy, BB->getTerminator(),
1351                                 gvn);
1352
1353       DEBUG(dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: " << Offset << "  "
1354                    << *getCoercedLoadValue() << '\n'
1355                    << *Res << '\n' << "\n\n\n");
1356     }
1357   } else if (isMemIntrinValue()) {
1358     const DataLayout *DL = gvn.getDataLayout();
1359     assert(DL && "Need target data to handle type mismatch case");
1360     Res = GetMemInstValueForLoad(getMemIntrinValue(), Offset,
1361                                  LoadTy, BB->getTerminator(), *DL);
1362     DEBUG(dbgs() << "GVN COERCED NONLOCAL MEM INTRIN:\nOffset: " << Offset
1363                  << "  " << *getMemIntrinValue() << '\n'
1364                  << *Res << '\n' << "\n\n\n");
1365   } else {
1366     assert(isUndefValue() && "Should be UndefVal");
1367     DEBUG(dbgs() << "GVN COERCED NONLOCAL Undef:\n";);
1368     return UndefValue::get(LoadTy);
1369   }
1370   return Res;
1371 }
1372
1373 static bool isLifetimeStart(const Instruction *Inst) {
1374   if (const IntrinsicInst* II = dyn_cast<IntrinsicInst>(Inst))
1375     return II->getIntrinsicID() == Intrinsic::lifetime_start;
1376   return false;
1377 }
1378
1379 void GVN::AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
1380                                   AvailValInBlkVect &ValuesPerBlock,
1381                                   UnavailBlkVect &UnavailableBlocks) {
1382
1383   // Filter out useless results (non-locals, etc).  Keep track of the blocks
1384   // where we have a value available in repl, also keep track of whether we see
1385   // dependencies that produce an unknown value for the load (such as a call
1386   // that could potentially clobber the load).
1387   unsigned NumDeps = Deps.size();
1388   for (unsigned i = 0, e = NumDeps; i != e; ++i) {
1389     BasicBlock *DepBB = Deps[i].getBB();
1390     MemDepResult DepInfo = Deps[i].getResult();
1391
1392     if (DeadBlocks.count(DepBB)) {
1393       // Dead dependent mem-op disguise as a load evaluating the same value
1394       // as the load in question.
1395       ValuesPerBlock.push_back(AvailableValueInBlock::getUndef(DepBB));
1396       continue;
1397     }
1398
1399     if (!DepInfo.isDef() && !DepInfo.isClobber()) {
1400       UnavailableBlocks.push_back(DepBB);
1401       continue;
1402     }
1403
1404     if (DepInfo.isClobber()) {
1405       // The address being loaded in this non-local block may not be the same as
1406       // the pointer operand of the load if PHI translation occurs.  Make sure
1407       // to consider the right address.
1408       Value *Address = Deps[i].getAddress();
1409
1410       // If the dependence is to a store that writes to a superset of the bits
1411       // read by the load, we can extract the bits we need for the load from the
1412       // stored value.
1413       if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInfo.getInst())) {
1414         if (DL && Address) {
1415           int Offset = AnalyzeLoadFromClobberingStore(LI->getType(), Address,
1416                                                       DepSI, *DL);
1417           if (Offset != -1) {
1418             ValuesPerBlock.push_back(AvailableValueInBlock::get(DepBB,
1419                                                        DepSI->getValueOperand(),
1420                                                                 Offset));
1421             continue;
1422           }
1423         }
1424       }
1425
1426       // Check to see if we have something like this:
1427       //    load i32* P
1428       //    load i8* (P+1)
1429       // if we have this, replace the later with an extraction from the former.
1430       if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInfo.getInst())) {
1431         // If this is a clobber and L is the first instruction in its block, then
1432         // we have the first instruction in the entry block.
1433         if (DepLI != LI && Address && DL) {
1434           int Offset = AnalyzeLoadFromClobberingLoad(LI->getType(), Address,
1435                                                      DepLI, *DL);
1436
1437           if (Offset != -1) {
1438             ValuesPerBlock.push_back(AvailableValueInBlock::getLoad(DepBB,DepLI,
1439                                                                     Offset));
1440             continue;
1441           }
1442         }
1443       }
1444
1445       // If the clobbering value is a memset/memcpy/memmove, see if we can
1446       // forward a value on from it.
1447       if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(DepInfo.getInst())) {
1448         if (DL && Address) {
1449           int Offset = AnalyzeLoadFromClobberingMemInst(LI->getType(), Address,
1450                                                         DepMI, *DL);
1451           if (Offset != -1) {
1452             ValuesPerBlock.push_back(AvailableValueInBlock::getMI(DepBB, DepMI,
1453                                                                   Offset));
1454             continue;
1455           }
1456         }
1457       }
1458
1459       UnavailableBlocks.push_back(DepBB);
1460       continue;
1461     }
1462
1463     // DepInfo.isDef() here
1464
1465     Instruction *DepInst = DepInfo.getInst();
1466
1467     // Loading the allocation -> undef.
1468     if (isa<AllocaInst>(DepInst) || isMallocLikeFn(DepInst, TLI) ||
1469         // Loading immediately after lifetime begin -> undef.
1470         isLifetimeStart(DepInst)) {
1471       ValuesPerBlock.push_back(AvailableValueInBlock::get(DepBB,
1472                                              UndefValue::get(LI->getType())));
1473       continue;
1474     }
1475
1476     // Loading from calloc (which zero initializes memory) -> zero
1477     if (isCallocLikeFn(DepInst, TLI)) {
1478       ValuesPerBlock.push_back(AvailableValueInBlock::get(
1479           DepBB, Constant::getNullValue(LI->getType())));
1480       continue;
1481     }
1482
1483     if (StoreInst *S = dyn_cast<StoreInst>(DepInst)) {
1484       // Reject loads and stores that are to the same address but are of
1485       // different types if we have to.
1486       if (S->getValueOperand()->getType() != LI->getType()) {
1487         // If the stored value is larger or equal to the loaded value, we can
1488         // reuse it.
1489         if (!DL || !CanCoerceMustAliasedValueToLoad(S->getValueOperand(),
1490                                                     LI->getType(), *DL)) {
1491           UnavailableBlocks.push_back(DepBB);
1492           continue;
1493         }
1494       }
1495
1496       ValuesPerBlock.push_back(AvailableValueInBlock::get(DepBB,
1497                                                          S->getValueOperand()));
1498       continue;
1499     }
1500
1501     if (LoadInst *LD = dyn_cast<LoadInst>(DepInst)) {
1502       // If the types mismatch and we can't handle it, reject reuse of the load.
1503       if (LD->getType() != LI->getType()) {
1504         // If the stored value is larger or equal to the loaded value, we can
1505         // reuse it.
1506         if (!DL || !CanCoerceMustAliasedValueToLoad(LD, LI->getType(),*DL)) {
1507           UnavailableBlocks.push_back(DepBB);
1508           continue;
1509         }
1510       }
1511       ValuesPerBlock.push_back(AvailableValueInBlock::getLoad(DepBB, LD));
1512       continue;
1513     }
1514
1515     UnavailableBlocks.push_back(DepBB);
1516   }
1517 }
1518
1519 bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
1520                          UnavailBlkVect &UnavailableBlocks) {
1521   // Okay, we have *some* definitions of the value.  This means that the value
1522   // is available in some of our (transitive) predecessors.  Lets think about
1523   // doing PRE of this load.  This will involve inserting a new load into the
1524   // predecessor when it's not available.  We could do this in general, but
1525   // prefer to not increase code size.  As such, we only do this when we know
1526   // that we only have to insert *one* load (which means we're basically moving
1527   // the load, not inserting a new one).
1528
1529   SmallPtrSet<BasicBlock *, 4> Blockers;
1530   for (unsigned i = 0, e = UnavailableBlocks.size(); i != e; ++i)
1531     Blockers.insert(UnavailableBlocks[i]);
1532
1533   // Let's find the first basic block with more than one predecessor.  Walk
1534   // backwards through predecessors if needed.
1535   BasicBlock *LoadBB = LI->getParent();
1536   BasicBlock *TmpBB = LoadBB;
1537
1538   while (TmpBB->getSinglePredecessor()) {
1539     TmpBB = TmpBB->getSinglePredecessor();
1540     if (TmpBB == LoadBB) // Infinite (unreachable) loop.
1541       return false;
1542     if (Blockers.count(TmpBB))
1543       return false;
1544
1545     // If any of these blocks has more than one successor (i.e. if the edge we
1546     // just traversed was critical), then there are other paths through this
1547     // block along which the load may not be anticipated.  Hoisting the load
1548     // above this block would be adding the load to execution paths along
1549     // which it was not previously executed.
1550     if (TmpBB->getTerminator()->getNumSuccessors() != 1)
1551       return false;
1552   }
1553
1554   assert(TmpBB);
1555   LoadBB = TmpBB;
1556
1557   // Check to see how many predecessors have the loaded value fully
1558   // available.
1559   MapVector<BasicBlock *, Value *> PredLoads;
1560   DenseMap<BasicBlock*, char> FullyAvailableBlocks;
1561   for (unsigned i = 0, e = ValuesPerBlock.size(); i != e; ++i)
1562     FullyAvailableBlocks[ValuesPerBlock[i].BB] = true;
1563   for (unsigned i = 0, e = UnavailableBlocks.size(); i != e; ++i)
1564     FullyAvailableBlocks[UnavailableBlocks[i]] = false;
1565
1566   SmallVector<BasicBlock *, 4> CriticalEdgePred;
1567   for (pred_iterator PI = pred_begin(LoadBB), E = pred_end(LoadBB);
1568        PI != E; ++PI) {
1569     BasicBlock *Pred = *PI;
1570     if (IsValueFullyAvailableInBlock(Pred, FullyAvailableBlocks, 0)) {
1571       continue;
1572     }
1573
1574     if (Pred->getTerminator()->getNumSuccessors() != 1) {
1575       if (isa<IndirectBrInst>(Pred->getTerminator())) {
1576         DEBUG(dbgs() << "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"
1577               << Pred->getName() << "': " << *LI << '\n');
1578         return false;
1579       }
1580
1581       if (LoadBB->isLandingPad()) {
1582         DEBUG(dbgs()
1583               << "COULD NOT PRE LOAD BECAUSE OF LANDING PAD CRITICAL EDGE '"
1584               << Pred->getName() << "': " << *LI << '\n');
1585         return false;
1586       }
1587
1588       CriticalEdgePred.push_back(Pred);
1589     } else {
1590       // Only add the predecessors that will not be split for now.
1591       PredLoads[Pred] = nullptr;
1592     }
1593   }
1594
1595   // Decide whether PRE is profitable for this load.
1596   unsigned NumUnavailablePreds = PredLoads.size() + CriticalEdgePred.size();
1597   assert(NumUnavailablePreds != 0 &&
1598          "Fully available value should already be eliminated!");
1599
1600   // If this load is unavailable in multiple predecessors, reject it.
1601   // FIXME: If we could restructure the CFG, we could make a common pred with
1602   // all the preds that don't have an available LI and insert a new load into
1603   // that one block.
1604   if (NumUnavailablePreds != 1)
1605       return false;
1606
1607   // Split critical edges, and update the unavailable predecessors accordingly.
1608   for (BasicBlock *OrigPred : CriticalEdgePred) {
1609     BasicBlock *NewPred = splitCriticalEdges(OrigPred, LoadBB);
1610     assert(!PredLoads.count(OrigPred) && "Split edges shouldn't be in map!");
1611     PredLoads[NewPred] = nullptr;
1612     DEBUG(dbgs() << "Split critical edge " << OrigPred->getName() << "->"
1613                  << LoadBB->getName() << '\n');
1614   }
1615
1616   // Check if the load can safely be moved to all the unavailable predecessors.
1617   bool CanDoPRE = true;
1618   SmallVector<Instruction*, 8> NewInsts;
1619   for (auto &PredLoad : PredLoads) {
1620     BasicBlock *UnavailablePred = PredLoad.first;
1621
1622     // Do PHI translation to get its value in the predecessor if necessary.  The
1623     // returned pointer (if non-null) is guaranteed to dominate UnavailablePred.
1624
1625     // If all preds have a single successor, then we know it is safe to insert
1626     // the load on the pred (?!?), so we can insert code to materialize the
1627     // pointer if it is not available.
1628     PHITransAddr Address(LI->getPointerOperand(), DL, AC);
1629     Value *LoadPtr = nullptr;
1630     LoadPtr = Address.PHITranslateWithInsertion(LoadBB, UnavailablePred,
1631                                                 *DT, NewInsts);
1632
1633     // If we couldn't find or insert a computation of this phi translated value,
1634     // we fail PRE.
1635     if (!LoadPtr) {
1636       DEBUG(dbgs() << "COULDN'T INSERT PHI TRANSLATED VALUE OF: "
1637             << *LI->getPointerOperand() << "\n");
1638       CanDoPRE = false;
1639       break;
1640     }
1641
1642     PredLoad.second = LoadPtr;
1643   }
1644
1645   if (!CanDoPRE) {
1646     while (!NewInsts.empty()) {
1647       Instruction *I = NewInsts.pop_back_val();
1648       if (MD) MD->removeInstruction(I);
1649       I->eraseFromParent();
1650     }
1651     // HINT: Don't revert the edge-splitting as following transformation may
1652     // also need to split these critical edges.
1653     return !CriticalEdgePred.empty();
1654   }
1655
1656   // Okay, we can eliminate this load by inserting a reload in the predecessor
1657   // and using PHI construction to get the value in the other predecessors, do
1658   // it.
1659   DEBUG(dbgs() << "GVN REMOVING PRE LOAD: " << *LI << '\n');
1660   DEBUG(if (!NewInsts.empty())
1661           dbgs() << "INSERTED " << NewInsts.size() << " INSTS: "
1662                  << *NewInsts.back() << '\n');
1663
1664   // Assign value numbers to the new instructions.
1665   for (unsigned i = 0, e = NewInsts.size(); i != e; ++i) {
1666     // FIXME: We really _ought_ to insert these value numbers into their
1667     // parent's availability map.  However, in doing so, we risk getting into
1668     // ordering issues.  If a block hasn't been processed yet, we would be
1669     // marking a value as AVAIL-IN, which isn't what we intend.
1670     VN.lookup_or_add(NewInsts[i]);
1671   }
1672
1673   for (const auto &PredLoad : PredLoads) {
1674     BasicBlock *UnavailablePred = PredLoad.first;
1675     Value *LoadPtr = PredLoad.second;
1676
1677     Instruction *NewLoad = new LoadInst(LoadPtr, LI->getName()+".pre", false,
1678                                         LI->getAlignment(),
1679                                         UnavailablePred->getTerminator());
1680
1681     // Transfer the old load's AA tags to the new load.
1682     AAMDNodes Tags;
1683     LI->getAAMetadata(Tags);
1684     if (Tags)
1685       NewLoad->setAAMetadata(Tags);
1686
1687     // Transfer DebugLoc.
1688     NewLoad->setDebugLoc(LI->getDebugLoc());
1689
1690     // Add the newly created load.
1691     ValuesPerBlock.push_back(AvailableValueInBlock::get(UnavailablePred,
1692                                                         NewLoad));
1693     MD->invalidateCachedPointerInfo(LoadPtr);
1694     DEBUG(dbgs() << "GVN INSERTED " << *NewLoad << '\n');
1695   }
1696
1697   // Perform PHI construction.
1698   Value *V = ConstructSSAForLoadSet(LI, ValuesPerBlock, *this);
1699   LI->replaceAllUsesWith(V);
1700   if (isa<PHINode>(V))
1701     V->takeName(LI);
1702   if (V->getType()->getScalarType()->isPointerTy())
1703     MD->invalidateCachedPointerInfo(V);
1704   markInstructionForDeletion(LI);
1705   ++NumPRELoad;
1706   return true;
1707 }
1708
1709 /// processNonLocalLoad - Attempt to eliminate a load whose dependencies are
1710 /// non-local by performing PHI construction.
1711 bool GVN::processNonLocalLoad(LoadInst *LI) {
1712   // Step 1: Find the non-local dependencies of the load.
1713   LoadDepVect Deps;
1714   MD->getNonLocalPointerDependency(LI, Deps);
1715
1716   // If we had to process more than one hundred blocks to find the
1717   // dependencies, this load isn't worth worrying about.  Optimizing
1718   // it will be too expensive.
1719   unsigned NumDeps = Deps.size();
1720   if (NumDeps > 100)
1721     return false;
1722
1723   // If we had a phi translation failure, we'll have a single entry which is a
1724   // clobber in the current block.  Reject this early.
1725   if (NumDeps == 1 &&
1726       !Deps[0].getResult().isDef() && !Deps[0].getResult().isClobber()) {
1727     DEBUG(
1728       dbgs() << "GVN: non-local load ";
1729       LI->printAsOperand(dbgs());
1730       dbgs() << " has unknown dependencies\n";
1731     );
1732     return false;
1733   }
1734
1735   // If this load follows a GEP, see if we can PRE the indices before analyzing.
1736   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0))) {
1737     for (GetElementPtrInst::op_iterator OI = GEP->idx_begin(),
1738                                         OE = GEP->idx_end();
1739          OI != OE; ++OI)
1740       if (Instruction *I = dyn_cast<Instruction>(OI->get()))
1741         performScalarPRE(I);
1742   }
1743
1744   // Step 2: Analyze the availability of the load
1745   AvailValInBlkVect ValuesPerBlock;
1746   UnavailBlkVect UnavailableBlocks;
1747   AnalyzeLoadAvailability(LI, Deps, ValuesPerBlock, UnavailableBlocks);
1748
1749   // If we have no predecessors that produce a known value for this load, exit
1750   // early.
1751   if (ValuesPerBlock.empty())
1752     return false;
1753
1754   // Step 3: Eliminate fully redundancy.
1755   //
1756   // If all of the instructions we depend on produce a known value for this
1757   // load, then it is fully redundant and we can use PHI insertion to compute
1758   // its value.  Insert PHIs and remove the fully redundant value now.
1759   if (UnavailableBlocks.empty()) {
1760     DEBUG(dbgs() << "GVN REMOVING NONLOCAL LOAD: " << *LI << '\n');
1761
1762     // Perform PHI construction.
1763     Value *V = ConstructSSAForLoadSet(LI, ValuesPerBlock, *this);
1764     LI->replaceAllUsesWith(V);
1765
1766     if (isa<PHINode>(V))
1767       V->takeName(LI);
1768     if (V->getType()->getScalarType()->isPointerTy())
1769       MD->invalidateCachedPointerInfo(V);
1770     markInstructionForDeletion(LI);
1771     ++NumGVNLoad;
1772     return true;
1773   }
1774
1775   // Step 4: Eliminate partial redundancy.
1776   if (!EnablePRE || !EnableLoadPRE)
1777     return false;
1778
1779   return PerformLoadPRE(LI, ValuesPerBlock, UnavailableBlocks);
1780 }
1781
1782
1783 static void patchReplacementInstruction(Instruction *I, Value *Repl) {
1784   // Patch the replacement so that it is not more restrictive than the value
1785   // being replaced.
1786   BinaryOperator *Op = dyn_cast<BinaryOperator>(I);
1787   BinaryOperator *ReplOp = dyn_cast<BinaryOperator>(Repl);
1788   if (Op && ReplOp && isa<OverflowingBinaryOperator>(Op) &&
1789       isa<OverflowingBinaryOperator>(ReplOp)) {
1790     if (ReplOp->hasNoSignedWrap() && !Op->hasNoSignedWrap())
1791       ReplOp->setHasNoSignedWrap(false);
1792     if (ReplOp->hasNoUnsignedWrap() && !Op->hasNoUnsignedWrap())
1793       ReplOp->setHasNoUnsignedWrap(false);
1794   }
1795   if (Instruction *ReplInst = dyn_cast<Instruction>(Repl)) {
1796     // FIXME: If both the original and replacement value are part of the
1797     // same control-flow region (meaning that the execution of one
1798     // guarentees the executation of the other), then we can combine the
1799     // noalias scopes here and do better than the general conservative
1800     // answer used in combineMetadata().
1801
1802     // In general, GVN unifies expressions over different control-flow
1803     // regions, and so we need a conservative combination of the noalias
1804     // scopes.
1805     unsigned KnownIDs[] = {
1806       LLVMContext::MD_tbaa,
1807       LLVMContext::MD_alias_scope,
1808       LLVMContext::MD_noalias,
1809       LLVMContext::MD_range,
1810       LLVMContext::MD_fpmath,
1811       LLVMContext::MD_invariant_load,
1812     };
1813     combineMetadata(ReplInst, I, KnownIDs);
1814   }
1815 }
1816
1817 static void patchAndReplaceAllUsesWith(Instruction *I, Value *Repl) {
1818   patchReplacementInstruction(I, Repl);
1819   I->replaceAllUsesWith(Repl);
1820 }
1821
1822 /// processLoad - Attempt to eliminate a load, first by eliminating it
1823 /// locally, and then attempting non-local elimination if that fails.
1824 bool GVN::processLoad(LoadInst *L) {
1825   if (!MD)
1826     return false;
1827
1828   if (!L->isSimple())
1829     return false;
1830
1831   if (L->use_empty()) {
1832     markInstructionForDeletion(L);
1833     return true;
1834   }
1835
1836   // ... to a pointer that has been loaded from before...
1837   MemDepResult Dep = MD->getDependency(L);
1838
1839   // If we have a clobber and target data is around, see if this is a clobber
1840   // that we can fix up through code synthesis.
1841   if (Dep.isClobber() && DL) {
1842     // Check to see if we have something like this:
1843     //   store i32 123, i32* %P
1844     //   %A = bitcast i32* %P to i8*
1845     //   %B = gep i8* %A, i32 1
1846     //   %C = load i8* %B
1847     //
1848     // We could do that by recognizing if the clobber instructions are obviously
1849     // a common base + constant offset, and if the previous store (or memset)
1850     // completely covers this load.  This sort of thing can happen in bitfield
1851     // access code.
1852     Value *AvailVal = nullptr;
1853     if (StoreInst *DepSI = dyn_cast<StoreInst>(Dep.getInst())) {
1854       int Offset = AnalyzeLoadFromClobberingStore(L->getType(),
1855                                                   L->getPointerOperand(),
1856                                                   DepSI, *DL);
1857       if (Offset != -1)
1858         AvailVal = GetStoreValueForLoad(DepSI->getValueOperand(), Offset,
1859                                         L->getType(), L, *DL);
1860     }
1861
1862     // Check to see if we have something like this:
1863     //    load i32* P
1864     //    load i8* (P+1)
1865     // if we have this, replace the later with an extraction from the former.
1866     if (LoadInst *DepLI = dyn_cast<LoadInst>(Dep.getInst())) {
1867       // If this is a clobber and L is the first instruction in its block, then
1868       // we have the first instruction in the entry block.
1869       if (DepLI == L)
1870         return false;
1871
1872       int Offset = AnalyzeLoadFromClobberingLoad(L->getType(),
1873                                                  L->getPointerOperand(),
1874                                                  DepLI, *DL);
1875       if (Offset != -1)
1876         AvailVal = GetLoadValueForLoad(DepLI, Offset, L->getType(), L, *this);
1877     }
1878
1879     // If the clobbering value is a memset/memcpy/memmove, see if we can forward
1880     // a value on from it.
1881     if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(Dep.getInst())) {
1882       int Offset = AnalyzeLoadFromClobberingMemInst(L->getType(),
1883                                                     L->getPointerOperand(),
1884                                                     DepMI, *DL);
1885       if (Offset != -1)
1886         AvailVal = GetMemInstValueForLoad(DepMI, Offset, L->getType(), L, *DL);
1887     }
1888
1889     if (AvailVal) {
1890       DEBUG(dbgs() << "GVN COERCED INST:\n" << *Dep.getInst() << '\n'
1891             << *AvailVal << '\n' << *L << "\n\n\n");
1892
1893       // Replace the load!
1894       L->replaceAllUsesWith(AvailVal);
1895       if (AvailVal->getType()->getScalarType()->isPointerTy())
1896         MD->invalidateCachedPointerInfo(AvailVal);
1897       markInstructionForDeletion(L);
1898       ++NumGVNLoad;
1899       return true;
1900     }
1901   }
1902
1903   // If the value isn't available, don't do anything!
1904   if (Dep.isClobber()) {
1905     DEBUG(
1906       // fast print dep, using operator<< on instruction is too slow.
1907       dbgs() << "GVN: load ";
1908       L->printAsOperand(dbgs());
1909       Instruction *I = Dep.getInst();
1910       dbgs() << " is clobbered by " << *I << '\n';
1911     );
1912     return false;
1913   }
1914
1915   // If it is defined in another block, try harder.
1916   if (Dep.isNonLocal())
1917     return processNonLocalLoad(L);
1918
1919   if (!Dep.isDef()) {
1920     DEBUG(
1921       // fast print dep, using operator<< on instruction is too slow.
1922       dbgs() << "GVN: load ";
1923       L->printAsOperand(dbgs());
1924       dbgs() << " has unknown dependence\n";
1925     );
1926     return false;
1927   }
1928
1929   Instruction *DepInst = Dep.getInst();
1930   if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) {
1931     Value *StoredVal = DepSI->getValueOperand();
1932
1933     // The store and load are to a must-aliased pointer, but they may not
1934     // actually have the same type.  See if we know how to reuse the stored
1935     // value (depending on its type).
1936     if (StoredVal->getType() != L->getType()) {
1937       if (DL) {
1938         StoredVal = CoerceAvailableValueToLoadType(StoredVal, L->getType(),
1939                                                    L, *DL);
1940         if (!StoredVal)
1941           return false;
1942
1943         DEBUG(dbgs() << "GVN COERCED STORE:\n" << *DepSI << '\n' << *StoredVal
1944                      << '\n' << *L << "\n\n\n");
1945       }
1946       else
1947         return false;
1948     }
1949
1950     // Remove it!
1951     L->replaceAllUsesWith(StoredVal);
1952     if (StoredVal->getType()->getScalarType()->isPointerTy())
1953       MD->invalidateCachedPointerInfo(StoredVal);
1954     markInstructionForDeletion(L);
1955     ++NumGVNLoad;
1956     return true;
1957   }
1958
1959   if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInst)) {
1960     Value *AvailableVal = DepLI;
1961
1962     // The loads are of a must-aliased pointer, but they may not actually have
1963     // the same type.  See if we know how to reuse the previously loaded value
1964     // (depending on its type).
1965     if (DepLI->getType() != L->getType()) {
1966       if (DL) {
1967         AvailableVal = CoerceAvailableValueToLoadType(DepLI, L->getType(),
1968                                                       L, *DL);
1969         if (!AvailableVal)
1970           return false;
1971
1972         DEBUG(dbgs() << "GVN COERCED LOAD:\n" << *DepLI << "\n" << *AvailableVal
1973                      << "\n" << *L << "\n\n\n");
1974       }
1975       else
1976         return false;
1977     }
1978
1979     // Remove it!
1980     patchAndReplaceAllUsesWith(L, AvailableVal);
1981     if (DepLI->getType()->getScalarType()->isPointerTy())
1982       MD->invalidateCachedPointerInfo(DepLI);
1983     markInstructionForDeletion(L);
1984     ++NumGVNLoad;
1985     return true;
1986   }
1987
1988   // If this load really doesn't depend on anything, then we must be loading an
1989   // undef value.  This can happen when loading for a fresh allocation with no
1990   // intervening stores, for example.
1991   if (isa<AllocaInst>(DepInst) || isMallocLikeFn(DepInst, TLI)) {
1992     L->replaceAllUsesWith(UndefValue::get(L->getType()));
1993     markInstructionForDeletion(L);
1994     ++NumGVNLoad;
1995     return true;
1996   }
1997
1998   // If this load occurs either right after a lifetime begin,
1999   // then the loaded value is undefined.
2000   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(DepInst)) {
2001     if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
2002       L->replaceAllUsesWith(UndefValue::get(L->getType()));
2003       markInstructionForDeletion(L);
2004       ++NumGVNLoad;
2005       return true;
2006     }
2007   }
2008
2009   // If this load follows a calloc (which zero initializes memory),
2010   // then the loaded value is zero
2011   if (isCallocLikeFn(DepInst, TLI)) {
2012     L->replaceAllUsesWith(Constant::getNullValue(L->getType()));
2013     markInstructionForDeletion(L);
2014     ++NumGVNLoad;
2015     return true;
2016   }
2017
2018   return false;
2019 }
2020
2021 // findLeader - In order to find a leader for a given value number at a
2022 // specific basic block, we first obtain the list of all Values for that number,
2023 // and then scan the list to find one whose block dominates the block in
2024 // question.  This is fast because dominator tree queries consist of only
2025 // a few comparisons of DFS numbers.
2026 Value *GVN::findLeader(const BasicBlock *BB, uint32_t num) {
2027   LeaderTableEntry Vals = LeaderTable[num];
2028   if (!Vals.Val) return nullptr;
2029
2030   Value *Val = nullptr;
2031   if (DT->dominates(Vals.BB, BB)) {
2032     Val = Vals.Val;
2033     if (isa<Constant>(Val)) return Val;
2034   }
2035
2036   LeaderTableEntry* Next = Vals.Next;
2037   while (Next) {
2038     if (DT->dominates(Next->BB, BB)) {
2039       if (isa<Constant>(Next->Val)) return Next->Val;
2040       if (!Val) Val = Next->Val;
2041     }
2042
2043     Next = Next->Next;
2044   }
2045
2046   return Val;
2047 }
2048
2049 /// replaceAllDominatedUsesWith - Replace all uses of 'From' with 'To' if the
2050 /// use is dominated by the given basic block.  Returns the number of uses that
2051 /// were replaced.
2052 unsigned GVN::replaceAllDominatedUsesWith(Value *From, Value *To,
2053                                           const BasicBlockEdge &Root) {
2054   unsigned Count = 0;
2055   for (Value::use_iterator UI = From->use_begin(), UE = From->use_end();
2056        UI != UE; ) {
2057     Use &U = *UI++;
2058
2059     if (DT->dominates(Root, U)) {
2060       U.set(To);
2061       ++Count;
2062     }
2063   }
2064   return Count;
2065 }
2066
2067 /// isOnlyReachableViaThisEdge - There is an edge from 'Src' to 'Dst'.  Return
2068 /// true if every path from the entry block to 'Dst' passes via this edge.  In
2069 /// particular 'Dst' must not be reachable via another edge from 'Src'.
2070 static bool isOnlyReachableViaThisEdge(const BasicBlockEdge &E,
2071                                        DominatorTree *DT) {
2072   // While in theory it is interesting to consider the case in which Dst has
2073   // more than one predecessor, because Dst might be part of a loop which is
2074   // only reachable from Src, in practice it is pointless since at the time
2075   // GVN runs all such loops have preheaders, which means that Dst will have
2076   // been changed to have only one predecessor, namely Src.
2077   const BasicBlock *Pred = E.getEnd()->getSinglePredecessor();
2078   const BasicBlock *Src = E.getStart();
2079   assert((!Pred || Pred == Src) && "No edge between these basic blocks!");
2080   (void)Src;
2081   return Pred != nullptr;
2082 }
2083
2084 /// propagateEquality - The given values are known to be equal in every block
2085 /// dominated by 'Root'.  Exploit this, for example by replacing 'LHS' with
2086 /// 'RHS' everywhere in the scope.  Returns whether a change was made.
2087 bool GVN::propagateEquality(Value *LHS, Value *RHS,
2088                             const BasicBlockEdge &Root) {
2089   SmallVector<std::pair<Value*, Value*>, 4> Worklist;
2090   Worklist.push_back(std::make_pair(LHS, RHS));
2091   bool Changed = false;
2092   // For speed, compute a conservative fast approximation to
2093   // DT->dominates(Root, Root.getEnd());
2094   bool RootDominatesEnd = isOnlyReachableViaThisEdge(Root, DT);
2095
2096   while (!Worklist.empty()) {
2097     std::pair<Value*, Value*> Item = Worklist.pop_back_val();
2098     LHS = Item.first; RHS = Item.second;
2099
2100     if (LHS == RHS) continue;
2101     assert(LHS->getType() == RHS->getType() && "Equality but unequal types!");
2102
2103     // Don't try to propagate equalities between constants.
2104     if (isa<Constant>(LHS) && isa<Constant>(RHS)) continue;
2105
2106     // Prefer a constant on the right-hand side, or an Argument if no constants.
2107     if (isa<Constant>(LHS) || (isa<Argument>(LHS) && !isa<Constant>(RHS)))
2108       std::swap(LHS, RHS);
2109     assert((isa<Argument>(LHS) || isa<Instruction>(LHS)) && "Unexpected value!");
2110
2111     // If there is no obvious reason to prefer the left-hand side over the
2112     // right-hand side, ensure the longest lived term is on the right-hand side,
2113     // so the shortest lived term will be replaced by the longest lived.
2114     // This tends to expose more simplifications.
2115     uint32_t LVN = VN.lookup_or_add(LHS);
2116     if ((isa<Argument>(LHS) && isa<Argument>(RHS)) ||
2117         (isa<Instruction>(LHS) && isa<Instruction>(RHS))) {
2118       // Move the 'oldest' value to the right-hand side, using the value number
2119       // as a proxy for age.
2120       uint32_t RVN = VN.lookup_or_add(RHS);
2121       if (LVN < RVN) {
2122         std::swap(LHS, RHS);
2123         LVN = RVN;
2124       }
2125     }
2126
2127     // If value numbering later sees that an instruction in the scope is equal
2128     // to 'LHS' then ensure it will be turned into 'RHS'.  In order to preserve
2129     // the invariant that instructions only occur in the leader table for their
2130     // own value number (this is used by removeFromLeaderTable), do not do this
2131     // if RHS is an instruction (if an instruction in the scope is morphed into
2132     // LHS then it will be turned into RHS by the next GVN iteration anyway, so
2133     // using the leader table is about compiling faster, not optimizing better).
2134     // The leader table only tracks basic blocks, not edges. Only add to if we
2135     // have the simple case where the edge dominates the end.
2136     if (RootDominatesEnd && !isa<Instruction>(RHS))
2137       addToLeaderTable(LVN, RHS, Root.getEnd());
2138
2139     // Replace all occurrences of 'LHS' with 'RHS' everywhere in the scope.  As
2140     // LHS always has at least one use that is not dominated by Root, this will
2141     // never do anything if LHS has only one use.
2142     if (!LHS->hasOneUse()) {
2143       unsigned NumReplacements = replaceAllDominatedUsesWith(LHS, RHS, Root);
2144       Changed |= NumReplacements > 0;
2145       NumGVNEqProp += NumReplacements;
2146     }
2147
2148     // Now try to deduce additional equalities from this one. For example, if
2149     // the known equality was "(A != B)" == "false" then it follows that A and B
2150     // are equal in the scope. Only boolean equalities with an explicit true or
2151     // false RHS are currently supported.
2152     if (!RHS->getType()->isIntegerTy(1))
2153       // Not a boolean equality - bail out.
2154       continue;
2155     ConstantInt *CI = dyn_cast<ConstantInt>(RHS);
2156     if (!CI)
2157       // RHS neither 'true' nor 'false' - bail out.
2158       continue;
2159     // Whether RHS equals 'true'.  Otherwise it equals 'false'.
2160     bool isKnownTrue = CI->isAllOnesValue();
2161     bool isKnownFalse = !isKnownTrue;
2162
2163     // If "A && B" is known true then both A and B are known true.  If "A || B"
2164     // is known false then both A and B are known false.
2165     Value *A, *B;
2166     if ((isKnownTrue && match(LHS, m_And(m_Value(A), m_Value(B)))) ||
2167         (isKnownFalse && match(LHS, m_Or(m_Value(A), m_Value(B))))) {
2168       Worklist.push_back(std::make_pair(A, RHS));
2169       Worklist.push_back(std::make_pair(B, RHS));
2170       continue;
2171     }
2172
2173     // If we are propagating an equality like "(A == B)" == "true" then also
2174     // propagate the equality A == B.  When propagating a comparison such as
2175     // "(A >= B)" == "true", replace all instances of "A < B" with "false".
2176     if (CmpInst *Cmp = dyn_cast<CmpInst>(LHS)) {
2177       Value *Op0 = Cmp->getOperand(0), *Op1 = Cmp->getOperand(1);
2178
2179       // If "A == B" is known true, or "A != B" is known false, then replace
2180       // A with B everywhere in the scope.
2181       if ((isKnownTrue && Cmp->getPredicate() == CmpInst::ICMP_EQ) ||
2182           (isKnownFalse && Cmp->getPredicate() == CmpInst::ICMP_NE))
2183         Worklist.push_back(std::make_pair(Op0, Op1));
2184
2185       // Handle the floating point versions of equality comparisons too.
2186       if ((isKnownTrue && Cmp->getPredicate() == CmpInst::FCMP_OEQ) ||
2187           (isKnownFalse && Cmp->getPredicate() == CmpInst::FCMP_UNE)) {
2188         // Floating point -0.0 and 0.0 compare equal, so we can't
2189         // propagate a constant based on that comparison.
2190         // FIXME: We should do this optimization if 'no signed zeros' is
2191         // applicable via an instruction-level fast-math-flag or some other
2192         // indicator that relaxed FP semantics are being used.
2193         if (!isa<ConstantFP>(Op1) || !cast<ConstantFP>(Op1)->isZero())
2194           Worklist.push_back(std::make_pair(Op0, Op1));
2195       }
2196
2197       // If "A >= B" is known true, replace "A < B" with false everywhere.
2198       CmpInst::Predicate NotPred = Cmp->getInversePredicate();
2199       Constant *NotVal = ConstantInt::get(Cmp->getType(), isKnownFalse);
2200       // Since we don't have the instruction "A < B" immediately to hand, work
2201       // out the value number that it would have and use that to find an
2202       // appropriate instruction (if any).
2203       uint32_t NextNum = VN.getNextUnusedValueNumber();
2204       uint32_t Num = VN.lookup_or_add_cmp(Cmp->getOpcode(), NotPred, Op0, Op1);
2205       // If the number we were assigned was brand new then there is no point in
2206       // looking for an instruction realizing it: there cannot be one!
2207       if (Num < NextNum) {
2208         Value *NotCmp = findLeader(Root.getEnd(), Num);
2209         if (NotCmp && isa<Instruction>(NotCmp)) {
2210           unsigned NumReplacements =
2211             replaceAllDominatedUsesWith(NotCmp, NotVal, Root);
2212           Changed |= NumReplacements > 0;
2213           NumGVNEqProp += NumReplacements;
2214         }
2215       }
2216       // Ensure that any instruction in scope that gets the "A < B" value number
2217       // is replaced with false.
2218       // The leader table only tracks basic blocks, not edges. Only add to if we
2219       // have the simple case where the edge dominates the end.
2220       if (RootDominatesEnd)
2221         addToLeaderTable(Num, NotVal, Root.getEnd());
2222
2223       continue;
2224     }
2225   }
2226
2227   return Changed;
2228 }
2229
2230 /// processInstruction - When calculating availability, handle an instruction
2231 /// by inserting it into the appropriate sets
2232 bool GVN::processInstruction(Instruction *I) {
2233   // Ignore dbg info intrinsics.
2234   if (isa<DbgInfoIntrinsic>(I))
2235     return false;
2236
2237   // If the instruction can be easily simplified then do so now in preference
2238   // to value numbering it.  Value numbering often exposes redundancies, for
2239   // example if it determines that %y is equal to %x then the instruction
2240   // "%z = and i32 %x, %y" becomes "%z = and i32 %x, %x" which we now simplify.
2241   if (Value *V = SimplifyInstruction(I, DL, TLI, DT, AC)) {
2242     I->replaceAllUsesWith(V);
2243     if (MD && V->getType()->getScalarType()->isPointerTy())
2244       MD->invalidateCachedPointerInfo(V);
2245     markInstructionForDeletion(I);
2246     ++NumGVNSimpl;
2247     return true;
2248   }
2249
2250   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
2251     if (processLoad(LI))
2252       return true;
2253
2254     unsigned Num = VN.lookup_or_add(LI);
2255     addToLeaderTable(Num, LI, LI->getParent());
2256     return false;
2257   }
2258
2259   // For conditional branches, we can perform simple conditional propagation on
2260   // the condition value itself.
2261   if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
2262     if (!BI->isConditional())
2263       return false;
2264
2265     if (isa<Constant>(BI->getCondition()))
2266       return processFoldableCondBr(BI);
2267
2268     Value *BranchCond = BI->getCondition();
2269     BasicBlock *TrueSucc = BI->getSuccessor(0);
2270     BasicBlock *FalseSucc = BI->getSuccessor(1);
2271     // Avoid multiple edges early.
2272     if (TrueSucc == FalseSucc)
2273       return false;
2274
2275     BasicBlock *Parent = BI->getParent();
2276     bool Changed = false;
2277
2278     Value *TrueVal = ConstantInt::getTrue(TrueSucc->getContext());
2279     BasicBlockEdge TrueE(Parent, TrueSucc);
2280     Changed |= propagateEquality(BranchCond, TrueVal, TrueE);
2281
2282     Value *FalseVal = ConstantInt::getFalse(FalseSucc->getContext());
2283     BasicBlockEdge FalseE(Parent, FalseSucc);
2284     Changed |= propagateEquality(BranchCond, FalseVal, FalseE);
2285
2286     return Changed;
2287   }
2288
2289   // For switches, propagate the case values into the case destinations.
2290   if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
2291     Value *SwitchCond = SI->getCondition();
2292     BasicBlock *Parent = SI->getParent();
2293     bool Changed = false;
2294
2295     // Remember how many outgoing edges there are to every successor.
2296     SmallDenseMap<BasicBlock *, unsigned, 16> SwitchEdges;
2297     for (unsigned i = 0, n = SI->getNumSuccessors(); i != n; ++i)
2298       ++SwitchEdges[SI->getSuccessor(i)];
2299
2300     for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
2301          i != e; ++i) {
2302       BasicBlock *Dst = i.getCaseSuccessor();
2303       // If there is only a single edge, propagate the case value into it.
2304       if (SwitchEdges.lookup(Dst) == 1) {
2305         BasicBlockEdge E(Parent, Dst);
2306         Changed |= propagateEquality(SwitchCond, i.getCaseValue(), E);
2307       }
2308     }
2309     return Changed;
2310   }
2311
2312   // Instructions with void type don't return a value, so there's
2313   // no point in trying to find redundancies in them.
2314   if (I->getType()->isVoidTy()) return false;
2315
2316   uint32_t NextNum = VN.getNextUnusedValueNumber();
2317   unsigned Num = VN.lookup_or_add(I);
2318
2319   // Allocations are always uniquely numbered, so we can save time and memory
2320   // by fast failing them.
2321   if (isa<AllocaInst>(I) || isa<TerminatorInst>(I) || isa<PHINode>(I)) {
2322     addToLeaderTable(Num, I, I->getParent());
2323     return false;
2324   }
2325
2326   // If the number we were assigned was a brand new VN, then we don't
2327   // need to do a lookup to see if the number already exists
2328   // somewhere in the domtree: it can't!
2329   if (Num >= NextNum) {
2330     addToLeaderTable(Num, I, I->getParent());
2331     return false;
2332   }
2333
2334   // Perform fast-path value-number based elimination of values inherited from
2335   // dominators.
2336   Value *repl = findLeader(I->getParent(), Num);
2337   if (!repl) {
2338     // Failure, just remember this instance for future use.
2339     addToLeaderTable(Num, I, I->getParent());
2340     return false;
2341   }
2342
2343   // Remove it!
2344   patchAndReplaceAllUsesWith(I, repl);
2345   if (MD && repl->getType()->getScalarType()->isPointerTy())
2346     MD->invalidateCachedPointerInfo(repl);
2347   markInstructionForDeletion(I);
2348   return true;
2349 }
2350
2351 /// runOnFunction - This is the main transformation entry point for a function.
2352 bool GVN::runOnFunction(Function& F) {
2353   if (skipOptnoneFunction(F))
2354     return false;
2355
2356   if (!NoLoads)
2357     MD = &getAnalysis<MemoryDependenceAnalysis>();
2358   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2359   DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
2360   DL = DLP ? &DLP->getDataLayout() : nullptr;
2361   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
2362   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
2363   VN.setAliasAnalysis(&getAnalysis<AliasAnalysis>());
2364   VN.setMemDep(MD);
2365   VN.setDomTree(DT);
2366
2367   bool Changed = false;
2368   bool ShouldContinue = true;
2369
2370   // Merge unconditional branches, allowing PRE to catch more
2371   // optimization opportunities.
2372   for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ) {
2373     BasicBlock *BB = FI++;
2374
2375     bool removedBlock = MergeBlockIntoPredecessor(
2376         BB, DT, /* LoopInfo */ nullptr, VN.getAliasAnalysis(), MD);
2377     if (removedBlock) ++NumGVNBlocks;
2378
2379     Changed |= removedBlock;
2380   }
2381
2382   unsigned Iteration = 0;
2383   while (ShouldContinue) {
2384     DEBUG(dbgs() << "GVN iteration: " << Iteration << "\n");
2385     ShouldContinue = iterateOnFunction(F);
2386     Changed |= ShouldContinue;
2387     ++Iteration;
2388   }
2389
2390   if (EnablePRE) {
2391     // Fabricate val-num for dead-code in order to suppress assertion in
2392     // performPRE().
2393     assignValNumForDeadCode();
2394     bool PREChanged = true;
2395     while (PREChanged) {
2396       PREChanged = performPRE(F);
2397       Changed |= PREChanged;
2398     }
2399   }
2400
2401   // FIXME: Should perform GVN again after PRE does something.  PRE can move
2402   // computations into blocks where they become fully redundant.  Note that
2403   // we can't do this until PRE's critical edge splitting updates memdep.
2404   // Actually, when this happens, we should just fully integrate PRE into GVN.
2405
2406   cleanupGlobalSets();
2407   // Do not cleanup DeadBlocks in cleanupGlobalSets() as it's called for each
2408   // iteration.
2409   DeadBlocks.clear();
2410
2411   return Changed;
2412 }
2413
2414
2415 bool GVN::processBlock(BasicBlock *BB) {
2416   // FIXME: Kill off InstrsToErase by doing erasing eagerly in a helper function
2417   // (and incrementing BI before processing an instruction).
2418   assert(InstrsToErase.empty() &&
2419          "We expect InstrsToErase to be empty across iterations");
2420   if (DeadBlocks.count(BB))
2421     return false;
2422
2423   bool ChangedFunction = false;
2424
2425   for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
2426        BI != BE;) {
2427     ChangedFunction |= processInstruction(BI);
2428     if (InstrsToErase.empty()) {
2429       ++BI;
2430       continue;
2431     }
2432
2433     // If we need some instructions deleted, do it now.
2434     NumGVNInstr += InstrsToErase.size();
2435
2436     // Avoid iterator invalidation.
2437     bool AtStart = BI == BB->begin();
2438     if (!AtStart)
2439       --BI;
2440
2441     for (SmallVectorImpl<Instruction *>::iterator I = InstrsToErase.begin(),
2442          E = InstrsToErase.end(); I != E; ++I) {
2443       DEBUG(dbgs() << "GVN removed: " << **I << '\n');
2444       if (MD) MD->removeInstruction(*I);
2445       DEBUG(verifyRemoved(*I));
2446       (*I)->eraseFromParent();
2447     }
2448     InstrsToErase.clear();
2449
2450     if (AtStart)
2451       BI = BB->begin();
2452     else
2453       ++BI;
2454   }
2455
2456   return ChangedFunction;
2457 }
2458
2459 // Instantiate an expression in a predecessor that lacked it.
2460 bool GVN::performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
2461                                     unsigned int ValNo) {
2462   // Because we are going top-down through the block, all value numbers
2463   // will be available in the predecessor by the time we need them.  Any
2464   // that weren't originally present will have been instantiated earlier
2465   // in this loop.
2466   bool success = true;
2467   for (unsigned i = 0, e = Instr->getNumOperands(); i != e; ++i) {
2468     Value *Op = Instr->getOperand(i);
2469     if (isa<Argument>(Op) || isa<Constant>(Op) || isa<GlobalValue>(Op))
2470       continue;
2471
2472     if (Value *V = findLeader(Pred, VN.lookup(Op))) {
2473       Instr->setOperand(i, V);
2474     } else {
2475       success = false;
2476       break;
2477     }
2478   }
2479
2480   // Fail out if we encounter an operand that is not available in
2481   // the PRE predecessor.  This is typically because of loads which
2482   // are not value numbered precisely.
2483   if (!success)
2484     return false;
2485
2486   Instr->insertBefore(Pred->getTerminator());
2487   Instr->setName(Instr->getName() + ".pre");
2488   Instr->setDebugLoc(Instr->getDebugLoc());
2489   VN.add(Instr, ValNo);
2490
2491   // Update the availability map to include the new instruction.
2492   addToLeaderTable(ValNo, Instr, Pred);
2493   return true;
2494 }
2495
2496 bool GVN::performScalarPRE(Instruction *CurInst) {
2497   SmallVector<std::pair<Value*, BasicBlock*>, 8> predMap;
2498
2499   if (isa<AllocaInst>(CurInst) || isa<TerminatorInst>(CurInst) ||
2500       isa<PHINode>(CurInst) || CurInst->getType()->isVoidTy() ||
2501       CurInst->mayReadFromMemory() || CurInst->mayHaveSideEffects() ||
2502       isa<DbgInfoIntrinsic>(CurInst))
2503     return false;
2504
2505   // Don't do PRE on compares. The PHI would prevent CodeGenPrepare from
2506   // sinking the compare again, and it would force the code generator to
2507   // move the i1 from processor flags or predicate registers into a general
2508   // purpose register.
2509   if (isa<CmpInst>(CurInst))
2510     return false;
2511
2512   // We don't currently value number ANY inline asm calls.
2513   if (CallInst *CallI = dyn_cast<CallInst>(CurInst))
2514     if (CallI->isInlineAsm())
2515       return false;
2516
2517   uint32_t ValNo = VN.lookup(CurInst);
2518
2519   // Look for the predecessors for PRE opportunities.  We're
2520   // only trying to solve the basic diamond case, where
2521   // a value is computed in the successor and one predecessor,
2522   // but not the other.  We also explicitly disallow cases
2523   // where the successor is its own predecessor, because they're
2524   // more complicated to get right.
2525   unsigned NumWith = 0;
2526   unsigned NumWithout = 0;
2527   BasicBlock *PREPred = nullptr;
2528   BasicBlock *CurrentBlock = CurInst->getParent();
2529   predMap.clear();
2530
2531   for (pred_iterator PI = pred_begin(CurrentBlock), PE = pred_end(CurrentBlock);
2532        PI != PE; ++PI) {
2533     BasicBlock *P = *PI;
2534     // We're not interested in PRE where the block is its
2535     // own predecessor, or in blocks with predecessors
2536     // that are not reachable.
2537     if (P == CurrentBlock) {
2538       NumWithout = 2;
2539       break;
2540     } else if (!DT->isReachableFromEntry(P)) {
2541       NumWithout = 2;
2542       break;
2543     }
2544
2545     Value *predV = findLeader(P, ValNo);
2546     if (!predV) {
2547       predMap.push_back(std::make_pair(static_cast<Value *>(nullptr), P));
2548       PREPred = P;
2549       ++NumWithout;
2550     } else if (predV == CurInst) {
2551       /* CurInst dominates this predecessor. */
2552       NumWithout = 2;
2553       break;
2554     } else {
2555       predMap.push_back(std::make_pair(predV, P));
2556       ++NumWith;
2557     }
2558   }
2559
2560   // Don't do PRE when it might increase code size, i.e. when
2561   // we would need to insert instructions in more than one pred.
2562   if (NumWithout > 1 || NumWith == 0)
2563     return false;
2564
2565   // We may have a case where all predecessors have the instruction,
2566   // and we just need to insert a phi node. Otherwise, perform
2567   // insertion.
2568   Instruction *PREInstr = nullptr;
2569
2570   if (NumWithout != 0) {
2571     // Don't do PRE across indirect branch.
2572     if (isa<IndirectBrInst>(PREPred->getTerminator()))
2573       return false;
2574
2575     // We can't do PRE safely on a critical edge, so instead we schedule
2576     // the edge to be split and perform the PRE the next time we iterate
2577     // on the function.
2578     unsigned SuccNum = GetSuccessorNumber(PREPred, CurrentBlock);
2579     if (isCriticalEdge(PREPred->getTerminator(), SuccNum)) {
2580       toSplit.push_back(std::make_pair(PREPred->getTerminator(), SuccNum));
2581       return false;
2582     }
2583     // We need to insert somewhere, so let's give it a shot
2584     PREInstr = CurInst->clone();
2585     if (!performScalarPREInsertion(PREInstr, PREPred, ValNo)) {
2586       // If we failed insertion, make sure we remove the instruction.
2587       DEBUG(verifyRemoved(PREInstr));
2588       delete PREInstr;
2589       return false;
2590     }
2591   }
2592
2593   // Either we should have filled in the PRE instruction, or we should
2594   // not have needed insertions.
2595   assert (PREInstr != nullptr || NumWithout == 0);
2596
2597   ++NumGVNPRE;
2598
2599   // Create a PHI to make the value available in this block.
2600   PHINode *Phi =
2601       PHINode::Create(CurInst->getType(), predMap.size(),
2602                       CurInst->getName() + ".pre-phi", CurrentBlock->begin());
2603   for (unsigned i = 0, e = predMap.size(); i != e; ++i) {
2604     if (Value *V = predMap[i].first)
2605       Phi->addIncoming(V, predMap[i].second);
2606     else
2607       Phi->addIncoming(PREInstr, PREPred);
2608   }
2609
2610   VN.add(Phi, ValNo);
2611   addToLeaderTable(ValNo, Phi, CurrentBlock);
2612   Phi->setDebugLoc(CurInst->getDebugLoc());
2613   CurInst->replaceAllUsesWith(Phi);
2614   if (Phi->getType()->getScalarType()->isPointerTy()) {
2615     // Because we have added a PHI-use of the pointer value, it has now
2616     // "escaped" from alias analysis' perspective.  We need to inform
2617     // AA of this.
2618     for (unsigned ii = 0, ee = Phi->getNumIncomingValues(); ii != ee; ++ii) {
2619       unsigned jj = PHINode::getOperandNumForIncomingValue(ii);
2620       VN.getAliasAnalysis()->addEscapingUse(Phi->getOperandUse(jj));
2621     }
2622
2623     if (MD)
2624       MD->invalidateCachedPointerInfo(Phi);
2625   }
2626   VN.erase(CurInst);
2627   removeFromLeaderTable(ValNo, CurInst, CurrentBlock);
2628
2629   DEBUG(dbgs() << "GVN PRE removed: " << *CurInst << '\n');
2630   if (MD)
2631     MD->removeInstruction(CurInst);
2632   DEBUG(verifyRemoved(CurInst));
2633   CurInst->eraseFromParent();
2634   ++NumGVNInstr;
2635
2636   return true;
2637 }
2638
2639 /// performPRE - Perform a purely local form of PRE that looks for diamond
2640 /// control flow patterns and attempts to perform simple PRE at the join point.
2641 bool GVN::performPRE(Function &F) {
2642   bool Changed = false;
2643   for (BasicBlock *CurrentBlock : depth_first(&F.getEntryBlock())) {
2644     // Nothing to PRE in the entry block.
2645     if (CurrentBlock == &F.getEntryBlock())
2646       continue;
2647
2648     // Don't perform PRE on a landing pad.
2649     if (CurrentBlock->isLandingPad())
2650       continue;
2651
2652     for (BasicBlock::iterator BI = CurrentBlock->begin(),
2653                               BE = CurrentBlock->end();
2654          BI != BE;) {
2655       Instruction *CurInst = BI++;
2656       Changed = performScalarPRE(CurInst);
2657     }
2658   }
2659
2660   if (splitCriticalEdges())
2661     Changed = true;
2662
2663   return Changed;
2664 }
2665
2666 /// Split the critical edge connecting the given two blocks, and return
2667 /// the block inserted to the critical edge.
2668 BasicBlock *GVN::splitCriticalEdges(BasicBlock *Pred, BasicBlock *Succ) {
2669   BasicBlock *BB = SplitCriticalEdge(
2670       Pred, Succ, CriticalEdgeSplittingOptions(getAliasAnalysis(), DT));
2671   if (MD)
2672     MD->invalidateCachedPredecessors();
2673   return BB;
2674 }
2675
2676 /// splitCriticalEdges - Split critical edges found during the previous
2677 /// iteration that may enable further optimization.
2678 bool GVN::splitCriticalEdges() {
2679   if (toSplit.empty())
2680     return false;
2681   do {
2682     std::pair<TerminatorInst*, unsigned> Edge = toSplit.pop_back_val();
2683     SplitCriticalEdge(Edge.first, Edge.second,
2684                       CriticalEdgeSplittingOptions(getAliasAnalysis(), DT));
2685   } while (!toSplit.empty());
2686   if (MD) MD->invalidateCachedPredecessors();
2687   return true;
2688 }
2689
2690 /// iterateOnFunction - Executes one iteration of GVN
2691 bool GVN::iterateOnFunction(Function &F) {
2692   cleanupGlobalSets();
2693
2694   // Top-down walk of the dominator tree
2695   bool Changed = false;
2696   // Save the blocks this function have before transformation begins. GVN may
2697   // split critical edge, and hence may invalidate the RPO/DT iterator.
2698   //
2699   std::vector<BasicBlock *> BBVect;
2700   BBVect.reserve(256);
2701   // Needed for value numbering with phi construction to work.
2702   ReversePostOrderTraversal<Function *> RPOT(&F);
2703   for (ReversePostOrderTraversal<Function *>::rpo_iterator RI = RPOT.begin(),
2704                                                            RE = RPOT.end();
2705        RI != RE; ++RI)
2706     BBVect.push_back(*RI);
2707
2708   for (std::vector<BasicBlock *>::iterator I = BBVect.begin(), E = BBVect.end();
2709        I != E; I++)
2710     Changed |= processBlock(*I);
2711
2712   return Changed;
2713 }
2714
2715 void GVN::cleanupGlobalSets() {
2716   VN.clear();
2717   LeaderTable.clear();
2718   TableAllocator.Reset();
2719 }
2720
2721 /// verifyRemoved - Verify that the specified instruction does not occur in our
2722 /// internal data structures.
2723 void GVN::verifyRemoved(const Instruction *Inst) const {
2724   VN.verifyRemoved(Inst);
2725
2726   // Walk through the value number scope to make sure the instruction isn't
2727   // ferreted away in it.
2728   for (DenseMap<uint32_t, LeaderTableEntry>::const_iterator
2729        I = LeaderTable.begin(), E = LeaderTable.end(); I != E; ++I) {
2730     const LeaderTableEntry *Node = &I->second;
2731     assert(Node->Val != Inst && "Inst still in value numbering scope!");
2732
2733     while (Node->Next) {
2734       Node = Node->Next;
2735       assert(Node->Val != Inst && "Inst still in value numbering scope!");
2736     }
2737   }
2738 }
2739
2740 // BB is declared dead, which implied other blocks become dead as well. This
2741 // function is to add all these blocks to "DeadBlocks". For the dead blocks'
2742 // live successors, update their phi nodes by replacing the operands
2743 // corresponding to dead blocks with UndefVal.
2744 //
2745 void GVN::addDeadBlock(BasicBlock *BB) {
2746   SmallVector<BasicBlock *, 4> NewDead;
2747   SmallSetVector<BasicBlock *, 4> DF;
2748
2749   NewDead.push_back(BB);
2750   while (!NewDead.empty()) {
2751     BasicBlock *D = NewDead.pop_back_val();
2752     if (DeadBlocks.count(D))
2753       continue;
2754
2755     // All blocks dominated by D are dead.
2756     SmallVector<BasicBlock *, 8> Dom;
2757     DT->getDescendants(D, Dom);
2758     DeadBlocks.insert(Dom.begin(), Dom.end());
2759
2760     // Figure out the dominance-frontier(D).
2761     for (SmallVectorImpl<BasicBlock *>::iterator I = Dom.begin(),
2762            E = Dom.end(); I != E; I++) {
2763       BasicBlock *B = *I;
2764       for (succ_iterator SI = succ_begin(B), SE = succ_end(B); SI != SE; SI++) {
2765         BasicBlock *S = *SI;
2766         if (DeadBlocks.count(S))
2767           continue;
2768
2769         bool AllPredDead = true;
2770         for (pred_iterator PI = pred_begin(S), PE = pred_end(S); PI != PE; PI++)
2771           if (!DeadBlocks.count(*PI)) {
2772             AllPredDead = false;
2773             break;
2774           }
2775
2776         if (!AllPredDead) {
2777           // S could be proved dead later on. That is why we don't update phi
2778           // operands at this moment.
2779           DF.insert(S);
2780         } else {
2781           // While S is not dominated by D, it is dead by now. This could take
2782           // place if S already have a dead predecessor before D is declared
2783           // dead.
2784           NewDead.push_back(S);
2785         }
2786       }
2787     }
2788   }
2789
2790   // For the dead blocks' live successors, update their phi nodes by replacing
2791   // the operands corresponding to dead blocks with UndefVal.
2792   for(SmallSetVector<BasicBlock *, 4>::iterator I = DF.begin(), E = DF.end();
2793         I != E; I++) {
2794     BasicBlock *B = *I;
2795     if (DeadBlocks.count(B))
2796       continue;
2797
2798     SmallVector<BasicBlock *, 4> Preds(pred_begin(B), pred_end(B));
2799     for (SmallVectorImpl<BasicBlock *>::iterator PI = Preds.begin(),
2800            PE = Preds.end(); PI != PE; PI++) {
2801       BasicBlock *P = *PI;
2802
2803       if (!DeadBlocks.count(P))
2804         continue;
2805
2806       if (isCriticalEdge(P->getTerminator(), GetSuccessorNumber(P, B))) {
2807         if (BasicBlock *S = splitCriticalEdges(P, B))
2808           DeadBlocks.insert(P = S);
2809       }
2810
2811       for (BasicBlock::iterator II = B->begin(); isa<PHINode>(II); ++II) {
2812         PHINode &Phi = cast<PHINode>(*II);
2813         Phi.setIncomingValue(Phi.getBasicBlockIndex(P),
2814                              UndefValue::get(Phi.getType()));
2815       }
2816     }
2817   }
2818 }
2819
2820 // If the given branch is recognized as a foldable branch (i.e. conditional
2821 // branch with constant condition), it will perform following analyses and
2822 // transformation.
2823 //  1) If the dead out-coming edge is a critical-edge, split it. Let
2824 //     R be the target of the dead out-coming edge.
2825 //  1) Identify the set of dead blocks implied by the branch's dead outcoming
2826 //     edge. The result of this step will be {X| X is dominated by R}
2827 //  2) Identify those blocks which haves at least one dead prodecessor. The
2828 //     result of this step will be dominance-frontier(R).
2829 //  3) Update the PHIs in DF(R) by replacing the operands corresponding to
2830 //     dead blocks with "UndefVal" in an hope these PHIs will optimized away.
2831 //
2832 // Return true iff *NEW* dead code are found.
2833 bool GVN::processFoldableCondBr(BranchInst *BI) {
2834   if (!BI || BI->isUnconditional())
2835     return false;
2836
2837   ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition());
2838   if (!Cond)
2839     return false;
2840
2841   BasicBlock *DeadRoot = Cond->getZExtValue() ?
2842                          BI->getSuccessor(1) : BI->getSuccessor(0);
2843   if (DeadBlocks.count(DeadRoot))
2844     return false;
2845
2846   if (!DeadRoot->getSinglePredecessor())
2847     DeadRoot = splitCriticalEdges(BI->getParent(), DeadRoot);
2848
2849   addDeadBlock(DeadRoot);
2850   return true;
2851 }
2852
2853 // performPRE() will trigger assert if it comes across an instruction without
2854 // associated val-num. As it normally has far more live instructions than dead
2855 // instructions, it makes more sense just to "fabricate" a val-number for the
2856 // dead code than checking if instruction involved is dead or not.
2857 void GVN::assignValNumForDeadCode() {
2858   for (SetVector<BasicBlock *>::iterator I = DeadBlocks.begin(),
2859         E = DeadBlocks.end(); I != E; I++) {
2860     BasicBlock *BB = *I;
2861     for (BasicBlock::iterator II = BB->begin(), EE = BB->end();
2862           II != EE; II++) {
2863       Instruction *Inst = &*II;
2864       unsigned ValNum = VN.lookup_or_add(Inst);
2865       addToLeaderTable(ValNum, Inst, BB);
2866     }
2867   }
2868 }