[WebAssembly] Add support for --gc-sections

[sbc100]

Summary

In this initial version we only GC symbols with hidden visibility since
other symbols we export to the embedder.

We could potentially modify this the future and only use symbols
explicitly passed via --export as GC roots.

This version of the code only does GC of data and code. GC for the
types sections is coming next.

[sbc100]

• revert + rebase

[sbc100]

One decision I'm not sure about is whether to default to --gc-section in the linker or have the clang driver pass it by default. @dschuff, what do you think about this? I think for -fdata-section and -ffunction-sections we redundantly set them on by default and also have the driver pass them too. I'd rather do just one or the other.

[sbc100]

• clang-format

[sbc100]

• revert

[ncw]

Overall great, just some comments/questions for potential polishing.

One big thing missing - should imports be GC'ed? I would have thought so. We shouldn't import unused symbols, if the import is only used in a function that's discarded/non-live.

wasm/Driver.cpp

225–226

Is it better LLVM style to make this a template on the Fn type, to avoid forcing the lambda to be wrapped in a std::function? (I think std::function creates some extra virtual wrapper objects.)

253–254

This patch doesn't seem to add any warnings? I don't see any harm to this - but if it's set, do we now need to remember to add if (errorCount()) return after any places where we emit warnings? I can't think of any I've noticed many/any warnings Wasm-LLD though.

302

Enqueue and MarkSymbol are pretty similar, do we need two nearly-identical helpers? is it marginally clearer to pass MarkSymbol into forEachSuccessor, or to get rid of MarkSymbol and simply call Enqueue directly on the Symbol's chunk in the two places where it's used? Could call "Enqueue" instead "MarkChunk".

The logic looks good, it's satisfyingly short and correct. Nice :)

323–327

I see above that you've made it so that -r can't be used with GC.

But, for avoidable of future bugs, it might wise to do an InputChunks.push_back(CtorFunction) where we create, and ditto in future for any other "synthetic" input chunks. Otherwise, it's too tempting to assume that InputChunks contains all the input. Or put another way, now that you have InputChunks as a global variable we may as well make it more generally useful by putting the CtorFunction in it as well, even though GC isn't currently used with the CtorFunction.

wasm/InputChunks.h

61 ↗

(On Diff #131727)

This should probably be a const ObjFile *const pointer if it's now public.

wasm/Writer.cpp

649–650 ↗

(On Diff #131727)

You've said that the intention is that exported symbols should not be GC'ed.

(Aside: I think that's good, that's exactly what we want - the public interface of the Wasm module can't be GC'ed, and it's the job of the programmer to use fvisibility=hidden or attributes to declare their "public" symbols to the linker.)

So if exported symbols are not GC'ed, how can it be that Live is false here? It would be clearer to assert(Sym->getChunk()->Live) just underneath the isHidden check (a few lines down).

[sbc100]

• revert part
• cleanup

[sbc100]

• - remove MarkSymbol

[sbc100]

wasm/Driver.cpp

225–226

I basically copied this directly from the ELF linker, but I'm open to changing it.

@ruiu what do you think about this?

I was thinking we might as well make this a local lamba within markLive() that always calls Enqueue? Right now is needlessly generic. Then we could just call it EnqueueSuccessors()

253–254

Sorry this should be a separate change..

323–327

Actually I think I might just remove InputChunks, this change doesn't justify its existence. I was copying it from the ELF linker which makes more use of it.

wasm/InputChunks.h

61 ↗

(On Diff #131727)

lld doesn't seem to be reaching for that level of const correctness so far (at least I dont' see any * const pointers yet

[sbc100]

• only export live symbols

[sbc100]

• revert

[sbc100]

revert even more!

[sbc100]

• update comment

[sbc100]

• add check for error message

[ncw]

wasm/Driver.cpp

286

Uh, shouldn't this be "continue"? Otherwise it'll give up processing symbols when it reaches the first type relocation.

[sbc100]

• feedback

[dschuff]

I think LLD should probably default to no gc, and in general to minimal/most simple options, and the smarts should be in the driver. I think this matches other targets, and I think it also matches (or at least, should match) the way we have options the frontend/backend vs the driver; i.e. IIRC the driver has logic to pass -ffunction-sections and other codegen options to the frontend. So basically all the special logic goes in one place.

[sbc100]

In D42511#991954, @dschuff wrote:

I think LLD should probably default to no gc, and in general to minimal/most simple options, and the smarts should be in the driver. I think this matches other targets, and I think it also matches (or at least, should match) the way we have options the frontend/backend vs the driver; i.e. IIRC the driver has logic to pass -ffunction-sections and other codegen options to the frontend. So basically all the special logic goes in one place.

Ha, Thats funny, Dan and I came to the exact opposite conclusion. We decided it was best to put the sensible defaults in the tools in order to (a) keep the command lines shorter (b) keep the driver simpler (c) give direct users of the tools, not via the driver, more sensible defaults.

[ruiu]

In D42511#991998, @sbc100 wrote:

In D42511#991954, @dschuff wrote:

I think LLD should probably default to no gc, and in general to minimal/most simple options, and the smarts should be in the driver. I think this matches other targets, and I think it also matches (or at least, should match) the way we have options the frontend/backend vs the driver; i.e. IIRC the driver has logic to pass -ffunction-sections and other codegen options to the frontend. So basically all the special logic goes in one place.

Ha, Thats funny, Dan and I came to the exact opposite conclusion. We decided it was best to put the sensible defaults in the tools in order to (a) keep the command lines shorter (b) keep the driver simpler (c) give direct users of the tools, not via the driver, more sensible defaults.

I think I agree with Sam. As long as options are consistent among toolchain (i.e. --f{function,data}-sections and -gc-sections are both on by default), turning on the gc by default makes sense to me. That option makes sense to wasm because the output size matters a lot for that target.

[ruiu]

Generally looking pretty good to me. A few minor comments.

wasm/Driver.cpp

225

I would move this function to a new file MarkLive.cpp for consistency with other targets.

277

I'd call Enqueue directly here and below to eliminate a local variable Sym.

[alexcrichton]

FWIW I've just recently started testing LLD support w/ Rust code again and LLD master is working beautifully! The output of lld was a little large given the set of exported items, but @sunfish pointed me at this diff which worked perfectly for us as well! This managed to strip notably all the unused entries in the global table for call_indirect entries.

One part I noticed though that this wasn't gc'ing was the type sections and declarations. The "hello world" output from my branch right now looks like https://gist.github.com/alexcrichton/c313672808533ff2f1d29538f390457a, which looks ideal from a "everything is gc'd point of view" except for the unused type declarations. Just wanted to let y'all know, but otherwise thanks so much for this!

[sbc100]

In D42511#992208, @alexcrichton wrote:

FWIW I've just recently started testing LLD support w/ Rust code again and LLD master is working beautifully! The output of lld was a little large given the set of exported items, but @sunfish pointed me at this diff which worked perfectly for us as well! This managed to strip notably all the unused entries in the global table for call_indirect entries.

One part I noticed though that this wasn't gc'ing was the type sections and declarations. The "hello world" output from my branch right now looks like https://gist.github.com/alexcrichton/c313672808533ff2f1d29538f390457a, which looks ideal from a "everything is gc'd point of view" except for the unused type declarations. Just wanted to let y'all know, but otherwise thanks so much for this!

Great news. And thanks for pointing out that I forgot to GC the type section. I'll fix that now.

[ncw]

As well as Types, I mentioned GC for Imports above as well. It would be very useful to be able to reduce the number of dependencies/imports of the module based on dead code - it's not just a size improvement.

For types, it's annoying, yes, I hadn't thought about it at all, but they do need to pruned via GC don't they. It's tempting to think that type relocations can only appear as the operand of instructions like call_indirect, and those must be pointing to either a defined or imported function - but it's not true, you could write code that does a call_indirect to the null function index using a type that otherwise wouldn't exist in the module at all. (Do we have a test for that?) So we really do have to look at the relocations before pruning the types.

[ruiu]

For types, it's annoying, yes, I hadn't thought about it at all, but they do need to pruned via GC don't they. It's tempting to think that type relocations can only appear as the operand of instructions like call_indirect, and those must be pointing to either a defined or imported function - but it's not true, you could write code that does a call_indirect to the null function index using a type that otherwise wouldn't exist in the module at all. (Do we have a test for that?) So we really do have to look at the relocations before pruning the types.

I'm not sure if I understand the last sentence correctly. If you need to scan relocations to garbage-collect types, that's what we do to other things like chunks in this file, so it's not special, is it?

[ncw]

In D42511#992690, @ruiu wrote:

I'm not sure if I understand the last sentence correctly. If you need to scan relocations to garbage-collect types, that's what we do to other things like chunks in this file, so it's not special, is it?

You're right it's not very special, it's just surprising (to me). My initial expectation was "surely the only types that can be referenced are ones that actually exist in the Wasm file", so it should be easy to construct the types list just by examining function imports+definitions, without needing the type-pruning code to care about relocations. It seems sneaky and surprising to me that you can't just do that. It definitely needs a test for the "sneaky" case of calling a null pointer with a type that's nowhere else used.

Plus, types aren't an input chunk so it's not going to fit into this logic directly. In fact the implementation doesn't need to be put here at all, and will presumably actually live somewhere in Writer, well away from anything to do with GC here.

[ruiu]

You're right it's not very special, it's just surprising (to me). My initial expectation was "surely the only types that can be referenced are ones that actually exist in the Wasm file", so it should be easy to construct the types list just by examining function imports+definitions, without needing the type-pruning code to care about relocations. It seems sneaky and surprising to me that you can't just do that. It definitely needs a test for the "sneaky" case of calling a null pointer with a type that's nowhere else used.

Plus, types aren't an input chunk so it's not going to fit into this logic directly. In fact the implementation doesn't need to be put here at all, and will presumably actually live somewhere in Writer, well away from anything to do with GC here.

I may be missing something, but if you need to mark types alive to garbage-collect them, I'd do that in this file instead of doing that in other files, because scanning all relocations isn't very cheap. It's better to do that only once.

[sbc100]

• split into seperate file
• clang-format
• feedback

[sbc100]

I've got a prototype of GC for the types, but I'd rather land that later since it is separable and an incremental improvement on this. Also, type GC should be very marginal compared to code and data GC. I'll make a note in the description that this is coming soon.

[ruiu]

LGTM with these changes.

wasm/Driver.cpp

283–290

I'd avoid writing a large nested if's if possible. Could you write two if's like this?

if (Config->Relocatable) {
   // error check
}

Symbol *EntrySym = nullptr;
if (!Config->Relocatalbe) {
  ....
}

wasm/MarkLive.cpp

94–98 ↗

(On Diff #132084)

I'd make this a file-scope function now. But on second thought, I'd just repeat it twice. It's not very beautiful but that's probably simpler than defining a function.

[sbc100]

• feedback

wasm/MarkLive.cpp

94–98 ↗

(On Diff #132084)

I'd rather not repeat that ugly multi-line error string.

( I imagine we will unify this into a single list of input chunks at some point (like ELF does) so this should go away then anyway).

[ruiu]

LGTM

wasm/MarkLive.cpp

94–98 ↗

(On Diff #132084)

Sure. It'd be nice if we can unify the two lists.

[sbc100]

In D42511#992208, @alexcrichton wrote:

FWIW I've just recently started testing LLD support w/ Rust code again and LLD master is working beautifully! The output of lld was a little large given the set of exported items, but @sunfish pointed me at this diff which worked perfectly for us as well! This managed to strip notably all the unused entries in the global table for call_indirect entries.

One part I noticed though that this wasn't gc'ing was the type sections and declarations. The "hello world" output from my branch right now looks like https://gist.github.com/alexcrichton/c313672808533ff2f1d29538f390457a, which looks ideal from a "everything is gc'd point of view" except for the unused type declarations. Just wanted to let y'all know, but otherwise thanks so much for this!

Alex, GC of types is now landed too: https://reviews.llvm.org/D42747

[alexcrichton]

Wow that was fast, thanks so much! We'll be updating to this as soon as we can!

wasm/Config.h

 
 namespace lld {
 namespace wasm {
 
 struct Configuration {
   bool AllowUndefined;
   bool CheckSignatures;
   bool Demangle;
+  bool GcSections;
   bool ImportMemory;
+  bool PrintGcSections;
   bool Relocatable;
   bool StripAll;
   bool StripDebug;
   uint32_t GlobalBase;
   uint32_t InitialMemory;
   uint32_t MaxMemory;
   uint32_t ZStackSize;
   llvm::StringRef Entry;

wasm/Driver.cpp

static StringRef getEntry(opt::InputArgList &Args, StringRef Default) {
   auto *Arg = Args.getLastArg(OPT_entry, OPT_no_entry);
   if (!Arg)
     return Default;
   if (Arg->getOption().getID() == OPT_no_entry)
     return "";
   return Arg->getValue();
 }
 
 void LinkerDriver::link(ArrayRef<const char *> ArgsArr) {
   WasmOptTable Parser;
   opt::InputArgList Args = Parser.parse(ArgsArr.slice(1));
 
   // Handle --help
   if (Args.hasArg(OPT_help)) {
     printHelp(ArgsArr[0]);
     return;
   }
 
if (Args.hasArg(OPT_version) || Args.hasArg(OPT_v)) {
     outs() << getLLDVersion() << "\n";
     return;
   }
 
   Config->AllowUndefined = Args.hasArg(OPT_allow_undefined);
   Config->CheckSignatures =
       Args.hasFlag(OPT_check_signatures, OPT_no_check_signatures, false);
   Config->Entry = getEntry(Args, Args.hasArg(OPT_relocatable) ? "" : "_start");
+  errorHandler().FatalWarnings =
+      Args.hasFlag(OPT_fatal_warnings, OPT_no_fatal_warnings, false);
+  Config->GcSections = Args.hasFlag(OPT_gc_sections, OPT_no_gc_sections, false);
   Config->ImportMemory = Args.hasArg(OPT_import_memory);
   Config->OutputFile = Args.getLastArgValue(OPT_o);
   Config->Relocatable = Args.hasArg(OPT_relocatable);
+  Config->PrintGcSections =
+      Args.hasFlag(OPT_print_gc_sections, OPT_no_print_gc_sections, false);
   Config->SearchPaths = args::getStrings(Args, OPT_L);
   Config->StripAll = Args.hasArg(OPT_strip_all);
   Config->StripDebug = Args.hasArg(OPT_strip_debug);
   errorHandler().Verbose = Args.hasArg(OPT_verbose);
   ThreadsEnabled = Args.hasFlag(OPT_threads, OPT_no_threads, true);
 
   Config->InitialMemory = args::getInteger(Args, OPT_initial_memory, 0);
   Config->GlobalBase = args::getInteger(Args, OPT_global_base, 1024);
   Config->MaxMemory = args::getInteger(Args, OPT_max_memory, 0);
   Config->ZStackSize =
       args::getZOptionValue(Args, OPT_z, "stack-size", WasmPageSize);
 
   if (auto *Arg = Args.getLastArg(OPT_allow_undefined_file))
     readImportFile(Arg->getValue());
 
   if (Config->OutputFile.empty())
     error("no output file specified");
 
   if (!Args.hasArg(OPT_INPUT))
     error("no input files");
 
-  if (Config->Relocatable && !Config->Entry.empty())
-    error("entry point specified for relocatable output file");
-  if (Config->Relocatable && Args.hasArg(OPT_undefined))
-    error("undefined symbols specified for relocatable output file");
-
   Symbol *EntrySym = nullptr;
-  if (!Config->Relocatable) {
+  if (Config->Relocatable) {
+    if (!Config->Entry.empty())
+      error("entry point specified for relocatable output file");
+    if (Config->GcSections)
+      error("-r and --gc-sections may not be used together");
+    if (Args.hasArg(OPT_undefined))
+      error("-r -and --undefined may not be used together");
+  } else {
     static WasmSignature Signature = {{}, WASM_TYPE_NORESULT};
     if (!Config->Entry.empty())
       EntrySym = Symtab->addUndefinedFunction(Config->Entry, &Signature);
 
     // Handle the `--undefined <sym>` options.
     for (auto* Arg : Args.filtered(OPT_undefined))
       Symtab->addUndefinedFunction(Arg->getValue(), nullptr);
 
     // Create linker-synthetic symbols
     // __wasm_call_ctors:
     //    Function that directly calls all ctors in priority order.
     // __stack_pointer:
     //    Wasm global that holds the address of the top of the explict
     //    value stack in linear memory.
     // __dso_handle;
     //    Global in calls to __cxa_atexit to determine current DLL
     Config->CtorSymbol = Symtab->addDefinedFunction(
         "__wasm_call_ctors", &Signature, WASM_SYMBOL_VISIBILITY_HIDDEN);
     Config->StackPointerSymbol = Symtab->addDefinedGlobal("__stack_pointer");
     Config->HeapBaseSymbol = Symtab->addDefinedGlobal("__heap_base");
     Symtab->addDefinedGlobal("__dso_handle")->setVirtualAddress(0);
   }
 
   createFiles(Args);
   if (errorCount())
     return;
 
   // Add all files to the symbol table. This will add almost all
   // symbols that we need to the symbol table.
   for (InputFile *F : Files)
     Symtab->addFile(F);
 
   // Make sure we have resolved all symbols.
   if (!Config->Relocatable && !Config->AllowUndefined) {
     Symtab->reportRemainingUndefines();
   } else {
     // When we allow undefined symbols we cannot include those defined in
     // -u/--undefined since these undefined symbols have only names and no
     // function signature, which means they cannot be written to the final
     // output.
     for (auto* Arg : Args.filtered(OPT_undefined)) {
       Symbol *Sym = Symtab->find(Arg->getValue());
       if (!Sym->isDefined())
         error("function forced with --undefined not found: " + Sym->getName());
     }

wasm/Options.td

 include "llvm/Option/OptParser.td"
 
 // For options whose names are multiple letters, either one dash or
 // two can precede the option name except those that start with 'o'.
 class F<string name>: Flag<["--", "-"], name>;
 class J<string name>: Joined<["--", "-"], name>;
 class S<string name>: Separate<["--", "-"], name>;
 
 multiclass Eq<string name> {
   def "": Separate<["--", "-"], name>;
   def _eq: Joined<["--", "-"], name # "=">, Alias<!cast<Separate>(NAME)>;
 }
 
+// The follow flags are shared with the ELF linker
 def L: JoinedOrSeparate<["-"], "L">, MetaVarName<"<dir>">,
   HelpText<"Add a directory to the library search path">;
 
 def color_diagnostics: F<"color-diagnostics">,
   HelpText<"Use colors in diagnostics">;
 
 def color_diagnostics_eq: J<"color-diagnostics=">,
   HelpText<"Use colors in diagnostics">;
 
-// The follow flags are shared with the ELF linker
+def entry: S<"entry">, MetaVarName<"<entry>">,
+  HelpText<"Name of entry point symbol">;
+
+def error_limit: J<"error-limit=">,
+  HelpText<"Maximum number of errors to emit before stopping (0 = no limit)">;
+
+def fatal_warnings: F<"fatal-warnings">,
+  HelpText<"Treat warnings as errors">;
+
+def gc_sections: F<"gc-sections">,
+  HelpText<"Enable garbage collection of unused sections">;
+
 def help: F<"help">, HelpText<"Print option help">;
 
 def l: JoinedOrSeparate<["-"], "l">, MetaVarName<"<libName>">,
   HelpText<"Root name of library to use">;
 
 def mllvm: S<"mllvm">, HelpText<"Options to pass to LLVM">;
 
 def no_threads: F<"no-threads">,
   HelpText<"Do not run the linker multi-threaded">;
 
 def no_color_diagnostics: F<"no-color-diagnostics">,
   HelpText<"Do not use colors in diagnostics">;
 
-def no_check_signatures: F<"no-check-signatures">, HelpText<"Don't check function signatures">;
+def no_fatal_warnings: F<"no-fatal-warnings">;
 
-def o: JoinedOrSeparate<["-"], "o">, MetaVarName<"<path>">,
-  HelpText<"Path to file to write output">;
-
-def threads: F<"threads">, HelpText<"Run the linker multi-threaded">;
+def no_gc_sections: F<"no-gc-sections">,
+  HelpText<"Disable garbage collection of unused sections">;
 
-def check_signatures: F<"check-signatures">, HelpText<"Check function signatures">;
-
-def v: Flag<["-"], "v">, HelpText<"Display the version number">;
+def no_print_gc_sections: F<"no-print-gc-sections">,
+  HelpText<"Do not list removed unused sections">;
 
-def version: F<"version">, HelpText<"Display the version number and exit">;
+def o: JoinedOrSeparate<["-"], "o">, MetaVarName<"<path>">,
+  HelpText<"Path to file to write output">;
 
-def verbose: F<"verbose">, HelpText<"Verbose mode">;
+def print_gc_sections: F<"print-gc-sections">,
+  HelpText<"List removed unused sections">;
 
 def relocatable: F<"relocatable">, HelpText<"Create relocatable object file">;
 
 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 v: Flag<["-"], "v">, HelpText<"Display the version number">;
+
 defm undefined: Eq<"undefined">,
   HelpText<"Force undefined symbol during linking">;
 
-def z: JoinedOrSeparate<["-"], "z">, MetaVarName<"<option>">,
-  HelpText<"Linker option extensions">;
-
-def entry: S<"entry">, MetaVarName<"<entry>">,
-  HelpText<"Name of entry point symbol">;
+def version: F<"version">, HelpText<"Display the version number and exit">;
 
-def no_entry: F<"no-entry">,
-  HelpText<"Do not output any entry point">;
+def verbose: F<"verbose">, HelpText<"Verbose mode">;
 
-def error_limit: J<"error-limit=">,
-  HelpText<"Maximum number of errors to emit before stopping (0 = no limit)">;
+def z: JoinedOrSeparate<["-"], "z">, MetaVarName<"<option>">,
+  HelpText<"Linker option extensions">;
 
 // The follow flags are unique to wasm
+def check_signatures: F<"check-signatures">,
+  HelpText<"Check function signatures">;
 
 defm export: Eq<"export">,
   HelpText<"Force a symbol to be exported">;
 
 def global_base: J<"global-base=">,
   HelpText<"Where to start to place global data">;
 
 def initial_memory: J<"initial-memory=">,
   HelpText<"Initial size of the linear memory">;
 
+def no_check_signatures: F<"no-check-signatures">,
+  HelpText<"Don't check function signatures">;
+
+def no_entry: F<"no-entry">,
+  HelpText<"Do not output any entry point">;
+
 def max_memory: J<"max-memory=">,
   HelpText<"Maximum size of the linear memory">;
 
 def import_memory: F<"import-memory">,
   HelpText<"Import memory from the environment">;
 
 def allow_undefined: F<"allow-undefined">,
   HelpText<"Allow undefined symbols in linked binary">;