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_gram2_memssa.ll
===================================================================
--- /dev/null
+++ test/Transforms/EarlyCSE/reduced_gram2_memssa.ll
@@ -0,0 +1,20 @@
+;RUN: opt < %s -early-cse-memssa -verify-memoryssa -disable-output
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.Grammar = type { i8*, i8*, %struct.anon }
+%struct.anon = type { i32, i32, %struct.Term**, [3 x %struct.Term*] }
+%struct.Term = type { i32 }
+
+define dso_local fastcc void @new_term_string(%struct.Grammar* %g) unnamed_addr {
+entry:
+  store i8* undef, i8** undef, align 8
+  %0 = load i8*, i8** undef, align 8
+  %arrayidx = getelementptr inbounds i8, i8* %0, i64 undef
+  store i8 0, i8* %arrayidx, align 1
+  %v = getelementptr inbounds %struct.Grammar, %struct.Grammar* %g, i64 0, i32 2, i32 2
+  %1 = load %struct.Term**, %struct.Term*** %v, align 8
+  unreachable
+}
+
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 -disable-output
+
+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
+}
+
Index: test/Transforms/EarlyCSE/reduced_macroblock_memssa.ll
===================================================================
--- /dev/null
+++ test/Transforms/EarlyCSE/reduced_macroblock_memssa.ll
@@ -0,0 +1,29 @@
+; RUN: opt < %s -early-cse-memssa -verify-memoryssa -disable-output
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.ImageParameters = type { i32, i32, i32 }
+
+@img = external dso_local local_unnamed_addr global %struct.ImageParameters*, align 8
+
+; Function Attrs: nounwind uwtable
+define dso_local void @write_one_macroblock() local_unnamed_addr {
+entry:
+  ; MemoryUse(LoE)
+  %0 = load %struct.ImageParameters*, %struct.ImageParameters** @img, align 8
+
+  %Pos_2 = getelementptr inbounds %struct.ImageParameters, %struct.ImageParameters* %0, i64 0, i32 2
+  ; 1 = MemoryDef(LoE)
+  store i32 undef, i32* %Pos_2, align 8
+
+  ; MemoryUse(LoE)
+  %1 = load %struct.ImageParameters*, %struct.ImageParameters** @img, align 8
+
+  %Pos_1 = getelementptr inbounds %struct.ImageParameters, %struct.ImageParameters* %1, i64 0, i32 1
+  ; MemoryUse(1) MayAlias
+  %2 = load i32, i32* %Pos_1, align 4
+  unreachable
+}
+
+