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

[sbc100]

• update test

[sbc100]

• remove debugging

[ruiu]

wasm/SymbolTable.cpp

439

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

[sbc100]

wasm/SymbolTable.cpp

439

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

85–86

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 ↗

(On Diff #185424)

unrelated change?

wasm/SymbolTable.cpp

91

Use true instead of 1.

wasm/SymbolTable.h

84–88

Thank you for adding this comment.

92–95

Dead members.

[sbc100]

• feedback

[ruiu]

LGTM

test/wasm/trace-symbol.ll

+; RUN: llc -filetype=obj %p/Inputs/ret32.ll -o %t.ret32.o
+; RUN: llc -filetype=obj -o %t.o %s
+; RUN: wasm-ld -o %t.wasm %t.o %t.ret32.o -y ret32 -y _start 2>&1 | FileCheck %s -check-prefix=BOTH
+
+; check alias
+; RUN: wasm-ld -o %t.wasm %t.o %t.ret32.o -trace-symbol=_start 2>&1 | FileCheck %s -check-prefixes=JUST-START
+
+target triple = "wasm32-unknown-unknown"
+
+declare i32 @ret32(float %arg)
+
+define void @_start() {
+entry:
+  %call1 = call i32 @ret32(float 0.0)
+  ret void
+}
+
+; BOTH: .o: definition of _start
+; BOTH: .o: reference to ret32
+; BOTH: .ret32.o: definition of ret32
+
+; JUST-START: .o: definition of _start
+; JUST-START-NOT: 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:
   DefinedData *addSyntheticDataSymbol(StringRef Name, uint32_t Flags);
   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);
+  std::pair<Symbol *, bool> insertName(StringRef Name);
 
-  llvm::DenseMap<llvm::CachedHashStringRef, Symbol *> SymMap;
+  // Maps symbol names to index into the SymVector.  -1 means that symbols
+  // is to not yet in the vector but it should have tracing enabled if it is
+  // ever added.
+  llvm::DenseMap<llvm::CachedHashStringRef, int> SymMap;
   std::vector<Symbol *> SymVector;
 
   llvm::DenseSet<llvm::CachedHashStringRef> Comdats;
 
   // 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);
 }
if (Config->AllowUndefinedSymbols.count(Sym->getName()) != 0)
       continue;
     if (!Sym->IsUsedInRegularObj)
       continue;
     error(toString(Sym->getFile()) + ": undefined symbol: " + toString(*Sym));
   }
 }
 
 Symbol *SymbolTable::find(StringRef Name) {
-  return SymMap.lookup(CachedHashStringRef(Name));
+  auto It = SymMap.find(CachedHashStringRef(Name));
+  if (It == SymMap.end() || It->second == -1)
+    return nullptr;
+  return SymVector[It->second];
+}
+
+std::pair<Symbol *, bool> SymbolTable::insertName(StringRef Name) {
+  bool Trace = false;
+  auto P = SymMap.insert({CachedHashStringRef(Name), (int)SymVector.size()});
+  int &SymIndex = P.first->second;
+  bool IsNew = P.second;
+  if (SymIndex == -1) {
+    SymIndex = SymVector.size();
+    Trace = true;
+    IsNew = true;
   }
 
-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 (!IsNew)
+    return {SymVector[SymIndex], false};
+
+  Symbol *Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
+  Sym->Traced = Trace;
+  return {Sym, true};
+
+std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name, InputFile *File) {
+  Symbol *S;
+  bool WasInserted;
+  std::tie(S, WasInserted) = insertName(Name);
+
   if (!File || File->kind() == InputFile::ObjectKind)
-    Sym->IsUsedInRegularObj = true;
-  return {Sym, Inserted};
+    S->IsUsedInRegularObj = true;
+
+  return {S, WasInserted};
 }
 
 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) {
+  SymMap.insert({CachedHashStringRef(Name), -1});
+}

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());
+}