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 for (const ObjFile *Obj : Symtab->ObjectFiles) { 54 const WasmLinkingData &L = Obj->getWasmObj()->linkingData(); 55 for (const WasmInitFunc &F : L.InitFunctions) { 56 auto* InitSym = Obj->getFunctionSymbol(F.Symbol); 57 if (!InitSym->isDiscarded()) 58 Enqueue(InitSym); 59 } 60 } 61 } 62 }; 63 64 // Add GC root symbols. 65 if (!Config->Entry.empty()) 66 Enqueue(Symtab->find(Config->Entry)); 67 68 // We need to preserve any exported symbol 69 for (Symbol *Sym : Symtab->getSymbols()) 70 if (Sym->isExported()) 71 Enqueue(Sym); 72 73 // For relocatable output, we need to preserve all the ctor functions 74 if (Config->Relocatable) { 75 for (const ObjFile *Obj : Symtab->ObjectFiles) { 76 const WasmLinkingData &L = Obj->getWasmObj()->linkingData(); 77 for (const WasmInitFunc &F : L.InitFunctions) 78 Enqueue(Obj->getFunctionSymbol(F.Symbol)); 79 } 80 } 81 82 if (Config->Pic) { 83 Enqueue(WasmSym::CallCtors); 84 Enqueue(WasmSym::ApplyRelocs); 85 } 86 87 // Follow relocations to mark all reachable chunks. 88 while (!Q.empty()) { 89 InputChunk *C = Q.pop_back_val(); 90 91 for (const WasmRelocation Reloc : C->getRelocations()) { 92 if (Reloc.Type == R_WASM_TYPE_INDEX_LEB) 93 continue; 94 Symbol *Sym = C->File->getSymbol(Reloc.Index); 95 96 // If the function has been assigned the special index zero in the table, 97 // the relocation doesn't pull in the function body, since the function 98 // won't actually go in the table (the runtime will trap attempts to call 99 // that index, since we don't use it). A function with a table index of 100 // zero is only reachable via "call", not via "call_indirect". The stub 101 // functions used for weak-undefined symbols have this behaviour (compare 102 // equal to null pointer, only reachable via direct call). 103 if (Reloc.Type == R_WASM_TABLE_INDEX_SLEB || 104 Reloc.Type == R_WASM_TABLE_INDEX_I32) { 105 auto *FuncSym = cast<FunctionSymbol>(Sym); 106 if (FuncSym->hasTableIndex() && FuncSym->getTableIndex() == 0) 107 continue; 108 } 109 110 Enqueue(Sym); 111 } 112 } 113 114 // Report garbage-collected sections. 115 if (Config->PrintGcSections) { 116 for (const ObjFile *Obj : Symtab->ObjectFiles) { 117 for (InputChunk *C : Obj->Functions) 118 if (!C->Live) 119 message("removing unused section " + toString(C)); 120 for (InputChunk *C : Obj->Segments) 121 if (!C->Live) 122 message("removing unused section " + toString(C)); 123 for (InputGlobal *G : Obj->Globals) 124 if (!G->Live) 125 message("removing unused section " + toString(G)); 126 for (InputEvent *E : Obj->Events) 127 if (!E->Live) 128 message("removing unused section " + toString(E)); 129 } 130 for (InputChunk *C : Symtab->SyntheticFunctions) 131 if (!C->Live) 132 message("removing unused section " + toString(C)); 133 for (InputGlobal *G : Symtab->SyntheticGlobals) 134 if (!G->Live) 135 message("removing unused section " + toString(G)); 136 } 137 } 138