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
@@ -317,13 +317,28 @@
   return MD.ID;
 }
 
+static void forEachSubmoduleSorted(const Module *M,
+                                   llvm::function_ref<void(const Module *)> F) {
+  // Submodule order depends on order of header includes for inferred submodules
+  // we don't care about the exact order, so sort so that it's consistent across
+  // TUs to improve sharing.
+  SmallVector<const Module *> Submodules(M->submodule_begin(),
+                                         M->submodule_end());
+  llvm::stable_sort(Submodules, [](const Module *A, const Module *B) {
+    return A->Name < B->Name;
+  });
+  for (const Module *SubM : Submodules)
+    F(SubM);
+}
+
 void ModuleDepCollectorPP::addAllSubmodulePrebuiltDeps(
     const Module *M, ModuleDeps &MD,
     llvm::DenseSet<const Module *> &SeenSubmodules) {
   addModulePrebuiltDeps(M, MD, SeenSubmodules);
 
-  for (const Module *SubM : M->submodules())
+  forEachSubmoduleSorted(M, [&](const Module *SubM) {
     addAllSubmodulePrebuiltDeps(SubM, MD, SeenSubmodules);
+  });
 }
 
 void ModuleDepCollectorPP::addModulePrebuiltDeps(
@@ -341,8 +356,9 @@
     llvm::DenseSet<const Module *> &AddedModules) {
   addModuleDep(M, MD, AddedModules);
 
-  for (const Module *SubM : M->submodules())
+  forEachSubmoduleSorted(M, [&](const Module *SubM) {
     addAllSubmoduleDeps(SubM, MD, AddedModules);
+  });
 }
 
 void ModuleDepCollectorPP::addModuleDep(
diff --git a/clang/test/ClangScanDeps/submodule-order.c b/clang/test/ClangScanDeps/submodule-order.c
new file mode 100644
--- /dev/null
+++ b/clang/test/ClangScanDeps/submodule-order.c
@@ -0,0 +1,56 @@
+// RUN: rm -rf %t
+// RUN: split-file %s %t
+// RUN: sed "s|DIR|%/t|g" %t/cdb.json.template > %t/cdb.json
+// RUN: clang-scan-deps -compilation-database %t/cdb.json -format experimental-full -generate-modules-path-args > %t/deps1.json
+// RUN: mv %t/tu2.c %t/tu.c
+// RUN: clang-scan-deps -compilation-database %t/cdb.json -format experimental-full -generate-modules-path-args > %t/deps2.json
+// RUN: diff -u %t/deps1.json %t/deps2.json
+// RUN: FileCheck %s < %t/deps1.json
+
+// CHECK: "-fmodule-file={{.*}}Indirect1
+// CHECK-NOT: "-fmodule-file={{.*}}Indirect
+// CHECK: "-fmodule-file={{.*}}Indirect2
+// CHECK-NOT: "-fmodule-file={{.*}}Indirect
+
+//--- cdb.json.template
+[{
+  "directory": "DIR",
+  "command": "clang -fsyntax-only DIR/tu.c -fmodules -fimplicit-module-maps -fmodules-cache-path=DIR/cache",
+  "file": "DIR/tu.c"
+}]
+
+//--- module.modulemap
+module Indirect1 { header "Indirect1.h" }
+module Indirect2 { header "Indirect2.h" }
+module Mod {
+  umbrella "Mod"
+  module * { export * }
+}
+
+//--- Indirect1.h
+void indirect1(void);
+
+//--- Indirect2.h
+void indirect2(void);
+
+//--- Mod/SubMod1.h
+#include "../Indirect1.h"
+
+//--- Mod/SubMod2.h
+#include "../Indirect2.h"
+
+//--- tu.c
+#include "Mod/SubMod1.h"
+#include "Mod/SubMod2.h"
+void tu1(void) {
+  indirect1();
+  indirect2();
+}
+
+//--- tu2.c
+#include "Mod/SubMod2.h"
+#include "Mod/SubMod1.h"
+void tu1(void) {
+  indirect1();
+  indirect2();
+}
\ No newline at end of file