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 "InputEvent.h"
25 #include "InputGlobal.h"
26 #include "SymbolTable.h"
27 #include "Symbols.h"
28
29 #define DEBUG_TYPE "lld"
30
31 using namespace llvm;
32 using namespace llvm::wasm;
33
34 namespace lld {
35 namespace wasm {
36
37 namespace {
38
39 class MarkLive {
40 public:
41 void run();
42
43 private:
44 void enqueue(Symbol *sym);
45 void enqueueInitFunctions(const ObjFile *sym);
46 void mark();
47 bool isCallCtorsLive();
48
49 // A list of chunks to visit.
50 SmallVector<InputChunk *, 256> queue;
51 };
52
53 } // namespace
54
enqueue(Symbol * sym)55 void 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 needInitFunctions = file && !file->isLive() && sym->isDefined();
62
63 sym->markLive();
64
65 // Mark ctor functions in the object that defines this symbol live.
66 // The ctor functions are all referenced by the synthetic callCtors
67 // function. However, this function does not contain relocations so we
68 // have to manually mark the ctors as live.
69 if (needInitFunctions)
70 enqueueInitFunctions(cast<ObjFile>(file));
71
72 if (InputChunk *chunk = sym->getChunk())
73 queue.push_back(chunk);
74 }
75
76 // The ctor functions are all referenced by the synthetic callCtors
77 // function. However, this function does not contain relocations so we
78 // have to manually mark the ctors as live.
enqueueInitFunctions(const ObjFile * obj)79 void MarkLive::enqueueInitFunctions(const ObjFile *obj) {
80 const WasmLinkingData &l = obj->getWasmObj()->linkingData();
81 for (const WasmInitFunc &f : l.InitFunctions) {
82 auto *initSym = obj->getFunctionSymbol(f.Symbol);
83 if (!initSym->isDiscarded())
84 enqueue(initSym);
85 }
86 }
87
run()88 void MarkLive::run() {
89 // Add GC root symbols.
90 if (!config->entry.empty())
91 enqueue(symtab->find(config->entry));
92
93 // We need to preserve any no-strip or exported symbol
94 for (Symbol *sym : symtab->getSymbols())
95 if (sym->isNoStrip() || sym->isExported())
96 enqueue(sym);
97
98 if (WasmSym::callDtors)
99 enqueue(WasmSym::callDtors);
100
101 if (WasmSym::applyRelocs)
102 enqueue(WasmSym::applyRelocs);
103
104 if (WasmSym::initMemory)
105 enqueue(WasmSym::initMemory);
106
107 // Enqueue constructors in objects explicitly live from the command-line.
108 for (const ObjFile *obj : symtab->objectFiles)
109 if (obj->isLive())
110 enqueueInitFunctions(obj);
111
112 mark();
113
114 // If we have any non-discarded init functions, mark `__wasm_call_ctors` as
115 // live so that we assign it an index and call it.
116 if (isCallCtorsLive())
117 WasmSym::callCtors->markLive();
118 }
119
mark()120 void MarkLive::mark() {
121 // Follow relocations to mark all reachable chunks.
122 while (!queue.empty()) {
123 InputChunk *c = queue.pop_back_val();
124
125 for (const WasmRelocation reloc : c->getRelocations()) {
126 if (reloc.Type == R_WASM_TYPE_INDEX_LEB)
127 continue;
128 Symbol *sym = c->file->getSymbol(reloc.Index);
129
130 // If the function has been assigned the special index zero in the table,
131 // the relocation doesn't pull in the function body, since the function
132 // won't actually go in the table (the runtime will trap attempts to call
133 // that index, since we don't use it). A function with a table index of
134 // zero is only reachable via "call", not via "call_indirect". The stub
135 // functions used for weak-undefined symbols have this behaviour (compare
136 // equal to null pointer, only reachable via direct call).
137 if (reloc.Type == R_WASM_TABLE_INDEX_SLEB ||
138 reloc.Type == R_WASM_TABLE_INDEX_SLEB64 ||
139 reloc.Type == R_WASM_TABLE_INDEX_I32 ||
140 reloc.Type == R_WASM_TABLE_INDEX_I64) {
141 auto *funcSym = cast<FunctionSymbol>(sym);
142 if (funcSym->isStub)
143 continue;
144 }
145
146 enqueue(sym);
147 }
148 }
149 }
150
markLive()151 void markLive() {
152 if (!config->gcSections)
153 return;
154
155 LLVM_DEBUG(dbgs() << "markLive\n");
156
157 MarkLive marker;
158 marker.run();
159
160 // Report garbage-collected sections.
161 if (config->printGcSections) {
162 for (const ObjFile *obj : symtab->objectFiles) {
163 for (InputChunk *c : obj->functions)
164 if (!c->live)
165 message("removing unused section " + toString(c));
166 for (InputChunk *c : obj->segments)
167 if (!c->live)
168 message("removing unused section " + toString(c));
169 for (InputGlobal *g : obj->globals)
170 if (!g->live)
171 message("removing unused section " + toString(g));
172 for (InputEvent *e : obj->events)
173 if (!e->live)
174 message("removing unused section " + toString(e));
175 }
176 for (InputChunk *c : symtab->syntheticFunctions)
177 if (!c->live)
178 message("removing unused section " + toString(c));
179 for (InputGlobal *g : symtab->syntheticGlobals)
180 if (!g->live)
181 message("removing unused section " + toString(g));
182 }
183 }
184
isCallCtorsLive()185 bool MarkLive::isCallCtorsLive() {
186 // In a reloctable link, we don't call `__wasm_call_ctors`.
187 if (config->relocatable)
188 return false;
189
190 // In Emscripten-style PIC, we call `__wasm_call_ctors` which calls
191 // `__wasm_apply_relocs`.
192 if (config->isPic)
193 return true;
194
195 // If there are any init functions, mark `__wasm_call_ctors` live so that
196 // it can call them.
197 for (const ObjFile *file : symtab->objectFiles) {
198 const WasmLinkingData &l = file->getWasmObj()->linkingData();
199 for (const WasmInitFunc &f : l.InitFunctions) {
200 auto *sym = file->getFunctionSymbol(f.Symbol);
201 if (!sym->isDiscarded() && sym->isLive())
202 return true;
203 }
204 }
205
206 return false;
207 }
208
209 } // namespace wasm
210 } // namespace lld
211