xref: /freebsd/contrib/llvm-project/lld/MachO/MarkLive.cpp (revision 924226fba12cc9a228c73b956e1b7fa24c60b055)
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 "MarkLive.h"
10 #include "Config.h"
11 #include "OutputSegment.h"
12 #include "SymbolTable.h"
13 #include "Symbols.h"
14 #include "UnwindInfoSection.h"
15 #include "mach-o/compact_unwind_encoding.h"
16 #include "llvm/Support/TimeProfiler.h"
17 
18 namespace lld {
19 namespace macho {
20 
21 using namespace llvm;
22 using namespace llvm::MachO;
23 
24 // Set live bit on for each reachable chunk. Unmarked (unreachable)
25 // InputSections will be ignored by Writer, so they will be excluded
26 // from the final output.
27 void markLive() {
28   TimeTraceScope timeScope("markLive");
29 
30   // We build up a worklist of sections which have been marked as live. We only
31   // push into the worklist when we discover an unmarked section, and we mark
32   // as we push, so sections never appear twice in the list.
33   // Literal sections cannot contain references to other sections, so we only
34   // store ConcatInputSections in our worklist.
35   SmallVector<ConcatInputSection *, 256> worklist;
36 
37   auto enqueue = [&](InputSection *isec, uint64_t off) {
38     if (isec->isLive(off))
39       return;
40     isec->markLive(off);
41     if (auto s = dyn_cast<ConcatInputSection>(isec)) {
42       assert(!s->isCoalescedWeak());
43       worklist.push_back(s);
44     }
45   };
46 
47   auto addSym = [&](Symbol *s) {
48     if (s->used)
49       return;
50     s->used = true;
51     if (auto *d = dyn_cast<Defined>(s)) {
52       if (d->isec)
53         enqueue(d->isec, d->value);
54       if (d->unwindEntry)
55         enqueue(d->unwindEntry, 0);
56     }
57   };
58 
59   // Add GC roots.
60   if (config->entry)
61     addSym(config->entry);
62   for (Symbol *sym : symtab->getSymbols()) {
63     if (auto *defined = dyn_cast<Defined>(sym)) {
64       // -exported_symbol(s_list)
65       if (!config->exportedSymbols.empty() &&
66           config->exportedSymbols.match(defined->getName())) {
67         // FIXME: Instead of doing this here, maybe the Driver code doing
68         // the matching should add them to explicitUndefineds? Then the
69         // explicitUndefineds code below would handle this automatically.
70         assert(!defined->privateExtern &&
71                "should have been rejected by driver");
72         addSym(defined);
73         continue;
74       }
75 
76       // public symbols explicitly marked .no_dead_strip
77       if (defined->referencedDynamically || defined->noDeadStrip) {
78         addSym(defined);
79         continue;
80       }
81 
82       // FIXME: When we implement these flags, make symbols from them GC roots:
83       // * -reexported_symbol(s_list)
84       // * -alias(-list)
85       // * -init
86 
87       // In dylibs and bundles and in executables with -export_dynamic,
88       // all external functions are GC roots.
89       bool externsAreRoots =
90           config->outputType != MH_EXECUTE || config->exportDynamic;
91       if (externsAreRoots && !defined->privateExtern) {
92         addSym(defined);
93         continue;
94       }
95     }
96   }
97   // -u symbols
98   for (Symbol *sym : config->explicitUndefineds)
99     addSym(sym);
100   // local symbols explicitly marked .no_dead_strip
101   for (const InputFile *file : inputFiles)
102     if (auto *objFile = dyn_cast<ObjFile>(file))
103       for (Symbol *sym : objFile->symbols)
104         if (auto *defined = dyn_cast_or_null<Defined>(sym))
105           if (!defined->isExternal() && defined->noDeadStrip)
106             addSym(defined);
107   if (auto *stubBinder =
108           dyn_cast_or_null<DylibSymbol>(symtab->find("dyld_stub_binder")))
109     addSym(stubBinder);
110   for (ConcatInputSection *isec : inputSections) {
111     // Sections marked no_dead_strip
112     if (isec->getFlags() & S_ATTR_NO_DEAD_STRIP) {
113       enqueue(isec, 0);
114       continue;
115     }
116 
117     // mod_init_funcs, mod_term_funcs sections
118     if (sectionType(isec->getFlags()) == S_MOD_INIT_FUNC_POINTERS ||
119         sectionType(isec->getFlags()) == S_MOD_TERM_FUNC_POINTERS) {
120       enqueue(isec, 0);
121       continue;
122     }
123   }
124 
125   do {
126     // Mark things reachable from GC roots as live.
127     while (!worklist.empty()) {
128       ConcatInputSection *s = worklist.pop_back_val();
129       assert(s->live && "We mark as live when pushing onto the worklist!");
130 
131       // Mark all symbols listed in the relocation table for this section.
132       for (const Reloc &r : s->relocs) {
133         if (auto *s = r.referent.dyn_cast<Symbol *>())
134           addSym(s);
135         else
136           enqueue(r.referent.get<InputSection *>(), r.addend);
137       }
138       for (Defined *d : s->symbols)
139         addSym(d);
140     }
141 
142     // S_ATTR_LIVE_SUPPORT sections are live if they point _to_ a live section.
143     // Process them in a second pass.
144     for (ConcatInputSection *isec : inputSections) {
145       // FIXME: Check if copying all S_ATTR_LIVE_SUPPORT sections into a
146       // separate vector and only walking that here is faster.
147       if (!(isec->getFlags() & S_ATTR_LIVE_SUPPORT) || isec->live)
148         continue;
149 
150       for (const Reloc &r : isec->relocs) {
151         bool referentLive;
152         if (auto *s = r.referent.dyn_cast<Symbol *>())
153           referentLive = s->isLive();
154         else
155           referentLive = r.referent.get<InputSection *>()->isLive(r.addend);
156         if (referentLive)
157           enqueue(isec, 0);
158       }
159     }
160 
161     // S_ATTR_LIVE_SUPPORT could have marked additional sections live,
162     // which in turn could mark additional S_ATTR_LIVE_SUPPORT sections live.
163     // Iterate. In practice, the second iteration won't mark additional
164     // S_ATTR_LIVE_SUPPORT sections live.
165   } while (!worklist.empty());
166 }
167 
168 } // namespace macho
169 } // namespace lld
170