diff --git a/clang/include/clang/Tooling/DependencyScanning/DependencyScanningTool.h b/clang/include/clang/Tooling/DependencyScanning/DependencyScanningTool.h
--- a/clang/include/clang/Tooling/DependencyScanning/DependencyScanningTool.h
+++ b/clang/include/clang/Tooling/DependencyScanning/DependencyScanningTool.h
@@ -158,6 +158,10 @@
     PrebuiltModuleDeps.emplace_back(std::move(PMD));
   }
 
+  bool alreadySeenModuleDependency(ModuleID ID) override {
+    return AlreadySeen.contains(ID);
+  }
+
   void handleModuleDependency(ModuleDeps MD) override {
     ClangModuleDeps[MD.ID] = std::move(MD);
   }
diff --git a/clang/include/clang/Tooling/DependencyScanning/DependencyScanningWorker.h b/clang/include/clang/Tooling/DependencyScanning/DependencyScanningWorker.h
--- a/clang/include/clang/Tooling/DependencyScanning/DependencyScanningWorker.h
+++ b/clang/include/clang/Tooling/DependencyScanning/DependencyScanningWorker.h
@@ -54,6 +54,8 @@
 
   virtual void handlePrebuiltModuleDependency(PrebuiltModuleDep PMD) = 0;
 
+  virtual bool alreadySeenModuleDependency(ModuleID ID) { return false; }
+
   virtual void handleModuleDependency(ModuleDeps MD) = 0;
 
   virtual void handleDirectModuleDependency(ModuleID MD) = 0;
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
@@ -172,15 +172,7 @@
   TU.FileDeps = std::move(Dependencies);
   TU.PrebuiltModuleDeps = std::move(PrebuiltModuleDeps);
   TU.Commands = std::move(Commands);
-
-  for (auto &&M : ClangModuleDeps) {
-    auto &MD = M.second;
-    // TODO: Avoid handleModuleDependency even being called for modules
-    //   we've already seen.
-    if (AlreadySeen.count(M.first))
-      continue;
-    TU.ModuleGraph.push_back(std::move(MD));
-  }
+  TU.ModuleGraph = takeModuleGraphDeps();
   TU.ClangModuleDeps = std::move(DirectModuleDeps);
 
   return TU;
@@ -189,14 +181,8 @@
 ModuleDepsGraph FullDependencyConsumer::takeModuleGraphDeps() {
   ModuleDepsGraph ModuleGraph;
 
-  for (auto &&M : ClangModuleDeps) {
-    auto &MD = M.second;
-    // TODO: Avoid handleModuleDependency even being called for modules
-    //   we've already seen.
-    if (AlreadySeen.count(M.first))
-      continue;
+  for (auto &&[ID, MD] : ClangModuleDeps)
     ModuleGraph.push_back(std::move(MD));
-  }
 
   return ModuleGraph;
 }
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
@@ -406,7 +406,8 @@
         MDC.ProvidedStdCXXModule, MDC.RequiredStdCXXModules);
 
   for (auto &&I : MDC.ModularDeps)
-    MDC.Consumer.handleModuleDependency(*I.second);
+    if (!MDC.Consumer.alreadySeenModuleDependency(I.second->ID))
+      MDC.Consumer.handleModuleDependency(*I.second);
 
   for (const Module *M : MDC.DirectModularDeps) {
     auto It = MDC.ModularDeps.find(M);
@@ -458,19 +459,6 @@
   serialization::ModuleFile *MF =
       MDC.ScanInstance.getASTReader()->getModuleManager().lookup(
           M->getASTFile());
-  MDC.ScanInstance.getASTReader()->visitInputFiles(
-      *MF, true, true, [&](const serialization::InputFile &IF, bool isSystem) {
-        // __inferred_module.map is the result of the way in which an implicit
-        // module build handles inferred modules. It adds an overlay VFS with
-        // this file in the proper directory and relies on the rest of Clang to
-        // handle it like normal. With explicitly built modules we don't need
-        // to play VFS tricks, so replace it with the correct module map.
-        if (IF.getFile()->getName().endswith("__inferred_module.map")) {
-          MDC.addFileDep(MD, ModuleMap->getName());
-          return;
-        }
-        MDC.addFileDep(MD, IF.getFile()->getName());
-      });
 
   llvm::DenseSet<const Module *> SeenDeps;
   addAllSubmodulePrebuiltDeps(M, MD, SeenDeps);
@@ -493,11 +481,28 @@
 
   MDC.associateWithContextHash(CI, MD);
 
+  if (MDC.Consumer.alreadySeenModuleDependency(MD.ID))
+    return MD.ID;
+
   // Finish the compiler invocation. Requires dependencies and the context hash.
   MDC.addOutputPaths(CI, MD);
 
   MD.BuildArguments = CI.getCC1CommandLine();
 
+  MDC.ScanInstance.getASTReader()->visitInputFiles(
+      *MF, true, true, [&](const serialization::InputFile &IF, bool isSystem) {
+        // __inferred_module.map is the result of the way in which an implicit
+        // module build handles inferred modules. It adds an overlay VFS with
+        // this file in the proper directory and relies on the rest of Clang to
+        // handle it like normal. With explicitly built modules we don't need
+        // to play VFS tricks, so replace it with the correct module map.
+        if (IF.getFile()->getName().endswith("__inferred_module.map")) {
+          MDC.addFileDep(MD, ModuleMap->getName());
+          return;
+        }
+        MDC.addFileDep(MD, IF.getFile()->getName());
+      });
+
   return MD.ID;
 }