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 2533c59abfSFangrui Song namespace lld { 2633c59abfSFangrui Song namespace wasm { 2733c59abfSFangrui Song SymbolTable *symtab; 28c94d393aSSam Clegg 29136d27abSRui Ueyama void SymbolTable::addFile(InputFile *file) { 30136d27abSRui Ueyama log("Processing: " + toString(file)); 31a282a61bSSam Clegg 32a282a61bSSam Clegg // .a file 33136d27abSRui Ueyama if (auto *f = dyn_cast<ArchiveFile>(file)) { 34136d27abSRui Ueyama f->parse(); 35a282a61bSSam Clegg return; 36a282a61bSSam Clegg } 37a282a61bSSam Clegg 38a282a61bSSam Clegg // .so file 39136d27abSRui Ueyama if (auto *f = dyn_cast<SharedFile>(file)) { 40136d27abSRui Ueyama sharedFiles.push_back(f); 41a282a61bSSam Clegg return; 42a282a61bSSam Clegg } 43a282a61bSSam Clegg 44136d27abSRui Ueyama if (config->trace) 45136d27abSRui Ueyama message(toString(file)); 46c94d393aSSam Clegg 47c729c1b4SSam Clegg // LLVM bitcode file 48136d27abSRui Ueyama if (auto *f = dyn_cast<BitcodeFile>(file)) { 49136d27abSRui Ueyama f->parse(); 50136d27abSRui Ueyama bitcodeFiles.push_back(f); 51a282a61bSSam Clegg return; 52a282a61bSSam Clegg } 53a282a61bSSam Clegg 54a282a61bSSam Clegg // Regular object file 55136d27abSRui Ueyama auto *f = cast<ObjFile>(file); 56136d27abSRui Ueyama f->parse(false); 57136d27abSRui Ueyama 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() { 68*b062fe18SSam Clegg // Prevent further LTO objects being included 69*b062fe18SSam Clegg BitcodeFile::doneLTO = true; 70*b062fe18SSam Clegg 71136d27abSRui Ueyama if (bitcodeFiles.empty()) 72c729c1b4SSam Clegg return; 73c729c1b4SSam Clegg 74c729c1b4SSam Clegg // Compile bitcode files and replace bitcode symbols. 75136d27abSRui Ueyama lto.reset(new BitcodeCompiler); 76136d27abSRui Ueyama for (BitcodeFile *f : bitcodeFiles) 77136d27abSRui Ueyama lto->add(*f); 78c729c1b4SSam Clegg 79136d27abSRui Ueyama for (StringRef filename : lto->compile()) { 80136d27abSRui Ueyama auto *obj = make<ObjFile>(MemoryBufferRef(filename, "lto.tmp"), ""); 81136d27abSRui Ueyama obj->parse(true); 82136d27abSRui Ueyama objectFiles.push_back(obj); 83c729c1b4SSam Clegg } 84c729c1b4SSam Clegg } 85c729c1b4SSam Clegg 86136d27abSRui Ueyama Symbol *SymbolTable::find(StringRef name) { 87136d27abSRui Ueyama auto it = symMap.find(CachedHashStringRef(name)); 88136d27abSRui Ueyama if (it == symMap.end() || it->second == -1) 891f3f774fSSam Clegg return nullptr; 90136d27abSRui Ueyama return symVector[it->second]; 911f3f774fSSam Clegg } 921f3f774fSSam Clegg 93136d27abSRui Ueyama void SymbolTable::replace(StringRef name, Symbol* sym) { 94136d27abSRui Ueyama auto it = symMap.find(CachedHashStringRef(name)); 95136d27abSRui Ueyama symVector[it->second] = sym; 966540e570SSam Clegg } 976540e570SSam Clegg 98136d27abSRui Ueyama std::pair<Symbol *, bool> SymbolTable::insertName(StringRef name) { 99136d27abSRui Ueyama bool trace = false; 100136d27abSRui Ueyama auto p = symMap.insert({CachedHashStringRef(name), (int)symVector.size()}); 101136d27abSRui Ueyama int &symIndex = p.first->second; 102136d27abSRui Ueyama bool isNew = p.second; 103136d27abSRui Ueyama if (symIndex == -1) { 104136d27abSRui Ueyama symIndex = symVector.size(); 105136d27abSRui Ueyama trace = true; 106136d27abSRui Ueyama isNew = true; 1071f3f774fSSam Clegg } 1081f3f774fSSam Clegg 109136d27abSRui Ueyama if (!isNew) 110136d27abSRui Ueyama return {symVector[symIndex], false}; 1111f3f774fSSam Clegg 112136d27abSRui Ueyama Symbol *sym = reinterpret_cast<Symbol *>(make<SymbolUnion>()); 113136d27abSRui Ueyama sym->isUsedInRegularObj = false; 114136d27abSRui Ueyama sym->canInline = true; 115136d27abSRui Ueyama sym->traced = trace; 116136d27abSRui Ueyama symVector.emplace_back(sym); 117136d27abSRui Ueyama return {sym, true}; 118c94d393aSSam Clegg } 119c94d393aSSam Clegg 120136d27abSRui Ueyama std::pair<Symbol *, bool> SymbolTable::insert(StringRef name, 121136d27abSRui Ueyama const InputFile *file) { 122136d27abSRui Ueyama Symbol *s; 123136d27abSRui Ueyama bool wasInserted; 124136d27abSRui Ueyama std::tie(s, wasInserted) = insertName(name); 1251f3f774fSSam Clegg 126136d27abSRui Ueyama if (!file || file->kind() == InputFile::ObjectKind) 127136d27abSRui Ueyama s->isUsedInRegularObj = true; 1281f3f774fSSam Clegg 129136d27abSRui Ueyama return {s, wasInserted}; 130c94d393aSSam Clegg } 131c94d393aSSam Clegg 132136d27abSRui Ueyama static void reportTypeError(const Symbol *existing, const InputFile *file, 133136d27abSRui Ueyama llvm::wasm::WasmSymbolType type) { 134136d27abSRui Ueyama error("symbol type mismatch: " + toString(*existing) + "\n>>> defined as " + 135136d27abSRui Ueyama toString(existing->getWasmType()) + " in " + 136136d27abSRui Ueyama toString(existing->getFile()) + "\n>>> defined as " + toString(type) + 137136d27abSRui Ueyama " in " + toString(file)); 138e3498ec5SRui Ueyama } 139e3498ec5SRui Ueyama 1406f4286fbSHeejin Ahn // Check the type of new symbol matches that of the symbol is replacing. 1416540e570SSam Clegg // Returns true if the function types match, false is there is a singature 1426540e570SSam Clegg // mismatch. 143136d27abSRui Ueyama static bool signatureMatches(FunctionSymbol *existing, 144136d27abSRui Ueyama const WasmSignature *newSig) { 145136d27abSRui Ueyama const WasmSignature *oldSig = existing->signature; 146d506b0a4SSam Clegg 147d506b0a4SSam Clegg // If either function is missing a signature (this happend for bitcode 148d506b0a4SSam Clegg // symbols) then assume they match. Any mismatch will be reported later 149d506b0a4SSam Clegg // when the LTO objects are added. 150136d27abSRui Ueyama if (!newSig || !oldSig) 1516540e570SSam Clegg return true; 152cefbf9acSSam Clegg 153136d27abSRui Ueyama return *newSig == *oldSig; 154e3498ec5SRui Ueyama } 155e3498ec5SRui Ueyama 156136d27abSRui Ueyama static void checkGlobalType(const Symbol *existing, const InputFile *file, 157136d27abSRui Ueyama const WasmGlobalType *newType) { 158136d27abSRui Ueyama if (!isa<GlobalSymbol>(existing)) { 159136d27abSRui Ueyama reportTypeError(existing, file, WASM_SYMBOL_TYPE_GLOBAL); 160b8621596SSam Clegg return; 161b8621596SSam Clegg } 162b8621596SSam Clegg 163136d27abSRui Ueyama const WasmGlobalType *oldType = cast<GlobalSymbol>(existing)->getGlobalType(); 164136d27abSRui Ueyama if (*newType != *oldType) { 165136d27abSRui Ueyama error("Global type mismatch: " + existing->getName() + "\n>>> defined as " + 166136d27abSRui Ueyama toString(*oldType) + " in " + toString(existing->getFile()) + 167136d27abSRui Ueyama "\n>>> defined as " + toString(*newType) + " in " + toString(file)); 168c94d393aSSam Clegg } 16924b3dcd4SSam Clegg } 17024b3dcd4SSam Clegg 171136d27abSRui Ueyama static void checkEventType(const Symbol *existing, const InputFile *file, 172136d27abSRui Ueyama const WasmEventType *newType, 173136d27abSRui Ueyama const WasmSignature *newSig) { 174136d27abSRui Ueyama auto existingEvent = dyn_cast<EventSymbol>(existing); 175136d27abSRui Ueyama if (!isa<EventSymbol>(existing)) { 176136d27abSRui Ueyama reportTypeError(existing, file, WASM_SYMBOL_TYPE_EVENT); 177e915a71fSHeejin Ahn return; 178e915a71fSHeejin Ahn } 179e915a71fSHeejin Ahn 180136d27abSRui Ueyama const WasmEventType *oldType = cast<EventSymbol>(existing)->getEventType(); 181136d27abSRui Ueyama const WasmSignature *oldSig = existingEvent->signature; 182136d27abSRui Ueyama if (newType->Attribute != oldType->Attribute) 183136d27abSRui Ueyama error("Event type mismatch: " + existing->getName() + "\n>>> defined as " + 184136d27abSRui Ueyama toString(*oldType) + " in " + toString(existing->getFile()) + 185136d27abSRui Ueyama "\n>>> defined as " + toString(*newType) + " in " + toString(file)); 186136d27abSRui Ueyama if (*newSig != *oldSig) 187136d27abSRui Ueyama warn("Event signature mismatch: " + existing->getName() + 188136d27abSRui Ueyama "\n>>> defined as " + toString(*oldSig) + " in " + 189136d27abSRui Ueyama toString(existing->getFile()) + "\n>>> defined as " + 190136d27abSRui Ueyama toString(*newSig) + " in " + toString(file)); 191e915a71fSHeejin Ahn } 192e915a71fSHeejin Ahn 193136d27abSRui Ueyama static void checkDataType(const Symbol *existing, const InputFile *file) { 194136d27abSRui Ueyama if (!isa<DataSymbol>(existing)) 195136d27abSRui Ueyama reportTypeError(existing, file, WASM_SYMBOL_TYPE_DATA); 196e3498ec5SRui Ueyama } 197e3498ec5SRui Ueyama 198136d27abSRui Ueyama DefinedFunction *SymbolTable::addSyntheticFunction(StringRef name, 199136d27abSRui Ueyama uint32_t flags, 200136d27abSRui Ueyama InputFunction *function) { 201136d27abSRui Ueyama LLVM_DEBUG(dbgs() << "addSyntheticFunction: " << name << "\n"); 202136d27abSRui Ueyama assert(!find(name)); 203136d27abSRui Ueyama syntheticFunctions.emplace_back(function); 204136d27abSRui Ueyama return replaceSymbol<DefinedFunction>(insertName(name).first, name, 205136d27abSRui Ueyama flags, nullptr, function); 20650686856SSam Clegg } 20750686856SSam Clegg 2088e8ddaa3SSam Clegg // Adds an optional, linker generated, data symbols. The symbol will only be 2097ae3d335SKazuaki Ishizaki // added if there is an undefine reference to it, or if it is explicitly 2107ae3d335SKazuaki Ishizaki // exported via the --export flag. Otherwise we don't add the symbol and return 2117ae3d335SKazuaki Ishizaki // nullptr. 212caa0db13SSam Clegg DefinedData *SymbolTable::addOptionalDataSymbol(StringRef name, 213caa0db13SSam Clegg uint32_t value) { 214136d27abSRui Ueyama Symbol *s = find(name); 215136d27abSRui Ueyama if (!s && (config->exportAll || config->exportedSymbols.count(name) != 0)) 216136d27abSRui Ueyama s = insertName(name).first; 217136d27abSRui Ueyama else if (!s || s->isDefined()) 2184bce63a0SSam Clegg return nullptr; 219136d27abSRui Ueyama LLVM_DEBUG(dbgs() << "addOptionalDataSymbol: " << name << "\n"); 220caa0db13SSam Clegg auto *rtn = replaceSymbol<DefinedData>(s, name, WASM_SYMBOL_VISIBILITY_HIDDEN); 221136d27abSRui Ueyama rtn->setVirtualAddress(value); 222136d27abSRui Ueyama rtn->referenced = true; 2234bce63a0SSam Clegg return rtn; 2244bce63a0SSam Clegg } 2254bce63a0SSam Clegg 226136d27abSRui Ueyama DefinedData *SymbolTable::addSyntheticDataSymbol(StringRef name, 227136d27abSRui Ueyama uint32_t flags) { 228136d27abSRui Ueyama LLVM_DEBUG(dbgs() << "addSyntheticDataSymbol: " << name << "\n"); 229136d27abSRui Ueyama assert(!find(name)); 230136d27abSRui Ueyama return replaceSymbol<DefinedData>(insertName(name).first, name, flags); 231c94d393aSSam Clegg } 232c94d393aSSam Clegg 233136d27abSRui Ueyama DefinedGlobal *SymbolTable::addSyntheticGlobal(StringRef name, uint32_t flags, 234136d27abSRui Ueyama InputGlobal *global) { 235136d27abSRui Ueyama LLVM_DEBUG(dbgs() << "addSyntheticGlobal: " << name << " -> " << global 236e7245b42SNicola Zaghen << "\n"); 237136d27abSRui Ueyama assert(!find(name)); 238136d27abSRui Ueyama syntheticGlobals.emplace_back(global); 239136d27abSRui Ueyama return replaceSymbol<DefinedGlobal>(insertName(name).first, name, flags, 240136d27abSRui Ueyama nullptr, global); 24193102974SSam Clegg } 24293102974SSam Clegg 243136d27abSRui Ueyama static bool shouldReplace(const Symbol *existing, InputFile *newFile, 244136d27abSRui Ueyama uint32_t newFlags) { 245c03c9040SRui Ueyama // If existing symbol is undefined, replace it. 246136d27abSRui Ueyama if (!existing->isDefined()) { 247e7245b42SNicola Zaghen LLVM_DEBUG(dbgs() << "resolving existing undefined symbol: " 248136d27abSRui Ueyama << existing->getName() << "\n"); 249c03c9040SRui Ueyama return true; 250c03c9040SRui Ueyama } 251c03c9040SRui Ueyama 252c03c9040SRui Ueyama // Now we have two defined symbols. If the new one is weak, we can ignore it. 253136d27abSRui Ueyama if ((newFlags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) { 254e7245b42SNicola Zaghen LLVM_DEBUG(dbgs() << "existing symbol takes precedence\n"); 255c03c9040SRui Ueyama return false; 256c03c9040SRui Ueyama } 257c03c9040SRui Ueyama 258c03c9040SRui Ueyama // If the existing symbol is weak, we should replace it. 259136d27abSRui Ueyama if (existing->isWeak()) { 260e7245b42SNicola Zaghen LLVM_DEBUG(dbgs() << "replacing existing weak symbol\n"); 261c03c9040SRui Ueyama return true; 262c03c9040SRui Ueyama } 263c03c9040SRui Ueyama 264c03c9040SRui Ueyama // Neither symbol is week. They conflict. 265136d27abSRui Ueyama error("duplicate symbol: " + toString(*existing) + "\n>>> defined in " + 266136d27abSRui Ueyama toString(existing->getFile()) + "\n>>> defined in " + 267136d27abSRui Ueyama toString(newFile)); 268c03c9040SRui Ueyama return true; 269b8621596SSam Clegg } 27093e559b1SSam Clegg 271136d27abSRui Ueyama Symbol *SymbolTable::addDefinedFunction(StringRef name, uint32_t flags, 272136d27abSRui Ueyama InputFile *file, 273136d27abSRui Ueyama InputFunction *function) { 274136d27abSRui Ueyama LLVM_DEBUG(dbgs() << "addDefinedFunction: " << name << " [" 275136d27abSRui Ueyama << (function ? toString(function->signature) : "none") 2768b0b48f3SSam Clegg << "]\n"); 277136d27abSRui Ueyama Symbol *s; 278136d27abSRui Ueyama bool wasInserted; 279136d27abSRui Ueyama std::tie(s, wasInserted) = insert(name, file); 280c729c1b4SSam Clegg 281136d27abSRui Ueyama auto replaceSym = [&](Symbol *sym) { 2826540e570SSam Clegg // If the new defined function doesn't have signture (i.e. bitcode 2836540e570SSam Clegg // functions) but the old symbol does, then preserve the old signature 284136d27abSRui Ueyama const WasmSignature *oldSig = s->getSignature(); 285136d27abSRui Ueyama auto* newSym = replaceSymbol<DefinedFunction>(sym, name, flags, file, function); 286136d27abSRui Ueyama if (!newSym->signature) 287136d27abSRui Ueyama newSym->signature = oldSig; 2886540e570SSam Clegg }; 2896540e570SSam Clegg 290136d27abSRui Ueyama if (wasInserted || s->isLazy()) { 291136d27abSRui Ueyama replaceSym(s); 292136d27abSRui Ueyama return s; 293e3498ec5SRui Ueyama } 294e3498ec5SRui Ueyama 295136d27abSRui Ueyama auto existingFunction = dyn_cast<FunctionSymbol>(s); 296136d27abSRui Ueyama if (!existingFunction) { 297136d27abSRui Ueyama reportTypeError(s, file, WASM_SYMBOL_TYPE_FUNCTION); 298136d27abSRui Ueyama return s; 2998b0b48f3SSam Clegg } 3006540e570SSam Clegg 301136d27abSRui Ueyama bool checkSig = true; 302136d27abSRui Ueyama if (auto ud = dyn_cast<UndefinedFunction>(existingFunction)) 303136d27abSRui Ueyama checkSig = ud->isCalledDirectly; 30459f959ffSSam Clegg 305136d27abSRui Ueyama if (checkSig && function && !signatureMatches(existingFunction, &function->signature)) { 306136d27abSRui Ueyama Symbol* variant; 307136d27abSRui Ueyama if (getFunctionVariant(s, &function->signature, file, &variant)) 3086540e570SSam Clegg // New variant, always replace 309136d27abSRui Ueyama replaceSym(variant); 310136d27abSRui Ueyama else if (shouldReplace(s, file, flags)) 3116540e570SSam Clegg // Variant already exists, replace it after checking shouldReplace 312136d27abSRui Ueyama replaceSym(variant); 3136540e570SSam Clegg 3146540e570SSam Clegg // This variant we found take the place in the symbol table as the primary 3156540e570SSam Clegg // variant. 316136d27abSRui Ueyama replace(name, variant); 317136d27abSRui Ueyama return variant; 3186540e570SSam Clegg } 3196540e570SSam Clegg 3206540e570SSam Clegg // Existing function with matching signature. 321136d27abSRui Ueyama if (shouldReplace(s, file, flags)) 322136d27abSRui Ueyama replaceSym(s); 3236540e570SSam Clegg 324136d27abSRui Ueyama return s; 32593e559b1SSam Clegg } 32693e559b1SSam Clegg 327136d27abSRui Ueyama Symbol *SymbolTable::addDefinedData(StringRef name, uint32_t flags, 328136d27abSRui Ueyama InputFile *file, InputSegment *segment, 329136d27abSRui Ueyama uint32_t address, uint32_t size) { 330136d27abSRui Ueyama LLVM_DEBUG(dbgs() << "addDefinedData:" << name << " addr:" << address 331e7245b42SNicola Zaghen << "\n"); 332136d27abSRui Ueyama Symbol *s; 333136d27abSRui Ueyama bool wasInserted; 334136d27abSRui Ueyama std::tie(s, wasInserted) = insert(name, file); 335c729c1b4SSam Clegg 336136d27abSRui Ueyama auto replaceSym = [&]() { 337136d27abSRui Ueyama replaceSymbol<DefinedData>(s, name, flags, file, segment, address, size); 3386540e570SSam Clegg }; 3396540e570SSam Clegg 340136d27abSRui Ueyama if (wasInserted || s->isLazy()) { 341136d27abSRui Ueyama replaceSym(); 342136d27abSRui Ueyama return s; 343e3498ec5SRui Ueyama } 344e3498ec5SRui Ueyama 345136d27abSRui Ueyama checkDataType(s, file); 346e3498ec5SRui Ueyama 347136d27abSRui Ueyama if (shouldReplace(s, file, flags)) 348136d27abSRui Ueyama replaceSym(); 349136d27abSRui Ueyama return s; 350c94d393aSSam Clegg } 351c94d393aSSam Clegg 352136d27abSRui Ueyama Symbol *SymbolTable::addDefinedGlobal(StringRef name, uint32_t flags, 353136d27abSRui Ueyama InputFile *file, InputGlobal *global) { 354136d27abSRui Ueyama LLVM_DEBUG(dbgs() << "addDefinedGlobal:" << name << "\n"); 3554c2cbfe6SSam Clegg 356136d27abSRui Ueyama Symbol *s; 357136d27abSRui Ueyama bool wasInserted; 358136d27abSRui Ueyama std::tie(s, wasInserted) = insert(name, file); 359c729c1b4SSam Clegg 360136d27abSRui Ueyama auto replaceSym = [&]() { 361136d27abSRui Ueyama replaceSymbol<DefinedGlobal>(s, name, flags, file, global); 3626540e570SSam Clegg }; 3636540e570SSam Clegg 364136d27abSRui Ueyama if (wasInserted || s->isLazy()) { 365136d27abSRui Ueyama replaceSym(); 366136d27abSRui Ueyama return s; 36793102974SSam Clegg } 36893102974SSam Clegg 369136d27abSRui Ueyama checkGlobalType(s, file, &global->getType()); 370e3498ec5SRui Ueyama 371136d27abSRui Ueyama if (shouldReplace(s, file, flags)) 372136d27abSRui Ueyama replaceSym(); 373136d27abSRui Ueyama return s; 374e3498ec5SRui Ueyama } 375e3498ec5SRui Ueyama 376136d27abSRui Ueyama Symbol *SymbolTable::addDefinedEvent(StringRef name, uint32_t flags, 377136d27abSRui Ueyama InputFile *file, InputEvent *event) { 378136d27abSRui Ueyama LLVM_DEBUG(dbgs() << "addDefinedEvent:" << name << "\n"); 379e915a71fSHeejin Ahn 380136d27abSRui Ueyama Symbol *s; 381136d27abSRui Ueyama bool wasInserted; 382136d27abSRui Ueyama std::tie(s, wasInserted) = insert(name, file); 383e915a71fSHeejin Ahn 384136d27abSRui Ueyama auto replaceSym = [&]() { 385136d27abSRui Ueyama replaceSymbol<DefinedEvent>(s, name, flags, file, event); 3866540e570SSam Clegg }; 3876540e570SSam Clegg 388136d27abSRui Ueyama if (wasInserted || s->isLazy()) { 389136d27abSRui Ueyama replaceSym(); 390136d27abSRui Ueyama return s; 391e915a71fSHeejin Ahn } 392e915a71fSHeejin Ahn 393136d27abSRui Ueyama checkEventType(s, file, &event->getType(), &event->signature); 394e915a71fSHeejin Ahn 395136d27abSRui Ueyama if (shouldReplace(s, file, flags)) 396136d27abSRui Ueyama replaceSym(); 397136d27abSRui Ueyama return s; 398e915a71fSHeejin Ahn } 399e915a71fSHeejin Ahn 40067b05584SSam Clegg // This function get called when an undefined symbol is added, and there is 40167b05584SSam Clegg // already an existing one in the symbols table. In this case we check that 40267b05584SSam Clegg // custom 'import-module' and 'import-field' symbol attributes agree. 4037ae3d335SKazuaki Ishizaki // With LTO these attributes are not available when the bitcode is read and only 40467b05584SSam Clegg // become available when the LTO object is read. In this case we silently 40567b05584SSam Clegg // replace the empty attributes with the valid ones. 40667b05584SSam Clegg template <typename T> 40767b05584SSam Clegg static void setImportAttributes(T *existing, StringRef importName, 40867b05584SSam Clegg StringRef importModule, InputFile *file) { 40967b05584SSam Clegg if (!importName.empty()) { 41067b05584SSam Clegg if (existing->importName.empty()) 41167b05584SSam Clegg existing->importName = importName; 41267b05584SSam Clegg if (existing->importName != importName) 41367b05584SSam Clegg error("import name mismatch for symbol: " + toString(*existing) + 41467b05584SSam Clegg "\n>>> defined as " + existing->importName + " in " + 41567b05584SSam Clegg toString(existing->getFile()) + "\n>>> defined as " + importName + 41667b05584SSam Clegg " in " + toString(file)); 41767b05584SSam Clegg } 41867b05584SSam Clegg 41967b05584SSam Clegg if (!importModule.empty()) { 42067b05584SSam Clegg if (existing->importModule.empty()) 42167b05584SSam Clegg existing->importModule = importModule; 42267b05584SSam Clegg if (existing->importModule != importModule) 42367b05584SSam Clegg error("import module mismatch for symbol: " + toString(*existing) + 42467b05584SSam Clegg "\n>>> defined as " + existing->importModule + " in " + 42567b05584SSam Clegg toString(existing->getFile()) + "\n>>> defined as " + importModule + 42667b05584SSam Clegg " in " + toString(file)); 42767b05584SSam Clegg } 42867b05584SSam Clegg } 42967b05584SSam Clegg 430136d27abSRui Ueyama Symbol *SymbolTable::addUndefinedFunction(StringRef name, StringRef importName, 431136d27abSRui Ueyama StringRef importModule, 432136d27abSRui Ueyama uint32_t flags, InputFile *file, 433136d27abSRui Ueyama const WasmSignature *sig, 434136d27abSRui Ueyama bool isCalledDirectly) { 435136d27abSRui Ueyama LLVM_DEBUG(dbgs() << "addUndefinedFunction: " << name << " [" 436136d27abSRui Ueyama << (sig ? toString(*sig) : "none") 437136d27abSRui Ueyama << "] IsCalledDirectly:" << isCalledDirectly << "\n"); 438f6f4b98fSSam Clegg assert(flags & WASM_SYMBOL_UNDEFINED); 439c03c9040SRui Ueyama 440136d27abSRui Ueyama Symbol *s; 441136d27abSRui Ueyama bool wasInserted; 442136d27abSRui Ueyama std::tie(s, wasInserted) = insert(name, file); 443136d27abSRui Ueyama if (s->traced) 444136d27abSRui Ueyama printTraceSymbolUndefined(name, file); 445c729c1b4SSam Clegg 446136d27abSRui Ueyama auto replaceSym = [&]() { 447136d27abSRui Ueyama replaceSymbol<UndefinedFunction>(s, name, importName, importModule, flags, 448136d27abSRui Ueyama file, sig, isCalledDirectly); 4496540e570SSam Clegg }; 4506540e570SSam Clegg 451136d27abSRui Ueyama if (wasInserted) 452136d27abSRui Ueyama replaceSym(); 453136d27abSRui Ueyama else if (auto *lazy = dyn_cast<LazySymbol>(s)) 454136d27abSRui Ueyama lazy->fetch(); 4556540e570SSam Clegg else { 456136d27abSRui Ueyama auto existingFunction = dyn_cast<FunctionSymbol>(s); 457136d27abSRui Ueyama if (!existingFunction) { 458136d27abSRui Ueyama reportTypeError(s, file, WASM_SYMBOL_TYPE_FUNCTION); 459136d27abSRui Ueyama return s; 4606540e570SSam Clegg } 46167b05584SSam Clegg auto *existingUndefined = dyn_cast<UndefinedFunction>(existingFunction); 462136d27abSRui Ueyama if (!existingFunction->signature && sig) 463136d27abSRui Ueyama existingFunction->signature = sig; 464fecfc592SSam Clegg if (isCalledDirectly && !signatureMatches(existingFunction, sig)) { 465fecfc592SSam Clegg // If the existing undefined functions is not called direcltly then let 466fecfc592SSam Clegg // this one take precedence. Otherwise the existing function is either 467fecfc592SSam Clegg // direclty called or defined, in which case we need a function variant. 468fecfc592SSam Clegg if (existingUndefined && !existingUndefined->isCalledDirectly) 469136d27abSRui Ueyama replaceSym(); 470fecfc592SSam Clegg else if (getFunctionVariant(s, sig, file, &s)) 471fecfc592SSam Clegg replaceSym(); 472fecfc592SSam Clegg } 47367b05584SSam Clegg if (existingUndefined) 47467b05584SSam Clegg setImportAttributes(existingUndefined, importName, importModule, file); 4756540e570SSam Clegg } 476cefbf9acSSam Clegg 477136d27abSRui Ueyama return s; 478c03c9040SRui Ueyama } 479c03c9040SRui Ueyama 480136d27abSRui Ueyama Symbol *SymbolTable::addUndefinedData(StringRef name, uint32_t flags, 481136d27abSRui Ueyama InputFile *file) { 482136d27abSRui Ueyama LLVM_DEBUG(dbgs() << "addUndefinedData: " << name << "\n"); 483f6f4b98fSSam Clegg assert(flags & WASM_SYMBOL_UNDEFINED); 48493102974SSam Clegg 485136d27abSRui Ueyama Symbol *s; 486136d27abSRui Ueyama bool wasInserted; 487136d27abSRui Ueyama std::tie(s, wasInserted) = insert(name, file); 488136d27abSRui Ueyama if (s->traced) 489136d27abSRui Ueyama printTraceSymbolUndefined(name, file); 490f989a92dSSam Clegg 491136d27abSRui Ueyama if (wasInserted) 492136d27abSRui Ueyama replaceSymbol<UndefinedData>(s, name, flags, file); 493136d27abSRui Ueyama else if (auto *lazy = dyn_cast<LazySymbol>(s)) 494136d27abSRui Ueyama lazy->fetch(); 495136d27abSRui Ueyama else if (s->isDefined()) 496136d27abSRui Ueyama checkDataType(s, file); 497136d27abSRui Ueyama return s; 498c94d393aSSam Clegg } 499c94d393aSSam Clegg 500136d27abSRui Ueyama Symbol *SymbolTable::addUndefinedGlobal(StringRef name, StringRef importName, 501136d27abSRui Ueyama StringRef importModule, uint32_t flags, 502136d27abSRui Ueyama InputFile *file, 503136d27abSRui Ueyama const WasmGlobalType *type) { 504136d27abSRui Ueyama LLVM_DEBUG(dbgs() << "addUndefinedGlobal: " << name << "\n"); 505f6f4b98fSSam Clegg assert(flags & WASM_SYMBOL_UNDEFINED); 506e3498ec5SRui Ueyama 507136d27abSRui Ueyama Symbol *s; 508136d27abSRui Ueyama bool wasInserted; 509136d27abSRui Ueyama std::tie(s, wasInserted) = insert(name, file); 510136d27abSRui Ueyama if (s->traced) 511136d27abSRui Ueyama printTraceSymbolUndefined(name, file); 512c729c1b4SSam Clegg 513136d27abSRui Ueyama if (wasInserted) 514136d27abSRui Ueyama replaceSymbol<UndefinedGlobal>(s, name, importName, importModule, flags, 515136d27abSRui Ueyama file, type); 516136d27abSRui Ueyama else if (auto *lazy = dyn_cast<LazySymbol>(s)) 517136d27abSRui Ueyama lazy->fetch(); 518136d27abSRui Ueyama else if (s->isDefined()) 519136d27abSRui Ueyama checkGlobalType(s, file, type); 520136d27abSRui Ueyama return s; 521e3498ec5SRui Ueyama } 522e3498ec5SRui Ueyama 523136d27abSRui Ueyama void SymbolTable::addLazy(ArchiveFile *file, const Archive::Symbol *sym) { 524136d27abSRui Ueyama LLVM_DEBUG(dbgs() << "addLazy: " << sym->getName() << "\n"); 525136d27abSRui Ueyama StringRef name = sym->getName(); 526c03c9040SRui Ueyama 527136d27abSRui Ueyama Symbol *s; 528136d27abSRui Ueyama bool wasInserted; 529136d27abSRui Ueyama std::tie(s, wasInserted) = insertName(name); 530c03c9040SRui Ueyama 531136d27abSRui Ueyama if (wasInserted) { 532136d27abSRui Ueyama replaceSymbol<LazySymbol>(s, name, 0, file, *sym); 533c03c9040SRui Ueyama return; 534c03c9040SRui Ueyama } 535c03c9040SRui Ueyama 536136d27abSRui Ueyama if (!s->isUndefined()) 53737b4ee52SSam Clegg return; 53837b4ee52SSam Clegg 53937b4ee52SSam Clegg // The existing symbol is undefined, load a new one from the archive, 5407ae3d335SKazuaki Ishizaki // unless the existing symbol is weak in which case replace the undefined 54137b4ee52SSam Clegg // symbols with a LazySymbol. 542136d27abSRui Ueyama if (s->isWeak()) { 543136d27abSRui Ueyama const WasmSignature *oldSig = nullptr; 54437b4ee52SSam Clegg // In the case of an UndefinedFunction we need to preserve the expected 54537b4ee52SSam Clegg // signature. 546136d27abSRui Ueyama if (auto *f = dyn_cast<UndefinedFunction>(s)) 547136d27abSRui Ueyama oldSig = f->signature; 54837b4ee52SSam Clegg LLVM_DEBUG(dbgs() << "replacing existing weak undefined symbol\n"); 549136d27abSRui Ueyama auto newSym = replaceSymbol<LazySymbol>(s, name, WASM_SYMBOL_BINDING_WEAK, 550136d27abSRui Ueyama file, *sym); 551136d27abSRui Ueyama newSym->signature = oldSig; 55237b4ee52SSam Clegg return; 55337b4ee52SSam Clegg } 55437b4ee52SSam Clegg 555e7245b42SNicola Zaghen LLVM_DEBUG(dbgs() << "replacing existing undefined\n"); 556136d27abSRui Ueyama file->addMember(sym); 557c94d393aSSam Clegg } 558e0f6fcd0SSam Clegg 559136d27abSRui Ueyama bool SymbolTable::addComdat(StringRef name) { 560136d27abSRui Ueyama return comdatGroups.insert(CachedHashStringRef(name)).second; 561e0f6fcd0SSam Clegg } 5621f3f774fSSam Clegg 5636540e570SSam Clegg // The new signature doesn't match. Create a variant to the symbol with the 5646540e570SSam Clegg // signature encoded in the name and return that instead. These symbols are 5656540e570SSam Clegg // then unified later in handleSymbolVariants. 566136d27abSRui Ueyama bool SymbolTable::getFunctionVariant(Symbol* sym, const WasmSignature *sig, 567136d27abSRui Ueyama const InputFile *file, Symbol **out) { 568136d27abSRui Ueyama LLVM_DEBUG(dbgs() << "getFunctionVariant: " << sym->getName() << " -> " 569136d27abSRui Ueyama << " " << toString(*sig) << "\n"); 570136d27abSRui Ueyama Symbol *variant = nullptr; 5716540e570SSam Clegg 5726540e570SSam Clegg // Linear search through symbol variants. Should never be more than two 5736540e570SSam Clegg // or three entries here. 574136d27abSRui Ueyama auto &variants = symVariants[CachedHashStringRef(sym->getName())]; 575136d27abSRui Ueyama if (variants.empty()) 576136d27abSRui Ueyama variants.push_back(sym); 5776540e570SSam Clegg 578136d27abSRui Ueyama for (Symbol* v : variants) { 579136d27abSRui Ueyama if (*v->getSignature() == *sig) { 580136d27abSRui Ueyama variant = v; 5816540e570SSam Clegg break; 5826540e570SSam Clegg } 5836540e570SSam Clegg } 5846540e570SSam Clegg 585136d27abSRui Ueyama bool wasAdded = !variant; 586136d27abSRui Ueyama if (wasAdded) { 5876540e570SSam Clegg // Create a new variant; 5886540e570SSam Clegg LLVM_DEBUG(dbgs() << "added new variant\n"); 589136d27abSRui Ueyama variant = reinterpret_cast<Symbol *>(make<SymbolUnion>()); 590136d27abSRui Ueyama variants.push_back(variant); 5916540e570SSam Clegg } else { 592136d27abSRui Ueyama LLVM_DEBUG(dbgs() << "variant already exists: " << toString(*variant) << "\n"); 593136d27abSRui Ueyama assert(*variant->getSignature() == *sig); 5946540e570SSam Clegg } 5956540e570SSam Clegg 596136d27abSRui Ueyama *out = variant; 597136d27abSRui Ueyama return wasAdded; 5986540e570SSam Clegg } 5996540e570SSam Clegg 6001f3f774fSSam Clegg // Set a flag for --trace-symbol so that we can print out a log message 6011f3f774fSSam Clegg // if a new symbol with the same name is inserted into the symbol table. 602136d27abSRui Ueyama void SymbolTable::trace(StringRef name) { 603136d27abSRui Ueyama symMap.insert({CachedHashStringRef(name), -1}); 6041f3f774fSSam Clegg } 605230dc11dSSam Clegg 606136d27abSRui Ueyama void SymbolTable::wrap(Symbol *sym, Symbol *real, Symbol *wrap) { 607a5ca34e6SSam Clegg // Swap symbols as instructed by -wrap. 608136d27abSRui Ueyama int &origIdx = symMap[CachedHashStringRef(sym->getName())]; 609136d27abSRui Ueyama int &realIdx= symMap[CachedHashStringRef(real->getName())]; 610136d27abSRui Ueyama int &wrapIdx = symMap[CachedHashStringRef(wrap->getName())]; 611136d27abSRui Ueyama LLVM_DEBUG(dbgs() << "wrap: " << sym->getName() << "\n"); 612a5ca34e6SSam Clegg 613a5ca34e6SSam Clegg // Anyone looking up __real symbols should get the original 614136d27abSRui Ueyama realIdx = origIdx; 615a5ca34e6SSam Clegg // Anyone looking up the original should get the __wrap symbol 616136d27abSRui Ueyama origIdx = wrapIdx; 617a5ca34e6SSam Clegg } 618a5ca34e6SSam Clegg 619136d27abSRui Ueyama static const uint8_t unreachableFn[] = { 620230dc11dSSam Clegg 0x03 /* ULEB length */, 0x00 /* ULEB num locals */, 621230dc11dSSam Clegg 0x00 /* opcode unreachable */, 0x0b /* opcode end */ 622230dc11dSSam Clegg }; 623230dc11dSSam Clegg 624230dc11dSSam Clegg // Replace the given symbol body with an unreachable function. 625230dc11dSSam Clegg // This is used by handleWeakUndefines in order to generate a callable 6266540e570SSam Clegg // equivalent of an undefined function and also handleSymbolVariants for 6276540e570SSam Clegg // undefined functions that don't match the signature of the definition. 628136d27abSRui Ueyama InputFunction *SymbolTable::replaceWithUnreachable(Symbol *sym, 629136d27abSRui Ueyama const WasmSignature &sig, 630136d27abSRui Ueyama StringRef debugName) { 631136d27abSRui Ueyama auto *func = make<SyntheticFunction>(sig, sym->getName(), debugName); 632136d27abSRui Ueyama func->setBody(unreachableFn); 633136d27abSRui Ueyama syntheticFunctions.emplace_back(func); 634136d27abSRui Ueyama replaceSymbol<DefinedFunction>(sym, sym->getName(), sym->getFlags(), nullptr, 635136d27abSRui Ueyama func); 636136d27abSRui Ueyama return func; 637230dc11dSSam Clegg } 638230dc11dSSam Clegg 639230dc11dSSam Clegg // For weak undefined functions, there may be "call" instructions that reference 640230dc11dSSam Clegg // the symbol. In this case, we need to synthesise a dummy/stub function that 641230dc11dSSam Clegg // will abort at runtime, so that relocations can still provided an operand to 642230dc11dSSam Clegg // the call instruction that passes Wasm validation. 643230dc11dSSam Clegg void SymbolTable::handleWeakUndefines() { 644136d27abSRui Ueyama for (Symbol *sym : getSymbols()) { 645136d27abSRui Ueyama if (!sym->isUndefWeak()) 646230dc11dSSam Clegg continue; 647230dc11dSSam Clegg 648136d27abSRui Ueyama const WasmSignature *sig = sym->getSignature(); 649136d27abSRui Ueyama if (!sig) { 650230dc11dSSam Clegg // It is possible for undefined functions not to have a signature (eg. if 651230dc11dSSam Clegg // added via "--undefined"), but weak undefined ones do have a signature. 6526540e570SSam Clegg // Lazy symbols may not be functions and therefore Sig can still be null 6537ae3d335SKazuaki Ishizaki // in some circumstance. 654136d27abSRui Ueyama assert(!isa<FunctionSymbol>(sym)); 655230dc11dSSam Clegg continue; 6566540e570SSam Clegg } 657230dc11dSSam Clegg 658230dc11dSSam Clegg // Add a synthetic dummy for weak undefined functions. These dummies will 659230dc11dSSam Clegg // be GC'd if not used as the target of any "call" instructions. 660136d27abSRui Ueyama StringRef debugName = saver.save("undefined:" + toString(*sym)); 661136d27abSRui Ueyama InputFunction* func = replaceWithUnreachable(sym, *sig, debugName); 662230dc11dSSam Clegg // Ensure it compares equal to the null pointer, and so that table relocs 663230dc11dSSam Clegg // don't pull in the stub body (only call-operand relocs should do that). 664136d27abSRui Ueyama func->setTableIndex(0); 665230dc11dSSam Clegg // Hide our dummy to prevent export. 666136d27abSRui Ueyama sym->setHidden(true); 667230dc11dSSam Clegg } 668230dc11dSSam Clegg } 6696540e570SSam Clegg 670136d27abSRui Ueyama static void reportFunctionSignatureMismatch(StringRef symName, 671136d27abSRui Ueyama FunctionSymbol *a, 672136d27abSRui Ueyama FunctionSymbol *b, bool isError) { 673136d27abSRui Ueyama std::string msg = ("function signature mismatch: " + symName + 674136d27abSRui Ueyama "\n>>> defined as " + toString(*a->signature) + " in " + 675136d27abSRui Ueyama toString(a->getFile()) + "\n>>> defined as " + 676136d27abSRui Ueyama toString(*b->signature) + " in " + toString(b->getFile())) 6776540e570SSam Clegg .str(); 678136d27abSRui Ueyama if (isError) 6796540e570SSam Clegg error(msg); 6806540e570SSam Clegg else 6816540e570SSam Clegg warn(msg); 6826540e570SSam Clegg } 6836540e570SSam Clegg 6846540e570SSam Clegg // Remove any variant symbols that were created due to function signature 6856540e570SSam Clegg // mismatches. 6866540e570SSam Clegg void SymbolTable::handleSymbolVariants() { 687136d27abSRui Ueyama for (auto pair : symVariants) { 6886540e570SSam Clegg // Push the initial symbol onto the list of variants. 689136d27abSRui Ueyama StringRef symName = pair.first.val(); 690136d27abSRui Ueyama std::vector<Symbol *> &variants = pair.second; 6916540e570SSam Clegg 6926540e570SSam Clegg #ifndef NDEBUG 693136d27abSRui Ueyama LLVM_DEBUG(dbgs() << "symbol with (" << variants.size() 694136d27abSRui Ueyama << ") variants: " << symName << "\n"); 695136d27abSRui Ueyama for (auto *s: variants) { 696136d27abSRui Ueyama auto *f = cast<FunctionSymbol>(s); 697136d27abSRui Ueyama LLVM_DEBUG(dbgs() << " variant: " + f->getName() << " " 698136d27abSRui Ueyama << toString(*f->signature) << "\n"); 6996540e570SSam Clegg } 7006540e570SSam Clegg #endif 7016540e570SSam Clegg 7026540e570SSam Clegg // Find the one definition. 703136d27abSRui Ueyama DefinedFunction *defined = nullptr; 704136d27abSRui Ueyama for (auto *symbol : variants) { 705136d27abSRui Ueyama if (auto f = dyn_cast<DefinedFunction>(symbol)) { 706136d27abSRui Ueyama defined = f; 7076540e570SSam Clegg break; 7086540e570SSam Clegg } 7096540e570SSam Clegg } 7106540e570SSam Clegg 7116540e570SSam Clegg // If there are no definitions, and the undefined symbols disagree on 7126540e570SSam Clegg // the signature, there is not we can do since we don't know which one 7136540e570SSam Clegg // to use as the signature on the import. 714136d27abSRui Ueyama if (!defined) { 715136d27abSRui Ueyama reportFunctionSignatureMismatch(symName, 716136d27abSRui Ueyama cast<FunctionSymbol>(variants[0]), 717136d27abSRui Ueyama cast<FunctionSymbol>(variants[1]), true); 7186540e570SSam Clegg return; 7196540e570SSam Clegg } 7206540e570SSam Clegg 721136d27abSRui Ueyama for (auto *symbol : variants) { 722136d27abSRui Ueyama if (symbol != defined) { 723136d27abSRui Ueyama auto *f = cast<FunctionSymbol>(symbol); 724136d27abSRui Ueyama reportFunctionSignatureMismatch(symName, f, defined, false); 72551b521c0SSam Clegg StringRef debugName = saver.save("signature_mismatch:" + toString(*f)); 726136d27abSRui Ueyama replaceWithUnreachable(f, *f->signature, debugName); 7276540e570SSam Clegg } 7286540e570SSam Clegg } 7296540e570SSam Clegg } 7306540e570SSam Clegg } 73133c59abfSFangrui Song 73233c59abfSFangrui Song } // namespace wasm 73333c59abfSFangrui Song } // namespace lld 734