[lld-link] resolve defined symbols before undefineds

[nico]

We agreed in #124294 that we should do this.

More links: https://reviews.llvm.org/D95985 (does this for ELF for regular files), https://reviews.llvm.org/D106293 (does this for lld/MachO for regular files), bd448f0 (lld/ELF for bitcode), #67445 (does this for lld/MachO for bitcode).

[llvmbot]

@llvm/issue-subscribers-lld-coff

Author: Nico Weber (nico)

We agreed in #124294 that we should do this.

More links: https://reviews.llvm.org/D95985 (does this for ELF for regular files), https://reviews.llvm.org/D106293 (does this for lld/MachO for regular files), bd448f0 (lld/ELF for bitcode), #67445 (does this for lld/MachO for bitcode).

[nico]

This might do the right thing for regular files:

diff --git a/lld/COFF/InputFiles.cpp b/lld/COFF/InputFiles.cpp
index fe1135db636c..d7e454d9d27a 100644
--- a/lld/COFF/InputFiles.cpp
+++ b/lld/COFF/InputFiles.cpp
@@ -497,11 +497,12 @@ void ObjFile::initializeSymbols() {
       coffObj->getNumberOfSections() + 1);
   COFFLinkerContext &ctx = symtab.ctx;
 
+  SmallVector<unsigned, 32> undefineds;
   for (uint32_t i = 0; i < numSymbols; ++i) {
     COFFSymbolRef coffSym = check(coffObj->getSymbol(i));
     bool prevailingComdat;
     if (coffSym.isUndefined()) {
-      symbols[i] = createUndefined(coffSym, false);
+      undefineds.push_back(i);
     } else if (coffSym.isWeakExternal()) {
       auto aux = coffSym.getAux<coff_aux_weak_external>();
       bool overrideLazy = true;
@@ -566,6 +567,17 @@ void ObjFile::initializeSymbols() {
     symbols[i] = createRegular(sym);
   }
 
+  // Undefined symbols can trigger recursive fetch from Archives due to
+  // LazySymbols. Process defined symbols first so that the relative order
+  // between a defined symbol and an undefined symbol does not change the
+  // symbol resolution behavior. In addition, a set of interconnected symbols
+  // will all be resolved to the same file, instead of being resolved to
+  // different files.
+  for (unsigned i : undefineds) {
+    COFFSymbolRef coffSym = check(coffObj->getSymbol(i));
+    symbols[i] = createUndefined(coffSym, false);
+  }
+
   for (auto &kv : weakAliases) {
     Symbol *sym = kv.first;
     const coff_aux_weak_external *aux = kv.second;

We could then possibly remove these two FIXMEs:

diff --git a/lld/COFF/SymbolTable.cpp b/lld/COFF/SymbolTable.cpp
index eff840d4d56c..c1b9631dc3ec 100644
--- a/lld/COFF/SymbolTable.cpp
+++ b/lld/COFF/SymbolTable.cpp
@@ -56,10 +56,7 @@ static void forceLazy(Symbol *s) {
   }
   case Symbol::Kind::LazyObjectKind: {
     InputFile *file = cast<LazyObject>(s)->file;
-    // FIXME: Remove this once we resolve all defineds before all undefineds in
-    //        ObjFile::initializeSymbols().
-    if (!file->lazy)
-      return;
+    CHECK(file->lazy);
     file->lazy = false;
     file->symtab.ctx.driver.addFile(file);
     break;
diff --git a/lld/COFF/InputFiles.cpp b/lld/COFF/InputFiles.cpp
index bb9f1407b51f..b373aa097f56 100644
--- a/lld/COFF/InputFiles.cpp
+++ b/lld/COFF/InputFiles.cpp
@@ -190,13 +190,6 @@ void ArchiveFile::addMember(const Archive::Symbol &sym) {
   const Archive::Child &c =
       CHECK(sym.getMember(), "could not get the member for symbol " +
                                  toCOFFString(symtab.ctx, sym));
-
-  // Return an empty buffer if we have already returned the same buffer.
-  // FIXME: Remove this once we resolve all defineds before all undefineds in
-  //        ObjFile::initializeSymbols().
-  if (!seen.insert(c.getChildOffset()).second)
-    return;
-
   symtab.ctx.driver.enqueueArchiveMember(c, sym, getName());
 }

We still want to do something similar in BitcodeFile::parse().

However, I so far failed writing a test that shows the difference from the above change. Here's what I tried:

% cat lld/test/COFF/weak-definition-in-main-file.s 
# REQUIRES: x86
# RUN: rm -rf %t; split-file %s %t

## Test that a weak symbol in a direct .obj file wins over
## a weak symbol in a .lib file.

# RUN: llvm-mc -filetype=obj -triple=x86_64-windows %t/test.s -o %t/test.obj
# RUN: llvm-mc -filetype=obj -triple=x86_64-windows %t/weakfoo.s -o %t/weakfoo.obj

# RUN: llvm-ar rcs %t/weakfoo.lib %t/weakfoo.obj

# PREFER-DIRECT-OBJECT: stosb

# RUN: lld-link /out:%t/out.dll /dll %t/weakfoo.lib %t/test.obj /subsystem:console
# RUN: llvm-objdump -d %t/out.dll | FileCheck %s --check-prefix=PREFER-DIRECT-OBJECT

#--- weakfoo.s
.text
.globl _baz
_baz:
  ret

.section .text$_foo, "rx", discard, _foo
.globl _foo
_foo:
  stosw
  ret

.section .drectve
.ascii "-export:_baz -export:_foo"

#--- test.s
.text
.globl _DllMainCRTStartup
_DllMainCRTStartup:
  # This pulls in weakfoo.lib due to the _baz undef, but _foo should
  # still be resolved against the weak symbol in this file.
  callq _baz
  callq _foo
  ret

.section .text$_foo, "rx", discard, _foo
.globl _foo
_foo:
  stosb
  ret

.section .drectve
.ascii "-export:_DllMainCRTStartup -export:_foo"

But that already passes without the code change, because the undefined is at the end of the symbol table in test.obj:

% /Users/thakis/src/llvm-project/out/gn/bin/llvm-objdump --syms /Users/thakis/src/llvm-project/out/gn/obj/lld/test/COFF/Output/weak-definition-in-main-file.s.tmp/test.obj

/Users/thakis/src/llvm-project/out/gn/obj/lld/test/COFF/Output/weak-definition-in-main-file.s.tmp/test.obj:	file format coff-x86-64

SYMBOL TABLE:
[ 0](sec  1)(fl 0x00)(ty   0)(scl   3) (nx 1) 0x00000000 .text
AUX scnlen 0xb nreloc 2 nlnno 0 checksum 0x658c4807 assoc 1 comdat 0
[ 2](sec  2)(fl 0x00)(ty   0)(scl   3) (nx 1) 0x00000000 .data
AUX scnlen 0x0 nreloc 0 nlnno 0 checksum 0x0 assoc 2 comdat 0
[ 4](sec  3)(fl 0x00)(ty   0)(scl   3) (nx 1) 0x00000000 .bss
AUX scnlen 0x0 nreloc 0 nlnno 0 checksum 0x0 assoc 3 comdat 0
[ 6](sec  4)(fl 0x00)(ty   0)(scl   3) (nx 1) 0x00000000 .text$_foo
AUX scnlen 0x2 nreloc 0 nlnno 0 checksum 0x5685c769 assoc 4 comdat 2
[ 8](sec  4)(fl 0x00)(ty   0)(scl   2) (nx 0) 0x00000000 _foo
[ 9](sec  5)(fl 0x00)(ty   0)(scl   3) (nx 1) 0x00000000 .drectve
AUX scnlen 0x27 nreloc 0 nlnno 0 checksum 0xf3086511 assoc 5 comdat 0
[11](sec  1)(fl 0x00)(ty   0)(scl   2) (nx 0) 0x00000000 _DllMainCRTStartup
[12](sec  0)(fl 0x00)(ty   0)(scl   2) (nx 0) 0x00000000 _baz

In ELF and MachO, a similar test worked.

Does anyone have an idea how we might test this? Is there a way to explicitly say "_baz is an undefined; please list it at the top of the symbol table"?

[nico]

@mstorsjo In case you happen to know the answer to the question above :)

[aganea]

Just a pass-by note: I think #85290 solves the issue of recursive load of OBJs by postponing OBJs containing undefines into a low-priority queue, which is iterated on after the main queue. I think it's a better solution overall than the undefineds proposed above, since it processes each OBJ on its own. If we later want to process OBJs in parallel (which would be nice) that recursivity -even treated separately by undefines- might make things more complicated.

Also as a secondary note, in the mentionned PR, OBJs in -start-lib / -end-lib are treated like regular Archives as they should be, which makes them fully lazy (see case OPT_start_lib in Driver.cpp).

[rnk]

Just a pass-by note: I think #85290 solves the issue of recursive load of OBJs by postponing OBJs containing undefines into a low-priority queue, which is iterated on after the main queue. I think it's a better solution overall than the undefineds proposed above, since it processes each OBJ on its own. If we later want to process OBJs in parallel (which would be nice) that recursivity -even treated separately by undefines- might make things more complicated.

Also as a secondary note, in the mentionned PR, OBJs in -start-lib / -end-lib are treated like regular Archives as they should be, which makes them fully lazy (see case OPT_start_lib in Driver.cpp).

I had forgotten about #85290 , but if that's a step towards parallelizing input parsing, I'll prioritize it.

[aganea]

@rnk I've split that change locally into smaller bits, but never got around to send PRs yet. #85290 contains too many things: 1. Treating -start-lib/-end-lib as regular archives. 2. handling parsing directives early on, for proper /DEFAULTLIB handling that follows the MSVC spec. 3. early machine type detection. 4. the unresolved symbol parsing which follows the MSVC spec.

As for symbols parallelization, I started some very early work on it last year, but I'd like to upstream the above first. And perhaps @cjacek might have some extra changes for ARM64EC?

[nico]

1. Treating -start-lib/-end-lib as regular archives.

FWIW, ELF went in the other direction: It first added support for thin archives without symbol tables and gave those --start-lib / --end-lib semantics (https://reviews.llvm.org/D117284) and then handled archives that way (https://reviews.llvm.org/D119074), since you need less hashing that way.

[mstorsjo]

Does anyone have an idea how we might test this? Is there a way to explicitly say "_baz is an undefined; please list it at the top of the symbol table"?

Hmm, I wouldn't think it's possible to do that from a .S source - but with yaml2obj I would expect that it's possible to craft exactly the kind of object file we want?