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