lld/COFF/SymbolTable.cpp

   1 //===- SymbolTable.cpp ----------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "SymbolTable.h"
  10 #include "COFFLinkerContext.h"
  11 #include "Config.h"
  12 #include "Driver.h"
  13 #include "LTO.h"
  14 #include "PDB.h"
  15 #include "Symbols.h"
  16 #include "lld/Common/ErrorHandler.h"
  17 #include "lld/Common/Memory.h"
  18 #include "lld/Common/Timer.h"
  19 #include "llvm/DebugInfo/DIContext.h"
  20 #include "llvm/IR/LLVMContext.h"
  21 #include "llvm/LTO/LTO.h"
  22 #include "llvm/Object/WindowsMachineFlag.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Support/raw_ostream.h"
  25 #include <utility>
  26
  27 using namespace llvm;
  28
  29 namespace lld::coff {
  30
  31 StringRef ltrim1(StringRef s, const char *chars) {
  32   if (!s.empty() && strchr(chars, s[0]))
  33     return s.substr(1);
  34   return s;
  35 }
  36
  37 static bool compatibleMachineType(COFFLinkerContext &ctx, MachineTypes mt) {
  38   if (mt == IMAGE_FILE_MACHINE_UNKNOWN)
  39     return true;
  40   switch (ctx.config.machine) {
  41   case ARM64:
  42     return mt == ARM64 || mt == ARM64X;
  43   case ARM64EC:
  44     return COFF::isArm64EC(mt) || mt == AMD64;
  45   case ARM64X:
  46     return COFF::isAnyArm64(mt) || mt == AMD64;
  47   default:
  48     return ctx.config.machine == mt;
  49   }
  50 }
  51
  52 void SymbolTable::addFile(InputFile *file) {
  53   log("Reading " + toString(file));
  54   if (file->lazy) {
  55     if (auto *f = dyn_cast<BitcodeFile>(file))
  56       f->parseLazy();
  57     else
  58       cast<ObjFile>(file)->parseLazy();
  59   } else {
  60     file->parse();
  61     if (auto *f = dyn_cast<ObjFile>(file)) {
  62       ctx.objFileInstances.push_back(f);
  63     } else if (auto *f = dyn_cast<BitcodeFile>(file)) {
  64       ctx.bitcodeFileInstances.push_back(f);
  65     } else if (auto *f = dyn_cast<ImportFile>(file)) {
  66       ctx.importFileInstances.push_back(f);
  67     }
  68   }
  69
  70   MachineTypes mt = file->getMachineType();
  71   if (ctx.config.machine == IMAGE_FILE_MACHINE_UNKNOWN) {
  72     ctx.config.machine = mt;
  73     ctx.driver.addWinSysRootLibSearchPaths();
  74   } else if (!compatibleMachineType(ctx, mt)) {
  75     error(toString(file) + ": machine type " + machineToStr(mt) +
  76           " conflicts with " + machineToStr(ctx.config.machine));
  77     return;
  78   }
  79
  80   ctx.driver.parseDirectives(file);
  81 }
  82
  83 static void errorOrWarn(const Twine &s, bool forceUnresolved) {
  84   if (forceUnresolved)
  85     warn(s);
  86   else
  87     error(s);
  88 }
  89
  90 // Causes the file associated with a lazy symbol to be linked in.
  91 static void forceLazy(Symbol *s) {
  92   s->pendingArchiveLoad = true;
  93   switch (s->kind()) {
  94   case Symbol::Kind::LazyArchiveKind: {
  95     auto *l = cast<LazyArchive>(s);
  96     l->file->addMember(l->sym);
  97     break;
  98   }
  99   case Symbol::Kind::LazyObjectKind: {
 100     InputFile *file = cast<LazyObject>(s)->file;
 101     file->ctx.symtab.addFile(file);
 102     break;
 103   }
 104   case Symbol::Kind::LazyDLLSymbolKind: {
 105     auto *l = cast<LazyDLLSymbol>(s);
 106     l->file->makeImport(l->sym);
 107     break;
 108   }
 109   default:
 110     llvm_unreachable(
 111         "symbol passed to forceLazy is not a LazyArchive or LazyObject");
 112   }
 113 }
 114
 115 // Returns the symbol in SC whose value is <= Addr that is closest to Addr.
 116 // This is generally the global variable or function whose definition contains
 117 // Addr.
 118 static Symbol *getSymbol(SectionChunk *sc, uint32_t addr) {
 119   DefinedRegular *candidate = nullptr;
 120
 121   for (Symbol *s : sc->file->getSymbols()) {
 122     auto *d = dyn_cast_or_null<DefinedRegular>(s);
 123     if (!d || !d->data || d->file != sc->file || d->getChunk() != sc ||
 124         d->getValue() > addr ||
 125         (candidate && d->getValue() < candidate->getValue()))
 126       continue;
 127
 128     candidate = d;
 129   }
 130
 131   return candidate;
 132 }
 133
 134 static std::vector<std::string> getSymbolLocations(BitcodeFile *file) {
 135   std::string res("\n>>> referenced by ");
 136   StringRef source = file->obj->getSourceFileName();
 137   if (!source.empty())
 138     res += source.str() + "\n>>>               ";
 139   res += toString(file);
 140   return {res};
 141 }
 142
 143 static std::optional<std::pair<StringRef, uint32_t>>
 144 getFileLineDwarf(const SectionChunk *c, uint32_t addr) {
 145   std::optional<DILineInfo> optionalLineInfo =
 146       c->file->getDILineInfo(addr, c->getSectionNumber() - 1);
 147   if (!optionalLineInfo)
 148     return std::nullopt;
 149   const DILineInfo &lineInfo = *optionalLineInfo;
 150   if (lineInfo.FileName == DILineInfo::BadString)
 151     return std::nullopt;
 152   return std::make_pair(saver().save(lineInfo.FileName), lineInfo.Line);
 153 }
 154
 155 static std::optional<std::pair<StringRef, uint32_t>>
 156 getFileLine(const SectionChunk *c, uint32_t addr) {
 157   // MinGW can optionally use codeview, even if the default is dwarf.
 158   std::optional<std::pair<StringRef, uint32_t>> fileLine =
 159       getFileLineCodeView(c, addr);
 160   // If codeview didn't yield any result, check dwarf in MinGW mode.
 161   if (!fileLine && c->file->ctx.config.mingw)
 162     fileLine = getFileLineDwarf(c, addr);
 163   return fileLine;
 164 }
 165
 166 // Given a file and the index of a symbol in that file, returns a description
 167 // of all references to that symbol from that file. If no debug information is
 168 // available, returns just the name of the file, else one string per actual
 169 // reference as described in the debug info.
 170 // Returns up to maxStrings string descriptions, along with the total number of
 171 // locations found.
 172 static std::pair<std::vector<std::string>, size_t>
 173 getSymbolLocations(ObjFile *file, uint32_t symIndex, size_t maxStrings) {
 174   struct Location {
 175     Symbol *sym;
 176     std::pair<StringRef, uint32_t> fileLine;
 177   };
 178   std::vector<Location> locations;
 179   size_t numLocations = 0;
 180
 181   for (Chunk *c : file->getChunks()) {
 182     auto *sc = dyn_cast<SectionChunk>(c);
 183     if (!sc)
 184       continue;
 185     for (const coff_relocation &r : sc->getRelocs()) {
 186       if (r.SymbolTableIndex != symIndex)
 187         continue;
 188       numLocations++;
 189       if (locations.size() >= maxStrings)
 190         continue;
 191
 192       std::optional<std::pair<StringRef, uint32_t>> fileLine =
 193           getFileLine(sc, r.VirtualAddress);
 194       Symbol *sym = getSymbol(sc, r.VirtualAddress);
 195       if (fileLine)
 196         locations.push_back({sym, *fileLine});
 197       else if (sym)
 198         locations.push_back({sym, {"", 0}});
 199     }
 200   }
 201
 202   if (maxStrings == 0)
 203     return std::make_pair(std::vector<std::string>(), numLocations);
 204
 205   if (numLocations == 0)
 206     return std::make_pair(
 207         std::vector<std::string>{"\n>>> referenced by " + toString(file)}, 1);
 208
 209   std::vector<std::string> symbolLocations(locations.size());
 210   size_t i = 0;
 211   for (Location loc : locations) {
 212     llvm::raw_string_ostream os(symbolLocations[i++]);
 213     os << "\n>>> referenced by ";
 214     if (!loc.fileLine.first.empty())
 215       os << loc.fileLine.first << ":" << loc.fileLine.second
 216          << "\n>>>               ";
 217     os << toString(file);
 218     if (loc.sym)
 219       os << ":(" << toString(file->ctx, *loc.sym) << ')';
 220   }
 221   return std::make_pair(symbolLocations, numLocations);
 222 }
 223
 224 std::vector<std::string> getSymbolLocations(ObjFile *file, uint32_t symIndex) {
 225   return getSymbolLocations(file, symIndex, SIZE_MAX).first;
 226 }
 227
 228 static std::pair<std::vector<std::string>, size_t>
 229 getSymbolLocations(InputFile *file, uint32_t symIndex, size_t maxStrings) {
 230   if (auto *o = dyn_cast<ObjFile>(file))
 231     return getSymbolLocations(o, symIndex, maxStrings);
 232   if (auto *b = dyn_cast<BitcodeFile>(file)) {
 233     std::vector<std::string> symbolLocations = getSymbolLocations(b);
 234     size_t numLocations = symbolLocations.size();
 235     if (symbolLocations.size() > maxStrings)
 236       symbolLocations.resize(maxStrings);
 237     return std::make_pair(symbolLocations, numLocations);
 238   }
 239   llvm_unreachable("unsupported file type passed to getSymbolLocations");
 240   return std::make_pair(std::vector<std::string>(), (size_t)0);
 241 }
 242
 243 // For an undefined symbol, stores all files referencing it and the index of
 244 // the undefined symbol in each file.
 245 struct UndefinedDiag {
 246   Symbol *sym;
 247   struct File {
 248     InputFile *file;
 249     uint32_t symIndex;
 250   };
 251   std::vector<File> files;
 252 };
 253
 254 static void reportUndefinedSymbol(const COFFLinkerContext &ctx,
 255                                   const UndefinedDiag &undefDiag) {
 256   std::string out;
 257   llvm::raw_string_ostream os(out);
 258   os << "undefined symbol: " << toString(ctx, *undefDiag.sym);
 259
 260   const size_t maxUndefReferences = 3;
 261   size_t numDisplayedRefs = 0, numRefs = 0;
 262   for (const UndefinedDiag::File &ref : undefDiag.files) {
 263     auto [symbolLocations, totalLocations] = getSymbolLocations(
 264         ref.file, ref.symIndex, maxUndefReferences - numDisplayedRefs);
 265
 266     numRefs += totalLocations;
 267     numDisplayedRefs += symbolLocations.size();
 268     for (const std::string &s : symbolLocations) {
 269       os << s;
 270     }
 271   }
 272   if (numDisplayedRefs < numRefs)
 273     os << "\n>>> referenced " << numRefs - numDisplayedRefs << " more times";
 274   errorOrWarn(os.str(), ctx.config.forceUnresolved);
 275 }
 276
 277 void SymbolTable::loadMinGWSymbols() {
 278   for (auto &i : symMap) {
 279     Symbol *sym = i.second;
 280     auto *undef = dyn_cast<Undefined>(sym);
 281     if (!undef)
 282       continue;
 283     if (undef->getWeakAlias())
 284       continue;
 285
 286     StringRef name = undef->getName();
 287
 288     if (ctx.config.machine == I386 && ctx.config.stdcallFixup) {
 289       // Check if we can resolve an undefined decorated symbol by finding
 290       // the intended target as an undecorated symbol (only with a leading
 291       // underscore).
 292       StringRef origName = name;
 293       StringRef baseName = name;
 294       // Trim down stdcall/fastcall/vectorcall symbols to the base name.
 295       baseName = ltrim1(baseName, "_@");
 296       baseName = baseName.substr(0, baseName.find('@'));
 297       // Add a leading underscore, as it would be in cdecl form.
 298       std::string newName = ("_" + baseName).str();
 299       Symbol *l;
 300       if (newName != origName && (l = find(newName)) != nullptr) {
 301         // If we found a symbol and it is lazy; load it.
 302         if (l->isLazy() && !l->pendingArchiveLoad) {
 303           log("Loading lazy " + l->getName() + " from " +
 304               l->getFile()->getName() + " for stdcall fixup");
 305           forceLazy(l);
 306         }
 307         // If it's lazy or already defined, hook it up as weak alias.
 308         if (l->isLazy() || isa<Defined>(l)) {
 309           if (ctx.config.warnStdcallFixup)
 310             warn("Resolving " + origName + " by linking to " + newName);
 311           else
 312             log("Resolving " + origName + " by linking to " + newName);
 313           undef->weakAlias = l;
 314           continue;
 315         }
 316       }
 317     }
 318
 319     if (ctx.config.autoImport) {
 320       if (name.starts_with("__imp_"))
 321         continue;
 322       // If we have an undefined symbol, but we have a lazy symbol we could
 323       // load, load it.
 324       Symbol *l = find(("__imp_" + name).str());
 325       if (!l || l->pendingArchiveLoad || !l->isLazy())
 326         continue;
 327
 328       log("Loading lazy " + l->getName() + " from " + l->getFile()->getName() +
 329           " for automatic import");
 330       forceLazy(l);
 331     }
 332   }
 333 }
 334
 335 Defined *SymbolTable::impSymbol(StringRef name) {
 336   if (name.starts_with("__imp_"))
 337     return nullptr;
 338   return dyn_cast_or_null<Defined>(find(("__imp_" + name).str()));
 339 }
 340
 341 bool SymbolTable::handleMinGWAutomaticImport(Symbol *sym, StringRef name) {
 342   Defined *imp = impSymbol(name);
 343   if (!imp)
 344     return false;
 345
 346   // Replace the reference directly to a variable with a reference
 347   // to the import address table instead. This obviously isn't right,
 348   // but we mark the symbol as isRuntimePseudoReloc, and a later pass
 349   // will add runtime pseudo relocations for every relocation against
 350   // this Symbol. The runtime pseudo relocation framework expects the
 351   // reference itself to point at the IAT entry.
 352   size_t impSize = 0;
 353   if (isa<DefinedImportData>(imp)) {
 354     log("Automatically importing " + name + " from " +
 355         cast<DefinedImportData>(imp)->getDLLName());
 356     impSize = sizeof(DefinedImportData);
 357   } else if (isa<DefinedRegular>(imp)) {
 358     log("Automatically importing " + name + " from " +
 359         toString(cast<DefinedRegular>(imp)->file));
 360     impSize = sizeof(DefinedRegular);
 361   } else {
 362     warn("unable to automatically import " + name + " from " + imp->getName() +
 363          " from " + toString(cast<DefinedRegular>(imp)->file) +
 364          "; unexpected symbol type");
 365     return false;
 366   }
 367   sym->replaceKeepingName(imp, impSize);
 368   sym->isRuntimePseudoReloc = true;
 369
 370   // There may exist symbols named .refptr.<name> which only consist
 371   // of a single pointer to <name>. If it turns out <name> is
 372   // automatically imported, we don't need to keep the .refptr.<name>
 373   // pointer at all, but redirect all accesses to it to the IAT entry
 374   // for __imp_<name> instead, and drop the whole .refptr.<name> chunk.
 375   DefinedRegular *refptr =
 376       dyn_cast_or_null<DefinedRegular>(find((".refptr." + name).str()));
 377   if (refptr && refptr->getChunk()->getSize() == ctx.config.wordsize) {
 378     SectionChunk *sc = dyn_cast_or_null<SectionChunk>(refptr->getChunk());
 379     if (sc && sc->getRelocs().size() == 1 && *sc->symbols().begin() == sym) {
 380       log("Replacing .refptr." + name + " with " + imp->getName());
 381       refptr->getChunk()->live = false;
 382       refptr->replaceKeepingName(imp, impSize);
 383     }
 384   }
 385   return true;
 386 }
 387
 388 /// Helper function for reportUnresolvable and resolveRemainingUndefines.
 389 /// This function emits an "undefined symbol" diagnostic for each symbol in
 390 /// undefs. If localImports is not nullptr, it also emits a "locally
 391 /// defined symbol imported" diagnostic for symbols in localImports.
 392 /// objFiles and bitcodeFiles (if not nullptr) are used to report where
 393 /// undefined symbols are referenced.
 394 static void reportProblemSymbols(
 395     const COFFLinkerContext &ctx, const SmallPtrSetImpl<Symbol *> &undefs,
 396     const DenseMap<Symbol *, Symbol *> *localImports, bool needBitcodeFiles) {
 397   // Return early if there is nothing to report (which should be
 398   // the common case).
 399   if (undefs.empty() && (!localImports || localImports->empty()))
 400     return;
 401
 402   for (Symbol *b : ctx.config.gcroot) {
 403     if (undefs.count(b))
 404       errorOrWarn("<root>: undefined symbol: " + toString(ctx, *b),
 405                   ctx.config.forceUnresolved);
 406     if (localImports)
 407       if (Symbol *imp = localImports->lookup(b))
 408         warn("<root>: locally defined symbol imported: " + toString(ctx, *imp) +
 409              " (defined in " + toString(imp->getFile()) + ") [LNK4217]");
 410   }
 411
 412   std::vector<UndefinedDiag> undefDiags;
 413   DenseMap<Symbol *, int> firstDiag;
 414
 415   auto processFile = [&](InputFile *file, ArrayRef<Symbol *> symbols) {
 416     uint32_t symIndex = (uint32_t)-1;
 417     for (Symbol *sym : symbols) {
 418       ++symIndex;
 419       if (!sym)
 420         continue;
 421       if (undefs.count(sym)) {
 422         auto it = firstDiag.find(sym);
 423         if (it == firstDiag.end()) {
 424           firstDiag[sym] = undefDiags.size();
 425           undefDiags.push_back({sym, {{file, symIndex}}});
 426         } else {
 427           undefDiags[it->second].files.push_back({file, symIndex});
 428         }
 429       }
 430       if (localImports)
 431         if (Symbol *imp = localImports->lookup(sym))
 432           warn(toString(file) +
 433                ": locally defined symbol imported: " + toString(ctx, *imp) +
 434                " (defined in " + toString(imp->getFile()) + ") [LNK4217]");
 435     }
 436   };
 437
 438   for (ObjFile *file : ctx.objFileInstances)
 439     processFile(file, file->getSymbols());
 440
 441   if (needBitcodeFiles)
 442     for (BitcodeFile *file : ctx.bitcodeFileInstances)
 443       processFile(file, file->getSymbols());
 444
 445   for (const UndefinedDiag &undefDiag : undefDiags)
 446     reportUndefinedSymbol(ctx, undefDiag);
 447 }
 448
 449 void SymbolTable::reportUnresolvable() {
 450   SmallPtrSet<Symbol *, 8> undefs;
 451   for (auto &i : symMap) {
 452     Symbol *sym = i.second;
 453     auto *undef = dyn_cast<Undefined>(sym);
 454     if (!undef || sym->deferUndefined)
 455       continue;
 456     if (undef->getWeakAlias())
 457       continue;
 458     StringRef name = undef->getName();
 459     if (name.starts_with("__imp_")) {
 460       Symbol *imp = find(name.substr(strlen("__imp_")));
 461       if (imp && isa<Defined>(imp))
 462         continue;
 463     }
 464     if (name.contains("_PchSym_"))
 465       continue;
 466     if (ctx.config.autoImport && impSymbol(name))
 467       continue;
 468     undefs.insert(sym);
 469   }
 470
 471   reportProblemSymbols(ctx, undefs,
 472                        /* localImports */ nullptr, true);
 473 }
 474
 475 void SymbolTable::resolveRemainingUndefines() {
 476   llvm::TimeTraceScope timeScope("Resolve remaining undefined symbols");
 477   SmallPtrSet<Symbol *, 8> undefs;
 478   DenseMap<Symbol *, Symbol *> localImports;
 479
 480   for (auto &i : symMap) {
 481     Symbol *sym = i.second;
 482     auto *undef = dyn_cast<Undefined>(sym);
 483     if (!undef)
 484       continue;
 485     if (!sym->isUsedInRegularObj)
 486       continue;
 487
 488     StringRef name = undef->getName();
 489
 490     // A weak alias may have been resolved, so check for that.
 491     if (Defined *d = undef->getWeakAlias()) {
 492       // We want to replace Sym with D. However, we can't just blindly
 493       // copy sizeof(SymbolUnion) bytes from D to Sym because D may be an
 494       // internal symbol, and internal symbols are stored as "unparented"
 495       // Symbols. For that reason we need to check which type of symbol we
 496       // are dealing with and copy the correct number of bytes.
 497       if (isa<DefinedRegular>(d))
 498         memcpy(sym, d, sizeof(DefinedRegular));
 499       else if (isa<DefinedAbsolute>(d))
 500         memcpy(sym, d, sizeof(DefinedAbsolute));
 501       else
 502         memcpy(sym, d, sizeof(SymbolUnion));
 503       continue;
 504     }
 505
 506     // If we can resolve a symbol by removing __imp_ prefix, do that.
 507     // This odd rule is for compatibility with MSVC linker.
 508     if (name.starts_with("__imp_")) {
 509       Symbol *imp = find(name.substr(strlen("__imp_")));
 510       if (imp && isa<Defined>(imp)) {
 511         auto *d = cast<Defined>(imp);
 512         replaceSymbol<DefinedLocalImport>(sym, ctx, name, d);
 513         localImportChunks.push_back(cast<DefinedLocalImport>(sym)->getChunk());
 514         localImports[sym] = d;
 515         continue;
 516       }
 517     }
 518
 519     // We don't want to report missing Microsoft precompiled headers symbols.
 520     // A proper message will be emitted instead in PDBLinker::aquirePrecompObj
 521     if (name.contains("_PchSym_"))
 522       continue;
 523
 524     if (ctx.config.autoImport && handleMinGWAutomaticImport(sym, name))
 525       continue;
 526
 527     // Remaining undefined symbols are not fatal if /force is specified.
 528     // They are replaced with dummy defined symbols.
 529     if (ctx.config.forceUnresolved)
 530       replaceSymbol<DefinedAbsolute>(sym, ctx, name, 0);
 531     undefs.insert(sym);
 532   }
 533
 534   reportProblemSymbols(
 535       ctx, undefs,
 536       ctx.config.warnLocallyDefinedImported ? &localImports : nullptr, false);
 537 }
 538
 539 std::pair<Symbol *, bool> SymbolTable::insert(StringRef name) {
 540   bool inserted = false;
 541   Symbol *&sym = symMap[CachedHashStringRef(name)];
 542   if (!sym) {
 543     sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
 544     sym->isUsedInRegularObj = false;
 545     sym->pendingArchiveLoad = false;
 546     sym->canInline = true;
 547     inserted = true;
 548   }
 549   return {sym, inserted};
 550 }
 551
 552 std::pair<Symbol *, bool> SymbolTable::insert(StringRef name, InputFile *file) {
 553   std::pair<Symbol *, bool> result = insert(name);
 554   if (!file || !isa<BitcodeFile>(file))
 555     result.first->isUsedInRegularObj = true;
 556   return result;
 557 }
 558
 559 Symbol *SymbolTable::addUndefined(StringRef name, InputFile *f,
 560                                   bool isWeakAlias) {
 561   auto [s, wasInserted] = insert(name, f);
 562   if (wasInserted || (s->isLazy() && isWeakAlias)) {
 563     replaceSymbol<Undefined>(s, name);
 564     return s;
 565   }
 566   if (s->isLazy())
 567     forceLazy(s);
 568   return s;
 569 }
 570
 571 void SymbolTable::addLazyArchive(ArchiveFile *f, const Archive::Symbol &sym) {
 572   StringRef name = sym.getName();
 573   auto [s, wasInserted] = insert(name);
 574   if (wasInserted) {
 575     replaceSymbol<LazyArchive>(s, f, sym);
 576     return;
 577   }
 578   auto *u = dyn_cast<Undefined>(s);
 579   if (!u || u->weakAlias || s->pendingArchiveLoad)
 580     return;
 581   s->pendingArchiveLoad = true;
 582   f->addMember(sym);
 583 }
 584
 585 void SymbolTable::addLazyObject(InputFile *f, StringRef n) {
 586   assert(f->lazy);
 587   auto [s, wasInserted] = insert(n, f);
 588   if (wasInserted) {
 589     replaceSymbol<LazyObject>(s, f, n);
 590     return;
 591   }
 592   auto *u = dyn_cast<Undefined>(s);
 593   if (!u || u->weakAlias || s->pendingArchiveLoad)
 594     return;
 595   s->pendingArchiveLoad = true;
 596   f->lazy = false;
 597   addFile(f);
 598 }
 599
 600 void SymbolTable::addLazyDLLSymbol(DLLFile *f, DLLFile::Symbol *sym,
 601                                    StringRef n) {
 602   auto [s, wasInserted] = insert(n);
 603   if (wasInserted) {
 604     replaceSymbol<LazyDLLSymbol>(s, f, sym, n);
 605     return;
 606   }
 607   auto *u = dyn_cast<Undefined>(s);
 608   if (!u || u->weakAlias || s->pendingArchiveLoad)
 609     return;
 610   s->pendingArchiveLoad = true;
 611   f->makeImport(sym);
 612 }
 613
 614 static std::string getSourceLocationBitcode(BitcodeFile *file) {
 615   std::string res("\n>>> defined at ");
 616   StringRef source = file->obj->getSourceFileName();
 617   if (!source.empty())
 618     res += source.str() + "\n>>>            ";
 619   res += toString(file);
 620   return res;
 621 }
 622
 623 static std::string getSourceLocationObj(ObjFile *file, SectionChunk *sc,
 624                                         uint32_t offset, StringRef name) {
 625   std::optional<std::pair<StringRef, uint32_t>> fileLine;
 626   if (sc)
 627     fileLine = getFileLine(sc, offset);
 628   if (!fileLine)
 629     fileLine = file->getVariableLocation(name);
 630
 631   std::string res;
 632   llvm::raw_string_ostream os(res);
 633   os << "\n>>> defined at ";
 634   if (fileLine)
 635     os << fileLine->first << ":" << fileLine->second << "\n>>>            ";
 636   os << toString(file);
 637   return os.str();
 638 }
 639
 640 static std::string getSourceLocation(InputFile *file, SectionChunk *sc,
 641                                      uint32_t offset, StringRef name) {
 642   if (!file)
 643     return "";
 644   if (auto *o = dyn_cast<ObjFile>(file))
 645     return getSourceLocationObj(o, sc, offset, name);
 646   if (auto *b = dyn_cast<BitcodeFile>(file))
 647     return getSourceLocationBitcode(b);
 648   return "\n>>> defined at " + toString(file);
 649 }
 650
 651 // Construct and print an error message in the form of:
 652 //
 653 //   lld-link: error: duplicate symbol: foo
 654 //   >>> defined at bar.c:30
 655 //   >>>            bar.o
 656 //   >>> defined at baz.c:563
 657 //   >>>            baz.o
 658 void SymbolTable::reportDuplicate(Symbol *existing, InputFile *newFile,
 659                                   SectionChunk *newSc,
 660                                   uint32_t newSectionOffset) {
 661   std::string msg;
 662   llvm::raw_string_ostream os(msg);
 663   os << "duplicate symbol: " << toString(ctx, *existing);
 664
 665   DefinedRegular *d = dyn_cast<DefinedRegular>(existing);
 666   if (d && isa<ObjFile>(d->getFile())) {
 667     os << getSourceLocation(d->getFile(), d->getChunk(), d->getValue(),
 668                             existing->getName());
 669   } else {
 670     os << getSourceLocation(existing->getFile(), nullptr, 0, "");
 671   }
 672   os << getSourceLocation(newFile, newSc, newSectionOffset,
 673                           existing->getName());
 674
 675   if (ctx.config.forceMultiple)
 676     warn(os.str());
 677   else
 678     error(os.str());
 679 }
 680
 681 Symbol *SymbolTable::addAbsolute(StringRef n, COFFSymbolRef sym) {
 682   auto [s, wasInserted] = insert(n, nullptr);
 683   s->isUsedInRegularObj = true;
 684   if (wasInserted || isa<Undefined>(s) || s->isLazy())
 685     replaceSymbol<DefinedAbsolute>(s, ctx, n, sym);
 686   else if (auto *da = dyn_cast<DefinedAbsolute>(s)) {
 687     if (da->getVA() != sym.getValue())
 688       reportDuplicate(s, nullptr);
 689   } else if (!isa<DefinedCOFF>(s))
 690     reportDuplicate(s, nullptr);
 691   return s;
 692 }
 693
 694 Symbol *SymbolTable::addAbsolute(StringRef n, uint64_t va) {
 695   auto [s, wasInserted] = insert(n, nullptr);
 696   s->isUsedInRegularObj = true;
 697   if (wasInserted || isa<Undefined>(s) || s->isLazy())
 698     replaceSymbol<DefinedAbsolute>(s, ctx, n, va);
 699   else if (auto *da = dyn_cast<DefinedAbsolute>(s)) {
 700     if (da->getVA() != va)
 701       reportDuplicate(s, nullptr);
 702   } else if (!isa<DefinedCOFF>(s))
 703     reportDuplicate(s, nullptr);
 704   return s;
 705 }
 706
 707 Symbol *SymbolTable::addSynthetic(StringRef n, Chunk *c) {
 708   auto [s, wasInserted] = insert(n, nullptr);
 709   s->isUsedInRegularObj = true;
 710   if (wasInserted || isa<Undefined>(s) || s->isLazy())
 711     replaceSymbol<DefinedSynthetic>(s, n, c);
 712   else if (!isa<DefinedCOFF>(s))
 713     reportDuplicate(s, nullptr);
 714   return s;
 715 }
 716
 717 Symbol *SymbolTable::addRegular(InputFile *f, StringRef n,
 718                                 const coff_symbol_generic *sym, SectionChunk *c,
 719                                 uint32_t sectionOffset, bool isWeak) {
 720   auto [s, wasInserted] = insert(n, f);
 721   if (wasInserted || !isa<DefinedRegular>(s) || s->isWeak)
 722     replaceSymbol<DefinedRegular>(s, f, n, /*IsCOMDAT*/ false,
 723                                   /*IsExternal*/ true, sym, c, isWeak);
 724   else if (!isWeak)
 725     reportDuplicate(s, f, c, sectionOffset);
 726   return s;
 727 }
 728
 729 std::pair<DefinedRegular *, bool>
 730 SymbolTable::addComdat(InputFile *f, StringRef n,
 731                        const coff_symbol_generic *sym) {
 732   auto [s, wasInserted] = insert(n, f);
 733   if (wasInserted || !isa<DefinedRegular>(s)) {
 734     replaceSymbol<DefinedRegular>(s, f, n, /*IsCOMDAT*/ true,
 735                                   /*IsExternal*/ true, sym, nullptr);
 736     return {cast<DefinedRegular>(s), true};
 737   }
 738   auto *existingSymbol = cast<DefinedRegular>(s);
 739   if (!existingSymbol->isCOMDAT)
 740     reportDuplicate(s, f);
 741   return {existingSymbol, false};
 742 }
 743
 744 Symbol *SymbolTable::addCommon(InputFile *f, StringRef n, uint64_t size,
 745                                const coff_symbol_generic *sym, CommonChunk *c) {
 746   auto [s, wasInserted] = insert(n, f);
 747   if (wasInserted || !isa<DefinedCOFF>(s))
 748     replaceSymbol<DefinedCommon>(s, f, n, size, sym, c);
 749   else if (auto *dc = dyn_cast<DefinedCommon>(s))
 750     if (size > dc->getSize())
 751       replaceSymbol<DefinedCommon>(s, f, n, size, sym, c);
 752   return s;
 753 }
 754
 755 Symbol *SymbolTable::addImportData(StringRef n, ImportFile *f) {
 756   auto [s, wasInserted] = insert(n, nullptr);
 757   s->isUsedInRegularObj = true;
 758   if (wasInserted || isa<Undefined>(s) || s->isLazy()) {
 759     replaceSymbol<DefinedImportData>(s, n, f);
 760     return s;
 761   }
 762
 763   reportDuplicate(s, f);
 764   return nullptr;
 765 }
 766
 767 Symbol *SymbolTable::addImportThunk(StringRef name, DefinedImportData *id,
 768                                     uint16_t machine) {
 769   auto [s, wasInserted] = insert(name, nullptr);
 770   s->isUsedInRegularObj = true;
 771   if (wasInserted || isa<Undefined>(s) || s->isLazy()) {
 772     replaceSymbol<DefinedImportThunk>(s, ctx, name, id, machine);
 773     return s;
 774   }
 775
 776   reportDuplicate(s, id->file);
 777   return nullptr;
 778 }
 779
 780 void SymbolTable::addLibcall(StringRef name) {
 781   Symbol *sym = findUnderscore(name);
 782   if (!sym)
 783     return;
 784
 785   if (auto *l = dyn_cast<LazyArchive>(sym)) {
 786     MemoryBufferRef mb = l->getMemberBuffer();
 787     if (isBitcode(mb))
 788       addUndefined(sym->getName());
 789   } else if (LazyObject *o = dyn_cast<LazyObject>(sym)) {
 790     if (isBitcode(o->file->mb))
 791       addUndefined(sym->getName());
 792   }
 793 }
 794
 795 std::vector<Chunk *> SymbolTable::getChunks() const {
 796   std::vector<Chunk *> res;
 797   for (ObjFile *file : ctx.objFileInstances) {
 798     ArrayRef<Chunk *> v = file->getChunks();
 799     res.insert(res.end(), v.begin(), v.end());
 800   }
 801   return res;
 802 }
 803
 804 Symbol *SymbolTable::find(StringRef name) const {
 805   return symMap.lookup(CachedHashStringRef(name));
 806 }
 807
 808 Symbol *SymbolTable::findUnderscore(StringRef name) const {
 809   if (ctx.config.machine == I386)
 810     return find(("_" + name).str());
 811   return find(name);
 812 }
 813
 814 // Return all symbols that start with Prefix, possibly ignoring the first
 815 // character of Prefix or the first character symbol.
 816 std::vector<Symbol *> SymbolTable::getSymsWithPrefix(StringRef prefix) {
 817   std::vector<Symbol *> syms;
 818   for (auto pair : symMap) {
 819     StringRef name = pair.first.val();
 820     if (name.starts_with(prefix) || name.starts_with(prefix.drop_front()) ||
 821         name.drop_front().starts_with(prefix) ||
 822         name.drop_front().starts_with(prefix.drop_front())) {
 823       syms.push_back(pair.second);
 824     }
 825   }
 826   return syms;
 827 }
 828
 829 Symbol *SymbolTable::findMangle(StringRef name) {
 830   if (Symbol *sym = find(name)) {
 831     if (auto *u = dyn_cast<Undefined>(sym)) {
 832       // We're specifically looking for weak aliases that ultimately resolve to
 833       // defined symbols, hence the call to getWeakAlias() instead of just using
 834       // the weakAlias member variable. This matches link.exe's behavior.
 835       if (Symbol *weakAlias = u->getWeakAlias())
 836         return weakAlias;
 837     } else {
 838       return sym;
 839     }
 840   }
 841
 842   // Efficient fuzzy string lookup is impossible with a hash table, so iterate
 843   // the symbol table once and collect all possibly matching symbols into this
 844   // vector. Then compare each possibly matching symbol with each possible
 845   // mangling.
 846   std::vector<Symbol *> syms = getSymsWithPrefix(name);
 847   auto findByPrefix = [&syms](const Twine &t) -> Symbol * {
 848     std::string prefix = t.str();
 849     for (auto *s : syms)
 850       if (s->getName().starts_with(prefix))
 851         return s;
 852     return nullptr;
 853   };
 854
 855   // For non-x86, just look for C++ functions.
 856   if (ctx.config.machine != I386)
 857     return findByPrefix("?" + name + "@@Y");
 858
 859   if (!name.starts_with("_"))
 860     return nullptr;
 861   // Search for x86 stdcall function.
 862   if (Symbol *s = findByPrefix(name + "@"))
 863     return s;
 864   // Search for x86 fastcall function.
 865   if (Symbol *s = findByPrefix("@" + name.substr(1) + "@"))
 866     return s;
 867   // Search for x86 vectorcall function.
 868   if (Symbol *s = findByPrefix(name.substr(1) + "@@"))
 869     return s;
 870   // Search for x86 C++ non-member function.
 871   return findByPrefix("?" + name.substr(1) + "@@Y");
 872 }
 873
 874 Symbol *SymbolTable::addUndefined(StringRef name) {
 875   return addUndefined(name, nullptr, false);
 876 }
 877
 878 void SymbolTable::compileBitcodeFiles() {
 879   if (ctx.bitcodeFileInstances.empty())
 880     return;
 881
 882   llvm::TimeTraceScope timeScope("Compile bitcode");
 883   ScopedTimer t(ctx.ltoTimer);
 884   lto.reset(new BitcodeCompiler(ctx));
 885   for (BitcodeFile *f : ctx.bitcodeFileInstances)
 886     lto->add(*f);
 887   for (InputFile *newObj : lto->compile()) {
 888     ObjFile *obj = cast<ObjFile>(newObj);
 889     obj->parse();
 890     ctx.objFileInstances.push_back(obj);
 891   }
 892 }
 893
 894 } // namespace lld::coff