[clang][deps] Include canonical invocation in ContextHash

[benlangmuir]

Summary

The "strict context hash" is insufficient to identify module
dependencies during scanning, leading to different module build commands
being produced for a single module, and non-deterministically choosing
between them. This commit switches to hashing the canonicalized
CompilerInvocation of the module. By hashing the invocation we are
converting these from correctness issues to performance issues, and we
can then incrementally improve our ability to canonicalize
command-lines.

This change can cause a regression in the number of modules needed. Of
the 4 projects I tested, 3 had no regression, but 1, which was
clang+llvm itself, had a 66% regression in number of modules (4%
regression in total invocations). This is almost entirely due to
differences between -W options across targets. Of this, 25% of the
additional modules are system modules, which we could avoid if we
canonicalized -W options when -Wsystem-headers is not present --
unfortunately this is non-trivial due to some warnings being enabled in
system headers by default. The rest of the additional modules are mostly
real differences in potential warnings, reflecting incorrect behaviour
in the current scanner.

There were also a couple of differences due to -DFOO
-fmodule-ignore-macro=FOO, which I fixed here.

Since the output paths for the module depend on its context hash, we
hash the invocation before filling in outputs, and rely on the build
system to always return the same output paths for a given module.

Note: since the scanner itself uses an implicit modules build, there can
still be non-determinism, but it will now present as different
module+hashes rather than different command-lines for the same
module+hash.

[jansvoboda11]

Would it make sense for this to replace the existing strict context hash implementation?

[benlangmuir]

In D129884#3677435, @jansvoboda11 wrote:

Would it make sense for this to replace the existing strict context hash implementation?

It's not clear to me whether this would be a good tradeoff or not: the explicit build canonicalizes its invocation, but the implicit build does not do so to the same extent. Some of that could be improved with some effort, but for example the optimizations we use for search path pruning in the explicit build cannot be done up-front in the implicit build, since we don't yet know which paths are relevant. I think we should consider this separately.

One necessary difference is that after scanning dependencies we want to hash the module dependencies (name + context hash), but we cannot do that in the implicit build since the dependencies are not discovered yet. The rest of the invocation hashing implementation could be shared though, if we decided it is the right approach.

[jansvoboda11]

Makes sense, thanks. LGTM provided you add brief explanation to each of the new tests.

[benlangmuir]

• Added comments to tests
• Added a missing test that I accidentally deleted
• Rebased on latest main

clang/include/clang/Tooling/DependencyScanning/ModuleDepCollector.h

 };
 
 /// This is used to identify a specific module.
 struct ModuleID {
   /// The name of the module. This may include `:` for C++20 module partitions,
   /// or a header-name for C++20 header units.
   std::string ModuleName;
 
-  /// The context hash of a module represents the set of compiler options that
-  /// may make one version of a module incompatible with another. This includes
-  /// things like language mode, predefined macros, header search paths, etc...
+  /// The context hash of a module represents the compiler options that affect
+  /// the resulting command-line invocation.
+  ///
+  /// Modules with the same name and ContextHash but different invocations could
+  /// cause non-deterministic build results.
   ///
   /// Modules with the same name but a different \c ContextHash should be
   /// treated as separate modules for the purpose of a build.
   std::string ContextHash;
 
   bool operator==(const ModuleID &Other) const {
     return ModuleName == Other.ModuleName && ContextHash == Other.ContextHash;
   }

clang/lib/Tooling/DependencyScanning/ModuleDepCollector.cpp

 //===- ModuleDepCollector.cpp - Callbacks to collect deps -------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Tooling/DependencyScanning/ModuleDepCollector.h"
 
 #include "clang/Basic/MakeSupport.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/DependencyScanning/DependencyScanningWorker.h"
+#include "llvm/Support/BLAKE3.h"
 #include "llvm/Support/StringSaver.h"
 
 using namespace clang;
 using namespace tooling;
 using namespace dependencies;
 
 static void optimizeHeaderSearchOpts(HeaderSearchOptions &Opts,
                                      ASTReader &Reader,
CompilerInvocation ModuleDepCollector::makeInvocationForModuleBuildWithoutPaths(
   CI.getHeaderSearchOpts().ModuleCachePath.clear();
   CI.getHeaderSearchOpts().ModulesValidateOncePerBuildSession = false;
   CI.getHeaderSearchOpts().BuildSessionTimestamp = 0;
   // The specific values we canonicalize to for pruning don't affect behaviour,
   /// so use the default values so they will be dropped from the command-line.
   CI.getHeaderSearchOpts().ModuleCachePruneInterval = 7 * 24 * 60 * 60;
   CI.getHeaderSearchOpts().ModuleCachePruneAfter = 31 * 24 * 60 * 60;
 
+  // Remove any macro definitions that are explicitly ignored.
+  if (!CI.getHeaderSearchOpts().ModulesIgnoreMacros.empty()) {
+    llvm::erase_if(
+        CI.getPreprocessorOpts().Macros,
+        [&CI](const std::pair<std::string, bool> &Def) {
+          StringRef MacroDef = Def.first;
+          return CI.getHeaderSearchOpts().ModulesIgnoreMacros.contains(
+              llvm::CachedHashString(MacroDef.split('=').first));
+        });
+    // Remove the now unused option.
+    CI.getHeaderSearchOpts().ModulesIgnoreMacros.clear();
+  }
+
   // Report the prebuilt modules this module uses.
   for (const auto &PrebuiltModule : Deps.PrebuiltModuleDeps)
     CI.getFrontendOpts().ModuleFiles.push_back(PrebuiltModule.PCMFile);
 
   CI.getFrontendOpts().ModuleMapFiles = Deps.ModuleMapFileDeps;
 
   Optimize(CI);
 
std::vector<std::string> ModuleDeps::getCanonicalCommandLine(
 
   for (ModuleID MID : ClangModuleDeps)
     FrontendOpts.ModuleFiles.push_back(
         LookupModuleOutput(MID, ModuleOutputKind::ModuleFile));
 
   return serializeCompilerInvocation(CI);
 }
 
+static std::string getModuleContextHash(const ModuleDeps &MD) {
+  llvm::HashBuilder<llvm::TruncatedBLAKE3<16>,
+                    llvm::support::endianness::native>
+      HashBuilder;
+  SmallString<32> Scratch;
+
+  // Hash the compiler version and serialization version to ensure the module
+  // will be readable.
+  HashBuilder.add(getClangFullRepositoryVersion());
+  HashBuilder.add(serialization::VERSION_MAJOR, serialization::VERSION_MINOR);
+
+  // Hash the BuildInvocation without any input files.
+  SmallVector<const char *, 32> DummyArgs;
+  MD.BuildInvocation.generateCC1CommandLine(DummyArgs, [&](const Twine &Arg) {
+    Scratch.clear();
+    StringRef Str = Arg.toStringRef(Scratch);
+    HashBuilder.add(Str);
+    return "<unused>";
+  });
+
+  // Hash the input file paths and module dependencies. These paths may differ
+  // even if the invocation is identical if they depend on the contents of the
+  // files in the TU -- for example, case-insensitive paths to modulemap files.
+  // Usually such a case would indicate a missed optimization to canonicalize,
+  // but it may be difficult to canonicalize all cases when there is a VFS.
+  HashBuilder.add(MD.ClangModuleMapFile);
+  for (const auto &Dep : MD.PrebuiltModuleDeps)
+    HashBuilder.add(Dep.PCMFile);
+  for (const auto &ID : MD.ClangModuleDeps) {
+    HashBuilder.add(ID.ModuleName);
+    HashBuilder.add(ID.ContextHash);
+  }
+
+  // Hash options that affect which callbacks are made for outputs.
+  HashBuilder.add(MD.HadDependencyFile);
+  HashBuilder.add(MD.HadSerializedDiagnostics);
+
+  llvm::BLAKE3Result<16> Hash = HashBuilder.final();
+  std::array<uint64_t, 2> Words;
+  static_assert(sizeof(Hash) == sizeof(Words), "Hash must match Words");
+  std::memcpy(Words.data(), Hash.data(), sizeof(Hash));
+  return toString(llvm::APInt(sizeof(Words) * 8, Words), 36, /*Signed=*/false);
+}
+
 std::vector<std::string>
 ModuleDeps::getCanonicalCommandLineWithoutModulePaths() const {
   return serializeCompilerInvocation(BuildInvocation);
 }
 
 void ModuleDepCollectorPP::FileChanged(SourceLocation Loc,
                                        FileChangeReason Reason,
                                        SrcMgr::CharacteristicKind FileType,
MD.BuildInvocation = MDC.makeInvocationForModuleBuildWithoutPaths(
         if (MDC.OptimizeArgs)
           optimizeHeaderSearchOpts(BuildInvocation.getHeaderSearchOpts(),
                                    *MDC.ScanInstance.getASTReader(), *MF);
       });
   MD.HadSerializedDiagnostics = !MDC.OriginalInvocation.getDiagnosticOpts()
                                      .DiagnosticSerializationFile.empty();
   MD.HadDependencyFile =
       !MDC.OriginalInvocation.getDependencyOutputOpts().OutputFile.empty();
-  // FIXME: HadSerializedDiagnostics and HadDependencyFile should be included in
-  // the context hash since it can affect the command-line.
-  MD.ID.ContextHash = MD.BuildInvocation.getModuleHash();
 
   llvm::DenseSet<const Module *> AddedModules;
   addAllSubmoduleDeps(M, MD, AddedModules);
 
+  // Do this last since it requires the dependencies.
+  MD.ID.ContextHash = getModuleContextHash(MD);
   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.

clang/test/ClangScanDeps/modules-context-hash-ignore-macros.c

+// 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 -j 1 \
+// RUN:   -format experimental-full > %t/deps.json
+// RUN: cat %t/deps.json | sed 's:\\\\\?:/:g' | FileCheck -DPREFIX=%/t %s
+
+// '-DFOO -fmodules-ignore-macro=FOO' is equivalent to ''.
+
+// CHECK:      {
+// CHECK-NEXT:   "modules": [
+// CHECK:          {
+// CHECK:            "command-line": [
+// CHECK-NOT:          "FOO"
+// CHECK-NOT:          "-fmodules-ignore-macro
+// CHECK:            ]
+// CHECK:            "context-hash": "[[HASH_NO_FOO:.*]]"
+// CHECK:            "name": "Mod"
+// CHECK-NEXT:     }
+// CHECK-NEXT:     {
+// CHECK:            "command-line": [
+// CHECK:              "-D"
+// CHECK-NEXT:         "FOO"
+// CHECK:            ]
+// CHECK:            "context-hash": "[[HASH_FOO:.*]]"
+// CHECK:            "name": "Mod"
+// CHECK-NEXT:     }
+// CHECK-NEXT:   ]
+// CHECK-NEXT:   "translation-units": [
+// CHECK-NEXT:     {
+// CHECK:            "clang-module-deps": [
+// CHECK-NEXT:         {
+// CHECK-NEXT:           "context-hash": "[[HASH_NO_FOO]]"
+// CHECK-NEXT:            "module-name": "Mod"
+// CHECK-NEXT:         }
+// CHECK-NEXT:       ]
+// CHECK-NEXT:       "command-line": [
+// CHECK-NOT:          "-DFOO"
+// CHECK:            ]
+// CHECK:            "input-file": "{{.*}}tu1.c"
+// CHECK-NEXT:     }
+// CHECK-NEXT:     {
+// CHECK:            "clang-module-deps": [
+// CHECK-NEXT:         {
+// CHECK-NEXT:           "context-hash": "[[HASH_FOO]]"
+// CHECK-NEXT:            "module-name": "Mod"
+// CHECK-NEXT:         }
+// CHECK-NEXT:       ]
+// CHECK-NEXT:       "command-line": [
+// CHECK:              "-DFOO"
+// CHECK:            ]
+// CHECK:            "input-file": "{{.*}}tu2.c"
+// CHECK-NEXT:     }
+// CHECK-NEXT:     {
+// CHECK:            "clang-module-deps": [
+// CHECK-NEXT:         {
+// CHECK-NEXT:           "context-hash": "[[HASH_NO_FOO]]"
+// CHECK-NEXT:            "module-name": "Mod"
+// CHECK-NEXT:         }
+// CHECK-NEXT:       ]
+// CHECK-NEXT:       "command-line": [
+// CHECK:              "-DFOO"
+// CHECK:              "-fmodules-ignore-macro=FOO"
+// CHECK:            ]
+// CHECK:            "input-file": "{{.*}}tu3.c"
+
+//--- cdb.json.template
+[
+  {
+    "directory": "DIR",
+    "command": "clang -fsyntax-only DIR/tu1.c -fmodules -fimplicit-module-maps -fmodules-cache-path=DIR/cache",
+    "file": "DIR/tu1.c"
+  },
+  {
+    "directory": "DIR",
+    "command": "clang -DFOO -fsyntax-only DIR/tu2.c -fmodules -fimplicit-module-maps -fmodules-cache-path=DIR/cache",
+    "file": "DIR/tu2.c"
+  },
+  {
+    "directory": "DIR",
+    "command": "clang -DFOO -fmodules-ignore-macro=FOO -fsyntax-only DIR/tu3.c -fmodules -fimplicit-module-maps -fmodules-cache-path=DIR/cache",
+    "file": "DIR/tu3.c"
+  },
+]
+
+//--- module.modulemap
+module Mod { header "Mod.h" }
+
+//--- Mod.h
+
+//--- tu1.c
+#include "Mod.h"
+
+//--- tu2.c
+#include "Mod.h"
+
+//--- tu3.c
+#include "Mod.h"

clang/test/ClangScanDeps/modules-context-hash-module-map-path.c

+// 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 -j 1 -generate-modules-path-args \
+// RUN:   -format experimental-full > %t/deps.json
+// RUN: cat %t/deps.json | sed 's:\\\\\?:/:g' | FileCheck -DPREFIX=%/t %s
+
+// CHECK:      {
+// CHECK-NEXT:   "modules": [
+// CHECK:          {
+// CHECK:            "command-line": [
+// CHECK:              "-dependency-file"
+// CHECK:            ]
+// CHECK:            "context-hash": "[[HASH1:.*]]"
+// CHECK:            "name": "Mod"
+// CHECK-NEXT:     }
+// CHECK-NEXT:     {
+// CHECK:            "command-line": [
+// CHECK-NOT:          "-dependency-file"
+// CHECK:            ]
+// CHECK:            "context-hash": "[[HASH2:.*]]"
+// CHECK:            "name": "Mod"
+// CHECK-NEXT:     }
+// CHECK-NEXT:   ]
+// CHECK-NEXT:   "translation-units": [
+// CHECK-NEXT:     {
+// CHECK:            "clang-module-deps": [
+// CHECK-NEXT:         {
+// CHECK-NEXT:           "context-hash": "[[HASH1]]"
+// CHECK-NEXT:            "module-name": "Mod"
+// CHECK-NEXT:         }
+// CHECK-NEXT:       ]
+// CHECK-NEXT:       "command-line": [
+// CHECK:              "-MF"
+// CHECK:            ]
+// CHECK:            "input-file": "{{.*}}tu1.c"
+// CHECK-NEXT:     }
+// CHECK-NEXT:     {
+// CHECK:            "clang-module-deps": [
+// CHECK-NEXT:         {
+// CHECK-NEXT:           "context-hash": "[[HASH2]]"
+// CHECK-NEXT:            "module-name": "Mod"
+// CHECK-NEXT:         }
+// CHECK-NEXT:       ]
+// CHECK-NEXT:       "command-line": [
+// CHECK-NOT:          "-MF"
+// CHECK:            ]
+// CHECK:            "input-file": "{{.*}}tu2.c"
+
+//--- cdb.json.template
+[
+  {
+    "directory": "DIR",
+    "command": "clang -MD -MF DIR/tu1.d -fsyntax-only DIR/tu1.c -fmodules -fimplicit-module-maps -fmodules-cache-path=DIR/cache",
+    "file": "DIR/tu1.c"
+  },
+  {
+    "directory": "DIR",
+    "command": "clang -fsyntax-only DIR/tu2.c -fmodules -fimplicit-module-maps -fmodules-cache-path=DIR/cache",
+    "file": "DIR/tu2.c"
+  },
+]
+
+//--- module.modulemap
+module Mod { header "Mod.h" }
+
+//--- Mod.h
+
+//--- tu1.c
+#include "Mod.h"
+
+//--- tu2.c
+#include "Mod.h"

clang/test/ClangScanDeps/modules-context-hash-warnings.c

+// 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 -j 1 \
+// RUN:   -format experimental-full > %t/deps.json
+// RUN: cat %t/deps.json | sed 's:\\\\\?:/:g' | FileCheck -DPREFIX=%/t %s
+
+// CHECK:      {
+// CHECK-NEXT:   "modules": [
+// CHECK:          {
+// CHECK:            "command-line": [
+// CHECK:              "-Wall"
+// CHECK:            ]
+// CHECK:            "context-hash": "[[HASH1:.*]]"
+// CHECK:            "name": "Mod"
+// CHECK-NEXT:     }
+// CHECK-NEXT:     {
+// CHECK:            "command-line": [
+// CHECK-NOT:          "-Wall"
+// CHECK:            ]
+// CHECK:            "context-hash": "[[HASH2:.*]]"
+// CHECK:            "name": "Mod"
+// CHECK-NEXT:     }
+// CHECK-NEXT:   ]
+// CHECK-NEXT:   "translation-units": [
+// CHECK-NEXT:     {
+// CHECK:            "clang-module-deps": [
+// CHECK-NEXT:         {
+// CHECK-NEXT:           "context-hash": "[[HASH1]]"
+// CHECK-NEXT:            "module-name": "Mod"
+// CHECK-NEXT:         }
+// CHECK-NEXT:       ]
+// CHECK-NEXT:       "command-line": [
+// CHECK:              "-Wall"
+// CHECK:            ]
+// CHECK:            "input-file": "{{.*}}tu1.c"
+// CHECK-NEXT:     }
+// CHECK-NEXT:     {
+// CHECK:            "clang-module-deps": [
+// CHECK-NEXT:         {
+// CHECK-NEXT:           "context-hash": "[[HASH2]]"
+// CHECK-NEXT:            "module-name": "Mod"
+// CHECK-NEXT:         }
+// CHECK-NEXT:       ]
+// CHECK-NEXT:       "command-line": [
+// CHECK-NOT:          "-Wall"
+// CHECK:            ]
+// CHECK:            "input-file": "{{.*}}tu2.c"
+
+//--- cdb.json.template
+[
+  {
+    "directory": "DIR",
+    "command": "clang -Wall -fsyntax-only DIR/tu1.c -fmodules -fimplicit-module-maps -fmodules-cache-path=DIR/cache",
+    "file": "DIR/tu1.c"
+  },
+  {
+    "directory": "DIR",
+    "command": "clang -fsyntax-only DIR/tu2.c -fmodules -fimplicit-module-maps -fmodules-cache-path=DIR/cache",
+    "file": "DIR/tu2.c"
+  },
+]
+
+//--- module.modulemap
+module Mod { header "Mod.h" }
+
+//--- Mod.h
+
+//--- tu1.c
+#include "Mod.h"
+
+//--- tu2.c
+#include "Mod.h"