COFF: Symbol resolution for common and comdat symbols defined in bitcode.

[pcc]

Summary

In the case where either a bitcode file and a regular file or two bitcode
files export a common or comdat symbol with the same name, the linker needs
to pick one of them following COFF semantics. This patch implements a design
for resolving such symbols that pushes most of the work onto either LLD's
regular mechanism for resolving common or comdat symbols or the IR linker's
mechanism for doing the same.

We modify SymbolBody::compare to always prefer non-bitcode symbols, so that
during the initial phase of symbol resolution, the symbol table always contains
a regular symbol in any case where we need to choose between a regular and
a bitcode symbol. In SymbolTable::addCombinedLTOObject, we force export
any bitcode symbols that were initially pre-empted by a regular symbol,
and later use SymbolBody::compare to choose between the regular symbol in
the symbol table and the regular symbol from the combined LTO object file.

This design seems to be sound, so long as the resolution mechanism is defined
to be commutative and associative modulo arbitrary choices between symbols
(which seems to be the case for COFF).

[ruiu]

LGTM

COFF/InputFiles.cpp

269 ↗

(On Diff #27349)

Add parentheses after =

COFF/SymbolTable.cpp

251 ↗

(On Diff #27349)

Nice. Looks like the separation of Symbol and SymbolBody works well here.

COFF/Symbols.cpp

72 ↗

(On Diff #27349)

if (auto *R = ...

76 ↗

(On Diff #27349)

if (auto *B = ...

82 ↗

(On Diff #27349)

Remove this blank line.

lld/trunk/COFF/InputFiles.cpp

for (unsigned I = 0, E = M->getSymbolCount(); I != E; ++I) {
     if ((Attrs & LTO_SYMBOL_SCOPE_MASK) == LTO_SYMBOL_SCOPE_INTERNAL)
       continue;
 
     StringRef SymName = M->getSymbolName(I);
     int SymbolDef = Attrs & LTO_SYMBOL_DEFINITION_MASK;
     if (SymbolDef == LTO_SYMBOL_DEFINITION_UNDEFINED) {
       SymbolBodies.push_back(new (Alloc) Undefined(SymName));
     } else {
-      SymbolBodies.push_back(new (Alloc) DefinedBitcode(SymName));
+      bool Replaceable = (SymbolDef == LTO_SYMBOL_DEFINITION_TENTATIVE ||
+                          (Attrs & LTO_SYMBOL_COMDAT));
+      SymbolBodies.push_back(new (Alloc) DefinedBitcode(SymName, Replaceable));
     }
   }
 
   // Extract any linker directives from the bitcode file, which are represented
   // as module flags with the key "Linker Options".
   llvm::SmallVector<llvm::Module::ModuleFlagEntry, 8> Flags;
   M->getModule().getModuleFlagsMetadata(Flags);
   for (auto &&Flag : Flags) {

lld/trunk/COFF/SymbolTable.cpp

for (SymbolBody *Body : Obj->getSymbols()) {
 
     if (isa<DefinedBitcode>(Sym->Body)) {
       // The symbol should now be defined.
       if (!isa<Defined>(Body)) {
         llvm::errs() << "LTO: undefined symbol: " << Name << '\n';
         return make_error_code(LLDError::BrokenFile);
       }
       Sym->Body = Body;
+    } else {
+      int comp = Sym->Body->compare(Body);
+      if (comp < 0)
+        Sym->Body = Body;
+      if (comp == 0) {
+        llvm::errs() << "LTO: unexpected duplicate symbol: " << Name << "\n";
+        return make_error_code(LLDError::BrokenFile);
+      }
     }
 
     // We may see new references to runtime library symbols such as __chkstk
     // here. These symbols must be wholly defined in non-bitcode files.
     if (auto *B = dyn_cast<Lazy>(Sym->Body)) {
       size_t NumBitcodeFiles = BitcodeFiles.size();
       if (auto EC = addMemberFile(B))
         return EC;

 // as a regular COFF object file.
 ErrorOr<ObjectFile *> SymbolTable::createLTOObject(LTOCodeGenerator *CG) {
   // All symbols referenced by non-bitcode objects must be preserved.
   for (std::unique_ptr<ObjectFile> &File : ObjectFiles)
     for (SymbolBody *Body : File->getSymbols())
       if (auto *S = dyn_cast<DefinedBitcode>(Body->getReplacement()))
         CG->addMustPreserveSymbol(S->getName());
 
+  // Likewise for bitcode symbols which we initially resolved to non-bitcode.
+  for (std::unique_ptr<BitcodeFile> &File : BitcodeFiles)
+    for (SymbolBody *Body : File->getSymbols())
+      if (isa<DefinedBitcode>(Body) &&
+          !isa<DefinedBitcode>(Body->getReplacement()))
+        CG->addMustPreserveSymbol(Body->getName());
+
   // Likewise for other symbols that must be preserved.
   for (StringRef Name : Config->GCRoots)
     if (isa<DefinedBitcode>(Symtab[Name]->Body))
       CG->addMustPreserveSymbol(Name);
 
   CG->setModule(BitcodeFiles[0]->releaseModule());
   for (unsigned I = 1, E = BitcodeFiles.size(); I != E; ++I)
     CG->addModule(BitcodeFiles[I]->getModule());

lld/trunk/COFF/Symbols.h

 
 private:
   StringRef Name;
   ImportThunkChunk Data;
 };
 
 class DefinedBitcode : public Defined {
 public:
-  DefinedBitcode(StringRef N) : Defined(DefinedBitcodeKind), Name(N) {}
+  DefinedBitcode(StringRef N, bool R)
+      : Defined(DefinedBitcodeKind), Name(N), Replaceable(R) {}
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == DefinedBitcodeKind;
   }
 
   StringRef getName() override { return Name; }
   uint64_t getRVA() override { llvm_unreachable("bitcode reached writer"); }
   uint64_t getFileOff() override { llvm_unreachable("bitcode reached writer"); }
+  int compare(SymbolBody *Other) override;
+  bool isReplaceable() const { return Replaceable; }
 
 private:
   StringRef Name;
+  bool Replaceable;
 };
 
 } // namespace coff
 } // namespace lld
 
 #endif

lld/trunk/COFF/Symbols.cpp

 
 using namespace llvm::object;
 using llvm::sys::fs::identify_magic;
 using llvm::sys::fs::file_magic;
 
 namespace lld {
 namespace coff {
 
+// As an approximation, regular symbols win over bitcode symbols, but we
+// definitely have a conflict if the regular symbol is not replaceable and
+// neither is the bitcode symbol. We do not replicate the rest of the symbol
+// resolution logic here; symbol resolution will be done accurately after
+// lowering bitcode symbols to regular symbols in addCombinedLTOObject().
+static int compareRegularBitcode(DefinedRegular *R, DefinedBitcode *B) {
+  if (!R->isCommon() && !R->isCOMDAT() && !B->isReplaceable())
+    return 0;
+  return 1;
+}
+
 // Returns 1, 0 or -1 if this symbol should take precedence over the
 // Other in the symbol table, tie or lose, respectively.
 int Defined::compare(SymbolBody *Other) {
   if (!isa<Defined>(Other))
     return 1;
   auto *X = dyn_cast<DefinedRegular>(this);
+  if (!X)
+    return 0;
+
+  if (auto *B = dyn_cast<DefinedBitcode>(Other))
+    return compareRegularBitcode(X, B);
+
   auto *Y = dyn_cast<DefinedRegular>(Other);
-  if (!X || !Y)
+  if (!Y)
     return 0;
 
   // Common symbols are weaker than other types of defined symbols.
   if (X->isCommon() && Y->isCommon())
     return (X->getCommonSize() < Y->getCommonSize()) ? -1 : 1;
   // TODO: we are not sure if regular defined symbol and common
   // symbols are allowed to have the same name.
   if (X->isCommon())
     return -1;
   if (Y->isCommon())
     return 1;
 
   if (X->isCOMDAT() && Y->isCOMDAT())
     return 1;
   return 0;
 }
 
+int DefinedBitcode::compare(SymbolBody *Other) {
+  if (!isa<Defined>(Other))
+    return 1;
+
+  if (auto *R = dyn_cast<DefinedRegular>(Other))
+    return -compareRegularBitcode(R, this);
+
+  if (auto *B = dyn_cast<DefinedBitcode>(Other)) {
+    if (!isReplaceable() && !B->isReplaceable())
+      return 0;
+    // Non-replaceable symbols win.
+    return isReplaceable() ? -1 : 1;
+  }
+  return 0;
+}
+
 int Lazy::compare(SymbolBody *Other) {
   if (isa<Defined>(Other))
     return -1;
 
   // Undefined symbols with weak aliases will turn into defined
   // symbols if they remain undefined, so we don't need to resolve
   // such symbols.
   if (auto *U = dyn_cast<Undefined>(Other))

lld/trunk/test/COFF/Inputs/lto-comdat1.ll

+target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-windows-msvc"
+
+$comdat = comdat any
+
+define void @f1() {
+  call void @comdat()
+  ret void
+}
+
+define linkonce_odr void @comdat() comdat {
+  ret void
+}

lld/trunk/test/COFF/Inputs/lto-comdat2.ll

+target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-windows-msvc"
+
+$comdat = comdat any
+
+define void @f2() {
+  call void @comdat()
+  ret void
+}
+
+define linkonce_odr void @comdat() comdat {
+  ret void
+}

lld/trunk/test/COFF/lto-comdat.ll

+; RUN: llvm-as -o %T/comdat-main.lto.obj %s
+; RUN: llvm-as -o %T/comdat1.lto.obj %S/Inputs/lto-comdat1.ll
+; RUN: llvm-as -o %T/comdat2.lto.obj %S/Inputs/lto-comdat2.ll
+; RUN: rm -f %T/comdat.lto.lib
+; RUN: llvm-ar cru %T/comdat.lto.lib %T/comdat1.lto.obj %T/comdat2.lto.obj
+
+; RUN: llc -filetype=obj -o %T/comdat-main.obj %s
+; RUN: llc -filetype=obj -o %T/comdat1.obj %S/Inputs/lto-comdat1.ll
+; RUN: llc -filetype=obj -o %T/comdat2.obj %S/Inputs/lto-comdat2.ll
+; RUN: rm -f %T/comdat.lib
+; RUN: llvm-ar cru %T/comdat.lib %T/comdat1.obj %T/comdat2.obj
+
+; RUN: lld -flavor link2 /out:%T/comdat-main.exe /entry:main /subsystem:console %T/comdat-main.lto.obj %T/comdat1.lto.obj %T/comdat2.lto.obj
+; RUN: llvm-readobj -file-headers %T/comdat-main.exe | FileCheck -check-prefix=HEADERS-11 %s
+; RUN: llvm-objdump -d %T/comdat-main.exe | FileCheck -check-prefix=TEXT-11 %s
+; RUN: lld -flavor link2 /out:%T/comdat-main.exe /entry:main /subsystem:console %T/comdat-main.lto.obj %T/comdat.lto.lib
+; RUN: llvm-readobj -file-headers %T/comdat-main.exe | FileCheck -check-prefix=HEADERS-11 %s
+; RUN: llvm-objdump -d %T/comdat-main.exe | FileCheck -check-prefix=TEXT-11 %s
+
+; RUN: lld -flavor link2 /out:%T/comdat-main.exe /entry:main /subsystem:console %T/comdat-main.obj %T/comdat1.lto.obj %T/comdat2.lto.obj
+; RUN: llvm-readobj -file-headers %T/comdat-main.exe | FileCheck -check-prefix=HEADERS-01 %s
+; RUN: llvm-objdump -d %T/comdat-main.exe | FileCheck -check-prefix=TEXT-01 %s
+; RUN: lld -flavor link2 /out:%T/comdat-main.exe /entry:main /subsystem:console %T/comdat-main.obj %T/comdat.lto.lib
+; RUN: llvm-readobj -file-headers %T/comdat-main.exe | FileCheck -check-prefix=HEADERS-01 %s
+; RUN: llvm-objdump -d %T/comdat-main.exe | FileCheck -check-prefix=TEXT-01 %s
+
+; RUN: lld -flavor link2 /out:%T/comdat-main.exe /entry:main /subsystem:console %T/comdat-main.lto.obj %T/comdat1.obj %T/comdat2.obj
+; RUN: llvm-readobj -file-headers %T/comdat-main.exe | FileCheck -check-prefix=HEADERS-10 %s
+; RUN: llvm-objdump -d %T/comdat-main.exe | FileCheck -check-prefix=TEXT-10 %s
+; RUN: lld -flavor link2 /out:%T/comdat-main.exe /entry:main /subsystem:console %T/comdat-main.lto.obj %T/comdat.lib
+; RUN: llvm-readobj -file-headers %T/comdat-main.exe | FileCheck -check-prefix=HEADERS-10 %s
+; RUN: llvm-objdump -d %T/comdat-main.exe | FileCheck -check-prefix=TEXT-10 %s
+
+; HEADERS-11: AddressOfEntryPoint: 0x1000
+; TEXT-11: Disassembly of section .text:
+; TEXT-11-NEXT: .text:
+; TEXT-11-NEXT: xorl  %eax, %eax
+; TEXT-11-NEXT: retq
+
+; HEADERS-01: AddressOfEntryPoint: 0x2000
+; TEXT-01: Disassembly of section .text:
+; TEXT-01-NEXT: .text:
+; TEXT-01-NEXT: subq  $40, %rsp
+; TEXT-01-NEXT: callq 39
+; TEXT-01-NEXT: callq 50
+; TEXT-01-NEXT: callq 13
+; TEXT-01-NEXT: xorl  %eax, %eax
+; TEXT-01-NEXT: addq  $40, %rsp
+; TEXT-01-NEXT: retq
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: retq
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: int3
+; TEXT-01-NEXT: retq
+; TEXT-01-NEXT: nopw  %cs:(%rax,%rax)
+; TEXT-01-NEXT: retq
+
+; HEADERS-10: AddressOfEntryPoint: 0x2030
+; TEXT-10: Disassembly of section .text:
+; TEXT-10-NEXT: .text:
+; TEXT-10-NEXT: subq  $40, %rsp
+; TEXT-10-NEXT: callq 7
+; TEXT-10-NEXT: nop
+; TEXT-10-NEXT: addq  $40, %rsp
+; TEXT-10-NEXT: retq
+; TEXT-10-NEXT: int3
+; TEXT-10-NEXT: retq
+; TEXT-10-NEXT: int3
+; TEXT-10-NEXT: int3
+; TEXT-10-NEXT: int3
+; TEXT-10-NEXT: int3
+; TEXT-10-NEXT: int3
+; TEXT-10-NEXT: int3
+; TEXT-10-NEXT: int3
+; TEXT-10-NEXT: int3
+; TEXT-10-NEXT: int3
+; TEXT-10-NEXT: int3
+; TEXT-10-NEXT: int3
+; TEXT-10-NEXT: int3
+; TEXT-10-NEXT: int3
+; TEXT-10-NEXT: int3
+; TEXT-10-NEXT: int3
+; TEXT-10-NEXT: subq  $40, %rsp
+; TEXT-10-NEXT: callq -25
+; TEXT-10-NEXT: nop
+; TEXT-10-NEXT: addq  $40, %rsp
+; TEXT-10-NEXT: retq
+; TEXT-10-NEXT: int3
+; TEXT-10-NEXT: subq  $40, %rsp
+; TEXT-10-NEXT: callq -57
+; TEXT-10-NEXT: callq -30
+; TEXT-10-NEXT: xorl  %eax, %eax
+; TEXT-10-NEXT: addq  $40, %rsp
+; TEXT-10-NEXT: retq
+
+target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-windows-msvc"
+
+$comdat = comdat any
+
+define i32 @main() {
+  call void @f1()
+  call void @f2()
+  call void @comdat()
+  ret i32 0
+}
+
+define linkonce_odr void @comdat() comdat {
+  ret void
+}
+
+declare void @f1()
+declare void @f2()