[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

228–229

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.)

305

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 :)

343–344

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.

412–416

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

62

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

wasm/Writer.cpp

649–650

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

228–229

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()

343–344

Sorry this should be a separate change..

412–416

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

62

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

289

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

228

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

280

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

372–379

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!

test/wasm/call-indirect.ll

 ; RUN: llc -filetype=obj %p/Inputs/call-indirect.ll -o %t2.o
 ; RUN: llc -filetype=obj %s -o %t.o
-; RUN: lld -flavor wasm -o %t.wasm %t2.o %t.o
+; RUN: lld -flavor wasm -no-gc-sections -o %t.wasm %t2.o %t.o
 ; RUN: obj2yaml %t.wasm | FileCheck %s
 
 ; bitcode generated from the following C code:
 ; int foo(void) { return 1; }
 ; int (*indirect_func)(void) = &foo;
 ; void _start(void) { indirect_func(); }
 
 target triple = "wasm32-unknown-unknown-wasm"

test/wasm/comdats.ll

 ; RUN: llc -filetype=obj -mtriple=wasm32-unknown-uknown-wasm %p/Inputs/comdat1.ll -o %t1.o
 ; RUN: llc -filetype=obj -mtriple=wasm32-unknown-uknown-wasm %p/Inputs/comdat2.ll -o %t2.o
 ; RUN: llc -filetype=obj -mtriple=wasm32-unknown-uknown-wasm %s -o %t.o
-; RUN: lld -flavor wasm -o %t.wasm %t.o %t1.o %t2.o
+; RUN: lld -flavor wasm -no-gc-sections -o %t.wasm %t.o %t1.o %t2.o
 ; RUN: obj2yaml %t.wasm | FileCheck %s
 
 target triple = "wasm32-unknown-unknown-wasm"
 
 declare i32 @inlineFn()
 
 define void @_start() local_unnamed_addr {
 entry:

test/wasm/data-layout.ll

 ; RUN: llc -filetype=obj %p/Inputs/hello.ll -o %t.hello.o
 ; RUN: llc -filetype=obj %s -o %t.o
 
 target triple = "wasm32-unknown-unknown-wasm"
 
 @foo = hidden global i32 1, align 4
 @aligned_bar = hidden global i32 3, align 16
 
 @hello_str = external global i8*
 @external_ref = global i8** @hello_str, align 8
 
-; RUN: lld -flavor wasm --allow-undefined -o %t.wasm %t.o %t.hello.o
+; RUN: lld -flavor wasm -no-gc-sections --allow-undefined -o %t.wasm %t.o %t.hello.o
 ; RUN: obj2yaml %t.wasm | FileCheck %s
 
 ; CHECK:        - Type:            GLOBAL
 ; CHECK-NEXT:     Globals:
 ; CHECK-NEXT:       - Index:           0
 ; CHECK-NEXT:         Type:            I32
 ; CHECK-NEXT:         Mutable:         true
 ; CHECK-NEXT:         InitExpr:

test/wasm/entry.ll

 
 ; CHECK-CTOR:        - Type:            EXPORT
 ; CHECK-CTOR-NEXT:     Exports:
 ; CHECK-CTOR-NEXT:       - Name:            memory
 ; CHECK-CTOR-NEXT:         Kind:            MEMORY
 ; CHECK-CTOR-NEXT:         Index:           0
 ; CHECK-CTOR-NEXT:       - Name:            __wasm_call_ctors
 ; CHECK-CTOR-NEXT:         Kind:            FUNCTION
-; CHECK-CTOR-NEXT:         Index:           1
+; CHECK-CTOR-NEXT:         Index:           0

test/wasm/gc-sections.ll

+; RUN: llc -filetype=obj %s -o %t.o
+; RUN: lld -flavor wasm -print-gc-sections -o %t1.wasm %t.o | FileCheck %s -check-prefix=PRINT-GC
+; PRINT-GC: removing unused section 'unused_function' in file '{{.*}}'
+; PRINT-GC-NOT: removing unused section 'used_function' in file '{{.*}}'
+; PRINT-GC: removing unused section '.data.unused_data' in file '{{.*}}'
+; PRINT-GC-NOT: removing unused section '.data.used_data' in file '{{.*}}'
+
+target triple = "wasm32-unknown-unknown-wasm"
+
+@unused_data = hidden global i32 1, align 4
+@used_data = hidden global i32 2, align 4
+
+define hidden i32 @unused_function() {
+  %1 = load i32, i32* @unused_data, align 4
+  ret i32 %1
+}
+
+define hidden i32 @used_function() {
+  %1 = load i32, i32* @used_data, align 4
+  ret i32 %1
+}
+
+define hidden void @_start() {
+entry:
+  call i32 @used_function()
+  ret void
+}
+
+; RUN: obj2yaml %t1.wasm | FileCheck %s
+; CHECK:        - Type:            DATA
+; CHECK-NEXT:     Segments:        
+; CHECK-NEXT:       - SectionOffset:   7
+; CHECK-NEXT:         MemoryIndex:     0
+; CHECK-NEXT:         Offset:          
+; CHECK-NEXT:           Opcode:          I32_CONST
+; CHECK-NEXT:           Value:           1024
+; CHECK-NEXT:         Content:         '02000000'
+; CHECK-NEXT:   - Type:            CUSTOM
+; CHECK-NEXT:     Name:            linking
+; CHECK-NEXT:     DataSize:        4
+; CHECK-NEXT:   - Type:            CUSTOM
+; CHECK-NEXT:     Name:            name
+; CHECK-NEXT:     FunctionNames:   
+; CHECK-NEXT:       - Index:           0
+; CHECK-NEXT:         Name:            used_function
+; CHECK-NEXT:       - Index:           1
+; CHECK-NEXT:         Name:            _start
+; CHECK-NEXT:       - Index:           2
+; CHECK-NEXT:         Name:            __wasm_call_ctors
+; CHECK-NEXT: ...
+
+; RUN: lld -flavor wasm -print-gc-sections --no-gc-sections -o %t1.no-gc.wasm %t.o
+; RUN: obj2yaml %t1.no-gc.wasm | FileCheck %s -check-prefix=NO-GC
+; NO-GC:        - Type:            DATA
+; NO-GC-NEXT:     Segments:        
+; NO-GC-NEXT:       - SectionOffset:   7
+; NO-GC-NEXT:         MemoryIndex:     0
+; NO-GC-NEXT:         Offset:          
+; NO-GC-NEXT:           Opcode:          I32_CONST
+; NO-GC-NEXT:           Value:           1024
+; NO-GC-NEXT:         Content:         '0100000002000000'
+; NO-GC-NEXT:   - Type:            CUSTOM
+; NO-GC-NEXT:     Name:            linking
+; NO-GC-NEXT:     DataSize:        8
+; NO-GC-NEXT:   - Type:            CUSTOM
+; NO-GC-NEXT:     Name:            name
+; NO-GC-NEXT:     FunctionNames:   
+; NO-GC-NEXT:       - Index:           0
+; NO-GC-NEXT:         Name:            unused_function
+; NO-GC-NEXT:       - Index:           1
+; NO-GC-NEXT:         Name:            used_function
+; NO-GC-NEXT:       - Index:           2
+; NO-GC-NEXT:         Name:            _start
+; NO-GC-NEXT:       - Index:           3
+; NO-GC-NEXT:         Name:            __wasm_call_ctors
+; NO-GC-NEXT: ...
+
+; RUN: not lld -flavor wasm --gc-sections --relocatable -o %t1.no-gc.wasm %t.o 2>&1 | FileCheck %s -check-prefix=CHECK-ERROR
+; CHECK-ERROR: lld: error: -r and --gc-sections may not be used together

test/wasm/local-symbols.ll

 ; RUN: llc -filetype=obj %s -o %t.o
 ; RUN: lld -flavor wasm -o %t.wasm %t.o
 ; RUN: obj2yaml %t.wasm | FileCheck %s
 
 target triple = "wasm32-unknown-unknown-wasm"
 
 @foo = default global i32 1, align 4
 @bar = internal default global i32 3, align 4
 
 define internal i32 @baz() local_unnamed_addr {
 entry:
-  ret i32 2
+  %0 = load i32, i32* @bar, align 4
+  ret i32 %0
 }
 
 define i32 @_start() local_unnamed_addr {
 entry:
+  call i32 @baz()
   ret i32 1
 }
 
 ; CHECK:      --- !WASM
 ; CHECK-NEXT: FileHeader:
 ; CHECK-NEXT:   Version:         0x00000001
 ; CHECK-NEXT: Sections:
 ; CHECK-NEXT:   - Type:            TYPE

 ; CHECK-NEXT:         Index:           1
 ; CHECK-NEXT:       - Name:            __heap_base
 ; CHECK-NEXT:         Kind:            GLOBAL
 ; CHECK-NEXT:         Index:           1
 ; CHECK-NEXT:   - Type:            CODE
 ; CHECK-NEXT:     Functions:
 ; CHECK-NEXT:       - Index:           0
 ; CHECK-NEXT:         Locals:
-; CHECK-NEXT:         Body:            41020B
+; CHECK-NEXT:         Body:            4100280284888080000B
 ; CHECK-NEXT:       - Index:           1
 ; CHECK-NEXT:         Locals:
-; CHECK-NEXT:         Body:            41010B
+; CHECK-NEXT:         Body:            1080808080001A41010B
 ; CHECK-NEXT:       - Index:           2
 ; CHECK-NEXT:         Locals:
 ; CHECK-NEXT:         Body:            0B
 ; CHECK-NEXT:   - Type:            DATA
 ; CHECK-NEXT:     Segments:
 ; CHECK-NEXT:       - SectionOffset:   7
 ; CHECK-NEXT:         MemoryIndex:     0
 ; CHECK-NEXT:         Offset:

test/wasm/weak-symbols.ll

 ; RUN: llc -filetype=obj %p/Inputs/weak-symbol1.ll -o %t1.o
 ; RUN: llc -filetype=obj %p/Inputs/weak-symbol2.ll -o %t2.o
 ; RUN: llc -filetype=obj %s -o %t.o
-; RUN: lld -flavor wasm -o %t.wasm %t.o %t1.o %t2.o
+; RUN: lld -flavor wasm -no-gc-sections -o %t.wasm %t.o %t1.o %t2.o
 ; RUN: obj2yaml %t.wasm | FileCheck %s
 
 target triple = "wasm32-unknown-unknown-wasm"
 
 declare i32 @weakFn() local_unnamed_addr
 @weakGlobal = external global i32
 
 define i32 @_start() local_unnamed_addr {

wasm/Config.h

 namespace wasm {
 
 class Symbol;
 
 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

 //===- Driver.cpp ---------------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "lld/Common/Driver.h"
 #include "Config.h"
+#include "InputChunks.h"
 #include "SymbolTable.h"
 #include "Writer.h"
 #include "lld/Common/Args.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "lld/Common/Threads.h"
 #include "lld/Common/Version.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Object/Wasm.h"
 #include "llvm/Option/ArgList.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Process.h"
 
+#define DEBUG_TYPE "lld"
+
 using namespace llvm;
 using namespace llvm::sys;
 using namespace llvm::wasm;
 
 using namespace lld;
 using namespace lld::wasm;
 
 namespace {
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();
 }
 
+// This functions implements --gc-sections, which is a feature to remove unused
+// chunks from the output. Unused chunks are those that are not reachable from
+// known root symbols or chunks. This feature is implemented as a mark-sweep
+// garbage collector.
+//
+// Here's how it works. Each InputChunk has a "Live" bit. The bit is off by
+// default. Starting with the GC-roots, visit all reachable chunks and set their
+// Live bits. The Writer will then ignore chunks whose Live bits are off, so
+// that such chunk are not appear in the output.
+static void markLive() { DEBUG(dbgs() << "markLive\n");
+
+  if (!Config->GcSections)
+    return;
+
+  SmallVector<InputChunk *, 256> Q;
+
+  auto Enqueue = [&](Symbol *Sym) {
+    if (!Sym)
+      return;
+    InputChunk *Chunk = Sym->getChunk();
+    if (!Chunk || Chunk->Live)
+      return;
+    Chunk->Live = true;
+    Q.push_back(Chunk);
+  };
+
+  // Add GC root symbols.
+  if (!Config->Entry.empty())
+    Enqueue(Symtab->find(Config->Entry));
+  Enqueue(Config->CtorSymbol);
+
+  // By default we export all non-hidden, so they are gc roots too
+  for (Symbol *Sym : Symtab->getSymbols())
+    if (!Sym->isHidden())
+      Enqueue(Sym);
+
+  // The ctor fuctions are all used the synthetic __wasm_call_ctors function,
+  // but since this function is created in-place it doesn't contain reloctations
+  // which mean we have to manually mark the ctors.
+  for (const ObjFile *Obj : Symtab->ObjectFiles) {
+    const WasmLinkingData &L = Obj->getWasmObj()->linkingData();
+    for (const WasmInitFunc &F : L.InitFunctions)
+      Enqueue(Obj->getFunctionSymbol(F.FunctionIndex));
+  }
+
+  auto EnqueueSuccessors = [Enqueue](InputChunk &Chunk) {
+    for (const WasmRelocation Reloc : Chunk.getRelocations()) {
+      Symbol *Sym = nullptr;
+      switch (Reloc.Type) {
+      case R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
+      case R_WEBASSEMBLY_TABLE_INDEX_I32:
+      case R_WEBASSEMBLY_TABLE_INDEX_SLEB:
+        Sym = Chunk.File->getFunctionSymbol(Reloc.Index);
+        break;
+      case R_WEBASSEMBLY_GLOBAL_INDEX_LEB:
+      case R_WEBASSEMBLY_MEMORY_ADDR_LEB:
+      case R_WEBASSEMBLY_MEMORY_ADDR_SLEB:
+      case R_WEBASSEMBLY_MEMORY_ADDR_I32:
+        Sym = Chunk.File->getGlobalSymbol(Reloc.Index);
+        break;
+      default:
+        return;
+      }
+      Enqueue(Sym);
+    }
+  };
+
+  while (!Q.empty())
+    EnqueueSuccessors(*Q.pop_back_val());
+
+  // Report garbage-collected sections.
+  if (Config->PrintGcSections) {
+    auto CheckChunk = [](const InputChunk *C) {
+      if (!C->Live)
+        message("removing unused section '" + C->getName() + "' in file '" +
+                C->getFileName() + "'");
+    };
+
+    for (const ObjFile *Obj : Symtab->ObjectFiles) {
+      for (InputChunk *C : Obj->Functions)
+        CheckChunk(C);
+      for (InputChunk *C : Obj->Segments)
+        CheckChunk(C);
+    }
+  }
+}
+
 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");
   Config->ImportMemory = Args.hasArg(OPT_import_memory);
   Config->OutputFile = Args.getLastArgValue(OPT_o);
   Config->Relocatable = Args.hasArg(OPT_relocatable);
+  Config->GcSections =
+      Args.hasFlag(OPT_gc_sections, OPT_no_gc_sections, !Config->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);
 
void LinkerDriver::link(ArrayRef<const char *> ArgsArr) {
   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());
     }
void LinkerDriver::link(ArrayRef<const char *> ArgsArr) {
   }
 
   if (EntrySym)
     EntrySym->setHidden(false);
 
   if (errorCount())
     return;
 
+  // Do size optimizations: garbage collection
+  markLive();
+
   // Write the result to the file.
   writeResult();
 }

wasm/InputChunks.h

 // An input chunk represents an indivisible blocks of code or data from an input
 // file.  i.e. a single wasm data segment or a single wasm function.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_WASM_INPUT_CHUNKS_H
 #define LLD_WASM_INPUT_CHUNKS_H
 
+#include "Config.h"
 #include "InputFiles.h"
 #include "WriterUtils.h"
 #include "lld/Common/ErrorHandler.h"
 #include "llvm/Object/Wasm.h"
 
 using llvm::object::WasmSegment;
 using llvm::wasm::WasmFunction;
 using llvm::wasm::WasmRelocation;
public:
   ArrayRef<WasmRelocation> getRelocations() const { return Relocations; }
   StringRef getFileName() const { return File->getName(); }
 
   virtual StringRef getComdat() const = 0;
   virtual StringRef getName() const = 0;
 
   bool Discarded = false;
   std::vector<OutputRelocation> OutRelocations;
+  const ObjFile *File;
+
+  // The garbage collector sets sections' Live bits.
+  // If GC is disabled, all sections are considered live by default.
+  unsigned Live : 1;
 
 protected:
-  InputChunk(const ObjFile *F, Kind K) : File(F), SectionKind(K) {}
+  InputChunk(const ObjFile *F, Kind K)
+      : File(F), Live(!Config->GcSections), SectionKind(K) {}
   virtual ~InputChunk() = default;
   void calcRelocations();
   virtual ArrayRef<uint8_t> data() const = 0;
   virtual uint32_t getInputSectionOffset() const = 0;
 
   std::vector<WasmRelocation> Relocations;
   int32_t OutputOffset = 0;
-  const ObjFile *File;
   Kind SectionKind;
 };
 
 // Represents a WebAssembly data segment which can be included as part of
 // an output data segments.  Note that in WebAssembly, unlike ELF and other
 // formats, used the term "data segment" to refer to the continous regions of
 // memory that make on the data section. See:
 // https://webassembly.github.io/spec/syntax/modules.html#syntax-data

wasm/InputFiles.h

public:
   std::vector<InputFunction *> Functions;
 
   ArrayRef<Symbol *> getSymbols() const { return Symbols; }
 
   Symbol *getFunctionSymbol(uint32_t Index) const {
     return FunctionSymbols[Index];
   }
 
+  Symbol *getGlobalSymbol(uint32_t Index) const { return GlobalSymbols[Index]; }
+
 private:
   uint32_t relocateVirtualAddress(uint32_t Index) const;
   uint32_t relocateTypeIndex(uint32_t Original) const;
   uint32_t relocateGlobalIndex(uint32_t Original) const;
   uint32_t relocateTableIndex(uint32_t Original) const;
 
   Symbol *createDefined(const WasmSymbol &Sym, Symbol::Kind Kind,
                         InputChunk *Chunk = nullptr,

wasm/InputFiles.cpp

void ObjFile::dumpInfo() const {
   log("info for: " + getName() + "\n" +
       "      Total Functions : " + Twine(FunctionSymbols.size()) + "\n" +
       "        Total Globals : " + Twine(GlobalSymbols.size()) + "\n" +
       "     Function Imports : " + Twine(NumFunctionImports) + "\n" +
       "       Global Imports : " + Twine(NumGlobalImports) + "\n");
 }
 
 uint32_t ObjFile::relocateVirtualAddress(uint32_t GlobalIndex) const {
-  return GlobalSymbols[GlobalIndex]->getVirtualAddress();
+  return getGlobalSymbol(GlobalIndex)->getVirtualAddress();
 }
 
 uint32_t ObjFile::relocateFunctionIndex(uint32_t Original) const {
-  Symbol *Sym = FunctionSymbols[Original];
+  const Symbol *Sym = getFunctionSymbol(Original);
   uint32_t Index = Sym->getOutputIndex();
   DEBUG(dbgs() << "relocateFunctionIndex: " << toString(*Sym) << ": "
                << Original << " -> " << Index << "\n");
   return Index;
 }
 
 uint32_t ObjFile::relocateTypeIndex(uint32_t Original) const {
   return TypeMap[Original];
 }
 
 uint32_t ObjFile::relocateTableIndex(uint32_t Original) const {
-  Symbol *Sym = FunctionSymbols[Original];
+  const Symbol *Sym = getFunctionSymbol(Original);
   uint32_t Index = Sym->hasTableIndex() ? Sym->getTableIndex() : 0;
   DEBUG(dbgs() << "relocateTableIndex: " << toString(*Sym) << ": " << Original
                << " -> " << Index << "\n");
   return Index;
 }
 
 uint32_t ObjFile::relocateGlobalIndex(uint32_t Original) const {
-  Symbol *Sym = GlobalSymbols[Original];
+  const Symbol *Sym = getGlobalSymbol(Original);
   uint32_t Index = Sym->hasOutputIndex() ? Sym->getOutputIndex() : 0;
   DEBUG(dbgs() << "relocateGlobalIndex: " << toString(*Sym) << ": " << Original
                << " -> " << Index << "\n");
   return Index;
 }
 
 // Relocations contain an index into the function, global or table index
 // space of the input file.  This function takes a relocation and returns the

wasm/Options.td

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 L: JoinedOrSeparate<["-"], "L">, MetaVarName<"<dir>">,
   HelpText<"Add a directory to the library search path">;
 
 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_fatal_warnings: F<"no-fatal-warnings">;
 
+def no_gc_sections: F<"no-gc-sections">,
+  HelpText<"Disable garbage collection of unused sections">;
+
+def no_print_gc_sections: F<"no-print-gc-sections">,
+  HelpText<"Do not list removed unused sections">;
+
 def o: JoinedOrSeparate<["-"], "o">, MetaVarName<"<path>">,
   HelpText<"Path to file to write output">;
 
+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">;
 

wasm/Writer.cpp

void Writer::calculateExports() {
   if (Config->CtorSymbol && (!Config->CtorSymbol->isHidden() || ExportHidden))
     ExportedSymbols.emplace_back(
         WasmExportEntry{Config->CtorSymbol, Config->CtorSymbol->getName()});
 
   for (ObjFile *File : Symtab->ObjectFiles) {
     for (Symbol *Sym : File->getSymbols()) {
       if (!Sym->isDefined() || File != Sym->getFile())
         continue;
       if (Sym->isGlobal())
         continue;
       if (Sym->getChunk()->Discarded)
         continue;
 
       if ((Sym->isHidden() || Sym->isLocal()) && !ExportHidden)
         continue;
+
+      // We should never be exporting a non-live symbol
+      assert(Sym->getChunk()->Live);
       ExportedSymbols.emplace_back(WasmExportEntry{Sym, BudgeLocalName(Sym)});
     }
   }
 
   for (const Symbol *Sym : DefinedGlobals) {
     // Can't export the SP right now because its mutable, and mutuable globals
     // are yet supported in the official binary format.
     // TODO(sbc): Remove this if/when the "mutable global" proposal is accepted.
if (Config->Relocatable) {
         Sym->setOutputIndex(GlobalIndex++);
       }
     }
   }
 
   for (ObjFile *File : Symtab->ObjectFiles) {
     DEBUG(dbgs() << "Functions: " << File->getName() << "\n");
     for (InputFunction *Func : File->Functions) {
-      if (Func->Discarded)
+      if (Func->Discarded || !Func->Live)
         continue;
       DefinedFunctions.emplace_back(Func);
       Func->setOutputIndex(FunctionIndex++);
     }
   }
 
   for (ObjFile *File : Symtab->ObjectFiles) {
     DEBUG(dbgs() << "Table Indexes: " << File->getName() << "\n");
static StringRef getOutputDataSegmentName(StringRef Name) {
   }
 
   return Name;
 }
 
 void Writer::createOutputSegments() {
   for (ObjFile *File : Symtab->ObjectFiles) {
     for (InputSegment *Segment : File->Segments) {
-      if (Segment->Discarded)
+      if (Segment->Discarded || !Segment->Live)
         continue;
       StringRef Name = getOutputDataSegmentName(Segment->getName());
       OutputSegment *&S = SegmentMap[Name];
       if (S == nullptr) {
         DEBUG(dbgs() << "new segment: " << Name << "\n");
         S = make<OutputSegment>(Name);
         Segments.push_back(S);
       }