[LTO] Parse deplibs sections for possible libcalls.

[mysterymath]

Summary

[LTO] Parse deplibs sections for possible libcalls.

LTO codegen can add symbol references resolved by object files with
.deplibs sections. These object files will be added to the link by
symbol resolution, but parseFile() will never be called on the object
file, so the .deplibs will never be resolved. This can lead to undefined
references.

This change scans the deplibs sections of such object files before LTO
occurs and summarily adds these libraries to the link. Shared libraries
are added as if --as-needed were specified, since they may not end up
actually being required. Similarly, shared libraries will only be
extracted if something actually ends up referencing the newly added
symbols.

Since the problem was first observed on AArch64-specific libcalls, this
also adds an ELF lld target interface for obtaining target-specific
libcalls (those corresponding to setLibcallName() calls in target
lowering). These are filled in for AArch64.

[mysterymath]

Add test case.

[mysterymath]

Fix requires.

[mysterymath]

Add comment.

[mysterymath]

Move parse loop earlier.

[mysterymath]

Update description.

[mysterymath]

Expand the summary.

[MaskRay]

This breaks the symbol resolution model of LTO. The symbol resolution intends to know all symbols and no new symbol can be added after LTO compiling.

[mysterymath]

In D127885#3587455, @MaskRay wrote:

This breaks the symbol resolution model of LTO. The symbol resolution intends to know all symbols and no new symbol can be added after LTO compiling.

Does that apply to symbols like __aarch64_ldadd4_relax? AFAICT, these are only discovered after LTO completes, which is the origin of the issue.
There's a bit of logic to handleLibcalls() before the link, but only if the libcalls are supplied via bitcode themselves, but not if they're provided via object files, as in the test case.

[mysterymath]

I've created https://github.com/llvm/llvm-project/issues/56070 to track the general issue and provide more background on the issue's diagnosis.

[MaskRay]

In D127885#3589557, @mysterymath wrote:

I've created https://github.com/llvm/llvm-project/issues/56070 to track the general issue and provide more background on the issue's diagnosis.

Thanks and I tagged folks who may want to participate in the discussion. Sending the patch without tagging appropriate folks motivated me to click "Request Changes".

[mysterymath]

Extract deplibs before LTO, as discussed in #56070.

This substantially reworks the change to partially parse deplibs sections from
object files that provide libcalls. A target interface is also added to supply
target-specific libcall names; this is filled out for AArch64.

Any found shared libraries are added as-needed, since the libcalls that might
require them may never be emitted. Static libraries are added lazily, as usual.

[mysterymath]

Since there wasn't a clear resolution around the ideal semantics, I'll abandon this change.

lld/ELF/Arch/AArch64.cpp

 //===- AArch64.cpp --------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "lld/Common/ErrorHandler.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/BinaryFormat/ELF.h"
 #include "llvm/Support/Endian.h"
 
 using namespace llvm;
 using namespace llvm::support::endian;
 using namespace llvm::ELF;
 using namespace lld;
 using namespace lld::elf;
void relocate(uint8_t *loc, const Relocation &rel,
                 uint64_t val) const override;
   RelExpr adjustTlsExpr(RelType type, RelExpr expr) const override;
   void relaxTlsGdToLe(uint8_t *loc, const Relocation &rel,
                       uint64_t val) const override;
   void relaxTlsGdToIe(uint8_t *loc, const Relocation &rel,
                       uint64_t val) const override;
   void relaxTlsIeToLe(uint8_t *loc, const Relocation &rel,
                       uint64_t val) const override;
+  ArrayRef<const char*> libcalls() const override;
 };
 } // namespace
 
 AArch64::AArch64() {
   copyRel = R_AARCH64_COPY;
   relativeRel = R_AARCH64_RELATIVE;
   iRelativeRel = R_AARCH64_IRELATIVE;
   gotRel = R_AARCH64_GLOB_DAT;
if (pacEntry)
     memcpy(buf + sizeof(addrInst), pacBr, sizeof(pacBr));
   else
     memcpy(buf + sizeof(addrInst), stdBr, sizeof(stdBr));
   if (!hasBti)
     // We didn't add the BTI c instruction so round out size with NOP.
     memcpy(buf + sizeof(addrInst) + sizeof(stdBr), nopData, sizeof(nopData));
 }
 
+#define LCALLNAMES(A, N)                                                       \
+  #A #N "_relax",                                                              \
+  #A #N "_acq",                                                                \
+  #A #N "_rel",                                                                \
+  #A #N "_acq_rel",
+#define LCALLNAME4(A)                                                          \
+  LCALLNAMES(A, 1)                                                             \
+  LCALLNAMES(A, 2) LCALLNAMES(A, 4) LCALLNAMES(A, 8)
+#define LCALLNAME5(A)                                                          \
+  LCALLNAMES(A, 1)                                                             \
+  LCALLNAMES(A, 2)                                                             \
+  LCALLNAMES(A, 4) LCALLNAMES(A, 8) LCALLNAMES(A, 16)
+
+static const char *aarch64Libcalls[] = {
+    LCALLNAME5(__aarch64_cas)
+    LCALLNAME4(__aarch64_swp)
+    LCALLNAME4(__aarch64_ldadd)
+    LCALLNAME4(__aarch64_ldset)
+    LCALLNAME4(__aarch64_ldclr)
+    LCALLNAME4(__aarch64_ldeor)
+};
+
+#undef LCALLNAMES
+#undef LCALLNAME4
+#undef LCALLNAME5
+
+ArrayRef<const char *> AArch64::libcalls() const {
+  return makeArrayRef(aarch64Libcalls);
+}
+
 static TargetInfo *getTargetInfo() {
   if (config->andFeatures & (GNU_PROPERTY_AARCH64_FEATURE_1_BTI |
                              GNU_PROPERTY_AARCH64_FEATURE_1_PAC)) {
     static AArch64BtiPac t;
     return &t;
   }
   static AArch64 t;
   return &t;
 }
 
 TargetInfo *elf::getAArch64TargetInfo() { return getTargetInfo(); }

lld/ELF/Driver.cpp

static void handleUndefinedGlob(StringRef arg) {
   for (Symbol *sym : symtab->symbols())
     if (!sym->isPlaceholder() && pat->match(sym->getName()))
       syms.push_back(sym);
 
   for (Symbol *sym : syms)
     handleUndefined(sym, "--undefined-glob");
 }
 
+template <class ELFT> static void parseDeplibs(InputFile *file) {
+  assert(file->lazy);
+  if (auto *f = dyn_cast<ObjFile<ELFT>>(file))
+    f->parseDeplibs();
+}
+
 static void handleLibcall(StringRef name) {
   Symbol *sym = symtab->find(name);
   if (!sym || !sym->isLazy())
     return;
 
   MemoryBufferRef mb;
   mb = cast<LazyObject>(sym)->file->mb;
 
   if (isBitcode(mb))
     sym->extract();
+  else if (config->dependentLibraries && !config->relocatable)
+    invokeELFT(parseDeplibs, sym->file);
 }
 
 void LinkerDriver::writeArchiveStats() const {
   if (config->printArchiveStats.empty())
     return;
 
   std::error_code ec;
   raw_fd_ostream os(config->printArchiveStats, ec, sys::fs::OF_None);
void LinkerDriver::link(opt::InputArgList &args) {
   {
     llvm::TimeTraceScope timeScope("Parse input files");
     for (size_t i = 0; i < files.size(); ++i) {
       llvm::TimeTraceScope timeScope("Parse input files", files[i]->getName());
       parseFile(files[i]);
     }
   }
 
-  // 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).
-  config->hasDynSymTab =
-      !sharedFiles.empty() || config->isPic || config->exportDynamic;
-
   // Some symbols (such as __ehdr_start) are defined lazily only when there
   // are undefined symbols for them, so we add these to trigger that logic.
   for (StringRef name : script->referencedSymbols) {
     Symbol *sym = addUnusedUndefined(name);
     sym->isUsedInRegularObj = true;
     sym->referenced = true;
   }
 
void LinkerDriver::link(opt::InputArgList &args) {
   // However, adding all libcall symbols to the link can have undesired
   // consequences. For example, the libgcc implementation of
   // __sync_val_compare_and_swap_8 on 32-bit ARM pulls in an .init_array entry
   // that aborts the program if the Linux kernel does not support 64-bit
   // atomics, which would prevent the program from running even if it does not
   // use 64-bit atomics.
   //
   // Therefore, we only add libcall symbols to the link before LTO if we have
-  // to, i.e. if the symbol's definition is in bitcode. Any other required
-  // libcall symbols will be added to the link after LTO when we add the LTO
-  // object file to the link.
-  if (!bitcodeFiles.empty())
+  // to, i.e. if the symbol's definition is in bitcode. If the definition's
+  // object files contain deplibs, these are summarily added to the link as
+  // well, since the set of input files must be fixed by the time LTO occurs.
+  // Any other required libcall symbols will be added to the link after LTO when
+  // we add the LTO object file to the link.
+  const size_t numFilesBeforeLibcalls = files.size();
+  if (!bitcodeFiles.empty()) {
     for (auto *s : lto::LTO::getRuntimeLibcallSymbols())
       handleLibcall(s);
+    for (auto *s : target->libcalls())
+      handleLibcall(s);
+  }
+
+  // Handling libcalls may have added new input files to the link via deplibs,
+  // so parse them.
+  {
+    llvm::TimeTraceScope timeScope("Parse input files");
+    for (size_t i = numFilesBeforeLibcalls; i < files.size(); ++i) {
+      llvm::TimeTraceScope timeScope("Parse input files", files[i]->getName());
+      parseFile(files[i]);
+    }
+  }
+
+  // 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).
+  config->hasDynSymTab =
+      !sharedFiles.empty() || config->isPic || config->exportDynamic;
 
   // Archive members defining __wrap symbols may be extracted.
   std::vector<WrappedSymbol> wrapped = addWrappedSymbols(args);
 
   // No more lazy bitcode can be extracted at this point. Do post parse work
   // like checking duplicate symbols.
   parallelForEach(objectFiles, initializeLocalSymbols);
   parallelForEach(objectFiles, postParseObjectFile);

lld/ELF/InputFiles.h

public:
 
   ObjFile(MemoryBufferRef m, StringRef archiveName) : ELFFileBase(ObjKind, m) {
     this->archiveName = archiveName;
   }
 
   void parse(bool ignoreComdats = false);
   void parseLazy();
 
+  // Parse only the dependent library sections and add the referenced libraries.
+  // Needed to finalize the set of input files possibly referenced by libcalls
+  // before LTO.
+  void parseDeplibs();
+
   StringRef getShtGroupSignature(ArrayRef<Elf_Shdr> sections,
                                  const Elf_Shdr &sec);
 
   Symbol &getSymbol(uint32_t symbolIndex) const {
     if (symbolIndex >= this->symbols.size())
       fatal(toString(this) + ": invalid symbol index");
     return *this->symbols[symbolIndex];
   }
public:
   // True if the file defines functions compiled with
   // -fsplit-stack. Usually false.
   bool splitStack = false;
 
   // True if the file defines functions compiled with -fsplit-stack,
   // but had one or more functions with the no_split_stack attribute.
   bool someNoSplitStack = false;
 
+  // True if the dependent library sections have already been parsed and the
+  // contents added to the link.
+  bool parsedDeplibs = false;
+
   // Get cached DWARF information.
   DWARFCache *getDwarf();
 
   void initializeLocalSymbols();
   void postParse();
 
 private:
   void initializeSections(bool ignoreComdats,

lld/ELF/InputFiles.cpp

 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "lld/Common/CommonLinkerContext.h"
 #include "lld/Common/DWARF.h"
 #include "llvm/ADT/CachedHashString.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/ScopeExit.h"
 #include "llvm/LTO/LTO.h"
 #include "llvm/Object/IRObjectFile.h"
 #include "llvm/Support/ARMAttributeParser.h"
 #include "llvm/Support/ARMBuildAttributes.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/RISCVAttributeParser.h"

 template <class ELFT> void ObjFile<ELFT>::parse(bool ignoreComdats) {
   object::ELFFile<ELFT> obj = this->getObj();
   // Read a section table. justSymbols is usually false.
   if (this->justSymbols)
     initializeJustSymbols();
   else
     initializeSections(ignoreComdats, obj);
 
+  parsedDeplibs = true;
+
   // Read a symbol table.
   initializeSymbols(obj);
 }
 
 // Sections with SHT_GROUP and comdat bits define comdat section groups.
 // They are identified and deduplicated by group name. This function
 // returns a group name.
 template <class ELFT>
if (Error e = attributes.parse(contents, support::little)) {
         in.attributes = std::make_unique<InputSection>(*this, sec, name);
         return in.attributes.get();
       }
       return &InputSection::discarded;
     }
   }
 
   if (sec.sh_type == SHT_LLVM_DEPENDENT_LIBRARIES && !config->relocatable) {
+    if (parsedDeplibs)
+      return &InputSection::discarded;
+
     ArrayRef<char> data =
         CHECK(this->getObj().template getSectionContentsAsArray<char>(sec), this);
     if (!data.empty() && data.back() != '\0') {
       error(toString(this) +
             ": corrupted dependent libraries section (unterminated string): " +
             name);
       return &InputSection::discarded;
     }
template <class ELFT> void ObjFile<ELFT>::parseLazy() {
   for (Symbol *sym : makeArrayRef(symbols).slice(firstGlobal))
     if (sym) {
       sym->resolve(LazyObject{*this});
       if (!lazy)
         return;
     }
 }
 
+template <class ELFT> void ObjFile<ELFT>::parseDeplibs() {
+  if (parsedDeplibs)
+    return;
+  parsedDeplibs = true;
+
+  ArrayRef<Elf_Shdr> objSections = getELFShdrs<ELFT>();
+  StringRef shstrtab =
+      CHECK(this->getObj().getSectionStringTable(objSections), this);
+  for (size_t i = 0, e = objSections.size(); i != e; ++i) {
+    const Elf_Shdr &sec = objSections[i];
+    if (sec.sh_type != SHT_LLVM_DEPENDENT_LIBRARIES ||
+        sec.sh_flags & SHF_EXCLUDE)
+      continue;
+
+    StringRef name = check(this->getObj().getSectionName(sec, shstrtab));
+    ArrayRef<char> data = CHECK(
+        this->getObj().template getSectionContentsAsArray<char>(sec), this);
+    if (!data.empty() && data.back() != '\0') {
+      error(
+          toString(this) +
+          ": corrupted dependent libraries section (unterminated string): " +
+          name);
+    }
+    // Shared libraries found through this process may not be needed if LTO
+    // doesn't emit the corresponding libcalls.
+    auto resetAsNeeded = make_scope_exit(
+        [oldAsNeeded = config->asNeeded] { config->asNeeded = oldAsNeeded; });
+    config->asNeeded = true;
+    for (const char *d = data.begin(), *e = data.end(); d < e;) {
+      StringRef s(d);
+      addDependentLibrary(s, this);
+      d += s.size() + 1;
+    }
+  }
+}
+
 bool InputFile::shouldExtractForCommon(StringRef name) {
   if (isBitcode(mb))
     return isBitcodeNonCommonDef(mb, name, archiveName);
 
   return isNonCommonDef(mb, name, archiveName);
 }
 
 std::string elf::replaceThinLTOSuffix(StringRef path) {

lld/ELF/Target.h

virtual void relocate(uint8_t *loc, const Relocation &rel,
                         uint64_t val) const = 0;
   void relocateNoSym(uint8_t *loc, RelType type, uint64_t val) const {
     relocate(loc, Relocation{R_NONE, type, 0, 0, nullptr}, val);
   }
 
   virtual void applyJumpInstrMod(uint8_t *loc, JumpModType type,
                                  JumpModType val) const {}
 
+  // Returns a list of target-specific runtime libcalls, not including
+  // target-independent libcalls.
+  virtual ArrayRef<const char *> libcalls() const { return {}; }
+
   virtual ~TargetInfo();
 
   // This deletes a jump insn at the end of the section if it is a fall thru to
   // the next section.  Further, if there is a conditional jump and a direct
   // jump consecutively, it tries to flip the conditional jump to convert the
   // direct jump into a fall thru and delete it.  Returns true if a jump
   // instruction can be deleted.
   virtual bool deleteFallThruJmpInsn(InputSection &is, InputFile *file,

lld/test/ELF/deplibs-lto-shared.s

+# REQUIRES: aarch64
+
+# RUN: rm -rf %t.inputs %t.dir
+# RUN: mkdir -p %t.inputs %t.dir
+# RUN: split-file %s %t.inputs
+# RUN: llvm-mc -filetype=obj -triple=aarch64 %t.inputs/deplibs.s -o %tdeplibs.o
+# RUN: llvm-mc -filetype=obj -triple=aarch64 %t.inputs/foo.s -o %tfoo.o
+# RUN: llvm-as %t.inputs/lto.ll -o %t.o
+# RUN: llvm-ar rc %t.dir/libdeplibs.a %tdeplibs.o
+# RUN: ld.lld %tfoo.o -o %t.dir/libfoo.so -shared
+
+# LTO can emit libcalls that are resolved using libraries that contain .deplibs.
+# Such libraries must be handled as if they were input files, and any referenced
+# deplibs must be added to the link. Otherwise, symbols in the library may go
+# undefined. Shared libraries added this way should be as-needed, since the
+# libcalls may not actually be emitted.
+
+# RUN: ld.lld %t.o -u a -o %t -L %t.dir -ldeplibs --trace 2>&1 | \
+# RUN:   FileCheck %s -DOBJ=%t.o -DDIR=%t.dir
+# RUN: llvm-readobj -d %t | FileCheck --check-prefix=OBJ %s
+
+# CHECK:      [[OBJ]]
+# CHECK-NEXT: [[DIR]]{{[\\/]}}libfoo.so
+# OBJ-NOT: NEEDED
+
+#--- foo.s
+.global foo
+foo:
+#--- deplibs.s
+.global __aarch64_ldadd4_relax
+__aarch64_ldadd4_relax:
+    b foo
+.section ".deplibs","MS",@llvm_dependent_libraries,1
+    .asciz "foo"
+.section ".deplibs.excluded","eMS",@llvm_dependent_libraries,1
+    .asciz "bar"
+#--- lto.ll
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64"
+
+define void @_start() {
+  ret void
+}

lld/test/ELF/deplibs-lto-static.s

+# REQUIRES: aarch64
+
+# RUN: rm -rf %t.inputs %t.dir
+# RUN: mkdir -p %t.inputs %t.dir
+# RUN: split-file %s %t.inputs
+# RUN: llvm-mc -filetype=obj -triple=aarch64 %t.inputs/deplibs.s -o %tdeplibs.o
+# RUN: llvm-mc -filetype=obj -triple=aarch64 %t.inputs/foo.s -o %tfoo.o
+# RUN: llvm-as %t.inputs/lto.ll -o %t.o
+# RUN: llvm-ar rc %t.dir/libdeplibs.a %tdeplibs.o
+# RUN: llvm-ar rc %t.dir/libfoo.a %tfoo.o
+
+# LTO can emit libcalls that are resolved using libraries that contain .deplibs.
+# Such libraries must be handled as if they were input files, and any referenced
+# deplibs must be added to the link. Otherwise, symbols in the library may go
+# undefined.
+
+# RUN: ld.lld %t.o -u a -o /dev/null -L %t.dir -ldeplibs --trace 2>&1 | \
+# RUN:   FileCheck %s -DOBJ=%t.o -DDIR=%t.dir
+
+# CHECK:      [[OBJ]]
+# CHECK-NEXT: [[DIR]]{{[\\/]}}libdeplibs.a
+# CHECK-NEXT: [[DIR]]{{[\\/]}}libfoo.a
+
+#--- foo.s
+.global foo
+foo:
+#--- deplibs.s
+.global __aarch64_ldadd4_relax
+__aarch64_ldadd4_relax:
+    b foo
+.section ".deplibs","MS",@llvm_dependent_libraries,1
+    .asciz "foo"
+#--- lto.ll
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64"
+
+define void @a(i32* nocapture %0) #0 {
+  %2 = atomicrmw add i32* %0, i32 1 monotonic, align 4
+  ret void
+}
+
+define void @_start() {
+  ret void
+}
+
+attributes #0 = { "target-features"="+outline-atomics" }