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,
228 arg&: flags, 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 = replaceSymbol<DefinedFunction>(s: sym, arg&: name, arg&: flags, arg&: file, arg&: function);
443 if (!newSym->signature)
444 newSym->signature = oldSig;
445 };
446
447 if (wasInserted || s->isLazy()) {
448 replaceSym(s);
449 return s;
450 }
451
452 auto existingFunction = dyn_cast<FunctionSymbol>(Val: s);
453 if (!existingFunction) {
454 reportTypeError(existing: s, file, type: WASM_SYMBOL_TYPE_FUNCTION);
455 return s;
456 }
457
458 bool checkSig = true;
459 if (auto ud = dyn_cast<UndefinedFunction>(Val: existingFunction))
460 checkSig = ud->isCalledDirectly;
461
462 if (checkSig && function && !signatureMatches(existing: existingFunction, newSig: &function->signature)) {
463 Symbol* variant;
464 if (getFunctionVariant(sym: s, sig: &function->signature, file, out: &variant))
465 // New variant, always replace
466 replaceSym(variant);
467 else if (shouldReplace(existing: s, newFile: file, newFlags: flags))
468 // Variant already exists, replace it after checking shouldReplace
469 replaceSym(variant);
470
471 // This variant we found take the place in the symbol table as the primary
472 // variant.
473 replace(name, sym: variant);
474 return variant;
475 }
476
477 // Existing function with matching signature.
478 if (shouldReplace(existing: s, newFile: file, newFlags: flags))
479 replaceSym(s);
480
481 return s;
482}
483
484Symbol *SymbolTable::addDefinedData(StringRef name, uint32_t flags,
485 InputFile *file, InputChunk *segment,
486 uint64_t address, uint64_t size) {
487 LLVM_DEBUG(dbgs() << "addDefinedData:" << name << " addr:" << address
488 << "\n");
489 Symbol *s;
490 bool wasInserted;
491 std::tie(args&: s, args&: wasInserted) = insert(name, file);
492
493 auto replaceSym = [&]() {
494 replaceSymbol<DefinedData>(s, arg&: name, arg&: flags, arg&: file, arg&: segment, arg&: address, arg&: size);
495 };
496
497 if (wasInserted || s->isLazy()) {
498 replaceSym();
499 return s;
500 }
501
502 checkDataType(existing: s, file);
503
504 if (shouldReplace(existing: s, newFile: file, newFlags: flags))
505 replaceSym();
506 return s;
507}
508
509Symbol *SymbolTable::addDefinedGlobal(StringRef name, uint32_t flags,
510 InputFile *file, InputGlobal *global) {
511 LLVM_DEBUG(dbgs() << "addDefinedGlobal:" << name << "\n");
512
513 Symbol *s;
514 bool wasInserted;
515 std::tie(args&: s, args&: wasInserted) = insert(name, file);
516
517 auto replaceSym = [&]() {
518 replaceSymbol<DefinedGlobal>(s, arg&: name, arg&: flags, arg&: file, arg&: global);
519 };
520
521 if (wasInserted || s->isLazy()) {
522 replaceSym();
523 return s;
524 }
525
526 checkGlobalType(existing: s, file, newType: &global->getType());
527
528 if (shouldReplace(existing: s, newFile: file, newFlags: flags))
529 replaceSym();
530 return s;
531}
532
533Symbol *SymbolTable::addDefinedTag(StringRef name, uint32_t flags,
534 InputFile *file, InputTag *tag) {
535 LLVM_DEBUG(dbgs() << "addDefinedTag:" << name << "\n");
536
537 Symbol *s;
538 bool wasInserted;
539 std::tie(args&: s, args&: wasInserted) = insert(name, file);
540
541 auto replaceSym = [&]() {
542 replaceSymbol<DefinedTag>(s, arg&: name, arg&: flags, arg&: file, arg&: tag);
543 };
544
545 if (wasInserted || s->isLazy()) {
546 replaceSym();
547 return s;
548 }
549
550 checkTagType(existing: s, file, newSig: &tag->signature);
551
552 if (shouldReplace(existing: s, newFile: file, newFlags: flags))
553 replaceSym();
554 return s;
555}
556
557Symbol *SymbolTable::addDefinedTable(StringRef name, uint32_t flags,
558 InputFile *file, InputTable *table) {
559 LLVM_DEBUG(dbgs() << "addDefinedTable:" << name << "\n");
560
561 Symbol *s;
562 bool wasInserted;
563 std::tie(args&: s, args&: wasInserted) = insert(name, file);
564
565 auto replaceSym = [&]() {
566 replaceSymbol<DefinedTable>(s, arg&: name, arg&: flags, arg&: file, arg&: table);
567 };
568
569 if (wasInserted || s->isLazy()) {
570 replaceSym();
571 return s;
572 }
573
574 checkTableType(existing: s, file, newType: &table->getType());
575
576 if (shouldReplace(existing: s, newFile: file, newFlags: flags))
577 replaceSym();
578 return s;
579}
580
581// This function get called when an undefined symbol is added, and there is
582// already an existing one in the symbols table. In this case we check that
583// custom 'import-module' and 'import-field' symbol attributes agree.
584// With LTO these attributes are not available when the bitcode is read and only
585// become available when the LTO object is read. In this case we silently
586// replace the empty attributes with the valid ones.
587static void
588updateExistingUndefined(Symbol *existing, uint32_t flags, InputFile *file,
589 std::optional<StringRef> importName = {},
590 std::optional<StringRef> importModule = {}) {
591 if (importName) {
592 if (!existing->importName)
593 existing->importName = importName;
594 if (existing->importName != importName)
595 error(msg: "import name mismatch for symbol: " + toString(sym: *existing) +
596 "\n>>> defined as " + *existing->importName + " in " +
597 toString(file: existing->getFile()) + "\n>>> defined as " + *importName +
598 " in " + toString(file));
599 }
600
601 if (importModule) {
602 if (!existing->importModule)
603 existing->importModule = importModule;
604 if (existing->importModule != importModule)
605 error(msg: "import module mismatch for symbol: " + toString(sym: *existing) +
606 "\n>>> defined as " + *existing->importModule + " in " +
607 toString(file: existing->getFile()) + "\n>>> defined as " +
608 *importModule + " in " + toString(file));
609 }
610
611 // Update symbol binding, if the existing symbol is weak
612 uint32_t binding = flags & WASM_SYMBOL_BINDING_MASK;
613 if (existing->isWeak() && binding != WASM_SYMBOL_BINDING_WEAK) {
614 existing->flags = (existing->flags & ~WASM_SYMBOL_BINDING_MASK) | binding;
615 }
616
617 // Certain flags such as NO_STRIP should be maintianed if either old or
618 // new symbol is marked as such.
619 existing->flags |= flags & WASM_SYMBOL_NO_STRIP;
620}
621
622Symbol *SymbolTable::addUndefinedFunction(StringRef name,
623 std::optional<StringRef> importName,
624 std::optional<StringRef> importModule,
625 uint32_t flags, InputFile *file,
626 const WasmSignature *sig,
627 bool isCalledDirectly) {
628 LLVM_DEBUG(dbgs() << "addUndefinedFunction: " << name << " ["
629 << (sig ? toString(*sig) : "none")
630 << "] IsCalledDirectly:" << isCalledDirectly << " flags=0x"
631 << utohexstr(flags) << "\n");
632 assert(flags & WASM_SYMBOL_UNDEFINED);
633
634 Symbol *s;
635 bool wasInserted;
636 std::tie(args&: s, args&: wasInserted) = insert(name, file);
637 if (s->traced)
638 printTraceSymbolUndefined(name, file);
639
640 auto replaceSym = [&]() {
641 replaceSymbol<UndefinedFunction>(s, arg&: name, arg&: importName, arg&: importModule, arg&: flags,
642 arg&: file, arg&: sig, arg&: isCalledDirectly);
643 };
644
645 if (wasInserted) {
646 replaceSym();
647 } else if (auto *lazy = dyn_cast<LazySymbol>(Val: s)) {
648 if ((flags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) {
649 lazy->setWeak();
650 lazy->signature = sig;
651 } else {
652 lazy->extract();
653 if (!ctx.arg.whyExtract.empty())
654 ctx.whyExtractRecords.emplace_back(Args: toString(file), Args: s->getFile(), Args&: *s);
655 }
656 } else {
657 auto existingFunction = dyn_cast<FunctionSymbol>(Val: s);
658 if (!existingFunction) {
659 reportTypeError(existing: s, file, type: WASM_SYMBOL_TYPE_FUNCTION);
660 return s;
661 }
662 if (!existingFunction->signature && sig)
663 existingFunction->signature = sig;
664 auto *existingUndefined = dyn_cast<UndefinedFunction>(Val: existingFunction);
665 if (isCalledDirectly && !signatureMatches(existing: existingFunction, newSig: sig)) {
666 if (existingFunction->isShared()) {
667 // Special handling for when the existing function is a shared symbol
668 if (ctx.arg.shlibSigCheck) {
669 reportFunctionSignatureMismatch(symName: name, sym: existingFunction, signature: sig, file);
670 } else {
671 existingFunction->signature = sig;
672 }
673 }
674 // If the existing undefined functions is not called directly then let
675 // this one take precedence. Otherwise the existing function is either
676 // directly called or defined, in which case we need a function variant.
677 else if (existingUndefined && !existingUndefined->isCalledDirectly)
678 replaceSym();
679 else if (getFunctionVariant(sym: s, sig, file, out: &s))
680 replaceSym();
681 }
682 if (existingUndefined) {
683 updateExistingUndefined(existing: existingUndefined, flags, file, importName,
684 importModule);
685 if (isCalledDirectly)
686 existingUndefined->isCalledDirectly = true;
687 }
688 }
689
690 return s;
691}
692
693Symbol *SymbolTable::addUndefinedData(StringRef name, uint32_t flags,
694 InputFile *file) {
695 LLVM_DEBUG(dbgs() << "addUndefinedData: " << name << "\n");
696 assert(flags & WASM_SYMBOL_UNDEFINED);
697
698 Symbol *s;
699 bool wasInserted;
700 std::tie(args&: s, args&: wasInserted) = insert(name, file);
701 if (s->traced)
702 printTraceSymbolUndefined(name, file);
703
704 if (wasInserted) {
705 replaceSymbol<UndefinedData>(s, arg&: name, arg&: flags, arg&: file);
706 } else if (auto *lazy = dyn_cast<LazySymbol>(Val: s)) {
707 if ((flags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK)
708 lazy->setWeak();
709 else
710 lazy->extract();
711 } else if (s->isDefined()) {
712 checkDataType(existing: s, file);
713 } else {
714 updateExistingUndefined(existing: s, flags, file);
715 }
716 return s;
717}
718
719Symbol *SymbolTable::addUndefinedGlobal(StringRef name,
720 std::optional<StringRef> importName,
721 std::optional<StringRef> importModule,
722 uint32_t flags, InputFile *file,
723 const WasmGlobalType *type) {
724 LLVM_DEBUG(dbgs() << "addUndefinedGlobal: " << name << "\n");
725 assert(flags & WASM_SYMBOL_UNDEFINED);
726
727 Symbol *s;
728 bool wasInserted;
729 std::tie(args&: s, args&: wasInserted) = insert(name, file);
730 if (s->traced)
731 printTraceSymbolUndefined(name, file);
732
733 if (wasInserted)
734 replaceSymbol<UndefinedGlobal>(s, arg&: name, arg&: importName, arg&: importModule, arg&: flags,
735 arg&: file, arg&: type);
736 else if (auto *lazy = dyn_cast<LazySymbol>(Val: s))
737 lazy->extract();
738 else if (s->isDefined())
739 checkGlobalType(existing: s, file, newType: type);
740 else
741 updateExistingUndefined(existing: s, flags, file);
742 return s;
743}
744
745Symbol *SymbolTable::addUndefinedTable(StringRef name,
746 std::optional<StringRef> importName,
747 std::optional<StringRef> importModule,
748 uint32_t flags, InputFile *file,
749 const WasmTableType *type) {
750 LLVM_DEBUG(dbgs() << "addUndefinedTable: " << name << "\n");
751 assert(flags & WASM_SYMBOL_UNDEFINED);
752
753 Symbol *s;
754 bool wasInserted;
755 std::tie(args&: s, args&: wasInserted) = insert(name, file);
756 if (s->traced)
757 printTraceSymbolUndefined(name, file);
758
759 if (wasInserted)
760 replaceSymbol<UndefinedTable>(s, arg&: name, arg&: importName, arg&: importModule, arg&: flags,
761 arg&: file, arg&: type);
762 else if (auto *lazy = dyn_cast<LazySymbol>(Val: s))
763 lazy->extract();
764 else if (s->isDefined())
765 checkTableType(existing: s, file, newType: type);
766 else
767 updateExistingUndefined(existing: s, flags, file);
768 return s;
769}
770
771Symbol *SymbolTable::addUndefinedTag(StringRef name,
772 std::optional<StringRef> importName,
773 std::optional<StringRef> importModule,
774 uint32_t flags, InputFile *file,
775 const WasmSignature *sig) {
776 LLVM_DEBUG(dbgs() << "addUndefinedTag: " << name << "\n");
777 assert(flags & WASM_SYMBOL_UNDEFINED);
778
779 Symbol *s;
780 bool wasInserted;
781 std::tie(args&: s, args&: wasInserted) = insert(name, file);
782 if (s->traced)
783 printTraceSymbolUndefined(name, file);
784
785 if (wasInserted)
786 replaceSymbol<UndefinedTag>(s, arg&: name, arg&: importName, arg&: importModule, arg&: flags, arg&: file,
787 arg&: sig);
788 else if (auto *lazy = dyn_cast<LazySymbol>(Val: s))
789 lazy->extract();
790 else if (s->isDefined())
791 checkTagType(existing: s, file, newSig: sig);
792 else
793 updateExistingUndefined(existing: s, flags, file);
794 return s;
795}
796
797TableSymbol *SymbolTable::createUndefinedIndirectFunctionTable(StringRef name) {
798 LLVM_DEBUG(llvm::dbgs() << "createUndefinedIndirectFunctionTable\n");
799 WasmLimits limits{.Flags: 0, .Minimum: 0, .Maximum: 0, .PageSize: 0}; // Set by the writer.
800 WasmTableType *type = make<WasmTableType>();
801 type->ElemType = ValType::FUNCREF;
802 type->Limits = limits;
803 uint32_t flags = ctx.arg.exportTable ? 0 : WASM_SYMBOL_VISIBILITY_HIDDEN;
804 flags |= WASM_SYMBOL_UNDEFINED;
805 Symbol *sym =
806 addUndefinedTable(name, importName: name, importModule: defaultModule, flags, file: nullptr, type);
807 sym->markLive();
808 sym->forceExport = ctx.arg.exportTable;
809 return cast<TableSymbol>(Val: sym);
810}
811
812TableSymbol *SymbolTable::createDefinedIndirectFunctionTable(StringRef name) {
813 LLVM_DEBUG(llvm::dbgs() << "createDefinedIndirectFunctionTable\n");
814 const uint32_t invalidIndex = -1;
815 WasmLimits limits{.Flags: 0, .Minimum: 0, .Maximum: 0, .PageSize: 0}; // Set by the writer.
816 WasmTableType type{.ElemType: ValType::FUNCREF, .Limits: limits};
817 WasmTable desc{.Index: invalidIndex, .Type: type, .SymbolName: name};
818 InputTable *table = make<InputTable>(args&: desc, args: nullptr);
819 uint32_t flags = ctx.arg.exportTable ? 0 : WASM_SYMBOL_VISIBILITY_HIDDEN;
820 TableSymbol *sym = addSyntheticTable(name, flags, table);
821 sym->markLive();
822 sym->forceExport = ctx.arg.exportTable;
823 return sym;
824}
825
826// Whether or not we need an indirect function table is usually a function of
827// whether an input declares a need for it. However sometimes it's possible for
828// no input to need the indirect function table, but then a late
829// addInternalGOTEntry causes a function to be allocated an address. In that
830// case address we synthesize a definition at the last minute.
831TableSymbol *SymbolTable::resolveIndirectFunctionTable(bool required) {
832 Symbol *existing = find(name: functionTableName);
833 if (existing) {
834 if (!isa<TableSymbol>(Val: existing)) {
835 error(msg: Twine("reserved symbol must be of type table: `") +
836 functionTableName + "`");
837 return nullptr;
838 }
839 if (existing->isDefined()) {
840 error(msg: Twine("reserved symbol must not be defined in input files: `") +
841 functionTableName + "`");
842 return nullptr;
843 }
844 }
845
846 if (ctx.arg.importTable) {
847 if (existing) {
848 existing->importModule = defaultModule;
849 existing->importName = functionTableName;
850 return cast<TableSymbol>(Val: existing);
851 }
852 if (required)
853 return createUndefinedIndirectFunctionTable(name: functionTableName);
854 } else if ((existing && existing->isLive()) || ctx.arg.exportTable ||
855 required) {
856 // A defined table is required. Either because the user request an exported
857 // table or because the table symbol is already live. The existing table is
858 // guaranteed to be undefined due to the check above.
859 return createDefinedIndirectFunctionTable(name: functionTableName);
860 }
861
862 // An indirect function table will only be present in the symbol table if
863 // needed by a reloc; if we get here, we don't need one.
864 return nullptr;
865}
866
867void SymbolTable::addLazy(StringRef name, InputFile *file) {
868 LLVM_DEBUG(dbgs() << "addLazy: " << name << "\n");
869
870 Symbol *s;
871 bool wasInserted;
872 std::tie(args&: s, args&: wasInserted) = insertName(name);
873
874 if (wasInserted) {
875 replaceSymbol<LazySymbol>(s, arg&: name, arg: 0, arg&: file);
876 return;
877 }
878
879 if (!s->isUndefined())
880 return;
881
882 // The existing symbol is undefined, load a new one from the archive,
883 // unless the existing symbol is weak in which case replace the undefined
884 // symbols with a LazySymbol.
885 if (s->isWeak()) {
886 const WasmSignature *oldSig = nullptr;
887 // In the case of an UndefinedFunction we need to preserve the expected
888 // signature.
889 if (auto *f = dyn_cast<UndefinedFunction>(Val: s))
890 oldSig = f->signature;
891 LLVM_DEBUG(dbgs() << "replacing existing weak undefined symbol\n");
892 auto newSym =
893 replaceSymbol<LazySymbol>(s, arg&: name, arg: WASM_SYMBOL_BINDING_WEAK, arg&: file);
894 newSym->signature = oldSig;
895 return;
896 }
897
898 LLVM_DEBUG(dbgs() << "replacing existing undefined\n");
899 const InputFile *oldFile = s->getFile();
900 LazySymbol(name, 0, file).extract();
901 if (!ctx.arg.whyExtract.empty())
902 ctx.whyExtractRecords.emplace_back(Args: toString(file: oldFile), Args: s->getFile(), Args&: *s);
903}
904
905bool SymbolTable::addComdat(StringRef name) {
906 return comdatGroups.insert(V: CachedHashStringRef(name)).second;
907}
908
909// The new signature doesn't match. Create a variant to the symbol with the
910// signature encoded in the name and return that instead. These symbols are
911// then unified later in handleSymbolVariants.
912bool SymbolTable::getFunctionVariant(Symbol* sym, const WasmSignature *sig,
913 const InputFile *file, Symbol **out) {
914 LLVM_DEBUG(dbgs() << "getFunctionVariant: " << sym->getName() << " -> "
915 << " " << toString(*sig) << "\n");
916 Symbol *variant = nullptr;
917
918 // Linear search through symbol variants. Should never be more than two
919 // or three entries here.
920 auto &variants = symVariants[CachedHashStringRef(sym->getName())];
921 if (variants.empty())
922 variants.push_back(x: sym);
923
924 for (Symbol* v : variants) {
925 if (*v->getSignature() == *sig) {
926 variant = v;
927 break;
928 }
929 }
930
931 bool wasAdded = !variant;
932 if (wasAdded) {
933 // Create a new variant;
934 LLVM_DEBUG(dbgs() << "added new variant\n");
935 variant = reinterpret_cast<Symbol *>(make<SymbolUnion>());
936 variant->isUsedInRegularObj =
937 !file || file->kind() == InputFile::ObjectKind;
938 variant->canInline = true;
939 variant->traced = false;
940 variant->forceExport = false;
941 variants.push_back(x: variant);
942 } else {
943 LLVM_DEBUG(dbgs() << "variant already exists: " << toString(*variant) << "\n");
944 assert(*variant->getSignature() == *sig);
945 }
946
947 *out = variant;
948 return wasAdded;
949}
950
951// Set a flag for --trace-symbol so that we can print out a log message
952// if a new symbol with the same name is inserted into the symbol table.
953void SymbolTable::trace(StringRef name) {
954 symMap.insert(KV: {CachedHashStringRef(name), -1});
955}
956
957void SymbolTable::wrap(Symbol *sym, Symbol *real, Symbol *wrap) {
958 // Swap symbols as instructed by -wrap.
959 int &origIdx = symMap[CachedHashStringRef(sym->getName())];
960 int &realIdx= symMap[CachedHashStringRef(real->getName())];
961 int &wrapIdx = symMap[CachedHashStringRef(wrap->getName())];
962 LLVM_DEBUG(dbgs() << "wrap: " << sym->getName() << "\n");
963
964 // Anyone looking up __real symbols should get the original
965 realIdx = origIdx;
966 // Anyone looking up the original should get the __wrap symbol
967 origIdx = wrapIdx;
968}
969
970static const uint8_t unreachableFn[] = {
971 0x03 /* ULEB length */, 0x00 /* ULEB num locals */,
972 0x00 /* opcode unreachable */, 0x0b /* opcode end */
973};
974
975// Replace the given symbol body with an unreachable function.
976// This is used by handleWeakUndefines in order to generate a callable
977// equivalent of an undefined function and also handleSymbolVariants for
978// undefined functions that don't match the signature of the definition.
979InputFunction *SymbolTable::replaceWithUnreachable(Symbol *sym,
980 const WasmSignature &sig,
981 StringRef debugName) {
982 auto *func = make<SyntheticFunction>(args: sig, args: sym->getName(), args&: debugName);
983 func->setBody(unreachableFn);
984 ctx.syntheticFunctions.emplace_back(Args&: func);
985 // Mark new symbols as local. For relocatable output we don't want them
986 // to be exported outside the object file.
987 replaceSymbol<DefinedFunction>(s: sym, arg&: debugName, arg: WASM_SYMBOL_BINDING_LOCAL,
988 arg: nullptr, arg&: func);
989 // Ensure the stub function doesn't get a table entry. Its address
990 // should always compare equal to the null pointer.
991 sym->isStub = true;
992 return func;
993}
994
995void SymbolTable::replaceWithUndefined(Symbol *sym) {
996 // Add a synthetic dummy for weak undefined functions. These dummies will
997 // be GC'd if not used as the target of any "call" instructions.
998 StringRef debugName = saver().save(S: "undefined_weak:" + toString(sym: *sym));
999 replaceWithUnreachable(sym, sig: *sym->getSignature(), debugName);
1000 // Hide our dummy to prevent export.
1001 sym->setHidden(true);
1002}
1003
1004// For weak undefined functions, there may be "call" instructions that reference
1005// the symbol. In this case, we need to synthesise a dummy/stub function that
1006// will abort at runtime, so that relocations can still provided an operand to
1007// the call instruction that passes Wasm validation.
1008void SymbolTable::handleWeakUndefines() {
1009 for (Symbol *sym : symbols()) {
1010 if (sym->isUndefWeak() && sym->isUsedInRegularObj) {
1011 if (sym->getSignature()) {
1012 replaceWithUndefined(sym);
1013 } else {
1014 // It is possible for undefined functions not to have a signature (eg.
1015 // if added via "--undefined"), but weak undefined ones do have a
1016 // signature. Lazy symbols may not be functions and therefore Sig can
1017 // still be null in some circumstance.
1018 assert(!isa<FunctionSymbol>(sym));
1019 }
1020 }
1021 }
1022}
1023
1024DefinedFunction *SymbolTable::createUndefinedStub(const WasmSignature &sig) {
1025 if (auto it = stubFunctions.find(Val: sig); it != stubFunctions.end())
1026 return it->second;
1027 LLVM_DEBUG(dbgs() << "createUndefinedStub: " << toString(sig) << "\n");
1028 auto *sym = reinterpret_cast<DefinedFunction *>(make<SymbolUnion>());
1029 sym->isUsedInRegularObj = true;
1030 sym->canInline = true;
1031 sym->traced = false;
1032 sym->forceExport = false;
1033 sym->signature = &sig;
1034 replaceSymbol<DefinedFunction>(
1035 s: sym, arg: "undefined_stub", arg: WASM_SYMBOL_VISIBILITY_HIDDEN, arg: nullptr, arg: nullptr);
1036 replaceWithUnreachable(sym, sig, debugName: "undefined_stub");
1037 stubFunctions[sig] = sym;
1038 return sym;
1039}
1040
1041// Remove any variant symbols that were created due to function signature
1042// mismatches.
1043void SymbolTable::handleSymbolVariants() {
1044 for (auto pair : symVariants) {
1045 // Push the initial symbol onto the list of variants.
1046 StringRef symName = pair.first.val();
1047 std::vector<Symbol *> &variants = pair.second;
1048
1049#ifndef NDEBUG
1050 LLVM_DEBUG(dbgs() << "symbol with (" << variants.size()
1051 << ") variants: " << symName << "\n");
1052 for (auto *s: variants) {
1053 auto *f = cast<FunctionSymbol>(s);
1054 LLVM_DEBUG(dbgs() << " variant: " + f->getName() << " "
1055 << toString(*f->signature) << "\n");
1056 }
1057#endif
1058
1059 // Find the one definition.
1060 DefinedFunction *defined = nullptr;
1061 for (auto *symbol : variants) {
1062 if (auto f = dyn_cast<DefinedFunction>(Val: symbol)) {
1063 defined = f;
1064 break;
1065 }
1066 }
1067
1068 // If there are no definitions, and the undefined symbols disagree on
1069 // the signature, there is not we can do since we don't know which one
1070 // to use as the signature on the import.
1071 if (!defined) {
1072 reportFunctionSignatureMismatch(symName,
1073 a: cast<FunctionSymbol>(Val: variants[0]),
1074 b: cast<FunctionSymbol>(Val: variants[1]));
1075 return;
1076 }
1077
1078 for (auto *symbol : variants) {
1079 if (symbol != defined) {
1080 auto *f = cast<FunctionSymbol>(Val: symbol);
1081 reportFunctionSignatureMismatch(symName, a: f, b: defined, isError: false);
1082 StringRef debugName =
1083 saver().save(S: "signature_mismatch:" + toString(sym: *f));
1084 replaceWithUnreachable(sym: f, sig: *f->signature, debugName);
1085 }
1086 }
1087 }
1088}
1089
1090} // namespace wasm::lld
1091