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