[ThinLTO] Make the cache key independent of the module identifier paths

[akyrtzi]

Summary

Otherwise there are cache misses just from changing the name of a path, even though the input modules did not change.

rdar://109672225

[steven_wu]

LGTM

[akyrtzi]

Use Index.getModule() to get both ModuleId and the hash, so that we do only one lookup for both.

[nikic]

@tejohnson Can you please confirm the correctness of this change?

This change has caused major compile-time regressions in Rust (compiled modules no longer get reused in incremental builds), because modules get added to the index in different orders across compilations. On the surface, it seems like we could easily work around this by adding a sort over the module key. However, the modules involved in the compilation can actually change, e.g. if references to symbols in a module are added/removed so that the module does not need to be linked at all (or starts needing to be linked). Even with a sort, this is going to shift the module indices, and result in at least unnecessary cache invalidation (I'm not sure it can result in result in incorrect cache reuse).

The basic premise of this patch (that we can use the module order instead of the module key) seems to be premised on a specific compilation model that is not valid for all thin lto consumers.

[akyrtzi]

What about changing the code to sort using the module hash:

   llvm::sort(ImportModulesVector,
              [](const ImportModule &Lhs, const ImportModule &Rhs) -> bool {
-               return Lhs.getId() < Rhs.getId();
+               return Lhs.getHash() < Rhs.getHash();
              });

would that resolve your issue?

[nikic]

In D151165#4538667, @akyrtzi wrote:

What about changing the code to sort using the module hash:

   llvm::sort(ImportModulesVector,
              [](const ImportModule &Lhs, const ImportModule &Rhs) -> bool {
-               return Lhs.getId() < Rhs.getId();
+               return Lhs.getHash() < Rhs.getHash();
              });

would that resolve your issue?

From a cursory test that seems to work.

[tejohnson]

In D151165#4538190, @nikic wrote:

@tejohnson Can you please confirm the correctness of this change?

This change has caused major compile-time regressions in Rust (compiled modules no longer get reused in incremental builds), because modules get added to the index in different orders across compilations. On the surface, it seems like we could easily work around this by adding a sort over the module key. However, the modules involved in the compilation can actually change, e.g. if references to symbols in a module are added/removed so that the module does not need to be linked at all (or starts needing to be linked). Even with a sort, this is going to shift the module indices, and result in at least unnecessary cache invalidation (I'm not sure it can result in result in incorrect cache reuse).

The basic premise of this patch (that we can use the module order instead of the module key) seems to be premised on a specific compilation model that is not valid for all thin lto consumers.

Thanks for the report, yeah I can see how using the module id here can result in spurious differences. Using the module hash should address the issue I think.

In D151165#4538667, @akyrtzi wrote:

What about changing the code to sort using the module hash:

   llvm::sort(ImportModulesVector,
              [](const ImportModule &Lhs, const ImportModule &Rhs) -> bool {
-               return Lhs.getId() < Rhs.getId();
+               return Lhs.getHash() < Rhs.getHash();
              });

would that resolve your issue?

This is better, @nikic can you confirm?

The module ID is an older concept that predates the module hash. We should probably remove that from the in-memory index completely, since it just takes up space and can lead to confusion about what values are stable and should be used. The numeric id is utilized in the Bitcode format for compactness, but I don't think we need it in memory anymore (quick scan of the codebase suggests not). Let me see if I can remove that once this issue is fixed.

[nikic]

I've just confirmed that using the hash works for the original, unreduced test cases as well.

[tejohnson]

In D151165#4538756, @tejohnson wrote:

The module ID is an older concept that predates the module hash. We should probably remove that from the in-memory index completely, since it just takes up space and can lead to confusion about what values are stable and should be used. The numeric id is utilized in the Bitcode format for compactness, but I don't think we need it in memory anymore (quick scan of the codebase suggests not). Let me see if I can remove that once this issue is fixed.

D156730

llvm/lib/LTO/LTO.cpp

for (uint64_t GUID : ExportsGUID) {
     // The export list can impact the internalization, be conservative here
     Hasher.update(ArrayRef<uint8_t>((uint8_t *)&GUID, sizeof(GUID)));
   }
 
   // Include the hash for every module we import functions from. The set of
   // imported symbols for each module may affect code generation and is
   // sensitive to link order, so include that as well.
   using ImportMapIteratorTy = FunctionImporter::ImportMapTy::const_iterator;
-  std::vector<ImportMapIteratorTy> ImportModulesVector;
+  struct ImportModule {
+    ImportMapIteratorTy ModIt;
+    uint64_t ModId;
+
+    StringRef getIdentifier() const { return ModIt->getKey(); }
+    const FunctionImporter::FunctionsToImportTy &getFunctions() const {
+      return ModIt->second;
+    }
+  };
+
+  std::vector<ImportModule> ImportModulesVector;
   ImportModulesVector.reserve(ImportList.size());
 
   for (ImportMapIteratorTy It = ImportList.begin(); It != ImportList.end();
        ++It) {
-    ImportModulesVector.push_back(It);
+    ImportModulesVector.push_back({It, Index.getModuleId(It->getKey())});
   }
+  // Order using moduleId integer which is based on the order the module was
+  // added.
   llvm::sort(ImportModulesVector,
-             [](const ImportMapIteratorTy &Lhs, const ImportMapIteratorTy &Rhs)
-                 -> bool { return Lhs->getKey() < Rhs->getKey(); });
-  for (const ImportMapIteratorTy &EntryIt : ImportModulesVector) {
-    auto ModHash = Index.getModuleHash(EntryIt->first());
+             [](const ImportModule &Lhs, const ImportModule &Rhs) -> bool {
+               return Lhs.ModId < Rhs.ModId;
+             });
+  for (const ImportModule &Entry : ImportModulesVector) {
+    auto ModHash = Index.getModuleHash(Entry.getIdentifier());
     Hasher.update(ArrayRef<uint8_t>((uint8_t *)&ModHash[0], sizeof(ModHash)));
 
-    AddUint64(EntryIt->second.size());
-    for (auto &Fn : EntryIt->second)
+    AddUint64(Entry.getFunctions().size());
+    for (auto &Fn : Entry.getFunctions())
       AddUint64(Fn);
   }
 
   // Include the hash for the resolved ODR.
   for (auto &Entry : ResolvedODR) {
     Hasher.update(ArrayRef<uint8_t>((const uint8_t *)&Entry.first,
                                     sizeof(GlobalValue::GUID)));
     Hasher.update(ArrayRef<uint8_t>((const uint8_t *)&Entry.second,
for (auto &GS : DefinedGlobals) {
     Hasher.update(
         ArrayRef<uint8_t>((const uint8_t *)&Linkage, sizeof(Linkage)));
     AddUsedCfiGlobal(GS.first);
     AddUsedThings(GS.second);
   }
 
   // Imported functions may introduce new uses of type identifier resolutions,
   // so we need to collect their used resolutions as well.
-  for (auto &ImpM : ImportList)
-    for (auto &ImpF : ImpM.second) {
-      GlobalValueSummary *S = Index.findSummaryInModule(ImpF, ImpM.first());
+  for (const ImportModule &ImpM : ImportModulesVector)
+    for (auto &ImpF : ImpM.getFunctions()) {
+      GlobalValueSummary *S =
+          Index.findSummaryInModule(ImpF, ImpM.getIdentifier());
       AddUsedThings(S);
       // If this is an alias, we also care about any types/etc. that the aliasee
       // may reference.
       if (auto *AS = dyn_cast_or_null<AliasSummary>(S))
         AddUsedThings(AS->getBaseObject());
     }
 
   auto AddTypeIdSummary = [&](StringRef TId, const TypeIdSummary &S) {

llvm/test/ThinLTO/X86/cache-decoupled-from-filenames.ll

+; RUN: rm -rf %t && mkdir -p %t/1 %t/2 %t/3 %t/4
+; RUN: opt -module-hash -module-summary %s -o %t/t.bc
+; RUN: opt -module-hash -module-summary %S/Inputs/cache-import-lists1.ll -o %t/1/a.bc
+; RUN: opt -module-hash -module-summary %S/Inputs/cache-import-lists2.ll -o %t/2/b.bc
+
+; Tests that the hash for t is insensitive to the bitcode module filenames.
+
+; RUN: rm -rf %t/cache
+; RUN: llvm-lto2 run -cache-dir %t/cache -o %t.o %t/t.bc %t/1/a.bc %t/2/b.bc -r=%t/t.bc,main,plx -r=%t/t.bc,f1,lx -r=%t/t.bc,f2,lx -r=%t/1/a.bc,f1,plx -r=%t/1/a.bc,linkonce_odr,plx -r=%t/2/b.bc,f2,plx -r=%t/2/b.bc,linkonce_odr,lx
+; RUN: ls %t/cache | count 3
+
+; RUN: cp %t/1/a.bc %t/4/d.bc
+; RUN: cp %t/2/b.bc %t/3/k.bc
+; RUN: llvm-lto2 run -cache-dir %t/cache -o %t.o %t/t.bc %t/4/d.bc %t/3/k.bc -r=%t/t.bc,main,plx -r=%t/t.bc,f1,lx -r=%t/t.bc,f2,lx -r=%t/4/d.bc,f1,plx -r=%t/4/d.bc,linkonce_odr,plx -r=%t/3/k.bc,f2,plx -r=%t/3/k.bc,linkonce_odr,lx
+; RUN: ls %t/cache | count 3
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @main() {
+  call void @f1()
+  call void @f2()
+  ret void
+}
+
+declare void @f1()
+declare void @f2()