Index: llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h
===================================================================
--- llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -26,6 +26,7 @@
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/PredIteratorCache.h"
+#include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/ErrorHandling.h"
 #include <cassert>
@@ -314,7 +315,7 @@
   /// Cache storing single nonlocal def for the instruction.
   /// It is set when nonlocal def would be found in function returning only
   /// local dependencies.
-  DenseMap<Instruction *, NonLocalDepResult> NonLocalDefsCache;
+  DenseMap<AssertingVH<const Value>, NonLocalDepResult> NonLocalDefsCache;
 
   /// This map stores the cached results of doing a pointer lookup at the
   /// bottom of a block.
Index: llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
===================================================================
--- llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -919,9 +919,7 @@
          "Can't get pointer deps of a non-pointer!");
   Result.clear();
   {
-    // Check if there is cached Def with invariant.group. FIXME: cache might be
-    // invalid if cached instruction would be removed between call to
-    // getPointerDependencyFrom and this function.
+    // Check if there is cached Def with invariant.group.
     auto NonLocalDefIt = NonLocalDefsCache.find(QueryInst);
     if (NonLocalDefIt != NonLocalDefsCache.end()) {
       Result.push_back(std::move(NonLocalDefIt->second));
@@ -1459,9 +1457,23 @@
   return true;
 }
 
-/// If P exists in CachedNonLocalPointerInfo, remove it.
+/// If P exists in CachedNonLocalPointerInfo or NonLocalDefsCache, remove it.
 void MemoryDependenceResults::RemoveCachedNonLocalPointerDependencies(
     ValueIsLoadPair P) {
+
+  // Most of the time this cache is empty.
+  if (!NonLocalDefsCache.empty()) {
+    NonLocalDefsCache.erase(P.getPointer());
+    SmallVector<const Value *, 4> KeysToDelete;
+
+    // This cache should always be very small, thus it should be fast.
+    for (const auto &entry : NonLocalDefsCache)
+      if (entry.second.getAddress() == P.getPointer())
+        KeysToDelete.push_back(entry.first);
+    for (const auto *Key : KeysToDelete)
+      NonLocalDefsCache.erase(Key);
+  }
+
   CachedNonLocalPointerInfo::iterator It = NonLocalPointerDeps.find(P);
   if (It == NonLocalPointerDeps.end())
     return;