diff --git a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
--- a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -1518,15 +1518,25 @@
     LocalDeps.erase(LocalDepEntry);
   }
 
-  // If we have any cached pointer dependencies on this instruction, remove
-  // them.  If the instruction has non-pointer type, then it can't be a pointer
-  // base.
+  // If we have any cached dependencies on this instruction, remove
+  // them.
 
-  // Remove it from both the load info and the store info.  The instruction
-  // can't be in either of these maps if it is non-pointer.
+  // If the instruction is a pointer, remove it from both the load info and the
+  // store info.
   if (RemInst->getType()->isPointerTy()) {
     RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false));
     RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true));
+  } else {
+    // Otherwise, if the instructions is in the map directly, it must be a load.
+    // Remove it.
+    auto toRemoveIt = NonLocalDefsCache.find(RemInst);
+    if (toRemoveIt != NonLocalDefsCache.end()) {
+      assert(isa<LoadInst>(RemInst) &&
+             "only load instructions should be added directly");
+      const Instruction *DepV = toRemoveIt->second.getResult().getInst();
+      ReverseNonLocalDefsCache.find(DepV)->second.erase(RemInst);
+      NonLocalDefsCache.erase(toRemoveIt);
+    }
   }
 
   // Loop over all of the things that depend on the instruction we're removing.
diff --git a/llvm/test/Transforms/GVN/pr46054-md-nonlocaldefcache-cleanup.ll b/llvm/test/Transforms/GVN/pr46054-md-nonlocaldefcache-cleanup.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/GVN/pr46054-md-nonlocaldefcache-cleanup.ll
@@ -0,0 +1,81 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -gvn -S %s | FileCheck %s
+
+; Test for PR46054. Make sure we correctly invalidate MemoryDependenceAnalysis,
+; after removing a nonlocaldef.
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @test_double(double* %data) {
+; CHECK-LABEL: @test_double(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[LUC:%.*]] = tail call noalias nonnull i64* @data()
+; CHECK-NEXT:    store i64 1, i64* [[LUC]], align 8, !invariant.group !0
+; CHECK-NEXT:    call void @fn(i64 1)
+; CHECK-NEXT:    br i1 true, label [[A:%.*]], label [[ENTRY_B_CRIT_EDGE:%.*]]
+; CHECK:       entry.B_crit_edge:
+; CHECK-NEXT:    br label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    br label [[B]]
+; CHECK:       B:
+; CHECK-NEXT:    call void @fn(i64 1)
+; CHECK-NEXT:    ret void
+;
+entry:
+  %luc = tail call noalias nonnull i64* @data()
+  store i64 1, i64* %luc, !invariant.group !0
+  %QQ = load i64, i64* %luc, !invariant.group !0
+  call void @fn(i64 %QQ)
+  br i1 true, label %A, label %B
+
+A:                                                ; preds = %loop
+  br label %B
+
+B:                                                ; preds = %A, %loop
+  %QQ.1 = load i64, i64* %luc, !invariant.group !0
+  call void @fn(i64 %QQ.1)
+  ret void
+}
+
+declare void @fn(i64)
+
+declare noalias i64* @data()
+
+
+define void @test_double_ptr(double** %data) {
+; CHECK-LABEL: @test_double_ptr(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[LUC:%.*]] = tail call noalias nonnull i64** @data.ptr()
+; CHECK-NEXT:    store i64* null, i64** [[LUC]], align 8, !invariant.group !0
+; CHECK-NEXT:    call void @fn.ptr(i64* null)
+; CHECK-NEXT:    br i1 true, label [[A:%.*]], label [[ENTRY_B_CRIT_EDGE:%.*]]
+; CHECK:       entry.B_crit_edge:
+; CHECK-NEXT:    br label [[B:%.*]]
+; CHECK:       A:
+; CHECK-NEXT:    br label [[B]]
+; CHECK:       B:
+; CHECK-NEXT:    call void @fn.ptr(i64* null)
+; CHECK-NEXT:    ret void
+;
+entry:
+  %luc = tail call noalias nonnull i64** @data.ptr()
+  store i64* null, i64** %luc, !invariant.group !0
+  %QQ = load i64*, i64** %luc, !invariant.group !0
+  call void @fn.ptr(i64* %QQ)
+  br i1 true, label %A, label %B
+
+A:                                                ; preds = %loop
+  br label %B
+
+B:                                                ; preds = %A, %loop
+  %QQ.1 = load i64*, i64** %luc, !invariant.group !0
+  call void @fn.ptr(i64* %QQ.1)
+  ret void
+}
+
+
+declare void @fn.ptr(i64 *)
+
+declare noalias i64** @data.ptr()
+
+!0 = distinct !{}