1//===- SymbolTable.h --------------------------------------------*- C++ -*-===//
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#ifndef LLD_WASM_SYMBOL_TABLE_H
10#define LLD_WASM_SYMBOL_TABLE_H
11
12#include "InputFiles.h"
13#include "LTO.h"
14#include "Symbols.h"
15#include "lld/Common/LLVM.h"
16#include "llvm/ADT/CachedHashString.h"
17#include "llvm/ADT/DenseSet.h"
18#include "llvm/BinaryFormat/WasmTraits.h"
19#include <optional>
20
21namespace lld::wasm {
22
23class InputSegment;
24
25// SymbolTable is a bucket of all known symbols, including defined,
26// undefined, or lazy symbols (the last one is symbols in archive
27// files whose archive members are not yet loaded).
28//
29// We put all symbols of all files to a SymbolTable, and the
30// SymbolTable selects the "best" symbols if there are name
31// conflicts. For example, obviously, a defined symbol is better than
32// an undefined symbol. Or, if there's a conflict between a lazy and a
33// undefined, it'll read an archive member to read a real definition
34// to replace the lazy symbol. The logic is implemented in the
35// add*() functions, which are called by input files as they are parsed.
36// There is one add* function per symbol type.
37class SymbolTable {
38public:
39 ArrayRef<Symbol *> symbols() const { return symVector; }
40
41 void wrap(Symbol *sym, Symbol *real, Symbol *wrap);
42
43 void addFile(InputFile *file, StringRef symName = {});
44
45 void compileBitcodeFiles();
46
47 Symbol *find(StringRef name);
48
49 void replace(StringRef name, Symbol *sym);
50
51 void trace(StringRef name);
52
53 Symbol *addSharedFunction(StringRef name, uint32_t flags, InputFile *file,
54 const WasmSignature *sig);
55 Symbol *addSharedData(StringRef name, uint32_t flags, InputFile *file);
56 Symbol *addSharedTag(StringRef name, uint32_t flags, InputFile *file,
57 const WasmSignature *sig);
58 Symbol *addCommon(StringRef name, uint32_t flags, InputFile *file,
59 uint64_t size, uint32_t alignment);
60 Symbol *addDefinedFunction(StringRef name, uint32_t flags, InputFile *file,
61 InputFunction *function);
62 Symbol *addDefinedData(StringRef name, uint32_t flags, InputFile *file,
63 InputChunk *segment, uint64_t address, uint64_t size);
64 Symbol *addDefinedGlobal(StringRef name, uint32_t flags, InputFile *file,
65 InputGlobal *g);
66 Symbol *addDefinedTag(StringRef name, uint32_t flags, InputFile *file,
67 InputTag *t);
68 Symbol *addDefinedTable(StringRef name, uint32_t flags, InputFile *file,
69 InputTable *t);
70
71 Symbol *addUndefinedFunction(StringRef name,
72 std::optional<StringRef> importName,
73 std::optional<StringRef> importModule,
74 uint32_t flags, InputFile *file,
75 const WasmSignature *signature,
76 bool isCalledDirectly);
77 Symbol *addUndefinedData(StringRef name, uint32_t flags, InputFile *file);
78 Symbol *addUndefinedGlobal(StringRef name,
79 std::optional<StringRef> importName,
80 std::optional<StringRef> importModule,
81 uint32_t flags, InputFile *file,
82 const WasmGlobalType *type);
83 Symbol *addUndefinedTable(StringRef name, std::optional<StringRef> importName,
84 std::optional<StringRef> importModule,
85 uint32_t flags, InputFile *file,
86 const WasmTableType *type);
87 Symbol *addUndefinedTag(StringRef name, std::optional<StringRef> importName,
88 std::optional<StringRef> importModule, uint32_t flags,
89 InputFile *file, const WasmSignature *sig);
90
91 TableSymbol *resolveIndirectFunctionTable(bool required);
92
93 void addLazy(StringRef name, InputFile *f);
94
95 bool addComdat(StringRef name);
96
97 DefinedData *addSyntheticDataSymbol(StringRef name, uint32_t flags);
98 DefinedGlobal *addSyntheticGlobal(StringRef name, uint32_t flags,
99 InputGlobal *global);
100 DefinedFunction *addSyntheticFunction(StringRef name, uint32_t flags,
101 InputFunction *function);
102 DefinedData *addOptionalDataSymbol(StringRef name, uint64_t value = 0);
103 DefinedGlobal *addOptionalGlobalSymbol(StringRef name, InputGlobal *global);
104 DefinedTable *addSyntheticTable(StringRef name, uint32_t flags,
105 InputTable *global);
106
107 void handleSymbolVariants();
108 void handleWeakUndefines();
109 DefinedFunction *createUndefinedStub(const WasmSignature &sig);
110
111private:
112 std::pair<Symbol *, bool> insert(StringRef name, const InputFile *file);
113 std::pair<Symbol *, bool> insertName(StringRef name);
114
115 bool getFunctionVariant(Symbol *sym, const WasmSignature *sig,
116 const InputFile *file, Symbol **out);
117 InputFunction *replaceWithUnreachable(Symbol *sym, const WasmSignature &sig,
118 StringRef debugName);
119 void replaceWithUndefined(Symbol *sym);
120
121 TableSymbol *createDefinedIndirectFunctionTable(StringRef name);
122 TableSymbol *createUndefinedIndirectFunctionTable(StringRef name);
123
124 // Maps symbol names to index into the symVector. -1 means that symbols
125 // is to not yet in the vector but it should have tracing enabled if it is
126 // ever added.
127 llvm::DenseMap<llvm::CachedHashStringRef, int> symMap;
128 std::vector<Symbol *> symVector;
129
130 // For certain symbols types, e.g. function symbols, we allow for multiple
131 // variants of the same symbol with different signatures.
132 llvm::DenseMap<llvm::CachedHashStringRef, std::vector<Symbol *>> symVariants;
133 llvm::DenseMap<WasmSignature, DefinedFunction *> stubFunctions;
134
135 // Comdat groups define "link once" sections. If two comdat groups have the
136 // same name, only one of them is linked, and the other is ignored. This set
137 // is used to uniquify them.
138 llvm::DenseSet<llvm::CachedHashStringRef> comdatGroups;
139
140 // For LTO.
141 std::unique_ptr<BitcodeCompiler> lto;
142};
143
144extern SymbolTable *symtab;
145
146} // namespace lld::wasm
147
148#endif
149