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)); 311f3f774fSSam Clegg if (Config->Trace) 321f3f774fSSam Clegg message(toString(File)); 33c94d393aSSam Clegg File->parse(); 34c94d393aSSam Clegg 35c729c1b4SSam Clegg // LLVM bitcode file 36c729c1b4SSam Clegg if (auto *F = dyn_cast<BitcodeFile>(File)) 37c729c1b4SSam Clegg BitcodeFiles.push_back(F); 38c729c1b4SSam Clegg else if (auto *F = dyn_cast<ObjFile>(File)) 39c94d393aSSam Clegg ObjectFiles.push_back(F); 40a688a42cSSam Clegg else if (auto *F = dyn_cast<SharedFile>(File)) 41a688a42cSSam Clegg SharedFiles.push_back(F); 42c94d393aSSam Clegg } 43c94d393aSSam Clegg 44c729c1b4SSam Clegg // This function is where all the optimizations of link-time 45c729c1b4SSam Clegg // optimization happens. When LTO is in use, some input files are 46c729c1b4SSam Clegg // not in native object file format but in the LLVM bitcode format. 47c729c1b4SSam Clegg // This function compiles bitcode files into a few big native files 48c729c1b4SSam Clegg // using LLVM functions and replaces bitcode symbols with the results. 49c729c1b4SSam Clegg // Because all bitcode files that the program consists of are passed 50c729c1b4SSam Clegg // to the compiler at once, it can do whole-program optimization. 51c729c1b4SSam Clegg void SymbolTable::addCombinedLTOObject() { 52c729c1b4SSam Clegg if (BitcodeFiles.empty()) 53c729c1b4SSam Clegg return; 54c729c1b4SSam Clegg 55c729c1b4SSam Clegg // Compile bitcode files and replace bitcode symbols. 56c729c1b4SSam Clegg LTO.reset(new BitcodeCompiler); 57c729c1b4SSam Clegg for (BitcodeFile *F : BitcodeFiles) 58c729c1b4SSam Clegg LTO->add(*F); 59c729c1b4SSam Clegg 60c729c1b4SSam Clegg for (StringRef Filename : LTO->compile()) { 610cfaa247SSam Clegg auto *Obj = make<ObjFile>(MemoryBufferRef(Filename, "lto.tmp"), ""); 62697f2149SSam Clegg Obj->parse(true); 63c729c1b4SSam Clegg ObjectFiles.push_back(Obj); 64c729c1b4SSam Clegg } 65c729c1b4SSam Clegg } 66c729c1b4SSam Clegg 67c94d393aSSam Clegg void SymbolTable::reportRemainingUndefines() { 68a5ca34e6SSam Clegg for (const auto& Pair : SymMap) { 69a5ca34e6SSam Clegg const Symbol *Sym = SymVector[Pair.second]; 70c729c1b4SSam Clegg if (!Sym->isUndefined() || Sym->isWeak()) 71c729c1b4SSam Clegg continue; 72c729c1b4SSam Clegg if (Config->AllowUndefinedSymbols.count(Sym->getName()) != 0) 73c729c1b4SSam Clegg continue; 74c729c1b4SSam Clegg if (!Sym->IsUsedInRegularObj) 75c729c1b4SSam Clegg continue; 7647e2b6b2SSam Clegg error(toString(Sym->getFile()) + ": undefined symbol: " + toString(*Sym)); 77c94d393aSSam Clegg } 78c94d393aSSam Clegg } 79c94d393aSSam Clegg 80c94d393aSSam Clegg Symbol *SymbolTable::find(StringRef Name) { 811f3f774fSSam Clegg auto It = SymMap.find(CachedHashStringRef(Name)); 821f3f774fSSam Clegg if (It == SymMap.end() || It->second == -1) 831f3f774fSSam Clegg return nullptr; 841f3f774fSSam Clegg return SymVector[It->second]; 851f3f774fSSam Clegg } 861f3f774fSSam Clegg 876540e570SSam Clegg void SymbolTable::replace(StringRef Name, Symbol* Sym) { 886540e570SSam Clegg auto It = SymMap.find(CachedHashStringRef(Name)); 896540e570SSam Clegg SymVector[It->second] = Sym; 906540e570SSam Clegg } 916540e570SSam Clegg 921f3f774fSSam Clegg std::pair<Symbol *, bool> SymbolTable::insertName(StringRef Name) { 931f3f774fSSam Clegg bool Trace = false; 941f3f774fSSam Clegg auto P = SymMap.insert({CachedHashStringRef(Name), (int)SymVector.size()}); 951f3f774fSSam Clegg int &SymIndex = P.first->second; 961f3f774fSSam Clegg bool IsNew = P.second; 971f3f774fSSam Clegg if (SymIndex == -1) { 981f3f774fSSam Clegg SymIndex = SymVector.size(); 991f3f774fSSam Clegg Trace = true; 1001f3f774fSSam Clegg IsNew = true; 1011f3f774fSSam Clegg } 1021f3f774fSSam Clegg 1031f3f774fSSam Clegg if (!IsNew) 1041f3f774fSSam Clegg return {SymVector[SymIndex], false}; 1051f3f774fSSam Clegg 1061f3f774fSSam Clegg Symbol *Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>()); 1071f3f774fSSam Clegg Sym->IsUsedInRegularObj = false; 108a5ca34e6SSam Clegg Sym->CanInline = true; 1091f3f774fSSam Clegg Sym->Traced = Trace; 1101f3f774fSSam Clegg SymVector.emplace_back(Sym); 1111f3f774fSSam Clegg return {Sym, true}; 112c94d393aSSam Clegg } 113c94d393aSSam Clegg 114230dc11dSSam Clegg std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name, 115230dc11dSSam Clegg const InputFile *File) { 1161f3f774fSSam Clegg Symbol *S; 1171f3f774fSSam Clegg bool WasInserted; 1181f3f774fSSam Clegg std::tie(S, WasInserted) = insertName(Name); 1191f3f774fSSam Clegg 1204c2cbfe6SSam Clegg if (!File || File->kind() == InputFile::ObjectKind) 1211f3f774fSSam Clegg S->IsUsedInRegularObj = true; 1221f3f774fSSam Clegg 1231f3f774fSSam Clegg return {S, WasInserted}; 124c94d393aSSam Clegg } 125c94d393aSSam Clegg 126e3498ec5SRui Ueyama static void reportTypeError(const Symbol *Existing, const InputFile *File, 1273876d89aSSam Clegg llvm::wasm::WasmSymbolType Type) { 128e3498ec5SRui Ueyama error("symbol type mismatch: " + toString(*Existing) + "\n>>> defined as " + 129e3498ec5SRui Ueyama toString(Existing->getWasmType()) + " in " + 1303876d89aSSam Clegg toString(Existing->getFile()) + "\n>>> defined as " + toString(Type) + 1313876d89aSSam Clegg " in " + toString(File)); 132e3498ec5SRui Ueyama } 133e3498ec5SRui Ueyama 1346f4286fbSHeejin Ahn // Check the type of new symbol matches that of the symbol is replacing. 1356540e570SSam Clegg // Returns true if the function types match, false is there is a singature 1366540e570SSam Clegg // mismatch. 137ba2ea93aSBenjamin Kramer static bool signatureMatches(FunctionSymbol *Existing, 138ba2ea93aSBenjamin Kramer const WasmSignature *NewSig) { 1396540e570SSam Clegg const WasmSignature *OldSig = Existing->Signature; 140d506b0a4SSam Clegg 141d506b0a4SSam Clegg // If either function is missing a signature (this happend for bitcode 142d506b0a4SSam Clegg // symbols) then assume they match. Any mismatch will be reported later 143d506b0a4SSam Clegg // when the LTO objects are added. 144d506b0a4SSam Clegg if (!NewSig || !OldSig) 1456540e570SSam Clegg return true; 146cefbf9acSSam Clegg 1476540e570SSam Clegg return *NewSig == *OldSig; 148e3498ec5SRui Ueyama } 149e3498ec5SRui Ueyama 150e3498ec5SRui Ueyama static void checkGlobalType(const Symbol *Existing, const InputFile *File, 151e3498ec5SRui Ueyama const WasmGlobalType *NewType) { 152e3498ec5SRui Ueyama if (!isa<GlobalSymbol>(Existing)) { 1533876d89aSSam Clegg reportTypeError(Existing, File, WASM_SYMBOL_TYPE_GLOBAL); 154b8621596SSam Clegg return; 155b8621596SSam Clegg } 156b8621596SSam Clegg 157e3498ec5SRui Ueyama const WasmGlobalType *OldType = cast<GlobalSymbol>(Existing)->getGlobalType(); 158e3498ec5SRui Ueyama if (*NewType != *OldType) { 159e3498ec5SRui Ueyama error("Global type mismatch: " + Existing->getName() + "\n>>> defined as " + 160e3498ec5SRui Ueyama toString(*OldType) + " in " + toString(Existing->getFile()) + 161e3498ec5SRui Ueyama "\n>>> defined as " + toString(*NewType) + " in " + toString(File)); 162c94d393aSSam Clegg } 16324b3dcd4SSam Clegg } 16424b3dcd4SSam Clegg 165e915a71fSHeejin Ahn static void checkEventType(const Symbol *Existing, const InputFile *File, 166e915a71fSHeejin Ahn const WasmEventType *NewType, 167e915a71fSHeejin Ahn const WasmSignature *NewSig) { 168e915a71fSHeejin Ahn auto ExistingEvent = dyn_cast<EventSymbol>(Existing); 169e915a71fSHeejin Ahn if (!isa<EventSymbol>(Existing)) { 170e915a71fSHeejin Ahn reportTypeError(Existing, File, WASM_SYMBOL_TYPE_EVENT); 171e915a71fSHeejin Ahn return; 172e915a71fSHeejin Ahn } 173e915a71fSHeejin Ahn 174e915a71fSHeejin Ahn const WasmEventType *OldType = cast<EventSymbol>(Existing)->getEventType(); 175e915a71fSHeejin Ahn const WasmSignature *OldSig = ExistingEvent->Signature; 176e915a71fSHeejin Ahn if (NewType->Attribute != OldType->Attribute) 177e915a71fSHeejin Ahn error("Event type mismatch: " + Existing->getName() + "\n>>> defined as " + 178e915a71fSHeejin Ahn toString(*OldType) + " in " + toString(Existing->getFile()) + 179e915a71fSHeejin Ahn "\n>>> defined as " + toString(*NewType) + " in " + toString(File)); 180e915a71fSHeejin Ahn if (*NewSig != *OldSig) 181e915a71fSHeejin Ahn warn("Event signature mismatch: " + Existing->getName() + 182e915a71fSHeejin Ahn "\n>>> defined as " + toString(*OldSig) + " in " + 183e915a71fSHeejin Ahn toString(Existing->getFile()) + "\n>>> defined as " + 184e915a71fSHeejin Ahn toString(*NewSig) + " in " + toString(File)); 185e915a71fSHeejin Ahn } 186e915a71fSHeejin Ahn 187e3498ec5SRui Ueyama static void checkDataType(const Symbol *Existing, const InputFile *File) { 188e3498ec5SRui Ueyama if (!isa<DataSymbol>(Existing)) 1893876d89aSSam Clegg reportTypeError(Existing, File, WASM_SYMBOL_TYPE_DATA); 190e3498ec5SRui Ueyama } 191e3498ec5SRui Ueyama 192dfb0b2c7SSam Clegg DefinedFunction *SymbolTable::addSyntheticFunction(StringRef Name, 193ebda41f8SNicholas Wilson uint32_t Flags, 194ebda41f8SNicholas Wilson InputFunction *Function) { 195e7245b42SNicola Zaghen LLVM_DEBUG(dbgs() << "addSyntheticFunction: " << Name << "\n"); 196b961abc8SRui Ueyama assert(!find(Name)); 197ebda41f8SNicholas Wilson SyntheticFunctions.emplace_back(Function); 198d15a4154SSam Clegg return replaceSymbol<DefinedFunction>(insertName(Name).first, Name, 1994c2cbfe6SSam Clegg Flags, nullptr, Function); 20050686856SSam Clegg } 20150686856SSam Clegg 202*8e8ddaa3SSam Clegg // Adds an optional, linker generated, data symbols. The symbol will only be 203*8e8ddaa3SSam Clegg // added if there is an undefine reference to it, or if it is explictly exported 204*8e8ddaa3SSam Clegg // via the --export flag. Otherwise we don't add the symbol and return nullptr. 2054bce63a0SSam Clegg DefinedData *SymbolTable::addOptionalDataSymbol(StringRef Name, uint32_t Value, 2064bce63a0SSam Clegg uint32_t Flags) { 2074bce63a0SSam Clegg Symbol *S = find(Name); 2087d4ec5afSSam Clegg if (!S && (Config->ExportAll || Config->ExportedSymbols.count(Name) != 0)) 2097d4ec5afSSam Clegg S = insertName(Name).first; 2107d4ec5afSSam Clegg else if (!S || S->isDefined()) 2114bce63a0SSam Clegg return nullptr; 2124bce63a0SSam Clegg LLVM_DEBUG(dbgs() << "addOptionalDataSymbol: " << Name << "\n"); 2134bce63a0SSam Clegg auto *rtn = replaceSymbol<DefinedData>(S, Name, Flags); 2144bce63a0SSam Clegg rtn->setVirtualAddress(Value); 2154bce63a0SSam Clegg return rtn; 2164bce63a0SSam Clegg } 2174bce63a0SSam Clegg 21800245539SSam Clegg DefinedData *SymbolTable::addSyntheticDataSymbol(StringRef Name, 21900245539SSam Clegg uint32_t Flags) { 220e7245b42SNicola Zaghen LLVM_DEBUG(dbgs() << "addSyntheticDataSymbol: " << Name << "\n"); 221b961abc8SRui Ueyama assert(!find(Name)); 222d15a4154SSam Clegg return replaceSymbol<DefinedData>(insertName(Name).first, Name, Flags); 223c94d393aSSam Clegg } 224c94d393aSSam Clegg 22593102974SSam Clegg DefinedGlobal *SymbolTable::addSyntheticGlobal(StringRef Name, uint32_t Flags, 22693102974SSam Clegg InputGlobal *Global) { 227e7245b42SNicola Zaghen LLVM_DEBUG(dbgs() << "addSyntheticGlobal: " << Name << " -> " << Global 228e7245b42SNicola Zaghen << "\n"); 229b961abc8SRui Ueyama assert(!find(Name)); 230ebda41f8SNicholas Wilson SyntheticGlobals.emplace_back(Global); 231d15a4154SSam Clegg return replaceSymbol<DefinedGlobal>(insertName(Name).first, Name, Flags, 2324c2cbfe6SSam Clegg nullptr, Global); 23393102974SSam Clegg } 23493102974SSam Clegg 235e3498ec5SRui Ueyama static bool shouldReplace(const Symbol *Existing, InputFile *NewFile, 236e3498ec5SRui Ueyama uint32_t NewFlags) { 237c03c9040SRui Ueyama // If existing symbol is undefined, replace it. 238e3498ec5SRui Ueyama if (!Existing->isDefined()) { 239e7245b42SNicola Zaghen LLVM_DEBUG(dbgs() << "resolving existing undefined symbol: " 240e3498ec5SRui Ueyama << Existing->getName() << "\n"); 241c03c9040SRui Ueyama return true; 242c03c9040SRui Ueyama } 243c03c9040SRui Ueyama 244c03c9040SRui Ueyama // Now we have two defined symbols. If the new one is weak, we can ignore it. 245c03c9040SRui Ueyama if ((NewFlags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) { 246e7245b42SNicola Zaghen LLVM_DEBUG(dbgs() << "existing symbol takes precedence\n"); 247c03c9040SRui Ueyama return false; 248c03c9040SRui Ueyama } 249c03c9040SRui Ueyama 250c03c9040SRui Ueyama // If the existing symbol is weak, we should replace it. 251e3498ec5SRui Ueyama if (Existing->isWeak()) { 252e7245b42SNicola Zaghen LLVM_DEBUG(dbgs() << "replacing existing weak symbol\n"); 253c03c9040SRui Ueyama return true; 254c03c9040SRui Ueyama } 255c03c9040SRui Ueyama 256c03c9040SRui Ueyama // Neither symbol is week. They conflict. 257e3498ec5SRui Ueyama error("duplicate symbol: " + toString(*Existing) + "\n>>> defined in " + 258e3498ec5SRui Ueyama toString(Existing->getFile()) + "\n>>> defined in " + 259e3498ec5SRui Ueyama toString(NewFile)); 260c03c9040SRui Ueyama return true; 261b8621596SSam Clegg } 26293e559b1SSam Clegg 26393e559b1SSam Clegg Symbol *SymbolTable::addDefinedFunction(StringRef Name, uint32_t Flags, 264e3498ec5SRui Ueyama InputFile *File, 265e3498ec5SRui Ueyama InputFunction *Function) { 2668b0b48f3SSam Clegg LLVM_DEBUG(dbgs() << "addDefinedFunction: " << Name << " [" 2678b0b48f3SSam Clegg << (Function ? toString(Function->Signature) : "none") 2688b0b48f3SSam Clegg << "]\n"); 26993e559b1SSam Clegg Symbol *S; 27093e559b1SSam Clegg bool WasInserted; 2714c2cbfe6SSam Clegg std::tie(S, WasInserted) = insert(Name, File); 272c729c1b4SSam Clegg 2736540e570SSam Clegg auto Replace = [&](Symbol* Sym) { 2746540e570SSam Clegg // If the new defined function doesn't have signture (i.e. bitcode 2756540e570SSam Clegg // functions) but the old symbol does, then preserve the old signature 2766540e570SSam Clegg const WasmSignature *OldSig = S->getSignature(); 2776540e570SSam Clegg auto* NewSym = replaceSymbol<DefinedFunction>(Sym, Name, Flags, File, Function); 2786540e570SSam Clegg if (!NewSym->Signature) 2796540e570SSam Clegg NewSym->Signature = OldSig; 2806540e570SSam Clegg }; 2816540e570SSam Clegg 282e3498ec5SRui Ueyama if (WasInserted || S->isLazy()) { 2836540e570SSam Clegg Replace(S); 284e3498ec5SRui Ueyama return S; 285e3498ec5SRui Ueyama } 286e3498ec5SRui Ueyama 2876540e570SSam Clegg auto ExistingFunction = dyn_cast<FunctionSymbol>(S); 2886540e570SSam Clegg if (!ExistingFunction) { 2896540e570SSam Clegg reportTypeError(S, File, WASM_SYMBOL_TYPE_FUNCTION); 2906540e570SSam Clegg return S; 2918b0b48f3SSam Clegg } 2926540e570SSam Clegg 29359f959ffSSam Clegg bool CheckSig = true; 29459f959ffSSam Clegg if (auto UD = dyn_cast<UndefinedFunction>(ExistingFunction)) 29559f959ffSSam Clegg CheckSig = UD->IsCalledDirectly; 29659f959ffSSam Clegg 29759f959ffSSam Clegg if (CheckSig && Function && !signatureMatches(ExistingFunction, &Function->Signature)) { 2986540e570SSam Clegg Symbol* Variant; 2996540e570SSam Clegg if (getFunctionVariant(S, &Function->Signature, File, &Variant)) 3006540e570SSam Clegg // New variant, always replace 3016540e570SSam Clegg Replace(Variant); 3026540e570SSam Clegg else if (shouldReplace(S, File, Flags)) 3036540e570SSam Clegg // Variant already exists, replace it after checking shouldReplace 3046540e570SSam Clegg Replace(Variant); 3056540e570SSam Clegg 3066540e570SSam Clegg // This variant we found take the place in the symbol table as the primary 3076540e570SSam Clegg // variant. 3086540e570SSam Clegg replace(Name, Variant); 3096540e570SSam Clegg return Variant; 3106540e570SSam Clegg } 3116540e570SSam Clegg 3126540e570SSam Clegg // Existing function with matching signature. 3136540e570SSam Clegg if (shouldReplace(S, File, Flags)) 3146540e570SSam Clegg Replace(S); 3156540e570SSam Clegg 31693e559b1SSam Clegg return S; 31793e559b1SSam Clegg } 31893e559b1SSam Clegg 31900245539SSam Clegg Symbol *SymbolTable::addDefinedData(StringRef Name, uint32_t Flags, 320e3498ec5SRui Ueyama InputFile *File, InputSegment *Segment, 32193102974SSam Clegg uint32_t Address, uint32_t Size) { 322e7245b42SNicola Zaghen LLVM_DEBUG(dbgs() << "addDefinedData:" << Name << " addr:" << Address 323e7245b42SNicola Zaghen << "\n"); 32493e559b1SSam Clegg Symbol *S; 32593e559b1SSam Clegg bool WasInserted; 3264c2cbfe6SSam Clegg std::tie(S, WasInserted) = insert(Name, File); 327c729c1b4SSam Clegg 3286540e570SSam Clegg auto Replace = [&]() { 329e3498ec5SRui Ueyama replaceSymbol<DefinedData>(S, Name, Flags, File, Segment, Address, Size); 3306540e570SSam Clegg }; 3316540e570SSam Clegg 3326540e570SSam Clegg if (WasInserted || S->isLazy()) { 3336540e570SSam Clegg Replace(); 334e3498ec5SRui Ueyama return S; 335e3498ec5SRui Ueyama } 336e3498ec5SRui Ueyama 337e3498ec5SRui Ueyama checkDataType(S, File); 338e3498ec5SRui Ueyama 339e3498ec5SRui Ueyama if (shouldReplace(S, File, Flags)) 3406540e570SSam Clegg Replace(); 341c94d393aSSam Clegg return S; 342c94d393aSSam Clegg } 343c94d393aSSam Clegg 34493102974SSam Clegg Symbol *SymbolTable::addDefinedGlobal(StringRef Name, uint32_t Flags, 345e3498ec5SRui Ueyama InputFile *File, InputGlobal *Global) { 346e7245b42SNicola Zaghen LLVM_DEBUG(dbgs() << "addDefinedGlobal:" << Name << "\n"); 3474c2cbfe6SSam Clegg 34893102974SSam Clegg Symbol *S; 34993102974SSam Clegg bool WasInserted; 3504c2cbfe6SSam Clegg std::tie(S, WasInserted) = insert(Name, File); 351c729c1b4SSam Clegg 3526540e570SSam Clegg auto Replace = [&]() { 353e3498ec5SRui Ueyama replaceSymbol<DefinedGlobal>(S, Name, Flags, File, Global); 3546540e570SSam Clegg }; 3556540e570SSam Clegg 3566540e570SSam Clegg if (WasInserted || S->isLazy()) { 3576540e570SSam Clegg Replace(); 35893102974SSam Clegg return S; 35993102974SSam Clegg } 36093102974SSam Clegg 361e3498ec5SRui Ueyama checkGlobalType(S, File, &Global->getType()); 362e3498ec5SRui Ueyama 363e3498ec5SRui Ueyama if (shouldReplace(S, File, Flags)) 3646540e570SSam Clegg Replace(); 365e3498ec5SRui Ueyama return S; 366e3498ec5SRui Ueyama } 367e3498ec5SRui Ueyama 368e915a71fSHeejin Ahn Symbol *SymbolTable::addDefinedEvent(StringRef Name, uint32_t Flags, 369e915a71fSHeejin Ahn InputFile *File, InputEvent *Event) { 370e915a71fSHeejin Ahn LLVM_DEBUG(dbgs() << "addDefinedEvent:" << Name << "\n"); 371e915a71fSHeejin Ahn 372e915a71fSHeejin Ahn Symbol *S; 373e915a71fSHeejin Ahn bool WasInserted; 374e915a71fSHeejin Ahn std::tie(S, WasInserted) = insert(Name, File); 375e915a71fSHeejin Ahn 3766540e570SSam Clegg auto Replace = [&]() { 377e915a71fSHeejin Ahn replaceSymbol<DefinedEvent>(S, Name, Flags, File, Event); 3786540e570SSam Clegg }; 3796540e570SSam Clegg 3806540e570SSam Clegg if (WasInserted || S->isLazy()) { 3816540e570SSam Clegg Replace(); 382e915a71fSHeejin Ahn return S; 383e915a71fSHeejin Ahn } 384e915a71fSHeejin Ahn 385e915a71fSHeejin Ahn checkEventType(S, File, &Event->getType(), &Event->Signature); 386e915a71fSHeejin Ahn 387e915a71fSHeejin Ahn if (shouldReplace(S, File, Flags)) 3886540e570SSam Clegg Replace(); 389e915a71fSHeejin Ahn return S; 390e915a71fSHeejin Ahn } 391e915a71fSHeejin Ahn 3929b84eeaaSDan Gohman Symbol *SymbolTable::addUndefinedFunction(StringRef Name, StringRef ImportName, 3939b84eeaaSDan Gohman StringRef ImportModule, 3947cc07531SSam Clegg uint32_t Flags, InputFile *File, 39559f959ffSSam Clegg const WasmSignature *Sig, 39659f959ffSSam Clegg bool IsCalledDirectly) { 397d506b0a4SSam Clegg LLVM_DEBUG(dbgs() << "addUndefinedFunction: " << Name << " [" 398d506b0a4SSam Clegg << (Sig ? toString(*Sig) : "none") 399d506b0a4SSam Clegg << "] IsCalledDirectly:" << IsCalledDirectly << "\n"); 400c03c9040SRui Ueyama 401c94d393aSSam Clegg Symbol *S; 402c94d393aSSam Clegg bool WasInserted; 4034c2cbfe6SSam Clegg std::tie(S, WasInserted) = insert(Name, File); 4047991b682SSam Clegg if (S->Traced) 4057991b682SSam Clegg printTraceSymbolUndefined(Name, File); 406c729c1b4SSam Clegg 4076540e570SSam Clegg auto Replace = [&]() { 4089b84eeaaSDan Gohman replaceSymbol<UndefinedFunction>(S, Name, ImportName, ImportModule, Flags, 40959f959ffSSam Clegg File, Sig, IsCalledDirectly); 4106540e570SSam Clegg }; 4116540e570SSam Clegg 4126540e570SSam Clegg if (WasInserted) 4136540e570SSam Clegg Replace(); 414e3498ec5SRui Ueyama else if (auto *Lazy = dyn_cast<LazySymbol>(S)) 415b961abc8SRui Ueyama Lazy->fetch(); 4166540e570SSam Clegg else { 4176540e570SSam Clegg auto ExistingFunction = dyn_cast<FunctionSymbol>(S); 4186540e570SSam Clegg if (!ExistingFunction) { 4196540e570SSam Clegg reportTypeError(S, File, WASM_SYMBOL_TYPE_FUNCTION); 4206540e570SSam Clegg return S; 4216540e570SSam Clegg } 422d506b0a4SSam Clegg if (!ExistingFunction->Signature && Sig) 423d506b0a4SSam Clegg ExistingFunction->Signature = Sig; 42459f959ffSSam Clegg if (IsCalledDirectly && !signatureMatches(ExistingFunction, Sig)) 4256540e570SSam Clegg if (getFunctionVariant(S, Sig, File, &S)) 4266540e570SSam Clegg Replace(); 4276540e570SSam Clegg } 428cefbf9acSSam Clegg 429c03c9040SRui Ueyama return S; 430c03c9040SRui Ueyama } 431c03c9040SRui Ueyama 432e3498ec5SRui Ueyama Symbol *SymbolTable::addUndefinedData(StringRef Name, uint32_t Flags, 433e3498ec5SRui Ueyama InputFile *File) { 434e7245b42SNicola Zaghen LLVM_DEBUG(dbgs() << "addUndefinedData: " << Name << "\n"); 43593102974SSam Clegg 436e3498ec5SRui Ueyama Symbol *S; 437e3498ec5SRui Ueyama bool WasInserted; 4384c2cbfe6SSam Clegg std::tie(S, WasInserted) = insert(Name, File); 4397991b682SSam Clegg if (S->Traced) 4407991b682SSam Clegg printTraceSymbolUndefined(Name, File); 441f989a92dSSam Clegg 442e3498ec5SRui Ueyama if (WasInserted) 443e3498ec5SRui Ueyama replaceSymbol<UndefinedData>(S, Name, Flags, File); 444e3498ec5SRui Ueyama else if (auto *Lazy = dyn_cast<LazySymbol>(S)) 445b961abc8SRui Ueyama Lazy->fetch(); 446e3498ec5SRui Ueyama else if (S->isDefined()) 447e3498ec5SRui Ueyama checkDataType(S, File); 448c94d393aSSam Clegg return S; 449c94d393aSSam Clegg } 450c94d393aSSam Clegg 4519b84eeaaSDan Gohman Symbol *SymbolTable::addUndefinedGlobal(StringRef Name, StringRef ImportName, 4529b84eeaaSDan Gohman StringRef ImportModule, uint32_t Flags, 453e3498ec5SRui Ueyama InputFile *File, 454e3498ec5SRui Ueyama const WasmGlobalType *Type) { 455e7245b42SNicola Zaghen LLVM_DEBUG(dbgs() << "addUndefinedGlobal: " << Name << "\n"); 456e3498ec5SRui Ueyama 457e3498ec5SRui Ueyama Symbol *S; 458e3498ec5SRui Ueyama bool WasInserted; 4594c2cbfe6SSam Clegg std::tie(S, WasInserted) = insert(Name, File); 4607991b682SSam Clegg if (S->Traced) 4617991b682SSam Clegg printTraceSymbolUndefined(Name, File); 462c729c1b4SSam Clegg 463e3498ec5SRui Ueyama if (WasInserted) 4649b84eeaaSDan Gohman replaceSymbol<UndefinedGlobal>(S, Name, ImportName, ImportModule, Flags, 4659b84eeaaSDan Gohman File, Type); 466e3498ec5SRui Ueyama else if (auto *Lazy = dyn_cast<LazySymbol>(S)) 467b961abc8SRui Ueyama Lazy->fetch(); 468e3498ec5SRui Ueyama else if (S->isDefined()) 469e3498ec5SRui Ueyama checkGlobalType(S, File, Type); 470e3498ec5SRui Ueyama return S; 471e3498ec5SRui Ueyama } 472e3498ec5SRui Ueyama 473e3498ec5SRui Ueyama void SymbolTable::addLazy(ArchiveFile *File, const Archive::Symbol *Sym) { 474e7245b42SNicola Zaghen LLVM_DEBUG(dbgs() << "addLazy: " << Sym->getName() << "\n"); 475c94d393aSSam Clegg StringRef Name = Sym->getName(); 476c03c9040SRui Ueyama 477c94d393aSSam Clegg Symbol *S; 478c94d393aSSam Clegg bool WasInserted; 479d15a4154SSam Clegg std::tie(S, WasInserted) = insertName(Name); 480c03c9040SRui Ueyama 481c94d393aSSam Clegg if (WasInserted) { 48237b4ee52SSam Clegg replaceSymbol<LazySymbol>(S, Name, 0, File, *Sym); 483c03c9040SRui Ueyama return; 484c03c9040SRui Ueyama } 485c03c9040SRui Ueyama 48637b4ee52SSam Clegg if (!S->isUndefined()) 48737b4ee52SSam Clegg return; 48837b4ee52SSam Clegg 48937b4ee52SSam Clegg // The existing symbol is undefined, load a new one from the archive, 49037b4ee52SSam Clegg // unless the the existing symbol is weak in which case replace the undefined 49137b4ee52SSam Clegg // symbols with a LazySymbol. 49237b4ee52SSam Clegg if (S->isWeak()) { 49337b4ee52SSam Clegg const WasmSignature *OldSig = nullptr; 49437b4ee52SSam Clegg // In the case of an UndefinedFunction we need to preserve the expected 49537b4ee52SSam Clegg // signature. 49637b4ee52SSam Clegg if (auto *F = dyn_cast<UndefinedFunction>(S)) 49737b4ee52SSam Clegg OldSig = F->Signature; 49837b4ee52SSam Clegg LLVM_DEBUG(dbgs() << "replacing existing weak undefined symbol\n"); 49937b4ee52SSam Clegg auto NewSym = replaceSymbol<LazySymbol>(S, Name, WASM_SYMBOL_BINDING_WEAK, 50037b4ee52SSam Clegg File, *Sym); 50137b4ee52SSam Clegg NewSym->Signature = OldSig; 50237b4ee52SSam Clegg return; 50337b4ee52SSam Clegg } 50437b4ee52SSam Clegg 505e7245b42SNicola Zaghen LLVM_DEBUG(dbgs() << "replacing existing undefined\n"); 506e3498ec5SRui Ueyama File->addMember(Sym); 507c94d393aSSam Clegg } 508e0f6fcd0SSam Clegg 509c4d9aa1bSNicholas Wilson bool SymbolTable::addComdat(StringRef Name) { 510697f2149SSam Clegg return ComdatGroups.insert(CachedHashStringRef(Name)).second; 511e0f6fcd0SSam Clegg } 5121f3f774fSSam Clegg 5136540e570SSam Clegg // The new signature doesn't match. Create a variant to the symbol with the 5146540e570SSam Clegg // signature encoded in the name and return that instead. These symbols are 5156540e570SSam Clegg // then unified later in handleSymbolVariants. 5166540e570SSam Clegg bool SymbolTable::getFunctionVariant(Symbol* Sym, const WasmSignature *Sig, 5176540e570SSam Clegg const InputFile *File, Symbol **Out) { 51814bab09eSRichard Trieu LLVM_DEBUG(dbgs() << "getFunctionVariant: " << Sym->getName() << " -> " 5196540e570SSam Clegg << " " << toString(*Sig) << "\n"); 5206540e570SSam Clegg Symbol *Variant = nullptr; 5216540e570SSam Clegg 5226540e570SSam Clegg // Linear search through symbol variants. Should never be more than two 5236540e570SSam Clegg // or three entries here. 5246540e570SSam Clegg auto &Variants = SymVariants[CachedHashStringRef(Sym->getName())]; 525196a4404SFangrui Song if (Variants.empty()) 5266540e570SSam Clegg Variants.push_back(Sym); 5276540e570SSam Clegg 5286540e570SSam Clegg for (Symbol* V : Variants) { 5296540e570SSam Clegg if (*V->getSignature() == *Sig) { 5306540e570SSam Clegg Variant = V; 5316540e570SSam Clegg break; 5326540e570SSam Clegg } 5336540e570SSam Clegg } 5346540e570SSam Clegg 5356540e570SSam Clegg bool WasAdded = !Variant; 5366540e570SSam Clegg if (WasAdded) { 5376540e570SSam Clegg // Create a new variant; 5386540e570SSam Clegg LLVM_DEBUG(dbgs() << "added new variant\n"); 5396540e570SSam Clegg Variant = reinterpret_cast<Symbol *>(make<SymbolUnion>()); 5406540e570SSam Clegg Variants.push_back(Variant); 5416540e570SSam Clegg } else { 5426540e570SSam Clegg LLVM_DEBUG(dbgs() << "variant already exists: " << toString(*Variant) << "\n"); 5436540e570SSam Clegg assert(*Variant->getSignature() == *Sig); 5446540e570SSam Clegg } 5456540e570SSam Clegg 5466540e570SSam Clegg *Out = Variant; 5476540e570SSam Clegg return WasAdded; 5486540e570SSam Clegg } 5496540e570SSam Clegg 5501f3f774fSSam Clegg // Set a flag for --trace-symbol so that we can print out a log message 5511f3f774fSSam Clegg // if a new symbol with the same name is inserted into the symbol table. 5521f3f774fSSam Clegg void SymbolTable::trace(StringRef Name) { 5531f3f774fSSam Clegg SymMap.insert({CachedHashStringRef(Name), -1}); 5541f3f774fSSam Clegg } 555230dc11dSSam Clegg 556a5ca34e6SSam Clegg void SymbolTable::wrap(Symbol *Sym, Symbol *Real, Symbol *Wrap) { 557a5ca34e6SSam Clegg // Swap symbols as instructed by -wrap. 558a5ca34e6SSam Clegg int &OrigIdx = SymMap[CachedHashStringRef(Sym->getName())]; 559a5ca34e6SSam Clegg int &RealIdx= SymMap[CachedHashStringRef(Real->getName())]; 560a5ca34e6SSam Clegg int &WrapIdx = SymMap[CachedHashStringRef(Wrap->getName())]; 561a5ca34e6SSam Clegg LLVM_DEBUG(dbgs() << "wrap: " << Sym->getName() << "\n"); 562a5ca34e6SSam Clegg 563a5ca34e6SSam Clegg // Anyone looking up __real symbols should get the original 564a5ca34e6SSam Clegg RealIdx = OrigIdx; 565a5ca34e6SSam Clegg // Anyone looking up the original should get the __wrap symbol 566a5ca34e6SSam Clegg OrigIdx = WrapIdx; 567a5ca34e6SSam Clegg } 568a5ca34e6SSam Clegg 569230dc11dSSam Clegg static const uint8_t UnreachableFn[] = { 570230dc11dSSam Clegg 0x03 /* ULEB length */, 0x00 /* ULEB num locals */, 571230dc11dSSam Clegg 0x00 /* opcode unreachable */, 0x0b /* opcode end */ 572230dc11dSSam Clegg }; 573230dc11dSSam Clegg 574230dc11dSSam Clegg // Replace the given symbol body with an unreachable function. 575230dc11dSSam Clegg // This is used by handleWeakUndefines in order to generate a callable 5766540e570SSam Clegg // equivalent of an undefined function and also handleSymbolVariants for 5776540e570SSam Clegg // undefined functions that don't match the signature of the definition. 578230dc11dSSam Clegg InputFunction *SymbolTable::replaceWithUnreachable(Symbol *Sym, 579230dc11dSSam Clegg const WasmSignature &Sig, 580230dc11dSSam Clegg StringRef DebugName) { 581230dc11dSSam Clegg auto *Func = make<SyntheticFunction>(Sig, Sym->getName(), DebugName); 582230dc11dSSam Clegg Func->setBody(UnreachableFn); 583230dc11dSSam Clegg SyntheticFunctions.emplace_back(Func); 5846540e570SSam Clegg replaceSymbol<DefinedFunction>(Sym, Sym->getName(), Sym->getFlags(), nullptr, 5856540e570SSam Clegg Func); 586230dc11dSSam Clegg return Func; 587230dc11dSSam Clegg } 588230dc11dSSam Clegg 589230dc11dSSam Clegg // For weak undefined functions, there may be "call" instructions that reference 590230dc11dSSam Clegg // the symbol. In this case, we need to synthesise a dummy/stub function that 591230dc11dSSam Clegg // will abort at runtime, so that relocations can still provided an operand to 592230dc11dSSam Clegg // the call instruction that passes Wasm validation. 593230dc11dSSam Clegg void SymbolTable::handleWeakUndefines() { 594230dc11dSSam Clegg for (Symbol *Sym : getSymbols()) { 595230dc11dSSam Clegg if (!Sym->isUndefWeak()) 596230dc11dSSam Clegg continue; 597230dc11dSSam Clegg 5986540e570SSam Clegg const WasmSignature *Sig = Sym->getSignature(); 5996540e570SSam Clegg if (!Sig) { 600230dc11dSSam Clegg // It is possible for undefined functions not to have a signature (eg. if 601230dc11dSSam Clegg // added via "--undefined"), but weak undefined ones do have a signature. 6026540e570SSam Clegg // Lazy symbols may not be functions and therefore Sig can still be null 6036540e570SSam Clegg // in some circumstantce. 6046540e570SSam Clegg assert(!isa<FunctionSymbol>(Sym)); 605230dc11dSSam Clegg continue; 6066540e570SSam Clegg } 607230dc11dSSam Clegg 608230dc11dSSam Clegg // Add a synthetic dummy for weak undefined functions. These dummies will 609230dc11dSSam Clegg // be GC'd if not used as the target of any "call" instructions. 610230dc11dSSam Clegg StringRef DebugName = Saver.save("undefined:" + toString(*Sym)); 611230dc11dSSam Clegg InputFunction* Func = replaceWithUnreachable(Sym, *Sig, DebugName); 612230dc11dSSam Clegg // Ensure it compares equal to the null pointer, and so that table relocs 613230dc11dSSam Clegg // don't pull in the stub body (only call-operand relocs should do that). 614230dc11dSSam Clegg Func->setTableIndex(0); 615230dc11dSSam Clegg // Hide our dummy to prevent export. 616230dc11dSSam Clegg Sym->setHidden(true); 617230dc11dSSam Clegg } 618230dc11dSSam Clegg } 6196540e570SSam Clegg 6206540e570SSam Clegg static void reportFunctionSignatureMismatch(StringRef SymName, 6216540e570SSam Clegg FunctionSymbol *A, 6226540e570SSam Clegg FunctionSymbol *B, bool Error) { 6236540e570SSam Clegg std::string msg = ("function signature mismatch: " + SymName + 6246540e570SSam Clegg "\n>>> defined as " + toString(*A->Signature) + " in " + 6256540e570SSam Clegg toString(A->getFile()) + "\n>>> defined as " + 6266540e570SSam Clegg toString(*B->Signature) + " in " + toString(B->getFile())) 6276540e570SSam Clegg .str(); 6286540e570SSam Clegg if (Error) 6296540e570SSam Clegg error(msg); 6306540e570SSam Clegg else 6316540e570SSam Clegg warn(msg); 6326540e570SSam Clegg } 6336540e570SSam Clegg 6346540e570SSam Clegg // Remove any variant symbols that were created due to function signature 6356540e570SSam Clegg // mismatches. 6366540e570SSam Clegg void SymbolTable::handleSymbolVariants() { 6376540e570SSam Clegg for (auto Pair : SymVariants) { 6386540e570SSam Clegg // Push the initial symbol onto the list of variants. 6396540e570SSam Clegg StringRef SymName = Pair.first.val(); 6406540e570SSam Clegg std::vector<Symbol *> &Variants = Pair.second; 6416540e570SSam Clegg 6426540e570SSam Clegg #ifndef NDEBUG 643f8d736f1SSam Clegg LLVM_DEBUG(dbgs() << "symbol with (" << Variants.size() 644f8d736f1SSam Clegg << ") variants: " << SymName << "\n"); 6456540e570SSam Clegg for (auto *S: Variants) { 6466540e570SSam Clegg auto *F = cast<FunctionSymbol>(S); 647f8d736f1SSam Clegg LLVM_DEBUG(dbgs() << " variant: " + F->getName() << " " 648f8d736f1SSam Clegg << toString(*F->Signature) << "\n"); 6496540e570SSam Clegg } 6506540e570SSam Clegg #endif 6516540e570SSam Clegg 6526540e570SSam Clegg // Find the one definition. 6536540e570SSam Clegg DefinedFunction *Defined = nullptr; 6546540e570SSam Clegg for (auto *Symbol : Variants) { 6556540e570SSam Clegg if (auto F = dyn_cast<DefinedFunction>(Symbol)) { 6566540e570SSam Clegg Defined = F; 6576540e570SSam Clegg break; 6586540e570SSam Clegg } 6596540e570SSam Clegg } 6606540e570SSam Clegg 6616540e570SSam Clegg // If there are no definitions, and the undefined symbols disagree on 6626540e570SSam Clegg // the signature, there is not we can do since we don't know which one 6636540e570SSam Clegg // to use as the signature on the import. 6646540e570SSam Clegg if (!Defined) { 6656540e570SSam Clegg reportFunctionSignatureMismatch(SymName, 6666540e570SSam Clegg cast<FunctionSymbol>(Variants[0]), 6676540e570SSam Clegg cast<FunctionSymbol>(Variants[1]), true); 6686540e570SSam Clegg return; 6696540e570SSam Clegg } 6706540e570SSam Clegg 6716540e570SSam Clegg for (auto *Symbol : Variants) { 6726540e570SSam Clegg if (Symbol != Defined) { 6736540e570SSam Clegg auto *F = cast<FunctionSymbol>(Symbol); 6746540e570SSam Clegg reportFunctionSignatureMismatch(SymName, F, Defined, false); 6756540e570SSam Clegg StringRef DebugName = Saver.save("unreachable:" + toString(*F)); 6766540e570SSam Clegg replaceWithUnreachable(F, *F->Signature, DebugName); 6776540e570SSam Clegg } 6786540e570SSam Clegg } 6796540e570SSam Clegg } 6806540e570SSam Clegg } 681