COFF: Numerous fixes for interaction between LTO and weak externals.

[pcc]

Summary

We were previously hitting assertion failures in the writer in cases where
a regular object file defined a weak external symbol that was defined by
a bitcode file. Because /export and /entry name mangling were implemented
using weak externals, the same problem affected mangled symbol names in
bitcode files.

The underlying cause of the problem was that weak external symbols were
being resolved before doing LTO, so the symbol table may have contained stale
references to bitcode symbols. The fix here is to defer weak external symbol
resolution until after LTO.

Also implement support for weak external symbols in bitcode files
by modelling them as replaceable DefinedBitcode symbols.

[ruiu]

LGTM

COFF/SymbolTable.cpp

130–133 ↗

(On Diff #29042)

Ah, this looks better than before.

COFF/Symbols.cpp

239 ↗

(On Diff #29042)

I'd name getWeakAlias.

244 ↗

(On Diff #29042)

You can remove this brace.

[pcc]

COFF/Symbols.cpp

239 ↗

(On Diff #29042)

Done

244 ↗

(On Diff #29042)

Done

lld/trunk/COFF/Driver.cpp

for (;;) {
     if (Symtab.queueEmpty())
       break;
     if (auto EC = Symtab.run()) {
       llvm::errs() << EC.message() << "\n";
       return false;
     }
   }
 
-  // Make sure we have resolved all symbols.
-  if (Symtab.reportRemainingUndefines())
-    return false;
-
   // Do LTO by compiling bitcode input files to a native COFF file
   // then link that file.
   if (auto EC = Symtab.addCombinedLTOObject()) {
     llvm::errs() << EC.message() << "\n";
     return false;
   }
 
+  // Make sure we have resolved all symbols.
+  if (Symtab.reportRemainingUndefines(/*Resolve=*/true))
+    return false;
+
   // Windows specific -- if no /subsystem is given, we need to infer
   // that from entry point name.
   if (Config->Subsystem == IMAGE_SUBSYSTEM_UNKNOWN) {
     Config->Subsystem = inferSubsystem();
     if (Config->Subsystem == IMAGE_SUBSYSTEM_UNKNOWN) {
       llvm::errs() << "subsystem must be defined\n";
       return false;
     }

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 = Saver.save(M->getSymbolName(I));
     int SymbolDef = Attrs & LTO_SYMBOL_DEFINITION_MASK;
     if (SymbolDef == LTO_SYMBOL_DEFINITION_UNDEFINED) {
       SymbolBodies.push_back(new (Alloc) Undefined(SymName));
     } else {
-      bool Replaceable = (SymbolDef == LTO_SYMBOL_DEFINITION_TENTATIVE ||
-                          (Attrs & LTO_SYMBOL_COMDAT));
+      bool Replaceable =
+          (SymbolDef == LTO_SYMBOL_DEFINITION_TENTATIVE || // common
+           (Attrs & LTO_SYMBOL_COMDAT) ||                  // comdat
+           (SymbolDef == LTO_SYMBOL_DEFINITION_WEAK &&     // weak external
+            (Attrs & LTO_SYMBOL_ALIAS)));
       SymbolBodies.push_back(new (Alloc) DefinedBitcode(this, SymName,
                                                         Replaceable));
     }
   }
 
   Directives = M->getLinkerOpts();
   return std::error_code();
 }
 
 } // namespace coff
 } // namespace lld

lld/trunk/COFF/SymbolTable.h

 // to replace the lazy symbol. The logic is implemented in resolve().
 class SymbolTable {
 public:
   void addFile(std::unique_ptr<InputFile> File);
   std::error_code step();
   std::error_code run();
   bool queueEmpty();
 
-  // Print an error message on undefined symbols.
-  bool reportRemainingUndefines();
+  // Print an error message on undefined symbols. If Resolve is true, try to
+  // resolve any undefined symbols and update the symbol table accordingly.
+  bool reportRemainingUndefines(bool Resolve);
 
   // Returns a list of chunks of selected symbols.
   std::vector<Chunk *> getChunks();
 
   // Returns a symbol for a given name. Returns a nullptr if not found.
   Symbol *find(StringRef Name);
 
   // Occasionally we have to resolve an undefined symbol to its

lld/trunk/COFF/SymbolTable.cpp

if (auto EC = Driver->parseDirectives(S))
       return EC;
   return std::error_code();
 }
 
 bool SymbolTable::queueEmpty() {
   return ArchiveQueue.empty() && ObjectQueue.empty();
 }
 
-bool SymbolTable::reportRemainingUndefines() {
+bool SymbolTable::reportRemainingUndefines(bool Resolve) {
   bool Ret = false;
   for (auto &I : Symtab) {
     Symbol *Sym = I.second;
     auto *Undef = dyn_cast<Undefined>(Sym->Body);
     if (!Undef)
       continue;
     StringRef Name = Undef->getName();
-    // A weak alias may have been resolved, so check for that. A weak alias
-    // may be a weak alias to another symbol, so check recursively.
-    for (SymbolBody *A = Undef->WeakAlias; A;
-         A = cast<Undefined>(A)->WeakAlias) {
-      if (auto *D = dyn_cast<Defined>(A->repl())) {
+    // A weak alias may have been resolved, so check for that.
+    if (Defined *D = Undef->getWeakAlias()) {
+      if (Resolve)
         Sym->Body = D;
-        goto next;
-      }
+      continue;
     }
     // If we can resolve a symbol by removing __imp_ prefix, do that.
     // This odd rule is for compatibility with MSVC linker.
     if (Name.startswith("__imp_")) {
       Symbol *Imp = find(Name.substr(strlen("__imp_")));
       if (Imp && isa<Defined>(Imp->Body)) {
+        if (!Resolve)
+          continue;
         auto *D = cast<Defined>(Imp->Body);
         auto *S = new (Alloc) DefinedLocalImport(Name, D);
         LocalImportChunks.push_back(S->getChunk());
         Sym->Body = S;
         continue;
       }
     }
     llvm::errs() << "undefined symbol: " << Name << "\n";
     // Remaining undefined symbols are not fatal if /force is specified.
     // They are replaced with dummy defined symbols.
     if (Config->Force) {
+      if (Resolve)
         Sym->Body = new (Alloc) DefinedAbsolute(Name, 0);
       continue;
     }
     Ret = true;
-    next:;
   }
   return Ret;
 }
 
 void SymbolTable::addLazy(Lazy *New, std::vector<Symbol *> *Accum) {
   Symbol *Sym = insert(New);
   if (Sym->Body == New)
     return;
for (SymbolBody *Body : File->getSymbols())
              << " " << R->getName() << "\n";
   }
 }
 
 std::error_code SymbolTable::addCombinedLTOObject() {
   if (BitcodeFiles.empty())
     return std::error_code();
 
+  // Diagnose any undefined symbols early, but do not resolve weak externals,
+  // as resolution breaks the invariant that each Symbol points to a unique
+  // SymbolBody, which we rely on to replace DefinedBitcode symbols correctly.
+  if (reportRemainingUndefines(/*Resolve=*/false))
+    return make_error_code(LLDError::BrokenFile);
+
   // Create an object file and add it to the symbol table by replacing any
   // DefinedBitcode symbols with the definitions in the object file.
   LTOCodeGenerator CG;
   auto FileOrErr = createLTOObject(&CG);
   if (auto EC = FileOrErr.getError())
     return EC;
   ObjectFile *Obj = FileOrErr.get();
 
   for (SymbolBody *Body : Obj->getSymbols()) {
     if (!Body->isExternal())
       continue;
-    // Find an existing Symbol. We should not see any new undefined symbols at
-    // this point.
+    // We should not see any new undefined symbols at this point, but we'll
+    // diagnose them later in reportRemainingUndefines().
     StringRef Name = Body->getName();
     Symbol *Sym = insert(Body);
-    if (Sym->Body == Body && !isa<Defined>(Body)) {
-      llvm::errs() << "LTO: undefined symbol: " << Name << '\n';
-      return make_error_code(LLDError::BrokenFile);
-    }
 
     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;
       continue;
     }
     if (auto *L = dyn_cast<Lazy>(Sym->Body)) {
       // 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 EC = addMemberFile(L))
         return EC;
std::error_code SymbolTable::addCombinedLTOObject() {
   size_t NumBitcodeFiles = BitcodeFiles.size();
   if (auto EC = run())
     return EC;
   if (BitcodeFiles.size() != NumBitcodeFiles) {
     llvm::errs() << "LTO: late loaded symbol created new bitcode reference\n";
     return make_error_code(LLDError::BrokenFile);
   }
 
-  // New runtime library symbol references may have created undefined references.
-  if (reportRemainingUndefines())
-    return make_error_code(LLDError::BrokenFile);
   return std::error_code();
 }
 
 // Combine and compile bitcode files and then return the result
 // as a regular COFF object file.
 ErrorOr<ObjectFile *> SymbolTable::createLTOObject(LTOCodeGenerator *CG) {
   // All symbols referenced by non-bitcode objects must be preserved.
   for (ObjectFile *File : ObjectFiles)
     for (SymbolBody *Body : File->getSymbols())
       if (auto *S = dyn_cast<DefinedBitcode>(Body->repl()))
         CG->addMustPreserveSymbol(S->getName());
 
   // Likewise for bitcode symbols which we initially resolved to non-bitcode.
   for (BitcodeFile *File : BitcodeFiles)
     for (SymbolBody *Body : File->getSymbols())
       if (isa<DefinedBitcode>(Body) && !isa<DefinedBitcode>(Body->repl()))
         CG->addMustPreserveSymbol(Body->getName());
 
   // Likewise for other symbols that must be preserved.
-  for (Undefined *U : Config->GCRoot)
-    if (isa<DefinedBitcode>(U->repl()))
-      CG->addMustPreserveSymbol(U->getName());
+  for (Undefined *U : Config->GCRoot) {
+    if (auto *S = dyn_cast<DefinedBitcode>(U->repl()))
+      CG->addMustPreserveSymbol(S->getName());
+    else if (auto *S = dyn_cast_or_null<DefinedBitcode>(U->getWeakAlias()))
+      CG->addMustPreserveSymbol(S->getName());
+  }
 
   CG->setModule(BitcodeFiles[0]->releaseModule());
   for (unsigned I = 1, E = BitcodeFiles.size(); I != E; ++I)
     CG->addModule(BitcodeFiles[I]->getModule());
 
   std::string ErrMsg;
   LTOMB = CG->compile(false, false, false, ErrMsg); // take MB ownership
   if (!LTOMB) {

lld/trunk/COFF/Symbols.h

static bool classof(const SymbolBody *S) {
     return S->kind() == UndefinedKind;
   }
 
   // An undefined symbol can have a fallback symbol which gives an
   // undefined symbol a second chance if it would remain undefined.
   // If it remains undefined, it'll be replaced with whatever the
   // Alias pointer points to.
   SymbolBody *WeakAlias = nullptr;
+
+  // If this symbol is external weak, try to resolve it to a defined
+  // symbol by searching the chain of fallback symbols. Returns the symbol if
+  // successful, otherwise returns null.
+  Defined *getWeakAlias();
 };
 
 // Windows-specific classes.
 
 // This class represents a symbol imported from a DLL. This has two
 // names for internal use and external use. The former is used for
 // name resolution, and the latter is used for the import descriptor
 // table in an output. The former has "__imp_" prefix.

lld/trunk/COFF/Symbols.cpp

if (Magic != file_magic::coff_object) {
     return make_error_code(LLDError::InvalidFile);
   }
 
   std::unique_ptr<InputFile> Obj(new ObjectFile(MBRef));
   Obj->setParentName(File->getName());
   return std::move(Obj);
 }
 
+Defined *Undefined::getWeakAlias() {
+  // A weak alias may be a weak alias to another symbol, so check recursively.
+  for (SymbolBody *A = WeakAlias; A; A = cast<Undefined>(A)->WeakAlias)
+    if (auto *D = dyn_cast<Defined>(A->repl()))
+      return D;
+  return nullptr;
+}
+
 } // namespace coff
 } // namespace lld

lld/trunk/test/COFF/Inputs/entry-mangled.ll

+target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-windows-msvc18.0.0"
+
+define void @"\01?main@@YAHXZ"() {
+  ret void
+}

lld/trunk/test/COFF/Inputs/weak-external.ll

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

lld/trunk/test/COFF/Inputs/weak-external2.ll

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

lld/trunk/test/COFF/Inputs/weak-external3.ll

+target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-windows-msvc"
+
+@f = weak alias void()* @g
+
+define void @g() {
+  ret void
+}

lld/trunk/test/COFF/entry-mangled.test

 # RUN: yaml2obj < %s > %t.obj
 # RUN: lld -flavor link2 /out:%t.exe /entry:main %t.obj
+# RUN: llvm-as -o %t.lto.obj %S/Inputs/entry-mangled.ll
+# RUN: lld -flavor link2 /out:%t.exe /entry:main %t.lto.obj
 
 ---
 header:
   Machine:         IMAGE_FILE_MACHINE_AMD64
   Characteristics: []
 sections:
   - Name:            .text
     Characteristics: [ IMAGE_SCN_CNT_CODE, IMAGE_SCN_MEM_EXECUTE, IMAGE_SCN_MEM_READ ]

lld/trunk/test/COFF/weak-external.test

 # RUN: yaml2obj %s > %t.obj
-# RUN: lld -flavor link2 /out:%t.exe /entry:g /subsystem:console %t.obj
+# RUN: llvm-as -o %t.lto.obj %S/Inputs/weak-external.ll
+# RUN: lld -flavor link2 /out:%t1.exe /entry:g /subsystem:console %t.obj
+# RUN: lld -flavor link2 /out:%t2.exe /entry:g /subsystem:console /lldmap:%t2.map %t.obj %t.lto.obj
+# RUN: FileCheck %s < %t2.map
+
+# CHECK: lto-llvm{{.*}}:
+# CHECK-NOT: :
+# CHECK: {{ g$}}
 
 ---
 header:          
   Machine:         IMAGE_FILE_MACHINE_AMD64
   Characteristics: [  ]
 sections:        
   - Name:            '.text'
     Characteristics: [ IMAGE_SCN_CNT_CODE, IMAGE_SCN_MEM_EXECUTE, IMAGE_SCN_MEM_READ ]

lld/trunk/test/COFF/weak-external2.test

+# RUN: yaml2obj %s > %t.obj
+# RUN: llvm-as -o %t.lto.obj %S/Inputs/weak-external2.ll
+# RUN: lld -flavor link2 /out:%t.exe /entry:g /subsystem:console %t.obj %t.lto.obj
+
+---
+header:          
+  Machine:         IMAGE_FILE_MACHINE_AMD64
+  Characteristics: [  ]
+sections:        
+  - Name:            '.text'
+    Characteristics: [ IMAGE_SCN_CNT_CODE, IMAGE_SCN_MEM_EXECUTE, IMAGE_SCN_MEM_READ ]
+    Alignment:       16
+    SectionData:     00
+symbols:         
+  - Name:            'f'
+    Value:           0
+    SectionNumber:   0
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_FUNCTION
+    StorageClass:    IMAGE_SYM_CLASS_EXTERNAL
+  - Name:            'g'
+    Value:           0
+    SectionNumber:   0
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_FUNCTION
+    StorageClass:    IMAGE_SYM_CLASS_WEAK_EXTERNAL
+    WeakExternal:    
+      TagIndex:        0
+      Characteristics: IMAGE_WEAK_EXTERN_SEARCH_LIBRARY
+...

lld/trunk/test/COFF/weak-external3.test

+# RUN: yaml2obj %s > %t.obj
+# RUN: llvm-as -o %t.lto.obj %S/Inputs/weak-external3.ll
+# RUN: lld -flavor link2 /out:%t1.exe /entry:f /subsystem:console /lldmap:%t1.map %t.lto.obj
+# RUN: FileCheck --check-prefix=CHECK1 %s < %t1.map
+# RUN: lld -flavor link2 /out:%t2.exe /entry:f /subsystem:console /lldmap:%t2.map %t.obj %t.lto.obj
+# RUN: FileCheck --check-prefix=CHECK2 %s < %t2.map
+
+# CHECK1: lto-llvm{{.*}}:
+# CHECK1-NOT: :
+# CHECK1: {{ g$}}
+
+# CHECK2: weak-external3{{.*}}:
+# CHECK2-NOT: :
+# CHECK2: {{ f$}}
+
+---
+header:          
+  Machine:         IMAGE_FILE_MACHINE_AMD64
+  Characteristics: [  ]
+sections:        
+  - Name:            '.text'
+    Characteristics: [ IMAGE_SCN_CNT_CODE, IMAGE_SCN_MEM_EXECUTE, IMAGE_SCN_MEM_READ ]
+    Alignment:       16
+    SectionData:     00
+symbols:         
+  - Name:            'f'
+    Value:           0
+    SectionNumber:   1
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_FUNCTION
+    StorageClass:    IMAGE_SYM_CLASS_EXTERNAL
+...