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