[ThinLTO] Use std::map to get determistic imports files

[tejohnson]

Summary

I noticed that the .imports files emitted for distributed ThinLTO
backends do not have consistent ordering. This is because StringMap
iteration order is not guaranteed to be deterministic. Since we already
have a std::map with this information, used when emitting the individual
index files (ModuleToSummariesForIndex), use it for the imports files as
well.

This issue is likely causing some unnecessary rebuilds of the ThinLTO
backends in our distributed build system as the imports files are inputs
to those backends.

[steven_wu]

Does the iteration order of those map matters other than changing the hash? Will it change symbol resolution or importing different function?

The other option is MapVector, which preserve the insertion order, which might be faster than std::map.

[tejohnson]

In D48783#1148412, @steven_wu wrote:

Does the iteration order of those map matters other than changing the hash? Will it change symbol resolution or importing different function?

No effect on importing/symbol resolution etc. In fact, this is not an input to the compiler at all, it is used by the build system. The change in order will just make it look to the build system like it has changed when it hasn't.

The other option is MapVector, which preserve the insertion order, which might be faster than std::map.

The trickiness is that currently it may not be inserted in a deterministic order, because we use StringMap elsewhere in the thin link. So std::map is the most straightforward way to get the desired behavior.

[steven_wu]

In D48783#1148427, @tejohnson wrote:

In D48783#1148412, @steven_wu wrote:

Does the iteration order of those map matters other than changing the hash? Will it change symbol resolution or importing different function?

No effect on importing/symbol resolution etc. In fact, this is not an input to the compiler at all, it is used by the build system. The change in order will just make it look to the build system like it has changed when it hasn't.

I understand. But if the order is used by the build system, it can also affect the output binary. If the only goal is to keep the thin link function import map constant when the input doesn't change, std::map is fine. Can you add a test case for this?

The other option is MapVector, which preserve the insertion order, which might be faster than std::map.

The trickiness is that currently it may not be inserted in a deterministic order, because we use StringMap elsewhere in the thin link. So std::map is the most straightforward way to get the desired behavior.

This is unfortunate. I can't think of anything can be wrong because of that now but might need to revisit.

[tejohnson]

In D48783#1148452, @steven_wu wrote:

In D48783#1148427, @tejohnson wrote:

In D48783#1148412, @steven_wu wrote:

Does the iteration order of those map matters other than changing the hash? Will it change symbol resolution or importing different function?

No effect on importing/symbol resolution etc. In fact, this is not an input to the compiler at all, it is used by the build system. The change in order will just make it look to the build system like it has changed when it hasn't.

I understand. But if the order is used by the build system, it can also affect the output binary.

I'm not sure I understand how - additional ThinLTO backend processes could be unnecessarily redone, but they would have the same inputs and produce the same object file as before.

If the only goal is to keep the thin link function import map constant when the input doesn't change, std::map is fine. Can you add a test case for this?

I'll add a test that emits an imports file with multiple lines and check for them in order - it wouldn't necessarily fail without this change (we could get lucky), but it might catch any regression in this ordering.

The other option is MapVector, which preserve the insertion order, which might be faster than std::map.

The trickiness is that currently it may not be inserted in a deterministic order, because we use StringMap elsewhere in the thin link. So std::map is the most straightforward way to get the desired behavior.

This is unfortunate. I can't think of anything can be wrong because of that now but might need to revisit.

[tejohnson]

Add test with multiple imports files that are expected to be ordered

[tejohnson]

Ping

[steven_wu]

LGTM. Thanks!

[mehdi_amini]

std::map is usually fairly slow, have you considered sorting at the time you write to the file instead? That would add a slow step when writing the files but wouldn't affect any in-memory operation.

[tejohnson]

In D48783#1157681, @mehdi_amini wrote:

std::map is usually fairly slow, have you considered sorting at the time you write to the file instead? That would add a slow step when writing the files but wouldn't affect any in-memory operation.

Actually...looking at the code and what I even wrote here in the description, I'm not sure why it didn't occur to me to simply use the std::map ModuleToSummariesForIndex we are already building for the purposes of writing the distributed index files. At least in the new LTO API, that is done just before calling EmitImportsFiles, so we have it on hand! For the old LTO API, that std::map is not being done yet, but this is just llvm-lto testing code, so I can add a call to the same llvm::gatherImportedSummariesForModule before invoking EmitImportsFiles.

Let me change my patch to do this...

[tejohnson]

Use the existing ModuleToSummariesForIndex instead.

[mehdi_amini]

LGTM.

include/llvm/Transforms/IPO/FunctionImport.h

public:
   /// containing all the functions to import for a source module.
   /// The keys is the GUID identifying a function to import, and the value
   /// is the threshold applied when deciding to import it.
   using FunctionsToImportTy = std::map<GlobalValue::GUID, unsigned>;
 
   /// The map contains an entry for every module to import from, the key being
   /// the module identifier to pass to the ModuleLoader. The value is the set of
   /// functions to import.
-  using ImportMapTy = StringMap<FunctionsToImportTy>;
+  using ImportMapTy = std::map<std::string,FunctionsToImportTy>;
 
   /// The set contains an entry for every global value the module exports.
   using ExportSetTy = std::unordered_set<GlobalValue::GUID>;
 
   /// A function of this type is used to load modules referenced by the index.
   using ModuleLoaderTy =
       std::function<Expected<std::unique_ptr<Module>>(StringRef Identifier)>;
 

lib/LTO/LTO.cpp

#endif
   for (auto F : ExportList)
     // The export list can impact the internalization, be conservative here
     Hasher.update(ArrayRef<uint8_t>((uint8_t *)&F, sizeof(F)));
 
   // 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.
   for (auto &Entry : ImportList) {
-    auto ModHash = Index.getModuleHash(Entry.first());
+    auto ModHash = Index.getModuleHash(Entry.first);
     Hasher.update(ArrayRef<uint8_t>((uint8_t *)&ModHash[0], sizeof(ModHash)));
 
     AddUint64(Entry.second.size());
     for (auto &Fn : Entry.second)
       AddUint64(Fn.first);
   }
 
   // Include the hash for the resolved ODR.
for (auto &GS : DefinedGlobals) {
     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)
-      AddUsedThings(Index.findSummaryInModule(ImpF.first, ImpM.first()));
+      AddUsedThings(Index.findSummaryInModule(ImpF.first, ImpM.first));
 
   auto AddTypeIdSummary = [&](StringRef TId, const TypeIdSummary &S) {
     AddString(TId);
 
     AddUnsigned(S.TTRes.TheKind);
     AddUnsigned(S.TTRes.SizeM1BitWidth);
 
     AddUint64(S.TTRes.AlignLog2);

lib/LTO/ThinLTOCodeGenerator.cpp

#endif
 
     Hasher.update(ArrayRef<uint8_t>((uint8_t *)&ModHash[0], sizeof(ModHash)));
     for (auto F : ExportList)
       // The export list can impact the internalization, be conservative here
       Hasher.update(ArrayRef<uint8_t>((uint8_t *)&F, sizeof(F)));
 
     // Include the hash for every module we import functions from
     for (auto &Entry : ImportList) {
-      auto ModHash = Index.getModuleHash(Entry.first());
+      auto ModHash = Index.getModuleHash(Entry.first);
       Hasher.update(ArrayRef<uint8_t>((uint8_t *)&ModHash[0], sizeof(ModHash)));
     }
 
     // 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,

lib/Transforms/IPO/FunctionImport.cpp

for (auto &ModuleImports : ImportLists) {
     auto ModName = ModuleImports.first();
     auto &Exports = ExportLists[ModName];
     unsigned NumGVS = numGlobalVarSummaries(Index, Exports);
     LLVM_DEBUG(dbgs() << "* Module " << ModName << " exports "
                       << Exports.size() - NumGVS << " functions and " << NumGVS
                       << " vars. Imports from " << ModuleImports.second.size()
                       << " modules.\n");
     for (auto &Src : ModuleImports.second) {
-      auto SrcModName = Src.first();
+      auto SrcModName = Src.first;
       unsigned NumGVSPerMod = numGlobalVarSummaries(Index, Src.second);
       LLVM_DEBUG(dbgs() << " - " << Src.second.size() - NumGVSPerMod
                         << " functions imported from " << SrcModName << "\n");
       LLVM_DEBUG(dbgs() << " - " << NumGVSPerMod
                         << " global vars imported from " << SrcModName << "\n");
     }
   }
 #endif
 }
 
 #ifndef NDEBUG
 static void dumpImportListForModule(const ModuleSummaryIndex &Index,
                                     StringRef ModulePath,
                                     FunctionImporter::ImportMapTy &ImportList) {
   LLVM_DEBUG(dbgs() << "* Module " << ModulePath << " imports from "
                     << ImportList.size() << " modules.\n");
   for (auto &Src : ImportList) {
-    auto SrcModName = Src.first();
+    auto SrcModName = Src.first;
     unsigned NumGVSPerMod = numGlobalVarSummaries(Index, Src.second);
     LLVM_DEBUG(dbgs() << " - " << Src.second.size() - NumGVSPerMod
                       << " functions imported from " << SrcModName << "\n");
     LLVM_DEBUG(dbgs() << " - " << NumGVSPerMod << " vars imported from "
                       << SrcModName << "\n");
   }
 }
 #endif
void llvm::gatherImportedSummariesForModule(
     const StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries,
     const FunctionImporter::ImportMapTy &ImportList,
     std::map<std::string, GVSummaryMapTy> &ModuleToSummariesForIndex) {
   // Include all summaries from the importing module.
   ModuleToSummariesForIndex[ModulePath] =
       ModuleToDefinedGVSummaries.lookup(ModulePath);
   // Include summaries for imports.
   for (auto &ILI : ImportList) {
-    auto &SummariesForIndex = ModuleToSummariesForIndex[ILI.first()];
+    auto &SummariesForIndex = ModuleToSummariesForIndex[ILI.first];
     const auto &DefinedGVSummaries =
-        ModuleToDefinedGVSummaries.lookup(ILI.first());
+        ModuleToDefinedGVSummaries.lookup(ILI.first);
     for (auto &GI : ILI.second) {
       const auto &DS = DefinedGVSummaries.find(GI.first);
       assert(DS != DefinedGVSummaries.end() &&
              "Expected a defined summary for imported global value");
       SummariesForIndex[GI.first] = DS->second;
     }
   }
 }
 
 /// Emit the files \p ModulePath will import from into \p OutputFilename.
 std::error_code
 llvm::EmitImportsFiles(StringRef ModulePath, StringRef OutputFilename,
                        const FunctionImporter::ImportMapTy &ModuleImports) {
   std::error_code EC;
   raw_fd_ostream ImportsOS(OutputFilename, EC, sys::fs::OpenFlags::F_None);
   if (EC)
     return EC;
   for (auto &ILI : ModuleImports)
-    ImportsOS << ILI.first() << "\n";
+    ImportsOS << ILI.first << "\n";
   return std::error_code();
 }
 
 bool llvm::convertToDeclaration(GlobalValue &GV) {
   LLVM_DEBUG(dbgs() << "Converting to a declaration: `" << GV.getName()
                     << "\n");
   if (Function *F = dyn_cast<Function>(&GV)) {
     F->deleteBody();
Expected<bool> FunctionImporter::importFunctions(
   LLVM_DEBUG(dbgs() << "Starting import for Module "
                     << DestModule.getModuleIdentifier() << "\n");
   unsigned ImportedCount = 0, ImportedGVCount = 0;
 
   IRMover Mover(DestModule);
   // Do the actual import of functions now, one Module at a time
   std::set<StringRef> ModuleNameOrderedList;
   for (auto &FunctionsToImportPerModule : ImportList) {
-    ModuleNameOrderedList.insert(FunctionsToImportPerModule.first());
+    ModuleNameOrderedList.insert(FunctionsToImportPerModule.first);
   }
   for (auto &Name : ModuleNameOrderedList) {
     // Get the module for the import
     const auto &FunctionsToImportPerModule = ImportList.find(Name);
     assert(FunctionsToImportPerModule != ImportList.end());
     Expected<std::unique_ptr<Module>> SrcModuleOrErr = ModuleLoader(Name);
     if (!SrcModuleOrErr)
       return SrcModuleOrErr.takeError();

test/ThinLTO/X86/Inputs/emit_imports2.ll

+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @h() {
+entry:
+  ret void
+}

test/ThinLTO/X86/emit_imports.ll

 ; RUN: opt -module-summary %s -o %t1.bc
 ; RUN: opt -module-summary %p/Inputs/emit_imports.ll -o %t2.bc
+; RUN: opt -module-summary %p/Inputs/emit_imports2.ll -o %t2b.bc
 ; Include a file with an empty module summary index, to ensure that the expected
 ; output files are created regardless, for a distributed build system.
 ; RUN: opt -module-summary %p/Inputs/empty.ll -o %t3.bc
 ; RUN: rm -f %t3.bc.imports
-; RUN: llvm-lto -thinlto-action=thinlink -o %t.index.bc %t1.bc %t2.bc %t3.bc
-; RUN: llvm-lto -thinlto-action=emitimports -thinlto-index %t.index.bc %t1.bc %t2.bc %t3.bc
+; RUN: llvm-lto -thinlto-action=thinlink -o %t.index.bc %t1.bc %t2.bc %t2b.bc %t3.bc
+; RUN: llvm-lto -thinlto-action=emitimports -thinlto-index %t.index.bc %t1.bc %t2.bc %t2b.bc %t3.bc
 
 ; The imports file for this module contains the bitcode file for
 ; Inputs/emit_imports.ll
-; RUN: cat %t1.bc.imports | count 1
+; RUN: cat %t1.bc.imports | count 2
 ; RUN: cat %t1.bc.imports | FileCheck %s --check-prefix=IMPORTS1
 ; IMPORTS1: emit_imports.ll.tmp2.bc
+; IMPORTS1: emit_imports.ll.tmp2b.bc
 
 ; The imports file for Input/emit_imports.ll is empty as it does not import anything.
 ; RUN: cat %t2.bc.imports | count 0
 
 ; The imports file for Input/empty.ll is empty but should exist.
 ; RUN: cat %t3.bc.imports | count 0
 
 ; RUN: rm -f %t1.thinlto.bc %t1.bc.imports
 ; RUN: rm -f %t2.thinlto.bc %t2.bc.imports
 ; RUN: rm -f %t3.bc.thinlto.bc %t3.bc.imports
-; RUN: llvm-lto2 run %t1.bc %t2.bc %t3.bc -o %t.o -save-temps \
+; RUN: llvm-lto2 run %t1.bc %t2.bc %t2b.bc %t3.bc -o %t.o -save-temps \
 ; RUN:     -thinlto-distributed-indexes \
 ; RUN:     -r=%t1.bc,g, \
+; RUN:     -r=%t1.bc,h, \
 ; RUN:     -r=%t1.bc,f,px \
-; RUN:     -r=%t2.bc,g,px
+; RUN:     -r=%t2.bc,g,px \
+; RUN:     -r=%t2b.bc,h,px
 
-; RUN: cat %t1.bc.imports | count 1
+; RUN: cat %t1.bc.imports | count 2
 ; RUN: cat %t1.bc.imports | FileCheck %s --check-prefix=IMPORTS1
 
 ; The imports file for Input/emit_imports.ll is empty as it does not import anything.
 ; RUN: cat %t2.bc.imports | count 0
 
 ; The imports file for Input/empty.ll is empty but should exist.
 ; RUN: cat %t3.bc.imports | count 0
 
 ; The index file should be created even for the input with an empty summary.
 ; RUN: ls %t3.bc.thinlto.bc
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 declare void @g(...)
+declare void @h(...)
 
 define void @f() {
 entry:
   call void (...) @g()
+  call void (...) @h()
   ret void
 }