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 "InputElement.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
  33 namespace lld::wasm {
  34
  35 namespace {
  36
  37 class MarkLive {
  38 public:
  39   void run();
  40
  41 private:
  42   void enqueue(Symbol *sym);
  43   void enqueueInitFunctions(const ObjFile *sym);
  44   void mark();
  45   bool isCallCtorsLive();
  46
  47   // A list of chunks to visit.
  48   SmallVector<InputChunk *, 256> queue;
  49 };
  50
  51 } // namespace
  52
  53 void MarkLive::enqueue(Symbol *sym) {
  54   if (!sym || sym->isLive())
  55     return;
  56   LLVM_DEBUG(dbgs() << "markLive: " << sym->getName() << "\n");
  57
  58   InputFile *file = sym->getFile();
  59   bool needInitFunctions = file && !file->isLive() && sym->isDefined();
  60
  61   sym->markLive();
  62
  63   // Mark ctor functions in the object that defines this symbol live.
  64   // The ctor functions are all referenced by the synthetic callCtors
  65   // function. However, this function does not contain relocations so we
  66   // have to manually mark the ctors as live.
  67   if (needInitFunctions)
  68     enqueueInitFunctions(cast<ObjFile>(file));
  69
  70   if (InputChunk *chunk = sym->getChunk())
  71     queue.push_back(chunk);
  72 }
  73
  74 // The ctor functions are all referenced by the synthetic callCtors
  75 // function.  However, this function does not contain relocations so we
  76 // have to manually mark the ctors as live.
  77 void MarkLive::enqueueInitFunctions(const ObjFile *obj) {
  78   const WasmLinkingData &l = obj->getWasmObj()->linkingData();
  79   for (const WasmInitFunc &f : l.InitFunctions) {
  80     auto *initSym = obj->getFunctionSymbol(f.Symbol);
  81     if (!initSym->isDiscarded())
  82       enqueue(initSym);
  83   }
  84 }
  85
  86 void MarkLive::run() {
  87   // Add GC root symbols.
  88   if (!config->entry.empty())
  89     enqueue(symtab->find(config->entry));
  90
  91   // We need to preserve any no-strip or exported symbol
  92   for (Symbol *sym : symtab->symbols())
  93     if (sym->isNoStrip() || sym->isExported())
  94       enqueue(sym);
  95
  96   if (WasmSym::callDtors)
  97     enqueue(WasmSym::callDtors);
  98
  99   // Enqueue constructors in objects explicitly live from the command-line.
 100   for (const ObjFile *obj : symtab->objectFiles)
 101     if (obj->isLive())
 102       enqueueInitFunctions(obj);
 103
 104   mark();
 105
 106   // If we have any non-discarded init functions, mark `__wasm_call_ctors` as
 107   // live so that we assign it an index and call it.
 108   if (isCallCtorsLive())
 109     WasmSym::callCtors->markLive();
 110 }
 111
 112 void MarkLive::mark() {
 113   // Follow relocations to mark all reachable chunks.
 114   while (!queue.empty()) {
 115     InputChunk *c = queue.pop_back_val();
 116
 117     for (const WasmRelocation reloc : c->getRelocations()) {
 118       if (reloc.Type == R_WASM_TYPE_INDEX_LEB)
 119         continue;
 120       Symbol *sym = c->file->getSymbol(reloc.Index);
 121
 122       // If the function has been assigned the special index zero in the table,
 123       // the relocation doesn't pull in the function body, since the function
 124       // won't actually go in the table (the runtime will trap attempts to call
 125       // that index, since we don't use it).  A function with a table index of
 126       // zero is only reachable via "call", not via "call_indirect".  The stub
 127       // functions used for weak-undefined symbols have this behaviour (compare
 128       // equal to null pointer, only reachable via direct call).
 129       if (reloc.Type == R_WASM_TABLE_INDEX_SLEB ||
 130           reloc.Type == R_WASM_TABLE_INDEX_SLEB64 ||
 131           reloc.Type == R_WASM_TABLE_INDEX_I32 ||
 132           reloc.Type == R_WASM_TABLE_INDEX_I64) {
 133         auto *funcSym = cast<FunctionSymbol>(sym);
 134         if (funcSym->isStub)
 135           continue;
 136       }
 137
 138       enqueue(sym);
 139     }
 140   }
 141 }
 142
 143 void markLive() {
 144   if (!config->gcSections)
 145     return;
 146
 147   LLVM_DEBUG(dbgs() << "markLive\n");
 148
 149   MarkLive marker;
 150   marker.run();
 151
 152   // Report garbage-collected sections.
 153   if (config->printGcSections) {
 154     for (const ObjFile *obj : symtab->objectFiles) {
 155       for (InputChunk *c : obj->functions)
 156         if (!c->live)
 157           message("removing unused section " + toString(c));
 158       for (InputChunk *c : obj->segments)
 159         if (!c->live)
 160           message("removing unused section " + toString(c));
 161       for (InputGlobal *g : obj->globals)
 162         if (!g->live)
 163           message("removing unused section " + toString(g));
 164       for (InputTag *t : obj->tags)
 165         if (!t->live)
 166           message("removing unused section " + toString(t));
 167       for (InputTable *t : obj->tables)
 168         if (!t->live)
 169           message("removing unused section " + toString(t));
 170     }
 171     for (InputChunk *c : symtab->syntheticFunctions)
 172       if (!c->live)
 173         message("removing unused section " + toString(c));
 174     for (InputGlobal *g : symtab->syntheticGlobals)
 175       if (!g->live)
 176         message("removing unused section " + toString(g));
 177     for (InputTable *t : symtab->syntheticTables)
 178       if (!t->live)
 179         message("removing unused section " + toString(t));
 180   }
 181 }
 182
 183 bool MarkLive::isCallCtorsLive() {
 184   // In a reloctable link, we don't call `__wasm_call_ctors`.
 185   if (config->relocatable)
 186     return false;
 187
 188   // In Emscripten-style PIC, we call `__wasm_call_ctors` which calls
 189   // `__wasm_apply_data_relocs`.
 190   if (config->isPic)
 191     return true;
 192
 193   // If there are any init functions, mark `__wasm_call_ctors` live so that
 194   // it can call them.
 195   for (const ObjFile *file : symtab->objectFiles) {
 196     const WasmLinkingData &l = file->getWasmObj()->linkingData();
 197     for (const WasmInitFunc &f : l.InitFunctions) {
 198       auto *sym = file->getFunctionSymbol(f.Symbol);
 199       if (!sym->isDiscarded() && sym->isLive())
 200         return true;
 201     }
 202   }
 203
 204   return false;
 205 }
 206
 207 } // namespace lld::wasm