1 //===- MarkLive.cpp -------------------------------------------------------===//
2 //
3 // The LLVM Linker
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements --gc-sections, which is a feature to remove unused
11 // chunks from the output. Unused chunks are those that are not reachable from
12 // known root symbols or chunks. This feature is implemented as a mark-sweep
13 // garbage collector.
14 //
15 // Here's how it works. Each InputChunk has a "Live" bit. The bit is off by
16 // default. Starting with the GC-roots, visit all reachable chunks and set their
17 // Live bits. The Writer will then ignore chunks whose Live bits are off, so
18 // that such chunk are not appear in the output.
19 //
20 //===----------------------------------------------------------------------===//
21
22 #include "MarkLive.h"
23 #include "Config.h"
24 #include "InputChunks.h"
25 #include "InputEvent.h"
26 #include "InputGlobal.h"
27 #include "SymbolTable.h"
28 #include "Symbols.h"
29
30 #define DEBUG_TYPE "lld"
31
32 using namespace llvm;
33 using namespace llvm::wasm;
34
markLive()35 void lld::wasm::markLive() {
36 if (!Config->GcSections)
37 return;
38
39 LLVM_DEBUG(dbgs() << "markLive\n");
40 SmallVector<InputChunk *, 256> Q;
41
42 auto Enqueue = [&](Symbol *Sym) {
43 if (!Sym || Sym->isLive())
44 return;
45 LLVM_DEBUG(dbgs() << "markLive: " << Sym->getName() << "\n");
46 Sym->markLive();
47 if (InputChunk *Chunk = Sym->getChunk())
48 Q.push_back(Chunk);
49 };
50
51 // Add GC root symbols.
52 if (!Config->Entry.empty())
53 Enqueue(Symtab->find(Config->Entry));
54 Enqueue(WasmSym::CallCtors);
55
56 // We need to preserve any exported symbol
57 for (Symbol *Sym : Symtab->getSymbols())
58 if (Sym->isExported())
59 Enqueue(Sym);
60
61 // The ctor functions are all used in the synthetic __wasm_call_ctors
62 // function, but since this function is created in-place it doesn't contain
63 // relocations which mean we have to manually mark the ctors.
64 for (const ObjFile *Obj : Symtab->ObjectFiles) {
65 const WasmLinkingData &L = Obj->getWasmObj()->linkingData();
66 for (const WasmInitFunc &F : L.InitFunctions)
67 Enqueue(Obj->getFunctionSymbol(F.Symbol));
68 }
69
70 // Follow relocations to mark all reachable chunks.
71 while (!Q.empty()) {
72 InputChunk *C = Q.pop_back_val();
73
74 for (const WasmRelocation Reloc : C->getRelocations()) {
75 if (Reloc.Type == R_WEBASSEMBLY_TYPE_INDEX_LEB)
76 continue;
77 Symbol *Sym = C->File->getSymbol(Reloc.Index);
78
79 // If the function has been assigned the special index zero in the table,
80 // the relocation doesn't pull in the function body, since the function
81 // won't actually go in the table (the runtime will trap attempts to call
82 // that index, since we don't use it). A function with a table index of
83 // zero is only reachable via "call", not via "call_indirect". The stub
84 // functions used for weak-undefined symbols have this behaviour (compare
85 // equal to null pointer, only reachable via direct call).
86 if (Reloc.Type == R_WEBASSEMBLY_TABLE_INDEX_SLEB ||
87 Reloc.Type == R_WEBASSEMBLY_TABLE_INDEX_I32) {
88 auto *FuncSym = cast<FunctionSymbol>(Sym);
89 if (FuncSym->hasTableIndex() && FuncSym->getTableIndex() == 0)
90 continue;
91 }
92
93 Enqueue(Sym);
94 }
95 }
96
97 // Report garbage-collected sections.
98 if (Config->PrintGcSections) {
99 for (const ObjFile *Obj : Symtab->ObjectFiles) {
100 for (InputChunk *C : Obj->Functions)
101 if (!C->Live)
102 message("removing unused section " + toString(C));
103 for (InputChunk *C : Obj->Segments)
104 if (!C->Live)
105 message("removing unused section " + toString(C));
106 for (InputGlobal *G : Obj->Globals)
107 if (!G->Live)
108 message("removing unused section " + toString(G));
109 for (InputEvent *E : Obj->Events)
110 if (!E->Live)
111 message("removing unused section " + toString(E));
112 }
113 for (InputChunk *C : Symtab->SyntheticFunctions)
114 if (!C->Live)
115 message("removing unused section " + toString(C));
116 for (InputGlobal *G : Symtab->SyntheticGlobals)
117 if (!G->Live)
118 message("removing unused section " + toString(G));
119 }
120 }
121