xref: /freebsd/contrib/llvm-project/lld/COFF/SymbolTable.cpp (revision cfd6422a5217410fbd66f7a7a8a64d9d85e61229)
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)
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 
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     inserted = true;
486   }
487   return {sym, inserted};
488 }
489 
490 std::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 
497 Symbol *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 
511 void 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 
527 void 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 
542 static 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 
551 static 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 
568 static 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
586 void 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 
609 Symbol *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 
624 Symbol *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 
639 Symbol *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 
651 Symbol *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 
665 std::pair<DefinedRegular *, bool>
666 SymbolTable::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 
682 Symbol *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 
695 Symbol *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 
709 Symbol *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 
724 void 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 
739 std::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 
748 Symbol *SymbolTable::find(StringRef name) {
749   return symMap.lookup(CachedHashStringRef(name));
750 }
751 
752 Symbol *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.
760 std::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 
773 Symbol *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 
810 Symbol *SymbolTable::addUndefined(StringRef name) {
811   return addUndefined(name, nullptr, false);
812 }
813 
814 void 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