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