lld/wasm/MarkLive.cpp

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