1 //===- SymbolTable.cpp ----------------------------------------------------===//
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "SymbolTable.h"
16 #include "lld/Common/ErrorHandler.h"
17 #include "lld/Common/Memory.h"
18 #include "lld/Common/Timer.h"
19 #include "llvm/IR/LLVMContext.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/raw_ostream.h"
29 static Timer LTOTimer("LTO", Timer::root());
33 void SymbolTable::addFile(InputFile *File) {
34 log("Reading " + toString(File));
37 MachineTypes MT = File->getMachineType();
38 if (Config->Machine == IMAGE_FILE_MACHINE_UNKNOWN) {
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));
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);
54 StringRef S = File->getDirectives();
58 log("Directives: " + toString(File) + ": " + S);
59 Driver->parseDirectives(S);
62 static void errorOrWarn(const Twine &S) {
69 // Returns the name of the symbol in SC whose value is <= Addr that is closest
70 // to Addr. This is generally the name of the global variable or function whose
71 // definition contains Addr.
72 static StringRef getSymbolName(SectionChunk *SC, uint32_t Addr) {
73 DefinedRegular *Candidate = nullptr;
75 for (Symbol *S : SC->File->getSymbols()) {
76 auto *D = dyn_cast_or_null<DefinedRegular>(S);
77 if (!D || D->getChunk() != SC || D->getValue() > Addr ||
78 (Candidate && D->getValue() < Candidate->getValue()))
86 return Candidate->getName();
89 static std::string getSymbolLocations(ObjFile *File, uint32_t SymIndex) {
92 std::pair<StringRef, uint32_t> FileLine;
94 std::vector<Location> Locations;
96 for (Chunk *C : File->getChunks()) {
97 auto *SC = dyn_cast<SectionChunk>(C);
100 for (const coff_relocation &R : SC->Relocs) {
101 if (R.SymbolTableIndex != SymIndex)
103 std::pair<StringRef, uint32_t> FileLine =
104 getFileLine(SC, R.VirtualAddress);
105 StringRef SymName = getSymbolName(SC, R.VirtualAddress);
106 if (!FileLine.first.empty() || !SymName.empty())
107 Locations.push_back({SymName, FileLine});
111 if (Locations.empty())
112 return "\n>>> referenced by " + toString(File) + "\n";
115 llvm::raw_string_ostream OS(Out);
116 for (Location Loc : Locations) {
117 OS << "\n>>> referenced by ";
118 if (!Loc.FileLine.first.empty())
119 OS << Loc.FileLine.first << ":" << Loc.FileLine.second
121 OS << toString(File);
122 if (!Loc.SymName.empty())
123 OS << ":(" << Loc.SymName << ')';
129 void SymbolTable::reportRemainingUndefines() {
130 SmallPtrSet<Symbol *, 8> Undefs;
131 DenseMap<Symbol *, Symbol *> LocalImports;
133 for (auto &I : SymMap) {
134 Symbol *Sym = I.second;
135 auto *Undef = dyn_cast<Undefined>(Sym);
138 if (!Sym->IsUsedInRegularObj)
141 StringRef Name = Undef->getName();
143 // A weak alias may have been resolved, so check for that.
144 if (Defined *D = Undef->getWeakAlias()) {
145 // We want to replace Sym with D. However, we can't just blindly
146 // copy sizeof(SymbolUnion) bytes from D to Sym because D may be an
147 // internal symbol, and internal symbols are stored as "unparented"
148 // Symbols. For that reason we need to check which type of symbol we
149 // are dealing with and copy the correct number of bytes.
150 if (isa<DefinedRegular>(D))
151 memcpy(Sym, D, sizeof(DefinedRegular));
152 else if (isa<DefinedAbsolute>(D))
153 memcpy(Sym, D, sizeof(DefinedAbsolute));
155 memcpy(Sym, D, sizeof(SymbolUnion));
159 // If we can resolve a symbol by removing __imp_ prefix, do that.
160 // This odd rule is for compatibility with MSVC linker.
161 if (Name.startswith("__imp_")) {
162 Symbol *Imp = find(Name.substr(strlen("__imp_")));
163 if (Imp && isa<Defined>(Imp)) {
164 auto *D = cast<Defined>(Imp);
165 replaceSymbol<DefinedLocalImport>(Sym, Name, D);
166 LocalImportChunks.push_back(cast<DefinedLocalImport>(Sym)->getChunk());
167 LocalImports[Sym] = D;
172 // Remaining undefined symbols are not fatal if /force is specified.
173 // They are replaced with dummy defined symbols.
175 replaceSymbol<DefinedAbsolute>(Sym, Name, 0);
179 if (Undefs.empty() && LocalImports.empty())
182 for (Symbol *B : Config->GCRoot) {
184 errorOrWarn("<root>: undefined symbol: " + B->getName());
185 if (Config->WarnLocallyDefinedImported)
186 if (Symbol *Imp = LocalImports.lookup(B))
187 warn("<root>: locally defined symbol imported: " + Imp->getName() +
188 " (defined in " + toString(Imp->getFile()) + ") [LNK4217]");
191 for (ObjFile *File : ObjFile::Instances) {
192 size_t SymIndex = (size_t)-1;
193 for (Symbol *Sym : File->getSymbols()) {
197 if (Undefs.count(Sym))
198 errorOrWarn("undefined symbol: " + Sym->getName() +
199 getSymbolLocations(File, SymIndex));
200 if (Config->WarnLocallyDefinedImported)
201 if (Symbol *Imp = LocalImports.lookup(Sym))
202 warn(toString(File) + ": locally defined symbol imported: " +
203 Imp->getName() + " (defined in " + toString(Imp->getFile()) +
209 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name) {
210 Symbol *&Sym = SymMap[CachedHashStringRef(Name)];
213 Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
214 Sym->IsUsedInRegularObj = false;
215 Sym->PendingArchiveLoad = false;
219 Symbol *SymbolTable::addUndefined(StringRef Name, InputFile *F,
223 std::tie(S, WasInserted) = insert(Name);
224 if (!F || !isa<BitcodeFile>(F))
225 S->IsUsedInRegularObj = true;
226 if (WasInserted || (isa<Lazy>(S) && IsWeakAlias)) {
227 replaceSymbol<Undefined>(S, Name);
230 if (auto *L = dyn_cast<Lazy>(S)) {
231 if (!S->PendingArchiveLoad) {
232 S->PendingArchiveLoad = true;
233 L->File->addMember(&L->Sym);
239 void SymbolTable::addLazy(ArchiveFile *F, const Archive::Symbol Sym) {
240 StringRef Name = Sym.getName();
243 std::tie(S, WasInserted) = insert(Name);
245 replaceSymbol<Lazy>(S, F, Sym);
248 auto *U = dyn_cast<Undefined>(S);
249 if (!U || U->WeakAlias || S->PendingArchiveLoad)
251 S->PendingArchiveLoad = true;
255 void SymbolTable::reportDuplicate(Symbol *Existing, InputFile *NewFile) {
256 error("duplicate symbol: " + toString(*Existing) + " in " +
257 toString(Existing->getFile()) + " and in " + toString(NewFile));
260 Symbol *SymbolTable::addAbsolute(StringRef N, COFFSymbolRef Sym) {
263 std::tie(S, WasInserted) = insert(N);
264 S->IsUsedInRegularObj = true;
265 if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
266 replaceSymbol<DefinedAbsolute>(S, N, Sym);
267 else if (!isa<DefinedCOFF>(S))
268 reportDuplicate(S, nullptr);
272 Symbol *SymbolTable::addAbsolute(StringRef N, uint64_t VA) {
275 std::tie(S, WasInserted) = insert(N);
276 S->IsUsedInRegularObj = true;
277 if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
278 replaceSymbol<DefinedAbsolute>(S, N, VA);
279 else if (!isa<DefinedCOFF>(S))
280 reportDuplicate(S, nullptr);
284 Symbol *SymbolTable::addSynthetic(StringRef N, Chunk *C) {
287 std::tie(S, WasInserted) = insert(N);
288 S->IsUsedInRegularObj = true;
289 if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
290 replaceSymbol<DefinedSynthetic>(S, N, C);
291 else if (!isa<DefinedCOFF>(S))
292 reportDuplicate(S, nullptr);
296 Symbol *SymbolTable::addRegular(InputFile *F, StringRef N,
297 const coff_symbol_generic *Sym,
301 std::tie(S, WasInserted) = insert(N);
302 if (!isa<BitcodeFile>(F))
303 S->IsUsedInRegularObj = true;
304 if (WasInserted || !isa<DefinedRegular>(S))
305 replaceSymbol<DefinedRegular>(S, F, N, /*IsCOMDAT*/ false,
306 /*IsExternal*/ true, Sym, C);
308 reportDuplicate(S, F);
312 std::pair<Symbol *, bool>
313 SymbolTable::addComdat(InputFile *F, StringRef N,
314 const coff_symbol_generic *Sym) {
317 std::tie(S, WasInserted) = insert(N);
318 if (!isa<BitcodeFile>(F))
319 S->IsUsedInRegularObj = true;
320 if (WasInserted || !isa<DefinedRegular>(S)) {
321 replaceSymbol<DefinedRegular>(S, F, N, /*IsCOMDAT*/ true,
322 /*IsExternal*/ true, Sym, nullptr);
325 if (!cast<DefinedRegular>(S)->isCOMDAT())
326 reportDuplicate(S, F);
330 Symbol *SymbolTable::addCommon(InputFile *F, StringRef N, uint64_t Size,
331 const coff_symbol_generic *Sym, CommonChunk *C) {
334 std::tie(S, WasInserted) = insert(N);
335 if (!isa<BitcodeFile>(F))
336 S->IsUsedInRegularObj = true;
337 if (WasInserted || !isa<DefinedCOFF>(S))
338 replaceSymbol<DefinedCommon>(S, F, N, Size, Sym, C);
339 else if (auto *DC = dyn_cast<DefinedCommon>(S))
340 if (Size > DC->getSize())
341 replaceSymbol<DefinedCommon>(S, F, N, Size, Sym, C);
345 Symbol *SymbolTable::addImportData(StringRef N, ImportFile *F) {
348 std::tie(S, WasInserted) = insert(N);
349 S->IsUsedInRegularObj = true;
350 if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S)) {
351 replaceSymbol<DefinedImportData>(S, N, F);
355 reportDuplicate(S, F);
359 Symbol *SymbolTable::addImportThunk(StringRef Name, DefinedImportData *ID,
363 std::tie(S, WasInserted) = insert(Name);
364 S->IsUsedInRegularObj = true;
365 if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S)) {
366 replaceSymbol<DefinedImportThunk>(S, Name, ID, Machine);
370 reportDuplicate(S, ID->File);
374 std::vector<Chunk *> SymbolTable::getChunks() {
375 std::vector<Chunk *> Res;
376 for (ObjFile *File : ObjFile::Instances) {
377 ArrayRef<Chunk *> V = File->getChunks();
378 Res.insert(Res.end(), V.begin(), V.end());
383 Symbol *SymbolTable::find(StringRef Name) {
384 return SymMap.lookup(CachedHashStringRef(Name));
387 Symbol *SymbolTable::findUnderscore(StringRef Name) {
388 if (Config->Machine == I386)
389 return find(("_" + Name).str());
393 StringRef SymbolTable::findByPrefix(StringRef Prefix) {
394 for (auto Pair : SymMap) {
395 StringRef Name = Pair.first.val();
396 if (Name.startswith(Prefix))
402 StringRef SymbolTable::findMangle(StringRef Name) {
403 if (Symbol *Sym = find(Name))
404 if (!isa<Undefined>(Sym))
406 if (Config->Machine != I386)
407 return findByPrefix(("?" + Name + "@@Y").str());
408 if (!Name.startswith("_"))
410 // Search for x86 stdcall function.
411 StringRef S = findByPrefix((Name + "@").str());
414 // Search for x86 fastcall function.
415 S = findByPrefix(("@" + Name.substr(1) + "@").str());
418 // Search for x86 vectorcall function.
419 S = findByPrefix((Name.substr(1) + "@@").str());
422 // Search for x86 C++ non-member function.
423 return findByPrefix(("?" + Name.substr(1) + "@@Y").str());
426 void SymbolTable::mangleMaybe(Symbol *B) {
427 auto *U = dyn_cast<Undefined>(B);
428 if (!U || U->WeakAlias)
430 StringRef Alias = findMangle(U->getName());
431 if (!Alias.empty()) {
432 log(U->getName() + " aliased to " + Alias);
433 U->WeakAlias = addUndefined(Alias);
437 Symbol *SymbolTable::addUndefined(StringRef Name) {
438 return addUndefined(Name, nullptr, false);
441 std::vector<StringRef> SymbolTable::compileBitcodeFiles() {
442 LTO.reset(new BitcodeCompiler);
443 for (BitcodeFile *F : BitcodeFile::Instances)
445 return LTO->compile();
448 void SymbolTable::addCombinedLTOObjects() {
449 if (BitcodeFile::Instances.empty())
452 ScopedTimer T(LTOTimer);
453 for (StringRef Object : compileBitcodeFiles()) {
454 auto *Obj = make<ObjFile>(MemoryBufferRef(Object, "lto.tmp"));
456 ObjFile::Instances.push_back(Obj);