[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 +=.

145

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));

256–323

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

145

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.

256–323

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

145

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

144

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

144

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 (unless -thinlto-index-only was given, in which case we
-  // resolve symbols and write indices, but don't generate native code or link).
-  symtab->addCombinedLTOObjects();
-
-  // If -thinlto-index-only is given, we should create only "index
-  // files" and not object files. Index file creation is already done
-  // in addCombinedLTOObject, so we are done if that's the case.
-  if (config->thinLTOIndexOnly)
-    return;
-
-  // If we generated native object files from bitcode files, this resolves
-  // references to the symbols we use from them.
-  run();
-
   if (args.hasArg(OPT_include_optional)) {
     // Handle /includeoptional
     for (auto *arg : args.filtered(OPT_include_optional))
       if (dyn_cast_or_null<Lazy>(symtab->find(arg->getValue())))
         addUndefined(arg->getValue());
     while (run());
   }
 
if (config->mingw) {
     // 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 (unless -thinlto-index-only was given, in which case we
+  // resolve symbols and write indices, but don't generate native code or link).
+  symtab->addCombinedLTOObjects();
+
+  // If -thinlto-index-only is given, we should create only "index
+  // files" and not object files. Index file creation is already done
+  // in addCombinedLTOObject, so we are done if that's the case.
+  if (config->thinLTOIndexOnly)
+    return;
+
+  // If we generated native object files from bitcode files, this resolves
+  // references to the symbols we use from them.
+  run();
+
+  // Resolve remaining undefined symbols and warn about imported locals.
+  symtab->resolveRemainingUndefines();
   if (errorCount())
     return;
 
   if (config->mingw) {
     // In MinGW, all symbols are automatically exported if no symbols
     // are chosen to be exported.
     maybeExportMinGWSymbols(args);
 

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->data || d->getChunk() != sc || d->getValue() > addr ||
+    if (!d || !d->data || d->file != sc->file || d->getChunk() != sc || d->getValue() > addr ||
         (candidate && d->getValue() < candidate->getValue()))
       continue;
 
     candidate = d;
   }
 
   return candidate;
 }
 
+static std::vector<std::string> getSymbolLocations(BitcodeFile *File) {
+  std::vector<std::string> res(1);
+  llvm::raw_string_ostream os(res[0]);
+  os << "\n>>> referenced by ";
+  StringRef Source = File->obj->getSourceFileName();
+  if (!Source.empty())
+    os << Source.str() << "\n>>>               ";
+  os << toString(File);
+  return res;
+}
+
 // Given a file and the index of a symbol in that file, returns a description
 // of all references to that symbol from that file. If no debug information is
 // available, returns just the name of the file, else one string per actual
 // reference as described in the debug info.
 std::vector<std::string> getSymbolLocations(ObjFile *file, uint32_t symIndex) {
   struct Location {
     Symbol *sym;
     std::pair<StringRef, uint32_t> fileLine;
if (!loc.fileLine.first.empty())
          << "\n>>>               ";
     os << toString(file);
     if (loc.sym)
       os << ":(" << toString(*loc.sym) << ')';
   }
   return symbolLocations;
 }
 
+std::vector<std::string> getSymbolLocations(InputFile *file, uint32_t symIndex) {
+  assert(file->kind() == InputFile::Kind::ObjectKind ||
+         file->kind() == InputFile::Kind::BitcodeKind);
+  if (auto *o = dyn_cast<ObjFile>(file))
+    return getSymbolLocations(o, symIndex);
+  if (auto *b = dyn_cast<BitcodeFile>(file))
+    return getSymbolLocations(b);
+  return {};
+}
+
 // For an undefined symbol, stores all files referencing it and the index of
 // the undefined symbol in each file.
 struct UndefinedDiag {
   Symbol *sym;
   struct File {
-    ObjFile *oFile;
-    uint64_t symIndex;
+    InputFile *file;
+    uint32_t symIndex;
   };
   std::vector<File> files;
 };
 
 static void reportUndefinedSymbol(const UndefinedDiag &undefDiag) {
   std::string out;
   llvm::raw_string_ostream os(out);
   os << "undefined symbol: " << toString(*undefDiag.sym);
 
   const size_t maxUndefReferences = 10;
   size_t i = 0, numRefs = 0;
   for (const UndefinedDiag::File &ref : undefDiag.files) {
     std::vector<std::string> symbolLocations =
-        getSymbolLocations(ref.oFile, ref.symIndex);
+        getSymbolLocations(ref.file, ref.symIndex);
     numRefs += symbolLocations.size();
     for (const std::string &s : symbolLocations) {
       if (i >= maxUndefReferences)
         break;
       os << s;
       i++;
     }
   }
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));
+
+  std::vector<UndefinedDiag> undefDiags;
+  DenseMap<Symbol *, int> firstDiag;
+
+  for (ObjFile *file : ObjFile::instances) {
+    uint32_t symIndex = (uint32_t) -1;
+    for (Symbol *sym : file->getSymbols()) {
+      ++symIndex;
+      if (!sym)
+        continue;
+      if (undefs.count(sym)) {
+        auto it = firstDiag.find(sym);
+        if (it == firstDiag.end()) {
+          firstDiag[sym] = undefDiags.size();
+          undefDiags.push_back({sym, {{file, symIndex}}});
+        } else {
+          undefDiags[it->second].files.push_back({file, symIndex});
+        }
+      }
+    }
+  }
+
+  for (BitcodeFile *file : BitcodeFile::instances) {
+    for (Symbol *sym : file->getSymbols()) {
+      if (!sym)
+        continue;
+      if (undefs.count(sym)) {
+        auto it = firstDiag.find(sym);
+        if (it == firstDiag.end()) {
+          firstDiag[sym] = undefDiags.size();
+          undefDiags.push_back({sym, {{file, 0}}});
+        } else {
+          undefDiags[it->second].files.push_back({file, 0});
+        }
+      }
+    }
+  }
+
+  for (const UndefinedDiag& undefDiag : undefDiags)
+    reportUndefinedSymbol(undefDiag);
+}
+
+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())
     return;
 
   for (Symbol *b : config->gcroot) {
     if (undefs.count(b))
       errorOrWarn("<root>: undefined symbol: " + toString(*b));
     if (config->warnLocallyDefinedImported)
       if (Symbol *imp = localImports.lookup(b))
         warn("<root>: locally defined symbol imported: " + toString(*imp) +
              " (defined in " + toString(imp->getFile()) + ") [LNK4217]");
   }
 
   std::vector<UndefinedDiag> undefDiags;
   DenseMap<Symbol *, int> firstDiag;
 
   for (ObjFile *file : ObjFile::instances) {
-    size_t symIndex = (size_t)-1;
+    uint32_t symIndex = (uint32_t) -1;
     for (Symbol *sym : file->getSymbols()) {
       ++symIndex;
       if (!sym)
         continue;
       if (undefs.count(sym)) {
         auto it = firstDiag.find(sym);
         if (it == firstDiag.end()) {
           firstDiag[sym] = undefDiags.size();

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
+; RUN: ls %t | count 2
+
+; 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: foo.obj
+; FILE: main.obj
+
+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
+; RUN: ls %t | count 2
+
+; 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 {{.*}}main.obj
+; FILE: foo.obj
+; FILE: main.obj
+
+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()