Index: lib/Transforms/Scalar/EarlyCSE.cpp
===================================================================
--- lib/Transforms/Scalar/EarlyCSE.cpp
+++ lib/Transforms/Scalar/EarlyCSE.cpp
@@ -604,6 +604,8 @@
   void removeMSSA(Instruction *Inst) {
     if (!MSSA)
       return;
+    if (VerifyMemorySSA)
+      MSSA->verifyMemorySSA();
     // Removing a store here can leave MemorySSA in an unoptimized state by
     // creating MemoryPhis that have identical arguments and by creating
     // MemoryUses whose defining access is not an actual clobber.  We handle the
@@ -636,6 +638,8 @@
         PhisToCheck.clear();
       }
     }
+    if (VerifyMemorySSA)
+      MSSA->verifyMemorySSA();
   }
 };
 
@@ -907,6 +911,8 @@
       } else {
         bool Killed = false;
         if (!Inst->use_empty()) {
+          if (MSSA)
+            MSSAUpdater->resetOptimizeUses(Inst);
           Inst->replaceAllUsesWith(V);
           Changed = true;
         }
@@ -935,6 +941,8 @@
         }
         if (auto *I = dyn_cast<Instruction>(V))
           I->andIRFlags(Inst);
+        if (MSSA)
+          MSSAUpdater->resetOptimizeUses(Inst);
         Inst->replaceAllUsesWith(V);
         removeMSSA(Inst);
         Inst->eraseFromParent();
@@ -994,8 +1002,11 @@
             LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
             continue;
           }
-          if (!Inst->use_empty())
+          if (!Inst->use_empty()) {
+            if (MSSA)
+              MSSAUpdater->resetOptimizeUses(Inst);
             Inst->replaceAllUsesWith(Op);
+          }
           removeMSSA(Inst);
           Inst->eraseFromParent();
           Changed = true;
@@ -1037,8 +1048,11 @@
           LLVM_DEBUG(dbgs() << "Skipping due to debug counter\n");
           continue;
         }
-        if (!Inst->use_empty())
+        if (!Inst->use_empty()) {
+          if (MSSA)
+            MSSAUpdater->resetOptimizeUses(Inst);
           Inst->replaceAllUsesWith(InVal.first);
+        }
         removeMSSA(Inst);
         Inst->eraseFromParent();
         Changed = true;
Index: test/Transforms/EarlyCSE/reduced_gram_memssa.ll
===================================================================
--- /dev/null
+++ test/Transforms/EarlyCSE/reduced_gram_memssa.ll
@@ -0,0 +1,16 @@
+; RUN: opt < %s -early-cse-memssa -verify-memoryssa -S | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.Term = type { i32, i32, i32, i32, i32, i8* }
+
+; Function Attrs: nounwind uwtable
+define dso_local fastcc void @new_term_string() unnamed_addr {
+entry:
+  %string = getelementptr inbounds %struct.Term, %struct.Term* undef, i64 0, i32 5
+  store i8* undef, i8** %string, align 8
+  %0 = load i8*, i8** %string, align 8
+  unreachable
+}
+