blob: 35ceed6d2a935062c79e371a9f6f72e8c636609e [file] [log] [blame]
Sam Cleggc94d3932017-11-17 18:14:09 +00001//===- SymbolTable.cpp ----------------------------------------------------===//
2//
Chandler Carruth2946cd72019-01-19 08:50:56 +00003// 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
Sam Cleggc94d3932017-11-17 18:14:09 +00006//
7//===----------------------------------------------------------------------===//
8
9#include "SymbolTable.h"
Sam Cleggc94d3932017-11-17 18:14:09 +000010#include "Config.h"
Sam Clegg5fa274b2018-01-10 01:13:34 +000011#include "InputChunks.h"
Heejin Ahne915a712018-12-08 06:17:43 +000012#include "InputEvent.h"
Sam Clegg93102972018-02-23 05:08:53 +000013#include "InputGlobal.h"
Sam Cleggb8621592017-11-30 01:40:08 +000014#include "WriterUtils.h"
Sam Cleggc94d3932017-11-17 18:14:09 +000015#include "lld/Common/ErrorHandler.h"
Rui Ueyama2017d522017-11-28 20:39:17 +000016#include "lld/Common/Memory.h"
Rui Ueyama7d67dd12018-02-13 22:30:52 +000017#include "llvm/ADT/SetVector.h"
Sam Cleggc94d3932017-11-17 18:14:09 +000018
19#define DEBUG_TYPE "lld"
20
21using namespace llvm;
Sam Clegg20db3812018-01-10 00:52:20 +000022using namespace llvm::wasm;
Sam Clegg45218f42018-11-27 01:08:16 +000023using namespace llvm::object;
Sam Cleggc94d3932017-11-17 18:14:09 +000024using namespace lld;
25using namespace lld::wasm;
26
27SymbolTable *lld::wasm::Symtab;
28
29void SymbolTable::addFile(InputFile *File) {
30 log("Processing: " + toString(File));
Sam Clegga282a612019-06-05 17:50:45 +000031
32 // .a file
33 if (auto *F = dyn_cast<ArchiveFile>(File)) {
34 F->parse();
35 return;
36 }
37
38 // .so file
39 if (auto *F = dyn_cast<SharedFile>(File)) {
40 SharedFiles.push_back(F);
41 return;
42 }
43
Sam Clegg1f3f7742019-02-06 02:35:18 +000044 if (Config->Trace)
45 message(toString(File));
Sam Cleggc94d3932017-11-17 18:14:09 +000046
Sam Cleggc729c1b2018-05-30 18:07:52 +000047 // LLVM bitcode file
Sam Clegga282a612019-06-05 17:50:45 +000048 if (auto *F = dyn_cast<BitcodeFile>(File)) {
49 F->parse();
Sam Cleggc729c1b2018-05-30 18:07:52 +000050 BitcodeFiles.push_back(F);
Sam Clegga282a612019-06-05 17:50:45 +000051 return;
52 }
53
54 // Regular object file
55 auto *F = cast<ObjFile>(File);
56 F->parse(false);
57 ObjectFiles.push_back(F);
Sam Cleggc94d3932017-11-17 18:14:09 +000058}
59
Sam Cleggc729c1b2018-05-30 18:07:52 +000060// This function is where all the optimizations of link-time
61// optimization happens. When LTO is in use, some input files are
62// not in native object file format but in the LLVM bitcode format.
63// This function compiles bitcode files into a few big native files
64// using LLVM functions and replaces bitcode symbols with the results.
65// Because all bitcode files that the program consists of are passed
66// to the compiler at once, it can do whole-program optimization.
67void SymbolTable::addCombinedLTOObject() {
68 if (BitcodeFiles.empty())
69 return;
70
71 // Compile bitcode files and replace bitcode symbols.
72 LTO.reset(new BitcodeCompiler);
73 for (BitcodeFile *F : BitcodeFiles)
74 LTO->add(*F);
75
76 for (StringRef Filename : LTO->compile()) {
Sam Clegg0cfaa242019-04-09 05:41:52 +000077 auto *Obj = make<ObjFile>(MemoryBufferRef(Filename, "lto.tmp"), "");
Sam Clegg697f2142019-05-15 16:03:28 +000078 Obj->parse(true);
Sam Cleggc729c1b2018-05-30 18:07:52 +000079 ObjectFiles.push_back(Obj);
80 }
81}
82
Sam Cleggc94d3932017-11-17 18:14:09 +000083Symbol *SymbolTable::find(StringRef Name) {
Sam Clegg1f3f7742019-02-06 02:35:18 +000084 auto It = SymMap.find(CachedHashStringRef(Name));
85 if (It == SymMap.end() || It->second == -1)
86 return nullptr;
87 return SymVector[It->second];
88}
89
Sam Clegg6540e572019-02-20 23:19:31 +000090void SymbolTable::replace(StringRef Name, Symbol* Sym) {
91 auto It = SymMap.find(CachedHashStringRef(Name));
92 SymVector[It->second] = Sym;
93}
94
Sam Clegg1f3f7742019-02-06 02:35:18 +000095std::pair<Symbol *, bool> SymbolTable::insertName(StringRef Name) {
96 bool Trace = false;
97 auto P = SymMap.insert({CachedHashStringRef(Name), (int)SymVector.size()});
98 int &SymIndex = P.first->second;
99 bool IsNew = P.second;
100 if (SymIndex == -1) {
101 SymIndex = SymVector.size();
102 Trace = true;
103 IsNew = true;
104 }
105
106 if (!IsNew)
107 return {SymVector[SymIndex], false};
108
109 Symbol *Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
110 Sym->IsUsedInRegularObj = false;
Sam Clegga5ca34e2019-05-24 14:14:25 +0000111 Sym->CanInline = true;
Sam Clegg1f3f7742019-02-06 02:35:18 +0000112 Sym->Traced = Trace;
113 SymVector.emplace_back(Sym);
114 return {Sym, true};
Sam Cleggc94d3932017-11-17 18:14:09 +0000115}
116
Sam Clegg230dc112019-02-07 22:42:16 +0000117std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name,
118 const InputFile *File) {
Sam Clegg1f3f7742019-02-06 02:35:18 +0000119 Symbol *S;
120 bool WasInserted;
121 std::tie(S, WasInserted) = insertName(Name);
122
Sam Clegg4c2cbfe2018-08-02 20:39:19 +0000123 if (!File || File->kind() == InputFile::ObjectKind)
Sam Clegg1f3f7742019-02-06 02:35:18 +0000124 S->IsUsedInRegularObj = true;
125
126 return {S, WasInserted};
Sam Cleggc94d3932017-11-17 18:14:09 +0000127}
128
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000129static void reportTypeError(const Symbol *Existing, const InputFile *File,
Sam Clegg3876d89a2018-05-14 22:42:33 +0000130 llvm::wasm::WasmSymbolType Type) {
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000131 error("symbol type mismatch: " + toString(*Existing) + "\n>>> defined as " +
132 toString(Existing->getWasmType()) + " in " +
Sam Clegg3876d89a2018-05-14 22:42:33 +0000133 toString(Existing->getFile()) + "\n>>> defined as " + toString(Type) +
134 " in " + toString(File));
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000135}
136
Heejin Ahn6f4286f2018-11-19 23:31:28 +0000137// Check the type of new symbol matches that of the symbol is replacing.
Sam Clegg6540e572019-02-20 23:19:31 +0000138// Returns true if the function types match, false is there is a singature
139// mismatch.
Benjamin Kramerba2ea932019-03-28 17:18:42 +0000140static bool signatureMatches(FunctionSymbol *Existing,
141 const WasmSignature *NewSig) {
Sam Clegg6540e572019-02-20 23:19:31 +0000142 const WasmSignature *OldSig = Existing->Signature;
Sam Cleggd506b0a2019-05-29 15:36:42 +0000143
144 // If either function is missing a signature (this happend for bitcode
145 // symbols) then assume they match. Any mismatch will be reported later
146 // when the LTO objects are added.
147 if (!NewSig || !OldSig)
Sam Clegg6540e572019-02-20 23:19:31 +0000148 return true;
Sam Cleggcefbf9a2018-06-28 16:53:53 +0000149
Sam Clegg6540e572019-02-20 23:19:31 +0000150 return *NewSig == *OldSig;
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000151}
152
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000153static void checkGlobalType(const Symbol *Existing, const InputFile *File,
154 const WasmGlobalType *NewType) {
155 if (!isa<GlobalSymbol>(Existing)) {
Sam Clegg3876d89a2018-05-14 22:42:33 +0000156 reportTypeError(Existing, File, WASM_SYMBOL_TYPE_GLOBAL);
Sam Cleggb8621592017-11-30 01:40:08 +0000157 return;
158 }
159
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000160 const WasmGlobalType *OldType = cast<GlobalSymbol>(Existing)->getGlobalType();
161 if (*NewType != *OldType) {
162 error("Global type mismatch: " + Existing->getName() + "\n>>> defined as " +
163 toString(*OldType) + " in " + toString(Existing->getFile()) +
164 "\n>>> defined as " + toString(*NewType) + " in " + toString(File));
Sam Clegg93102972018-02-23 05:08:53 +0000165 }
Sam Clegg24b3dcd2018-01-28 19:57:01 +0000166}
167
Heejin Ahne915a712018-12-08 06:17:43 +0000168static void checkEventType(const Symbol *Existing, const InputFile *File,
169 const WasmEventType *NewType,
170 const WasmSignature *NewSig) {
171 auto ExistingEvent = dyn_cast<EventSymbol>(Existing);
172 if (!isa<EventSymbol>(Existing)) {
173 reportTypeError(Existing, File, WASM_SYMBOL_TYPE_EVENT);
174 return;
175 }
176
177 const WasmEventType *OldType = cast<EventSymbol>(Existing)->getEventType();
178 const WasmSignature *OldSig = ExistingEvent->Signature;
179 if (NewType->Attribute != OldType->Attribute)
180 error("Event type mismatch: " + Existing->getName() + "\n>>> defined as " +
181 toString(*OldType) + " in " + toString(Existing->getFile()) +
182 "\n>>> defined as " + toString(*NewType) + " in " + toString(File));
183 if (*NewSig != *OldSig)
184 warn("Event signature mismatch: " + Existing->getName() +
185 "\n>>> defined as " + toString(*OldSig) + " in " +
186 toString(Existing->getFile()) + "\n>>> defined as " +
187 toString(*NewSig) + " in " + toString(File));
188}
189
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000190static void checkDataType(const Symbol *Existing, const InputFile *File) {
191 if (!isa<DataSymbol>(Existing))
Sam Clegg3876d89a2018-05-14 22:42:33 +0000192 reportTypeError(Existing, File, WASM_SYMBOL_TYPE_DATA);
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000193}
194
Sam Cleggdfb0b2c2018-02-14 18:27:59 +0000195DefinedFunction *SymbolTable::addSyntheticFunction(StringRef Name,
Nicholas Wilsonebda41f2018-03-09 16:43:05 +0000196 uint32_t Flags,
197 InputFunction *Function) {
Nicola Zaghene7245b42018-05-15 13:36:20 +0000198 LLVM_DEBUG(dbgs() << "addSyntheticFunction: " << Name << "\n");
Rui Ueyamab961abc2018-02-28 22:51:51 +0000199 assert(!find(Name));
Nicholas Wilsonebda41f2018-03-09 16:43:05 +0000200 SyntheticFunctions.emplace_back(Function);
Sam Cleggd15a41542019-03-08 21:10:48 +0000201 return replaceSymbol<DefinedFunction>(insertName(Name).first, Name,
Sam Clegg4c2cbfe2018-08-02 20:39:19 +0000202 Flags, nullptr, Function);
Sam Clegg50686852018-01-12 18:35:13 +0000203}
204
Sam Clegg8e8ddaa2019-06-04 16:35:23 +0000205// Adds an optional, linker generated, data symbols. The symbol will only be
206// added if there is an undefine reference to it, or if it is explictly exported
207// via the --export flag. Otherwise we don't add the symbol and return nullptr.
Sam Clegg4bce63a2019-05-23 10:06:03 +0000208DefinedData *SymbolTable::addOptionalDataSymbol(StringRef Name, uint32_t Value,
209 uint32_t Flags) {
210 Symbol *S = find(Name);
Sam Clegg7d4ec5a2019-05-31 22:51:59 +0000211 if (!S && (Config->ExportAll || Config->ExportedSymbols.count(Name) != 0))
212 S = insertName(Name).first;
213 else if (!S || S->isDefined())
Sam Clegg4bce63a2019-05-23 10:06:03 +0000214 return nullptr;
215 LLVM_DEBUG(dbgs() << "addOptionalDataSymbol: " << Name << "\n");
216 auto *rtn = replaceSymbol<DefinedData>(S, Name, Flags);
217 rtn->setVirtualAddress(Value);
Sam Clegg15006462019-07-08 10:35:08 +0000218 rtn->Referenced = true;
Sam Clegg4bce63a2019-05-23 10:06:03 +0000219 return rtn;
220}
221
Sam Clegg00245532018-02-20 23:38:27 +0000222DefinedData *SymbolTable::addSyntheticDataSymbol(StringRef Name,
223 uint32_t Flags) {
Nicola Zaghene7245b42018-05-15 13:36:20 +0000224 LLVM_DEBUG(dbgs() << "addSyntheticDataSymbol: " << Name << "\n");
Rui Ueyamab961abc2018-02-28 22:51:51 +0000225 assert(!find(Name));
Sam Cleggd15a41542019-03-08 21:10:48 +0000226 return replaceSymbol<DefinedData>(insertName(Name).first, Name, Flags);
Sam Cleggc94d3932017-11-17 18:14:09 +0000227}
228
Sam Clegg93102972018-02-23 05:08:53 +0000229DefinedGlobal *SymbolTable::addSyntheticGlobal(StringRef Name, uint32_t Flags,
230 InputGlobal *Global) {
Nicola Zaghene7245b42018-05-15 13:36:20 +0000231 LLVM_DEBUG(dbgs() << "addSyntheticGlobal: " << Name << " -> " << Global
232 << "\n");
Rui Ueyamab961abc2018-02-28 22:51:51 +0000233 assert(!find(Name));
Nicholas Wilsonebda41f2018-03-09 16:43:05 +0000234 SyntheticGlobals.emplace_back(Global);
Sam Cleggd15a41542019-03-08 21:10:48 +0000235 return replaceSymbol<DefinedGlobal>(insertName(Name).first, Name, Flags,
Sam Clegg4c2cbfe2018-08-02 20:39:19 +0000236 nullptr, Global);
Sam Clegg93102972018-02-23 05:08:53 +0000237}
238
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000239static bool shouldReplace(const Symbol *Existing, InputFile *NewFile,
240 uint32_t NewFlags) {
Rui Ueyamac03c9042018-02-20 21:08:47 +0000241 // If existing symbol is undefined, replace it.
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000242 if (!Existing->isDefined()) {
Nicola Zaghene7245b42018-05-15 13:36:20 +0000243 LLVM_DEBUG(dbgs() << "resolving existing undefined symbol: "
244 << Existing->getName() << "\n");
Rui Ueyamac03c9042018-02-20 21:08:47 +0000245 return true;
246 }
247
248 // Now we have two defined symbols. If the new one is weak, we can ignore it.
249 if ((NewFlags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) {
Nicola Zaghene7245b42018-05-15 13:36:20 +0000250 LLVM_DEBUG(dbgs() << "existing symbol takes precedence\n");
Rui Ueyamac03c9042018-02-20 21:08:47 +0000251 return false;
252 }
253
254 // If the existing symbol is weak, we should replace it.
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000255 if (Existing->isWeak()) {
Nicola Zaghene7245b42018-05-15 13:36:20 +0000256 LLVM_DEBUG(dbgs() << "replacing existing weak symbol\n");
Rui Ueyamac03c9042018-02-20 21:08:47 +0000257 return true;
258 }
259
260 // Neither symbol is week. They conflict.
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000261 error("duplicate symbol: " + toString(*Existing) + "\n>>> defined in " +
262 toString(Existing->getFile()) + "\n>>> defined in " +
263 toString(NewFile));
Rui Ueyamac03c9042018-02-20 21:08:47 +0000264 return true;
Sam Clegg93e559b2018-02-20 18:55:06 +0000265}
266
267Symbol *SymbolTable::addDefinedFunction(StringRef Name, uint32_t Flags,
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000268 InputFile *File,
269 InputFunction *Function) {
Sam Clegg8b0b48f2018-09-28 16:50:14 +0000270 LLVM_DEBUG(dbgs() << "addDefinedFunction: " << Name << " ["
271 << (Function ? toString(Function->Signature) : "none")
272 << "]\n");
Sam Clegg93e559b2018-02-20 18:55:06 +0000273 Symbol *S;
274 bool WasInserted;
Sam Clegg4c2cbfe2018-08-02 20:39:19 +0000275 std::tie(S, WasInserted) = insert(Name, File);
Sam Cleggc729c1b2018-05-30 18:07:52 +0000276
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000277 auto ReplaceSym = [&](Symbol *Sym) {
Sam Clegg6540e572019-02-20 23:19:31 +0000278 // If the new defined function doesn't have signture (i.e. bitcode
279 // functions) but the old symbol does, then preserve the old signature
280 const WasmSignature *OldSig = S->getSignature();
281 auto* NewSym = replaceSymbol<DefinedFunction>(Sym, Name, Flags, File, Function);
282 if (!NewSym->Signature)
283 NewSym->Signature = OldSig;
284 };
285
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000286 if (WasInserted || S->isLazy()) {
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000287 ReplaceSym(S);
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000288 return S;
289 }
290
Sam Clegg6540e572019-02-20 23:19:31 +0000291 auto ExistingFunction = dyn_cast<FunctionSymbol>(S);
292 if (!ExistingFunction) {
293 reportTypeError(S, File, WASM_SYMBOL_TYPE_FUNCTION);
294 return S;
Sam Clegg8b0b48f2018-09-28 16:50:14 +0000295 }
Sam Clegg6540e572019-02-20 23:19:31 +0000296
Sam Clegg59f959f2019-05-24 22:45:08 +0000297 bool CheckSig = true;
298 if (auto UD = dyn_cast<UndefinedFunction>(ExistingFunction))
299 CheckSig = UD->IsCalledDirectly;
300
301 if (CheckSig && Function && !signatureMatches(ExistingFunction, &Function->Signature)) {
Sam Clegg6540e572019-02-20 23:19:31 +0000302 Symbol* Variant;
303 if (getFunctionVariant(S, &Function->Signature, File, &Variant))
304 // New variant, always replace
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000305 ReplaceSym(Variant);
Sam Clegg6540e572019-02-20 23:19:31 +0000306 else if (shouldReplace(S, File, Flags))
307 // Variant already exists, replace it after checking shouldReplace
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000308 ReplaceSym(Variant);
Sam Clegg6540e572019-02-20 23:19:31 +0000309
310 // This variant we found take the place in the symbol table as the primary
311 // variant.
312 replace(Name, Variant);
313 return Variant;
314 }
315
316 // Existing function with matching signature.
317 if (shouldReplace(S, File, Flags))
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000318 ReplaceSym(S);
Sam Clegg6540e572019-02-20 23:19:31 +0000319
Sam Clegg93e559b2018-02-20 18:55:06 +0000320 return S;
321}
322
Sam Clegg00245532018-02-20 23:38:27 +0000323Symbol *SymbolTable::addDefinedData(StringRef Name, uint32_t Flags,
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000324 InputFile *File, InputSegment *Segment,
Sam Clegg93102972018-02-23 05:08:53 +0000325 uint32_t Address, uint32_t Size) {
Nicola Zaghene7245b42018-05-15 13:36:20 +0000326 LLVM_DEBUG(dbgs() << "addDefinedData:" << Name << " addr:" << Address
327 << "\n");
Sam Clegg93e559b2018-02-20 18:55:06 +0000328 Symbol *S;
329 bool WasInserted;
Sam Clegg4c2cbfe2018-08-02 20:39:19 +0000330 std::tie(S, WasInserted) = insert(Name, File);
Sam Cleggc729c1b2018-05-30 18:07:52 +0000331
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000332 auto ReplaceSym = [&]() {
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000333 replaceSymbol<DefinedData>(S, Name, Flags, File, Segment, Address, Size);
Sam Clegg6540e572019-02-20 23:19:31 +0000334 };
335
336 if (WasInserted || S->isLazy()) {
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000337 ReplaceSym();
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000338 return S;
339 }
340
341 checkDataType(S, File);
342
343 if (shouldReplace(S, File, Flags))
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000344 ReplaceSym();
Sam Cleggc94d3932017-11-17 18:14:09 +0000345 return S;
346}
347
Sam Clegg93102972018-02-23 05:08:53 +0000348Symbol *SymbolTable::addDefinedGlobal(StringRef Name, uint32_t Flags,
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000349 InputFile *File, InputGlobal *Global) {
Nicola Zaghene7245b42018-05-15 13:36:20 +0000350 LLVM_DEBUG(dbgs() << "addDefinedGlobal:" << Name << "\n");
Sam Clegg4c2cbfe2018-08-02 20:39:19 +0000351
Sam Clegg93102972018-02-23 05:08:53 +0000352 Symbol *S;
353 bool WasInserted;
Sam Clegg4c2cbfe2018-08-02 20:39:19 +0000354 std::tie(S, WasInserted) = insert(Name, File);
Sam Cleggc729c1b2018-05-30 18:07:52 +0000355
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000356 auto ReplaceSym = [&]() {
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000357 replaceSymbol<DefinedGlobal>(S, Name, Flags, File, Global);
Sam Clegg6540e572019-02-20 23:19:31 +0000358 };
359
360 if (WasInserted || S->isLazy()) {
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000361 ReplaceSym();
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000362 return S;
363 }
364
365 checkGlobalType(S, File, &Global->getType());
366
367 if (shouldReplace(S, File, Flags))
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000368 ReplaceSym();
Sam Clegg93102972018-02-23 05:08:53 +0000369 return S;
370}
371
Heejin Ahne915a712018-12-08 06:17:43 +0000372Symbol *SymbolTable::addDefinedEvent(StringRef Name, uint32_t Flags,
373 InputFile *File, InputEvent *Event) {
374 LLVM_DEBUG(dbgs() << "addDefinedEvent:" << Name << "\n");
375
376 Symbol *S;
377 bool WasInserted;
378 std::tie(S, WasInserted) = insert(Name, File);
379
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000380 auto ReplaceSym = [&]() {
Heejin Ahne915a712018-12-08 06:17:43 +0000381 replaceSymbol<DefinedEvent>(S, Name, Flags, File, Event);
Sam Clegg6540e572019-02-20 23:19:31 +0000382 };
383
384 if (WasInserted || S->isLazy()) {
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000385 ReplaceSym();
Heejin Ahne915a712018-12-08 06:17:43 +0000386 return S;
387 }
388
389 checkEventType(S, File, &Event->getType(), &Event->Signature);
390
391 if (shouldReplace(S, File, Flags))
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000392 ReplaceSym();
Heejin Ahne915a712018-12-08 06:17:43 +0000393 return S;
394}
395
Dan Gohman9b84eea2019-02-07 22:00:48 +0000396Symbol *SymbolTable::addUndefinedFunction(StringRef Name, StringRef ImportName,
397 StringRef ImportModule,
Sam Clegg7cc07532019-02-01 02:29:57 +0000398 uint32_t Flags, InputFile *File,
Sam Clegg59f959f2019-05-24 22:45:08 +0000399 const WasmSignature *Sig,
400 bool IsCalledDirectly) {
Sam Cleggd506b0a2019-05-29 15:36:42 +0000401 LLVM_DEBUG(dbgs() << "addUndefinedFunction: " << Name << " ["
402 << (Sig ? toString(*Sig) : "none")
403 << "] IsCalledDirectly:" << IsCalledDirectly << "\n");
Rui Ueyamac03c9042018-02-20 21:08:47 +0000404
Sam Cleggc94d3932017-11-17 18:14:09 +0000405 Symbol *S;
406 bool WasInserted;
Sam Clegg4c2cbfe2018-08-02 20:39:19 +0000407 std::tie(S, WasInserted) = insert(Name, File);
Sam Clegg7991b682019-05-24 13:29:17 +0000408 if (S->Traced)
409 printTraceSymbolUndefined(Name, File);
Sam Cleggc729c1b2018-05-30 18:07:52 +0000410
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000411 auto ReplaceSym = [&]() {
Dan Gohman9b84eea2019-02-07 22:00:48 +0000412 replaceSymbol<UndefinedFunction>(S, Name, ImportName, ImportModule, Flags,
Sam Clegg59f959f2019-05-24 22:45:08 +0000413 File, Sig, IsCalledDirectly);
Sam Clegg6540e572019-02-20 23:19:31 +0000414 };
415
416 if (WasInserted)
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000417 ReplaceSym();
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000418 else if (auto *Lazy = dyn_cast<LazySymbol>(S))
Rui Ueyamab961abc2018-02-28 22:51:51 +0000419 Lazy->fetch();
Sam Clegg6540e572019-02-20 23:19:31 +0000420 else {
421 auto ExistingFunction = dyn_cast<FunctionSymbol>(S);
422 if (!ExistingFunction) {
423 reportTypeError(S, File, WASM_SYMBOL_TYPE_FUNCTION);
424 return S;
425 }
Sam Cleggd506b0a2019-05-29 15:36:42 +0000426 if (!ExistingFunction->Signature && Sig)
427 ExistingFunction->Signature = Sig;
Sam Clegg59f959f2019-05-24 22:45:08 +0000428 if (IsCalledDirectly && !signatureMatches(ExistingFunction, Sig))
Sam Clegg6540e572019-02-20 23:19:31 +0000429 if (getFunctionVariant(S, Sig, File, &S))
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000430 ReplaceSym();
Sam Clegg6540e572019-02-20 23:19:31 +0000431 }
Sam Cleggcefbf9a2018-06-28 16:53:53 +0000432
Sam Cleggc94d3932017-11-17 18:14:09 +0000433 return S;
434}
435
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000436Symbol *SymbolTable::addUndefinedData(StringRef Name, uint32_t Flags,
437 InputFile *File) {
Nicola Zaghene7245b42018-05-15 13:36:20 +0000438 LLVM_DEBUG(dbgs() << "addUndefinedData: " << Name << "\n");
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000439
440 Symbol *S;
441 bool WasInserted;
Sam Clegg4c2cbfe2018-08-02 20:39:19 +0000442 std::tie(S, WasInserted) = insert(Name, File);
Sam Clegg7991b682019-05-24 13:29:17 +0000443 if (S->Traced)
444 printTraceSymbolUndefined(Name, File);
Sam Cleggf989a922018-07-17 19:15:02 +0000445
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000446 if (WasInserted)
447 replaceSymbol<UndefinedData>(S, Name, Flags, File);
448 else if (auto *Lazy = dyn_cast<LazySymbol>(S))
Rui Ueyamab961abc2018-02-28 22:51:51 +0000449 Lazy->fetch();
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000450 else if (S->isDefined())
451 checkDataType(S, File);
452 return S;
453}
454
Dan Gohman9b84eea2019-02-07 22:00:48 +0000455Symbol *SymbolTable::addUndefinedGlobal(StringRef Name, StringRef ImportName,
456 StringRef ImportModule, uint32_t Flags,
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000457 InputFile *File,
458 const WasmGlobalType *Type) {
Nicola Zaghene7245b42018-05-15 13:36:20 +0000459 LLVM_DEBUG(dbgs() << "addUndefinedGlobal: " << Name << "\n");
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000460
461 Symbol *S;
462 bool WasInserted;
Sam Clegg4c2cbfe2018-08-02 20:39:19 +0000463 std::tie(S, WasInserted) = insert(Name, File);
Sam Clegg7991b682019-05-24 13:29:17 +0000464 if (S->Traced)
465 printTraceSymbolUndefined(Name, File);
Sam Cleggc729c1b2018-05-30 18:07:52 +0000466
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000467 if (WasInserted)
Dan Gohman9b84eea2019-02-07 22:00:48 +0000468 replaceSymbol<UndefinedGlobal>(S, Name, ImportName, ImportModule, Flags,
469 File, Type);
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000470 else if (auto *Lazy = dyn_cast<LazySymbol>(S))
Rui Ueyamab961abc2018-02-28 22:51:51 +0000471 Lazy->fetch();
Rui Ueyamae3498ec2018-02-28 00:09:22 +0000472 else if (S->isDefined())
473 checkGlobalType(S, File, Type);
474 return S;
475}
476
477void SymbolTable::addLazy(ArchiveFile *File, const Archive::Symbol *Sym) {
Nicola Zaghene7245b42018-05-15 13:36:20 +0000478 LLVM_DEBUG(dbgs() << "addLazy: " << Sym->getName() << "\n");
Sam Cleggc94d3932017-11-17 18:14:09 +0000479 StringRef Name = Sym->getName();
Rui Ueyamac03c9042018-02-20 21:08:47 +0000480
Sam Cleggc94d3932017-11-17 18:14:09 +0000481 Symbol *S;
482 bool WasInserted;
Sam Cleggd15a41542019-03-08 21:10:48 +0000483 std::tie(S, WasInserted) = insertName(Name);
Rui Ueyamac03c9042018-02-20 21:08:47 +0000484
Sam Cleggc94d3932017-11-17 18:14:09 +0000485 if (WasInserted) {
Sam Clegg37b4ee52019-01-29 22:26:31 +0000486 replaceSymbol<LazySymbol>(S, Name, 0, File, *Sym);
Rui Ueyamac03c9042018-02-20 21:08:47 +0000487 return;
488 }
489
Sam Clegg37b4ee52019-01-29 22:26:31 +0000490 if (!S->isUndefined())
491 return;
492
493 // The existing symbol is undefined, load a new one from the archive,
494 // unless the the existing symbol is weak in which case replace the undefined
495 // symbols with a LazySymbol.
496 if (S->isWeak()) {
497 const WasmSignature *OldSig = nullptr;
498 // In the case of an UndefinedFunction we need to preserve the expected
499 // signature.
500 if (auto *F = dyn_cast<UndefinedFunction>(S))
501 OldSig = F->Signature;
502 LLVM_DEBUG(dbgs() << "replacing existing weak undefined symbol\n");
503 auto NewSym = replaceSymbol<LazySymbol>(S, Name, WASM_SYMBOL_BINDING_WEAK,
504 File, *Sym);
505 NewSym->Signature = OldSig;
506 return;
Sam Cleggc94d3932017-11-17 18:14:09 +0000507 }
Sam Clegg37b4ee52019-01-29 22:26:31 +0000508
509 LLVM_DEBUG(dbgs() << "replacing existing undefined\n");
510 File->addMember(Sym);
Sam Cleggc94d3932017-11-17 18:14:09 +0000511}
Sam Clegge0f6fcd2018-01-12 22:25:17 +0000512
Nicholas Wilsonc4d9aa12018-03-14 15:45:11 +0000513bool SymbolTable::addComdat(StringRef Name) {
Sam Clegg697f2142019-05-15 16:03:28 +0000514 return ComdatGroups.insert(CachedHashStringRef(Name)).second;
Sam Clegge0f6fcd2018-01-12 22:25:17 +0000515}
Sam Clegg1f3f7742019-02-06 02:35:18 +0000516
Sam Clegg6540e572019-02-20 23:19:31 +0000517// The new signature doesn't match. Create a variant to the symbol with the
518// signature encoded in the name and return that instead. These symbols are
519// then unified later in handleSymbolVariants.
520bool SymbolTable::getFunctionVariant(Symbol* Sym, const WasmSignature *Sig,
521 const InputFile *File, Symbol **Out) {
Richard Trieu14bab092019-02-21 00:36:14 +0000522 LLVM_DEBUG(dbgs() << "getFunctionVariant: " << Sym->getName() << " -> "
Sam Clegg6540e572019-02-20 23:19:31 +0000523 << " " << toString(*Sig) << "\n");
524 Symbol *Variant = nullptr;
525
526 // Linear search through symbol variants. Should never be more than two
527 // or three entries here.
528 auto &Variants = SymVariants[CachedHashStringRef(Sym->getName())];
Fangrui Song196a4402019-04-18 13:33:29 +0000529 if (Variants.empty())
Sam Clegg6540e572019-02-20 23:19:31 +0000530 Variants.push_back(Sym);
531
532 for (Symbol* V : Variants) {
533 if (*V->getSignature() == *Sig) {
534 Variant = V;
535 break;
536 }
537 }
538
539 bool WasAdded = !Variant;
540 if (WasAdded) {
541 // Create a new variant;
542 LLVM_DEBUG(dbgs() << "added new variant\n");
543 Variant = reinterpret_cast<Symbol *>(make<SymbolUnion>());
544 Variants.push_back(Variant);
545 } else {
546 LLVM_DEBUG(dbgs() << "variant already exists: " << toString(*Variant) << "\n");
547 assert(*Variant->getSignature() == *Sig);
548 }
549
550 *Out = Variant;
551 return WasAdded;
552}
553
Sam Clegg1f3f7742019-02-06 02:35:18 +0000554// Set a flag for --trace-symbol so that we can print out a log message
555// if a new symbol with the same name is inserted into the symbol table.
556void SymbolTable::trace(StringRef Name) {
557 SymMap.insert({CachedHashStringRef(Name), -1});
558}
Sam Clegg230dc112019-02-07 22:42:16 +0000559
Sam Clegga5ca34e2019-05-24 14:14:25 +0000560void SymbolTable::wrap(Symbol *Sym, Symbol *Real, Symbol *Wrap) {
561 // Swap symbols as instructed by -wrap.
562 int &OrigIdx = SymMap[CachedHashStringRef(Sym->getName())];
563 int &RealIdx= SymMap[CachedHashStringRef(Real->getName())];
564 int &WrapIdx = SymMap[CachedHashStringRef(Wrap->getName())];
565 LLVM_DEBUG(dbgs() << "wrap: " << Sym->getName() << "\n");
566
567 // Anyone looking up __real symbols should get the original
568 RealIdx = OrigIdx;
569 // Anyone looking up the original should get the __wrap symbol
570 OrigIdx = WrapIdx;
571}
572
Sam Clegg230dc112019-02-07 22:42:16 +0000573static const uint8_t UnreachableFn[] = {
574 0x03 /* ULEB length */, 0x00 /* ULEB num locals */,
575 0x00 /* opcode unreachable */, 0x0b /* opcode end */
576};
577
578// Replace the given symbol body with an unreachable function.
579// This is used by handleWeakUndefines in order to generate a callable
Sam Clegg6540e572019-02-20 23:19:31 +0000580// equivalent of an undefined function and also handleSymbolVariants for
581// undefined functions that don't match the signature of the definition.
Sam Clegg230dc112019-02-07 22:42:16 +0000582InputFunction *SymbolTable::replaceWithUnreachable(Symbol *Sym,
583 const WasmSignature &Sig,
584 StringRef DebugName) {
585 auto *Func = make<SyntheticFunction>(Sig, Sym->getName(), DebugName);
586 Func->setBody(UnreachableFn);
587 SyntheticFunctions.emplace_back(Func);
Sam Clegg6540e572019-02-20 23:19:31 +0000588 replaceSymbol<DefinedFunction>(Sym, Sym->getName(), Sym->getFlags(), nullptr,
589 Func);
Sam Clegg230dc112019-02-07 22:42:16 +0000590 return Func;
591}
592
593// For weak undefined functions, there may be "call" instructions that reference
594// the symbol. In this case, we need to synthesise a dummy/stub function that
595// will abort at runtime, so that relocations can still provided an operand to
596// the call instruction that passes Wasm validation.
597void SymbolTable::handleWeakUndefines() {
598 for (Symbol *Sym : getSymbols()) {
599 if (!Sym->isUndefWeak())
600 continue;
601
Sam Clegg6540e572019-02-20 23:19:31 +0000602 const WasmSignature *Sig = Sym->getSignature();
603 if (!Sig) {
Sam Clegg230dc112019-02-07 22:42:16 +0000604 // It is possible for undefined functions not to have a signature (eg. if
605 // added via "--undefined"), but weak undefined ones do have a signature.
Sam Clegg6540e572019-02-20 23:19:31 +0000606 // Lazy symbols may not be functions and therefore Sig can still be null
607 // in some circumstantce.
608 assert(!isa<FunctionSymbol>(Sym));
Sam Clegg230dc112019-02-07 22:42:16 +0000609 continue;
Sam Clegg6540e572019-02-20 23:19:31 +0000610 }
Sam Clegg230dc112019-02-07 22:42:16 +0000611
612 // Add a synthetic dummy for weak undefined functions. These dummies will
613 // be GC'd if not used as the target of any "call" instructions.
614 StringRef DebugName = Saver.save("undefined:" + toString(*Sym));
615 InputFunction* Func = replaceWithUnreachable(Sym, *Sig, DebugName);
616 // Ensure it compares equal to the null pointer, and so that table relocs
617 // don't pull in the stub body (only call-operand relocs should do that).
618 Func->setTableIndex(0);
619 // Hide our dummy to prevent export.
620 Sym->setHidden(true);
621 }
622}
Sam Clegg6540e572019-02-20 23:19:31 +0000623
624static void reportFunctionSignatureMismatch(StringRef SymName,
625 FunctionSymbol *A,
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000626 FunctionSymbol *B, bool IsError) {
Sam Clegg6540e572019-02-20 23:19:31 +0000627 std::string msg = ("function signature mismatch: " + SymName +
628 "\n>>> defined as " + toString(*A->Signature) + " in " +
629 toString(A->getFile()) + "\n>>> defined as " +
630 toString(*B->Signature) + " in " + toString(B->getFile()))
631 .str();
Rui Ueyama7e296ad2019-07-10 09:10:01 +0000632 if (IsError)
Sam Clegg6540e572019-02-20 23:19:31 +0000633 error(msg);
634 else
635 warn(msg);
636}
637
638// Remove any variant symbols that were created due to function signature
639// mismatches.
640void SymbolTable::handleSymbolVariants() {
641 for (auto Pair : SymVariants) {
642 // Push the initial symbol onto the list of variants.
643 StringRef SymName = Pair.first.val();
644 std::vector<Symbol *> &Variants = Pair.second;
645
646#ifndef NDEBUG
Sam Cleggf8d736f2019-02-21 01:33:26 +0000647 LLVM_DEBUG(dbgs() << "symbol with (" << Variants.size()
648 << ") variants: " << SymName << "\n");
Sam Clegg6540e572019-02-20 23:19:31 +0000649 for (auto *S: Variants) {
650 auto *F = cast<FunctionSymbol>(S);
Sam Cleggf8d736f2019-02-21 01:33:26 +0000651 LLVM_DEBUG(dbgs() << " variant: " + F->getName() << " "
652 << toString(*F->Signature) << "\n");
Sam Clegg6540e572019-02-20 23:19:31 +0000653 }
654#endif
655
656 // Find the one definition.
657 DefinedFunction *Defined = nullptr;
658 for (auto *Symbol : Variants) {
659 if (auto F = dyn_cast<DefinedFunction>(Symbol)) {
660 Defined = F;
661 break;
662 }
663 }
664
665 // If there are no definitions, and the undefined symbols disagree on
666 // the signature, there is not we can do since we don't know which one
667 // to use as the signature on the import.
668 if (!Defined) {
669 reportFunctionSignatureMismatch(SymName,
670 cast<FunctionSymbol>(Variants[0]),
671 cast<FunctionSymbol>(Variants[1]), true);
672 return;
673 }
674
675 for (auto *Symbol : Variants) {
676 if (Symbol != Defined) {
677 auto *F = cast<FunctionSymbol>(Symbol);
678 reportFunctionSignatureMismatch(SymName, F, Defined, false);
679 StringRef DebugName = Saver.save("unreachable:" + toString(*F));
680 replaceWithUnreachable(F, *F->Signature, DebugName);
681 }
682 }
683 }
684}