MarkLive.cpp revision 363496 
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#include "Chunks.h"
10#include "Symbols.h"
11#include "lld/Common/Timer.h"
12#include "llvm/ADT/STLExtras.h"
13#include <vector>
14
15namespace lld {
16namespace coff {
17
18static Timer gctimer("GC", Timer::root());
19
20// Set live bit on for each reachable chunk. Unmarked (unreachable)
21// COMDAT chunks will be ignored by Writer, so they will be excluded
22// from the final output.
23void markLive(ArrayRef<Chunk *> chunks) {
24  ScopedTimer t(gctimer);
25
26  // We build up a worklist of sections which have been marked as live. We only
27  // push into the worklist when we discover an unmarked section, and we mark
28  // as we push, so sections never appear twice in the list.
29  SmallVector<SectionChunk *, 256> worklist;
30
31  // COMDAT section chunks are dead by default. Add non-COMDAT chunks. Do not
32  // traverse DWARF sections. They are live, but they should not keep other
33  // sections alive.
34  for (Chunk *c : chunks)
35    if (auto *sc = dyn_cast<SectionChunk>(c))
36      if (sc->live && !sc->isDWARF())
37        worklist.push_back(sc);
38
39  auto enqueue = [&](SectionChunk *c) {
40    if (c->live)
41      return;
42    c->live = true;
43    worklist.push_back(c);
44  };
45
46  auto addSym = [&](Symbol *b) {
47    if (auto *sym = dyn_cast<DefinedRegular>(b))
48      enqueue(sym->getChunk());
49    else if (auto *sym = dyn_cast<DefinedImportData>(b))
50      sym->file->live = true;
51    else if (auto *sym = dyn_cast<DefinedImportThunk>(b))
52      sym->wrappedSym->file->live = sym->wrappedSym->file->thunkLive = true;
53  };
54
55  // Add GC root chunks.
56  for (Symbol *b : config->gcroot)
57    addSym(b);
58
59  while (!worklist.empty()) {
60    SectionChunk *sc = worklist.pop_back_val();
61    assert(sc->live && "We mark as live when pushing onto the worklist!");
62
63    // Mark all symbols listed in the relocation table for this section.
64    for (Symbol *b : sc->symbols())
65      if (b)
66        addSym(b);
67
68    // Mark associative sections if any.
69    for (SectionChunk &c : sc->children())
70      enqueue(&c);
71  }
72}
73
74}
75}
76