[ELF] Skip repeated libraries.

[ikudrin]

Summary

If a library is added in the link several times, there is no need to process it more than once, because LLD is able to resolve back refs. The optimization is especially useful for the dependent libraries feature, where the same library may be referenced many times in input files.

[MaskRay]

I am skeptical about the change.

• The duplicated libraries are usually indicator of user errors or build system brittleness.
• The current way the state is introduced is incompatible with the direction on LLD-as-a-library (D88348) (This can be fixed).
• The --verbose now diverges from GNU ld and gold. (This is usually a tie-breaker instead of a decisive reason.)
• When duplicated libraries happen, the archive index can guarantee that the performance is not degraded.

[ikudrin]

In D88944#2316011, @MaskRay wrote:

I am skeptical about the change.

• The duplicated libraries are usually indicator of user errors or build system brittleness.

The provided optimization is aimed to slightly improve the dependent libraries' case, where lots (hundreds) of references is very common. In a regular link, its impact is not expected to be noticeable.

• The current way the state is introduced is incompatible with the direction on LLD-as-a-library (D88348) (This can be fixed).

Do you mean that addedLibraries is not reset on reenter? If so, the same is true for other members of LinkerDriver as well, so the patch does not make the situation worse.

• The --verbose now diverges from GNU ld and gold. (This is usually a tie-breaker instead of a decisive reason.)

Well, we should not imitate GNU linkers in every nuance, especially in the internals, aren't we?

• When duplicated libraries happen, the archive index can guarantee that the performance is not degraded.

The more repeated libraries referenced, the more time and memory the optimization saves. Even reading and basically parsing the archive files takes some time, and if there are hundreds of them, the improvement becomes noticeable. Of course, saving is not huge, but why not have it if the implementation is cheap?

[MaskRay]

In D88944#2316057, @ikudrin wrote:

In D88944#2316011, @MaskRay wrote:

I am skeptical about the change.

• The duplicated libraries are usually indicator of user errors or build system brittleness.

The provided optimization is aimed to slightly improve the dependent libraries' case, where lots (hundreds) of references is very common. In a regular link, its impact is not expected to be noticeable.

• The current way the state is introduced is incompatible with the direction on LLD-as-a-library (D88348) (This can be fixed).

Do you mean that addedLibraries is not reset on reenter? If so, the same is true for other members of LinkerDriver as well, so the patch does not make the situation worse.

• The --verbose now diverges from GNU ld and gold. (This is usually a tie-breaker instead of a decisive reason.)

Well, we should not imitate GNU linkers in every nuance, especially in the internals, aren't we?

• When duplicated libraries happen, the archive index can guarantee that the performance is not degraded.

The more repeated libraries referenced, the more time and memory the optimization saves. Even reading and basically parsing the archive files takes some time, and if there are hundreds of them, the improvement becomes noticeable. Of course, saving is not huge, but why not have it if the implementation is cheap?

The implementation may look cheap but "the provided optimization is aimed to slightly improve the dependent libraries' case" The benefit may not be noticeable. So far I am on the fence. However, then there are a few downsides including the incompatibility with --warn-backrefs and --verbose output. (The !config->formatBinary && !inWholeArchive condition looks subtle and can be error-prone as well)

[ikudrin]

I've made some tests and speculatively estimate the saving up to several seconds for a relatively large library (about 100000 symbols) which is referenced several hundred times. For me, that is noticeable.

lld/ELF/Driver.h

private:
 
   // True if we are in --start-lib and --end-lib.
   bool inLib = false;
 
   // For LTO.
   std::unique_ptr<BitcodeCompiler> lto;
 
   std::vector<InputFile *> files;
+
+  llvm::StringSet<> addedLibraries;
 };
 
 // Parses command line options.
 class ELFOptTable : public llvm::opt::OptTable {
 public:
   ELFOptTable();
   llvm::opt::InputArgList parse(ArrayRef<const char *> argv);
 };

lld/ELF/Driver.cpp

std::vector<std::pair<MemoryBufferRef, uint64_t>> static getArchiveMembers(
 
   return v;
 }
 
 // Opens a file and create a file object. Path has to be resolved already.
 void LinkerDriver::addFile(StringRef path, bool withLOption) {
   using namespace sys::fs;
 
+  // If we have already added the file as a library, no need to do that again.
+  // However, there are a few cases when the file might be processed in
+  // a different way and the optimization should be avoided.
+  if (!config->warnBackrefs && !config->formatBinary && !inWholeArchive &&
+      addedLibraries.contains(path))
+    return;
+
   Optional<MemoryBufferRef> buffer = readFile(path);
   if (!buffer.hasValue())
     return;
   MemoryBufferRef mbref = *buffer;
 
   if (config->formatBinary) {
     files.push_back(make<BinaryFile>(mbref));
     return;
   }
 
   switch (identify_magic(mbref.getBuffer())) {
   case file_magic::unknown:
     readLinkerScript(mbref);
     return;
   case file_magic::archive: {
+    // The optimization is incompatible with --warn-backrefs; do not waste time
+    // filling the set in that case.
+    if (!config->warnBackrefs)
+      addedLibraries.insert(path);
+
     // Handle -whole-archive.
     if (inWholeArchive) {
       for (const auto &p : getArchiveMembers(mbref))
         files.push_back(createObjectFile(p.first, path, p.second));
       return;
     }
 
     std::unique_ptr<Archive> file =

lld/test/ELF/print-archive-stats.s

 #      CHECK:members  fetched archive
 # CHECK-NEXT:1  0 [[T]]weak.a
 # CHECK-NEXT:3  2 [[T]]1.a
 
 ## - means stdout.
 # RUN: ld.lld %t.o %tweak.a %t1.a --print-archive-stats=- -o /dev/null | diff %t.txt -
 
 ## The second %t1.a has 0 fetched member.
-# RUN: ld.lld %t.o %tweak.a %t1.a %t1.a --print-archive-stats=- -o /dev/null | \
+## Note: --warn-backrefs disables the optimization which skips repeated archives.
+# RUN: ld.lld %t.o %tweak.a %t1.a %t1.a --print-archive-stats=- --warn-backrefs -o /dev/null | \
 # RUN:   FileCheck --check-prefix=CHECK2 %s
 # CHECK2:      members  fetched archive
 # CHECK2-NEXT: 1  0 {{.*}}weak.a
 # CHECK2-NEXT: 3  2 {{.*}}1.a
 # CHECK2-NEXT: 3  0 {{.*}}1.a
 
 # RUN: not ld.lld -shared %t.o --print-archive-stats=/ -o /dev/null 2>&1 | FileCheck --check-prefix=ERR %s
 # ERR: error: --print-archive-stats=: cannot open /: {{.*}}
 
 .globl _start
 .weak weak
 _start:
   call foo
   call bar
   call weak

lld/test/ELF/skip-repeated-libs.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t.o
+# RUN: echo ".global foo; foo:" | \
+# RUN:   llvm-mc -filetype=obj -triple=x86_64 - -o %t1.o
+# RUN: rm -f %t1.a && llvm-ar rc %t1.a %t1.o
+
+## The linker can resolve backrefs, so the repeated adding of the library can be skipped.
+# RUN: ld.lld %t1.a %t1.a %t.o -o /dev/null --verbose 2>&1 | FileCheck %s
+# CHECK:     {{.*}}1.a
+# CHECK-NOT: {{.*}}1.a
+
+## If the repeated definition is given after -whole-archive, it should not be skipped.
+# RUN: ld.lld %t1.a -whole-archive %t1.a %t.o -o /dev/null --verbose 2>&1 | FileCheck %s --check-prefix=WHA
+# WHA:      {{.*}}1.a
+# WHA-NEXT: {{.*}}1.a
+
+## If, for any reason, the second definition is given after -format binary,
+## it should not be skipped.
+# RUN: ld.lld %t.o %t1.a -format binary %t1.a -o %t
+# RUN: llvm-nm %t | FileCheck --check-prefix=BINARY %s
+# BINARY: D _binary_{{.+}}1_a_start
+
+  .global _start
+_start:
+  call foo