lld/wasm/SymbolTable.cpp

   1 //===- SymbolTable.cpp ----------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "SymbolTable.h"
  10 #include "Config.h"
  11 #include "InputChunks.h"
  12 #include "InputElement.h"
  13 #include "WriterUtils.h"
  14 #include "lld/Common/CommonLinkerContext.h"
  15 #include <optional>
  16
  17 #define DEBUG_TYPE "lld"
  18
  19 using namespace llvm;
  20 using namespace llvm::wasm;
  21 using namespace llvm::object;
  22
  23 namespace lld::wasm {
  24 SymbolTable *symtab;
  25
  26 void SymbolTable::addFile(InputFile *file, StringRef symName) {
  27   log("Processing: " + toString(file));
  28
  29   // .a file
  30   if (auto *f = dyn_cast<ArchiveFile>(file)) {
  31     f->parse();
  32     return;
  33   }
  34
  35   // .so file
  36   if (auto *f = dyn_cast<SharedFile>(file)) {
  37     sharedFiles.push_back(f);
  38     return;
  39   }
  40
  41   // stub file
  42   if (auto *f = dyn_cast<StubFile>(file)) {
  43     f->parse();
  44     stubFiles.push_back(f);
  45     return;
  46   }
  47
  48   if (config->trace)
  49     message(toString(file));
  50
  51   // LLVM bitcode file
  52   if (auto *f = dyn_cast<BitcodeFile>(file)) {
  53     f->parse(symName);
  54     bitcodeFiles.push_back(f);
  55     return;
  56   }
  57
  58   // Regular object file
  59   auto *f = cast<ObjFile>(file);
  60   f->parse(false);
  61   objectFiles.push_back(f);
  62 }
  63
  64 // This function is where all the optimizations of link-time
  65 // optimization happens. When LTO is in use, some input files are
  66 // not in native object file format but in the LLVM bitcode format.
  67 // This function compiles bitcode files into a few big native files
  68 // using LLVM functions and replaces bitcode symbols with the results.
  69 // Because all bitcode files that the program consists of are passed
  70 // to the compiler at once, it can do whole-program optimization.
  71 void SymbolTable::compileBitcodeFiles() {
  72   // Prevent further LTO objects being included
  73   BitcodeFile::doneLTO = true;
  74
  75   if (bitcodeFiles.empty())
  76     return;
  77
  78   // Compile bitcode files and replace bitcode symbols.
  79   lto.reset(new BitcodeCompiler);
  80   for (BitcodeFile *f : bitcodeFiles)
  81     lto->add(*f);
  82
  83   for (StringRef filename : lto->compile()) {
  84     auto *obj = make<ObjFile>(MemoryBufferRef(filename, "lto.tmp"), "");
  85     obj->parse(true);
  86     objectFiles.push_back(obj);
  87   }
  88 }
  89
  90 Symbol *SymbolTable::find(StringRef name) {
  91   auto it = symMap.find(CachedHashStringRef(name));
  92   if (it == symMap.end() || it->second == -1)
  93     return nullptr;
  94   return symVector[it->second];
  95 }
  96
  97 void SymbolTable::replace(StringRef name, Symbol* sym) {
  98   auto it = symMap.find(CachedHashStringRef(name));
  99   symVector[it->second] = sym;
 100 }
 101
 102 std::pair<Symbol *, bool> SymbolTable::insertName(StringRef name) {
 103   bool trace = false;
 104   auto p = symMap.insert({CachedHashStringRef(name), (int)symVector.size()});
 105   int &symIndex = p.first->second;
 106   bool isNew = p.second;
 107   if (symIndex == -1) {
 108     symIndex = symVector.size();
 109     trace = true;
 110     isNew = true;
 111   }
 112
 113   if (!isNew)
 114     return {symVector[symIndex], false};
 115
 116   Symbol *sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
 117   sym->isUsedInRegularObj = false;
 118   sym->canInline = true;
 119   sym->traced = trace;
 120   sym->forceExport = false;
 121   sym->referenced = !config->gcSections;
 122   symVector.emplace_back(sym);
 123   return {sym, true};
 124 }
 125
 126 std::pair<Symbol *, bool> SymbolTable::insert(StringRef name,
 127                                               const InputFile *file) {
 128   Symbol *s;
 129   bool wasInserted;
 130   std::tie(s, wasInserted) = insertName(name);
 131
 132   if (!file || file->kind() == InputFile::ObjectKind)
 133     s->isUsedInRegularObj = true;
 134
 135   return {s, wasInserted};
 136 }
 137
 138 static void reportTypeError(const Symbol *existing, const InputFile *file,
 139                             llvm::wasm::WasmSymbolType type) {
 140   error("symbol type mismatch: " + toString(*existing) + "\n>>> defined as " +
 141         toString(existing->getWasmType()) + " in " +
 142         toString(existing->getFile()) + "\n>>> defined as " + toString(type) +
 143         " in " + toString(file));
 144 }
 145
 146 // Check the type of new symbol matches that of the symbol is replacing.
 147 // Returns true if the function types match, false is there is a signature
 148 // mismatch.
 149 static bool signatureMatches(FunctionSymbol *existing,
 150                              const WasmSignature *newSig) {
 151   const WasmSignature *oldSig = existing->signature;
 152
 153   // If either function is missing a signature (this happens for bitcode
 154   // symbols) then assume they match.  Any mismatch will be reported later
 155   // when the LTO objects are added.
 156   if (!newSig || !oldSig)
 157     return true;
 158
 159   return *newSig == *oldSig;
 160 }
 161
 162 static void checkGlobalType(const Symbol *existing, const InputFile *file,
 163                             const WasmGlobalType *newType) {
 164   if (!isa<GlobalSymbol>(existing)) {
 165     reportTypeError(existing, file, WASM_SYMBOL_TYPE_GLOBAL);
 166     return;
 167   }
 168
 169   const WasmGlobalType *oldType = cast<GlobalSymbol>(existing)->getGlobalType();
 170   if (*newType != *oldType) {
 171     error("Global type mismatch: " + existing->getName() + "\n>>> defined as " +
 172           toString(*oldType) + " in " + toString(existing->getFile()) +
 173           "\n>>> defined as " + toString(*newType) + " in " + toString(file));
 174   }
 175 }
 176
 177 static void checkTagType(const Symbol *existing, const InputFile *file,
 178                          const WasmSignature *newSig) {
 179   const auto *existingTag = dyn_cast<TagSymbol>(existing);
 180   if (!isa<TagSymbol>(existing)) {
 181     reportTypeError(existing, file, WASM_SYMBOL_TYPE_TAG);
 182     return;
 183   }
 184
 185   const WasmSignature *oldSig = existingTag->signature;
 186   if (*newSig != *oldSig)
 187     warn("Tag signature mismatch: " + existing->getName() +
 188          "\n>>> defined as " + toString(*oldSig) + " in " +
 189          toString(existing->getFile()) + "\n>>> defined as " +
 190          toString(*newSig) + " in " + toString(file));
 191 }
 192
 193 static void checkTableType(const Symbol *existing, const InputFile *file,
 194                            const WasmTableType *newType) {
 195   if (!isa<TableSymbol>(existing)) {
 196     reportTypeError(existing, file, WASM_SYMBOL_TYPE_TABLE);
 197     return;
 198   }
 199
 200   const WasmTableType *oldType = cast<TableSymbol>(existing)->getTableType();
 201   if (newType->ElemType != oldType->ElemType) {
 202     error("Table type mismatch: " + existing->getName() + "\n>>> defined as " +
 203           toString(*oldType) + " in " + toString(existing->getFile()) +
 204           "\n>>> defined as " + toString(*newType) + " in " + toString(file));
 205   }
 206   // FIXME: No assertions currently on the limits.
 207 }
 208
 209 static void checkDataType(const Symbol *existing, const InputFile *file) {
 210   if (!isa<DataSymbol>(existing))
 211     reportTypeError(existing, file, WASM_SYMBOL_TYPE_DATA);
 212 }
 213
 214 DefinedFunction *SymbolTable::addSyntheticFunction(StringRef name,
 215                                                    uint32_t flags,
 216                                                    InputFunction *function) {
 217   LLVM_DEBUG(dbgs() << "addSyntheticFunction: " << name << "\n");
 218   assert(!find(name));
 219   syntheticFunctions.emplace_back(function);
 220   return replaceSymbol<DefinedFunction>(insertName(name).first, name,
 221                                         flags, nullptr, function);
 222 }
 223
 224 // Adds an optional, linker generated, data symbol.  The symbol will only be
 225 // added if there is an undefine reference to it, or if it is explicitly
 226 // exported via the --export flag.  Otherwise we don't add the symbol and return
 227 // nullptr.
 228 DefinedData *SymbolTable::addOptionalDataSymbol(StringRef name,
 229                                                 uint64_t value) {
 230   Symbol *s = find(name);
 231   if (!s && (config->exportAll || config->exportedSymbols.count(name) != 0))
 232     s = insertName(name).first;
 233   else if (!s || s->isDefined())
 234     return nullptr;
 235   LLVM_DEBUG(dbgs() << "addOptionalDataSymbol: " << name << "\n");
 236   auto *rtn = replaceSymbol<DefinedData>(
 237       s, name, WASM_SYMBOL_VISIBILITY_HIDDEN | WASM_SYMBOL_ABSOLUTE);
 238   rtn->setVA(value);
 239   rtn->referenced = true;
 240   return rtn;
 241 }
 242
 243 DefinedData *SymbolTable::addSyntheticDataSymbol(StringRef name,
 244                                                  uint32_t flags) {
 245   LLVM_DEBUG(dbgs() << "addSyntheticDataSymbol: " << name << "\n");
 246   assert(!find(name));
 247   return replaceSymbol<DefinedData>(insertName(name).first, name,
 248                                     flags | WASM_SYMBOL_ABSOLUTE);
 249 }
 250
 251 DefinedGlobal *SymbolTable::addSyntheticGlobal(StringRef name, uint32_t flags,
 252                                                InputGlobal *global) {
 253   LLVM_DEBUG(dbgs() << "addSyntheticGlobal: " << name << " -> " << global
 254                     << "\n");
 255   assert(!find(name));
 256   syntheticGlobals.emplace_back(global);
 257   return replaceSymbol<DefinedGlobal>(insertName(name).first, name, flags,
 258                                       nullptr, global);
 259 }
 260
 261 DefinedGlobal *SymbolTable::addOptionalGlobalSymbol(StringRef name,
 262                                                     InputGlobal *global) {
 263   Symbol *s = find(name);
 264   if (!s || s->isDefined())
 265     return nullptr;
 266   LLVM_DEBUG(dbgs() << "addOptionalGlobalSymbol: " << name << " -> " << global
 267                     << "\n");
 268   syntheticGlobals.emplace_back(global);
 269   return replaceSymbol<DefinedGlobal>(s, name, WASM_SYMBOL_VISIBILITY_HIDDEN,
 270                                       nullptr, global);
 271 }
 272
 273 DefinedTable *SymbolTable::addSyntheticTable(StringRef name, uint32_t flags,
 274                                              InputTable *table) {
 275   LLVM_DEBUG(dbgs() << "addSyntheticTable: " << name << " -> " << table
 276                     << "\n");
 277   Symbol *s = find(name);
 278   assert(!s || s->isUndefined());
 279   if (!s)
 280     s = insertName(name).first;
 281   syntheticTables.emplace_back(table);
 282   return replaceSymbol<DefinedTable>(s, name, flags, nullptr, table);
 283 }
 284
 285 static bool shouldReplace(const Symbol *existing, InputFile *newFile,
 286                           uint32_t newFlags) {
 287   // If existing symbol is undefined, replace it.
 288   if (!existing->isDefined()) {
 289     LLVM_DEBUG(dbgs() << "resolving existing undefined symbol: "
 290                       << existing->getName() << "\n");
 291     return true;
 292   }
 293
 294   // Now we have two defined symbols. If the new one is weak, we can ignore it.
 295   if ((newFlags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) {
 296     LLVM_DEBUG(dbgs() << "existing symbol takes precedence\n");
 297     return false;
 298   }
 299
 300   // If the existing symbol is weak, we should replace it.
 301   if (existing->isWeak()) {
 302     LLVM_DEBUG(dbgs() << "replacing existing weak symbol\n");
 303     return true;
 304   }
 305
 306   // Neither symbol is week. They conflict.
 307   error("duplicate symbol: " + toString(*existing) + "\n>>> defined in " +
 308         toString(existing->getFile()) + "\n>>> defined in " +
 309         toString(newFile));
 310   return true;
 311 }
 312
 313 Symbol *SymbolTable::addDefinedFunction(StringRef name, uint32_t flags,
 314                                         InputFile *file,
 315                                         InputFunction *function) {
 316   LLVM_DEBUG(dbgs() << "addDefinedFunction: " << name << " ["
 317                     << (function ? toString(function->signature) : "none")
 318                     << "]\n");
 319   Symbol *s;
 320   bool wasInserted;
 321   std::tie(s, wasInserted) = insert(name, file);
 322
 323   auto replaceSym = [&](Symbol *sym) {
 324     // If the new defined function doesn't have signature (i.e. bitcode
 325     // functions) but the old symbol does, then preserve the old signature
 326     const WasmSignature *oldSig = s->getSignature();
 327     auto* newSym = replaceSymbol<DefinedFunction>(sym, name, flags, file, function);
 328     if (!newSym->signature)
 329       newSym->signature = oldSig;
 330   };
 331
 332   if (wasInserted || s->isLazy()) {
 333     replaceSym(s);
 334     return s;
 335   }
 336
 337   auto existingFunction = dyn_cast<FunctionSymbol>(s);
 338   if (!existingFunction) {
 339     reportTypeError(s, file, WASM_SYMBOL_TYPE_FUNCTION);
 340     return s;
 341   }
 342
 343   bool checkSig = true;
 344   if (auto ud = dyn_cast<UndefinedFunction>(existingFunction))
 345     checkSig = ud->isCalledDirectly;
 346
 347   if (checkSig && function && !signatureMatches(existingFunction, &function->signature)) {
 348     Symbol* variant;
 349     if (getFunctionVariant(s, &function->signature, file, &variant))
 350       // New variant, always replace
 351       replaceSym(variant);
 352     else if (shouldReplace(s, file, flags))
 353       // Variant already exists, replace it after checking shouldReplace
 354       replaceSym(variant);
 355
 356     // This variant we found take the place in the symbol table as the primary
 357     // variant.
 358     replace(name, variant);
 359     return variant;
 360   }
 361
 362   // Existing function with matching signature.
 363   if (shouldReplace(s, file, flags))
 364     replaceSym(s);
 365
 366   return s;
 367 }
 368
 369 Symbol *SymbolTable::addDefinedData(StringRef name, uint32_t flags,
 370                                     InputFile *file, InputChunk *segment,
 371                                     uint64_t address, uint64_t size) {
 372   LLVM_DEBUG(dbgs() << "addDefinedData:" << name << " addr:" << address
 373                     << "\n");
 374   Symbol *s;
 375   bool wasInserted;
 376   std::tie(s, wasInserted) = insert(name, file);
 377
 378   auto replaceSym = [&]() {
 379     replaceSymbol<DefinedData>(s, name, flags, file, segment, address, size);
 380   };
 381
 382   if (wasInserted || s->isLazy()) {
 383     replaceSym();
 384     return s;
 385   }
 386
 387   checkDataType(s, file);
 388
 389   if (shouldReplace(s, file, flags))
 390     replaceSym();
 391   return s;
 392 }
 393
 394 Symbol *SymbolTable::addDefinedGlobal(StringRef name, uint32_t flags,
 395                                       InputFile *file, InputGlobal *global) {
 396   LLVM_DEBUG(dbgs() << "addDefinedGlobal:" << name << "\n");
 397
 398   Symbol *s;
 399   bool wasInserted;
 400   std::tie(s, wasInserted) = insert(name, file);
 401
 402   auto replaceSym = [&]() {
 403     replaceSymbol<DefinedGlobal>(s, name, flags, file, global);
 404   };
 405
 406   if (wasInserted || s->isLazy()) {
 407     replaceSym();
 408     return s;
 409   }
 410
 411   checkGlobalType(s, file, &global->getType());
 412
 413   if (shouldReplace(s, file, flags))
 414     replaceSym();
 415   return s;
 416 }
 417
 418 Symbol *SymbolTable::addDefinedTag(StringRef name, uint32_t flags,
 419                                    InputFile *file, InputTag *tag) {
 420   LLVM_DEBUG(dbgs() << "addDefinedTag:" << name << "\n");
 421
 422   Symbol *s;
 423   bool wasInserted;
 424   std::tie(s, wasInserted) = insert(name, file);
 425
 426   auto replaceSym = [&]() {
 427     replaceSymbol<DefinedTag>(s, name, flags, file, tag);
 428   };
 429
 430   if (wasInserted || s->isLazy()) {
 431     replaceSym();
 432     return s;
 433   }
 434
 435   checkTagType(s, file, &tag->signature);
 436
 437   if (shouldReplace(s, file, flags))
 438     replaceSym();
 439   return s;
 440 }
 441
 442 Symbol *SymbolTable::addDefinedTable(StringRef name, uint32_t flags,
 443                                      InputFile *file, InputTable *table) {
 444   LLVM_DEBUG(dbgs() << "addDefinedTable:" << name << "\n");
 445
 446   Symbol *s;
 447   bool wasInserted;
 448   std::tie(s, wasInserted) = insert(name, file);
 449
 450   auto replaceSym = [&]() {
 451     replaceSymbol<DefinedTable>(s, name, flags, file, table);
 452   };
 453
 454   if (wasInserted || s->isLazy()) {
 455     replaceSym();
 456     return s;
 457   }
 458
 459   checkTableType(s, file, &table->getType());
 460
 461   if (shouldReplace(s, file, flags))
 462     replaceSym();
 463   return s;
 464 }
 465
 466 // This function get called when an undefined symbol is added, and there is
 467 // already an existing one in the symbols table.  In this case we check that
 468 // custom 'import-module' and 'import-field' symbol attributes agree.
 469 // With LTO these attributes are not available when the bitcode is read and only
 470 // become available when the LTO object is read.  In this case we silently
 471 // replace the empty attributes with the valid ones.
 472 template <typename T>
 473 static void setImportAttributes(T *existing,
 474                                 std::optional<StringRef> importName,
 475                                 std::optional<StringRef> importModule,
 476                                 uint32_t flags, InputFile *file) {
 477   if (importName) {
 478     if (!existing->importName)
 479       existing->importName = importName;
 480     if (existing->importName != importName)
 481       error("import name mismatch for symbol: " + toString(*existing) +
 482             "\n>>> defined as " + *existing->importName + " in " +
 483             toString(existing->getFile()) + "\n>>> defined as " + *importName +
 484             " in " + toString(file));
 485   }
 486
 487   if (importModule) {
 488     if (!existing->importModule)
 489       existing->importModule = importModule;
 490     if (existing->importModule != importModule)
 491       error("import module mismatch for symbol: " + toString(*existing) +
 492             "\n>>> defined as " + *existing->importModule + " in " +
 493             toString(existing->getFile()) + "\n>>> defined as " +
 494             *importModule + " in " + toString(file));
 495   }
 496
 497   // Update symbol binding, if the existing symbol is weak
 498   uint32_t binding = flags & WASM_SYMBOL_BINDING_MASK;
 499   if (existing->isWeak() && binding != WASM_SYMBOL_BINDING_WEAK) {
 500     existing->flags = (existing->flags & ~WASM_SYMBOL_BINDING_MASK) | binding;
 501   }
 502 }
 503
 504 Symbol *SymbolTable::addUndefinedFunction(StringRef name,
 505                                           std::optional<StringRef> importName,
 506                                           std::optional<StringRef> importModule,
 507                                           uint32_t flags, InputFile *file,
 508                                           const WasmSignature *sig,
 509                                           bool isCalledDirectly) {
 510   LLVM_DEBUG(dbgs() << "addUndefinedFunction: " << name << " ["
 511                     << (sig ? toString(*sig) : "none")
 512                     << "] IsCalledDirectly:" << isCalledDirectly << " flags=0x"
 513                     << utohexstr(flags) << "\n");
 514   assert(flags & WASM_SYMBOL_UNDEFINED);
 515
 516   Symbol *s;
 517   bool wasInserted;
 518   std::tie(s, wasInserted) = insert(name, file);
 519   if (s->traced)
 520     printTraceSymbolUndefined(name, file);
 521
 522   auto replaceSym = [&]() {
 523     replaceSymbol<UndefinedFunction>(s, name, importName, importModule, flags,
 524                                      file, sig, isCalledDirectly);
 525   };
 526
 527   if (wasInserted) {
 528     replaceSym();
 529   } else if (auto *lazy = dyn_cast<LazySymbol>(s)) {
 530     if ((flags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) {
 531       lazy->setWeak();
 532       lazy->signature = sig;
 533     } else {
 534       lazy->fetch();
 535       if (!config->whyExtract.empty())
 536         config->whyExtractRecords.emplace_back(toString(file), s->getFile(),
 537                                                *s);
 538     }
 539   } else {
 540     auto existingFunction = dyn_cast<FunctionSymbol>(s);
 541     if (!existingFunction) {
 542       reportTypeError(s, file, WASM_SYMBOL_TYPE_FUNCTION);
 543       return s;
 544     }
 545     if (!existingFunction->signature && sig)
 546       existingFunction->signature = sig;
 547     auto *existingUndefined = dyn_cast<UndefinedFunction>(existingFunction);
 548     if (isCalledDirectly && !signatureMatches(existingFunction, sig)) {
 549       // If the existing undefined functions is not called directly then let
 550       // this one take precedence.  Otherwise the existing function is either
 551       // directly called or defined, in which case we need a function variant.
 552       if (existingUndefined && !existingUndefined->isCalledDirectly)
 553         replaceSym();
 554       else if (getFunctionVariant(s, sig, file, &s))
 555         replaceSym();
 556     }
 557     if (existingUndefined) {
 558       setImportAttributes(existingUndefined, importName, importModule, flags,
 559                           file);
 560       if (isCalledDirectly)
 561         existingUndefined->isCalledDirectly = true;
 562       if (s->isWeak())
 563         s->flags = flags;
 564     }
 565   }
 566
 567   return s;
 568 }
 569
 570 Symbol *SymbolTable::addUndefinedData(StringRef name, uint32_t flags,
 571                                       InputFile *file) {
 572   LLVM_DEBUG(dbgs() << "addUndefinedData: " << name << "\n");
 573   assert(flags & WASM_SYMBOL_UNDEFINED);
 574
 575   Symbol *s;
 576   bool wasInserted;
 577   std::tie(s, wasInserted) = insert(name, file);
 578   if (s->traced)
 579     printTraceSymbolUndefined(name, file);
 580
 581   if (wasInserted) {
 582     replaceSymbol<UndefinedData>(s, name, flags, file);
 583   } else if (auto *lazy = dyn_cast<LazySymbol>(s)) {
 584     if ((flags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK)
 585       lazy->setWeak();
 586     else
 587       lazy->fetch();
 588   } else if (s->isDefined()) {
 589     checkDataType(s, file);
 590   } else if (s->isWeak()) {
 591     s->flags = flags;
 592   }
 593   return s;
 594 }
 595
 596 Symbol *SymbolTable::addUndefinedGlobal(StringRef name,
 597                                         std::optional<StringRef> importName,
 598                                         std::optional<StringRef> importModule,
 599                                         uint32_t flags, InputFile *file,
 600                                         const WasmGlobalType *type) {
 601   LLVM_DEBUG(dbgs() << "addUndefinedGlobal: " << name << "\n");
 602   assert(flags & WASM_SYMBOL_UNDEFINED);
 603
 604   Symbol *s;
 605   bool wasInserted;
 606   std::tie(s, wasInserted) = insert(name, file);
 607   if (s->traced)
 608     printTraceSymbolUndefined(name, file);
 609
 610   if (wasInserted)
 611     replaceSymbol<UndefinedGlobal>(s, name, importName, importModule, flags,
 612                                    file, type);
 613   else if (auto *lazy = dyn_cast<LazySymbol>(s))
 614     lazy->fetch();
 615   else if (s->isDefined())
 616     checkGlobalType(s, file, type);
 617   else if (s->isWeak())
 618     s->flags = flags;
 619   return s;
 620 }
 621
 622 Symbol *SymbolTable::addUndefinedTable(StringRef name,
 623                                        std::optional<StringRef> importName,
 624                                        std::optional<StringRef> importModule,
 625                                        uint32_t flags, InputFile *file,
 626                                        const WasmTableType *type) {
 627   LLVM_DEBUG(dbgs() << "addUndefinedTable: " << name << "\n");
 628   assert(flags & WASM_SYMBOL_UNDEFINED);
 629
 630   Symbol *s;
 631   bool wasInserted;
 632   std::tie(s, wasInserted) = insert(name, file);
 633   if (s->traced)
 634     printTraceSymbolUndefined(name, file);
 635
 636   if (wasInserted)
 637     replaceSymbol<UndefinedTable>(s, name, importName, importModule, flags,
 638                                   file, type);
 639   else if (auto *lazy = dyn_cast<LazySymbol>(s))
 640     lazy->fetch();
 641   else if (s->isDefined())
 642     checkTableType(s, file, type);
 643   else if (s->isWeak())
 644     s->flags = flags;
 645   return s;
 646 }
 647
 648 Symbol *SymbolTable::addUndefinedTag(StringRef name,
 649                                      std::optional<StringRef> importName,
 650                                      std::optional<StringRef> importModule,
 651                                      uint32_t flags, InputFile *file,
 652                                      const WasmSignature *sig) {
 653   LLVM_DEBUG(dbgs() << "addUndefinedTag: " << name << "\n");
 654   assert(flags & WASM_SYMBOL_UNDEFINED);
 655
 656   Symbol *s;
 657   bool wasInserted;
 658   std::tie(s, wasInserted) = insert(name, file);
 659   if (s->traced)
 660     printTraceSymbolUndefined(name, file);
 661
 662   if (wasInserted)
 663     replaceSymbol<UndefinedTag>(s, name, importName, importModule, flags, file,
 664                                 sig);
 665   else if (auto *lazy = dyn_cast<LazySymbol>(s))
 666     lazy->fetch();
 667   else if (s->isDefined())
 668     checkTagType(s, file, sig);
 669   else if (s->isWeak())
 670     s->flags = flags;
 671   return s;
 672 }
 673
 674 TableSymbol *SymbolTable::createUndefinedIndirectFunctionTable(StringRef name) {
 675   WasmLimits limits{0, 0, 0}; // Set by the writer.
 676   WasmTableType *type = make<WasmTableType>();
 677   type->ElemType = uint8_t(ValType::FUNCREF);
 678   type->Limits = limits;
 679   StringRef module(defaultModule);
 680   uint32_t flags = config->exportTable ? 0 : WASM_SYMBOL_VISIBILITY_HIDDEN;
 681   flags |= WASM_SYMBOL_UNDEFINED;
 682   Symbol *sym = addUndefinedTable(name, name, module, flags, nullptr, type);
 683   sym->markLive();
 684   sym->forceExport = config->exportTable;
 685   return cast<TableSymbol>(sym);
 686 }
 687
 688 TableSymbol *SymbolTable::createDefinedIndirectFunctionTable(StringRef name) {
 689   const uint32_t invalidIndex = -1;
 690   WasmLimits limits{0, 0, 0}; // Set by the writer.
 691   WasmTableType type{uint8_t(ValType::FUNCREF), limits};
 692   WasmTable desc{invalidIndex, type, name};
 693   InputTable *table = make<InputTable>(desc, nullptr);
 694   uint32_t flags = config->exportTable ? 0 : WASM_SYMBOL_VISIBILITY_HIDDEN;
 695   TableSymbol *sym = addSyntheticTable(name, flags, table);
 696   sym->markLive();
 697   sym->forceExport = config->exportTable;
 698   return sym;
 699 }
 700
 701 // Whether or not we need an indirect function table is usually a function of
 702 // whether an input declares a need for it.  However sometimes it's possible for
 703 // no input to need the indirect function table, but then a late
 704 // addInternalGOTEntry causes a function to be allocated an address.  In that
 705 // case address we synthesize a definition at the last minute.
 706 TableSymbol *SymbolTable::resolveIndirectFunctionTable(bool required) {
 707   Symbol *existing = find(functionTableName);
 708   if (existing) {
 709     if (!isa<TableSymbol>(existing)) {
 710       error(Twine("reserved symbol must be of type table: `") +
 711             functionTableName + "`");
 712       return nullptr;
 713     }
 714     if (existing->isDefined()) {
 715       error(Twine("reserved symbol must not be defined in input files: `") +
 716             functionTableName + "`");
 717       return nullptr;
 718     }
 719   }
 720
 721   if (config->importTable) {
 722     if (existing)
 723       return cast<TableSymbol>(existing);
 724     if (required)
 725       return createUndefinedIndirectFunctionTable(functionTableName);
 726   } else if ((existing && existing->isLive()) || config->exportTable ||
 727              required) {
 728     // A defined table is required.  Either because the user request an exported
 729     // table or because the table symbol is already live.  The existing table is
 730     // guaranteed to be undefined due to the check above.
 731     return createDefinedIndirectFunctionTable(functionTableName);
 732   }
 733
 734   // An indirect function table will only be present in the symbol table if
 735   // needed by a reloc; if we get here, we don't need one.
 736   return nullptr;
 737 }
 738
 739 void SymbolTable::addLazy(ArchiveFile *file, const Archive::Symbol *sym) {
 740   LLVM_DEBUG(dbgs() << "addLazy: " << sym->getName() << "\n");
 741   StringRef name = sym->getName();
 742
 743   Symbol *s;
 744   bool wasInserted;
 745   std::tie(s, wasInserted) = insertName(name);
 746
 747   if (wasInserted) {
 748     replaceSymbol<LazySymbol>(s, name, 0, file, *sym);
 749     return;
 750   }
 751
 752   if (!s->isUndefined())
 753     return;
 754
 755   // The existing symbol is undefined, load a new one from the archive,
 756   // unless the existing symbol is weak in which case replace the undefined
 757   // symbols with a LazySymbol.
 758   if (s->isWeak()) {
 759     const WasmSignature *oldSig = nullptr;
 760     // In the case of an UndefinedFunction we need to preserve the expected
 761     // signature.
 762     if (auto *f = dyn_cast<UndefinedFunction>(s))
 763       oldSig = f->signature;
 764     LLVM_DEBUG(dbgs() << "replacing existing weak undefined symbol\n");
 765     auto newSym = replaceSymbol<LazySymbol>(s, name, WASM_SYMBOL_BINDING_WEAK,
 766                                             file, *sym);
 767     newSym->signature = oldSig;
 768     return;
 769   }
 770
 771   LLVM_DEBUG(dbgs() << "replacing existing undefined\n");
 772   const InputFile *oldFile = s->getFile();
 773   file->addMember(sym);
 774   if (!config->whyExtract.empty())
 775     config->whyExtractRecords.emplace_back(toString(oldFile), s->getFile(), *s);
 776 }
 777
 778 bool SymbolTable::addComdat(StringRef name) {
 779   return comdatGroups.insert(CachedHashStringRef(name)).second;
 780 }
 781
 782 // The new signature doesn't match.  Create a variant to the symbol with the
 783 // signature encoded in the name and return that instead.  These symbols are
 784 // then unified later in handleSymbolVariants.
 785 bool SymbolTable::getFunctionVariant(Symbol* sym, const WasmSignature *sig,
 786                                      const InputFile *file, Symbol **out) {
 787   LLVM_DEBUG(dbgs() << "getFunctionVariant: " << sym->getName() << " -> "
 788                     << " " << toString(*sig) << "\n");
 789   Symbol *variant = nullptr;
 790
 791   // Linear search through symbol variants.  Should never be more than two
 792   // or three entries here.
 793   auto &variants = symVariants[CachedHashStringRef(sym->getName())];
 794   if (variants.empty())
 795     variants.push_back(sym);
 796
 797   for (Symbol* v : variants) {
 798     if (*v->getSignature() == *sig) {
 799       variant = v;
 800       break;
 801     }
 802   }
 803
 804   bool wasAdded = !variant;
 805   if (wasAdded) {
 806     // Create a new variant;
 807     LLVM_DEBUG(dbgs() << "added new variant\n");
 808     variant = reinterpret_cast<Symbol *>(make<SymbolUnion>());
 809     variant->isUsedInRegularObj =
 810         !file || file->kind() == InputFile::ObjectKind;
 811     variant->canInline = true;
 812     variant->traced = false;
 813     variant->forceExport = false;
 814     variants.push_back(variant);
 815   } else {
 816     LLVM_DEBUG(dbgs() << "variant already exists: " << toString(*variant) << "\n");
 817     assert(*variant->getSignature() == *sig);
 818   }
 819
 820   *out = variant;
 821   return wasAdded;
 822 }
 823
 824 // Set a flag for --trace-symbol so that we can print out a log message
 825 // if a new symbol with the same name is inserted into the symbol table.
 826 void SymbolTable::trace(StringRef name) {
 827   symMap.insert({CachedHashStringRef(name), -1});
 828 }
 829
 830 void SymbolTable::wrap(Symbol *sym, Symbol *real, Symbol *wrap) {
 831   // Swap symbols as instructed by -wrap.
 832   int &origIdx = symMap[CachedHashStringRef(sym->getName())];
 833   int &realIdx= symMap[CachedHashStringRef(real->getName())];
 834   int &wrapIdx = symMap[CachedHashStringRef(wrap->getName())];
 835   LLVM_DEBUG(dbgs() << "wrap: " << sym->getName() << "\n");
 836
 837   // Anyone looking up __real symbols should get the original
 838   realIdx = origIdx;
 839   // Anyone looking up the original should get the __wrap symbol
 840   origIdx = wrapIdx;
 841 }
 842
 843 static const uint8_t unreachableFn[] = {
 844     0x03 /* ULEB length */, 0x00 /* ULEB num locals */,
 845     0x00 /* opcode unreachable */, 0x0b /* opcode end */
 846 };
 847
 848 // Replace the given symbol body with an unreachable function.
 849 // This is used by handleWeakUndefines in order to generate a callable
 850 // equivalent of an undefined function and also handleSymbolVariants for
 851 // undefined functions that don't match the signature of the definition.
 852 InputFunction *SymbolTable::replaceWithUnreachable(Symbol *sym,
 853                                                    const WasmSignature &sig,
 854                                                    StringRef debugName) {
 855   auto *func = make<SyntheticFunction>(sig, sym->getName(), debugName);
 856   func->setBody(unreachableFn);
 857   syntheticFunctions.emplace_back(func);
 858   // Mark new symbols as local. For relocatable output we don't want them
 859   // to be exported outside the object file.
 860   replaceSymbol<DefinedFunction>(sym, debugName, WASM_SYMBOL_BINDING_LOCAL,
 861                                  nullptr, func);
 862   // Ensure the stub function doesn't get a table entry.  Its address
 863   // should always compare equal to the null pointer.
 864   sym->isStub = true;
 865   return func;
 866 }
 867
 868 void SymbolTable::replaceWithUndefined(Symbol *sym) {
 869   // Add a synthetic dummy for weak undefined functions.  These dummies will
 870   // be GC'd if not used as the target of any "call" instructions.
 871   StringRef debugName = saver().save("undefined_weak:" + toString(*sym));
 872   replaceWithUnreachable(sym, *sym->getSignature(), debugName);
 873   // Hide our dummy to prevent export.
 874   sym->setHidden(true);
 875 }
 876
 877 // For weak undefined functions, there may be "call" instructions that reference
 878 // the symbol. In this case, we need to synthesise a dummy/stub function that
 879 // will abort at runtime, so that relocations can still provided an operand to
 880 // the call instruction that passes Wasm validation.
 881 void SymbolTable::handleWeakUndefines() {
 882   for (Symbol *sym : symbols()) {
 883     if (sym->isUndefWeak() && sym->isUsedInRegularObj) {
 884       if (sym->getSignature()) {
 885         replaceWithUndefined(sym);
 886       } else {
 887         // It is possible for undefined functions not to have a signature (eg.
 888         // if added via "--undefined"), but weak undefined ones do have a
 889         // signature.  Lazy symbols may not be functions and therefore Sig can
 890         // still be null in some circumstance.
 891         assert(!isa<FunctionSymbol>(sym));
 892       }
 893     }
 894   }
 895 }
 896
 897 DefinedFunction *SymbolTable::createUndefinedStub(const WasmSignature &sig) {
 898   if (stubFunctions.count(sig))
 899     return stubFunctions[sig];
 900   LLVM_DEBUG(dbgs() << "createUndefinedStub: " << toString(sig) << "\n");
 901   auto *sym = reinterpret_cast<DefinedFunction *>(make<SymbolUnion>());
 902   sym->isUsedInRegularObj = true;
 903   sym->canInline = true;
 904   sym->traced = false;
 905   sym->forceExport = false;
 906   sym->signature = &sig;
 907   replaceSymbol<DefinedFunction>(
 908       sym, "undefined_stub", WASM_SYMBOL_VISIBILITY_HIDDEN, nullptr, nullptr);
 909   replaceWithUnreachable(sym, sig, "undefined_stub");
 910   stubFunctions[sig] = sym;
 911   return sym;
 912 }
 913
 914 static void reportFunctionSignatureMismatch(StringRef symName,
 915                                             FunctionSymbol *a,
 916                                             FunctionSymbol *b, bool isError) {
 917   std::string msg = ("function signature mismatch: " + symName +
 918                      "\n>>> defined as " + toString(*a->signature) + " in " +
 919                      toString(a->getFile()) + "\n>>> defined as " +
 920                      toString(*b->signature) + " in " + toString(b->getFile()))
 921                         .str();
 922   if (isError)
 923     error(msg);
 924   else
 925     warn(msg);
 926 }
 927
 928 // Remove any variant symbols that were created due to function signature
 929 // mismatches.
 930 void SymbolTable::handleSymbolVariants() {
 931   for (auto pair : symVariants) {
 932     // Push the initial symbol onto the list of variants.
 933     StringRef symName = pair.first.val();
 934     std::vector<Symbol *> &variants = pair.second;
 935
 936 #ifndef NDEBUG
 937     LLVM_DEBUG(dbgs() << "symbol with (" << variants.size()
 938                       << ") variants: " << symName << "\n");
 939     for (auto *s: variants) {
 940       auto *f = cast<FunctionSymbol>(s);
 941       LLVM_DEBUG(dbgs() << " variant: " + f->getName() << " "
 942                         << toString(*f->signature) << "\n");
 943     }
 944 #endif
 945
 946     // Find the one definition.
 947     DefinedFunction *defined = nullptr;
 948     for (auto *symbol : variants) {
 949       if (auto f = dyn_cast<DefinedFunction>(symbol)) {
 950         defined = f;
 951         break;
 952       }
 953     }
 954
 955     // If there are no definitions, and the undefined symbols disagree on
 956     // the signature, there is not we can do since we don't know which one
 957     // to use as the signature on the import.
 958     if (!defined) {
 959       reportFunctionSignatureMismatch(symName,
 960                                       cast<FunctionSymbol>(variants[0]),
 961                                       cast<FunctionSymbol>(variants[1]), true);
 962       return;
 963     }
 964
 965     for (auto *symbol : variants) {
 966       if (symbol != defined) {
 967         auto *f = cast<FunctionSymbol>(symbol);
 968         reportFunctionSignatureMismatch(symName, f, defined, false);
 969         StringRef debugName =
 970             saver().save("signature_mismatch:" + toString(*f));
 971         replaceWithUnreachable(f, *f->signature, debugName);
 972       }
 973     }
 974   }
 975 }
 976
 977 } // namespace wasm::lld