--thinlto-full-index to index both native and bitcode objects

[weiwang]

Summary

Add new option --thinlto-full-index to work together with --thinlto-index-only= to produce an extended index list including both prebuilt native and bitcode objects.

For file name thinlto.index given to --thinlto-index-only=, the new option writes the extended list to thinlto.index.full. Then distributed backend can use thinlto.index to guide its compilation and use thinlto.index.full can be fed into final link as the full input list with the intended resolution order.

Currently --thinlto-index-only appends to the list for non-lazy bitcode object file as they are encountered and lazy bitcode object files when they are parsed. It basically emits the symbol resolution order for those files. However when user inputs consist of both prebuilt native objects and bitcode objects, the list is incomplete and it is hard to achieve the same symbol resolution order during final link to produce the same result as the inputs were going through local ThinLTO.

--thinlto-full-index appends to the list for non-lazy object files, both native and bitcode, as they are encountered and lazy object files, both native and bitcode, when they are parsed.

[MaskRay]

I considered this approach. I went with D130229 as I have thought of some minor issues:

• The requires clang -nostdlib ...
• An archive member cannot be serialized as file->getName(). Actually lld doesn't support syntax reading just an archive member instead of the whole archive. As an example, glibc libc.so reads libc_nonshared.a which contains elf-init.oS and the patch will incorrectly print elf-init.oS. This approach assuredly needs an option doing something similar to --remapping-file= in spirit, but more involved.
• A build system needs to recognize all input files, and remove them for the final native link. This is nearly mostly feasible with Bazel/Buck style build systems, but not with others. Even in Bazel/Buck, I don't think linkopts = ["file_added_as_an_option_instead_of_src_or_deps.o"] can be recognized.

The above is off the top of my head.

And we lose opportunities to fix some problems for free:

• If we are to support bitcode files in archives, we will need more options.
• This still misses an opportunity to properly fix "libcall symbols defined in bitcode member of an archive".

I wish that you can give a fair consideration of D130229 and not simply dismiss it with "it differs from in-process ThinLTO, it's not right."

[weiwang]

Thanks for the quick feedback!

In D130975#3694180, @MaskRay wrote:

I considered this approach. I went with D130229 as I have thought of some minor issues:

• The requires clang -nostdlib ...
• An archive member cannot be serialized as file->getName(). Actually lld doesn't support syntax reading just an archive member instead of the whole archive. As an example, glibc libc.so reads libc_nonshared.a which contains elf-init.oS and the patch will incorrectly print elf-init.oS. This approach assuredly needs an option doing something similar to --remapping-file= in spirit, but more involved.
• A build system needs to recognize all input files, and remove them for the final native link. This is nearly mostly feasible with Bazel/Buck style build systems, but not with others. Even in Bazel/Buck, I don't think linkopts = ["file_added_as_an_option_instead_of_src_or_deps.o"] can be recognized.

The above is off the top of my head.

Your concerns are valid. I encountered them as well during local testing.

• Our internal build system (buck) applies -nostdlib throughout linking, so this requirement is satisfied.
• There are no direct support to extract specific members from archive. We are updating build system to make all regular archives into thin archive (--[start|end]-lib). With that done, archive members can be accessed directly. And you are right about elf-init.oS. During my local testing, I had to extract it manually, so some work needs to be done here. In a more general approach, formatting the index with ("archivename", "object") pair and using a separate flag to parse the index (like "--remapping-file=") is also doable.
• The index file contains line separated input file list, and can be used directly as response file in the final link (I should've just used @thinlto.index.full in the test case provided).

And we lose opportunities to fix some problems for free:

• If we are to support bitcode files in archives, we will need more options.
• This still misses an opportunity to properly fix "libcall symbols defined in bitcode member of an archive".

I wish that you can give a fair consideration of D130229 and not simply dismiss it with "it differs from in-process ThinLTO, it's not right."

The concern we have is not about which linking order is right or wrong, it's rather making it consistent with its local in-process thinlto counterpart. We are kind of late in the game of distributed thinlto and we have large scale of services (20K inputs for linking) running with local thinlto for years. We can't guarantee that changing the resolution order of inputs from local to distributed thinlto won't make a difference in binary runtime behavior, and it would be a big headache to debug after everything goes production. So our current approach is to

1. Make sure that distributed thinlto thinlink uses the same inputs and order as local thinlto. This is more of the build system level change.
2. Make sure that distributed thinlto final link uses the same resolution order as thinlink with the help of this new option.
3. Verify that binaries generated from both local and distributed thinlink matches at per symbol level.

[MaskRay]

In D130975#3694853, @weiwang wrote:

And we lose opportunities to fix some problems for free:

• If we are to support bitcode files in archives, we will need more options.
• This still misses an opportunity to properly fix "libcall symbols defined in bitcode member of an archive".

I wish that you can give a fair consideration of D130229 and not simply dismiss it with "it differs from in-process ThinLTO, it's not right."

The concern we have is not about which linking order is right or wrong, it's rather making it consistent with its local in-process thinlto counterpart. We are kind of late in the game of distributed thinlto and we have large scale of services (20K inputs for linking) running with local thinlto for years. We can't guarantee that changing the resolution order of inputs from local to distributed thinlto won't make a difference in binary runtime behavior, and it would be a big headache to debug after everything goes production. So our current approach is to

1. Make sure that distributed thinlto thinlink uses the same inputs and order as local thinlto. This is more of the build system level change.
2. Make sure that distributed thinlto final link uses the same resolution order as thinlink with the help of this new option.
3. Verify that binaries generated from both local and distributed thinlink matches at per symbol level.

Thanks for being open. However, this is something I'd push back a bit.

See the last paragraph of https://reviews.llvm.org/D130229#3674024 : I think lld users need to ensure their build targets and the dependencies are in a decent state.
In the past, I have fixed a lot of internal builds to cooperate with the executable default --no-allow-shlib-undefined and later --warn-backrefs (https://maskray.me/blog/2021-06-13-dependency-related-linker-options#warn-backrefs).
Perhaps these things indirectly help stabilize our ThinLTO builds.
I did not add options to lld just so that my company could quickly adapt the dependency restriction features.

In addition, I suspect our current archive member extraction logic isn't ideal and we may need to revamp it. See mold which has implemented great parallel input file parsing.
Applications tied to every implementation detail of the archive member extraction is brittle and should be avoided.
Improving lld performance isn't my work priority, so I basically do it in my spare time in a slow but hopefully steady pace.
See https://discourse.llvm.org/t/parallel-input-file-parsing/60164 and a few patches from me mentioning "parallel". There have been some changes like D95985, removing ArchiveFile, etc.
I think we will do similar things if parallel non-local symbol resolution can become more feasible, as long as the symbol resolution logic still makes sense.

As mentioned, the in-process ThinLTO symbol resolution probably isn't that ideal and we need to fix that, too, though probably with a low priority.
For this patch, I want to give a clear NAK unless you can come up with a reasonable example that --thinlto-index= + --remapping-file= don't work well (not a brittle archive shadow example).

lld/ELF/Config.h

struct Configuration {
   bool symbolic;
   bool isStatic = false;
   bool sysvHash = false;
   bool target1Rel;
   bool trace;
   bool thinLTOEmitImportsFiles;
   bool thinLTOEmitIndexFiles;
   bool thinLTOIndexOnly;
+  bool thinLTOFullIndex;
   bool timeTraceEnabled;
   bool tocOptimize;
   bool pcRelOptimize;
   bool undefinedVersion;
   bool unique;
   bool useAndroidRelrTags = false;
   bool warnBackrefs;
   llvm::SmallVector<llvm::GlobPattern, 0> warnBackrefsExclude;
struct Ctx {
   // A tuple of (reference, extractedFile, sym). Used by --why-extract=.
   SmallVector<std::tuple<std::string, const InputFile *, const Symbol &>, 0>
       whyExtractRecords;
   // A mapping from a symbol to an InputFile referencing it backward. Used by
   // --warn-backrefs.
   llvm::DenseMap<const Symbol *,
                  std::pair<const InputFile *, const InputFile *>>
       backwardReferences;
+  std::unique_ptr<llvm::raw_fd_ostream> fullIndexFile;
 };
 
 // The only instance of Ctx struct.
 extern std::unique_ptr<Ctx> ctx;
 
 // The first two elements of versionDefinitions represent VER_NDX_LOCAL and
 // VER_NDX_GLOBAL. This helper returns other elements.
 static inline ArrayRef<VersionDefinition> namedVersionDefs() {

lld/ELF/Driver.cpp

config->thinLTOCachePolicy = CHECK(
       "--thinlto-cache-policy: invalid cache policy");
   config->thinLTOEmitImportsFiles = args.hasArg(OPT_thinlto_emit_imports_files);
   config->thinLTOEmitIndexFiles = args.hasArg(OPT_thinlto_emit_index_files) ||
                                   args.hasArg(OPT_thinlto_index_only) ||
                                   args.hasArg(OPT_thinlto_index_only_eq);
   config->thinLTOIndexOnly = args.hasArg(OPT_thinlto_index_only) ||
                              args.hasArg(OPT_thinlto_index_only_eq);
   config->thinLTOIndexOnlyArg = args.getLastArgValue(OPT_thinlto_index_only_eq);
+  config->thinLTOFullIndex = args.hasArg(OPT_thinlto_full_index);
   config->thinLTOObjectSuffixReplace =
       getOldNewOptions(args, OPT_thinlto_object_suffix_replace_eq);
   config->thinLTOPrefixReplace =
       getOldNewOptions(args, OPT_thinlto_prefix_replace_eq);
   if (config->thinLTOEmitIndexFiles && !config->thinLTOIndexOnly) {
     if (args.hasArg(OPT_thinlto_object_suffix_replace_eq))
       error("--thinlto-object-suffix-replace is not supported with "
             "--thinlto-emit-index-files");
for (StringRef name : config->undefined)
     addUnusedUndefined(name)->referenced = true;
 
   // Add all files to the symbol table. This will add almost all
   // symbols that we need to the symbol table. This process might
   // add files to the link, via autolinking, these files are always
   // appended to the Files vector.
   {
     llvm::TimeTraceScope timeScope("Parse input files");
+    if (!config->thinLTOIndexOnlyArg.empty() && config->thinLTOFullIndex) {
+      std::error_code ec;
+      ctx->fullIndexFile = std::make_unique<raw_fd_ostream>(
+          (config->thinLTOIndexOnlyArg + ".full").str(), ec,
+          sys::fs::OpenFlags::OF_None);
+      if (ec) {
+        error("cannot open " + config->thinLTOIndexOnlyArg +
+              ".full: " + ec.message());
+        return;
+      }
+    }
     for (size_t i = 0; i < files.size(); ++i) {
       llvm::TimeTraceScope timeScope("Parse input files", files[i]->getName());
       parseFile(files[i]);
     }
+    if (ctx->fullIndexFile) {
+      ctx->fullIndexFile->close();
+      ctx->fullIndexFile.release();
+    }
   }
 
   // Now that we have every file, we can decide if we will need a
   // dynamic symbol table.
   // We need one if we were asked to export dynamic symbols or if we are
   // producing a shared library.
   // We also need one if any shared libraries are used and for pie executables
   // (probably because the dynamic linker needs it).

lld/ELF/InputFiles.cpp

 
 template <class ELFT> static void doParseFile(InputFile *file) {
   if (!isCompatible(file))
     return;
 
   // Binary file
   if (auto *f = dyn_cast<BinaryFile>(file)) {
     ctx->binaryFiles.push_back(f);
+    if (ctx->fullIndexFile)
+      *(ctx->fullIndexFile) << file->getName() << "\n";
     f->parse();
     return;
   }
 
   // Lazy object file
   if (file->lazy) {
     if (auto *f = dyn_cast<BitcodeFile>(file)) {
       ctx->lazyBitcodeFiles.push_back(f);
       f->parseLazy();
     } else {
       cast<ObjFile<ELFT>>(file)->parseLazy();
     }
     return;
   }
 
   if (config->trace)
     message(toString(file));
 
   // .so file
   if (auto *f = dyn_cast<SharedFile>(file)) {
+    if (ctx->fullIndexFile)
+      *(ctx->fullIndexFile) << file->getName() << "\n";
     f->parse<ELFT>();
     return;
   }
 
   // LLVM bitcode file
   if (auto *f = dyn_cast<BitcodeFile>(file)) {
     ctx->bitcodeFiles.push_back(f);
+    if (ctx->fullIndexFile) {
+      auto NewModulePath = lto::getThinLTOOutputFile(
+          std::string(f->obj->getName()),
+          std::string(config->thinLTOPrefixReplace.first),
+          std::string(config->thinLTOPrefixReplace.second));
+      *(ctx->fullIndexFile) << NewModulePath << "\n";
+    }
     f->parse<ELFT>();
     return;
   }
 
   // Regular object file
   ctx->objectFiles.push_back(cast<ELFFileBase>(file));
+  if (ctx->fullIndexFile)
+    *(ctx->fullIndexFile) << file->getName() << "\n";
   cast<ObjFile<ELFT>>(file)->parse();
 }
 
 // Add symbols in File to the symbol table.
 void elf::parseFile(InputFile *file) { invokeELFT(doParseFile, file); }
 
 // Concatenates arguments to construct a string representing an error location.
 static std::string createFileLineMsg(StringRef path, unsigned line) {

lld/ELF/Options.td

defm shuffle_sections: EEq<"shuffle-sections",
   MetaVarName<"<section-glob>=<seed>">;
 def thinlto_cache_dir: JJ<"thinlto-cache-dir=">,
   HelpText<"Path to ThinLTO cached object file directory">;
 defm thinlto_cache_policy: EEq<"thinlto-cache-policy", "Pruning policy for the ThinLTO cache">;
 def thinlto_emit_imports_files: FF<"thinlto-emit-imports-files">;
 def thinlto_emit_index_files: FF<"thinlto-emit-index-files">;
 def thinlto_index_only: FF<"thinlto-index-only">;
 def thinlto_index_only_eq: JJ<"thinlto-index-only=">;
+def thinlto_full_index: FF<"thinlto-full-index">;
 def thinlto_jobs: JJ<"thinlto-jobs=">,
   HelpText<"Number of ThinLTO jobs. Default to --threads=">;
 def thinlto_object_suffix_replace_eq: JJ<"thinlto-object-suffix-replace=">;
 def thinlto_prefix_replace_eq: JJ<"thinlto-prefix-replace=">;
 def thinlto_single_module_eq: JJ<"thinlto-single-module=">,
   HelpText<"Specific a single module to compile in ThinLTO mode, for debugging only">;
 
 def: J<"plugin-opt=O">, Alias<lto_O>, HelpText<"Alias for --lto-O">;
def: F<"plugin-opt=thinlto-emit-imports-files">,
   Alias<thinlto_emit_imports_files>,
   HelpText<"Alias for --thinlto-emit-imports-files">;
 def: F<"plugin-opt=thinlto-index-only">,
   Alias<thinlto_index_only>,
   HelpText<"Alias for --thinlto-index-only">;
 def: J<"plugin-opt=thinlto-index-only=">,
   Alias<thinlto_index_only_eq>,
   HelpText<"Alias for --thinlto-index-only=">;
+def: F<"plugin-opt=thinlto-full-index">,
+  Alias<thinlto_full_index>,
+  HelpText<"Alias for --thinlto-full-index">;
 def: J<"plugin-opt=thinlto-object-suffix-replace=">,
  Alias<thinlto_object_suffix_replace_eq>,
  HelpText<"Alias for --thinlto-object-suffix-replace=">;
 def: J<"plugin-opt=thinlto-prefix-replace=">,
   Alias<thinlto_prefix_replace_eq>,
   HelpText<"Alias for --thinlto-prefix-replace=">;
 
 // Ignore LTO plugin-related options.

lld/test/ELF/lto/thinlto-full-index.ll

+; REQUIRES: x86
+;; Test --thinlto-full-index for distributed ThinLTO.
+
+; RUN: rm -rf %t && split-file %s %t && cd %t
+; RUN: llvm-mc -filetype=obj -triple=x86_64 a.s -o a.o
+; RUN: llvm-mc -filetype=obj -triple=x86_64 b.s -o b.o
+; RUN: opt -module-summary c.ll -o c.bc
+; RUN: opt -module-summary d.ll -o d.bc
+; RUN: ld.lld --thinlto-index-only=thinlto.index --thinlto-full-index --thinlto-emit-imports-files --start-lib a.o --end-lib c.bc --start-lib b.o --end-lib d.bc -shared -o /dev/null
+;; The index files and imports files are created.
+; RUN: ls c.bc.thinlto.bc c.bc.imports d.bc.thinlto.bc d.bc.imports
+;; Nothing to import.
+; RUN: cat c.bc.imports | count 0
+; RUN: cat d.bc.imports | count 0
+
+;; Check that index file has 2 bitcode objects.
+; RUN: FileCheck %s --check-prefix=CHECK-INDEX < thinlto.index
+; CHECK-INDEX: c.bc
+; CHECK-INDEX-NEXT: d.bc
+
+;; Check that full index file has 2 bitcode objects plus 1 native object.
+; RUN: FileCheck %s --check-prefix=CHECK-FULL < thinlto.index.full
+; CHECK-FULL: c.bc
+; CHECK-FULL-NEXT: b.o
+; CHECK-FULL-NEXT: d.bc
+
+;; No need for importing. Compile both bitcode objects to native objects.
+; RUN: llc c.bc --filetype=obj -o c.o
+; RUN: llc d.bc --filetype=obj -o d.o
+;; Run final link following thinlto.index. Because there is no indication of
+;; where to place the native objects, they are moved to the end of inputs.
+; RUN: not ld.lld c.o d.o --start-lib a.o --end-lib --start-lib b.o --end-lib -o /dev/null 2>&1 | FileCheck %s --check-prefix=CHECK-DUP
+; CHECK-DUP: duplicate symbol: g
+; CHECK-DUP-NEXT: defined at a.o
+; CHECK-DUP-NEXT: defined at b.o
+
+;; Run final link following thinlto.index.full.
+; RUN: ld.lld c.o b.o d.o -o /dev/null
+
+;--- a.s
+.globl g
+g:
+  ret
+
+;--- b.s
+.globl g
+g:
+  ret
+
+.globl f
+f:
+  ret
+
+;--- c.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"
+
+declare void @f()
+
+define void @foo() {
+  call void () @f()
+  ret void
+}
+
+;--- d.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"
+
+declare void @g()
+
+define void @bar() {
+  call void () @g()
+  ret void
+}