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 "SymbolTable.h" 26 #include "Symbols.h" 27 28 #define DEBUG_TYPE "lld" 29 30 using namespace llvm; 31 using namespace llvm::wasm; 32 using namespace lld; 33 using namespace lld::wasm; 34 35 void lld::wasm::markLive() { 36 if (!Config->GcSections) 37 return; 38 39 DEBUG(dbgs() << "markLive\n"); 40 SmallVector<InputChunk *, 256> Q; 41 42 auto Enqueue = [&](Symbol *Sym) { 43 if (!Sym) 44 return; 45 InputChunk *Chunk = Sym->getChunk(); 46 if (!Chunk || Chunk->Live) 47 return; 48 Chunk->Live = true; 49 Q.push_back(Chunk); 50 }; 51 52 // Add GC root symbols. 53 if (!Config->Entry.empty()) 54 Enqueue(Symtab->find(Config->Entry)); 55 Enqueue(WasmSym::CallCtors); 56 57 // By default we export all non-hidden, so they are gc roots too 58 for (Symbol *Sym : Symtab->getSymbols()) 59 if (!Sym->isHidden()) 60 Enqueue(Sym); 61 62 // The ctor fuctions are all used the synthetic __wasm_call_ctors function, 63 // but since this function is created in-place it doesn't contain reloctations 64 // which mean we have to manually mark the ctors. 65 for (const ObjFile *Obj : Symtab->ObjectFiles) { 66 const WasmLinkingData &L = Obj->getWasmObj()->linkingData(); 67 for (const WasmInitFunc &F : L.InitFunctions) 68 Enqueue(Obj->getFunctionSymbol(F.FunctionIndex)); 69 } 70 71 auto EnqueueSuccessors = [Enqueue](InputChunk &Chunk) { 72 for (const WasmRelocation Reloc : Chunk.getRelocations()) { 73 switch (Reloc.Type) { 74 case R_WEBASSEMBLY_FUNCTION_INDEX_LEB: 75 case R_WEBASSEMBLY_TABLE_INDEX_I32: 76 case R_WEBASSEMBLY_TABLE_INDEX_SLEB: 77 Enqueue(Chunk.File->getFunctionSymbol(Reloc.Index)); 78 break; 79 case R_WEBASSEMBLY_GLOBAL_INDEX_LEB: 80 case R_WEBASSEMBLY_MEMORY_ADDR_LEB: 81 case R_WEBASSEMBLY_MEMORY_ADDR_SLEB: 82 case R_WEBASSEMBLY_MEMORY_ADDR_I32: 83 Enqueue(Chunk.File->getGlobalSymbol(Reloc.Index)); 84 break; 85 } 86 } 87 }; 88 89 while (!Q.empty()) 90 EnqueueSuccessors(*Q.pop_back_val()); 91 92 // Report garbage-collected sections. 93 if (Config->PrintGcSections) { 94 auto CheckChunk = [](const InputChunk *C) { 95 if (!C->Live) 96 message("removing unused section '" + C->getName() + "' in file '" + 97 C->getFileName() + "'"); 98 }; 99 100 for (const ObjFile *Obj : Symtab->ObjectFiles) { 101 for (InputChunk *C : Obj->Functions) 102 CheckChunk(C); 103 for (InputChunk *C : Obj->Segments) 104 CheckChunk(C); 105 } 106 } 107 } 108