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.
139// Returns up to maxStrings string descriptions, along with the total number of
140// locations found.
141static std::pair<std::vector<std::string>, size_t>
142getSymbolLocations(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
193std::vector<std::string> getSymbolLocations(ObjFile *file, uint32_t symIndex) {
194  return getSymbolLocations(file, symIndex, SIZE_MAX).first;
195}
196
197static std::pair<std::vector<std::string>, size_t>
198getSymbolLocations(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.
214struct UndefinedDiag {
215  Symbol *sym;
216  struct File {
217    InputFile *file;
218    uint32_t symIndex;
219  };
220  std::vector<File> files;
221};
222
223static 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
247void 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
272Defined *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
278bool 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.
331static void
332reportProblemSymbols(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
388void 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)
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->mingw && impSymbol(name))
406      continue;
407    undefs.insert(sym);
408  }
409
410  reportProblemSymbols(undefs,
411                       /* localImports */ nullptr, ObjFile::instances,
412                       &BitcodeFile::instances);
413}
414
415void 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
478std::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    inserted = true;
486  }
487  return {sym, inserted};
488}
489
490std::pair<Symbol *, bool> SymbolTable::insert(StringRef name, InputFile *file) {
491  std::pair<Symbol *, bool> result = insert(name);
492  if (!file || !isa<BitcodeFile>(file))
493    result.first->isUsedInRegularObj = true;
494  return result;
495}
496
497Symbol *SymbolTable::addUndefined(StringRef name, InputFile *f,
498                                  bool isWeakAlias) {
499  Symbol *s;
500  bool wasInserted;
501  std::tie(s, wasInserted) = insert(name, f);
502  if (wasInserted || (s->isLazy() && isWeakAlias)) {
503    replaceSymbol<Undefined>(s, name);
504    return s;
505  }
506  if (s->isLazy())
507    forceLazy(s);
508  return s;
509}
510
511void SymbolTable::addLazyArchive(ArchiveFile *f, const Archive::Symbol &sym) {
512  StringRef name = sym.getName();
513  Symbol *s;
514  bool wasInserted;
515  std::tie(s, wasInserted) = insert(name);
516  if (wasInserted) {
517    replaceSymbol<LazyArchive>(s, f, sym);
518    return;
519  }
520  auto *u = dyn_cast<Undefined>(s);
521  if (!u || u->weakAlias || s->pendingArchiveLoad)
522    return;
523  s->pendingArchiveLoad = true;
524  f->addMember(sym);
525}
526
527void SymbolTable::addLazyObject(LazyObjFile *f, StringRef n) {
528  Symbol *s;
529  bool wasInserted;
530  std::tie(s, wasInserted) = insert(n, f);
531  if (wasInserted) {
532    replaceSymbol<LazyObject>(s, f, n);
533    return;
534  }
535  auto *u = dyn_cast<Undefined>(s);
536  if (!u || u->weakAlias || s->pendingArchiveLoad)
537    return;
538  s->pendingArchiveLoad = true;
539  f->fetch();
540}
541
542static std::string getSourceLocationBitcode(BitcodeFile *file) {
543  std::string res("\n>>> defined at ");
544  StringRef source = file->obj->getSourceFileName();
545  if (!source.empty())
546    res += source.str() + "\n>>>            ";
547  res += toString(file);
548  return res;
549}
550
551static std::string getSourceLocationObj(ObjFile *file, SectionChunk *sc,
552                                        uint32_t offset, StringRef name) {
553  Optional<std::pair<StringRef, uint32_t>> fileLine;
554  if (sc)
555    fileLine = getFileLine(sc, offset);
556  if (!fileLine)
557    fileLine = file->getVariableLocation(name);
558
559  std::string res;
560  llvm::raw_string_ostream os(res);
561  os << "\n>>> defined at ";
562  if (fileLine)
563    os << fileLine->first << ":" << fileLine->second << "\n>>>            ";
564  os << toString(file);
565  return os.str();
566}
567
568static std::string getSourceLocation(InputFile *file, SectionChunk *sc,
569                                     uint32_t offset, StringRef name) {
570  if (!file)
571    return "";
572  if (auto *o = dyn_cast<ObjFile>(file))
573    return getSourceLocationObj(o, sc, offset, name);
574  if (auto *b = dyn_cast<BitcodeFile>(file))
575    return getSourceLocationBitcode(b);
576  return "\n>>> defined at " + toString(file);
577}
578
579// Construct and print an error message in the form of:
580//
581//   lld-link: error: duplicate symbol: foo
582//   >>> defined at bar.c:30
583//   >>>            bar.o
584//   >>> defined at baz.c:563
585//   >>>            baz.o
586void SymbolTable::reportDuplicate(Symbol *existing, InputFile *newFile,
587                                  SectionChunk *newSc,
588                                  uint32_t newSectionOffset) {
589  std::string msg;
590  llvm::raw_string_ostream os(msg);
591  os << "duplicate symbol: " << toString(*existing);
592
593  DefinedRegular *d = dyn_cast<DefinedRegular>(existing);
594  if (d && isa<ObjFile>(d->getFile())) {
595    os << getSourceLocation(d->getFile(), d->getChunk(), d->getValue(),
596                            existing->getName());
597  } else {
598    os << getSourceLocation(existing->getFile(), nullptr, 0, "");
599  }
600  os << getSourceLocation(newFile, newSc, newSectionOffset,
601                          existing->getName());
602
603  if (config->forceMultiple)
604    warn(os.str());
605  else
606    error(os.str());
607}
608
609Symbol *SymbolTable::addAbsolute(StringRef n, COFFSymbolRef sym) {
610  Symbol *s;
611  bool wasInserted;
612  std::tie(s, wasInserted) = insert(n, nullptr);
613  s->isUsedInRegularObj = true;
614  if (wasInserted || isa<Undefined>(s) || s->isLazy())
615    replaceSymbol<DefinedAbsolute>(s, n, sym);
616  else if (auto *da = dyn_cast<DefinedAbsolute>(s)) {
617    if (da->getVA() != sym.getValue())
618      reportDuplicate(s, nullptr);
619  } else if (!isa<DefinedCOFF>(s))
620    reportDuplicate(s, nullptr);
621  return s;
622}
623
624Symbol *SymbolTable::addAbsolute(StringRef n, uint64_t va) {
625  Symbol *s;
626  bool wasInserted;
627  std::tie(s, wasInserted) = insert(n, nullptr);
628  s->isUsedInRegularObj = true;
629  if (wasInserted || isa<Undefined>(s) || s->isLazy())
630    replaceSymbol<DefinedAbsolute>(s, n, va);
631  else if (auto *da = dyn_cast<DefinedAbsolute>(s)) {
632    if (da->getVA() != va)
633      reportDuplicate(s, nullptr);
634  } else if (!isa<DefinedCOFF>(s))
635    reportDuplicate(s, nullptr);
636  return s;
637}
638
639Symbol *SymbolTable::addSynthetic(StringRef n, Chunk *c) {
640  Symbol *s;
641  bool wasInserted;
642  std::tie(s, wasInserted) = insert(n, nullptr);
643  s->isUsedInRegularObj = true;
644  if (wasInserted || isa<Undefined>(s) || s->isLazy())
645    replaceSymbol<DefinedSynthetic>(s, n, c);
646  else if (!isa<DefinedCOFF>(s))
647    reportDuplicate(s, nullptr);
648  return s;
649}
650
651Symbol *SymbolTable::addRegular(InputFile *f, StringRef n,
652                                const coff_symbol_generic *sym, SectionChunk *c,
653                                uint32_t sectionOffset) {
654  Symbol *s;
655  bool wasInserted;
656  std::tie(s, wasInserted) = insert(n, f);
657  if (wasInserted || !isa<DefinedRegular>(s))
658    replaceSymbol<DefinedRegular>(s, f, n, /*IsCOMDAT*/ false,
659                                  /*IsExternal*/ true, sym, c);
660  else
661    reportDuplicate(s, f, c, sectionOffset);
662  return s;
663}
664
665std::pair<DefinedRegular *, bool>
666SymbolTable::addComdat(InputFile *f, StringRef n,
667                       const coff_symbol_generic *sym) {
668  Symbol *s;
669  bool wasInserted;
670  std::tie(s, wasInserted) = insert(n, f);
671  if (wasInserted || !isa<DefinedRegular>(s)) {
672    replaceSymbol<DefinedRegular>(s, f, n, /*IsCOMDAT*/ true,
673                                  /*IsExternal*/ true, sym, nullptr);
674    return {cast<DefinedRegular>(s), true};
675  }
676  auto *existingSymbol = cast<DefinedRegular>(s);
677  if (!existingSymbol->isCOMDAT)
678    reportDuplicate(s, f);
679  return {existingSymbol, false};
680}
681
682Symbol *SymbolTable::addCommon(InputFile *f, StringRef n, uint64_t size,
683                               const coff_symbol_generic *sym, CommonChunk *c) {
684  Symbol *s;
685  bool wasInserted;
686  std::tie(s, wasInserted) = insert(n, f);
687  if (wasInserted || !isa<DefinedCOFF>(s))
688    replaceSymbol<DefinedCommon>(s, f, n, size, sym, c);
689  else if (auto *dc = dyn_cast<DefinedCommon>(s))
690    if (size > dc->getSize())
691      replaceSymbol<DefinedCommon>(s, f, n, size, sym, c);
692  return s;
693}
694
695Symbol *SymbolTable::addImportData(StringRef n, ImportFile *f) {
696  Symbol *s;
697  bool wasInserted;
698  std::tie(s, wasInserted) = insert(n, nullptr);
699  s->isUsedInRegularObj = true;
700  if (wasInserted || isa<Undefined>(s) || s->isLazy()) {
701    replaceSymbol<DefinedImportData>(s, n, f);
702    return s;
703  }
704
705  reportDuplicate(s, f);
706  return nullptr;
707}
708
709Symbol *SymbolTable::addImportThunk(StringRef name, DefinedImportData *id,
710                                    uint16_t machine) {
711  Symbol *s;
712  bool wasInserted;
713  std::tie(s, wasInserted) = insert(name, nullptr);
714  s->isUsedInRegularObj = true;
715  if (wasInserted || isa<Undefined>(s) || s->isLazy()) {
716    replaceSymbol<DefinedImportThunk>(s, name, id, machine);
717    return s;
718  }
719
720  reportDuplicate(s, id->file);
721  return nullptr;
722}
723
724void SymbolTable::addLibcall(StringRef name) {
725  Symbol *sym = findUnderscore(name);
726  if (!sym)
727    return;
728
729  if (auto *l = dyn_cast<LazyArchive>(sym)) {
730    MemoryBufferRef mb = l->getMemberBuffer();
731    if (isBitcode(mb))
732      addUndefined(sym->getName());
733  } else if (LazyObject *o = dyn_cast<LazyObject>(sym)) {
734    if (isBitcode(o->file->mb))
735      addUndefined(sym->getName());
736  }
737}
738
739std::vector<Chunk *> SymbolTable::getChunks() {
740  std::vector<Chunk *> res;
741  for (ObjFile *file : ObjFile::instances) {
742    ArrayRef<Chunk *> v = file->getChunks();
743    res.insert(res.end(), v.begin(), v.end());
744  }
745  return res;
746}
747
748Symbol *SymbolTable::find(StringRef name) {
749  return symMap.lookup(CachedHashStringRef(name));
750}
751
752Symbol *SymbolTable::findUnderscore(StringRef name) {
753  if (config->machine == I386)
754    return find(("_" + name).str());
755  return find(name);
756}
757
758// Return all symbols that start with Prefix, possibly ignoring the first
759// character of Prefix or the first character symbol.
760std::vector<Symbol *> SymbolTable::getSymsWithPrefix(StringRef prefix) {
761  std::vector<Symbol *> syms;
762  for (auto pair : symMap) {
763    StringRef name = pair.first.val();
764    if (name.startswith(prefix) || name.startswith(prefix.drop_front()) ||
765        name.drop_front().startswith(prefix) ||
766        name.drop_front().startswith(prefix.drop_front())) {
767      syms.push_back(pair.second);
768    }
769  }
770  return syms;
771}
772
773Symbol *SymbolTable::findMangle(StringRef name) {
774  if (Symbol *sym = find(name))
775    if (!isa<Undefined>(sym))
776      return sym;
777
778  // Efficient fuzzy string lookup is impossible with a hash table, so iterate
779  // the symbol table once and collect all possibly matching symbols into this
780  // vector. Then compare each possibly matching symbol with each possible
781  // mangling.
782  std::vector<Symbol *> syms = getSymsWithPrefix(name);
783  auto findByPrefix = [&syms](const Twine &t) -> Symbol * {
784    std::string prefix = t.str();
785    for (auto *s : syms)
786      if (s->getName().startswith(prefix))
787        return s;
788    return nullptr;
789  };
790
791  // For non-x86, just look for C++ functions.
792  if (config->machine != I386)
793    return findByPrefix("?" + name + "@@Y");
794
795  if (!name.startswith("_"))
796    return nullptr;
797  // Search for x86 stdcall function.
798  if (Symbol *s = findByPrefix(name + "@"))
799    return s;
800  // Search for x86 fastcall function.
801  if (Symbol *s = findByPrefix("@" + name.substr(1) + "@"))
802    return s;
803  // Search for x86 vectorcall function.
804  if (Symbol *s = findByPrefix(name.substr(1) + "@@"))
805    return s;
806  // Search for x86 C++ non-member function.
807  return findByPrefix("?" + name.substr(1) + "@@Y");
808}
809
810Symbol *SymbolTable::addUndefined(StringRef name) {
811  return addUndefined(name, nullptr, false);
812}
813
814void SymbolTable::addCombinedLTOObjects() {
815  if (BitcodeFile::instances.empty())
816    return;
817
818  ScopedTimer t(ltoTimer);
819  lto.reset(new BitcodeCompiler);
820  for (BitcodeFile *f : BitcodeFile::instances)
821    lto->add(*f);
822  for (InputFile *newObj : lto->compile()) {
823    ObjFile *obj = cast<ObjFile>(newObj);
824    obj->parse();
825    ObjFile::instances.push_back(obj);
826  }
827}
828
829} // namespace coff
830} // namespace lld
831