Index: include/llvm/Analysis/LazyValueInfo.h
===================================================================
--- include/llvm/Analysis/LazyValueInfo.h
+++ include/llvm/Analysis/LazyValueInfo.h
@@ -103,6 +103,9 @@
   /// PredBB to OldSucc to be from PredBB to NewSucc instead.
   void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc);
 
+  /// Inform the analysis cache that we have erased a value.
+  void eraseValue(Value *V);
+
   /// Inform the analysis cache that we have erased a block.
   void eraseBlock(BasicBlock *BB);
 
Index: lib/Analysis/LazyValueInfo.cpp
===================================================================
--- lib/Analysis/LazyValueInfo.cpp
+++ lib/Analysis/LazyValueInfo.cpp
@@ -466,6 +466,11 @@
       TheCache.eraseBlock(BB);
     }
 
+    /// Inform the cache that a value has been deleted.
+    void eraseValue(Value *V) {
+      TheCache.eraseValue(V);
+    }
+
     /// Disables use of the DominatorTree within LVI.
     void disableDT() {
       if (DT) {
@@ -1812,6 +1817,12 @@
   }
 }
 
+void LazyValueInfo::eraseValue(Value *V) {
+  if (PImpl) {
+    getImpl(PImpl, AC, DL, DT).eraseValue(V);
+  }
+}
+
 void LazyValueInfo::eraseBlock(BasicBlock *BB) {
   if (PImpl) {
     const DataLayout &DL = BB->getModule()->getDataLayout();
Index: lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
===================================================================
--- lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
+++ lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
@@ -83,6 +83,7 @@
       AU.addRequired<LazyValueInfoWrapperPass>();
       AU.addPreserved<GlobalsAAWrapperPass>();
       AU.addPreserved<DominatorTreeWrapperPass>();
+      AU.addPreserved<LazyValueInfoWrapperPass>();
     }
   };
 
@@ -118,6 +119,7 @@
   if (ReplaceWith == S) ReplaceWith = UndefValue::get(S->getType());
 
   S->replaceAllUsesWith(ReplaceWith);
+  LVI->eraseValue(S);
   S->eraseFromParent();
 
   ++NumSelects;
@@ -176,6 +178,7 @@
   // All constant incoming values map to the same variable along the incoming
   // edges of the phi. The phi is unnecessary.
   P->replaceAllUsesWith(CommonValue);
+  LVI->eraseValue(P);
   P->eraseFromParent();
   ++NumPhiCommon;
   return true;
@@ -238,6 +241,7 @@
 
   if (Value *V = SimplifyInstruction(P, SQ)) {
     P->replaceAllUsesWith(V);
+    LVI->eraseValue(P);
     P->eraseFromParent();
     Changed = true;
   }
@@ -295,6 +299,7 @@
   ++NumCmps;
   Constant *TorF = ConstantInt::get(Type::getInt1Ty(Cmp->getContext()), Result);
   Cmp->replaceAllUsesWith(TorF);
+  LVI->eraseValue(Cmp);
   Cmp->eraseFromParent();
   return true;
 }
@@ -428,7 +433,7 @@
   return false;
 }
 
-static void processOverflowIntrinsic(IntrinsicInst *II) {
+static void processOverflowIntrinsic(IntrinsicInst *II, LazyValueInfo *LVI) {
   IRBuilder<> B(II);
   Value *NewOp = nullptr;
   switch (II->getIntrinsicID()) {
@@ -447,6 +452,7 @@
   Value *NewI = B.CreateInsertValue(UndefValue::get(II->getType()), NewOp, 0);
   NewI = B.CreateInsertValue(NewI, ConstantInt::getFalse(II->getContext()), 1);
   II->replaceAllUsesWith(NewI);
+  LVI->eraseValue(II);
   II->eraseFromParent();
 }
 
@@ -457,7 +463,7 @@
 
   if (auto *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
     if (willNotOverflow(II, LVI)) {
-      processOverflowIntrinsic(II);
+      processOverflowIntrinsic(II, LVI);
       return true;
     }
   }
@@ -562,6 +568,7 @@
       BinOp->setIsExact(Instr->isExact());
 
   Instr->replaceAllUsesWith(Zext);
+  LVI->eraseValue(Instr);
   Instr->eraseFromParent();
   return true;
 }
@@ -575,6 +582,7 @@
                                         SDI->getName(), SDI);
   BO->setDebugLoc(SDI->getDebugLoc());
   SDI->replaceAllUsesWith(BO);
+  LVI->eraseValue(SDI);
   SDI->eraseFromParent();
 
   // Try to process our new urem.
@@ -598,6 +606,7 @@
   BO->setDebugLoc(SDI->getDebugLoc());
   BO->setIsExact(SDI->isExact());
   SDI->replaceAllUsesWith(BO);
+  LVI->eraseValue(SDI);
   SDI->eraseFromParent();
 
   // Try to simplify our new udiv.
@@ -621,6 +630,7 @@
   BO->setDebugLoc(SDI->getDebugLoc());
   BO->setIsExact(SDI->isExact());
   SDI->replaceAllUsesWith(BO);
+  LVI->eraseValue(SDI);
   SDI->eraseFromParent();
 
   return true;
@@ -802,5 +812,6 @@
   PreservedAnalyses PA;
   PA.preserve<GlobalsAA>();
   PA.preserve<DominatorTreeAnalysis>();
+  PA.preserve<LazyValueAnalysis>();
   return PA;
 }