1 //===- MarkLive.cpp -------------------------------------------------------===// 2 // 3 // The LLVM Linker 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements --gc-sections, which is a feature to remove unused 11 // chunks from the output. Unused chunks are those that are not reachable from 12 // known root symbols or chunks. This feature is implemented as a mark-sweep 13 // garbage collector. 14 // 15 // Here's how it works. Each InputChunk has a "Live" bit. The bit is off by 16 // default. Starting with the GC-roots, visit all reachable chunks and set their 17 // Live bits. The Writer will then ignore chunks whose Live bits are off, so 18 // that such chunk are not appear in the output. 19 // 20 //===----------------------------------------------------------------------===// 21 22 #include "MarkLive.h" 23 #include "Config.h" 24 #include "InputChunks.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 using namespace lld; 34 using namespace lld::wasm; 35 36 void lld::wasm::markLive() { 37 LLVM_DEBUG(dbgs() << "markLive\n"); 38 SmallVector<InputChunk *, 256> Q; 39 40 auto Enqueue = [&](Symbol *Sym) { 41 if (!Sym || Sym->isLive()) 42 return; 43 LLVM_DEBUG(dbgs() << "markLive: " << Sym->getName() << "\n"); 44 Sym->markLive(); 45 if (Sym->SignatureMismatch) 46 error("function signature mismatch: " + Sym->getName()); 47 if (InputChunk *Chunk = Sym->getChunk()) 48 Q.push_back(Chunk); 49 }; 50 51 // Add GC root symbols. 52 if (!Config->Entry.empty()) 53 Enqueue(Symtab->find(Config->Entry)); 54 Enqueue(WasmSym::CallCtors); 55 56 // We export all defined, non-hidden symbols so they are all gc roots too 57 for (Symbol *Sym : Symtab->getSymbols()) 58 if (Sym->isDefined() && !Sym->isHidden()) 59 Enqueue(Sym); 60 61 // The ctor functions are all used in the synthetic __wasm_call_ctors 62 // function, but since this function is created in-place it doesn't contain 63 // relocations which mean we have to manually mark the ctors. 64 for (const ObjFile *Obj : Symtab->ObjectFiles) { 65 const WasmLinkingData &L = Obj->getWasmObj()->linkingData(); 66 for (const WasmInitFunc &F : L.InitFunctions) 67 Enqueue(Obj->getFunctionSymbol(F.Symbol)); 68 } 69 70 // Follow relocations to mark all reachable chunks. 71 while (!Q.empty()) { 72 InputChunk *C = Q.pop_back_val(); 73 74 for (const WasmRelocation Reloc : C->getRelocations()) { 75 if (Reloc.Type == R_WEBASSEMBLY_TYPE_INDEX_LEB) 76 continue; 77 Symbol *Sym = C->File->getSymbol(Reloc.Index); 78 79 // If the function has been assigned the special index zero in the table, 80 // the relocation doesn't pull in the function body, since the function 81 // won't actually go in the table (the runtime will trap attempts to call 82 // that index, since we don't use it). A function with a table index of 83 // zero is only reachable via "call", not via "call_indirect". The stub 84 // functions used for weak-undefined symbols have this behaviour (compare 85 // equal to null pointer, only reachable via direct call). 86 if (Reloc.Type == R_WEBASSEMBLY_TABLE_INDEX_SLEB || 87 Reloc.Type == R_WEBASSEMBLY_TABLE_INDEX_I32) { 88 FunctionSymbol *FuncSym = cast<FunctionSymbol>(Sym); 89 if (FuncSym->hasTableIndex() && FuncSym->getTableIndex() == 0) 90 continue; 91 } 92 93 Enqueue(Sym); 94 } 95 } 96 97 // Report garbage-collected sections. 98 if (Config->PrintGcSections) { 99 for (const ObjFile *Obj : Symtab->ObjectFiles) { 100 for (InputChunk *C : Obj->Functions) 101 if (!C->Live) 102 message("removing unused section " + toString(C)); 103 for (InputChunk *C : Obj->Segments) 104 if (!C->Live) 105 message("removing unused section " + toString(C)); 106 for (InputGlobal *G : Obj->Globals) 107 if (!G->Live) 108 message("removing unused section " + toString(G)); 109 } 110 for (InputChunk *C : Symtab->SyntheticFunctions) 111 if (!C->Live) 112 message("removing unused section " + toString(C)); 113 for (InputGlobal *G : Symtab->SyntheticGlobals) 114 if (!G->Live) 115 message("removing unused section " + toString(G)); 116 } 117 } 118