wasm/MarkLive.cpp

   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   if (!Config->GcSections)
  38     return;
  39
  40   LLVM_DEBUG(dbgs() << "markLive\n");
  41   SmallVector<InputChunk *, 256> Q;
  42
  43   auto Enqueue = [&](Symbol *Sym) {
  44     if (!Sym || Sym->isLive())
  45       return;
  46     LLVM_DEBUG(dbgs() << "markLive: " << Sym->getName() << "\n");
  47     Sym->markLive();
  48     if (InputChunk *Chunk = Sym->getChunk())
  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   // We need to preserve any exported symbol
  58   for (Symbol *Sym : Symtab->getSymbols())
  59     if (Sym->isExported())
  60       Enqueue(Sym);
  61
  62   // The ctor functions are all used in the synthetic __wasm_call_ctors
  63   // function, but since this function is created in-place it doesn't contain
  64   // relocations 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.Symbol));
  69   }
  70
  71   // Follow relocations to mark all reachable chunks.
  72   while (!Q.empty()) {
  73     InputChunk *C = Q.pop_back_val();
  74
  75     for (const WasmRelocation Reloc : C->getRelocations()) {
  76       if (Reloc.Type == R_WEBASSEMBLY_TYPE_INDEX_LEB)
  77         continue;
  78       Symbol *Sym = C->File->getSymbol(Reloc.Index);
  79
  80       // If the function has been assigned the special index zero in the table,
  81       // the relocation doesn't pull in the function body, since the function
  82       // won't actually go in the table (the runtime will trap attempts to call
  83       // that index, since we don't use it).  A function with a table index of
  84       // zero is only reachable via "call", not via "call_indirect".  The stub
  85       // functions used for weak-undefined symbols have this behaviour (compare
  86       // equal to null pointer, only reachable via direct call).
  87       if (Reloc.Type == R_WEBASSEMBLY_TABLE_INDEX_SLEB ||
  88           Reloc.Type == R_WEBASSEMBLY_TABLE_INDEX_I32) {
  89         FunctionSymbol *FuncSym = cast<FunctionSymbol>(Sym);
  90         if (FuncSym->hasTableIndex() && FuncSym->getTableIndex() == 0)
  91           continue;
  92       }
  93
  94       Enqueue(Sym);
  95     }
  96   }
  97
  98   // Report garbage-collected sections.
  99   if (Config->PrintGcSections) {
 100     for (const ObjFile *Obj : Symtab->ObjectFiles) {
 101       for (InputChunk *C : Obj->Functions)
 102         if (!C->Live)
 103           message("removing unused section " + toString(C));
 104       for (InputChunk *C : Obj->Segments)
 105         if (!C->Live)
 106           message("removing unused section " + toString(C));
 107       for (InputGlobal *G : Obj->Globals)
 108         if (!G->Live)
 109           message("removing unused section " + toString(G));
 110     }
 111     for (InputChunk *C : Symtab->SyntheticFunctions)
 112       if (!C->Live)
 113         message("removing unused section " + toString(C));
 114     for (InputGlobal *G : Symtab->SyntheticGlobals)
 115       if (!G->Live)
 116         message("removing unused section " + toString(G));
 117   }
 118 }