diff --git a/clang/include/clang/Tooling/DependencyScanning/ModuleDepCollector.h b/clang/include/clang/Tooling/DependencyScanning/ModuleDepCollector.h
--- a/clang/include/clang/Tooling/DependencyScanning/ModuleDepCollector.h
+++ b/clang/include/clang/Tooling/DependencyScanning/ModuleDepCollector.h
@@ -149,9 +149,9 @@
   /// The parent dependency collector.
   ModuleDepCollector &MDC;
   /// Working set of direct modular dependencies.
-  llvm::DenseSet<const Module *> DirectModularDeps;
+  llvm::SetVector<const Module *> DirectModularDeps;
   /// Working set of direct modular dependencies that have already been built.
-  llvm::DenseSet<const Module *> DirectPrebuiltModularDeps;
+  llvm::SetVector<const Module *> DirectPrebuiltModularDeps;
 
   void handleImport(const Module *Imported);
 
@@ -199,7 +199,7 @@
   /// textually included header files.
   std::vector<std::string> FileDeps;
   /// Direct and transitive modular dependencies of the main source file.
-  std::unordered_map<const Module *, ModuleDeps> ModularDeps;
+  llvm::MapVector<const Module *, std::unique_ptr<ModuleDeps>> ModularDeps;
   /// Options that control the dependency output generation.
   std::unique_ptr<DependencyOutputOptions> Opts;
   /// The original Clang invocation passed to dependency scanner.
diff --git a/clang/lib/Tooling/DependencyScanning/DependencyScanningTool.cpp b/clang/lib/Tooling/DependencyScanning/DependencyScanningTool.cpp
--- a/clang/lib/Tooling/DependencyScanning/DependencyScanningTool.cpp
+++ b/clang/lib/Tooling/DependencyScanning/DependencyScanningTool.cpp
@@ -133,7 +133,9 @@
     }
 
     void handleModuleDependency(ModuleDeps MD) override {
-      ClangModuleDeps[MD.ID.ContextHash + MD.ID.ModuleName] = std::move(MD);
+      ClangModuleDeps.insert(
+          std::make_pair(MD.ID.ContextHash + MD.ID.ModuleName,
+                         std::make_unique<ModuleDeps>(std::move(MD))));
     }
 
     void handleContextHash(std::string Hash) override {
@@ -152,7 +154,7 @@
       FD.FileDeps.assign(Dependencies.begin(), Dependencies.end());
 
       for (auto &&M : ClangModuleDeps) {
-        auto &MD = M.second;
+        auto &MD = *M.second;
         if (MD.ImportedByMainFile)
           FD.ClangModuleDeps.push_back(MD.ID);
       }
@@ -166,7 +168,7 @@
         //   we've already seen.
         if (AlreadySeen.count(M.first))
           continue;
-        FDR.DiscoveredModules.push_back(std::move(M.second));
+        FDR.DiscoveredModules.push_back(std::move(*M.second));
       }
 
       FDR.FullDeps = std::move(FD);
@@ -176,7 +178,9 @@
   private:
     std::vector<std::string> Dependencies;
     std::vector<PrebuiltModuleDep> PrebuiltModuleDeps;
-    std::map<std::string, ModuleDeps> ClangModuleDeps;
+    llvm::MapVector<std::string, std::unique_ptr<ModuleDeps>,
+                    llvm::StringMap<unsigned>>
+        ClangModuleDeps;
     std::string ContextHash;
     std::vector<std::string> OutputPaths;
     const llvm::StringSet<> &AlreadySeen;
diff --git a/clang/lib/Tooling/DependencyScanning/ModuleDepCollector.cpp b/clang/lib/Tooling/DependencyScanning/ModuleDepCollector.cpp
--- a/clang/lib/Tooling/DependencyScanning/ModuleDepCollector.cpp
+++ b/clang/lib/Tooling/DependencyScanning/ModuleDepCollector.cpp
@@ -199,7 +199,7 @@
   MDC.Consumer.handleDependencyOutputOpts(*MDC.Opts);
 
   for (auto &&I : MDC.ModularDeps)
-    MDC.Consumer.handleModuleDependency(I.second);
+    MDC.Consumer.handleModuleDependency(*I.second);
 
   for (auto &&I : MDC.FileDeps)
     MDC.Consumer.handleFileDependency(I);
@@ -212,11 +212,12 @@
   assert(M == M->getTopLevelModule() && "Expected top level module!");
 
   // If this module has been handled already, just return its ID.
-  auto ModI = MDC.ModularDeps.insert({M, ModuleDeps{}});
+  auto ModI = MDC.ModularDeps.insert({M, nullptr});
   if (!ModI.second)
-    return ModI.first->second.ID;
+    return ModI.first->second->ID;
 
-  ModuleDeps &MD = ModI.first->second;
+  ModI.first->second = std::make_unique<ModuleDeps>();
+  ModuleDeps &MD = *ModI.first->second;
 
   MD.ID.ModuleName = M->getFullModuleName();
   MD.ImportedByMainFile = DirectModularDeps.contains(M);