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 // Mark ctor functions in the object that defines this symbol live.
67 // The ctor functions are all referenced by the synthetic callCtors
68 // function. However, this function does not contain relocations so we
69 // have to manually mark the ctors as live.
70 enqueueInitFunctions(sym: cast<ObjFile>(Val: file));
71 // Mark retained segments in the object that defines this symbol live.
72 enqueueRetainedSegments(file: cast<ObjFile>(Val: file));
73 }
74
75 if (InputChunk *chunk = sym->getChunk())
76 queue.push_back(Elt: chunk);
77}
78
79void MarkLive::enqueue(InputChunk *chunk) {
80 LLVM_DEBUG(dbgs() << "markLive: " << toString(chunk) << "\n");
81 chunk->live = true;
82 queue.push_back(Elt: chunk);
83}
84
85// The ctor functions are all referenced by the synthetic callCtors
86// function. However, this function does not contain relocations so we
87// have to manually mark the ctors as live.
88void MarkLive::enqueueInitFunctions(const ObjFile *obj) {
89 const WasmLinkingData &l = obj->getWasmObj()->linkingData();
90 for (const WasmInitFunc &f : l.InitFunctions) {
91 auto *initSym = obj->getFunctionSymbol(index: f.Symbol);
92 if (!initSym->isDiscarded())
93 enqueue(sym: initSym);
94 }
95}
96
97// Mark segments flagged by segment-level no-strip. Segment-level no-strip is
98// usually used to retain segments without having symbol table entry.
99void MarkLive::enqueueRetainedSegments(const ObjFile *file) {
100 for (InputChunk *chunk : file->segments)
101 if (chunk->isRetained())
102 enqueue(chunk);
103}
104
105void MarkLive::run() {
106 // Add GC root symbols.
107 if (!config->entry.empty())
108 enqueue(sym: symtab->find(name: config->entry));
109
110 // We need to preserve any no-strip or exported symbol
111 for (Symbol *sym : symtab->symbols())
112 if (sym->isNoStrip() || sym->isExported())
113 enqueue(sym);
114
115 if (WasmSym::callDtors)
116 enqueue(sym: WasmSym::callDtors);
117
118 for (const ObjFile *obj : ctx.objectFiles)
119 if (obj->isLive()) {
120 // Enqueue constructors in objects explicitly live from the command-line.
121 enqueueInitFunctions(obj);
122 // Enqueue retained segments in objects explicitly live from the
123 // command-line.
124 enqueueRetainedSegments(file: obj);
125 }
126
127 mark();
128
129 // If we have any non-discarded init functions, mark `__wasm_call_ctors` as
130 // live so that we assign it an index and call it.
131 if (isCallCtorsLive())
132 WasmSym::callCtors->markLive();
133}
134
135void MarkLive::mark() {
136 // Follow relocations to mark all reachable chunks.
137 while (!queue.empty()) {
138 InputChunk *c = queue.pop_back_val();
139
140 for (const WasmRelocation reloc : c->getRelocations()) {
141 if (reloc.Type == R_WASM_TYPE_INDEX_LEB)
142 continue;
143 Symbol *sym = c->file->getSymbol(index: reloc.Index);
144
145 // If the function has been assigned the special index zero in the table,
146 // the relocation doesn't pull in the function body, since the function
147 // won't actually go in the table (the runtime will trap attempts to call
148 // that index, since we don't use it). A function with a table index of
149 // zero is only reachable via "call", not via "call_indirect". The stub
150 // functions used for weak-undefined symbols have this behaviour (compare
151 // equal to null pointer, only reachable via direct call).
152 if (reloc.Type == R_WASM_TABLE_INDEX_SLEB ||
153 reloc.Type == R_WASM_TABLE_INDEX_SLEB64 ||
154 reloc.Type == R_WASM_TABLE_INDEX_I32 ||
155 reloc.Type == R_WASM_TABLE_INDEX_I64) {
156 auto *funcSym = cast<FunctionSymbol>(Val: sym);
157 if (funcSym->isStub)
158 continue;
159 }
160
161 enqueue(sym);
162 }
163 }
164}
165
166void markLive() {
167 if (!config->gcSections)
168 return;
169
170 LLVM_DEBUG(dbgs() << "markLive\n");
171
172 MarkLive marker;
173 marker.run();
174
175 // Report garbage-collected sections.
176 if (config->printGcSections) {
177 for (const ObjFile *obj : ctx.objectFiles) {
178 for (InputChunk *c : obj->functions)
179 if (!c->live)
180 message(msg: "removing unused section " + toString(c));
181 for (InputChunk *c : obj->segments)
182 if (!c->live)
183 message(msg: "removing unused section " + toString(c));
184 for (InputGlobal *g : obj->globals)
185 if (!g->live)
186 message(msg: "removing unused section " + toString(d: g));
187 for (InputTag *t : obj->tags)
188 if (!t->live)
189 message(msg: "removing unused section " + toString(d: t));
190 for (InputTable *t : obj->tables)
191 if (!t->live)
192 message(msg: "removing unused section " + toString(d: t));
193 }
194 for (InputChunk *c : ctx.syntheticFunctions)
195 if (!c->live)
196 message(msg: "removing unused section " + toString(c));
197 for (InputGlobal *g : ctx.syntheticGlobals)
198 if (!g->live)
199 message(msg: "removing unused section " + toString(d: g));
200 for (InputTable *t : ctx.syntheticTables)
201 if (!t->live)
202 message(msg: "removing unused section " + toString(d: t));
203 }
204}
205
206bool MarkLive::isCallCtorsLive() {
207 // In a reloctable link, we don't call `__wasm_call_ctors`.
208 if (config->relocatable)
209 return false;
210
211 // In Emscripten-style PIC, we call `__wasm_call_ctors` which calls
212 // `__wasm_apply_data_relocs`.
213 if (ctx.isPic)
214 return true;
215
216 // If there are any init functions, mark `__wasm_call_ctors` live so that
217 // it can call them.
218 for (const ObjFile *file : ctx.objectFiles) {
219 const WasmLinkingData &l = file->getWasmObj()->linkingData();
220 for (const WasmInitFunc &f : l.InitFunctions) {
221 auto *sym = file->getFunctionSymbol(index: f.Symbol);
222 if (!sym->isDiscarded() && sym->isLive())
223 return true;
224 }
225 }
226
227 return false;
228}
229
230} // namespace lld::wasm
231

source code of lld/wasm/MarkLive.cpp