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 "InputChunks.h"
12#include "InputElement.h"
13#include "WriterUtils.h"
14#include "lld/Common/CommonLinkerContext.h"
15#include <optional>
16
17#define DEBUG_TYPE "lld"
18
19using namespace llvm;
20using namespace llvm::wasm;
21using namespace llvm::object;
22
23namespace lld::wasm {
24SymbolTable *symtab;
25
26void SymbolTable::addFile(InputFile *file, StringRef symName) {
27 log(msg: "Processing: " + toString(file));
28
29 // Lazy object file
30 if (file->lazy) {
31 if (auto *f = dyn_cast<BitcodeFile>(Val: file)) {
32 ctx.lazyBitcodeFiles.push_back(Elt: f);
33 f->parseLazy();
34 } else {
35 cast<ObjFile>(Val: file)->parseLazy();
36 }
37 return;
38 }
39
40 // .so file
41 if (auto *f = dyn_cast<SharedFile>(Val: file)) {
42 // If we are not reporting undefined symbols that we don't actualy
43 // parse the shared library symbol table.
44 f->parse();
45 ctx.sharedFiles.push_back(Elt: f);
46 return;
47 }
48
49 // stub file
50 if (auto *f = dyn_cast<StubFile>(Val: file)) {
51 f->parse();
52 ctx.stubFiles.push_back(Elt: f);
53 return;
54 }
55
56 if (ctx.arg.trace)
57 message(msg: toString(file));
58
59 // LLVM bitcode file
60 if (auto *f = dyn_cast<BitcodeFile>(Val: file)) {
61 // This order, first adding to `bitcodeFiles` and then parsing is necessary.
62 // See https://github.com/llvm/llvm-project/pull/73095
63 ctx.bitcodeFiles.push_back(Elt: f);
64 f->parse(symName);
65 return;
66 }
67
68 // Regular object file
69 auto *f = cast<ObjFile>(Val: file);
70 f->parse(ignoreComdats: false);
71 ctx.objectFiles.push_back(Elt: f);
72}
73
74// This function is where all the optimizations of link-time
75// optimization happens. When LTO is in use, some input files are
76// not in native object file format but in the LLVM bitcode format.
77// This function compiles bitcode files into a few big native files
78// using LLVM functions and replaces bitcode symbols with the results.
79// Because all bitcode files that the program consists of are passed
80// to the compiler at once, it can do whole-program optimization.
81void SymbolTable::compileBitcodeFiles() {
82 // Prevent further LTO objects being included
83 BitcodeFile::doneLTO = true;
84
85 // Compile bitcode files and replace bitcode symbols.
86 lto.reset(p: new BitcodeCompiler);
87 for (BitcodeFile *f : ctx.bitcodeFiles)
88 lto->add(f&: *f);
89
90 for (auto &file : lto->compile()) {
91 auto *obj = cast<ObjFile>(Val: file);
92 obj->parse(ignoreComdats: true);
93 ctx.objectFiles.push_back(Elt: obj);
94 }
95}
96
97Symbol *SymbolTable::find(StringRef name) {
98 auto it = symMap.find(Val: CachedHashStringRef(name));
99 if (it == symMap.end() || it->second == -1)
100 return nullptr;
101 return symVector[it->second];
102}
103
104void SymbolTable::replace(StringRef name, Symbol *sym) {
105 auto it = symMap.find(Val: CachedHashStringRef(name));
106 symVector[it->second] = sym;
107}
108
109std::pair<Symbol *, bool> SymbolTable::insertName(StringRef name) {
110 bool trace = false;
111 auto p = symMap.insert(KV: {CachedHashStringRef(name), (int)symVector.size()});
112 int &symIndex = p.first->second;
113 bool isNew = p.second;
114 if (symIndex == -1) {
115 symIndex = symVector.size();
116 trace = true;
117 isNew = true;
118 }
119
120 if (!isNew)
121 return {symVector[symIndex], false};
122
123 Symbol *sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
124 sym->isUsedInRegularObj = false;
125 sym->canInline = true;
126 sym->traced = trace;
127 sym->forceExport = false;
128 sym->referenced = !ctx.arg.gcSections;
129 symVector.emplace_back(args&: sym);
130 return {sym, true};
131}
132
133std::pair<Symbol *, bool> SymbolTable::insert(StringRef name,
134 const InputFile *file) {
135 Symbol *s;
136 bool wasInserted;
137 std::tie(args&: s, args&: wasInserted) = insertName(name);
138
139 if (!file || file->kind() == InputFile::ObjectKind)
140 s->isUsedInRegularObj = true;
141
142 return {s, wasInserted};
143}
144
145static void reportTypeError(const Symbol *existing, const InputFile *file,
146 llvm::wasm::WasmSymbolType type) {
147 error(msg: "symbol type mismatch: " + toString(sym: *existing) + "\n>>> defined as " +
148 toString(type: existing->getWasmType()) + " in " +
149 toString(file: existing->getFile()) + "\n>>> defined as " + toString(type) +
150 " in " + toString(file));
151}
152
153// Check the type of new symbol matches that of the symbol is replacing.
154// Returns true if the function types match, false is there is a signature
155// mismatch.
156static bool signatureMatches(FunctionSymbol *existing,
157 const WasmSignature *newSig) {
158 const WasmSignature *oldSig = existing->signature;
159
160 // If either function is missing a signature (this happens for bitcode
161 // symbols) then assume they match. Any mismatch will be reported later
162 // when the LTO objects are added.
163 if (!newSig || !oldSig)
164 return true;
165
166 return *newSig == *oldSig;
167}
168
169static void checkGlobalType(const Symbol *existing, const InputFile *file,
170 const WasmGlobalType *newType) {
171 if (!isa<GlobalSymbol>(Val: existing)) {
172 reportTypeError(existing, file, type: WASM_SYMBOL_TYPE_GLOBAL);
173 return;
174 }
175
176 const WasmGlobalType *oldType = cast<GlobalSymbol>(Val: existing)->getGlobalType();
177 if (*newType != *oldType) {
178 error(msg: "Global type mismatch: " + existing->getName() + "\n>>> defined as " +
179 toString(type: *oldType) + " in " + toString(file: existing->getFile()) +
180 "\n>>> defined as " + toString(type: *newType) + " in " + toString(file));
181 }
182}
183
184static void checkTagType(const Symbol *existing, const InputFile *file,
185 const WasmSignature *newSig) {
186 const auto *existingTag = dyn_cast<TagSymbol>(Val: existing);
187 if (!isa<TagSymbol>(Val: existing)) {
188 reportTypeError(existing, file, type: WASM_SYMBOL_TYPE_TAG);
189 return;
190 }
191
192 const WasmSignature *oldSig = existingTag->signature;
193 if (*newSig != *oldSig)
194 warn(msg: "Tag signature mismatch: " + existing->getName() +
195 "\n>>> defined as " + toString(sig: *oldSig) + " in " +
196 toString(file: existing->getFile()) + "\n>>> defined as " +
197 toString(sig: *newSig) + " in " + toString(file));
198}
199
200static void checkTableType(const Symbol *existing, const InputFile *file,
201 const WasmTableType *newType) {
202 if (!isa<TableSymbol>(Val: existing)) {
203 reportTypeError(existing, file, type: WASM_SYMBOL_TYPE_TABLE);
204 return;
205 }
206
207 const WasmTableType *oldType = cast<TableSymbol>(Val: existing)->getTableType();
208 if (newType->ElemType != oldType->ElemType) {
209 error(msg: "Table type mismatch: " + existing->getName() + "\n>>> defined as " +
210 toString(type: *oldType) + " in " + toString(file: existing->getFile()) +
211 "\n>>> defined as " + toString(type: *newType) + " in " + toString(file));
212 }
213 // FIXME: No assertions currently on the limits.
214}
215
216static void checkDataType(const Symbol *existing, const InputFile *file) {
217 if (!isa<DataSymbol>(Val: existing))
218 reportTypeError(existing, file, type: WASM_SYMBOL_TYPE_DATA);
219}
220
221DefinedFunction *SymbolTable::addSyntheticFunction(StringRef name,
222 uint32_t flags,
223 InputFunction *function) {
224 LLVM_DEBUG(dbgs() << "addSyntheticFunction: " << name << "\n");
225 assert(!find(name));
226 ctx.syntheticFunctions.emplace_back(Args&: function);
227 return replaceSymbol<DefinedFunction>(s: insertName(name).first, arg&: name, arg&: flags,
228 arg: nullptr, arg&: function);
229}
230
231// Adds an optional, linker generated, data symbol. The symbol will only be
232// added if there is an undefine reference to it, or if it is explicitly
233// exported via the --export flag. Otherwise we don't add the symbol and return
234// nullptr.
235DefinedData *SymbolTable::addOptionalDataSymbol(StringRef name,
236 uint64_t value) {
237 Symbol *s = find(name);
238 if (!s && (ctx.arg.exportAll || ctx.arg.exportedSymbols.contains(key: name)))
239 s = insertName(name).first;
240 else if (!s || s->isDefined())
241 return nullptr;
242 LLVM_DEBUG(dbgs() << "addOptionalDataSymbol: " << name << "\n");
243 auto *rtn = replaceSymbol<DefinedData>(
244 s, arg&: name, arg: WASM_SYMBOL_VISIBILITY_HIDDEN | WASM_SYMBOL_ABSOLUTE);
245 rtn->setVA(value);
246 rtn->referenced = true;
247 return rtn;
248}
249
250DefinedData *SymbolTable::addSyntheticDataSymbol(StringRef name,
251 uint32_t flags) {
252 LLVM_DEBUG(dbgs() << "addSyntheticDataSymbol: " << name << "\n");
253 assert(!find(name));
254 return replaceSymbol<DefinedData>(s: insertName(name).first, arg&: name,
255 arg: flags | WASM_SYMBOL_ABSOLUTE);
256}
257
258DefinedGlobal *SymbolTable::addSyntheticGlobal(StringRef name, uint32_t flags,
259 InputGlobal *global) {
260 LLVM_DEBUG(dbgs() << "addSyntheticGlobal: " << name << " -> " << global
261 << "\n");
262 assert(!find(name));
263 ctx.syntheticGlobals.emplace_back(Args&: global);
264 return replaceSymbol<DefinedGlobal>(s: insertName(name).first, arg&: name, arg&: flags,
265 arg: nullptr, arg&: global);
266}
267
268DefinedGlobal *SymbolTable::addOptionalGlobalSymbol(StringRef name,
269 InputGlobal *global) {
270 Symbol *s = find(name);
271 if (!s && (ctx.arg.exportAll || ctx.arg.exportedSymbols.contains(key: name)))
272 s = insertName(name).first;
273 else if (!s || s->isDefined())
274 return nullptr;
275 LLVM_DEBUG(dbgs() << "addOptionalGlobalSymbol: " << name << " -> " << global
276 << "\n");
277 ctx.syntheticGlobals.emplace_back(Args&: global);
278 return replaceSymbol<DefinedGlobal>(s, arg&: name, arg: WASM_SYMBOL_VISIBILITY_HIDDEN,
279 arg: nullptr, arg&: global);
280}
281
282DefinedTable *SymbolTable::addSyntheticTable(StringRef name, uint32_t flags,
283 InputTable *table) {
284 LLVM_DEBUG(dbgs() << "addSyntheticTable: " << name << " -> " << table
285 << "\n");
286 Symbol *s = find(name);
287 assert(!s || s->isUndefined());
288 if (!s)
289 s = insertName(name).first;
290 ctx.syntheticTables.emplace_back(Args&: table);
291 return replaceSymbol<DefinedTable>(s, arg&: name, arg&: flags, arg: nullptr, arg&: table);
292}
293
294static bool shouldReplace(const Symbol *existing, InputFile *newFile,
295 uint32_t newFlags) {
296 // If existing symbol is undefined, replace it.
297 if (!existing->isDefined()) {
298 LLVM_DEBUG(dbgs() << "resolving existing undefined symbol: "
299 << existing->getName() << "\n");
300 return true;
301 }
302
303 // Now we have two defined symbols. If the new one is weak, we can ignore it.
304 if ((newFlags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) {
305 LLVM_DEBUG(dbgs() << "existing symbol takes precedence\n");
306 return false;
307 }
308
309 // If the existing symbol is weak, we should replace it.
310 if (existing->isWeak()) {
311 LLVM_DEBUG(dbgs() << "replacing existing weak symbol\n");
312 return true;
313 }
314
315 // Similarly with shared symbols
316 if (existing->isShared()) {
317 LLVM_DEBUG(dbgs() << "replacing existing shared symbol\n");
318 return true;
319 }
320
321 // Neither symbol is week. They conflict.
322 if (ctx.arg.allowMultipleDefinition)
323 return false;
324
325 errorOrWarn(msg: "duplicate symbol: " + toString(sym: *existing) + "\n>>> defined in " +
326 toString(file: existing->getFile()) + "\n>>> defined in " +
327 toString(file: newFile));
328 return true;
329}
330
331static void reportFunctionSignatureMismatch(StringRef symName,
332 FunctionSymbol *sym,
333 const WasmSignature *signature,
334 InputFile *file,
335 bool isError = true) {
336 std::string msg =
337 ("function signature mismatch: " + symName + "\n>>> defined as " +
338 toString(sig: *sym->signature) + " in " + toString(file: sym->getFile()) +
339 "\n>>> defined as " + toString(sig: *signature) + " in " + toString(file))
340 .str();
341 if (isError)
342 error(msg);
343 else
344 warn(msg);
345}
346
347static void reportFunctionSignatureMismatch(StringRef symName,
348 FunctionSymbol *a,
349 FunctionSymbol *b,
350 bool isError = true) {
351 reportFunctionSignatureMismatch(symName, sym: a, signature: b->signature, file: b->getFile(),
352 isError);
353}
354
355Symbol *SymbolTable::addSharedFunction(StringRef name, uint32_t flags,
356 InputFile *file,
357 const WasmSignature *sig) {
358 LLVM_DEBUG(dbgs() << "addSharedFunction: " << name << " [" << toString(*sig)
359 << "]\n");
360 Symbol *s;
361 bool wasInserted;
362 std::tie(args&: s, args&: wasInserted) = insert(name, file);
363
364 auto replaceSym = [&](Symbol *sym) {
365 replaceSymbol<SharedFunctionSymbol>(s: sym, arg&: name, arg&: flags, arg&: file, arg&: sig);
366 };
367
368 if (wasInserted || s->isLazy()) {
369 replaceSym(s);
370 return s;
371 }
372
373 auto existingFunction = dyn_cast<FunctionSymbol>(Val: s);
374 if (!existingFunction) {
375 reportTypeError(existing: s, file, type: WASM_SYMBOL_TYPE_FUNCTION);
376 return s;
377 }
378
379 // Shared symbols should never replace locally-defined ones
380 if (s->isDefined()) {
381 return s;
382 }
383
384 LLVM_DEBUG(dbgs() << "resolving existing undefined symbol: " << s->getName()
385 << "\n");
386
387 bool checkSig = true;
388 if (auto ud = dyn_cast<UndefinedFunction>(Val: existingFunction))
389 checkSig = ud->isCalledDirectly;
390
391 if (checkSig && !signatureMatches(existing: existingFunction, newSig: sig)) {
392 if (ctx.arg.shlibSigCheck) {
393 reportFunctionSignatureMismatch(symName: name, sym: existingFunction, signature: sig, file);
394 } else {
395 // With --no-shlib-sigcheck we ignore the signature of the function as
396 // defined by the shared library and instead use the signature as
397 // expected by the program being linked.
398 sig = existingFunction->signature;
399 }
400 }
401
402 replaceSym(s);
403 return s;
404}
405
406Symbol *SymbolTable::addSharedData(StringRef name, uint32_t flags,
407 InputFile *file) {
408 LLVM_DEBUG(dbgs() << "addSharedData: " << name << "\n");
409 Symbol *s;
410 bool wasInserted;
411 std::tie(args&: s, args&: wasInserted) = insert(name, file);
412
413 if (wasInserted || s->isLazy()) {
414 replaceSymbol<SharedData>(s, arg&: name, arg&: flags, arg&: file);
415 return s;
416 }
417
418 // Shared symbols should never replace locally-defined ones
419 if (s->isDefined()) {
420 return s;
421 }
422
423 checkDataType(existing: s, file);
424 replaceSymbol<SharedData>(s, arg&: name, arg&: flags, arg&: file);
425 return s;
426}
427
428Symbol *SymbolTable::addDefinedFunction(StringRef name, uint32_t flags,
429 InputFile *file,
430 InputFunction *function) {
431 LLVM_DEBUG(dbgs() << "addDefinedFunction: " << name << " ["
432 << (function ? toString(function->signature) : "none")
433 << "]\n");
434 Symbol *s;
435 bool wasInserted;
436 std::tie(args&: s, args&: wasInserted) = insert(name, file);
437
438 auto replaceSym = [&](Symbol *sym) {
439 // If the new defined function doesn't have signature (i.e. bitcode
440 // functions) but the old symbol does, then preserve the old signature
441 const WasmSignature *oldSig = s->getSignature();
442 auto *newSym =
443 replaceSymbol<DefinedFunction>(s: sym, arg&: name, arg&: flags, arg&: file, arg&: function);
444 if (!newSym->signature)
445 newSym->signature = oldSig;
446 };
447
448 if (wasInserted || s->isLazy()) {
449 replaceSym(s);
450 return s;
451 }
452
453 auto existingFunction = dyn_cast<FunctionSymbol>(Val: s);
454 if (!existingFunction) {
455 reportTypeError(existing: s, file, type: WASM_SYMBOL_TYPE_FUNCTION);
456 return s;
457 }
458
459 bool checkSig = true;
460 if (auto ud = dyn_cast<UndefinedFunction>(Val: existingFunction))
461 checkSig = ud->isCalledDirectly;
462
463 if (checkSig && function &&
464 !signatureMatches(existing: existingFunction, newSig: &function->signature)) {
465 Symbol *variant;
466 if (getFunctionVariant(sym: s, sig: &function->signature, file, out: &variant))
467 // New variant, always replace
468 replaceSym(variant);
469 else if (shouldReplace(existing: s, newFile: file, newFlags: flags))
470 // Variant already exists, replace it after checking shouldReplace
471 replaceSym(variant);
472
473 // This variant we found take the place in the symbol table as the primary
474 // variant.
475 replace(name, sym: variant);
476 return variant;
477 }
478
479 // Existing function with matching signature.
480 if (shouldReplace(existing: s, newFile: file, newFlags: flags))
481 replaceSym(s);
482
483 return s;
484}
485
486Symbol *SymbolTable::addDefinedData(StringRef name, uint32_t flags,
487 InputFile *file, InputChunk *segment,
488 uint64_t address, uint64_t size) {
489 LLVM_DEBUG(dbgs() << "addDefinedData:" << name << " addr:" << address
490 << "\n");
491 Symbol *s;
492 bool wasInserted;
493 std::tie(args&: s, args&: wasInserted) = insert(name, file);
494
495 auto replaceSym = [&]() {
496 replaceSymbol<DefinedData>(s, arg&: name, arg&: flags, arg&: file, arg&: segment, arg&: address, arg&: size);
497 };
498
499 if (wasInserted || s->isLazy()) {
500 replaceSym();
501 return s;
502 }
503
504 checkDataType(existing: s, file);
505
506 if (shouldReplace(existing: s, newFile: file, newFlags: flags))
507 replaceSym();
508 return s;
509}
510
511Symbol *SymbolTable::addDefinedGlobal(StringRef name, uint32_t flags,
512 InputFile *file, InputGlobal *global) {
513 LLVM_DEBUG(dbgs() << "addDefinedGlobal:" << name << "\n");
514
515 Symbol *s;
516 bool wasInserted;
517 std::tie(args&: s, args&: wasInserted) = insert(name, file);
518
519 auto replaceSym = [&]() {
520 replaceSymbol<DefinedGlobal>(s, arg&: name, arg&: flags, arg&: file, arg&: global);
521 };
522
523 if (wasInserted || s->isLazy()) {
524 replaceSym();
525 return s;
526 }
527
528 checkGlobalType(existing: s, file, newType: &global->getType());
529
530 if (shouldReplace(existing: s, newFile: file, newFlags: flags))
531 replaceSym();
532 return s;
533}
534
535Symbol *SymbolTable::addDefinedTag(StringRef name, uint32_t flags,
536 InputFile *file, InputTag *tag) {
537 LLVM_DEBUG(dbgs() << "addDefinedTag:" << name << "\n");
538
539 Symbol *s;
540 bool wasInserted;
541 std::tie(args&: s, args&: wasInserted) = insert(name, file);
542
543 auto replaceSym = [&]() {
544 replaceSymbol<DefinedTag>(s, arg&: name, arg&: flags, arg&: file, arg&: tag);
545 };
546
547 if (wasInserted || s->isLazy()) {
548 replaceSym();
549 return s;
550 }
551
552 checkTagType(existing: s, file, newSig: &tag->signature);
553
554 if (shouldReplace(existing: s, newFile: file, newFlags: flags))
555 replaceSym();
556 return s;
557}
558
559Symbol *SymbolTable::addDefinedTable(StringRef name, uint32_t flags,
560 InputFile *file, InputTable *table) {
561 LLVM_DEBUG(dbgs() << "addDefinedTable:" << name << "\n");
562
563 Symbol *s;
564 bool wasInserted;
565 std::tie(args&: s, args&: wasInserted) = insert(name, file);
566
567 auto replaceSym = [&]() {
568 replaceSymbol<DefinedTable>(s, arg&: name, arg&: flags, arg&: file, arg&: table);
569 };
570
571 if (wasInserted || s->isLazy()) {
572 replaceSym();
573 return s;
574 }
575
576 checkTableType(existing: s, file, newType: &table->getType());
577
578 if (shouldReplace(existing: s, newFile: file, newFlags: flags))
579 replaceSym();
580 return s;
581}
582
583// This function get called when an undefined symbol is added, and there is
584// already an existing one in the symbols table. In this case we check that
585// custom 'import-module' and 'import-field' symbol attributes agree.
586// With LTO these attributes are not available when the bitcode is read and only
587// become available when the LTO object is read. In this case we silently
588// replace the empty attributes with the valid ones.
589static void
590updateExistingUndefined(Symbol *existing, uint32_t flags, InputFile *file,
591 std::optional<StringRef> importName = {},
592 std::optional<StringRef> importModule = {}) {
593 if (importName) {
594 if (!existing->importName)
595 existing->importName = importName;
596 if (existing->importName != importName)
597 error(msg: "import name mismatch for symbol: " + toString(sym: *existing) +
598 "\n>>> defined as " + *existing->importName + " in " +
599 toString(file: existing->getFile()) + "\n>>> defined as " + *importName +
600 " in " + toString(file));
601 }
602
603 if (importModule) {
604 if (!existing->importModule)
605 existing->importModule = importModule;
606 if (existing->importModule != importModule)
607 error(msg: "import module mismatch for symbol: " + toString(sym: *existing) +
608 "\n>>> defined as " + *existing->importModule + " in " +
609 toString(file: existing->getFile()) + "\n>>> defined as " +
610 *importModule + " in " + toString(file));
611 }
612
613 // Update symbol binding, if the existing symbol is weak
614 uint32_t binding = flags & WASM_SYMBOL_BINDING_MASK;
615 if (existing->isWeak() && binding != WASM_SYMBOL_BINDING_WEAK) {
616 existing->flags = (existing->flags & ~WASM_SYMBOL_BINDING_MASK) | binding;
617 }
618
619 // Certain flags such as NO_STRIP should be maintianed if either old or
620 // new symbol is marked as such.
621 existing->flags |= flags & WASM_SYMBOL_NO_STRIP;
622}
623
624Symbol *SymbolTable::addUndefinedFunction(StringRef name,
625 std::optional<StringRef> importName,
626 std::optional<StringRef> importModule,
627 uint32_t flags, InputFile *file,
628 const WasmSignature *sig,
629 bool isCalledDirectly) {
630 LLVM_DEBUG(dbgs() << "addUndefinedFunction: " << name << " ["
631 << (sig ? toString(*sig) : "none")
632 << "] IsCalledDirectly:" << isCalledDirectly << " flags=0x"
633 << utohexstr(flags) << "\n");
634 assert(flags & WASM_SYMBOL_UNDEFINED);
635
636 Symbol *s;
637 bool wasInserted;
638 std::tie(args&: s, args&: wasInserted) = insert(name, file);
639 if (s->traced)
640 printTraceSymbolUndefined(name, file);
641
642 auto replaceSym = [&]() {
643 replaceSymbol<UndefinedFunction>(s, arg&: name, arg&: importName, arg&: importModule, arg&: flags,
644 arg&: file, arg&: sig, arg&: isCalledDirectly);
645 };
646
647 if (wasInserted) {
648 replaceSym();
649 } else if (auto *lazy = dyn_cast<LazySymbol>(Val: s)) {
650 if ((flags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) {
651 lazy->setWeak();
652 lazy->signature = sig;
653 } else {
654 lazy->extract();
655 if (!ctx.arg.whyExtract.empty())
656 ctx.whyExtractRecords.emplace_back(Args: toString(file), Args: s->getFile(), Args&: *s);
657 }
658 } else {
659 auto existingFunction = dyn_cast<FunctionSymbol>(Val: s);
660 if (!existingFunction) {
661 reportTypeError(existing: s, file, type: WASM_SYMBOL_TYPE_FUNCTION);
662 return s;
663 }
664 if (!existingFunction->signature && sig)
665 existingFunction->signature = sig;
666 auto *existingUndefined = dyn_cast<UndefinedFunction>(Val: existingFunction);
667 if (isCalledDirectly && !signatureMatches(existing: existingFunction, newSig: sig)) {
668 if (existingFunction->isShared()) {
669 // Special handling for when the existing function is a shared symbol
670 if (ctx.arg.shlibSigCheck) {
671 reportFunctionSignatureMismatch(symName: name, sym: existingFunction, signature: sig, file);
672 } else {
673 existingFunction->signature = sig;
674 }
675 }
676 // If the existing undefined functions is not called directly then let
677 // this one take precedence. Otherwise the existing function is either
678 // directly called or defined, in which case we need a function variant.
679 else if (existingUndefined && !existingUndefined->isCalledDirectly)
680 replaceSym();
681 else if (getFunctionVariant(sym: s, sig, file, out: &s))
682 replaceSym();
683 }
684 if (existingUndefined) {
685 updateExistingUndefined(existing: existingUndefined, flags, file, importName,
686 importModule);
687 if (isCalledDirectly)
688 existingUndefined->isCalledDirectly = true;
689 }
690 }
691
692 return s;
693}
694
695Symbol *SymbolTable::addUndefinedData(StringRef name, uint32_t flags,
696 InputFile *file) {
697 LLVM_DEBUG(dbgs() << "addUndefinedData: " << name << "\n");
698 assert(flags & WASM_SYMBOL_UNDEFINED);
699
700 Symbol *s;
701 bool wasInserted;
702 std::tie(args&: s, args&: wasInserted) = insert(name, file);
703 if (s->traced)
704 printTraceSymbolUndefined(name, file);
705
706 if (wasInserted) {
707 replaceSymbol<UndefinedData>(s, arg&: name, arg&: flags, arg&: file);
708 } else if (auto *lazy = dyn_cast<LazySymbol>(Val: s)) {
709 if ((flags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK)
710 lazy->setWeak();
711 else
712 lazy->extract();
713 } else if (s->isDefined()) {
714 checkDataType(existing: s, file);
715 } else {
716 updateExistingUndefined(existing: s, flags, file);
717 }
718 return s;
719}
720
721Symbol *SymbolTable::addUndefinedGlobal(StringRef name,
722 std::optional<StringRef> importName,
723 std::optional<StringRef> importModule,
724 uint32_t flags, InputFile *file,
725 const WasmGlobalType *type) {
726 LLVM_DEBUG(dbgs() << "addUndefinedGlobal: " << name << "\n");
727 assert(flags & WASM_SYMBOL_UNDEFINED);
728
729 Symbol *s;
730 bool wasInserted;
731 std::tie(args&: s, args&: wasInserted) = insert(name, file);
732 if (s->traced)
733 printTraceSymbolUndefined(name, file);
734
735 if (wasInserted)
736 replaceSymbol<UndefinedGlobal>(s, arg&: name, arg&: importName, arg&: importModule, arg&: flags,
737 arg&: file, arg&: type);
738 else if (auto *lazy = dyn_cast<LazySymbol>(Val: s))
739 lazy->extract();
740 else if (s->isDefined())
741 checkGlobalType(existing: s, file, newType: type);
742 else
743 updateExistingUndefined(existing: s, flags, file, importName, importModule);
744 return s;
745}
746
747Symbol *SymbolTable::addUndefinedTable(StringRef name,
748 std::optional<StringRef> importName,
749 std::optional<StringRef> importModule,
750 uint32_t flags, InputFile *file,
751 const WasmTableType *type) {
752 LLVM_DEBUG(dbgs() << "addUndefinedTable: " << name << "\n");
753 assert(flags & WASM_SYMBOL_UNDEFINED);
754
755 Symbol *s;
756 bool wasInserted;
757 std::tie(args&: s, args&: wasInserted) = insert(name, file);
758 if (s->traced)
759 printTraceSymbolUndefined(name, file);
760
761 if (wasInserted)
762 replaceSymbol<UndefinedTable>(s, arg&: name, arg&: importName, arg&: importModule, arg&: flags,
763 arg&: file, arg&: type);
764 else if (auto *lazy = dyn_cast<LazySymbol>(Val: s))
765 lazy->extract();
766 else if (s->isDefined())
767 checkTableType(existing: s, file, newType: type);
768 else
769 updateExistingUndefined(existing: s, flags, file, importName, importModule);
770 return s;
771}
772
773Symbol *SymbolTable::addUndefinedTag(StringRef name,
774 std::optional<StringRef> importName,
775 std::optional<StringRef> importModule,
776 uint32_t flags, InputFile *file,
777 const WasmSignature *sig) {
778 LLVM_DEBUG(dbgs() << "addUndefinedTag: " << name << "\n");
779 assert(flags & WASM_SYMBOL_UNDEFINED);
780
781 Symbol *s;
782 bool wasInserted;
783 std::tie(args&: s, args&: wasInserted) = insert(name, file);
784 if (s->traced)
785 printTraceSymbolUndefined(name, file);
786
787 if (wasInserted)
788 replaceSymbol<UndefinedTag>(s, arg&: name, arg&: importName, arg&: importModule, arg&: flags, arg&: file,
789 arg&: sig);
790 else if (auto *lazy = dyn_cast<LazySymbol>(Val: s))
791 lazy->extract();
792 else if (s->isDefined())
793 checkTagType(existing: s, file, newSig: sig);
794 else
795 updateExistingUndefined(existing: s, flags, file, importName, importModule);
796 return s;
797}
798
799TableSymbol *SymbolTable::createUndefinedIndirectFunctionTable(StringRef name) {
800 LLVM_DEBUG(llvm::dbgs() << "createUndefinedIndirectFunctionTable\n");
801 WasmLimits limits{.Flags: 0, .Minimum: 0, .Maximum: 0, .PageSize: 0}; // Set by the writer.
802 WasmTableType *type = make<WasmTableType>();
803 type->ElemType = ValType::FUNCREF;
804 type->Limits = limits;
805 uint32_t flags = ctx.arg.exportTable ? 0 : WASM_SYMBOL_VISIBILITY_HIDDEN;
806 flags |= WASM_SYMBOL_UNDEFINED;
807 Symbol *sym =
808 addUndefinedTable(name, importName: name, importModule: defaultModule, flags, file: nullptr, type);
809 sym->markLive();
810 sym->forceExport = ctx.arg.exportTable;
811 return cast<TableSymbol>(Val: sym);
812}
813
814TableSymbol *SymbolTable::createDefinedIndirectFunctionTable(StringRef name) {
815 LLVM_DEBUG(llvm::dbgs() << "createDefinedIndirectFunctionTable\n");
816 const uint32_t invalidIndex = -1;
817 WasmLimits limits{.Flags: 0, .Minimum: 0, .Maximum: 0, .PageSize: 0}; // Set by the writer.
818 WasmTableType type{.ElemType: ValType::FUNCREF, .Limits: limits};
819 WasmTable desc{.Index: invalidIndex, .Type: type, .SymbolName: name};
820 InputTable *table = make<InputTable>(args&: desc, args: nullptr);
821 uint32_t flags = ctx.arg.exportTable ? 0 : WASM_SYMBOL_VISIBILITY_HIDDEN;
822 TableSymbol *sym = addSyntheticTable(name, flags, table);
823 sym->markLive();
824 sym->forceExport = ctx.arg.exportTable;
825 return sym;
826}
827
828// Whether or not we need an indirect function table is usually a function of
829// whether an input declares a need for it. However sometimes it's possible for
830// no input to need the indirect function table, but then a late
831// addInternalGOTEntry causes a function to be allocated an address. In that
832// case address we synthesize a definition at the last minute.
833TableSymbol *SymbolTable::resolveIndirectFunctionTable(bool required) {
834 Symbol *existing = find(name: functionTableName);
835 if (existing) {
836 if (!isa<TableSymbol>(Val: existing)) {
837 error(msg: Twine("reserved symbol must be of type table: `") +
838 functionTableName + "`");
839 return nullptr;
840 }
841 if (existing->isDefined()) {
842 error(msg: Twine("reserved symbol must not be defined in input files: `") +
843 functionTableName + "`");
844 return nullptr;
845 }
846 }
847
848 if (ctx.arg.importTable) {
849 if (existing) {
850 existing->importModule = defaultModule;
851 existing->importName = functionTableName;
852 return cast<TableSymbol>(Val: existing);
853 }
854 if (required)
855 return createUndefinedIndirectFunctionTable(name: functionTableName);
856 } else if ((existing && existing->isLive()) || ctx.arg.exportTable ||
857 required) {
858 // A defined table is required. Either because the user request an exported
859 // table or because the table symbol is already live. The existing table is
860 // guaranteed to be undefined due to the check above.
861 return createDefinedIndirectFunctionTable(name: functionTableName);
862 }
863
864 // An indirect function table will only be present in the symbol table if
865 // needed by a reloc; if we get here, we don't need one.
866 return nullptr;
867}
868
869void SymbolTable::addLazy(StringRef name, InputFile *file) {
870 LLVM_DEBUG(dbgs() << "addLazy: " << name << "\n");
871
872 Symbol *s;
873 bool wasInserted;
874 std::tie(args&: s, args&: wasInserted) = insertName(name);
875
876 if (wasInserted) {
877 replaceSymbol<LazySymbol>(s, arg&: name, arg: 0, arg&: file);
878 return;
879 }
880
881 if (!s->isUndefined())
882 return;
883
884 // The existing symbol is undefined, load a new one from the archive,
885 // unless the existing symbol is weak in which case replace the undefined
886 // symbols with a LazySymbol.
887 if (s->isWeak()) {
888 const WasmSignature *oldSig = nullptr;
889 // In the case of an UndefinedFunction we need to preserve the expected
890 // signature.
891 if (auto *f = dyn_cast<UndefinedFunction>(Val: s))
892 oldSig = f->signature;
893 LLVM_DEBUG(dbgs() << "replacing existing weak undefined symbol\n");
894 auto newSym =
895 replaceSymbol<LazySymbol>(s, arg&: name, arg: WASM_SYMBOL_BINDING_WEAK, arg&: file);
896 newSym->signature = oldSig;
897 return;
898 }
899
900 LLVM_DEBUG(dbgs() << "replacing existing undefined\n");
901 const InputFile *oldFile = s->getFile();
902 LazySymbol(name, 0, file).extract();
903 if (!ctx.arg.whyExtract.empty())
904 ctx.whyExtractRecords.emplace_back(Args: toString(file: oldFile), Args: s->getFile(), Args&: *s);
905}
906
907bool SymbolTable::addComdat(StringRef name) {
908 return comdatGroups.insert(V: CachedHashStringRef(name)).second;
909}
910
911// The new signature doesn't match. Create a variant to the symbol with the
912// signature encoded in the name and return that instead. These symbols are
913// then unified later in handleSymbolVariants.
914bool SymbolTable::getFunctionVariant(Symbol *sym, const WasmSignature *sig,
915 const InputFile *file, Symbol **out) {
916 LLVM_DEBUG(dbgs() << "getFunctionVariant: " << sym->getName() << " -> "
917 << " " << toString(*sig) << "\n");
918 Symbol *variant = nullptr;
919
920 // Linear search through symbol variants. Should never be more than two
921 // or three entries here.
922 auto &variants = symVariants[CachedHashStringRef(sym->getName())];
923 if (variants.empty())
924 variants.push_back(x: sym);
925
926 for (Symbol *v : variants) {
927 if (*v->getSignature() == *sig) {
928 variant = v;
929 break;
930 }
931 }
932
933 bool wasAdded = !variant;
934 if (wasAdded) {
935 // Create a new variant;
936 LLVM_DEBUG(dbgs() << "added new variant\n");
937 variant = reinterpret_cast<Symbol *>(make<SymbolUnion>());
938 variant->isUsedInRegularObj =
939 !file || file->kind() == InputFile::ObjectKind;
940 variant->canInline = true;
941 variant->traced = false;
942 variant->forceExport = false;
943 variants.push_back(x: variant);
944 } else {
945 LLVM_DEBUG(dbgs() << "variant already exists: " << toString(*variant)
946 << "\n");
947 assert(*variant->getSignature() == *sig);
948 }
949
950 *out = variant;
951 return wasAdded;
952}
953
954// Set a flag for --trace-symbol so that we can print out a log message
955// if a new symbol with the same name is inserted into the symbol table.
956void SymbolTable::trace(StringRef name) {
957 symMap.insert(KV: {CachedHashStringRef(name), -1});
958}
959
960void SymbolTable::wrap(Symbol *sym, Symbol *real, Symbol *wrap) {
961 // Swap symbols as instructed by -wrap.
962 int &origIdx = symMap[CachedHashStringRef(sym->getName())];
963 int &realIdx = symMap[CachedHashStringRef(real->getName())];
964 int &wrapIdx = symMap[CachedHashStringRef(wrap->getName())];
965 LLVM_DEBUG(dbgs() << "wrap: " << sym->getName() << "\n");
966
967 // Anyone looking up __real symbols should get the original
968 realIdx = origIdx;
969 // Anyone looking up the original should get the __wrap symbol
970 origIdx = wrapIdx;
971}
972
973static const uint8_t unreachableFn[] = {
974 0x03 /* ULEB length */, 0x00 /* ULEB num locals */,
975 0x00 /* opcode unreachable */, 0x0b /* opcode end */
976};
977
978// Replace the given symbol body with an unreachable function.
979// This is used by handleWeakUndefines in order to generate a callable
980// equivalent of an undefined function and also handleSymbolVariants for
981// undefined functions that don't match the signature of the definition.
982InputFunction *SymbolTable::replaceWithUnreachable(Symbol *sym,
983 const WasmSignature &sig,
984 StringRef debugName) {
985 auto *func = make<SyntheticFunction>(args: sig, args: sym->getName(), args&: debugName);
986 func->setBody(unreachableFn);
987 ctx.syntheticFunctions.emplace_back(Args&: func);
988 // Mark new symbols as local. For relocatable output we don't want them
989 // to be exported outside the object file.
990 replaceSymbol<DefinedFunction>(s: sym, arg&: debugName, arg: WASM_SYMBOL_BINDING_LOCAL,
991 arg: nullptr, arg&: func);
992 // Ensure the stub function doesn't get a table entry. Its address
993 // should always compare equal to the null pointer.
994 sym->isStub = true;
995 return func;
996}
997
998void SymbolTable::replaceWithUndefined(Symbol *sym) {
999 // Add a synthetic dummy for weak undefined functions. These dummies will
1000 // be GC'd if not used as the target of any "call" instructions.
1001 StringRef debugName = saver().save(S: "undefined_weak:" + toString(sym: *sym));
1002 replaceWithUnreachable(sym, sig: *sym->getSignature(), debugName);
1003 // Hide our dummy to prevent export.
1004 sym->setHidden(true);
1005}
1006
1007// For weak undefined functions, there may be "call" instructions that reference
1008// the symbol. In this case, we need to synthesise a dummy/stub function that
1009// will abort at runtime, so that relocations can still provided an operand to
1010// the call instruction that passes Wasm validation.
1011void SymbolTable::handleWeakUndefines() {
1012 for (Symbol *sym : symbols()) {
1013 if (sym->isUndefWeak() && sym->isUsedInRegularObj) {
1014 if (sym->getSignature()) {
1015 replaceWithUndefined(sym);
1016 } else {
1017 // It is possible for undefined functions not to have a signature (eg.
1018 // if added via "--undefined"), but weak undefined ones do have a
1019 // signature. Lazy symbols may not be functions and therefore Sig can
1020 // still be null in some circumstance.
1021 assert(!isa<FunctionSymbol>(sym));
1022 }
1023 }
1024 }
1025}
1026
1027DefinedFunction *SymbolTable::createUndefinedStub(const WasmSignature &sig) {
1028 if (auto it = stubFunctions.find(Val: sig); it != stubFunctions.end())
1029 return it->second;
1030 LLVM_DEBUG(dbgs() << "createUndefinedStub: " << toString(sig) << "\n");
1031 auto *sym = reinterpret_cast<DefinedFunction *>(make<SymbolUnion>());
1032 sym->isUsedInRegularObj = true;
1033 sym->canInline = true;
1034 sym->traced = false;
1035 sym->forceExport = false;
1036 sym->signature = &sig;
1037 replaceSymbol<DefinedFunction>(
1038 s: sym, arg: "undefined_stub", arg: WASM_SYMBOL_VISIBILITY_HIDDEN, arg: nullptr, arg: nullptr);
1039 replaceWithUnreachable(sym, sig, debugName: "undefined_stub");
1040 stubFunctions[sig] = sym;
1041 return sym;
1042}
1043
1044// Remove any variant symbols that were created due to function signature
1045// mismatches.
1046void SymbolTable::handleSymbolVariants() {
1047 for (auto pair : symVariants) {
1048 // Push the initial symbol onto the list of variants.
1049 StringRef symName = pair.first.val();
1050 std::vector<Symbol *> &variants = pair.second;
1051
1052#ifndef NDEBUG
1053 LLVM_DEBUG(dbgs() << "symbol with (" << variants.size()
1054 << ") variants: " << symName << "\n");
1055 for (auto *s : variants) {
1056 auto *f = cast<FunctionSymbol>(s);
1057 LLVM_DEBUG(dbgs() << " variant: " + f->getName() << " "
1058 << toString(*f->signature) << "\n");
1059 }
1060#endif
1061
1062 // Find the one definition.
1063 DefinedFunction *defined = nullptr;
1064 for (auto *symbol : variants) {
1065 if (auto f = dyn_cast<DefinedFunction>(Val: symbol)) {
1066 defined = f;
1067 break;
1068 }
1069 }
1070
1071 // If there are no definitions, and the undefined symbols disagree on
1072 // the signature, there is not we can do since we don't know which one
1073 // to use as the signature on the import.
1074 if (!defined) {
1075 reportFunctionSignatureMismatch(symName,
1076 a: cast<FunctionSymbol>(Val: variants[0]),
1077 b: cast<FunctionSymbol>(Val: variants[1]));
1078 return;
1079 }
1080
1081 for (auto *symbol : variants) {
1082 if (symbol != defined) {
1083 auto *f = cast<FunctionSymbol>(Val: symbol);
1084 reportFunctionSignatureMismatch(symName, a: f, b: defined, isError: false);
1085 StringRef debugName =
1086 saver().save(S: "signature_mismatch:" + toString(sym: *f));
1087 replaceWithUnreachable(sym: f, sig: *f->signature, debugName);
1088 }
1089 }
1090 }
1091}
1092
1093} // namespace lld::wasm
1094