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
@@ -59,7 +59,13 @@
   std::string ContextHash;
 
   bool operator==(const ModuleID &Other) const {
-    return ModuleName == Other.ModuleName && ContextHash == Other.ContextHash;
+    return std::tie(ModuleName, ContextHash) ==
+           std::tie(Other.ModuleName, Other.ContextHash);
+  }
+
+  bool operator<(const ModuleID& Other) const {
+    return std::tie(ModuleName, ContextHash) <
+           std::tie(Other.ModuleName, Other.ContextHash);
   }
 };
 
diff --git a/clang/tools/clang-scan-deps/ClangScanDeps.cpp b/clang/tools/clang-scan-deps/ClangScanDeps.cpp
--- a/clang/tools/clang-scan-deps/ClangScanDeps.cpp
+++ b/clang/tools/clang-scan-deps/ClangScanDeps.cpp
@@ -323,11 +323,10 @@
   return llvm::json::Array(Strings);
 }
 
+// Technically, we don't need to sort the dependency list to get determinism.
+// Leaving these be will simply preserve the import order.
 static llvm::json::Array toJSONSorted(std::vector<ModuleID> V) {
-  llvm::sort(V, [](const ModuleID &A, const ModuleID &B) {
-    return std::tie(A.ModuleName, A.ContextHash) <
-           std::tie(B.ModuleName, B.ContextHash);
-  });
+  llvm::sort(V);
 
   llvm::json::Array Ret;
   for (const ModuleID &MID : V)
@@ -406,11 +405,7 @@
     std::vector<IndexedModuleID> ModuleIDs;
     for (auto &&M : Modules)
       ModuleIDs.push_back(M.first);
-    llvm::sort(ModuleIDs,
-               [](const IndexedModuleID &A, const IndexedModuleID &B) {
-                 return std::tie(A.ID.ModuleName, A.InputIndex) <
-                        std::tie(B.ID.ModuleName, B.InputIndex);
-               });
+    llvm::sort(ModuleIDs);
 
     using namespace llvm::json;
 
@@ -470,20 +465,37 @@
 private:
   struct IndexedModuleID {
     ModuleID ID;
+
+    // FIXME: This is mutable so that it can still be updated after insertion
+    //  into an unordered associative container. This is "fine", since this
+    //  field doesn't contribute to the hash, but it's a brittle hack.
     mutable size_t InputIndex;
 
     bool operator==(const IndexedModuleID &Other) const {
-      return ID.ModuleName == Other.ID.ModuleName &&
-             ID.ContextHash == Other.ID.ContextHash;
+      return std::tie(ID.ModuleName, ID.ContextHash) ==
+             std::tie(Other.ID.ModuleName, Other.ID.ContextHash);
     }
-  };
-
-  struct IndexedModuleIDHasher {
-    std::size_t operator()(const IndexedModuleID &IMID) const {
-      using llvm::hash_combine;
 
-      return hash_combine(IMID.ID.ModuleName, IMID.ID.ContextHash);
+    bool operator<(const IndexedModuleID &Other) const {
+      /// We need the output of clang-scan-deps to be deterministic. However,
+      /// the dependency graph may contain two modules with the same name. How
+      /// do we decide which one to print first? If we made that decision based
+      /// on the context hash, the ordering would be deterministic, but
+      /// different across machines. This can happen for example when the inputs
+      /// or the SDKs (which both contribute to the "context" hash) live in
+      /// different absolute locations. We solve that by tracking the index of
+      /// the first input TU that (transitively) imports the dependency, which
+      /// is always the same for the same input, resulting in deterministic
+      /// sorting that's also reproducible across machines.
+      return std::tie(ID.ModuleName, InputIndex) <
+             std::tie(Other.ID.ModuleName, Other.InputIndex);
     }
+
+    struct Hasher {
+      std::size_t operator()(const IndexedModuleID &IMID) const {
+        return llvm::hash_combine(IMID.ID.ModuleName, IMID.ID.ContextHash);
+      }
+    };
   };
 
   struct InputDeps {
@@ -496,7 +508,7 @@
   };
 
   std::mutex Lock;
-  std::unordered_map<IndexedModuleID, ModuleDeps, IndexedModuleIDHasher>
+  std::unordered_map<IndexedModuleID, ModuleDeps, IndexedModuleID::Hasher>
       Modules;
   std::vector<InputDeps> Inputs;
 };