[WebAssembly] Implement --trace (-y) and --trace-symbol

[sbc100]

• update test

[sbc100]

• remove debugging

[ruiu]

wasm/SymbolTable.cpp

420

Is this implementation complete? I think you can track only one symbol with this implementation.

[sbc100]

wasm/SymbolTable.cpp

420

Yes, you are correct. Thats all I needed in my example use case, so I didn't realize the intention was allow multiple symbols to be traced.

[sbc100]

• .
• support multiple traced symbols
• feedback

[sbc100]

• clang-format

[ruiu]

wasm/SymbolTable.cpp

89–90

Any operation that we do for each symbol can be super expensive, as the number of symbols can be in the order of millions. In particular, lld should do more than one hash table lookup for each symbol. This is one of reasons why lld is so fast.

So, this new hash table shouldn't be added. Take a look at ELF/SymbolTable.cpp. We implemented this feature without adding a new hash table lookup.

[sbc100]

• update test
• avoid hash

[ruiu]

Overall looks good.

test/ELF/trace.s

9

unrelated change?

wasm/SymbolTable.cpp

95

Use true instead of 1.

wasm/SymbolTable.h

83–84

Thank you for adding this comment.

88–91

Dead members.

[sbc100]

• feedback

[ruiu]

LGTM

test/ELF/trace.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t.foo.o
 
 ## Check -t
 # RUN: ld.lld -shared %t.foo.o -o %t.so -t 2>&1 | FileCheck %s
 # CHECK: {{.*}}.foo.o
 
 ## Check --trace alias
-# RUN: ld.lld -shared %t.foo.o -o %t.so -t 2>&1 | FileCheck %s
+# RUN: ld.lld -shared %t.foo.o -o %t.so --trace 2>&1 | FileCheck %s

test/wasm/trace-symbol.ll

+; RUN: llc -filetype=obj %p/Inputs/ret32.ll -o %t.ret32.o
+; RUN: llc -filetype=obj %p/Inputs/start.ll -o %t.start.o
+; RUN: wasm-ld -o %t.wasm %t.start.o %t.ret32.o -y ret32 -y _start 2>&1 | FileCheck %s -check-prefixes=RET32,START
+
+; check alias
+; RUN: wasm-ld -o %t.wasm %t.start.o %t.ret32.o -trace-symbol=ret32 2>&1 | FileCheck %s -check-prefixes=RET32,NOTSTART
+
+target triple = "wasm32-unknown-unknown"
+
+declare i32 @ret32()
+
+define void @_start() {
+entry:
+  %call1 = call i32 @ret32()
+  ret void
+}
+
+; NOTSTART-NOT: definition of _start
+; START: .start.o: definition of _start
+; RET32: .ret32.o: definition of ret32

test/wasm/trace.test

+RUN: llc -filetype=obj %p/Inputs/start.ll -o %t.foo.o
+
+# Check -t
+RUN: wasm-ld %t.foo.o -o out.wasm -t 2>&1 | FileCheck %s
+CHECK: {{.*}}.foo.o
+
+# Check --trace alias
+RUN: wasm-ld %t.foo.o -o out.wasm --trace 2>&1 | FileCheck %s

wasm/Config.h

struct Configuration {
   bool Pie;
   bool PrintGcSections;
   bool Relocatable;
   bool SaveTemps;
   bool Shared;
   bool StripAll;
   bool StripDebug;
   bool StackFirst;
+  bool Trace;
   uint32_t GlobalBase;
   uint32_t InitialMemory;
   uint32_t MaxMemory;
   uint32_t ZStackSize;
   unsigned LTOPartitions;
   unsigned LTOO;
   unsigned Optimize;
   unsigned ThinLTOJobs;

wasm/Driver.cpp

static void setConfigs(opt::InputArgList &Args) {
   Config->PrintGcSections =
       Args.hasFlag(OPT_print_gc_sections, OPT_no_print_gc_sections, false);
   Config->SaveTemps = Args.hasArg(OPT_save_temps);
   Config->SearchPaths = args::getStrings(Args, OPT_L);
   Config->Shared = Args.hasArg(OPT_shared);
   Config->StripAll = Args.hasArg(OPT_strip_all);
   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->ThinLTOJobs = args::getInteger(Args, OPT_thinlto_jobs, -1u);
   errorHandler().Verbose = Args.hasArg(OPT_verbose);
   ThreadsEnabled = Args.hasFlag(OPT_threads, OPT_no_threads, true);
 
if (Config->Pic) {
     Config->ImportTable = true;
   }
 
   if (Config->Shared) {
     Config->ExportDynamic = true;
     Config->AllowUndefined = true;
   }
 
+  // Handle --trace-symbol.
+  for (auto *Arg : Args.filtered(OPT_trace_symbol))
+    Symtab->trace(Arg->getValue());
+
   if (!Config->Relocatable)
     createSyntheticSymbols();
 
   createFiles(Args);
   if (errorCount())
     return;
 
   // Add all files to the symbol table. This will add almost all

wasm/Options.td

 def shared: F<"shared">, HelpText<"Build a shared object">;
 
 def strip_all: F<"strip-all">, HelpText<"Strip all symbols">;
 
 def strip_debug: F<"strip-debug">, HelpText<"Strip debugging information">;
 
 def threads: F<"threads">, HelpText<"Run the linker multi-threaded">;
 
+def trace: F<"trace">, HelpText<"Print the names of the input files">;
+
+defm trace_symbol: Eq<"trace-symbol", "Trace references to symbols">;
+
 defm undefined: Eq<"undefined", "Force undefined symbol during linking">;
 
 def v: Flag<["-"], "v">, HelpText<"Display the version number">;
 
 def verbose: F<"verbose">, HelpText<"Verbose mode">;
 
 def version: F<"version">, HelpText<"Display the version number and exit">;
 

 def: JoinedOrSeparate<["-"], "e">, Alias<entry>;
 def: J<"entry=">, Alias<entry>;
 def: Flag<["-"], "E">, Alias<export_dynamic>, HelpText<"Alias for --export-dynamic">;
 def: Flag<["-"], "i">, Alias<initial_memory>;
 def: Flag<["-"], "m">, Alias<max_memory>;
 def: Flag<["-"], "r">, Alias<relocatable>;
 def: Flag<["-"], "s">, Alias<strip_all>, HelpText<"Alias for --strip-all">;
 def: Flag<["-"], "S">, Alias<strip_debug>, HelpText<"Alias for --strip-debug">;
+def: Flag<["-"], "t">, Alias<trace>, HelpText<"Alias for --trace">;
+def: JoinedOrSeparate<["-"], "y">, Alias<trace_symbol>, HelpText<"Alias for --trace-symbol">;
 def: JoinedOrSeparate<["-"], "u">, Alias<undefined>;
 
 // LTO-related options.
 def lto_O: J<"lto-O">, MetaVarName<"<opt-level>">,
   HelpText<"Optimization level for LTO">;
 def lto_partitions: J<"lto-partitions=">,
   HelpText<"Number of LTO codegen partitions">;
 def disable_verify: F<"disable-verify">;
 def save_temps: F<"save-temps">;
 def thinlto_cache_dir: J<"thinlto-cache-dir=">,
   HelpText<"Path to ThinLTO cached object file directory">;
 defm thinlto_cache_policy: Eq<"thinlto-cache-policy", "Pruning policy for the ThinLTO cache">;
 def thinlto_jobs: J<"thinlto-jobs=">, HelpText<"Number of ThinLTO jobs">;

wasm/SymbolTable.h

public:
   std::vector<ObjFile *> ObjectFiles;
   std::vector<BitcodeFile *> BitcodeFiles;
   std::vector<InputFunction *> SyntheticFunctions;
   std::vector<InputGlobal *> SyntheticGlobals;
 
   void reportRemainingUndefines();
 
   ArrayRef<Symbol *> getSymbols() const { return SymVector; }
+
   Symbol *find(StringRef Name);
 
+  void trace(StringRef Name);
+
   Symbol *addDefinedFunction(StringRef Name, uint32_t Flags, InputFile *File,
                              InputFunction *Function);
   Symbol *addDefinedData(StringRef Name, uint32_t Flags, InputFile *File,
                          InputSegment *Segment, uint32_t Address,
                          uint32_t Size);
   Symbol *addDefinedGlobal(StringRef Name, uint32_t Flags, InputFile *File,
                            InputGlobal *G);
   Symbol *addDefinedEvent(StringRef Name, uint32_t Flags, InputFile *File,
public:
   DefinedGlobal *addSyntheticGlobal(StringRef Name, uint32_t Flags,
                                     InputGlobal *Global);
   DefinedFunction *addSyntheticFunction(StringRef Name, uint32_t Flags,
                                         InputFunction *Function);
 
 private:
   std::pair<Symbol *, bool> insert(StringRef Name, InputFile *File);
 
   llvm::DenseMap<llvm::CachedHashStringRef, Symbol *> SymMap;
   std::vector<Symbol *> SymVector;
 
   llvm::DenseSet<llvm::CachedHashStringRef> Comdats;
 
+  StringRef TraceSymbol;
+
+  llvm::StringSet<> TraceSymbols;
+
   // For LTO.
   std::unique_ptr<BitcodeCompiler> LTO;
 };
 
 extern SymbolTable *Symtab;
 
 } // namespace wasm
 } // namespace lld
 
 #endif

wasm/SymbolTable.cpp

 using namespace llvm::object;
 using namespace lld;
 using namespace lld::wasm;
 
 SymbolTable *lld::wasm::Symtab;
 
 void SymbolTable::addFile(InputFile *File) {
   log("Processing: " + toString(File));
+  if (Config->Trace)
+    message(toString(File));
   File->parse();
 
   // LLVM bitcode file
   if (auto *F = dyn_cast<BitcodeFile>(File))
     BitcodeFiles.push_back(F);
   else if (auto *F = dyn_cast<ObjFile>(File))
     ObjectFiles.push_back(F);
 }

 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name, InputFile *File) {
   bool Inserted = false;
   Symbol *&Sym = SymMap[CachedHashStringRef(Name)];
   if (!Sym) {
     Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
     Sym->IsUsedInRegularObj = false;
     SymVector.emplace_back(Sym);
     Inserted = true;
+    if (TraceSymbols.count(Name) != 0)
+      Sym->Traced = true;
   }
   if (!File || File->kind() == InputFile::ObjectKind)
     Sym->IsUsedInRegularObj = true;
   return {Sym, Inserted};
 }
 
 static void reportTypeError(const Symbol *Existing, const InputFile *File,
                             llvm::wasm::WasmSymbolType Type) {
   error("symbol type mismatch: " + toString(*Existing) + "\n>>> defined as " +
         toString(Existing->getWasmType()) + " in " +
         toString(Existing->getFile()) + "\n>>> defined as " + toString(Type) +
         " in " + toString(File));
 }
void SymbolTable::addLazy(ArchiveFile *File, const Archive::Symbol *Sym) {
 
   LLVM_DEBUG(dbgs() << "replacing existing undefined\n");
   File->addMember(Sym);
 }
 
 bool SymbolTable::addComdat(StringRef Name) {
   return Comdats.insert(CachedHashStringRef(Name)).second;
 }
+
+// Set a flag for --trace-symbol so that we can print out a log message
+// if a new symbol with the same name is inserted into the symbol table.
+void SymbolTable::trace(StringRef Name) {
+  TraceSymbols.insert(Name);
+}

wasm/Symbols.h

public:
 
   WasmSymbolType getWasmType() const;
   bool isExported() const;
 
   // True if this symbol was referenced by a regular (non-bitcode) object.
   unsigned IsUsedInRegularObj : 1;
   unsigned ForceExport : 1;
 
+  // True if this symbol is specified by --trace-symbol option.
+  unsigned Traced : 1;
+
 protected:
   Symbol(StringRef Name, Kind K, uint32_t Flags, InputFile *F)
-      : IsUsedInRegularObj(false), ForceExport(false), Name(Name),
-        SymbolKind(K), Flags(Flags), File(F), Referenced(!Config->GcSections) {}
+      : IsUsedInRegularObj(false), ForceExport(false), Traced(false),
+        Name(Name), SymbolKind(K), Flags(Flags), File(F),
+        Referenced(!Config->GcSections) {}
 
   StringRef Name;
   Kind SymbolKind;
   uint32_t Flags;
   InputFile *File;
   uint32_t OutputSymbolIndex = INVALID_INDEX;
   bool Referenced;
 };
union SymbolUnion {
   alignas(DefinedEvent) char D[sizeof(DefinedEvent)];
   alignas(LazySymbol) char E[sizeof(LazySymbol)];
   alignas(UndefinedFunction) char F[sizeof(UndefinedFunction)];
   alignas(UndefinedData) char G[sizeof(UndefinedData)];
   alignas(UndefinedGlobal) char H[sizeof(UndefinedGlobal)];
   alignas(SectionSymbol) char I[sizeof(SectionSymbol)];
 };
 
+void printTraceSymbol(Symbol *Sym);
+
 template <typename T, typename... ArgT>
 T *replaceSymbol(Symbol *S, ArgT &&... Arg) {
   static_assert(std::is_trivially_destructible<T>(),
                 "Symbol types must be trivially destructible");
   static_assert(sizeof(T) <= sizeof(SymbolUnion), "SymbolUnion too small");
   static_assert(alignof(T) <= alignof(SymbolUnion),
                 "SymbolUnion not aligned enough");
   assert(static_cast<Symbol *>(static_cast<T *>(nullptr)) == nullptr &&
          "Not a Symbol");
 
   Symbol SymCopy = *S;
 
   T *S2 = new (S) T(std::forward<ArgT>(Arg)...);
   S2->IsUsedInRegularObj = SymCopy.IsUsedInRegularObj;
   S2->ForceExport = SymCopy.ForceExport;
+  S2->Traced = SymCopy.Traced;
+
+  // Print out a log message if --trace-symbol was specified.
+  // This is for debugging.
+  if (S2->Traced)
+    printTraceSymbol(S2);
+
   return S2;
 }
 
 } // namespace wasm
 
 // Returns a symbol name for an error message.
 std::string toString(const wasm::Symbol &Sym);
 std::string toString(wasm::Symbol::Kind Kind);
 std::string maybeDemangleSymbol(StringRef Name);
 
 } // namespace lld
 
 #endif

wasm/Symbols.cpp

case wasm::Symbol::UndefinedGlobalKind:
     return "UndefinedGlobal";
   case wasm::Symbol::LazyKind:
     return "LazyKind";
   case wasm::Symbol::SectionKind:
     return "SectionKind";
   }
   llvm_unreachable("invalid symbol kind");
 }
+
+// Print out a log message for --trace-symbol.
+void lld::wasm::printTraceSymbol(Symbol *Sym) {
+  std::string S;
+  if (Sym->isUndefined())
+    S = ": reference to ";
+  else if (Sym->isLazy())
+    S = ": lazy definition of ";
+  else
+    S = ": definition of ";
+
+  message(toString(Sym->getFile()) + S + Sym->getName());
+}