[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

87

Source -> source

91

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

91

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

144

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

260–350

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

144

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.

260–350

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

144

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

143

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

143

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 we are going to do codegen for link-time optimization, check for
+  // unresolvable symbols first, so we don't spend time generating code that
+  // will fail to link anyway.
+  if (!BitcodeFile::instances.empty() && !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.
public:
 
   // Iterates symbols in non-determinstic hash table order.
   template <typename T> void forEachSymbol(T callback) {
     for (auto &pair : symMap)
       callback(pair.second);
   }
 
 private:
+  /// Given a name without "__imp_" prefix, returns a defined symbol
+  /// with the "__imp_" prefix, if it exists.
+  Defined *impSymbol(StringRef name);
   /// Inserts symbol if not already present.
   std::pair<Symbol *, bool> insert(StringRef name);
   /// Same as insert(Name), but also sets isUsedInRegularObj.
   std::pair<Symbol *, bool> insert(StringRef name, InputFile *f);
 
   std::vector<Symbol *> getSymsWithPrefix(StringRef prefix);
 
   llvm::DenseMap<llvm::CachedHashStringRef, Symbol *> symMap;

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::string res("\n>>> referenced by ");
+  StringRef source = file->obj->getSourceFileName();
+  if (!source.empty())
+    res += source.str() + "\n>>>               ";
+  res += 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++;
     }
   }
for (auto &i : symMap) {
 
     log("Loading lazy " + l->getName() + " from " + l->file->getName() +
         " for automatic import");
     l->pendingArchiveLoad = true;
     l->file->addMember(&l->sym);
   }
 }
 
-bool SymbolTable::handleMinGWAutomaticImport(Symbol *sym, StringRef name) {
+Defined *SymbolTable::impSymbol(StringRef name) {
   if (name.startswith("__imp_"))
-    return false;
-  Defined *imp = dyn_cast_or_null<Defined>(find(("__imp_" + name).str()));
+    return nullptr;
+  return dyn_cast_or_null<Defined>(find(("__imp_" + name).str()));
+}
+
+bool SymbolTable::handleMinGWAutomaticImport(Symbol *sym, StringRef name) {
+  Defined *imp = impSymbol(name);
   if (!imp)
     return false;
 
   // Replace the reference directly to a variable with a reference
   // to the import address table instead. This obviously isn't right,
   // but we mark the symbol as isRuntimePseudoReloc, and a later pass
   // will add runtime pseudo relocations for every relocation against
   // this Symbol. The runtime pseudo relocation framework expects the
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() {
+/// Helper function for reportUnresolvable and resolveRemainingUndefines.
+/// This function emits an "undefined symbol" diagnostic for each symbol in
+/// undefs. If localImports is not nullptr, it also emits a "locally
+/// defined symbol imported" diagnostic for symbols in localImports.
+/// objFiles and bitcodeFiles (if not nullptr) are used to report where
+/// undefined symbols are referenced.
+static void
+reportProblemSymbols(const SmallPtrSetImpl<Symbol *> &undefs,
+                     const DenseMap<Symbol *, Symbol *> *localImports,
+                     const std::vector<ObjFile *> objFiles,
+                     const std::vector<BitcodeFile *> *bitcodeFiles) {
+
+  // Return early if there is nothing to report (which should be
+  // the common case).
+  if (undefs.empty() && (!localImports || localImports->empty()))
+    return;
+
+  for (Symbol *b : config->gcroot) {
+    if (undefs.count(b))
+      errorOrWarn("<root>: undefined symbol: " + toString(*b));
+    if (localImports)
+      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;
+
+  auto processFile = [&](InputFile *file, ArrayRef<Symbol *> symbols) {
+    uint32_t symIndex = (uint32_t)-1;
+    for (Symbol *sym : symbols) {
+      ++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});
+        }
+      }
+      if (localImports)
+        if (Symbol *imp = localImports->lookup(sym))
+          warn(toString(file) +
+               ": locally defined symbol imported: " + toString(*imp) +
+               " (defined in " + toString(imp->getFile()) + ") [LNK4217]");
+    }
+  };
+
+  for (ObjFile *file : objFiles)
+    processFile(file, file->getSymbols());
+
+  if (bitcodeFiles)
+    for (BitcodeFile *file : *bitcodeFiles)
+      processFile(file, file->getSymbols());
+
+  for (const UndefinedDiag &undefDiag : undefDiags)
+    reportUndefinedSymbol(undefDiag);
+}
+
+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 && impSymbol(name))
+      continue;
+    undefs.insert(sym);
+  }
+
+  reportProblemSymbols(undefs,
+                       /* localImports */ nullptr, ObjFile::instances,
+                       &BitcodeFile::instances);
+}
+
+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;
for (auto &i : symMap) {
 
     // 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;
-    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});
-        }
-      }
-      if (config->warnLocallyDefinedImported)
-        if (Symbol *imp = localImports.lookup(sym))
-          warn(toString(file) +
-               ": locally defined symbol imported: " + toString(*imp) +
-               " (defined in " + toString(imp->getFile()) + ") [LNK4217]");
-    }
-  }
-
-  for (const UndefinedDiag& undefDiag : undefDiags)
-    reportUndefinedSymbol(undefDiag);
+  reportProblemSymbols(
+      undefs, config->warnLocallyDefinedImported ? &localImports : nullptr,
+      ObjFile::instances, /* bitcode files no longer needed */ nullptr);
 }
 
 std::pair<Symbol *, bool> SymbolTable::insert(StringRef name) {
   bool inserted = false;
   Symbol *&sym = symMap[CachedHashStringRef(name)];
   if (!sym) {
     sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
     sym->isUsedInRegularObj = false;

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