[lld-link] diagnose undefined symbols before LTO when possible

[inglorion]

Summary

This allows reporting undefined symbols before LTO codegen is
run. Since LTO codegen can take a long time, this improves user
experience by avoiding that time spend if the link is going to
fail with undefined symbols anyway.

Fixes PR32400.

[inglorion]

rebase

[inglorion]

Ready for review now.

[inglorion]

removed redundant check

[inglorion]

don't process bitcode files in resolveRemainindUndefines

[inglorion]

The basic idea here is:

reportRemainingUndefines did two things: it attempts to resolve undefined symbols, and it reports any that remain undefined.

This splits reportRemainingUndefines into two functions, one which reports symbols which we know are unresolvable (reportUnresolvable, which we run before LTO) and one which actually does the resolution (resolveRemainingUndefines, which we run after LTO).

Then there is a little bit of added code report undefined symbols in bitcode files.

[ruiu]

lld/COFF/SymbolTable.cpp

86

Source -> source

90

nit: maybe it is a bit more straightforward if you define res as std::string res and return a vector with return {res};?

90

Or, maybe it is better to avoid ostream and just append strings to res using +=.

131

This line is unreachable as you explicitly asserted it by assert, no?

I think you can change the second condition to return getSymbolLocations(cast<BitcodeFile>(file));

205–255

Can you expand the comment to explain what this function does a little bit more in detail?

[inglorion]

addressed @ruiu's comments

[inglorion]

lld/COFF/SymbolTable.cpp

131

This line is unreachable as you explicitly asserted it by assert, no?

When asserts are enabled, yes. But they aren't always.

I'm not super concerned that we would ever change this to pass in other types of file and forget to update it, but I kind of like the behavior as it is: if we do that with asserts enabled, we will get an informative message, and if we do it with asserts disabled, just don't return any symbol locations.

That said, if you want me to change it, I will.

205–255

Is this better?

[inglorion]

added comment explaining BitcodeFiles::instances.empty() check

[inglorion]

Linking ThinLTO chrome.dll with an undefined symbol:

Without this change: ~13 minutes.
With this change: ~4 seconds.

[ruiu]

Generally looking ogod.

lld/COFF/SymbolTable.cpp

131

I feel like returning a "reasonable" value for an impossible condition does more harm than mitigating a pain. When a program reaches here under an unintended condition, something bad has already occurred, and we should report it of swallowing it.

How about changing the last line to llvm_unreachable?

[inglorion]

replaced assert with llvm_unreachable

[ruiu]

LGTM

lld/COFF/SymbolTable.cpp

130

I don't think you need this return after an unreachable statement. I believe all C++ compilers that are smart enough to recognize that this function always return a value or abort. (If it would fail on a buildbot, we can add this line later.)

[inglorion]

lld/COFF/SymbolTable.cpp

130

I grepped the LLVM codebase, and it seems that in other places, we follow llvm_unreachable() with return. I think it's safer and more consistent to leave this return in here, so unless you object I'd like to ship this as it stands.

[thakis]

lld/trunk/COFF/SymbolTable.cpp

329 ↗

(On Diff #211970)

A bot notices:

lld/COFF/SymbolTable.cpp:329:18: warning: unused variable ‘d’ [-Wunused-variable]
     if (Defined *d = undef->getWeakAlias())
                  ^

I'd just remove d but I'm not sure if you intended to do something with it.

lld/COFF/Driver.cpp

for (auto Pair : Config->AlternateNames) {
           U->WeakAlias = Symtab->addUndefined(To);
     }
 
     // Windows specific -- if __load_config_used can be resolved, resolve it.
     if (Symtab->findUnderscore("_load_config_used"))
       addUndefined(mangle("_load_config_used"));
   } while (run());
 
-  if (errorCount())
-    return;
-
-  // Do LTO by compiling bitcode input files to a set of native COFF files then
-  // link those files.
-  Symtab->addCombinedLTOObjects();
-  run();
-
   if (Config->MinGW) {
     // Load any further object files that might be needed for doing automatic
     // imports.
     //
     // For cases with no automatically imported symbols, this iterates once
     // over the symbol table and doesn't do anything.
     //
     // For the normal case with a few automatically imported symbols, this
     // should only need to be run once, since each new object file imported
     // is an import library and wouldn't add any new undefined references,
     // but there's nothing stopping the __imp_ symbols from coming from a
     // normal object file as well (although that won't be used for the
     // actual autoimport later on). If this pass adds new undefined references,
     // we won't iterate further to resolve them.
     Symtab->loadMinGWAutomaticImports();
     run();
   }
 
-  // Make sure we have resolved all symbols.
-  Symtab->reportRemainingUndefines();
+  // At this point, we should not have any symbols that cannot be resolved.
+  if (!Config->ForceUnresolved)
+    Symtab->reportUnresolvable();
+
+  if (errorCount())
+    return;
+
+  // Do LTO by compiling bitcode input files to a set of native COFF files then
+  // link those files.
+  Symtab->addCombinedLTOObjects();
+  run();
+
+  // Resolve remaining undefined symbols and warn about imported locals.
+  Symtab->resolveRemainingUndefines();
   if (errorCount())
     return;
 
   // Handle /safeseh.
   if (Args.hasFlag(OPT_safeseh, OPT_safeseh_no, false)) {
     for (ObjFile *File : ObjFile::Instances)
       if (!File->hasSafeSEH())
         error("/safeseh: " + File->getName() + " is not compatible with SEH");

lld/COFF/SymbolTable.h

 // undefined, it'll read an archive member to read a real definition
 // to replace the lazy symbol. The logic is implemented in the
 // add*() functions, which are called by input files as they are parsed.
 // There is one add* function per symbol type.
 class SymbolTable {
 public:
   void addFile(InputFile *File);
 
+  // Emit errors for symbols that cannot be resolved.
+  void reportUnresolvable();
+
   // Try to resolve any undefined symbols and update the symbol table
   // accordingly, then print an error message for any remaining undefined
-  // symbols.
-  void reportRemainingUndefines();
+  // symbols and warn about imported local symbols.
+  void resolveRemainingUndefines();
 
   void loadMinGWAutomaticImports();
   bool handleMinGWAutomaticImport(Symbol *Sym, StringRef Name);
 
   // 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.

lld/COFF/SymbolTable.cpp

 // Returns the symbol in SC whose value is <= Addr that is closest to Addr.
 // This is generally the global variable or function whose definition contains
 // Addr.
 static Symbol *getSymbol(SectionChunk *SC, uint32_t Addr) {
   DefinedRegular *Candidate = nullptr;
 
   for (Symbol *S : SC->File->getSymbols()) {
     auto *D = dyn_cast_or_null<DefinedRegular>(S);
-    if (!D || D->getChunk() != SC || D->getValue() > Addr ||
+    if (!D || D->File != SC->File || D->getChunk() != SC ||
+        D->getValue() > Addr ||
         (Candidate && D->getValue() < Candidate->getValue()))
       continue;
 
     Candidate = D;
   }
 
   return Candidate;
 }
 
+static std::string getSymbolLocations(BitcodeFile *File) {
+  std::string Result = "\n>>> referenced by ";
+  StringRef Source = File->Obj->getSourceFileName();
+  if (!Source.empty())
+    Result += Source.str() + "\n>>>               ";
+  Result += toString(File);
+  return Result;
+}
+
 std::string getSymbolLocations(ObjFile *File, uint32_t SymIndex) {
   struct Location {
     Symbol *Sym;
     std::pair<StringRef, uint32_t> FileLine;
   };
   std::vector<Location> Locations;
 
   for (Chunk *C : File->getChunks()) {
if (!Loc.FileLine.first.empty())
          << "\n>>>               ";
     OS << toString(File);
     if (Loc.Sym)
       OS << ":(" << toString(*Loc.Sym) << ')';
   }
   return OS.str();
 }
 
 void SymbolTable::loadMinGWAutomaticImports() {
   for (auto &I : SymMap) {
     Symbol *Sym = I.second;
     auto *Undef = dyn_cast<Undefined>(Sym);
     if (!Undef)
       continue;
     if (!Sym->IsUsedInRegularObj)
       continue;
 
     StringRef Name = Undef->getName();
if (SC && SC->getRelocs().size() == 1 && *SC->symbols().begin() == Sym) {
       log("Replacing .refptr." + Name + " with " + Imp->getName());
       Refptr->getChunk()->Live = false;
       Refptr->replaceKeepingName(Imp, ImpSize);
     }
   }
   return true;
 }
 
-void SymbolTable::reportRemainingUndefines() {
+void SymbolTable::reportUnresolvable() {
+  SmallPtrSet<Symbol *, 8> Undefs;
+  for (auto &I : SymMap) {
+    Symbol *Sym = I.second;
+    auto *Undef = dyn_cast<Undefined>(Sym);
+    if (!Undef)
+      continue;
+    if (Defined *D = Undef->getWeakAlias())
+      continue;
+    StringRef Name = Undef->getName();
+    if (Name.startswith("__imp_")) {
+      Symbol *Imp = find(Name.substr(strlen("__imp_")));
+      if (Imp && isa<Defined>(Imp))
+        continue;
+    }
+    if (Name.contains("_PchSym_"))
+      continue;
+    if (Config->MinGW && handleMinGWAutomaticImport(Sym, Name))
+      continue;
+    Undefs.insert(Sym);
+  }
+
+  for (Symbol *B : Config->GCRoot)
+    if (Undefs.count(B))
+      error("<root>: undefined symbol: " + toString(*B));
+
+  for (ObjFile *File : ObjFile::Instances) {
+    size_t SymIndex = (size_t)-1;
+    for (Symbol *Sym : File->getSymbols()) {
+      ++SymIndex;
+      if (!Sym)
+        continue;
+      if (Undefs.count(Sym)) {
+        error("undefined symbol: " + toString(*Sym) +
+              getSymbolLocations(File, SymIndex));
+      }
+    }
+  }
+
+  for (BitcodeFile *File : BitcodeFile::Instances) {
+    for (Symbol *Sym : File->getSymbols()) {
+      if (!Sym)
+        continue;
+      if (Undefs.count(Sym)) {
+        error("undefined symbol: " + toString(*Sym) + getSymbolLocations(File));
+      }
+    }
+  }
+}
+
+void SymbolTable::resolveRemainingUndefines() {
   SmallPtrSet<Symbol *, 8> Undefs;
   DenseMap<Symbol *, Symbol *> LocalImports;
 
   for (auto &I : SymMap) {
     Symbol *Sym = I.second;
     auto *Undef = dyn_cast<Undefined>(Sym);
     if (!Undef)
       continue;
if (Name.startswith("__imp_")) {
       }
     }
 
     // We don't want to report missing Microsoft precompiled headers symbols.
     // A proper message will be emitted instead in PDBLinker::aquirePrecompObj
     if (Name.contains("_PchSym_"))
       continue;
 
-    if (Config->MinGW && handleMinGWAutomaticImport(Sym, Name))
-      continue;
-
     // Remaining undefined symbols are not fatal if /force is specified.
     // They are replaced with dummy defined symbols.
     if (Config->ForceUnresolved)
       replaceSymbol<DefinedAbsolute>(Sym, Name, 0);
     Undefs.insert(Sym);
   }
 
   if (Undefs.empty() && LocalImports.empty())

lld/test/COFF/unresolved-lto-bitcode.ll

+; REQUIRES: x86
+; RUN: rm -fr %t
+; RUN: mkdir %t
+; RUN: opt -thinlto-bc -o %t/main.obj %s
+; RUN: opt -thinlto-bc -o %t/foo.obj %S/Inputs/lto-dep.ll
+; RUN: not lld-link -lldsavetemps -out:%t/main.exe -entry:main \
+; RUN:   -subsystem:console %t/main.obj %t/foo.obj 2>&1 | FileCheck %s
+; RUN: ls %t | sort | FileCheck --check-prefix=FILE %s
+
+; Check that the undefined symbol is reported, and that only the two
+; object files we created are present in the directory (indicating that
+; LTO did not run).
+; CHECK: undefined symbol: bar
+; CHECK: referenced by {{.*}}unresolved-lto-bitcode.ll
+; CHECK: >>>           {{.*}}unresolved-lto-bitcode.ll.tmp/main.obj
+; FILE-NOT: {{.}}
+; FILE: foo.obj
+; FILE: main.obj
+; FILE-NOT: {{.}}
+
+target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-windows-msvc"
+
+define i32 @main() {
+  call void @foo()
+  call void @bar()
+  ret i32 0
+}
+
+declare void @bar()
+declare void @foo()

lld/test/COFF/unresolved-lto.ll

+; REQUIRES: x86
+; RUN: rm -fr %t
+; RUN: mkdir %t
+; RUN: llc -filetype=obj -o %t/main.obj %s
+; RUN: opt -thinlto-bc -o %t/foo.obj %S/Inputs/lto-dep.ll
+; RUN: not lld-link -lldsavetemps -out:%t/main.exe -entry:main \
+; RUN:   -subsystem:console %t/main.obj %t/foo.obj 2>&1 | FileCheck %s
+; RUN: ls %t | sort | FileCheck --check-prefix=FILE %s
+
+; Check that the undefined symbol is reported, and that only the two
+; object files we created are present in the directory (indicating that
+; LTO did not run).
+; CHECK: undefined symbol: bar
+; FILE-NOT: {{.}}
+; FILE: foo.obj
+; FILE: main.obj
+; FILE-NOT: {{.}}
+
+target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-windows-msvc"
+
+define i32 @main() {
+  call void @foo()
+  call void @bar()
+  ret i32 0
+}
+
+declare void @bar()
+declare void @foo()