[lld/mac] Resolve defined symbols before undefined symbols

[thakis]

Summary

Ports https://reviews.llvm.org/D95985 to the MachO port.
Happens to fix PR51135; see that bug for details.
Also makes lld's behavior match ld64 for the included test case.

[thakis]

forgot to amend local test change to final commit

(i verified that the test fails without the code change)

[int3]

Nice!

lld/MachO/InputFiles.cpp

602

nit: how about undefineds?

[thakis]

Thanks!

lld/MachO/InputFiles.cpp

602

Sure, done.

lld/ELF/InputFiles.cpp

else if (sec == &InputSection::discarded)
           make<Undefined>(this, name, STB_LOCAL, eSym.st_other, type,
                           /*discardedSecIdx=*/secIdx);
     else
       this->symbols[i] = make<Defined>(this, name, STB_LOCAL, eSym.st_other,
                                        type, eSym.st_value, eSym.st_size, sec);
   }
 
   // Symbol resolution of non-local symbols.
-  SmallVector<unsigned, 32> unds;
+  SmallVector<unsigned, 32> undefineds;
   for (size_t i = firstGlobal, end = eSyms.size(); i != end; ++i) {
     const Elf_Sym &eSym = eSyms[i];
     uint8_t binding = eSym.getBinding();
     if (binding == STB_LOCAL)
       continue; // Errored above.
 
     uint32_t secIdx = getSectionIndex(eSym);
     InputSectionBase *sec = this->sections[secIdx];
     uint8_t stOther = eSym.st_other;
     uint8_t type = eSym.getType();
     uint64_t value = eSym.st_value;
     uint64_t size = eSym.st_size;
     StringRefZ name = this->stringTable.data() + eSym.st_name;
 
     // Handle global undefined symbols.
     if (eSym.st_shndx == SHN_UNDEF) {
-      unds.push_back(i);
+      undefineds.push_back(i);
       continue;
     }
 
     // Handle global common symbols.
     if (eSym.st_shndx == SHN_COMMON) {
       if (value == 0 || value >= UINT32_MAX)
         fatal(toString(this) + ": common symbol '" + StringRef(name.data) +
               "' has invalid alignment: " + Twine(value));
template <class ELFT> void ObjFile<ELFT>::initializeSymbols() {
   }
 
   // Undefined symbols (excluding those defined relative to non-prevailing
   // sections) can trigger recursive fetch. 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 : unds) {
+  for (unsigned i : undefineds) {
     const Elf_Sym &eSym = eSyms[i];
     StringRefZ name = this->stringTable.data() + eSym.st_name;
     this->symbols[i]->resolve(Undefined{this, name, eSym.getBinding(),
                                         eSym.st_other, eSym.getType()});
     this->symbols[i]->referenced = true;
   }
 }
 

lld/MachO/InputFiles.cpp

macho::Symbol *ObjFile::parseNonSectionSymbol(const NList &sym,
   case N_SECT:
     llvm_unreachable(
         "N_SECT symbols should not be passed to parseNonSectionSymbol");
   default:
     llvm_unreachable("invalid symbol type");
   }
 }
 
+template <class NList>
+static bool isUndef(const NList &sym) {
+  return (sym.n_type & N_TYPE) == N_UNDF && sym.n_value == 0;
+}
+
 template <class LP>
 void ObjFile::parseSymbols(ArrayRef<typename LP::section> sectionHeaders,
                            ArrayRef<typename LP::nlist> nList,
                            const char *strtab, bool subsectionsViaSymbols) {
   using NList = typename LP::nlist;
 
   // Groups indices of the symbols by the sections that contain them.
   std::vector<std::vector<uint32_t>> symbolsBySection(subsections.size());
   symbols.resize(nList.size());
+  SmallVector<unsigned, 32> undefineds;
   for (uint32_t i = 0; i < nList.size(); ++i) {
     const NList &sym = nList[i];
 
     // Ignore debug symbols for now.
     // FIXME: may need special handling.
     if (sym.n_type & N_STAB)
       continue;
 
     StringRef name = strtab + sym.n_strx;
     if ((sym.n_type & N_TYPE) == N_SECT) {
       SubsectionMap &subsecMap = subsections[sym.n_sect - 1];
       // parseSections() may have chosen not to parse this section.
       if (subsecMap.empty())
         continue;
       symbolsBySection[sym.n_sect - 1].push_back(i);
+    } else if (isUndef(sym)) {
+      undefineds.push_back(i);
     } else {
       symbols[i] = parseNonSectionSymbol(sym, name);
     }
   }
 
   for (size_t i = 0; i < subsections.size(); ++i) {
     SubsectionMap &subsecMap = subsections[i];
     if (subsecMap.empty())
for (size_t j = 0; j < symbolIndices.size(); ++j) {
       // TODO: ld64 appears to preserve the original alignment as well as each
       // subsection's offset from the last aligned address. We should consider
       // emulating that behavior.
       nextIsec->align = MinAlign(sectionAlign, sym.n_value);
       subsecMap.push_back({sym.n_value - sectionAddr, nextIsec});
       subsecEntry = subsecMap.back();
     }
   }
+
+  // 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) {
+    const NList &sym = nList[i];
+    StringRef name = strtab + sym.n_strx;
+    symbols[i] = parseNonSectionSymbol(sym, name);
+  }
 }
 
 OpaqueFile::OpaqueFile(MemoryBufferRef mb, StringRef segName,
                        StringRef sectName)
     : InputFile(OpaqueKind, mb) {
   const auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
   ArrayRef<uint8_t> data = {buf, mb.getBufferSize()};
   ConcatInputSection *isec =

lld/test/MachO/weak-definition-in-main-file.s

+# REQUIRES: x86
+# RUN: rm -rf %t; split-file %s %t
+
+## Test that a weak symbol in a direct .o file wins over
+## a weak symbol in a .a file.
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/test.s -o %t/test.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/weakfoo.s -o %t/weakfoo.o
+
+# RUN: llvm-ar --format=darwin rcs %t/weakfoo.a %t/weakfoo.o
+
+# PREFER-DIRECT-OBJECT-NOT: O __TEXT,weak __foo
+
+# RUN: %lld -lSystem -o %t/out %t/weakfoo.a %t/test.o
+# RUN: llvm-objdump --syms %t/out | FileCheck %s --check-prefix=PREFER-DIRECT-OBJECT
+
+#--- weakfoo.s
+.globl __baz
+__baz:
+  ret
+
+.section __TEXT,weak
+.weak_definition __foo
+.globl __foo
+__foo:
+  ret
+
+.subsections_via_symbols
+
+#--- test.s
+.globl __foo
+.weak_definition __foo
+__foo:
+  ret
+
+.globl _main
+_main:
+  # This pulls in weakfoo.a due to the __baz undef, but __foo should
+  # still be resolved against the weak symbol in this file.
+  callq __baz
+  callq __foo
+  ret
+
+.subsections_via_symbols