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