[ThinLTO] Use module hash instead of module ID for cache key

[nikic]

Summary

This is a followup to D151165. Instead of using the module ID, use the module hash for sorting the import list. The module hash is what will actually be included in the hash.

This has the advantage of being independent of the module order, which is something that Rust relies on.

A caveat here is that the test doesn't quite work for linkonce_odr functions, because the function may be imported from two different modules, and the first one on the llvm-lto2 command line gets picked (rather than, say, the prevailing copy). This doesn't really matter for Rust's purposes (because it does not use linkonce_odr linkage), but may still be worth addressing. For now I'm using a variant of the test using internal instead of linkonce_odr functions.

[tejohnson]

A caveat here is that this doesn't quite work for linkonce_odr functions, because it seems like the function from the first encountered module gets picked (rather than say, the prevailing function). This doesn't really matter for Rust's purposes (because it does not use linkonce_odr linkage), but may still be worth addressing. For now I'm using a variant of the test using internal instead of linkonce_odr functions.

Can you clarify what doesn't work with linkonce_odr? This patch shouldn't affect any importing decisions, which have already been made, so the import list sorted here should only include a single copy of a linkonce_odr function.

[nikic]

In D156525#4542312, @tejohnson wrote:

A caveat here is that this doesn't quite work for linkonce_odr functions, because it seems like the function from the first encountered module gets picked (rather than say, the prevailing function). This doesn't really matter for Rust's purposes (because it does not use linkonce_odr linkage), but may still be worth addressing. For now I'm using a variant of the test using internal instead of linkonce_odr functions.

Can you clarify what doesn't work with linkonce_odr? This patch shouldn't affect any importing decisions, which have already been made, so the import list sorted here should only include a single copy of a linkonce_odr function.

What I'm seeing is that the linkonce_odr function will be imported from either a.bc or b.bc, depending on the order of llvm-lto2 arguments. The patch doesn't affect importing decisions, it's just that the test case doesn't work with linkonce_odr, because it ends up still being order-dependent.

[tejohnson]

In D156525#4542351, @nikic wrote:

In D156525#4542312, @tejohnson wrote:

A caveat here is that this doesn't quite work for linkonce_odr functions, because it seems like the function from the first encountered module gets picked (rather than say, the prevailing function). This doesn't really matter for Rust's purposes (because it does not use linkonce_odr linkage), but may still be worth addressing. For now I'm using a variant of the test using internal instead of linkonce_odr functions.

Can you clarify what doesn't work with linkonce_odr? This patch shouldn't affect any importing decisions, which have already been made, so the import list sorted here should only include a single copy of a linkonce_odr function.

What I'm seeing is that the linkonce_odr function will be imported from either a.bc or b.bc, depending on the order of llvm-lto2 arguments. The patch doesn't affect importing decisions, it's just that the test case doesn't work with linkonce_odr, because it ends up still being order-dependent.

Ok thanks, can you change the wording in the summary to clarify that you are talking about the test, e.g. maybe replace "this" with "the test" in "A caveat here is that this doesn't quite work for linkonce_odr functions".

lgtm otherwise

llvm/lib/LTO/LTO.cpp

struct ImportModule {
     const ModuleSummaryIndex::ModuleInfo *ModInfo;
 
     StringRef getIdentifier() const { return ModIt->getKey(); }
     const FunctionImporter::FunctionsToImportTy &getFunctions() const {
       return ModIt->second;
     }
 
     const ModuleHash &getHash() const { return ModInfo->second.second; }
-    uint64_t getId() const { return ModInfo->second.first; }
   };
 
   std::vector<ImportModule> ImportModulesVector;
   ImportModulesVector.reserve(ImportList.size());
 
   for (ImportMapIteratorTy It = ImportList.begin(); It != ImportList.end();
        ++It) {
     ImportModulesVector.push_back({It, Index.getModule(It->getKey())});
   }
-  // Order using moduleId integer which is based on the order the module was
-  // added.
+  // Order using module hash, to be both independent of module name and
+  // module order.
   llvm::sort(ImportModulesVector,
              [](const ImportModule &Lhs, const ImportModule &Rhs) -> bool {
-               return Lhs.getId() < Rhs.getId();
+               return Lhs.getHash() < Rhs.getHash();
              });
   for (const ImportModule &Entry : ImportModulesVector) {
     auto ModHash = Entry.getHash();
     Hasher.update(ArrayRef<uint8_t>((uint8_t *)&ModHash[0], sizeof(ModHash)));
 
     AddUint64(Entry.getFunctions().size());
     for (auto &Fn : Entry.getFunctions())
       AddUint64(Fn);

llvm/test/ThinLTO/X86/Inputs/cache-import-lists3.ll

+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 @f1() {
+  call void @internal()
+  ret void
+}
+
+define internal void @internal() {
+  ret void
+}

llvm/test/ThinLTO/X86/Inputs/cache-import-lists4.ll

+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 @f2() {
+  call void @internal()
+  ret void
+}
+
+define internal void @internal() {
+  ret void
+}

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

+; RUN: rm -rf %t && mkdir -p %t
+; RUN: opt -module-hash -module-summary %s -o %t/t.bc
+; RUN: opt -module-hash -module-summary %S/Inputs/cache-import-lists3.ll -o %t/a.bc
+; RUN: opt -module-hash -module-summary %S/Inputs/cache-import-lists4.ll -o %t/b.bc
+
+; Tests that the hash for t is insensitive to the order of the modules.
+
+; RUN: llvm-lto2 run -cache-dir %t/cache -o %t.o %t/t.bc %t/a.bc %t/b.bc -r=%t/t.bc,main,plx -r=%t/t.bc,f1,lx -r=%t/t.bc,f2,lx -r=%t/a.bc,f1,plx -r=%t/b.bc,f2,plx
+; RUN: ls %t/cache | count 3
+
+; RUN: llvm-lto2 run -cache-dir %t/cache -o %t.o %t/b.bc %t/a.bc %t/t.bc -r=%t/t.bc,main,plx -r=%t/t.bc,f1,lx -r=%t/t.bc,f2,lx -r=%t/a.bc,f1,plx -r=%t/b.bc,f2,plx
+; 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()