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