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 void lld::wasm::markLive() { 35 if (!config->gcSections) 36 return; 37 38 LLVM_DEBUG(dbgs() << "markLive\n"); 39 SmallVector<InputChunk *, 256> q; 40 41 std::function<void(Symbol*)> enqueue = [&](Symbol *sym) { 42 if (!sym || sym->isLive()) 43 return; 44 LLVM_DEBUG(dbgs() << "markLive: " << sym->getName() << "\n"); 45 sym->markLive(); 46 if (InputChunk *chunk = sym->getChunk()) 47 q.push_back(chunk); 48 49 // The ctor functions are all referenced by the synthetic callCtors 50 // function. However, this function does not contain relocations so we 51 // have to manually mark the ctors as live if callCtors itself is live. 52 if (sym == WasmSym::callCtors) { 53 if (config->isPic) 54 enqueue(WasmSym::applyRelocs); 55 for (const ObjFile *obj : symtab->objectFiles) { 56 const WasmLinkingData &l = obj->getWasmObj()->linkingData(); 57 for (const WasmInitFunc &f : l.InitFunctions) { 58 auto* initSym = obj->getFunctionSymbol(f.Symbol); 59 if (!initSym->isDiscarded()) 60 enqueue(initSym); 61 } 62 } 63 } 64 }; 65 66 // Add GC root symbols. 67 if (!config->entry.empty()) 68 enqueue(symtab->find(config->entry)); 69 70 // We need to preserve any no-strip or exported symbol 71 for (Symbol *sym : symtab->getSymbols()) 72 if (sym->isNoStrip() || sym->isExported()) 73 enqueue(sym); 74 75 // For relocatable output, we need to preserve all the ctor functions 76 if (config->relocatable) { 77 for (const ObjFile *obj : symtab->objectFiles) { 78 const WasmLinkingData &l = obj->getWasmObj()->linkingData(); 79 for (const WasmInitFunc &f : l.InitFunctions) 80 enqueue(obj->getFunctionSymbol(f.Symbol)); 81 } 82 } 83 84 if (config->isPic) 85 enqueue(WasmSym::callCtors); 86 87 if (config->sharedMemory && !config->shared) 88 enqueue(WasmSym::initMemory); 89 90 // Follow relocations to mark all reachable chunks. 91 while (!q.empty()) { 92 InputChunk *c = q.pop_back_val(); 93 94 for (const WasmRelocation reloc : c->getRelocations()) { 95 if (reloc.Type == R_WASM_TYPE_INDEX_LEB) 96 continue; 97 Symbol *sym = c->file->getSymbol(reloc.Index); 98 99 // If the function has been assigned the special index zero in the table, 100 // the relocation doesn't pull in the function body, since the function 101 // won't actually go in the table (the runtime will trap attempts to call 102 // that index, since we don't use it). A function with a table index of 103 // zero is only reachable via "call", not via "call_indirect". The stub 104 // functions used for weak-undefined symbols have this behaviour (compare 105 // equal to null pointer, only reachable via direct call). 106 if (reloc.Type == R_WASM_TABLE_INDEX_SLEB || 107 reloc.Type == R_WASM_TABLE_INDEX_I32) { 108 auto *funcSym = cast<FunctionSymbol>(sym); 109 if (funcSym->hasTableIndex() && funcSym->getTableIndex() == 0) 110 continue; 111 } 112 113 enqueue(sym); 114 } 115 } 116 117 // Report garbage-collected sections. 118 if (config->printGcSections) { 119 for (const ObjFile *obj : symtab->objectFiles) { 120 for (InputChunk *c : obj->functions) 121 if (!c->live) 122 message("removing unused section " + toString(c)); 123 for (InputChunk *c : obj->segments) 124 if (!c->live) 125 message("removing unused section " + toString(c)); 126 for (InputGlobal *g : obj->globals) 127 if (!g->live) 128 message("removing unused section " + toString(g)); 129 for (InputEvent *e : obj->events) 130 if (!e->live) 131 message("removing unused section " + toString(e)); 132 } 133 for (InputChunk *c : symtab->syntheticFunctions) 134 if (!c->live) 135 message("removing unused section " + toString(c)); 136 for (InputGlobal *g : symtab->syntheticGlobals) 137 if (!g->live) 138 message("removing unused section " + toString(g)); 139 } 140 } 141