1//===- MarkLive.cpp -------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements --gc-sections, which is a feature to remove unused
10// chunks from the output. Unused chunks are those that are not reachable from
11// known root symbols or chunks. This feature is implemented as a mark-sweep
12// garbage collector.
13//
14// Here's how it works. Each InputChunk has a "Live" bit. The bit is off by
15// default. Starting with the GC-roots, visit all reachable chunks and set their
16// Live bits. The Writer will then ignore chunks whose Live bits are off, so
17// that such chunk are not appear in the output.
18//
19//===----------------------------------------------------------------------===//
20
21#include "MarkLive.h"
22#include "Config.h"
23#include "InputChunks.h"
24#include "InputElement.h"
25#include "SymbolTable.h"
26#include "Symbols.h"
27
28#define DEBUG_TYPE "lld"
29
30using namespace llvm;
31using namespace llvm::wasm;
32
33namespace lld::wasm {
34
35namespace {
36
37class MarkLive {
38public:
39 void run();
40
41private:
42 void enqueue(Symbol *sym);
43 void enqueue(InputChunk *chunk);
44 void enqueueInitFunctions(const ObjFile *sym);
45 void enqueueRetainedSegments(const ObjFile *file);
46 void mark();
47 bool isCallCtorsLive();
48
49 // A list of chunks to visit.
50 SmallVector<InputChunk *, 256> queue;
51};
52
53} // namespace
54
55void MarkLive::enqueue(Symbol *sym) {
56 if (!sym || sym->isLive())
57 return;
58 LLVM_DEBUG(dbgs() << "markLive: " << sym->getName() << "\n");
59
60 InputFile *file = sym->getFile();
61 bool markImplicitDeps = file && !file->isLive() && sym->isDefined();
62
63 sym->markLive();
64
65 if (markImplicitDeps) {
66 if (auto obj = dyn_cast<ObjFile>(Val: file)) {
67 // Mark as live the ctor functions in the object that defines this symbol.
68 // The ctor functions are all referenced by the synthetic callCtors
69 // function. However, this function does not contain relocations so we
70 // have to manually mark the ctors as live.
71 enqueueInitFunctions(sym: obj);
72 // Mark retained segments in the object that defines this symbol live.
73 enqueueRetainedSegments(file: obj);
74 }
75 }
76
77 if (InputChunk *chunk = sym->getChunk())
78 queue.push_back(Elt: chunk);
79}
80
81void MarkLive::enqueue(InputChunk *chunk) {
82 LLVM_DEBUG(dbgs() << "markLive: " << toString(chunk) << "\n");
83 chunk->live = true;
84 queue.push_back(Elt: chunk);
85}
86
87// The ctor functions are all referenced by the synthetic callCtors
88// function. However, this function does not contain relocations so we
89// have to manually mark the ctors as live.
90void MarkLive::enqueueInitFunctions(const ObjFile *obj) {
91 const WasmLinkingData &l = obj->getWasmObj()->linkingData();
92 for (const WasmInitFunc &f : l.InitFunctions) {
93 auto *initSym = obj->getFunctionSymbol(index: f.Symbol);
94 if (!initSym->isDiscarded())
95 enqueue(sym: initSym);
96 }
97}
98
99// Mark segments flagged by segment-level no-strip. Segment-level no-strip is
100// usually used to retain segments without having symbol table entry.
101void MarkLive::enqueueRetainedSegments(const ObjFile *file) {
102 for (InputChunk *chunk : file->segments)
103 if (chunk->isRetained())
104 enqueue(chunk);
105}
106
107void MarkLive::run() {
108 // Add GC root symbols.
109 if (!ctx.arg.entry.empty())
110 enqueue(sym: symtab->find(name: ctx.arg.entry));
111
112 // We need to preserve any no-strip or exported symbol
113 for (Symbol *sym : symtab->symbols())
114 if (sym->isNoStrip() || sym->isExported())
115 enqueue(sym);
116
117 if (ctx.sym.callDtors)
118 enqueue(sym: ctx.sym.callDtors);
119
120 for (const ObjFile *obj : ctx.objectFiles)
121 if (obj->isLive()) {
122 // Enqueue constructors in objects explicitly live from the command-line.
123 enqueueInitFunctions(obj);
124 // Enqueue retained segments in objects explicitly live from the
125 // command-line.
126 enqueueRetainedSegments(file: obj);
127 }
128
129 // `__wasm_{get,set}_tls_base` are called from synthetic init functions (e.g.
130 // `__wasm_init_tls`, `__wasm_init_memory`) via raw `call` instructions that
131 // carry no relocations, so the mark phase below cannot discover the functions
132 // they in turn call (e.g. the cooperative-threading
133 // `context.get`/`context.set` builtins). They are already marked live, but
134 // their defining chunks were never enqueued; enqueue them here so their
135 // relocations are followed. This mirrors the handling of ctor functions
136 // reached via `__wasm_call_ctors`.
137 for (Symbol *sym : {static_cast<Symbol *>(ctx.sym.getTLSBase),
138 static_cast<Symbol *>(ctx.sym.setTLSBase)})
139 if (sym)
140 if (InputChunk *c = sym->getChunk())
141 enqueue(chunk: c);
142
143 mark();
144
145 // If we have any non-discarded init functions, mark `__wasm_call_ctors` as
146 // live so that we assign it an index and call it.
147 if (isCallCtorsLive())
148 ctx.sym.callCtors->markLive();
149}
150
151void MarkLive::mark() {
152 // Follow relocations to mark all reachable chunks.
153 while (!queue.empty()) {
154 InputChunk *c = queue.pop_back_val();
155
156 for (const WasmRelocation reloc : c->getRelocations()) {
157 if (reloc.Type == R_WASM_TYPE_INDEX_LEB)
158 continue;
159 Symbol *sym = c->file->getSymbol(index: reloc.Index);
160
161 // If the function has been assigned the special index zero in the table,
162 // the relocation doesn't pull in the function body, since the function
163 // won't actually go in the table (the runtime will trap attempts to call
164 // that index, since we don't use it). A function with a table index of
165 // zero is only reachable via "call", not via "call_indirect". The stub
166 // functions used for weak-undefined symbols have this behaviour (compare
167 // equal to null pointer, only reachable via direct call).
168 if (reloc.Type == R_WASM_TABLE_INDEX_SLEB ||
169 reloc.Type == R_WASM_TABLE_INDEX_SLEB64 ||
170 reloc.Type == R_WASM_TABLE_INDEX_I32 ||
171 reloc.Type == R_WASM_TABLE_INDEX_I64) {
172 auto *funcSym = cast<FunctionSymbol>(Val: sym);
173 if (funcSym->isStub)
174 continue;
175 }
176
177 enqueue(sym);
178 }
179 }
180}
181
182void markLive() {
183 if (!ctx.arg.gcSections)
184 return;
185
186 LLVM_DEBUG(dbgs() << "markLive\n");
187
188 MarkLive marker;
189 marker.run();
190
191 // Report garbage-collected sections.
192 if (ctx.arg.printGcSections) {
193 for (const ObjFile *obj : ctx.objectFiles) {
194 for (InputChunk *c : obj->functions)
195 if (!c->live)
196 message(msg: "removing unused section " + toString(c));
197 for (InputChunk *c : obj->segments)
198 if (!c->live)
199 message(msg: "removing unused section " + toString(c));
200 for (InputGlobal *g : obj->globals)
201 if (!g->live)
202 message(msg: "removing unused section " + toString(d: g));
203 for (InputTag *t : obj->tags)
204 if (!t->live)
205 message(msg: "removing unused section " + toString(d: t));
206 for (InputTable *t : obj->tables)
207 if (!t->live)
208 message(msg: "removing unused section " + toString(d: t));
209 }
210 for (InputChunk *c : ctx.syntheticFunctions)
211 if (!c->live)
212 message(msg: "removing unused section " + toString(c));
213 for (InputGlobal *g : ctx.syntheticGlobals)
214 if (!g->live)
215 message(msg: "removing unused section " + toString(d: g));
216 for (InputTable *t : ctx.syntheticTables)
217 if (!t->live)
218 message(msg: "removing unused section " + toString(d: t));
219 }
220}
221
222bool MarkLive::isCallCtorsLive() {
223 // In a reloctable link, we don't call `__wasm_call_ctors`.
224 if (ctx.arg.relocatable)
225 return false;
226
227 // In Emscripten-style PIC, we call `__wasm_call_ctors` which calls
228 // `__wasm_apply_data_relocs`.
229 if (ctx.isPic)
230 return true;
231
232 // If there are any init functions, mark `__wasm_call_ctors` live so that
233 // it can call them.
234 for (const ObjFile *file : ctx.objectFiles) {
235 const WasmLinkingData &l = file->getWasmObj()->linkingData();
236 for (const WasmInitFunc &f : l.InitFunctions) {
237 auto *sym = file->getFunctionSymbol(index: f.Symbol);
238 if (!sym->isDiscarded() && sym->isLive())
239 return true;
240 }
241 }
242
243 return false;
244}
245
246} // namespace lld::wasm
247