1c94d393aSSam Clegg //===- SymbolTable.cpp ----------------------------------------------------===//
2c94d393aSSam Clegg //
32946cd70SChandler Carruth // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
42946cd70SChandler Carruth // See https://llvm.org/LICENSE.txt for license information.
52946cd70SChandler Carruth // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6c94d393aSSam Clegg //
7c94d393aSSam Clegg //===----------------------------------------------------------------------===//
8c94d393aSSam Clegg 
9c94d393aSSam Clegg #include "SymbolTable.h"
10c94d393aSSam Clegg #include "Config.h"
115fa274beSSam Clegg #include "InputChunks.h"
12e915a71fSHeejin Ahn #include "InputEvent.h"
1393102974SSam Clegg #include "InputGlobal.h"
14b8621596SSam Clegg #include "WriterUtils.h"
15c94d393aSSam Clegg #include "lld/Common/ErrorHandler.h"
162017d52bSRui Ueyama #include "lld/Common/Memory.h"
177d67dd11SRui Ueyama #include "llvm/ADT/SetVector.h"
18c94d393aSSam Clegg 
19c94d393aSSam Clegg #define DEBUG_TYPE "lld"
20c94d393aSSam Clegg 
21c94d393aSSam Clegg using namespace llvm;
2220db381bSSam Clegg using namespace llvm::wasm;
2345218f4aSSam Clegg using namespace llvm::object;
24c94d393aSSam Clegg using namespace lld;
25c94d393aSSam Clegg using namespace lld::wasm;
26c94d393aSSam Clegg 
27c94d393aSSam Clegg SymbolTable *lld::wasm::Symtab;
28c94d393aSSam Clegg 
29c94d393aSSam Clegg void SymbolTable::addFile(InputFile *File) {
30c94d393aSSam Clegg   log("Processing: " + toString(File));
31*a282a61bSSam Clegg 
32*a282a61bSSam Clegg   // .a file
33*a282a61bSSam Clegg   if (auto *F = dyn_cast<ArchiveFile>(File)) {
34*a282a61bSSam Clegg     F->parse();
35*a282a61bSSam Clegg     return;
36*a282a61bSSam Clegg   }
37*a282a61bSSam Clegg 
38*a282a61bSSam Clegg   // .so file
39*a282a61bSSam Clegg   if (auto *F = dyn_cast<SharedFile>(File)) {
40*a282a61bSSam Clegg     SharedFiles.push_back(F);
41*a282a61bSSam Clegg     return;
42*a282a61bSSam Clegg   }
43*a282a61bSSam Clegg 
441f3f774fSSam Clegg   if (Config->Trace)
451f3f774fSSam Clegg     message(toString(File));
46c94d393aSSam Clegg 
47c729c1b4SSam Clegg   // LLVM bitcode file
48*a282a61bSSam Clegg   if (auto *F = dyn_cast<BitcodeFile>(File)) {
49*a282a61bSSam Clegg     F->parse();
50c729c1b4SSam Clegg     BitcodeFiles.push_back(F);
51*a282a61bSSam Clegg     return;
52*a282a61bSSam Clegg   }
53*a282a61bSSam Clegg 
54*a282a61bSSam Clegg   // Regular object file
55*a282a61bSSam Clegg   auto *F = cast<ObjFile>(File);
56*a282a61bSSam Clegg   F->parse(false);
57c94d393aSSam Clegg   ObjectFiles.push_back(F);
58c94d393aSSam Clegg }
59c94d393aSSam Clegg 
60c729c1b4SSam Clegg // This function is where all the optimizations of link-time
61c729c1b4SSam Clegg // optimization happens. When LTO is in use, some input files are
62c729c1b4SSam Clegg // not in native object file format but in the LLVM bitcode format.
63c729c1b4SSam Clegg // This function compiles bitcode files into a few big native files
64c729c1b4SSam Clegg // using LLVM functions and replaces bitcode symbols with the results.
65c729c1b4SSam Clegg // Because all bitcode files that the program consists of are passed
66c729c1b4SSam Clegg // to the compiler at once, it can do whole-program optimization.
67c729c1b4SSam Clegg void SymbolTable::addCombinedLTOObject() {
68c729c1b4SSam Clegg   if (BitcodeFiles.empty())
69c729c1b4SSam Clegg     return;
70c729c1b4SSam Clegg 
71c729c1b4SSam Clegg   // Compile bitcode files and replace bitcode symbols.
72c729c1b4SSam Clegg   LTO.reset(new BitcodeCompiler);
73c729c1b4SSam Clegg   for (BitcodeFile *F : BitcodeFiles)
74c729c1b4SSam Clegg     LTO->add(*F);
75c729c1b4SSam Clegg 
76c729c1b4SSam Clegg   for (StringRef Filename : LTO->compile()) {
770cfaa247SSam Clegg     auto *Obj = make<ObjFile>(MemoryBufferRef(Filename, "lto.tmp"), "");
78697f2149SSam Clegg     Obj->parse(true);
79c729c1b4SSam Clegg     ObjectFiles.push_back(Obj);
80c729c1b4SSam Clegg   }
81c729c1b4SSam Clegg }
82c729c1b4SSam Clegg 
83c94d393aSSam Clegg void SymbolTable::reportRemainingUndefines() {
84a5ca34e6SSam Clegg   for (const auto& Pair : SymMap) {
85a5ca34e6SSam Clegg     const Symbol *Sym = SymVector[Pair.second];
86c729c1b4SSam Clegg     if (!Sym->isUndefined() || Sym->isWeak())
87c729c1b4SSam Clegg       continue;
88c729c1b4SSam Clegg     if (Config->AllowUndefinedSymbols.count(Sym->getName()) != 0)
89c729c1b4SSam Clegg       continue;
90c729c1b4SSam Clegg     if (!Sym->IsUsedInRegularObj)
91c729c1b4SSam Clegg       continue;
9247e2b6b2SSam Clegg     error(toString(Sym->getFile()) + ": undefined symbol: " + toString(*Sym));
93c94d393aSSam Clegg   }
94c94d393aSSam Clegg }
95c94d393aSSam Clegg 
96c94d393aSSam Clegg Symbol *SymbolTable::find(StringRef Name) {
971f3f774fSSam Clegg   auto It = SymMap.find(CachedHashStringRef(Name));
981f3f774fSSam Clegg   if (It == SymMap.end() || It->second == -1)
991f3f774fSSam Clegg     return nullptr;
1001f3f774fSSam Clegg   return SymVector[It->second];
1011f3f774fSSam Clegg }
1021f3f774fSSam Clegg 
1036540e570SSam Clegg void SymbolTable::replace(StringRef Name, Symbol* Sym) {
1046540e570SSam Clegg   auto It = SymMap.find(CachedHashStringRef(Name));
1056540e570SSam Clegg   SymVector[It->second] = Sym;
1066540e570SSam Clegg }
1076540e570SSam Clegg 
1081f3f774fSSam Clegg std::pair<Symbol *, bool> SymbolTable::insertName(StringRef Name) {
1091f3f774fSSam Clegg   bool Trace = false;
1101f3f774fSSam Clegg   auto P = SymMap.insert({CachedHashStringRef(Name), (int)SymVector.size()});
1111f3f774fSSam Clegg   int &SymIndex = P.first->second;
1121f3f774fSSam Clegg   bool IsNew = P.second;
1131f3f774fSSam Clegg   if (SymIndex == -1) {
1141f3f774fSSam Clegg     SymIndex = SymVector.size();
1151f3f774fSSam Clegg     Trace = true;
1161f3f774fSSam Clegg     IsNew = true;
1171f3f774fSSam Clegg   }
1181f3f774fSSam Clegg 
1191f3f774fSSam Clegg   if (!IsNew)
1201f3f774fSSam Clegg     return {SymVector[SymIndex], false};
1211f3f774fSSam Clegg 
1221f3f774fSSam Clegg   Symbol *Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
1231f3f774fSSam Clegg   Sym->IsUsedInRegularObj = false;
124a5ca34e6SSam Clegg   Sym->CanInline = true;
1251f3f774fSSam Clegg   Sym->Traced = Trace;
1261f3f774fSSam Clegg   SymVector.emplace_back(Sym);
1271f3f774fSSam Clegg   return {Sym, true};
128c94d393aSSam Clegg }
129c94d393aSSam Clegg 
130230dc11dSSam Clegg std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name,
131230dc11dSSam Clegg                                               const InputFile *File) {
1321f3f774fSSam Clegg   Symbol *S;
1331f3f774fSSam Clegg   bool WasInserted;
1341f3f774fSSam Clegg   std::tie(S, WasInserted) = insertName(Name);
1351f3f774fSSam Clegg 
1364c2cbfe6SSam Clegg   if (!File || File->kind() == InputFile::ObjectKind)
1371f3f774fSSam Clegg     S->IsUsedInRegularObj = true;
1381f3f774fSSam Clegg 
1391f3f774fSSam Clegg   return {S, WasInserted};
140c94d393aSSam Clegg }
141c94d393aSSam Clegg 
142e3498ec5SRui Ueyama static void reportTypeError(const Symbol *Existing, const InputFile *File,
1433876d89aSSam Clegg                             llvm::wasm::WasmSymbolType Type) {
144e3498ec5SRui Ueyama   error("symbol type mismatch: " + toString(*Existing) + "\n>>> defined as " +
145e3498ec5SRui Ueyama         toString(Existing->getWasmType()) + " in " +
1463876d89aSSam Clegg         toString(Existing->getFile()) + "\n>>> defined as " + toString(Type) +
1473876d89aSSam Clegg         " in " + toString(File));
148e3498ec5SRui Ueyama }
149e3498ec5SRui Ueyama 
1506f4286fbSHeejin Ahn // Check the type of new symbol matches that of the symbol is replacing.
1516540e570SSam Clegg // Returns true if the function types match, false is there is a singature
1526540e570SSam Clegg // mismatch.
153ba2ea93aSBenjamin Kramer static bool signatureMatches(FunctionSymbol *Existing,
154ba2ea93aSBenjamin Kramer                              const WasmSignature *NewSig) {
1556540e570SSam Clegg   const WasmSignature *OldSig = Existing->Signature;
156d506b0a4SSam Clegg 
157d506b0a4SSam Clegg   // If either function is missing a signature (this happend for bitcode
158d506b0a4SSam Clegg   // symbols) then assume they match.  Any mismatch will be reported later
159d506b0a4SSam Clegg   // when the LTO objects are added.
160d506b0a4SSam Clegg   if (!NewSig || !OldSig)
1616540e570SSam Clegg     return true;
162cefbf9acSSam Clegg 
1636540e570SSam Clegg   return *NewSig == *OldSig;
164e3498ec5SRui Ueyama }
165e3498ec5SRui Ueyama 
166e3498ec5SRui Ueyama static void checkGlobalType(const Symbol *Existing, const InputFile *File,
167e3498ec5SRui Ueyama                             const WasmGlobalType *NewType) {
168e3498ec5SRui Ueyama   if (!isa<GlobalSymbol>(Existing)) {
1693876d89aSSam Clegg     reportTypeError(Existing, File, WASM_SYMBOL_TYPE_GLOBAL);
170b8621596SSam Clegg     return;
171b8621596SSam Clegg   }
172b8621596SSam Clegg 
173e3498ec5SRui Ueyama   const WasmGlobalType *OldType = cast<GlobalSymbol>(Existing)->getGlobalType();
174e3498ec5SRui Ueyama   if (*NewType != *OldType) {
175e3498ec5SRui Ueyama     error("Global type mismatch: " + Existing->getName() + "\n>>> defined as " +
176e3498ec5SRui Ueyama           toString(*OldType) + " in " + toString(Existing->getFile()) +
177e3498ec5SRui Ueyama           "\n>>> defined as " + toString(*NewType) + " in " + toString(File));
178c94d393aSSam Clegg   }
17924b3dcd4SSam Clegg }
18024b3dcd4SSam Clegg 
181e915a71fSHeejin Ahn static void checkEventType(const Symbol *Existing, const InputFile *File,
182e915a71fSHeejin Ahn                            const WasmEventType *NewType,
183e915a71fSHeejin Ahn                            const WasmSignature *NewSig) {
184e915a71fSHeejin Ahn   auto ExistingEvent = dyn_cast<EventSymbol>(Existing);
185e915a71fSHeejin Ahn   if (!isa<EventSymbol>(Existing)) {
186e915a71fSHeejin Ahn     reportTypeError(Existing, File, WASM_SYMBOL_TYPE_EVENT);
187e915a71fSHeejin Ahn     return;
188e915a71fSHeejin Ahn   }
189e915a71fSHeejin Ahn 
190e915a71fSHeejin Ahn   const WasmEventType *OldType = cast<EventSymbol>(Existing)->getEventType();
191e915a71fSHeejin Ahn   const WasmSignature *OldSig = ExistingEvent->Signature;
192e915a71fSHeejin Ahn   if (NewType->Attribute != OldType->Attribute)
193e915a71fSHeejin Ahn     error("Event type mismatch: " + Existing->getName() + "\n>>> defined as " +
194e915a71fSHeejin Ahn           toString(*OldType) + " in " + toString(Existing->getFile()) +
195e915a71fSHeejin Ahn           "\n>>> defined as " + toString(*NewType) + " in " + toString(File));
196e915a71fSHeejin Ahn   if (*NewSig != *OldSig)
197e915a71fSHeejin Ahn     warn("Event signature mismatch: " + Existing->getName() +
198e915a71fSHeejin Ahn          "\n>>> defined as " + toString(*OldSig) + " in " +
199e915a71fSHeejin Ahn          toString(Existing->getFile()) + "\n>>> defined as " +
200e915a71fSHeejin Ahn          toString(*NewSig) + " in " + toString(File));
201e915a71fSHeejin Ahn }
202e915a71fSHeejin Ahn 
203e3498ec5SRui Ueyama static void checkDataType(const Symbol *Existing, const InputFile *File) {
204e3498ec5SRui Ueyama   if (!isa<DataSymbol>(Existing))
2053876d89aSSam Clegg     reportTypeError(Existing, File, WASM_SYMBOL_TYPE_DATA);
206e3498ec5SRui Ueyama }
207e3498ec5SRui Ueyama 
208dfb0b2c7SSam Clegg DefinedFunction *SymbolTable::addSyntheticFunction(StringRef Name,
209ebda41f8SNicholas Wilson                                                    uint32_t Flags,
210ebda41f8SNicholas Wilson                                                    InputFunction *Function) {
211e7245b42SNicola Zaghen   LLVM_DEBUG(dbgs() << "addSyntheticFunction: " << Name << "\n");
212b961abc8SRui Ueyama   assert(!find(Name));
213ebda41f8SNicholas Wilson   SyntheticFunctions.emplace_back(Function);
214d15a4154SSam Clegg   return replaceSymbol<DefinedFunction>(insertName(Name).first, Name,
2154c2cbfe6SSam Clegg                                         Flags, nullptr, Function);
21650686856SSam Clegg }
21750686856SSam Clegg 
2188e8ddaa3SSam Clegg // Adds an optional, linker generated, data symbols.  The symbol will only be
2198e8ddaa3SSam Clegg // added if there is an undefine reference to it, or if it is explictly exported
2208e8ddaa3SSam Clegg // via the --export flag.  Otherwise we don't add the symbol and return nullptr.
2214bce63a0SSam Clegg DefinedData *SymbolTable::addOptionalDataSymbol(StringRef Name, uint32_t Value,
2224bce63a0SSam Clegg                                                 uint32_t Flags) {
2234bce63a0SSam Clegg   Symbol *S = find(Name);
2247d4ec5afSSam Clegg   if (!S && (Config->ExportAll || Config->ExportedSymbols.count(Name) != 0))
2257d4ec5afSSam Clegg     S = insertName(Name).first;
2267d4ec5afSSam Clegg   else if (!S || S->isDefined())
2274bce63a0SSam Clegg     return nullptr;
2284bce63a0SSam Clegg   LLVM_DEBUG(dbgs() << "addOptionalDataSymbol: " << Name << "\n");
2294bce63a0SSam Clegg   auto *rtn = replaceSymbol<DefinedData>(S, Name, Flags);
2304bce63a0SSam Clegg   rtn->setVirtualAddress(Value);
2314bce63a0SSam Clegg   return rtn;
2324bce63a0SSam Clegg }
2334bce63a0SSam Clegg 
23400245539SSam Clegg DefinedData *SymbolTable::addSyntheticDataSymbol(StringRef Name,
23500245539SSam Clegg                                                  uint32_t Flags) {
236e7245b42SNicola Zaghen   LLVM_DEBUG(dbgs() << "addSyntheticDataSymbol: " << Name << "\n");
237b961abc8SRui Ueyama   assert(!find(Name));
238d15a4154SSam Clegg   return replaceSymbol<DefinedData>(insertName(Name).first, Name, Flags);
239c94d393aSSam Clegg }
240c94d393aSSam Clegg 
24193102974SSam Clegg DefinedGlobal *SymbolTable::addSyntheticGlobal(StringRef Name, uint32_t Flags,
24293102974SSam Clegg                                                InputGlobal *Global) {
243e7245b42SNicola Zaghen   LLVM_DEBUG(dbgs() << "addSyntheticGlobal: " << Name << " -> " << Global
244e7245b42SNicola Zaghen                     << "\n");
245b961abc8SRui Ueyama   assert(!find(Name));
246ebda41f8SNicholas Wilson   SyntheticGlobals.emplace_back(Global);
247d15a4154SSam Clegg   return replaceSymbol<DefinedGlobal>(insertName(Name).first, Name, Flags,
2484c2cbfe6SSam Clegg                                       nullptr, Global);
24993102974SSam Clegg }
25093102974SSam Clegg 
251e3498ec5SRui Ueyama static bool shouldReplace(const Symbol *Existing, InputFile *NewFile,
252e3498ec5SRui Ueyama                           uint32_t NewFlags) {
253c03c9040SRui Ueyama   // If existing symbol is undefined, replace it.
254e3498ec5SRui Ueyama   if (!Existing->isDefined()) {
255e7245b42SNicola Zaghen     LLVM_DEBUG(dbgs() << "resolving existing undefined symbol: "
256e3498ec5SRui Ueyama                       << Existing->getName() << "\n");
257c03c9040SRui Ueyama     return true;
258c03c9040SRui Ueyama   }
259c03c9040SRui Ueyama 
260c03c9040SRui Ueyama   // Now we have two defined symbols. If the new one is weak, we can ignore it.
261c03c9040SRui Ueyama   if ((NewFlags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) {
262e7245b42SNicola Zaghen     LLVM_DEBUG(dbgs() << "existing symbol takes precedence\n");
263c03c9040SRui Ueyama     return false;
264c03c9040SRui Ueyama   }
265c03c9040SRui Ueyama 
266c03c9040SRui Ueyama   // If the existing symbol is weak, we should replace it.
267e3498ec5SRui Ueyama   if (Existing->isWeak()) {
268e7245b42SNicola Zaghen     LLVM_DEBUG(dbgs() << "replacing existing weak symbol\n");
269c03c9040SRui Ueyama     return true;
270c03c9040SRui Ueyama   }
271c03c9040SRui Ueyama 
272c03c9040SRui Ueyama   // Neither symbol is week. They conflict.
273e3498ec5SRui Ueyama   error("duplicate symbol: " + toString(*Existing) + "\n>>> defined in " +
274e3498ec5SRui Ueyama         toString(Existing->getFile()) + "\n>>> defined in " +
275e3498ec5SRui Ueyama         toString(NewFile));
276c03c9040SRui Ueyama   return true;
277b8621596SSam Clegg }
27893e559b1SSam Clegg 
27993e559b1SSam Clegg Symbol *SymbolTable::addDefinedFunction(StringRef Name, uint32_t Flags,
280e3498ec5SRui Ueyama                                         InputFile *File,
281e3498ec5SRui Ueyama                                         InputFunction *Function) {
2828b0b48f3SSam Clegg   LLVM_DEBUG(dbgs() << "addDefinedFunction: " << Name << " ["
2838b0b48f3SSam Clegg                     << (Function ? toString(Function->Signature) : "none")
2848b0b48f3SSam Clegg                     << "]\n");
28593e559b1SSam Clegg   Symbol *S;
28693e559b1SSam Clegg   bool WasInserted;
2874c2cbfe6SSam Clegg   std::tie(S, WasInserted) = insert(Name, File);
288c729c1b4SSam Clegg 
2896540e570SSam Clegg   auto Replace = [&](Symbol* Sym) {
2906540e570SSam Clegg     // If the new defined function doesn't have signture (i.e. bitcode
2916540e570SSam Clegg     // functions) but the old symbol does, then preserve the old signature
2926540e570SSam Clegg     const WasmSignature *OldSig = S->getSignature();
2936540e570SSam Clegg     auto* NewSym = replaceSymbol<DefinedFunction>(Sym, Name, Flags, File, Function);
2946540e570SSam Clegg     if (!NewSym->Signature)
2956540e570SSam Clegg       NewSym->Signature = OldSig;
2966540e570SSam Clegg   };
2976540e570SSam Clegg 
298e3498ec5SRui Ueyama   if (WasInserted || S->isLazy()) {
2996540e570SSam Clegg     Replace(S);
300e3498ec5SRui Ueyama     return S;
301e3498ec5SRui Ueyama   }
302e3498ec5SRui Ueyama 
3036540e570SSam Clegg   auto ExistingFunction = dyn_cast<FunctionSymbol>(S);
3046540e570SSam Clegg   if (!ExistingFunction) {
3056540e570SSam Clegg     reportTypeError(S, File, WASM_SYMBOL_TYPE_FUNCTION);
3066540e570SSam Clegg     return S;
3078b0b48f3SSam Clegg   }
3086540e570SSam Clegg 
30959f959ffSSam Clegg   bool CheckSig = true;
31059f959ffSSam Clegg   if (auto UD = dyn_cast<UndefinedFunction>(ExistingFunction))
31159f959ffSSam Clegg     CheckSig = UD->IsCalledDirectly;
31259f959ffSSam Clegg 
31359f959ffSSam Clegg   if (CheckSig && Function && !signatureMatches(ExistingFunction, &Function->Signature)) {
3146540e570SSam Clegg     Symbol* Variant;
3156540e570SSam Clegg     if (getFunctionVariant(S, &Function->Signature, File, &Variant))
3166540e570SSam Clegg       // New variant, always replace
3176540e570SSam Clegg       Replace(Variant);
3186540e570SSam Clegg     else if (shouldReplace(S, File, Flags))
3196540e570SSam Clegg       // Variant already exists, replace it after checking shouldReplace
3206540e570SSam Clegg       Replace(Variant);
3216540e570SSam Clegg 
3226540e570SSam Clegg     // This variant we found take the place in the symbol table as the primary
3236540e570SSam Clegg     // variant.
3246540e570SSam Clegg     replace(Name, Variant);
3256540e570SSam Clegg     return Variant;
3266540e570SSam Clegg   }
3276540e570SSam Clegg 
3286540e570SSam Clegg   // Existing function with matching signature.
3296540e570SSam Clegg   if (shouldReplace(S, File, Flags))
3306540e570SSam Clegg     Replace(S);
3316540e570SSam Clegg 
33293e559b1SSam Clegg   return S;
33393e559b1SSam Clegg }
33493e559b1SSam Clegg 
33500245539SSam Clegg Symbol *SymbolTable::addDefinedData(StringRef Name, uint32_t Flags,
336e3498ec5SRui Ueyama                                     InputFile *File, InputSegment *Segment,
33793102974SSam Clegg                                     uint32_t Address, uint32_t Size) {
338e7245b42SNicola Zaghen   LLVM_DEBUG(dbgs() << "addDefinedData:" << Name << " addr:" << Address
339e7245b42SNicola Zaghen                     << "\n");
34093e559b1SSam Clegg   Symbol *S;
34193e559b1SSam Clegg   bool WasInserted;
3424c2cbfe6SSam Clegg   std::tie(S, WasInserted) = insert(Name, File);
343c729c1b4SSam Clegg 
3446540e570SSam Clegg   auto Replace = [&]() {
345e3498ec5SRui Ueyama     replaceSymbol<DefinedData>(S, Name, Flags, File, Segment, Address, Size);
3466540e570SSam Clegg   };
3476540e570SSam Clegg 
3486540e570SSam Clegg   if (WasInserted || S->isLazy()) {
3496540e570SSam Clegg     Replace();
350e3498ec5SRui Ueyama     return S;
351e3498ec5SRui Ueyama   }
352e3498ec5SRui Ueyama 
353e3498ec5SRui Ueyama   checkDataType(S, File);
354e3498ec5SRui Ueyama 
355e3498ec5SRui Ueyama   if (shouldReplace(S, File, Flags))
3566540e570SSam Clegg     Replace();
357c94d393aSSam Clegg   return S;
358c94d393aSSam Clegg }
359c94d393aSSam Clegg 
36093102974SSam Clegg Symbol *SymbolTable::addDefinedGlobal(StringRef Name, uint32_t Flags,
361e3498ec5SRui Ueyama                                       InputFile *File, InputGlobal *Global) {
362e7245b42SNicola Zaghen   LLVM_DEBUG(dbgs() << "addDefinedGlobal:" << Name << "\n");
3634c2cbfe6SSam Clegg 
36493102974SSam Clegg   Symbol *S;
36593102974SSam Clegg   bool WasInserted;
3664c2cbfe6SSam Clegg   std::tie(S, WasInserted) = insert(Name, File);
367c729c1b4SSam Clegg 
3686540e570SSam Clegg   auto Replace = [&]() {
369e3498ec5SRui Ueyama     replaceSymbol<DefinedGlobal>(S, Name, Flags, File, Global);
3706540e570SSam Clegg   };
3716540e570SSam Clegg 
3726540e570SSam Clegg   if (WasInserted || S->isLazy()) {
3736540e570SSam Clegg     Replace();
37493102974SSam Clegg     return S;
37593102974SSam Clegg   }
37693102974SSam Clegg 
377e3498ec5SRui Ueyama   checkGlobalType(S, File, &Global->getType());
378e3498ec5SRui Ueyama 
379e3498ec5SRui Ueyama   if (shouldReplace(S, File, Flags))
3806540e570SSam Clegg     Replace();
381e3498ec5SRui Ueyama   return S;
382e3498ec5SRui Ueyama }
383e3498ec5SRui Ueyama 
384e915a71fSHeejin Ahn Symbol *SymbolTable::addDefinedEvent(StringRef Name, uint32_t Flags,
385e915a71fSHeejin Ahn                                      InputFile *File, InputEvent *Event) {
386e915a71fSHeejin Ahn   LLVM_DEBUG(dbgs() << "addDefinedEvent:" << Name << "\n");
387e915a71fSHeejin Ahn 
388e915a71fSHeejin Ahn   Symbol *S;
389e915a71fSHeejin Ahn   bool WasInserted;
390e915a71fSHeejin Ahn   std::tie(S, WasInserted) = insert(Name, File);
391e915a71fSHeejin Ahn 
3926540e570SSam Clegg   auto Replace = [&]() {
393e915a71fSHeejin Ahn     replaceSymbol<DefinedEvent>(S, Name, Flags, File, Event);
3946540e570SSam Clegg   };
3956540e570SSam Clegg 
3966540e570SSam Clegg   if (WasInserted || S->isLazy()) {
3976540e570SSam Clegg     Replace();
398e915a71fSHeejin Ahn     return S;
399e915a71fSHeejin Ahn   }
400e915a71fSHeejin Ahn 
401e915a71fSHeejin Ahn   checkEventType(S, File, &Event->getType(), &Event->Signature);
402e915a71fSHeejin Ahn 
403e915a71fSHeejin Ahn   if (shouldReplace(S, File, Flags))
4046540e570SSam Clegg     Replace();
405e915a71fSHeejin Ahn   return S;
406e915a71fSHeejin Ahn }
407e915a71fSHeejin Ahn 
4089b84eeaaSDan Gohman Symbol *SymbolTable::addUndefinedFunction(StringRef Name, StringRef ImportName,
4099b84eeaaSDan Gohman                                           StringRef ImportModule,
4107cc07531SSam Clegg                                           uint32_t Flags, InputFile *File,
41159f959ffSSam Clegg                                           const WasmSignature *Sig,
41259f959ffSSam Clegg                                           bool IsCalledDirectly) {
413d506b0a4SSam Clegg   LLVM_DEBUG(dbgs() << "addUndefinedFunction: " << Name << " ["
414d506b0a4SSam Clegg                     << (Sig ? toString(*Sig) : "none")
415d506b0a4SSam Clegg                     << "] IsCalledDirectly:" << IsCalledDirectly << "\n");
416c03c9040SRui Ueyama 
417c94d393aSSam Clegg   Symbol *S;
418c94d393aSSam Clegg   bool WasInserted;
4194c2cbfe6SSam Clegg   std::tie(S, WasInserted) = insert(Name, File);
4207991b682SSam Clegg   if (S->Traced)
4217991b682SSam Clegg     printTraceSymbolUndefined(Name, File);
422c729c1b4SSam Clegg 
4236540e570SSam Clegg   auto Replace = [&]() {
4249b84eeaaSDan Gohman     replaceSymbol<UndefinedFunction>(S, Name, ImportName, ImportModule, Flags,
42559f959ffSSam Clegg                                      File, Sig, IsCalledDirectly);
4266540e570SSam Clegg   };
4276540e570SSam Clegg 
4286540e570SSam Clegg   if (WasInserted)
4296540e570SSam Clegg     Replace();
430e3498ec5SRui Ueyama   else if (auto *Lazy = dyn_cast<LazySymbol>(S))
431b961abc8SRui Ueyama     Lazy->fetch();
4326540e570SSam Clegg   else {
4336540e570SSam Clegg     auto ExistingFunction = dyn_cast<FunctionSymbol>(S);
4346540e570SSam Clegg     if (!ExistingFunction) {
4356540e570SSam Clegg       reportTypeError(S, File, WASM_SYMBOL_TYPE_FUNCTION);
4366540e570SSam Clegg       return S;
4376540e570SSam Clegg     }
438d506b0a4SSam Clegg     if (!ExistingFunction->Signature && Sig)
439d506b0a4SSam Clegg       ExistingFunction->Signature = Sig;
44059f959ffSSam Clegg     if (IsCalledDirectly && !signatureMatches(ExistingFunction, Sig))
4416540e570SSam Clegg       if (getFunctionVariant(S, Sig, File, &S))
4426540e570SSam Clegg         Replace();
4436540e570SSam Clegg   }
444cefbf9acSSam Clegg 
445c03c9040SRui Ueyama   return S;
446c03c9040SRui Ueyama }
447c03c9040SRui Ueyama 
448e3498ec5SRui Ueyama Symbol *SymbolTable::addUndefinedData(StringRef Name, uint32_t Flags,
449e3498ec5SRui Ueyama                                       InputFile *File) {
450e7245b42SNicola Zaghen   LLVM_DEBUG(dbgs() << "addUndefinedData: " << Name << "\n");
45193102974SSam Clegg 
452e3498ec5SRui Ueyama   Symbol *S;
453e3498ec5SRui Ueyama   bool WasInserted;
4544c2cbfe6SSam Clegg   std::tie(S, WasInserted) = insert(Name, File);
4557991b682SSam Clegg   if (S->Traced)
4567991b682SSam Clegg     printTraceSymbolUndefined(Name, File);
457f989a92dSSam Clegg 
458e3498ec5SRui Ueyama   if (WasInserted)
459e3498ec5SRui Ueyama     replaceSymbol<UndefinedData>(S, Name, Flags, File);
460e3498ec5SRui Ueyama   else if (auto *Lazy = dyn_cast<LazySymbol>(S))
461b961abc8SRui Ueyama     Lazy->fetch();
462e3498ec5SRui Ueyama   else if (S->isDefined())
463e3498ec5SRui Ueyama     checkDataType(S, File);
464c94d393aSSam Clegg   return S;
465c94d393aSSam Clegg }
466c94d393aSSam Clegg 
4679b84eeaaSDan Gohman Symbol *SymbolTable::addUndefinedGlobal(StringRef Name, StringRef ImportName,
4689b84eeaaSDan Gohman                                         StringRef ImportModule, uint32_t Flags,
469e3498ec5SRui Ueyama                                         InputFile *File,
470e3498ec5SRui Ueyama                                         const WasmGlobalType *Type) {
471e7245b42SNicola Zaghen   LLVM_DEBUG(dbgs() << "addUndefinedGlobal: " << Name << "\n");
472e3498ec5SRui Ueyama 
473e3498ec5SRui Ueyama   Symbol *S;
474e3498ec5SRui Ueyama   bool WasInserted;
4754c2cbfe6SSam Clegg   std::tie(S, WasInserted) = insert(Name, File);
4767991b682SSam Clegg   if (S->Traced)
4777991b682SSam Clegg     printTraceSymbolUndefined(Name, File);
478c729c1b4SSam Clegg 
479e3498ec5SRui Ueyama   if (WasInserted)
4809b84eeaaSDan Gohman     replaceSymbol<UndefinedGlobal>(S, Name, ImportName, ImportModule, Flags,
4819b84eeaaSDan Gohman                                    File, Type);
482e3498ec5SRui Ueyama   else if (auto *Lazy = dyn_cast<LazySymbol>(S))
483b961abc8SRui Ueyama     Lazy->fetch();
484e3498ec5SRui Ueyama   else if (S->isDefined())
485e3498ec5SRui Ueyama     checkGlobalType(S, File, Type);
486e3498ec5SRui Ueyama   return S;
487e3498ec5SRui Ueyama }
488e3498ec5SRui Ueyama 
489e3498ec5SRui Ueyama void SymbolTable::addLazy(ArchiveFile *File, const Archive::Symbol *Sym) {
490e7245b42SNicola Zaghen   LLVM_DEBUG(dbgs() << "addLazy: " << Sym->getName() << "\n");
491c94d393aSSam Clegg   StringRef Name = Sym->getName();
492c03c9040SRui Ueyama 
493c94d393aSSam Clegg   Symbol *S;
494c94d393aSSam Clegg   bool WasInserted;
495d15a4154SSam Clegg   std::tie(S, WasInserted) = insertName(Name);
496c03c9040SRui Ueyama 
497c94d393aSSam Clegg   if (WasInserted) {
49837b4ee52SSam Clegg     replaceSymbol<LazySymbol>(S, Name, 0, File, *Sym);
499c03c9040SRui Ueyama     return;
500c03c9040SRui Ueyama   }
501c03c9040SRui Ueyama 
50237b4ee52SSam Clegg   if (!S->isUndefined())
50337b4ee52SSam Clegg     return;
50437b4ee52SSam Clegg 
50537b4ee52SSam Clegg   // The existing symbol is undefined, load a new one from the archive,
50637b4ee52SSam Clegg   // unless the the existing symbol is weak in which case replace the undefined
50737b4ee52SSam Clegg   // symbols with a LazySymbol.
50837b4ee52SSam Clegg   if (S->isWeak()) {
50937b4ee52SSam Clegg     const WasmSignature *OldSig = nullptr;
51037b4ee52SSam Clegg     // In the case of an UndefinedFunction we need to preserve the expected
51137b4ee52SSam Clegg     // signature.
51237b4ee52SSam Clegg     if (auto *F = dyn_cast<UndefinedFunction>(S))
51337b4ee52SSam Clegg       OldSig = F->Signature;
51437b4ee52SSam Clegg     LLVM_DEBUG(dbgs() << "replacing existing weak undefined symbol\n");
51537b4ee52SSam Clegg     auto NewSym = replaceSymbol<LazySymbol>(S, Name, WASM_SYMBOL_BINDING_WEAK,
51637b4ee52SSam Clegg                                             File, *Sym);
51737b4ee52SSam Clegg     NewSym->Signature = OldSig;
51837b4ee52SSam Clegg     return;
51937b4ee52SSam Clegg   }
52037b4ee52SSam Clegg 
521e7245b42SNicola Zaghen   LLVM_DEBUG(dbgs() << "replacing existing undefined\n");
522e3498ec5SRui Ueyama   File->addMember(Sym);
523c94d393aSSam Clegg }
524e0f6fcd0SSam Clegg 
525c4d9aa1bSNicholas Wilson bool SymbolTable::addComdat(StringRef Name) {
526697f2149SSam Clegg   return ComdatGroups.insert(CachedHashStringRef(Name)).second;
527e0f6fcd0SSam Clegg }
5281f3f774fSSam Clegg 
5296540e570SSam Clegg // The new signature doesn't match.  Create a variant to the symbol with the
5306540e570SSam Clegg // signature encoded in the name and return that instead.  These symbols are
5316540e570SSam Clegg // then unified later in handleSymbolVariants.
5326540e570SSam Clegg bool SymbolTable::getFunctionVariant(Symbol* Sym, const WasmSignature *Sig,
5336540e570SSam Clegg                                      const InputFile *File, Symbol **Out) {
53414bab09eSRichard Trieu   LLVM_DEBUG(dbgs() << "getFunctionVariant: " << Sym->getName() << " -> "
5356540e570SSam Clegg                     << " " << toString(*Sig) << "\n");
5366540e570SSam Clegg   Symbol *Variant = nullptr;
5376540e570SSam Clegg 
5386540e570SSam Clegg   // Linear search through symbol variants.  Should never be more than two
5396540e570SSam Clegg   // or three entries here.
5406540e570SSam Clegg   auto &Variants = SymVariants[CachedHashStringRef(Sym->getName())];
541196a4404SFangrui Song   if (Variants.empty())
5426540e570SSam Clegg     Variants.push_back(Sym);
5436540e570SSam Clegg 
5446540e570SSam Clegg   for (Symbol* V : Variants) {
5456540e570SSam Clegg     if (*V->getSignature() == *Sig) {
5466540e570SSam Clegg       Variant = V;
5476540e570SSam Clegg       break;
5486540e570SSam Clegg     }
5496540e570SSam Clegg   }
5506540e570SSam Clegg 
5516540e570SSam Clegg   bool WasAdded = !Variant;
5526540e570SSam Clegg   if (WasAdded) {
5536540e570SSam Clegg     // Create a new variant;
5546540e570SSam Clegg     LLVM_DEBUG(dbgs() << "added new variant\n");
5556540e570SSam Clegg     Variant = reinterpret_cast<Symbol *>(make<SymbolUnion>());
5566540e570SSam Clegg     Variants.push_back(Variant);
5576540e570SSam Clegg   } else {
5586540e570SSam Clegg     LLVM_DEBUG(dbgs() << "variant already exists: " << toString(*Variant) << "\n");
5596540e570SSam Clegg     assert(*Variant->getSignature() == *Sig);
5606540e570SSam Clegg   }
5616540e570SSam Clegg 
5626540e570SSam Clegg   *Out = Variant;
5636540e570SSam Clegg   return WasAdded;
5646540e570SSam Clegg }
5656540e570SSam Clegg 
5661f3f774fSSam Clegg // Set a flag for --trace-symbol so that we can print out a log message
5671f3f774fSSam Clegg // if a new symbol with the same name is inserted into the symbol table.
5681f3f774fSSam Clegg void SymbolTable::trace(StringRef Name) {
5691f3f774fSSam Clegg   SymMap.insert({CachedHashStringRef(Name), -1});
5701f3f774fSSam Clegg }
571230dc11dSSam Clegg 
572a5ca34e6SSam Clegg void SymbolTable::wrap(Symbol *Sym, Symbol *Real, Symbol *Wrap) {
573a5ca34e6SSam Clegg   // Swap symbols as instructed by -wrap.
574a5ca34e6SSam Clegg   int &OrigIdx = SymMap[CachedHashStringRef(Sym->getName())];
575a5ca34e6SSam Clegg   int &RealIdx= SymMap[CachedHashStringRef(Real->getName())];
576a5ca34e6SSam Clegg   int &WrapIdx = SymMap[CachedHashStringRef(Wrap->getName())];
577a5ca34e6SSam Clegg   LLVM_DEBUG(dbgs() << "wrap: " << Sym->getName() << "\n");
578a5ca34e6SSam Clegg 
579a5ca34e6SSam Clegg   // Anyone looking up __real symbols should get the original
580a5ca34e6SSam Clegg   RealIdx = OrigIdx;
581a5ca34e6SSam Clegg   // Anyone looking up the original should get the __wrap symbol
582a5ca34e6SSam Clegg   OrigIdx = WrapIdx;
583a5ca34e6SSam Clegg }
584a5ca34e6SSam Clegg 
585230dc11dSSam Clegg static const uint8_t UnreachableFn[] = {
586230dc11dSSam Clegg     0x03 /* ULEB length */, 0x00 /* ULEB num locals */,
587230dc11dSSam Clegg     0x00 /* opcode unreachable */, 0x0b /* opcode end */
588230dc11dSSam Clegg };
589230dc11dSSam Clegg 
590230dc11dSSam Clegg // Replace the given symbol body with an unreachable function.
591230dc11dSSam Clegg // This is used by handleWeakUndefines in order to generate a callable
5926540e570SSam Clegg // equivalent of an undefined function and also handleSymbolVariants for
5936540e570SSam Clegg // undefined functions that don't match the signature of the definition.
594230dc11dSSam Clegg InputFunction *SymbolTable::replaceWithUnreachable(Symbol *Sym,
595230dc11dSSam Clegg                                                    const WasmSignature &Sig,
596230dc11dSSam Clegg                                                    StringRef DebugName) {
597230dc11dSSam Clegg   auto *Func = make<SyntheticFunction>(Sig, Sym->getName(), DebugName);
598230dc11dSSam Clegg   Func->setBody(UnreachableFn);
599230dc11dSSam Clegg   SyntheticFunctions.emplace_back(Func);
6006540e570SSam Clegg   replaceSymbol<DefinedFunction>(Sym, Sym->getName(), Sym->getFlags(), nullptr,
6016540e570SSam Clegg                                  Func);
602230dc11dSSam Clegg   return Func;
603230dc11dSSam Clegg }
604230dc11dSSam Clegg 
605230dc11dSSam Clegg // For weak undefined functions, there may be "call" instructions that reference
606230dc11dSSam Clegg // the symbol. In this case, we need to synthesise a dummy/stub function that
607230dc11dSSam Clegg // will abort at runtime, so that relocations can still provided an operand to
608230dc11dSSam Clegg // the call instruction that passes Wasm validation.
609230dc11dSSam Clegg void SymbolTable::handleWeakUndefines() {
610230dc11dSSam Clegg   for (Symbol *Sym : getSymbols()) {
611230dc11dSSam Clegg     if (!Sym->isUndefWeak())
612230dc11dSSam Clegg       continue;
613230dc11dSSam Clegg 
6146540e570SSam Clegg     const WasmSignature *Sig = Sym->getSignature();
6156540e570SSam Clegg     if (!Sig) {
616230dc11dSSam Clegg       // It is possible for undefined functions not to have a signature (eg. if
617230dc11dSSam Clegg       // added via "--undefined"), but weak undefined ones do have a signature.
6186540e570SSam Clegg       // Lazy symbols may not be functions and therefore Sig can still be null
6196540e570SSam Clegg       // in some circumstantce.
6206540e570SSam Clegg       assert(!isa<FunctionSymbol>(Sym));
621230dc11dSSam Clegg       continue;
6226540e570SSam Clegg     }
623230dc11dSSam Clegg 
624230dc11dSSam Clegg     // Add a synthetic dummy for weak undefined functions.  These dummies will
625230dc11dSSam Clegg     // be GC'd if not used as the target of any "call" instructions.
626230dc11dSSam Clegg     StringRef DebugName = Saver.save("undefined:" + toString(*Sym));
627230dc11dSSam Clegg     InputFunction* Func = replaceWithUnreachable(Sym, *Sig, DebugName);
628230dc11dSSam Clegg     // Ensure it compares equal to the null pointer, and so that table relocs
629230dc11dSSam Clegg     // don't pull in the stub body (only call-operand relocs should do that).
630230dc11dSSam Clegg     Func->setTableIndex(0);
631230dc11dSSam Clegg     // Hide our dummy to prevent export.
632230dc11dSSam Clegg     Sym->setHidden(true);
633230dc11dSSam Clegg   }
634230dc11dSSam Clegg }
6356540e570SSam Clegg 
6366540e570SSam Clegg static void reportFunctionSignatureMismatch(StringRef SymName,
6376540e570SSam Clegg                                             FunctionSymbol *A,
6386540e570SSam Clegg                                             FunctionSymbol *B, bool Error) {
6396540e570SSam Clegg   std::string msg = ("function signature mismatch: " + SymName +
6406540e570SSam Clegg                      "\n>>> defined as " + toString(*A->Signature) + " in " +
6416540e570SSam Clegg                      toString(A->getFile()) + "\n>>> defined as " +
6426540e570SSam Clegg                      toString(*B->Signature) + " in " + toString(B->getFile()))
6436540e570SSam Clegg                         .str();
6446540e570SSam Clegg   if (Error)
6456540e570SSam Clegg     error(msg);
6466540e570SSam Clegg   else
6476540e570SSam Clegg     warn(msg);
6486540e570SSam Clegg }
6496540e570SSam Clegg 
6506540e570SSam Clegg // Remove any variant symbols that were created due to function signature
6516540e570SSam Clegg // mismatches.
6526540e570SSam Clegg void SymbolTable::handleSymbolVariants() {
6536540e570SSam Clegg   for (auto Pair : SymVariants) {
6546540e570SSam Clegg     // Push the initial symbol onto the list of variants.
6556540e570SSam Clegg     StringRef SymName = Pair.first.val();
6566540e570SSam Clegg     std::vector<Symbol *> &Variants = Pair.second;
6576540e570SSam Clegg 
6586540e570SSam Clegg #ifndef NDEBUG
659f8d736f1SSam Clegg     LLVM_DEBUG(dbgs() << "symbol with (" << Variants.size()
660f8d736f1SSam Clegg                       << ") variants: " << SymName << "\n");
6616540e570SSam Clegg     for (auto *S: Variants) {
6626540e570SSam Clegg       auto *F = cast<FunctionSymbol>(S);
663f8d736f1SSam Clegg       LLVM_DEBUG(dbgs() << " variant: " + F->getName() << " "
664f8d736f1SSam Clegg                         << toString(*F->Signature) << "\n");
6656540e570SSam Clegg     }
6666540e570SSam Clegg #endif
6676540e570SSam Clegg 
6686540e570SSam Clegg     // Find the one definition.
6696540e570SSam Clegg     DefinedFunction *Defined = nullptr;
6706540e570SSam Clegg     for (auto *Symbol : Variants) {
6716540e570SSam Clegg       if (auto F = dyn_cast<DefinedFunction>(Symbol)) {
6726540e570SSam Clegg         Defined = F;
6736540e570SSam Clegg         break;
6746540e570SSam Clegg       }
6756540e570SSam Clegg     }
6766540e570SSam Clegg 
6776540e570SSam Clegg     // If there are no definitions, and the undefined symbols disagree on
6786540e570SSam Clegg     // the signature, there is not we can do since we don't know which one
6796540e570SSam Clegg     // to use as the signature on the import.
6806540e570SSam Clegg     if (!Defined) {
6816540e570SSam Clegg       reportFunctionSignatureMismatch(SymName,
6826540e570SSam Clegg                                       cast<FunctionSymbol>(Variants[0]),
6836540e570SSam Clegg                                       cast<FunctionSymbol>(Variants[1]), true);
6846540e570SSam Clegg       return;
6856540e570SSam Clegg     }
6866540e570SSam Clegg 
6876540e570SSam Clegg     for (auto *Symbol : Variants) {
6886540e570SSam Clegg       if (Symbol != Defined) {
6896540e570SSam Clegg         auto *F = cast<FunctionSymbol>(Symbol);
6906540e570SSam Clegg         reportFunctionSignatureMismatch(SymName, F, Defined, false);
6916540e570SSam Clegg         StringRef DebugName = Saver.save("unreachable:" + toString(*F));
6926540e570SSam Clegg         replaceWithUnreachable(F, *F->Signature, DebugName);
6936540e570SSam Clegg       }
6946540e570SSam Clegg     }
6956540e570SSam Clegg   }
6966540e570SSam Clegg }
697