[lld][WebAssembly] Implement --why-extract flag from the ELF backend

[sbc100]

Summary

See https://reviews.llvm.org/D109572 for the original ELF version.

[sbc100]

• revert ELF

[sbc100]

• Revert part

[dschuff]

I love these kinds of debugging options...

[MaskRay]

lld/wasm/SymbolTable.cpp

767

drop braces for one-line simple statements.

[sbc100]

• feedback

lld/test/wasm/why-extract.s

+# RUN: rm -rf %t && split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %t/main.s -o %t/main.o
+# RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %t/a.s -o %t/a.o
+# RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %t/a_b.s -o %t/a_b.o
+# RUN: llvm-mc -filetype=obj -triple=wasm32-unknown-unknown %t/b.s -o %t/b.o
+# RUN: llvm-ar rc %t/a.a %t/a.o
+# RUN: llvm-ar rc %t/a_b.a %t/a_b.o
+# RUN: llvm-ar rc %t/b.a %t/b.o
+# RUN: cd %t
+
+## Nothing is extracted from an archive. The file is created with just a header.
+# RUN: wasm-ld main.o a.o b.a -o /dev/null --why-extract=why1.txt
+# RUN: FileCheck %s --input-file=why1.txt --check-prefix=CHECK1 --match-full-lines --strict-whitespace
+
+#      CHECK1:reference extracted symbol
+#  CHECK1-NOT:{{.}}
+
+## Some archive members are extracted.
+# RUN: wasm-ld main.o a_b.a b.a -o /dev/null --why-extract=why2.txt
+# RUN: FileCheck %s --input-file=why2.txt --check-prefix=CHECK2 --match-full-lines --strict-whitespace
+
+#      CHECK2:reference extracted symbol
+# CHECK2-NEXT:main.o  a_b.a(a_b.o)  a
+# CHECK2-NEXT:a_b.a(a_b.o)  b.a(b.o)  b()
+
+## An undefined symbol error does not suppress the output.
+# RUN: not wasm-ld main.o a_b.a -o /dev/null --why-extract=why3.txt
+# RUN: FileCheck %s --input-file=why3.txt --check-prefix=CHECK3 --match-full-lines --strict-whitespace
+
+## Check that backward references are supported.
+## - means stdout.
+# RUN: wasm-ld b.a a_b.a main.o -o /dev/null --why-extract=- | FileCheck %s --check-prefix=CHECK4
+
+#      CHECK3:reference extracted symbol
+# CHECK3-NEXT:main.o  a_b.a(a_b.o)  a
+
+#      CHECK4:reference extracted symbol
+# CHECK4-NEXT:a_b.a(a_b.o)  b.a(b.o)  b()
+# CHECK4-NEXT:main.o  a_b.a(a_b.o)  a
+
+# RUN: wasm-ld main.o a_b.a b.a -o /dev/null --no-demangle --why-extract=- | FileCheck %s --check-prefix=MANGLED
+
+# MANGLED: a_b.a(a_b.o) b.a(b.o)  _Z1bv
+
+# RUN: wasm-ld main.o a.a b.a -o /dev/null -u _Z1bv --why-extract=- | FileCheck %s --check-prefix=UNDEFINED
+
+## We insert -u symbol before processing other files, so its name is <internal>.
+## This is not ideal.
+# UNDEFINED: <internal> b.a(b.o)  b()
+
+# RUN: wasm-ld main.o a.a b.a -o /dev/null -e _Z1bv --why-extract=- | FileCheck %s --check-prefix=ENTRY
+
+# ENTRY: --entry  b.a(b.o)  b()
+
+# SCRIPT: <internal>  b.a(b.o)  b()
+
+# RUN: not wasm-ld -shared main.o -o /dev/null --why-extract=/ 2>&1 | FileCheck %s --check-prefix=ERR
+
+# ERR: error: cannot open --why-extract= file /: {{.*}}
+
+#--- main.s
+.globl _start
+.functype a () -> ()
+_start:
+  .functype _start () -> ()
+  call a
+  end_function
+
+#--- a.s
+.globl a
+a:
+  .functype a () -> ()
+  end_function
+
+#--- a_b.s
+.functype _Z1bv () -> ()
+.globl a
+a:
+  .functype a () -> ()
+  call _Z1bv
+  end_function
+
+#--- b.s
+.globl _Z1bv
+_Z1bv:
+  .functype _Z1bv () -> ()
+  end_function

lld/wasm/Config.h

 
 namespace llvm::CodeGenOpt {
 enum Level : int;
 } // namespace llvm::CodeGenOpt
 
 namespace lld {
 namespace wasm {
 
+class InputFile;
+class Symbol;
+
 // For --unresolved-symbols.
 enum class UnresolvedPolicy { ReportError, Warn, Ignore, ImportDynamic };
 
 // For --build-id.
 enum class BuildIdKind { None, Fast, Sha1, Hexstring, Uuid };
 
 // This struct contains the global configuration for the linker.
 // Most fields are direct mapping from the command line options
struct Configuration {
   bool ltoDebugPassManager;
   UnresolvedPolicy unresolvedSymbols;
   BuildIdKind buildId = BuildIdKind::None;
 
   llvm::StringRef entry;
   llvm::StringRef mapFile;
   llvm::StringRef outputFile;
   llvm::StringRef thinLTOCacheDir;
+  llvm::StringRef whyExtract;
 
   llvm::StringSet<> allowUndefinedSymbols;
   llvm::StringSet<> exportedSymbols;
   std::vector<llvm::StringRef> requiredExports;
   llvm::SmallVector<llvm::StringRef, 0> searchPaths;
   llvm::CachePruningPolicy thinLTOCachePolicy;
   std::optional<std::vector<std::string>> features;
   std::optional<std::vector<std::string>> extraFeatures;
   llvm::SmallVector<uint8_t, 0> buildIdVector;
 
   // The following config options do not directly correspond to any
-  // particular command line options.
+  // particular command line options, and should probably be moved to seperate
+  // Ctx struct as in ELF/Config.h
 
   // True if we are creating position-independent code.
   bool isPic;
 
   // True if we have an MVP input that uses __indirect_function_table and which
   // requires it to be allocated to table number 0.
   bool legacyFunctionTable = false;
 
   // The table offset at which to place function addresses.  We reserve zero
   // for the null function pointer.  This gets set to 1 for executables and 0
   // for shared libraries (since they always added to a dynamic offset at
   // runtime).
   uint32_t tableBase = 0;
 
   // Will be set to true if bss data segments should be emitted. In most cases
   // this is not necessary.
   bool emitBssSegments = false;
+
+  // A tuple of (reference, extractedFile, sym). Used by --why-extract=.
+  llvm::SmallVector<std::tuple<std::string, const InputFile *, const Symbol &>,
+                    0>
+      whyExtractRecords;
 };
 
 // The only instance of Configuration struct.
 extern Configuration *config;
 
 } // namespace wasm
 } // namespace lld
 
 #endif

lld/wasm/Driver.cpp

static void readConfigs(opt::InputArgList &args) {
   config->stripDebug = args.hasArg(OPT_strip_debug);
   config->stackFirst = args.hasArg(OPT_stack_first);
   config->trace = args.hasArg(OPT_trace);
   config->thinLTOCacheDir = args.getLastArgValue(OPT_thinlto_cache_dir);
   config->thinLTOCachePolicy = CHECK(
       parseCachePruningPolicy(args.getLastArgValue(OPT_thinlto_cache_policy)),
       "--thinlto-cache-policy: invalid cache policy");
   config->unresolvedSymbols = getUnresolvedSymbolPolicy(args);
+  config->whyExtract = args.getLastArgValue(OPT_why_extract);
   errorHandler().verbose = args.hasArg(OPT_verbose);
   LLVM_DEBUG(errorHandler().verbose = true);
 
   config->initialMemory = args::getInteger(args, OPT_initial_memory, 0);
   config->globalBase = args::getInteger(args, OPT_global_base, 0);
   config->maxMemory = args::getInteger(args, OPT_max_memory, 0);
   config->zStackSize =
       args::getZOptionValue(args, OPT_z, "stack-size", WasmPageSize);

 
 static const char *getReproduceOption(opt::InputArgList &args) {
   if (auto *arg = args.getLastArg(OPT_reproduce))
     return arg->getValue();
   return getenv("LLD_REPRODUCE");
 }
 
 // Force Sym to be entered in the output. Used for -u or equivalent.
-static Symbol *handleUndefined(StringRef name) {
+static Symbol *handleUndefined(StringRef name, const char *option) {
   Symbol *sym = symtab->find(name);
   if (!sym)
     return nullptr;
 
   // Since symbol S may not be used inside the program, LTO may
   // eliminate it. Mark the symbol as "used" to prevent it.
   sym->isUsedInRegularObj = true;
 
-  if (auto *lazySym = dyn_cast<LazySymbol>(sym))
+  if (auto *lazySym = dyn_cast<LazySymbol>(sym)) {
     lazySym->fetch();
+    if (!config->whyExtract.empty())
+      config->whyExtractRecords.emplace_back(option, sym->getFile(), *sym);
+  }
 
   return sym;
 }
 
 static void handleLibcall(StringRef name) {
   Symbol *sym = symtab->find(name);
   if (!sym)
     return;
 
   if (auto *lazySym = dyn_cast<LazySymbol>(sym)) {
     MemoryBufferRef mb = lazySym->getMemberBuffer();
-    if (isBitcode(mb))
+    if (isBitcode(mb)) {
+      if (!config->whyExtract.empty())
+        config->whyExtractRecords.emplace_back("<libcall>", sym->getFile(),
+                                               *sym);
       lazySym->fetch();
     }
   }
+}
+
+static void writeWhyExtract() {
+  if (config->whyExtract.empty())
+    return;
+
+  std::error_code ec;
+  raw_fd_ostream os(config->whyExtract, ec, sys::fs::OF_None);
+  if (ec) {
+    error("cannot open --why-extract= file " + config->whyExtract + ": " +
+          ec.message());
+    return;
+  }
+
+  os << "reference\textracted\tsymbol\n";
+  for (auto &entry : config->whyExtractRecords) {
+    os << std::get<0>(entry) << '\t' << toString(std::get<1>(entry)) << '\t'
+       << toString(std::get<2>(entry)) << '\n';
+  }
+}
 
 // Equivalent of demote demoteSharedAndLazySymbols() in the ELF linker
 static void demoteLazySymbols() {
   for (Symbol *sym : symtab->symbols()) {
     if (auto* s = dyn_cast<LazySymbol>(sym)) {
       if (s->signature) {
         LLVM_DEBUG(llvm::dbgs()
                    << "demoting lazy func: " << s->getName() << "\n");
void LinkerDriver::linkerMain(ArrayRef<const char *> argsArr) {
   // symbols that we need to the symbol table.
   for (InputFile *f : files)
     symtab->addFile(f);
   if (errorCount())
     return;
 
   // Handle the `--undefined <sym>` options.
   for (auto *arg : args.filtered(OPT_undefined))
-    handleUndefined(arg->getValue());
+    handleUndefined(arg->getValue(), "<internal>");
 
   // Handle the `--export <sym>` options
   // This works like --undefined but also exports the symbol if its found
   for (auto &iter : config->exportedSymbols)
-    handleUndefined(iter.first());
+    handleUndefined(iter.first(), "--export");
 
   Symbol *entrySym = nullptr;
   if (!config->relocatable && !config->entry.empty()) {
-    entrySym = handleUndefined(config->entry);
+    entrySym = handleUndefined(config->entry, "--entry");
     if (entrySym && entrySym->isDefined())
       entrySym->forceExport = true;
     else
       error("entry symbol not defined (pass --no-entry to suppress): " +
             config->entry);
   }
 
   // If the user code defines a `__wasm_call_dtors` function, remember it so
   // that we can call it from the command export wrappers. Unlike
   // `__wasm_call_ctors` which we synthesize, `__wasm_call_dtors` is defined
   // by libc/etc., because destructors are registered dynamically with
   // `__cxa_atexit` and friends.
   if (!config->relocatable && !config->shared &&
       !WasmSym::callCtors->isUsedInRegularObj &&
       WasmSym::callCtors->getName() != config->entry &&
       !config->exportedSymbols.count(WasmSym::callCtors->getName())) {
-    if (Symbol *callDtors = handleUndefined("__wasm_call_dtors")) {
+    if (Symbol *callDtors =
+            handleUndefined("__wasm_call_dtors", "<internal>")) {
       if (auto *callDtorsFunc = dyn_cast<DefinedFunction>(callDtors)) {
         if (callDtorsFunc->signature &&
             (!callDtorsFunc->signature->Params.empty() ||
              !callDtorsFunc->signature->Returns.empty())) {
           error("__wasm_call_dtors must have no argument or return values");
         }
         WasmSym::callDtors = callDtorsFunc;
       } else {
void LinkerDriver::linkerMain(ArrayRef<const char *> argsArr) {
   // definition is in bitcode. Any other required libcall symbols will be added
   // to the link after LTO when we add the LTO object file to the link.
   if (!symtab->bitcodeFiles.empty())
     for (auto *s : lto::LTO::getRuntimeLibcallSymbols())
       handleLibcall(s);
   if (errorCount())
     return;
 
+  writeWhyExtract();
+
   // Do link-time optimization if given files are LLVM bitcode files.
   // This compiles bitcode files into real object files.
   symtab->compileBitcodeFiles();
   if (errorCount())
     return;
 
   createOptionalSymbols();
 

lld/wasm/Options.td

 
 def stack_first: FF<"stack-first">,
   HelpText<"Place stack at start of linear memory rather than after data">;
 
 defm whole_archive: B<"whole-archive",
     "Force load of all members in a static library",
     "Do not force load of all members in a static library (default)">;
 
+def why_extract: JJ<"why-extract=">, HelpText<"Print to a file about why archive members are extracted">;
+
 defm check_features: BB<"check-features",
     "Check feature compatibility of linked objects (default)",
     "Ignore feature compatibility of linked objects">;
 
 def features: CommaJoined<["--", "-"], "features=">,
   HelpText<"Comma-separated used features, inferred from input objects by default.">;
 
 def extra_features: CommaJoined<["--", "-"], "extra-features=">,

lld/wasm/SymbolTable.cpp

Symbol *SymbolTable::addUndefinedFunction(StringRef name,
   if (wasInserted) {
     replaceSym();
   } else if (auto *lazy = dyn_cast<LazySymbol>(s)) {
     if ((flags & WASM_SYMBOL_BINDING_MASK) == WASM_SYMBOL_BINDING_WEAK) {
       lazy->setWeak();
       lazy->signature = sig;
     } else {
       lazy->fetch();
+      if (!config->whyExtract.empty())
+        config->whyExtractRecords.emplace_back(toString(file), s->getFile(),
+                                               *s);
     }
   } else {
     auto existingFunction = dyn_cast<FunctionSymbol>(s);
     if (!existingFunction) {
       reportTypeError(s, file, WASM_SYMBOL_TYPE_FUNCTION);
       return s;
     }
     if (!existingFunction->signature && sig)
if (s->isWeak()) {
     LLVM_DEBUG(dbgs() << "replacing existing weak undefined symbol\n");
     auto newSym = replaceSymbol<LazySymbol>(s, name, WASM_SYMBOL_BINDING_WEAK,
                                             file, *sym);
     newSym->signature = oldSig;
     return;
   }
 
   LLVM_DEBUG(dbgs() << "replacing existing undefined\n");
+  const InputFile *oldFile = s->getFile();
   file->addMember(sym);
+  if (!config->whyExtract.empty())
+    config->whyExtractRecords.emplace_back(toString(oldFile), s->getFile(), *s);
 }
 
 bool SymbolTable::addComdat(StringRef name) {
   return comdatGroups.insert(CachedHashStringRef(name)).second;
 }
 
 // The new signature doesn't match.  Create a variant to the symbol with the
 // signature encoded in the name and return that instead.  These symbols are