1 //===- SymbolTable.cpp ----------------------------------------------------===//
2 //
3 //                             The LLVM Linker
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "SymbolTable.h"
11 #include "Config.h"
12 #include "Driver.h"
13 #include "LTO.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/Support/Debug.h"
20 #include "llvm/Support/raw_ostream.h"
21 #include <utility>
22 
23 using namespace llvm;
24 
25 namespace lld {
26 namespace coff {
27 
28 static Timer LTOTimer("LTO", Timer::root());
29 
30 SymbolTable *Symtab;
31 
32 void SymbolTable::addFile(InputFile *File) {
33   log("Reading " + toString(File));
34   File->parse();
35 
36   MachineTypes MT = File->getMachineType();
37   if (Config->Machine == IMAGE_FILE_MACHINE_UNKNOWN) {
38     Config->Machine = MT;
39   } else if (MT != IMAGE_FILE_MACHINE_UNKNOWN && Config->Machine != MT) {
40     fatal(toString(File) + ": machine type " + machineToStr(MT) +
41           " conflicts with " + machineToStr(Config->Machine));
42   }
43 
44   if (auto *F = dyn_cast<ObjFile>(File)) {
45     ObjFile::Instances.push_back(F);
46   } else if (auto *F = dyn_cast<BitcodeFile>(File)) {
47     BitcodeFile::Instances.push_back(F);
48   } else if (auto *F = dyn_cast<ImportFile>(File)) {
49     ImportFile::Instances.push_back(F);
50   }
51 
52   StringRef S = File->getDirectives();
53   if (S.empty())
54     return;
55 
56   log("Directives: " + toString(File) + ": " + S);
57   Driver->parseDirectives(S);
58 }
59 
60 static void errorOrWarn(const Twine &S) {
61   if (Config->Force)
62     warn(S);
63   else
64     error(S);
65 }
66 
67 void SymbolTable::reportRemainingUndefines() {
68   SmallPtrSet<Symbol *, 8> Undefs;
69   DenseMap<Symbol *, Symbol *> LocalImports;
70 
71   for (auto &I : SymMap) {
72     Symbol *Sym = I.second;
73     auto *Undef = dyn_cast<Undefined>(Sym);
74     if (!Undef)
75       continue;
76     if (!Sym->IsUsedInRegularObj)
77       continue;
78 
79     StringRef Name = Undef->getName();
80 
81     // A weak alias may have been resolved, so check for that.
82     if (Defined *D = Undef->getWeakAlias()) {
83       // We want to replace Sym with D. However, we can't just blindly
84       // copy sizeof(SymbolUnion) bytes from D to Sym because D may be an
85       // internal symbol, and internal symbols are stored as "unparented"
86       // Symbols. For that reason we need to check which type of symbol we
87       // are dealing with and copy the correct number of bytes.
88       if (isa<DefinedRegular>(D))
89         memcpy(Sym, D, sizeof(DefinedRegular));
90       else if (isa<DefinedAbsolute>(D))
91         memcpy(Sym, D, sizeof(DefinedAbsolute));
92       else
93         memcpy(Sym, D, sizeof(SymbolUnion));
94       continue;
95     }
96 
97     // If we can resolve a symbol by removing __imp_ prefix, do that.
98     // This odd rule is for compatibility with MSVC linker.
99     if (Name.startswith("__imp_")) {
100       Symbol *Imp = find(Name.substr(strlen("__imp_")));
101       if (Imp && isa<Defined>(Imp)) {
102         auto *D = cast<Defined>(Imp);
103         replaceSymbol<DefinedLocalImport>(Sym, Name, D);
104         LocalImportChunks.push_back(cast<DefinedLocalImport>(Sym)->getChunk());
105         LocalImports[Sym] = D;
106         continue;
107       }
108     }
109 
110     // Remaining undefined symbols are not fatal if /force is specified.
111     // They are replaced with dummy defined symbols.
112     if (Config->Force)
113       replaceSymbol<DefinedAbsolute>(Sym, Name, 0);
114     Undefs.insert(Sym);
115   }
116 
117   if (Undefs.empty() && LocalImports.empty())
118     return;
119 
120   for (Symbol *B : Config->GCRoot) {
121     if (Undefs.count(B))
122       errorOrWarn("<root>: undefined symbol: " + B->getName());
123     if (Config->WarnLocallyDefinedImported)
124       if (Symbol *Imp = LocalImports.lookup(B))
125         warn("<root>: locally defined symbol imported: " + Imp->getName() +
126              " (defined in " + toString(Imp->getFile()) + ") [LNK4217]");
127   }
128 
129   for (ObjFile *File : ObjFile::Instances) {
130     for (Symbol *Sym : File->getSymbols()) {
131       if (!Sym)
132         continue;
133       if (Undefs.count(Sym))
134         errorOrWarn(toString(File) + ": undefined symbol: " + Sym->getName());
135       if (Config->WarnLocallyDefinedImported)
136         if (Symbol *Imp = LocalImports.lookup(Sym))
137           warn(toString(File) + ": locally defined symbol imported: " +
138                Imp->getName() + " (defined in " + toString(Imp->getFile()) +
139                ") [LNK4217]");
140     }
141   }
142 }
143 
144 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name) {
145   Symbol *&Sym = SymMap[CachedHashStringRef(Name)];
146   if (Sym)
147     return {Sym, false};
148   Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
149   Sym->IsUsedInRegularObj = false;
150   Sym->PendingArchiveLoad = false;
151   return {Sym, true};
152 }
153 
154 Symbol *SymbolTable::addUndefined(StringRef Name, InputFile *F,
155                                   bool IsWeakAlias) {
156   Symbol *S;
157   bool WasInserted;
158   std::tie(S, WasInserted) = insert(Name);
159   if (!F || !isa<BitcodeFile>(F))
160     S->IsUsedInRegularObj = true;
161   if (WasInserted || (isa<Lazy>(S) && IsWeakAlias)) {
162     replaceSymbol<Undefined>(S, Name);
163     return S;
164   }
165   if (auto *L = dyn_cast<Lazy>(S)) {
166     if (!S->PendingArchiveLoad) {
167       S->PendingArchiveLoad = true;
168       L->File->addMember(&L->Sym);
169     }
170   }
171   return S;
172 }
173 
174 void SymbolTable::addLazy(ArchiveFile *F, const Archive::Symbol Sym) {
175   StringRef Name = Sym.getName();
176   Symbol *S;
177   bool WasInserted;
178   std::tie(S, WasInserted) = insert(Name);
179   if (WasInserted) {
180     replaceSymbol<Lazy>(S, F, Sym);
181     return;
182   }
183   auto *U = dyn_cast<Undefined>(S);
184   if (!U || U->WeakAlias || S->PendingArchiveLoad)
185     return;
186   S->PendingArchiveLoad = true;
187   F->addMember(&Sym);
188 }
189 
190 void SymbolTable::reportDuplicate(Symbol *Existing, InputFile *NewFile) {
191   error("duplicate symbol: " + toString(*Existing) + " in " +
192         toString(Existing->getFile()) + " and in " + toString(NewFile));
193 }
194 
195 Symbol *SymbolTable::addAbsolute(StringRef N, COFFSymbolRef Sym) {
196   Symbol *S;
197   bool WasInserted;
198   std::tie(S, WasInserted) = insert(N);
199   S->IsUsedInRegularObj = true;
200   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
201     replaceSymbol<DefinedAbsolute>(S, N, Sym);
202   else if (!isa<DefinedCOFF>(S))
203     reportDuplicate(S, nullptr);
204   return S;
205 }
206 
207 Symbol *SymbolTable::addAbsolute(StringRef N, uint64_t VA) {
208   Symbol *S;
209   bool WasInserted;
210   std::tie(S, WasInserted) = insert(N);
211   S->IsUsedInRegularObj = true;
212   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
213     replaceSymbol<DefinedAbsolute>(S, N, VA);
214   else if (!isa<DefinedCOFF>(S))
215     reportDuplicate(S, nullptr);
216   return S;
217 }
218 
219 Symbol *SymbolTable::addSynthetic(StringRef N, Chunk *C) {
220   Symbol *S;
221   bool WasInserted;
222   std::tie(S, WasInserted) = insert(N);
223   S->IsUsedInRegularObj = true;
224   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S))
225     replaceSymbol<DefinedSynthetic>(S, N, C);
226   else if (!isa<DefinedCOFF>(S))
227     reportDuplicate(S, nullptr);
228   return S;
229 }
230 
231 Symbol *SymbolTable::addRegular(InputFile *F, StringRef N,
232                                 const coff_symbol_generic *Sym,
233                                 SectionChunk *C) {
234   Symbol *S;
235   bool WasInserted;
236   std::tie(S, WasInserted) = insert(N);
237   if (!isa<BitcodeFile>(F))
238     S->IsUsedInRegularObj = true;
239   if (WasInserted || !isa<DefinedRegular>(S))
240     replaceSymbol<DefinedRegular>(S, F, N, /*IsCOMDAT*/ false,
241                                   /*IsExternal*/ true, Sym, C);
242   else
243     reportDuplicate(S, F);
244   return S;
245 }
246 
247 std::pair<Symbol *, bool>
248 SymbolTable::addComdat(InputFile *F, StringRef N,
249                        const coff_symbol_generic *Sym) {
250   Symbol *S;
251   bool WasInserted;
252   std::tie(S, WasInserted) = insert(N);
253   if (!isa<BitcodeFile>(F))
254     S->IsUsedInRegularObj = true;
255   if (WasInserted || !isa<DefinedRegular>(S)) {
256     replaceSymbol<DefinedRegular>(S, F, N, /*IsCOMDAT*/ true,
257                                   /*IsExternal*/ true, Sym, nullptr);
258     return {S, true};
259   }
260   if (!cast<DefinedRegular>(S)->isCOMDAT())
261     reportDuplicate(S, F);
262   return {S, false};
263 }
264 
265 Symbol *SymbolTable::addCommon(InputFile *F, StringRef N, uint64_t Size,
266                                const coff_symbol_generic *Sym, CommonChunk *C) {
267   Symbol *S;
268   bool WasInserted;
269   std::tie(S, WasInserted) = insert(N);
270   if (!isa<BitcodeFile>(F))
271     S->IsUsedInRegularObj = true;
272   if (WasInserted || !isa<DefinedCOFF>(S))
273     replaceSymbol<DefinedCommon>(S, F, N, Size, Sym, C);
274   else if (auto *DC = dyn_cast<DefinedCommon>(S))
275     if (Size > DC->getSize())
276       replaceSymbol<DefinedCommon>(S, F, N, Size, Sym, C);
277   return S;
278 }
279 
280 DefinedImportData *SymbolTable::addImportData(StringRef N, ImportFile *F) {
281   Symbol *S;
282   bool WasInserted;
283   std::tie(S, WasInserted) = insert(N);
284   S->IsUsedInRegularObj = true;
285   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S)) {
286     replaceSymbol<DefinedImportData>(S, N, F);
287     return cast<DefinedImportData>(S);
288   }
289 
290   reportDuplicate(S, F);
291   return nullptr;
292 }
293 
294 DefinedImportThunk *SymbolTable::addImportThunk(StringRef Name,
295                                                DefinedImportData *ID,
296                                                uint16_t Machine) {
297   Symbol *S;
298   bool WasInserted;
299   std::tie(S, WasInserted) = insert(Name);
300   S->IsUsedInRegularObj = true;
301   if (WasInserted || isa<Undefined>(S) || isa<Lazy>(S)) {
302     replaceSymbol<DefinedImportThunk>(S, Name, ID, Machine);
303     return cast<DefinedImportThunk>(S);
304   }
305 
306   reportDuplicate(S, ID->File);
307   return nullptr;
308 }
309 
310 std::vector<Chunk *> SymbolTable::getChunks() {
311   std::vector<Chunk *> Res;
312   for (ObjFile *File : ObjFile::Instances) {
313     ArrayRef<Chunk *> V = File->getChunks();
314     Res.insert(Res.end(), V.begin(), V.end());
315   }
316   return Res;
317 }
318 
319 Symbol *SymbolTable::find(StringRef Name) {
320   return SymMap.lookup(CachedHashStringRef(Name));
321 }
322 
323 Symbol *SymbolTable::findUnderscore(StringRef Name) {
324   if (Config->Machine == I386)
325     return find(("_" + Name).str());
326   return find(Name);
327 }
328 
329 StringRef SymbolTable::findByPrefix(StringRef Prefix) {
330   for (auto Pair : SymMap) {
331     StringRef Name = Pair.first.val();
332     if (Name.startswith(Prefix))
333       return Name;
334   }
335   return "";
336 }
337 
338 StringRef SymbolTable::findMangle(StringRef Name) {
339   if (Symbol *Sym = find(Name))
340     if (!isa<Undefined>(Sym))
341       return Name;
342   if (Config->Machine != I386)
343     return findByPrefix(("?" + Name + "@@Y").str());
344   if (!Name.startswith("_"))
345     return "";
346   // Search for x86 stdcall function.
347   StringRef S = findByPrefix((Name + "@").str());
348   if (!S.empty())
349     return S;
350   // Search for x86 fastcall function.
351   S = findByPrefix(("@" + Name.substr(1) + "@").str());
352   if (!S.empty())
353     return S;
354   // Search for x86 vectorcall function.
355   S = findByPrefix((Name.substr(1) + "@@").str());
356   if (!S.empty())
357     return S;
358   // Search for x86 C++ non-member function.
359   return findByPrefix(("?" + Name.substr(1) + "@@Y").str());
360 }
361 
362 void SymbolTable::mangleMaybe(Symbol *B) {
363   auto *U = dyn_cast<Undefined>(B);
364   if (!U || U->WeakAlias)
365     return;
366   StringRef Alias = findMangle(U->getName());
367   if (!Alias.empty()) {
368     log(U->getName() + " aliased to " + Alias);
369     U->WeakAlias = addUndefined(Alias);
370   }
371 }
372 
373 Symbol *SymbolTable::addUndefined(StringRef Name) {
374   return addUndefined(Name, nullptr, false);
375 }
376 
377 std::vector<StringRef> SymbolTable::compileBitcodeFiles() {
378   LTO.reset(new BitcodeCompiler);
379   for (BitcodeFile *F : BitcodeFile::Instances)
380     LTO->add(*F);
381   return LTO->compile();
382 }
383 
384 void SymbolTable::addCombinedLTOObjects() {
385   if (BitcodeFile::Instances.empty())
386     return;
387 
388   ScopedTimer T(LTOTimer);
389   for (StringRef Object : compileBitcodeFiles()) {
390     auto *Obj = make<ObjFile>(MemoryBufferRef(Object, "lto.tmp"));
391     Obj->parse();
392     ObjFile::Instances.push_back(Obj);
393   }
394 }
395 
396 } // namespace coff
397 } // namespace lld
398