Vendor import of llvm-project main 88e66fa60ae5, the last commit beforevendor/llvm-project/llvmorg-13-init-16847-g88e66fa60ae5vendor/llvm-project/llvmorg-12.0.1-rc2-0-ge7dac564cd0evendor/llvm-project/llvmorg-12.0.1-0-gfed41342a82f

the upstream release/13.x branch was created.

1 files changed, 358 insertions, 204 deletions

diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp
index c6b6d75aefe8..16368aec7c3f 100644
--- a/llvm/lib/Transforms/Scalar/GVN.cpp
+++ b/llvm/lib/Transforms/Scalar/GVN.cpp
@@ -82,7 +82,6 @@
 #include <cassert>
 #include <cstdint>
 #include <utility>
-#include <vector>
 
 using namespace llvm;
 using namespace llvm::gvn;
@@ -91,13 +90,14 @@ using namespace PatternMatch;
 
 #define DEBUG_TYPE "gvn"
 
-STATISTIC(NumGVNInstr,  "Number of instructions deleted");
-STATISTIC(NumGVNLoad,   "Number of loads deleted");
-STATISTIC(NumGVNPRE,    "Number of instructions PRE'd");
+STATISTIC(NumGVNInstr, "Number of instructions deleted");
+STATISTIC(NumGVNLoad, "Number of loads deleted");
+STATISTIC(NumGVNPRE, "Number of instructions PRE'd");
 STATISTIC(NumGVNBlocks, "Number of blocks merged");
-STATISTIC(NumGVNSimpl,  "Number of instructions simplified");
+STATISTIC(NumGVNSimpl, "Number of instructions simplified");
 STATISTIC(NumGVNEqProp, "Number of equalities propagated");
-STATISTIC(NumPRELoad,   "Number of loads PRE'd");
+STATISTIC(NumPRELoad, "Number of loads PRE'd");
+STATISTIC(NumPRELoopLoad, "Number of loop loads PRE'd");
 
 STATISTIC(IsValueFullyAvailableInBlockNumSpeculationsMax,
           "Number of blocks speculated as available in "
@@ -207,9 +207,9 @@ struct llvm::gvn::AvailableValue {
     return Res;
   }
 
-  static AvailableValue getLoad(LoadInst *LI, unsigned Offset = 0) {
+  static AvailableValue getLoad(LoadInst *Load, unsigned Offset = 0) {
     AvailableValue Res;
-    Res.Val.setPointer(LI);
+    Res.Val.setPointer(Load);
     Res.Val.setInt(LoadVal);
     Res.Offset = Offset;
     return Res;
@@ -245,7 +245,7 @@ struct llvm::gvn::AvailableValue {
 
   /// Emit code at the specified insertion point to adjust the value defined
   /// here to the specified type. This handles various coercion cases.
-  Value *MaterializeAdjustedValue(LoadInst *LI, Instruction *InsertPt,
+  Value *MaterializeAdjustedValue(LoadInst *Load, Instruction *InsertPt,
                                   GVN &gvn) const;
 };
 
@@ -276,8 +276,8 @@ struct llvm::gvn::AvailableValueInBlock {
 
   /// Emit code at the end of this block to adjust the value defined here to
   /// the specified type. This handles various coercion cases.
-  Value *MaterializeAdjustedValue(LoadInst *LI, GVN &gvn) const {
-    return AV.MaterializeAdjustedValue(LI, BB->getTerminator(), gvn);
+  Value *MaterializeAdjustedValue(LoadInst *Load, GVN &gvn) const {
+    return AV.MaterializeAdjustedValue(Load, BB->getTerminator(), gvn);
   }
 };
 
@@ -289,9 +289,17 @@ GVN::Expression GVN::ValueTable::createExpr(Instruction *I) {
   Expression e;
   e.type = I->getType();
   e.opcode = I->getOpcode();
-  for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end();
-       OI != OE; ++OI)
-    e.varargs.push_back(lookupOrAdd(*OI));
+  if (const GCRelocateInst *GCR = dyn_cast<GCRelocateInst>(I)) {
+    // gc.relocate is 'special' call: its second and third operands are
+    // not real values, but indices into statepoint's argument list.
+    // Use the refered to values for purposes of identity.
+    e.varargs.push_back(lookupOrAdd(GCR->getOperand(0)));
+    e.varargs.push_back(lookupOrAdd(GCR->getBasePtr()));
+    e.varargs.push_back(lookupOrAdd(GCR->getDerivedPtr()));
+  } else {
+    for (Use &Op : I->operands())
+      e.varargs.push_back(lookupOrAdd(Op));
+  }
   if (I->isCommutative()) {
     // Ensure that commutative instructions that only differ by a permutation
     // of their operands get the same value number by sorting the operand value
@@ -362,9 +370,8 @@ GVN::Expression GVN::ValueTable::createExtractvalueExpr(ExtractValueInst *EI) {
   // Not a recognised intrinsic. Fall back to producing an extract value
   // expression.
   e.opcode = EI->getOpcode();
-  for (Instruction::op_iterator OI = EI->op_begin(), OE = EI->op_end();
-       OI != OE; ++OI)
-    e.varargs.push_back(lookupOrAdd(*OI));
+  for (Use &Op : EI->operands())
+    e.varargs.push_back(lookupOrAdd(Op));
 
   append_range(e.varargs, EI->indices());
 
@@ -669,7 +676,6 @@ PreservedAnalyses GVN::run(Function &F, FunctionAnalysisManager &AM) {
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<DominatorTreeAnalysis>();
-  PA.preserve<GlobalsAA>();
   PA.preserve<TargetLibraryAnalysis>();
   if (MSSA)
     PA.preserve<MemorySSAAnalysis>();
@@ -681,10 +687,9 @@ PreservedAnalyses GVN::run(Function &F, FunctionAnalysisManager &AM) {
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void GVN::dump(DenseMap<uint32_t, Value*>& d) const {
   errs() << "{\n";
-  for (DenseMap<uint32_t, Value*>::iterator I = d.begin(),
-       E = d.end(); I != E; ++I) {
-      errs() << I->first << "\n";
-      I->second->dump();
+  for (auto &I : d) {
+    errs() << I.first << "\n";
+    I.second->dump();
   }
   errs() << "}\n";
 }
@@ -727,7 +732,7 @@ static bool IsValueFullyAvailableInBlock(
 
   Worklist.emplace_back(BB);
   while (!Worklist.empty()) {
-    BasicBlock *CurrBB = Worklist.pop_back_val(); // LIFO - depth-first!
+    BasicBlock *CurrBB = Worklist.pop_back_val(); // LoadFO - depth-first!
     // Optimistically assume that the block is Speculatively Available and check
     // to see if we already know about this block in one lookup.
     std::pair<DenseMap<BasicBlock *, AvailabilityState>::iterator, bool> IV =
@@ -825,29 +830,33 @@ static bool IsValueFullyAvailableInBlock(
 }
 
 /// Given a set of loads specified by ValuesPerBlock,
-/// construct SSA form, allowing us to eliminate LI.  This returns the value
-/// that should be used at LI's definition site.
-static Value *ConstructSSAForLoadSet(LoadInst *LI,
-                         SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock,
-                                     GVN &gvn) {
+/// construct SSA form, allowing us to eliminate Load.  This returns the value
+/// that should be used at Load's definition site.
+static Value *
+ConstructSSAForLoadSet(LoadInst *Load,
+                       SmallVectorImpl<AvailableValueInBlock> &ValuesPerBlock,
+                       GVN &gvn) {
   // Check for the fully redundant, dominating load case.  In this case, we can
   // just use the dominating value directly.
   if (ValuesPerBlock.size() == 1 &&
       gvn.getDominatorTree().properlyDominates(ValuesPerBlock[0].BB,
-                                               LI->getParent())) {
+                                               Load->getParent())) {
     assert(!ValuesPerBlock[0].AV.isUndefValue() &&
            "Dead BB dominate this block");
-    return ValuesPerBlock[0].MaterializeAdjustedValue(LI, gvn);
+    return ValuesPerBlock[0].MaterializeAdjustedValue(Load, gvn);
   }
 
   // Otherwise, we have to construct SSA form.
   SmallVector<PHINode*, 8> NewPHIs;
   SSAUpdater SSAUpdate(&NewPHIs);
-  SSAUpdate.Initialize(LI->getType(), LI->getName());
+  SSAUpdate.Initialize(Load->getType(), Load->getName());
 
   for (const AvailableValueInBlock &AV : ValuesPerBlock) {
     BasicBlock *BB = AV.BB;
 
+    if (AV.AV.isUndefValue())
+      continue;
+
     if (SSAUpdate.HasValueForBlock(BB))
       continue;
 
@@ -855,24 +864,24 @@ static Value *ConstructSSAForLoadSet(LoadInst *LI,
     // available in is the block that the load is in, then don't add it as
     // SSAUpdater will resolve the value to the relevant phi which may let it
     // avoid phi construction entirely if there's actually only one value.
-    if (BB == LI->getParent() &&
-        ((AV.AV.isSimpleValue() && AV.AV.getSimpleValue() == LI) ||
-         (AV.AV.isCoercedLoadValue() && AV.AV.getCoercedLoadValue() == LI)))
+    if (BB == Load->getParent() &&
+        ((AV.AV.isSimpleValue() && AV.AV.getSimpleValue() == Load) ||
+         (AV.AV.isCoercedLoadValue() && AV.AV.getCoercedLoadValue() == Load)))
       continue;
 
-    SSAUpdate.AddAvailableValue(BB, AV.MaterializeAdjustedValue(LI, gvn));
+    SSAUpdate.AddAvailableValue(BB, AV.MaterializeAdjustedValue(Load, gvn));
   }
 
   // Perform PHI construction.
-  return SSAUpdate.GetValueInMiddleOfBlock(LI->getParent());
+  return SSAUpdate.GetValueInMiddleOfBlock(Load->getParent());
 }
 
-Value *AvailableValue::MaterializeAdjustedValue(LoadInst *LI,
+Value *AvailableValue::MaterializeAdjustedValue(LoadInst *Load,
                                                 Instruction *InsertPt,
                                                 GVN &gvn) const {
   Value *Res;
-  Type *LoadTy = LI->getType();
-  const DataLayout &DL = LI->getModule()->getDataLayout();
+  Type *LoadTy = Load->getType();
+  const DataLayout &DL = Load->getModule()->getDataLayout();
   if (isSimpleValue()) {
     Res = getSimpleValue();
     if (Res->getType() != LoadTy) {
@@ -884,17 +893,17 @@ Value *AvailableValue::MaterializeAdjustedValue(LoadInst *LI,
                         << "\n\n\n");
     }
   } else if (isCoercedLoadValue()) {
-    LoadInst *Load = getCoercedLoadValue();
-    if (Load->getType() == LoadTy && Offset == 0) {
-      Res = Load;
+    LoadInst *CoercedLoad = getCoercedLoadValue();
+    if (CoercedLoad->getType() == LoadTy && Offset == 0) {
+      Res = CoercedLoad;
     } else {
-      Res = getLoadValueForLoad(Load, Offset, LoadTy, InsertPt, DL);
+      Res = getLoadValueForLoad(CoercedLoad, Offset, LoadTy, InsertPt, DL);
       // We would like to use gvn.markInstructionForDeletion here, but we can't
       // because the load is already memoized into the leader map table that GVN
       // tracks.  It is potentially possible to remove the load from the table,
       // but then there all of the operations based on it would need to be
       // rehashed.  Just leave the dead load around.
-      gvn.getMemDep().removeInstruction(Load);
+      gvn.getMemDep().removeInstruction(CoercedLoad);
       LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL LOAD:\nOffset: " << Offset
                         << "  " << *getCoercedLoadValue() << '\n'
                         << *Res << '\n'
@@ -908,9 +917,7 @@ Value *AvailableValue::MaterializeAdjustedValue(LoadInst *LI,
                       << *Res << '\n'
                       << "\n\n\n");
   } else {
-    assert(isUndefValue() && "Should be UndefVal");
-    LLVM_DEBUG(dbgs() << "GVN COERCED NONLOCAL Undef:\n";);
-    return UndefValue::get(LoadTy);
+    llvm_unreachable("Should not materialize value from dead block");
   }
   assert(Res && "failed to materialize?");
   return Res;
@@ -922,30 +929,70 @@ static bool isLifetimeStart(const Instruction *Inst) {
   return false;
 }
 
+/// Assuming To can be reached from both From and Between, does Between lie on
+/// every path from From to To?
+static bool liesBetween(const Instruction *From, Instruction *Between,
+                        const Instruction *To, DominatorTree *DT) {
+  if (From->getParent() == Between->getParent())
+    return DT->dominates(From, Between);
+  SmallSet<BasicBlock *, 1> Exclusion;
+  Exclusion.insert(Between->getParent());
+  return !isPotentiallyReachable(From, To, &Exclusion, DT);
+}
+
 /// Try to locate the three instruction involved in a missed
 /// load-elimination case that is due to an intervening store.
-static void reportMayClobberedLoad(LoadInst *LI, MemDepResult DepInfo,
+static void reportMayClobberedLoad(LoadInst *Load, MemDepResult DepInfo,
                                    DominatorTree *DT,
                                    OptimizationRemarkEmitter *ORE) {
   using namespace ore;
 
   User *OtherAccess = nullptr;
 
-  OptimizationRemarkMissed R(DEBUG_TYPE, "LoadClobbered", LI);
-  R << "load of type " << NV("Type", LI->getType()) << " not eliminated"
+  OptimizationRemarkMissed R(DEBUG_TYPE, "LoadClobbered", Load);
+  R << "load of type " << NV("Type", Load->getType()) << " not eliminated"
     << setExtraArgs();
 
-  for (auto *U : LI->getPointerOperand()->users())
-    if (U != LI && (isa<LoadInst>(U) || isa<StoreInst>(U)) &&
-        DT->dominates(cast<Instruction>(U), LI)) {
-      // FIXME: for now give up if there are multiple memory accesses that
-      // dominate the load.  We need further analysis to decide which one is
-      // that we're forwarding from.
-      if (OtherAccess)
-        OtherAccess = nullptr;
-      else
+  for (auto *U : Load->getPointerOperand()->users()) {
+    if (U != Load && (isa<LoadInst>(U) || isa<StoreInst>(U)) &&
+        cast<Instruction>(U)->getFunction() == Load->getFunction() &&
+        DT->dominates(cast<Instruction>(U), Load)) {
+      // Use the most immediately dominating value
+      if (OtherAccess) {
+        if (DT->dominates(cast<Instruction>(OtherAccess), cast<Instruction>(U)))
+          OtherAccess = U;
+        else
+          assert(DT->dominates(cast<Instruction>(U),
+                               cast<Instruction>(OtherAccess)));
+      } else
         OtherAccess = U;
     }
+  }
+
+  if (!OtherAccess) {
+    // There is no dominating use, check if we can find a closest non-dominating
+    // use that lies between any other potentially available use and Load.
+    for (auto *U : Load->getPointerOperand()->users()) {
+      if (U != Load && (isa<LoadInst>(U) || isa<StoreInst>(U)) &&
+          cast<Instruction>(U)->getFunction() == Load->getFunction() &&
+          isPotentiallyReachable(cast<Instruction>(U), Load, nullptr, DT)) {
+        if (OtherAccess) {
+          if (liesBetween(cast<Instruction>(OtherAccess), cast<Instruction>(U),
+                          Load, DT)) {
+            OtherAccess = U;
+          } else if (!liesBetween(cast<Instruction>(U),
+                                  cast<Instruction>(OtherAccess), Load, DT)) {
+            // These uses are both partially available at Load were it not for
+            // the clobber, but neither lies strictly after the other.
+            OtherAccess = nullptr;
+            break;
+          } // else: keep current OtherAccess since it lies between U and Load
+        } else {
+          OtherAccess = U;
+        }
+      }
+    }
+  }
 
   if (OtherAccess)
     R << " in favor of " << NV("OtherAccess", OtherAccess);
@@ -955,13 +1002,13 @@ static void reportMayClobberedLoad(LoadInst *LI, MemDepResult DepInfo,
   ORE->emit(R);
 }
 
-bool GVN::AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
+bool GVN::AnalyzeLoadAvailability(LoadInst *Load, MemDepResult DepInfo,
                                   Value *Address, AvailableValue &Res) {
   assert((DepInfo.isDef() || DepInfo.isClobber()) &&
          "expected a local dependence");
-  assert(LI->isUnordered() && "rules below are incorrect for ordered access");
+  assert(Load->isUnordered() && "rules below are incorrect for ordered access");
 
-  const DataLayout &DL = LI->getModule()->getDataLayout();
+  const DataLayout &DL = Load->getModule()->getDataLayout();
 
   Instruction *DepInst = DepInfo.getInst();
   if (DepInfo.isClobber()) {
@@ -970,9 +1017,9 @@ bool GVN::AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
     // stored value.
     if (StoreInst *DepSI = dyn_cast<StoreInst>(DepInst)) {
       // Can't forward from non-atomic to atomic without violating memory model.
-      if (Address && LI->isAtomic() <= DepSI->isAtomic()) {
+      if (Address && Load->isAtomic() <= DepSI->isAtomic()) {
         int Offset =
-          analyzeLoadFromClobberingStore(LI->getType(), Address, DepSI, DL);
+            analyzeLoadFromClobberingStore(Load->getType(), Address, DepSI, DL);
         if (Offset != -1) {
           Res = AvailableValue::get(DepSI->getValueOperand(), Offset);
           return true;
@@ -984,16 +1031,29 @@ bool GVN::AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
     //    load i32* P
     //    load i8* (P+1)
     // if we have this, replace the later with an extraction from the former.
-    if (LoadInst *DepLI = dyn_cast<LoadInst>(DepInst)) {
+    if (LoadInst *DepLoad = dyn_cast<LoadInst>(DepInst)) {
       // If this is a clobber and L is the first instruction in its block, then
       // we have the first instruction in the entry block.
       // Can't forward from non-atomic to atomic without violating memory model.
-      if (DepLI != LI && Address && LI->isAtomic() <= DepLI->isAtomic()) {
-        int Offset =
-          analyzeLoadFromClobberingLoad(LI->getType(), Address, DepLI, DL);
-
+      if (DepLoad != Load && Address &&
+          Load->isAtomic() <= DepLoad->isAtomic()) {
+        Type *LoadType = Load->getType();
+        int Offset = -1;
+
+        // If MD reported clobber, check it was nested.
+        if (DepInfo.isClobber() &&
+            canCoerceMustAliasedValueToLoad(DepLoad, LoadType, DL)) {
+          const auto ClobberOff = MD->getClobberOffset(DepLoad);
+          // GVN has no deal with a negative offset.
+          Offset = (ClobberOff == None || ClobberOff.getValue() < 0)
+                       ? -1
+                       : ClobberOff.getValue();
+        }
+        if (Offset == -1)
+          Offset =
+              analyzeLoadFromClobberingLoad(LoadType, Address, DepLoad, DL);
         if (Offset != -1) {
-          Res = AvailableValue::getLoad(DepLI, Offset);
+          Res = AvailableValue::getLoad(DepLoad, Offset);
           return true;
         }
       }
@@ -1002,8 +1062,8 @@ bool GVN::AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
     // If the clobbering value is a memset/memcpy/memmove, see if we can
     // forward a value on from it.
     if (MemIntrinsic *DepMI = dyn_cast<MemIntrinsic>(DepInst)) {
-      if (Address && !LI->isAtomic()) {
-        int Offset = analyzeLoadFromClobberingMemInst(LI->getType(), Address,
+      if (Address && !Load->isAtomic()) {
+        int Offset = analyzeLoadFromClobberingMemInst(Load->getType(), Address,
                                                       DepMI, DL);
         if (Offset != -1) {
           Res = AvailableValue::getMI(DepMI, Offset);
@@ -1014,10 +1074,10 @@ bool GVN::AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
     // Nothing known about this clobber, have to be conservative
     LLVM_DEBUG(
         // fast print dep, using operator<< on instruction is too slow.
-        dbgs() << "GVN: load "; LI->printAsOperand(dbgs());
+        dbgs() << "GVN: load "; Load->printAsOperand(dbgs());
         dbgs() << " is clobbered by " << *DepInst << '\n';);
     if (ORE->allowExtraAnalysis(DEBUG_TYPE))
-      reportMayClobberedLoad(LI, DepInfo, DT, ORE);
+      reportMayClobberedLoad(Load, DepInfo, DT, ORE);
 
     return false;
   }
@@ -1028,13 +1088,13 @@ bool GVN::AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
       isAlignedAllocLikeFn(DepInst, TLI) ||
       // Loading immediately after lifetime begin -> undef.
       isLifetimeStart(DepInst)) {
-    Res = AvailableValue::get(UndefValue::get(LI->getType()));
+    Res = AvailableValue::get(UndefValue::get(Load->getType()));
     return true;
   }
 
   // Loading from calloc (which zero initializes memory) -> zero
   if (isCallocLikeFn(DepInst, TLI)) {
-    Res = AvailableValue::get(Constant::getNullValue(LI->getType()));
+    Res = AvailableValue::get(Constant::getNullValue(Load->getType()));
     return true;
   }
 
@@ -1042,12 +1102,12 @@ bool GVN::AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
     // Reject loads and stores that are to the same address but are of
     // different types if we have to. If the stored value is convertable to
     // the loaded value, we can reuse it.
-    if (!canCoerceMustAliasedValueToLoad(S->getValueOperand(), LI->getType(),
+    if (!canCoerceMustAliasedValueToLoad(S->getValueOperand(), Load->getType(),
                                          DL))
       return false;
 
     // Can't forward from non-atomic to atomic without violating memory model.
-    if (S->isAtomic() < LI->isAtomic())
+    if (S->isAtomic() < Load->isAtomic())
       return false;
 
     Res = AvailableValue::get(S->getValueOperand());
@@ -1058,11 +1118,11 @@ bool GVN::AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
     // If the types mismatch and we can't handle it, reject reuse of the load.
     // If the stored value is larger or equal to the loaded value, we can reuse
     // it.
-    if (!canCoerceMustAliasedValueToLoad(LD, LI->getType(), DL))
+    if (!canCoerceMustAliasedValueToLoad(LD, Load->getType(), DL))
       return false;
 
     // Can't forward from non-atomic to atomic without violating memory model.
-    if (LD->isAtomic() < LI->isAtomic())
+    if (LD->isAtomic() < Load->isAtomic())
       return false;
 
     Res = AvailableValue::getLoad(LD);
@@ -1072,12 +1132,12 @@ bool GVN::AnalyzeLoadAvailability(LoadInst *LI, MemDepResult DepInfo,
   // Unknown def - must be conservative
   LLVM_DEBUG(
       // fast print dep, using operator<< on instruction is too slow.
-      dbgs() << "GVN: load "; LI->printAsOperand(dbgs());
+      dbgs() << "GVN: load "; Load->printAsOperand(dbgs());
       dbgs() << " has unknown def " << *DepInst << '\n';);
   return false;
 }
 
-void GVN::AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
+void GVN::AnalyzeLoadAvailability(LoadInst *Load, LoadDepVect &Deps,
                                   AvailValInBlkVect &ValuesPerBlock,
                                   UnavailBlkVect &UnavailableBlocks) {
   // Filter out useless results (non-locals, etc).  Keep track of the blocks
@@ -1107,7 +1167,7 @@ void GVN::AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
     Value *Address = Deps[i].getAddress();
 
     AvailableValue AV;
-    if (AnalyzeLoadAvailability(LI, DepInfo, Address, AV)) {
+    if (AnalyzeLoadAvailability(Load, DepInfo, Address, AV)) {
       // subtlety: because we know this was a non-local dependency, we know
       // it's safe to materialize anywhere between the instruction within
       // DepInfo and the end of it's block.
@@ -1122,7 +1182,82 @@ void GVN::AnalyzeLoadAvailability(LoadInst *LI, LoadDepVect &Deps,
          "post condition violation");
 }
 
-bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
+void GVN::eliminatePartiallyRedundantLoad(
+    LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
+    MapVector<BasicBlock *, Value *> &AvailableLoads) {
+  for (const auto &AvailableLoad : AvailableLoads) {
+    BasicBlock *UnavailableBlock = AvailableLoad.first;
+    Value *LoadPtr = AvailableLoad.second;
+
+    auto *NewLoad =
+        new LoadInst(Load->getType(), LoadPtr, Load->getName() + ".pre",
+                     Load->isVolatile(), Load->getAlign(), Load->getOrdering(),
+                     Load->getSyncScopeID(), UnavailableBlock->getTerminator());
+    NewLoad->setDebugLoc(Load->getDebugLoc());
+    if (MSSAU) {
+      auto *MSSA = MSSAU->getMemorySSA();
+      // Get the defining access of the original load or use the load if it is a
+      // MemoryDef (e.g. because it is volatile). The inserted loads are
+      // guaranteed to load from the same definition.
+      auto *LoadAcc = MSSA->getMemoryAccess(Load);
+      auto *DefiningAcc =
+          isa<MemoryDef>(LoadAcc) ? LoadAcc : LoadAcc->getDefiningAccess();
+      auto *NewAccess = MSSAU->createMemoryAccessInBB(
+          NewLoad, DefiningAcc, NewLoad->getParent(),
+          MemorySSA::BeforeTerminator);
+      if (auto *NewDef = dyn_cast<MemoryDef>(NewAccess))
+        MSSAU->insertDef(NewDef, /*RenameUses=*/true);
+      else
+        MSSAU->insertUse(cast<MemoryUse>(NewAccess), /*RenameUses=*/true);
+    }
+
+    // Transfer the old load's AA tags to the new load.
+    AAMDNodes Tags;
+    Load->getAAMetadata(Tags);
+    if (Tags)
+      NewLoad->setAAMetadata(Tags);
+
+    if (auto *MD = Load->getMetadata(LLVMContext::MD_invariant_load))
+      NewLoad->setMetadata(LLVMContext::MD_invariant_load, MD);
+    if (auto *InvGroupMD = Load->getMetadata(LLVMContext::MD_invariant_group))
+      NewLoad->setMetadata(LLVMContext::MD_invariant_group, InvGroupMD);
+    if (auto *RangeMD = Load->getMetadata(LLVMContext::MD_range))
+      NewLoad->setMetadata(LLVMContext::MD_range, RangeMD);
+    if (auto *AccessMD = Load->getMetadata(LLVMContext::MD_access_group))
+      if (LI &&
+          LI->getLoopFor(Load->getParent()) == LI->getLoopFor(UnavailableBlock))
+        NewLoad->setMetadata(LLVMContext::MD_access_group, AccessMD);
+
+    // We do not propagate the old load's debug location, because the new
+    // load now lives in a different BB, and we want to avoid a jumpy line
+    // table.
+    // FIXME: How do we retain source locations without causing poor debugging
+    // behavior?
+
+    // Add the newly created load.
+    ValuesPerBlock.push_back(
+        AvailableValueInBlock::get(UnavailableBlock, NewLoad));
+    MD->invalidateCachedPointerInfo(LoadPtr);
+    LLVM_DEBUG(dbgs() << "GVN INSERTED " << *NewLoad << '\n');
+  }
+
+  // Perform PHI construction.
+  Value *V = ConstructSSAForLoadSet(Load, ValuesPerBlock, *this);
+  Load->replaceAllUsesWith(V);
+  if (isa<PHINode>(V))
+    V->takeName(Load);
+  if (Instruction *I = dyn_cast<Instruction>(V))
+    I->setDebugLoc(Load->getDebugLoc());
+  if (V->getType()->isPtrOrPtrVectorTy())
+    MD->invalidateCachedPointerInfo(V);
+  markInstructionForDeletion(Load);
+  ORE->emit([&]() {
+    return OptimizationRemark(DEBUG_TYPE, "LoadPRE", Load)
+           << "load eliminated by PRE";
+  });
+}
+
+bool GVN::PerformLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
                          UnavailBlkVect &UnavailableBlocks) {
   // Okay, we have *some* definitions of the value.  This means that the value
   // is available in some of our (transitive) predecessors.  Lets think about
@@ -1137,7 +1272,7 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
 
   // Let's find the first basic block with more than one predecessor.  Walk
   // backwards through predecessors if needed.
-  BasicBlock *LoadBB = LI->getParent();
+  BasicBlock *LoadBB = Load->getParent();
   BasicBlock *TmpBB = LoadBB;
 
   // Check that there is no implicit control flow instructions above our load in
@@ -1156,7 +1291,7 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
   // access the array.
   // Check that there is no guard in this block above our instruction.
   bool MustEnsureSafetyOfSpeculativeExecution =
-      ICF->isDominatedByICFIFromSameBlock(LI);
+      ICF->isDominatedByICFIFromSameBlock(Load);
 
   while (TmpBB->getSinglePredecessor()) {
     TmpBB = TmpBB->getSinglePredecessor();
@@ -1197,7 +1332,7 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
     if (Pred->getTerminator()->isEHPad()) {
       LLVM_DEBUG(
           dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD PREDECESSOR '"
-                 << Pred->getName() << "': " << *LI << '\n');
+                 << Pred->getName() << "': " << *Load << '\n');
       return false;
     }
 
@@ -1209,7 +1344,7 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
       if (isa<IndirectBrInst>(Pred->getTerminator())) {
         LLVM_DEBUG(
             dbgs() << "COULD NOT PRE LOAD BECAUSE OF INDBR CRITICAL EDGE '"
-                   << Pred->getName() << "': " << *LI << '\n');
+                   << Pred->getName() << "': " << *Load << '\n');
         return false;
       }
 
@@ -1217,14 +1352,14 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
       if (isa<CallBrInst>(Pred->getTerminator())) {
         LLVM_DEBUG(
             dbgs() << "COULD NOT PRE LOAD BECAUSE OF CALLBR CRITICAL EDGE '"
-                   << Pred->getName() << "': " << *LI << '\n');
+                   << Pred->getName() << "': " << *Load << '\n');
         return false;
       }
 
       if (LoadBB->isEHPad()) {
         LLVM_DEBUG(
             dbgs() << "COULD NOT PRE LOAD BECAUSE OF AN EH PAD CRITICAL EDGE '"
-                   << Pred->getName() << "': " << *LI << '\n');
+                   << Pred->getName() << "': " << *Load << '\n');
         return false;
       }
 
@@ -1234,7 +1369,7 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
           LLVM_DEBUG(
               dbgs()
               << "COULD NOT PRE LOAD BECAUSE OF A BACKEDGE CRITICAL EDGE '"
-              << Pred->getName() << "': " << *LI << '\n');
+              << Pred->getName() << "': " << *Load << '\n');
           return false;
         }
 
@@ -1252,7 +1387,7 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
 
   // If this load is unavailable in multiple predecessors, reject it.
   // FIXME: If we could restructure the CFG, we could make a common pred with
-  // all the preds that don't have an available LI and insert a new load into
+  // all the preds that don't have an available Load and insert a new load into
   // that one block.
   if (NumUnavailablePreds != 1)
       return false;
@@ -1261,10 +1396,10 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
   // to speculatively execute the load at that points.
   if (MustEnsureSafetyOfSpeculativeExecution) {
     if (CriticalEdgePred.size())
-      if (!isSafeToSpeculativelyExecute(LI, LoadBB->getFirstNonPHI(), DT))
+      if (!isSafeToSpeculativelyExecute(Load, LoadBB->getFirstNonPHI(), DT))
         return false;
     for (auto &PL : PredLoads)
-      if (!isSafeToSpeculativelyExecute(LI, PL.first->getTerminator(), DT))
+      if (!isSafeToSpeculativelyExecute(Load, PL.first->getTerminator(), DT))
         return false;
   }
 
@@ -1279,21 +1414,21 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
 
   // Check if the load can safely be moved to all the unavailable predecessors.
   bool CanDoPRE = true;
-  const DataLayout &DL = LI->getModule()->getDataLayout();
+  const DataLayout &DL = Load->getModule()->getDataLayout();
   SmallVector<Instruction*, 8> NewInsts;
   for (auto &PredLoad : PredLoads) {
     BasicBlock *UnavailablePred = PredLoad.first;
 
     // Do PHI translation to get its value in the predecessor if necessary.  The
     // returned pointer (if non-null) is guaranteed to dominate UnavailablePred.
-    // We do the translation for each edge we skipped by going from LI's block
+    // We do the translation for each edge we skipped by going from Load's block
     // to LoadBB, otherwise we might miss pieces needing translation.
 
     // If all preds have a single successor, then we know it is safe to insert
     // the load on the pred (?!?), so we can insert code to materialize the
     // pointer if it is not available.
-    Value *LoadPtr = LI->getPointerOperand();
-    BasicBlock *Cur = LI->getParent();
+    Value *LoadPtr = Load->getPointerOperand();
+    BasicBlock *Cur = Load->getParent();
     while (Cur != LoadBB) {
       PHITransAddr Address(LoadPtr, DL, AC);
       LoadPtr = Address.PHITranslateWithInsertion(
@@ -1314,7 +1449,7 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
     // we fail PRE.
     if (!LoadPtr) {
       LLVM_DEBUG(dbgs() << "COULDN'T INSERT PHI TRANSLATED VALUE OF: "
-                        << *LI->getPointerOperand() << "\n");
+                        << *Load->getPointerOperand() << "\n");
       CanDoPRE = false;
       break;
     }
@@ -1339,10 +1474,10 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
   // Okay, we can eliminate this load by inserting a reload in the predecessor
   // and using PHI construction to get the value in the other predecessors, do
   // it.
-  LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOAD: " << *LI << '\n');
-  LLVM_DEBUG(if (!NewInsts.empty()) dbgs()
-             << "INSERTED " << NewInsts.size() << " INSTS: " << *NewInsts.back()
-             << '\n');
+  LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOAD: " << *Load << '\n');
+  LLVM_DEBUG(if (!NewInsts.empty()) dbgs() << "INSERTED " << NewInsts.size()
+                                           << " INSTS: " << *NewInsts.back()
+                                           << '\n');
 
   // Assign value numbers to the new instructions.
   for (Instruction *I : NewInsts) {
@@ -1358,83 +1493,96 @@ bool GVN::PerformLoadPRE(LoadInst *LI, AvailValInBlkVect &ValuesPerBlock,
     VN.lookupOrAdd(I);
   }
 
-  for (const auto &PredLoad : PredLoads) {
-    BasicBlock *UnavailablePred = PredLoad.first;
-    Value *LoadPtr = PredLoad.second;
+  eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, PredLoads);
+  ++NumPRELoad;
+  return true;
+}
 
-    auto *NewLoad = new LoadInst(
-        LI->getType(), LoadPtr, LI->getName() + ".pre", LI->isVolatile(),
-        LI->getAlign(), LI->getOrdering(), LI->getSyncScopeID(),
-        UnavailablePred->getTerminator());
-    NewLoad->setDebugLoc(LI->getDebugLoc());
-    if (MSSAU) {
-      auto *MSSA = MSSAU->getMemorySSA();
-      // Get the defining access of the original load or use the load if it is a
-      // MemoryDef (e.g. because it is volatile). The inserted loads are
-      // guaranteed to load from the same definition.
-      auto *LIAcc = MSSA->getMemoryAccess(LI);
-      auto *DefiningAcc =
-          isa<MemoryDef>(LIAcc) ? LIAcc : LIAcc->getDefiningAccess();
-      auto *NewAccess = MSSAU->createMemoryAccessInBB(
-          NewLoad, DefiningAcc, NewLoad->getParent(),
-          MemorySSA::BeforeTerminator);
-      if (auto *NewDef = dyn_cast<MemoryDef>(NewAccess))
-        MSSAU->insertDef(NewDef, /*RenameUses=*/true);
-      else
-        MSSAU->insertUse(cast<MemoryUse>(NewAccess), /*RenameUses=*/true);
-    }
+bool GVN::performLoopLoadPRE(LoadInst *Load, AvailValInBlkVect &ValuesPerBlock,
+                             UnavailBlkVect &UnavailableBlocks) {
+  if (!LI)
+    return false;
 
-    // Transfer the old load's AA tags to the new load.
-    AAMDNodes Tags;
-    LI->getAAMetadata(Tags);
-    if (Tags)
-      NewLoad->setAAMetadata(Tags);
+  const Loop *L = LI->getLoopFor(Load->getParent());
+  // TODO: Generalize to other loop blocks that dominate the latch.
+  if (!L || L->getHeader() != Load->getParent())
+    return false;
 
-    if (auto *MD = LI->getMetadata(LLVMContext::MD_invariant_load))
-      NewLoad->setMetadata(LLVMContext::MD_invariant_load, MD);
-    if (auto *InvGroupMD = LI->getMetadata(LLVMContext::MD_invariant_group))
-      NewLoad->setMetadata(LLVMContext::MD_invariant_group, InvGroupMD);
-    if (auto *RangeMD = LI->getMetadata(LLVMContext::MD_range))
-      NewLoad->setMetadata(LLVMContext::MD_range, RangeMD);
+  BasicBlock *Preheader = L->getLoopPreheader();
+  BasicBlock *Latch = L->getLoopLatch();
+  if (!Preheader || !Latch)
+    return false;
 
-    // We do not propagate the old load's debug location, because the new
-    // load now lives in a different BB, and we want to avoid a jumpy line
-    // table.
-    // FIXME: How do we retain source locations without causing poor debugging
-    // behavior?
+  Value *LoadPtr = Load->getPointerOperand();
+  // Must be available in preheader.
+  if (!L->isLoopInvariant(LoadPtr))
+    return false;
 
-    // Add the newly created load.
-    ValuesPerBlock.push_back(AvailableValueInBlock::get(UnavailablePred,
-                                                        NewLoad));
-    MD->invalidateCachedPointerInfo(LoadPtr);
-    LLVM_DEBUG(dbgs() << "GVN INSERTED " << *NewLoad << '\n');
+  // We plan to hoist the load to preheader without introducing a new fault.
+  // In order to do it, we need to prove that we cannot side-exit the loop
+  // once loop header is first entered before execution of the load.
+  if (ICF->isDominatedByICFIFromSameBlock(Load))
+    return false;
+
+  BasicBlock *LoopBlock = nullptr;
+  for (auto *Blocker : UnavailableBlocks) {
+    // Blockers from outside the loop are handled in preheader.
+    if (!L->contains(Blocker))
+      continue;
+
+    // Only allow one loop block. Loop header is not less frequently executed
+    // than each loop block, and likely it is much more frequently executed. But
+    // in case of multiple loop blocks, we need extra information (such as block
+    // frequency info) to understand whether it is profitable to PRE into
+    // multiple loop blocks.
+    if (LoopBlock)
+      return false;
+
+    // Do not sink into inner loops. This may be non-profitable.
+    if (L != LI->getLoopFor(Blocker))
+      return false;
+
+    // Blocks that dominate the latch execute on every single iteration, maybe
+    // except the last one. So PREing into these blocks doesn't make much sense
+    // in most cases. But the blocks that do not necessarily execute on each
+    // iteration are sometimes much colder than the header, and this is when
+    // PRE is potentially profitable.
+    if (DT->dominates(Blocker, Latch))
+      return false;
+
+    // Make sure that the terminator itself doesn't clobber.
+    if (Blocker->getTerminator()->mayWriteToMemory())
+      return false;
+
+    LoopBlock = Blocker;
   }
 
-  // Perform PHI construction.
-  Value *V = ConstructSSAForLoadSet(LI, ValuesPerBlock, *this);
-  LI->replaceAllUsesWith(V);
-  if (isa<PHINode>(V))
-    V->takeName(LI);
-  if (Instruction *I = dyn_cast<Instruction>(V))
-    I->setDebugLoc(LI->getDebugLoc());
-  if (V->getType()->isPtrOrPtrVectorTy())
-    MD->invalidateCachedPointerInfo(V);
-  markInstructionForDeletion(LI);
-  ORE->emit([&]() {
-    return OptimizationRemark(DEBUG_TYPE, "LoadPRE", LI)
-           << "load eliminated by PRE";
-  });
-  ++NumPRELoad;
+  if (!LoopBlock)
+    return false;
+
+  // Make sure the memory at this pointer cannot be freed, therefore we can
+  // safely reload from it after clobber.
+  if (LoadPtr->canBeFreed())
+    return false;
+
+  // TODO: Support critical edge splitting if blocker has more than 1 successor.
+  MapVector<BasicBlock *, Value *> AvailableLoads;
+  AvailableLoads[LoopBlock] = LoadPtr;
+  AvailableLoads[Preheader] = LoadPtr;
+
+  LLVM_DEBUG(dbgs() << "GVN REMOVING PRE LOOP LOAD: " << *Load << '\n');
+  eliminatePartiallyRedundantLoad(Load, ValuesPerBlock, AvailableLoads);
+  ++NumPRELoopLoad;
   return true;
 }
 
-static void reportLoadElim(LoadInst *LI, Value *AvailableValue,
+static void reportLoadElim(LoadInst *Load, Value *AvailableValue,
                            OptimizationRemarkEmitter *ORE) {
   using namespace ore;
 
   ORE->emit([&]() {
-    return OptimizationRemark(DEBUG_TYPE, "LoadElim", LI)
-           << "load of type " << NV("Type", LI->getType()) << " eliminated"
+    return OptimizationRemark(DEBUG_TYPE, "LoadElim", Load)
+           << "load of type " << NV("Type", Load->getType()) << " eliminated"
            << setExtraArgs() << " in favor of "
            << NV("InfavorOfValue", AvailableValue);
   });
@@ -1442,17 +1590,17 @@ static void reportLoadElim(LoadInst *LI, Value *AvailableValue,
 
 /// Attempt to eliminate a load whose dependencies are
 /// non-local by performing PHI construction.
-bool GVN::processNonLocalLoad(LoadInst *LI) {
+bool GVN::processNonLocalLoad(LoadInst *Load) {
   // non-local speculations are not allowed under asan.
-  if (LI->getParent()->getParent()->hasFnAttribute(
+  if (Load->getParent()->getParent()->hasFnAttribute(
           Attribute::SanitizeAddress) ||
-      LI->getParent()->getParent()->hasFnAttribute(
+      Load->getParent()->getParent()->hasFnAttribute(
           Attribute::SanitizeHWAddress))
     return false;
 
   // Step 1: Find the non-local dependencies of the load.
   LoadDepVect Deps;
-  MD->getNonLocalPointerDependency(LI, Deps);
+  MD->getNonLocalPointerDependency(Load, Deps);
 
   // If we had to process more than one hundred blocks to find the
   // dependencies, this load isn't worth worrying about.  Optimizing
@@ -1465,14 +1613,15 @@ bool GVN::processNonLocalLoad(LoadInst *LI) {
   // clobber in the current block.  Reject this early.
   if (NumDeps == 1 &&
       !Deps[0].getResult().isDef() && !Deps[0].getResult().isClobber()) {
-    LLVM_DEBUG(dbgs() << "GVN: non-local load "; LI->printAsOperand(dbgs());
+    LLVM_DEBUG(dbgs() << "GVN: non-local load "; Load->printAsOperand(dbgs());
                dbgs() << " has unknown dependencies\n";);
     return false;
   }
 
   bool Changed = false;
   // If this load follows a GEP, see if we can PRE the indices before analyzing.
-  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0))) {
+  if (GetElementPtrInst *GEP =
+          dyn_cast<GetElementPtrInst>(Load->getOperand(0))) {
     for (GetElementPtrInst::op_iterator OI = GEP->idx_begin(),
                                         OE = GEP->idx_end();
          OI != OE; ++OI)
@@ -1483,7 +1632,7 @@ bool GVN::processNonLocalLoad(LoadInst *LI) {
   // Step 2: Analyze the availability of the load
   AvailValInBlkVect ValuesPerBlock;
   UnavailBlkVect UnavailableBlocks;
-  AnalyzeLoadAvailability(LI, Deps, ValuesPerBlock, UnavailableBlocks);
+  AnalyzeLoadAvailability(Load, Deps, ValuesPerBlock, UnavailableBlocks);
 
   // If we have no predecessors that produce a known value for this load, exit
   // early.
@@ -1496,36 +1645,36 @@ bool GVN::processNonLocalLoad(LoadInst *LI) {
   // load, then it is fully redundant and we can use PHI insertion to compute
   // its value.  Insert PHIs and remove the fully redundant value now.
   if (UnavailableBlocks.empty()) {
-    LLVM_DEBUG(dbgs() << "GVN REMOVING NONLOCAL LOAD: " << *LI << '\n');
+    LLVM_DEBUG(dbgs() << "GVN REMOVING NONLOCAL LOAD: " << *Load << '\n');
 
     // Perform PHI construction.
-    Value *V = ConstructSSAForLoadSet(LI, ValuesPerBlock, *this);
-    LI->replaceAllUsesWith(V);
+    Value *V = ConstructSSAForLoadSet(Load, ValuesPerBlock, *this);
+    Load->replaceAllUsesWith(V);
 
     if (isa<PHINode>(V))
-      V->takeName(LI);
+      V->takeName(Load);
     if (Instruction *I = dyn_cast<Instruction>(V))
       // If instruction I has debug info, then we should not update it.
       // Also, if I has a null DebugLoc, then it is still potentially incorrect
-      // to propagate LI's DebugLoc because LI may not post-dominate I.
-      if (LI->getDebugLoc() && LI->getParent() == I->getParent())
-        I->setDebugLoc(LI->getDebugLoc());
+      // to propagate Load's DebugLoc because Load may not post-dominate I.
+      if (Load->getDebugLoc() && Load->getParent() == I->getParent())
+        I->setDebugLoc(Load->getDebugLoc());
     if (V->getType()->isPtrOrPtrVectorTy())
       MD->invalidateCachedPointerInfo(V);
-    markInstructionForDeletion(LI);
+    markInstructionForDeletion(Load);
     ++NumGVNLoad;
-    reportLoadElim(LI, V, ORE);
+    reportLoadElim(Load, V, ORE);
     return true;
   }
 
   // Step 4: Eliminate partial redundancy.
   if (!isPREEnabled() || !isLoadPREEnabled())
     return Changed;
-  if (!isLoadInLoopPREEnabled() && this->LI &&
-      this->LI->getLoopFor(LI->getParent()))
+  if (!isLoadInLoopPREEnabled() && LI && LI->getLoopFor(Load->getParent()))
     return Changed;
 
-  return Changed || PerformLoadPRE(LI, ValuesPerBlock, UnavailableBlocks);
+  return Changed || PerformLoadPRE(Load, ValuesPerBlock, UnavailableBlocks) ||
+         performLoopLoadPRE(Load, ValuesPerBlock, UnavailableBlocks);
 }
 
 static bool impliesEquivalanceIfTrue(CmpInst* Cmp) {
@@ -1589,9 +1738,7 @@ static bool hasUsersIn(Value *V, BasicBlock *BB) {
   return false;
 }
 
-bool GVN::processAssumeIntrinsic(IntrinsicInst *IntrinsicI) {
-  assert(IntrinsicI->getIntrinsicID() == Intrinsic::assume &&
-         "This function can only be called with llvm.assume intrinsic");
+bool GVN::processAssumeIntrinsic(AssumeInst *IntrinsicI) {
   Value *V = IntrinsicI->getArgOperand(0);
 
   if (ConstantInt *Cond = dyn_cast<ConstantInt>(V)) {
@@ -1776,7 +1923,7 @@ bool GVN::processLoad(LoadInst *L) {
       MSSAU->removeMemoryAccess(L);
     ++NumGVNLoad;
     reportLoadElim(L, AvailableValue, ORE);
-    // Tell MDA to rexamine the reused pointer since we might have more
+    // Tell MDA to reexamine the reused pointer since we might have more
     // information after forwarding it.
     if (MD && AvailableValue->getType()->isPtrOrPtrVectorTy())
       MD->invalidateCachedPointerInfo(AvailableValue);
@@ -1852,8 +1999,8 @@ bool GVN::ValueTable::areCallValsEqual(uint32_t Num, uint32_t NewNum,
       MD->getNonLocalCallDependency(Call);
 
   // Check to see if the Call has no function local clobber.
-  for (unsigned i = 0; i < deps.size(); i++) {
-    if (deps[i].getResult().isNonFuncLocal())
+  for (const NonLocalDepEntry &D : deps) {
+    if (D.getResult().isNonFuncLocal())
       return true;
   }
   return false;
@@ -2157,6 +2304,9 @@ bool GVN::processInstruction(Instruction *I) {
   if (Value *V = SimplifyInstruction(I, {DL, TLI, DT, AC})) {
     bool Changed = false;
     if (!I->use_empty()) {
+      // Simplification can cause a special instruction to become not special.
+      // For example, devirtualization to a willreturn function.
+      ICF->removeUsersOf(I);
       I->replaceAllUsesWith(V);
       Changed = true;
     }
@@ -2172,16 +2322,15 @@ bool GVN::processInstruction(Instruction *I) {
     }
   }
 
-  if (IntrinsicInst *IntrinsicI = dyn_cast<IntrinsicInst>(I))
-    if (IntrinsicI->getIntrinsicID() == Intrinsic::assume)
-      return processAssumeIntrinsic(IntrinsicI);
+  if (auto *Assume = dyn_cast<AssumeInst>(I))
+    return processAssumeIntrinsic(Assume);
 
-  if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
-    if (processLoad(LI))
+  if (LoadInst *Load = dyn_cast<LoadInst>(I)) {
+    if (processLoad(Load))
       return true;
 
-    unsigned Num = VN.lookupOrAdd(LI);
-    addToLeaderTable(Num, LI, LI->getParent());
+    unsigned Num = VN.lookupOrAdd(Load);
+    addToLeaderTable(Num, Load, Load->getParent());
     return false;
   }
 
@@ -2365,6 +2514,12 @@ bool GVN::processBlock(BasicBlock *BB) {
   ReplaceOperandsWithMap.clear();
   bool ChangedFunction = false;
 
+  // Since we may not have visited the input blocks of the phis, we can't
+  // use our normal hash approach for phis.  Instead, simply look for
+  // obvious duplicates.  The first pass of GVN will tend to create
+  // identical phis, and the second or later passes can eliminate them.
+  ChangedFunction |= EliminateDuplicatePHINodes(BB);
+
   for (BasicBlock::iterator BI = BB->begin(), BE = BB->end();
        BI != BE;) {
     if (!ReplaceOperandsWithMap.empty())
@@ -2447,6 +2602,8 @@ bool GVN::performScalarPREInsertion(Instruction *Instr, BasicBlock *Pred,
   Instr->setName(Instr->getName() + ".pre");
   Instr->setDebugLoc(Instr->getDebugLoc());
 
+  ICF->insertInstructionTo(Instr, Pred);
+
   unsigned Num = VN.lookupOrAdd(Instr);
   VN.add(Instr, Num);
 
@@ -2735,9 +2892,8 @@ void GVN::verifyRemoved(const Instruction *Inst) const {
 
   // Walk through the value number scope to make sure the instruction isn't
   // ferreted away in it.
-  for (DenseMap<uint32_t, LeaderTableEntry>::const_iterator
-       I = LeaderTable.begin(), E = LeaderTable.end(); I != E; ++I) {
-    const LeaderTableEntry *Node = &I->second;
+  for (const auto &I : LeaderTable) {
+    const LeaderTableEntry *Node = &I.second;
     assert(Node->Val != Inst && "Inst still in value numbering scope!");
 
     while (Node->Next) {
@@ -2795,9 +2951,7 @@ void GVN::addDeadBlock(BasicBlock *BB) {
 
   // For the dead blocks' live successors, update their phi nodes by replacing
   // the operands corresponding to dead blocks with UndefVal.
-  for(SmallSetVector<BasicBlock *, 4>::iterator I = DF.begin(), E = DF.end();
-        I != E; I++) {
-    BasicBlock *B = *I;
+  for (BasicBlock *B : DF) {
     if (DeadBlocks.count(B))
       continue;