[lld-macho] Add support for common bitcode symbols

[int3]

Summary

For some reason, ld64 gives common bitcode symbols a lower
priority than common non-bitcode symbols. As such, I've created a
BitcodeCommonSymbol in order to handle this.

Note that we still deviate from ld64's behavior in some cases,
particularly when bitcode and non-bitcode symbols of the same name are
mixed. I doubt such a situation occurs often in practice, so it should
be fine. I would like to avoid overly complicating our implementation
unless necessary. I've added comments in the test to highlight these
cases.

[int3]

Whoops, missed a test failure. But that aside, I'm a bit ambivalent about trying to follow ld64's weird symbol precedence rules here... it makes the implementation quite a bit uglier, for edge cases that may never be exercised.

lld/MachO/ConcatOutputSection.cpp

for (Reloc &r : reverse(relocs)) {
         // unfinalized inputs[finalIdx].
         fatal(Twine(__FUNCTION__) + ": FIXME: thunk range overrun");
       }
       thunkInfo.isec =
           make<ConcatInputSection>(isec->getSegName(), isec->getName());
       thunkInfo.isec->parent = this;
       StringRef thunkName = saver.save(funcSym->getName() + ".thunk." +
                                        std::to_string(thunkInfo.sequence++));
-      r.referent = thunkInfo.sym = symtab->addDefined(
+      // calls to addDefined() with isWeakDef=false always return a Defined
+      r.referent = thunkInfo.sym = cast<Defined>(symtab->addDefined(
           thunkName, /*file=*/nullptr, thunkInfo.isec, /*value=*/0,
           /*size=*/thunkSize, /*isWeakDef=*/false, /*isPrivateExtern=*/true,
           /*isThumb=*/false, /*isReferencedDynamically=*/false,
-          /*noDeadStrip=*/false);
+          /*noDeadStrip=*/false));
       target->populateThunk(thunkInfo.isec, funcSym);
       finalizeOne(thunkInfo.isec);
       thunks.push_back(thunkInfo.isec);
       ++thunkCount;
     }
   }
   size = isecAddr - addr;
   fileSize = isecFileOff - fileOff;

lld/MachO/InputFiles.cpp

 static macho::Symbol *createBitcodeSymbol(const lto::InputFile::Symbol &objSym,
                                           BitcodeFile &file) {
   StringRef name = saver.save(objSym.getName());
 
   // TODO: support weak references
   if (objSym.isUndefined())
     return symtab->addUndefined(name, &file, /*isWeakRef=*/false);
 
-  assert(!objSym.isCommon() && "TODO: support common symbols in LTO");
-
   // TODO: Write a test demonstrating why computing isPrivateExtern before
   // LTO compilation is important.
   bool isPrivateExtern = false;
   switch (objSym.getVisibility()) {
   case GlobalValue::HiddenVisibility:
     isPrivateExtern = true;
     break;
   case GlobalValue::ProtectedVisibility:
     error(name + " has protected visibility, which is not supported by Mach-O");
     break;
   case GlobalValue::DefaultVisibility:
     break;
   }
 
+  if (objSym.isCommon())
+    return symtab->addBitcodeCommon(name, &file, isPrivateExtern);
+
   return symtab->addDefined(name, &file, /*isec=*/nullptr, /*value=*/0,
                             /*size=*/0, objSym.isWeak(), isPrivateExtern,
                             /*isThumb=*/false,
                             /*isReferencedDynamically=*/false,
                             /*noDeadStrip=*/false);
 }
 
 BitcodeFile::BitcodeFile(WritableMemoryBufferRef mbref)

lld/MachO/SymbolTable.h

 /*
  * Note that the SymbolTable handles name collisions by calling
  * replaceSymbol(), which does an in-place update of the Symbol via `placement
  * new`. Therefore, there is no need to update any relocations that hold
  * pointers the "old" Symbol -- they will automatically point to the new one.
  */
 class SymbolTable {
 public:
-  Defined *addDefined(StringRef name, InputFile *, InputSection *,
-                      uint64_t value, uint64_t size, bool isWeakDef,
-                      bool isPrivateExtern, bool isThumb,
-                      bool isReferencedDynamically, bool noDeadStrip);
+  Symbol *addDefined(StringRef name, InputFile *, InputSection *,
 
   Symbol *addUndefined(StringRef name, InputFile *, bool isWeakRef);
 
   Symbol *addCommon(StringRef name, InputFile *, uint64_t size, uint32_t align,
                     bool isPrivateExtern);
 
+  Symbol *addBitcodeCommon(StringRef name, InputFile *, bool isPrivateExtern);
+
   Symbol *addDylib(StringRef name, DylibFile *file, bool isWeakDef, bool isTlv);
   Symbol *addDynamicLookup(StringRef name);
 
   Symbol *addLazy(StringRef name, ArchiveFile *file,
                   const llvm::object::Archive::Symbol &sym);
 
   Defined *addSynthetic(StringRef name, InputSection *, uint64_t value,
                         bool isPrivateExtern, bool includeInSymtab,

lld/MachO/SymbolTable.cpp

if (!p.second) {
     sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
     symVector.push_back(sym);
   }
 
   sym->isUsedInRegularObj |= !file || isa<ObjFile>(file);
   return {sym, p.second};
 }
 
-Defined *SymbolTable::addDefined(StringRef name, InputFile *file,
-                                 InputSection *isec, uint64_t value,
-                                 uint64_t size, bool isWeakDef,
-                                 bool isPrivateExtern, bool isThumb,
-                                 bool isReferencedDynamically,
-                                 bool noDeadStrip) {
+Symbol *SymbolTable::addDefined(StringRef name, InputFile *file,
   Symbol *s;
   bool wasInserted;
   bool overridesWeakDef = false;
   std::tie(s, wasInserted) = insert(name, file);
 
   assert(!isWeakDef || (isa<BitcodeFile>(file) && !isec) ||
          (isa<ObjFile>(file) && file == isec->getFile()));
 
if (auto *defined = dyn_cast<Defined>(s)) {
       }
       if (!defined->isWeakDef())
         error("duplicate symbol: " + name + "\n>>> defined in " +
               toString(defined->getFile()) + "\n>>> defined in " +
               toString(file));
     } else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {
       overridesWeakDef = !isWeakDef && dysym->isWeakDef();
       dysym->unreference();
+    } else if (isa<BitcodeCommonSymbol>(s) && isWeakDef) {
+      return s;
     }
     // Defined symbols take priority over other types of symbols, so in case
     // of a name conflict, we fall through to the replaceSymbol() call below.
   }
 
   Defined *defined = replaceSymbol<Defined>(
       s, name, file, isec, value, size, isWeakDef, /*isExternal=*/true,
       isPrivateExtern, isThumb, isReferencedDynamically, noDeadStrip);
if (!wasInserted) {
     // Common symbols take priority over all non-Defined symbols, so in case of
     // a name conflict, we fall through to the replaceSymbol() call below.
   }
 
   replaceSymbol<CommonSymbol>(s, name, file, size, align, isPrivateExtern);
   return s;
 }
 
+Symbol *SymbolTable::addBitcodeCommon(StringRef name, InputFile *file,
+                                      bool isPrivateExtern) {
+  Symbol *s;
+  bool wasInserted;
+  std::tie(s, wasInserted) = insert(name, file);
+
+  if (!wasInserted) {
+    if (auto *lazy = dyn_cast<LazySymbol>(s))
+      lazy->fetchArchiveMember();
+    return s;
+  }
+
+  replaceSymbol<BitcodeCommonSymbol>(s, name, file, isPrivateExtern);
+  return s;
+}
+
 Symbol *SymbolTable::addDylib(StringRef name, DylibFile *file, bool isWeakDef,
                               bool isTlv) {
   Symbol *s;
   bool wasInserted;
   std::tie(s, wasInserted) = insert(name, file);
 
   RefState refState = RefState::Unreferenced;
   if (!wasInserted) {
     if (auto *defined = dyn_cast<Defined>(s)) {
       if (isWeakDef && !defined->isWeakDef())
         defined->overridesWeakDef = true;
     } else if (auto *undefined = dyn_cast<Undefined>(s)) {
       refState = undefined->refState;
     } else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {
       refState = dysym->getRefState();
     }
   }
 
   bool isDynamicLookup = file == nullptr;
-  if (wasInserted || isa<Undefined>(s) ||
+  if (wasInserted || isa<Undefined>(s) || isa<BitcodeCommonSymbol>(s) ||
       (isa<DylibSymbol>(s) &&
        ((!isWeakDef && s->isWeakDef()) ||
         (!isDynamicLookup && cast<DylibSymbol>(s)->isDynamicLookup())))) {
     if (auto *dynsym = dyn_cast<DylibSymbol>(s))
       dynsym->unreference();
     replaceSymbol<DylibSymbol>(s, file, name, isWeakDef, refState, isTlv);
   }
 
   return s;
 }
 
 Symbol *SymbolTable::addDynamicLookup(StringRef name) {
   return addDylib(name, /*file=*/nullptr, /*isWeakDef=*/false, /*isTlv=*/false);
 }
 
 Symbol *SymbolTable::addLazy(StringRef name, ArchiveFile *file,
                              const object::Archive::Symbol &sym) {
   Symbol *s;
   bool wasInserted;
   std::tie(s, wasInserted) = insert(name, file);
 
   if (wasInserted)
     replaceSymbol<LazySymbol>(s, file, sym);
-  else if (isa<Undefined>(s) || (isa<DylibSymbol>(s) && s->isWeakDef()))
+  else if (isa<Undefined>(s) || isa<BitcodeCommonSymbol>(s) ||
+           (isa<DylibSymbol>(s) && s->isWeakDef()))
     file->fetch(sym);
   return s;
 }
 
 Defined *SymbolTable::addSynthetic(StringRef name, InputSection *isec,
                                    uint64_t value, bool isPrivateExtern,
                                    bool includeInSymtab,
                                    bool referencedDynamically) {
-  Defined *s = addDefined(name, nullptr, isec, value, /*size=*/0,
-                          /*isWeakDef=*/false, isPrivateExtern,
-                          /*isThumb=*/false, referencedDynamically,
-                          /*noDeadStrip=*/false);
-  s->includeInSymtab = includeInSymtab;
-  return s;
+  Symbol *s = addDefined(name, nullptr, isec, value, /*size=*/0,
+  // calls to addDefined() with isWeakDef=false always return a Defined
+  Defined *d = cast<Defined>(s);
+  d->includeInSymtab = includeInSymtab;
+  return d;
 }
 
 void lld::macho::treatUndefinedSymbol(const Undefined &sym, StringRef source) {
   auto message = [source, &sym]() {
     std::string message = "undefined symbol";
     if (config->archMultiple)
       message += (" for arch " + getArchitectureName(config->arch())).str();
     message += ": " + toString(sym);

lld/MachO/Symbols.h

 };
 
 class Symbol {
 public:
   enum Kind {
     DefinedKind,
     UndefinedKind,
     CommonKind,
+    BitcodeCommonKind,
     DylibKind,
     LazyKind,
   };
 
   virtual ~Symbol() {}
 
   Kind kind() const { return symbolKind; }
 
public:
 
   static bool classof(const Symbol *s) { return s->kind() == CommonKind; }
 
   const uint64_t size;
   const uint32_t align;
   const bool privateExtern;
 };
 
+// For some reason, ld64 applies different precedence rules to common bitcode
+// symbols. Hence we create a separate type for them.
+class BitcodeCommonSymbol : public Symbol {
+public:
+  BitcodeCommonSymbol(StringRefZ name, InputFile *file, bool isPrivateExtern)
+      : Symbol(BitcodeCommonKind, name, file), privateExtern(isPrivateExtern) {}
+
+  static bool classof(const Symbol *s) {
+    return s->kind() == BitcodeCommonKind;
+  }
+
+  const bool privateExtern;
+};
+
 class DylibSymbol : public Symbol {
 public:
   DylibSymbol(DylibFile *file, StringRefZ name, bool isWeakDef,
               RefState refState, bool isTlv)
       : Symbol(DylibKind, name, file), refState(refState), weakDef(isWeakDef),
         tlv(isTlv) {
     if (file && refState > RefState::Unreferenced)
       file->numReferencedSymbols++;

lld/test/MachO/lto-common-symbol-coalescing.ll

+; REQUIRES: x86
+; RUN: rm -rf %t; split-file %s %t
+
+; RUN: opt -module-summary %t/test.ll -o %t/test.o
+; RUN: opt -module-summary %t/same-size.ll -o %t/same-size.o
+; RUN: opt -module-summary %t/smaller-size.ll -o %t/smaller-size.o
+; RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/same-size.s -o %t/same-size-asm.o
+; RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/smaller-size.s -o %t/smaller-size-asm.o
+
+;; Common bitcode symbols all have equal precedence, regardless of size or
+;; alignment.
+; RUN: %lld -dylib %t/test.o %t/smaller-size.o -order_file %t/order -o %t/test
+; RUN: llvm-objdump --section-headers --syms %t/test | FileCheck %s -D#SIZE=2 -D#ALIGN=8
+; RUN: %lld -dylib %t/smaller-size.o %t/test.o -order_file %t/order -o %t/test
+; RUN: llvm-objdump --section-headers --syms %t/test | FileCheck %s -D#SIZE=1 -D#ALIGN=16
+
+; RUN: %lld -dylib %t/test.o %t/same-size.o -order_file %t/order -o %t/test
+; RUN: llvm-objdump --section-headers --syms %t/test | FileCheck %s -D#SIZE=2 -D#ALIGN=8
+; RUN: %lld -dylib %t/same-size.o %t/test.o -order_file %t/order -o %t/test
+; RUN: llvm-objdump --section-headers --syms %t/test | FileCheck %s -D#SIZE=2 -D#ALIGN=16
+
+;; Non-bitcode common symbols take precedence.
+; RUN: %lld -dylib %t/test.o %t/smaller-size-asm.o -order_file %t/order -o %t/test
+; RUN: llvm-objdump --section-headers --syms %t/test | FileCheck %s -D#SIZE=1 -D#ALIGN=16
+; RUN: %lld -dylib %t/smaller-size-asm.o %t/test.o -order_file %t/order -o %t/test
+; RUN: llvm-objdump --section-headers --syms %t/test | FileCheck %s -D#SIZE=1 -D#ALIGN=16
+
+; RUN: %lld -dylib %t/test.o %t/same-size-asm.o -order_file %t/order -o %t/test
+; RUN: llvm-objdump --section-headers --syms %t/test | FileCheck %s -D#SIZE=2 -D#ALIGN=16
+; RUN: %lld -dylib %t/same-size-asm.o %t/test.o -order_file %t/order -o %t/test
+; RUN: llvm-objdump --section-headers --syms %t/test | FileCheck %s -D#SIZE=2 -D#ALIGN=16
+
+; CHECK-LABEL: Sections:
+; CHECK:       __common      {{[0-9a-f]+}} [[#%x, COMMON_START:]]  BSS
+;
+; CHECK-LABEL: SYMBOL TABLE:
+; CHECK-DAG:   [[#%.16x, COMMON_START]]         g     O __DATA,__common _check_size
+; CHECK-DAG:   [[#%.16x, COMMON_START + SIZE]]  g     O __DATA,__common _end_marker
+; CHECK-DAG:   [[#%.16x, COMMON_START + ALIGN]] g     O __DATA,__common _check_alignment
+
+;--- order
+;; Order is important as we determine the size of a given symbol via the
+;; address of the next symbol.
+_check_size
+_end_marker
+_check_alignment
+
+;--- smaller-size.ll
+target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.15.0"
+
+@check_size = common global i8 0, align 1
+@check_alignment = common global i8 0, align 16
+
+;--- same-size.ll
+target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.15.0"
+
+@check_size = common global i16 0, align 1
+@check_alignment = common global i16 0, align 16
+
+;--- smaller-size.s
+.comm _check_size, 1, 1
+.comm _check_alignment, 1, 4
+
+;--- same-size.s
+.comm _check_size, 2, 1
+.comm _check_alignment, 2, 4
+
+;--- test.ll
+target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.15.0"
+@check_size = common global i16 0, align 1
+@end_marker = common global i8 0
+@check_alignment = common global i16 0, align 8

lld/test/MachO/lto-common-symbol-resolution.ll

+; REQUIRES: x86
+
+; RUN: rm -rf %t; split-file %s %t
+
+; RUN: opt -module-summary %t/common.ll -o %t/common.o
+; RUN: opt -module-summary %t/defined.ll -o %t/defined.o
+; RUN: opt -module-summary %t/weak-defined.ll -o %t/weak-defined.o
+; RUN: opt -module-summary %t/libfoo.ll -o %t/libfoo.o
+; RUN: opt -module-summary %t/refs-foo.ll -o %t/refs-foo.o
+; RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/weak-defined.s -o %t/weak-defined-asm.o
+
+; RUN: %lld -dylib -dylib %t/libfoo.o -o %t/libfoo.dylib
+
+; RUN: llvm-ar rcs %t/defined.a %t/defined.o
+; RUN: llvm-ar rcs %t/defined-and-common.a %t/defined.o %t/common.o
+; RUN: llvm-ar rcs %t/common-and-defined.a %t/common.o %t/defined.o
+; RUN: llvm-ar rcs %t/weak-defined-and-common.a %t/weak-defined.o %t/common.o
+; RUN: llvm-ar rcs %t/common-and-weak-defined.a %t/common.o %t/weak-defined.o
+
+;; Defined symbols take precedence over common bitcode symbols.
+; RUN: %lld -dylib %t/defined.o %t/common.o -o %t/test
+; RUN: llvm-objdump --syms %t/test | FileCheck %s --check-prefix=DEFINED
+; RUN: %lld -dylib %t/common.o %t/defined.o -o %t/test
+; RUN: llvm-objdump --syms %t/test | FileCheck %s --check-prefix=DEFINED
+
+;; NOTE: we are deviating from ld64's behavior here.
+;; ld64: Defined symbols have the same precedence as common bitcode symbols
+;; within an archive.
+;; lld: Defined symbols take precedence over common bitcode symbols within an
+;; archive.
+; RUN: %lld -dylib %t/defined-and-common.a %t/refs-foo.o -o %t/refs-foo
+; RUN: llvm-objdump --syms %t/refs-foo | FileCheck %s --check-prefix=DEFINED
+; RUN: %lld -dylib %t/common-and-defined.a %t/refs-foo.o -o %t/refs-foo
+; RUN: llvm-objdump --syms %t/refs-foo | FileCheck %s --check-prefix=DEFINED
+; COM (ld64): llvm-objdump --syms %t/refs-foo | FileCheck %s --check-prefix=COMMON
+
+;; Weak bitcode symbols have the same precedence as common bitcode symbols.
+; RUN: %lld -dylib %t/weak-defined.o %t/common.o -o %t/test
+; RUN: llvm-objdump --syms %t/test | FileCheck %s --check-prefix=WEAK-DEFINED
+; RUN: %lld -dylib %t/common.o %t/weak-defined.o -o %t/test
+; RUN: llvm-objdump --syms %t/test | FileCheck %s --check-prefix=COMMON
+
+;; NOTE: we are deviating from ld64's behavior here.
+;; ld64: Weak non-bitcode symbols take precedence over common bitcode symbols.
+;; lld: Weak non-bitcode symbols have the same precedence as common bitcode
+;; symbols.
+; RUN: %lld -dylib %t/weak-defined-asm.o %t/common.o -o %t/test
+; RUN: llvm-objdump --syms %t/test | FileCheck %s --check-prefix=WEAK-DEFINED
+; RUN: %lld -dylib %t/common.o %t/weak-defined-asm.o -o %t/test
+; RUN: llvm-objdump --syms %t/test | FileCheck %s --check-prefix=COMMON
+; COM (ld64): llvm-objdump --syms %t/test | FileCheck %s --check-prefix=WEAK-DEFINED
+
+;; Archive symbols take precedence over common bitcode symbols.
+; RUN: %lld -dylib %t/defined.a %t/common.o -o %t/test
+; RUN: llvm-objdump --syms %t/test | FileCheck %s --check-prefix=DEFINED
+; RUN: %lld -dylib %t/common.o %t/defined.a -o %t/test
+; RUN: llvm-objdump --syms %t/test | FileCheck %s --check-prefix=DEFINED
+
+;; Dylib symbols take precedence over common bitcode symbols.
+; RUN: %lld -dylib %t/libfoo.dylib %t/common.o %t/refs-foo.o -o %t/test
+; RUN: llvm-objdump --syms %t/test | FileCheck %s --check-prefix=DYLIB
+; RUN: %lld -dylib %t/common.o %t/libfoo.dylib %t/refs-foo.o -o %t/test
+; RUN: llvm-objdump --syms %t/test | FileCheck %s --check-prefix=DYLIB
+
+; COMMON:       g     O __DATA,__common _foo
+; DEFINED:      g     O __DATA,__data _foo
+; WEAK-DEFINED: w     O __DATA,__data _foo
+; DYLIB:        *UND* _foo
+
+;--- common.ll
+target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.15.0"
+
+@foo = common global i8 0
+
+;--- defined.ll
+target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.15.0"
+
+@foo = global i8 12
+
+;--- weak-defined.ll
+target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.15.0"
+
+@foo = weak global i8 12
+
+;--- weak-defined.s
+.globl _foo
+.weak_definition _foo
+.data
+_foo:
+
+;--- libfoo.ll
+target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.15.0"
+
+@foo = common global i8 0
+
+;--- refs-foo.ll
+target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.15.0"
+
+@foo = external global i8
+
+define void @f() {
+  %1 = load i8, i8* @foo
+  ret void
+}