Index: include/llvm/Analysis/MemoryDependenceAnalysis.h
===================================================================
--- include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ 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/ValueMap.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;
+  ValueMap<Instruction *, NonLocalDepResult> NonLocalDefsCache;
 
   /// This map stores the cached results of doing a pointer lookup at the
   /// bottom of a block.
Index: include/llvm/IR/ValueMap.h
===================================================================
--- include/llvm/IR/ValueMap.h
+++ include/llvm/IR/ValueMap.h
@@ -106,6 +106,9 @@
       : Map(NumInitBuckets), Data() {}
   explicit ValueMap(const ExtraData &Data, unsigned NumInitBuckets = 64)
       : Map(NumInitBuckets), Data(Data) {}
+  ValueMap(ValueMap &&) noexcept = default;
+  ValueMap &operator=(ValueMap &&) noexcept = default;
+
   ValueMap(const ValueMap &) = delete;
   ValueMap &operator=(const ValueMap &) = delete;
 
Index: lib/Analysis/MemoryDependenceAnalysis.cpp
===================================================================
--- lib/Analysis/MemoryDependenceAnalysis.cpp
+++ lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -430,9 +430,10 @@
   // dependency won't be found then return nonLocal counting that the
   // user will call getNonLocalPointerDependency, which will return cached
   // result.
-  NonLocalDefsCache.try_emplace(
-      LI, NonLocalDepResult(ClosestDependency->getParent(),
-                            MemDepResult::getDef(ClosestDependency), nullptr));
+  NonLocalDefsCache.insert(
+    {LI, NonLocalDepResult(ClosestDependency->getParent(),
+                           MemDepResult::getDef(ClosestDependency),
+                           nullptr)});
   return MemDepResult::getNonLocal();
 }
 
@@ -919,9 +920,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));
@@ -1709,7 +1708,7 @@
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
-  return MemoryDependenceResults(AA, AC, TLI, DT);
+  return {AA, AC, TLI, DT};
 }
 
 char MemoryDependenceWrapperPass::ID = 0;