diff --git a/lld/MachO/MarkLive.cpp b/lld/MachO/MarkLive.cpp --- a/lld/MachO/MarkLive.cpp +++ b/lld/MachO/MarkLive.cpp @@ -21,44 +21,96 @@ using namespace llvm; using namespace llvm::MachO; -// Set live bit on for each reachable chunk. Unmarked (unreachable) -// InputSections will be ignored by Writer, so they will be excluded -// from the final output. -void markLive() { - TimeTraceScope timeScope("markLive"); - - // We build up a worklist of sections which have been marked as live. We only - // push into the worklist when we discover an unmarked section, and we mark - // as we push, so sections never appear twice in the list. - // Literal sections cannot contain references to other sections, so we only - // store ConcatInputSections in our worklist. +class MarkLive { +public: + void enqueue(InputSection *isec, uint64_t off); + void addSym(Symbol *s); + void markTransitively(); + +private: + // We build up a worklist of sections which have been marked as live. We + // only push into the worklist when we discover an unmarked section, and we + // mark as we push, so sections never appear twice in the list. Literal + // sections cannot contain references to other sections, so we only store + // ConcatInputSections in our worklist. SmallVector worklist; +}; + +void MarkLive::enqueue(InputSection *isec, uint64_t off) { + if (isec->isLive(off)) + return; + isec->markLive(off); + if (auto s = dyn_cast(isec)) { + assert(!s->isCoalescedWeak()); + worklist.push_back(s); + } +} + +void MarkLive::addSym(Symbol *s) { + if (s->used) + return; + s->used = true; + if (auto *d = dyn_cast(s)) { + if (d->isec) + enqueue(d->isec, d->value); + if (d->unwindEntry) + enqueue(d->unwindEntry, 0); + } +} + +void MarkLive::markTransitively() { + do { + // Mark things reachable from GC roots as live. + while (!worklist.empty()) { + ConcatInputSection *s = worklist.pop_back_val(); + assert(s->live && "We mark as live when pushing onto the worklist!"); - auto enqueue = [&](InputSection *isec, uint64_t off) { - if (isec->isLive(off)) - return; - isec->markLive(off); - if (auto s = dyn_cast(isec)) { - assert(!s->isCoalescedWeak()); - worklist.push_back(s); + // Mark all symbols listed in the relocation table for this section. + for (const Reloc &r : s->relocs) { + if (auto *s = r.referent.dyn_cast()) + addSym(s); + else + enqueue(r.referent.get(), r.addend); + } + for (Defined *d : s->symbols) + addSym(d); } - }; - - auto addSym = [&](Symbol *s) { - if (s->used) - return; - s->used = true; - if (auto *d = dyn_cast(s)) { - if (d->isec) - enqueue(d->isec, d->value); - if (d->unwindEntry) - enqueue(d->unwindEntry, 0); + + // S_ATTR_LIVE_SUPPORT sections are live if they point _to_ a live + // section. Process them in a second pass. + for (ConcatInputSection *isec : inputSections) { + // FIXME: Check if copying all S_ATTR_LIVE_SUPPORT sections into a + // separate vector and only walking that here is faster. + if (!(isec->getFlags() & S_ATTR_LIVE_SUPPORT) || isec->live) + continue; + + for (const Reloc &r : isec->relocs) { + bool referentLive; + if (auto *s = r.referent.dyn_cast()) + referentLive = s->isLive(); + else + referentLive = r.referent.get()->isLive(r.addend); + if (referentLive) + enqueue(isec, 0); + } } - }; + // S_ATTR_LIVE_SUPPORT could have marked additional sections live, + // which in turn could mark additional S_ATTR_LIVE_SUPPORT sections live. + // Iterate. In practice, the second iteration won't mark additional + // S_ATTR_LIVE_SUPPORT sections live. + } while (!worklist.empty()); +} + +// Set live bit on for each reachable chunk. Unmarked (unreachable) +// InputSections will be ignored by Writer, so they will be excluded +// from the final output. +void markLive() { + TimeTraceScope timeScope("markLive"); + MarkLive marker; // Add GC roots. if (config->entry) - addSym(config->entry); + marker.addSym(config->entry); for (Symbol *sym : symtab->getSymbols()) { if (auto *defined = dyn_cast(sym)) { // -exported_symbol(s_list) @@ -69,17 +121,18 @@ // explicitUndefineds code below would handle this automatically. assert(!defined->privateExtern && "should have been rejected by driver"); - addSym(defined); + marker.addSym(defined); continue; } // public symbols explicitly marked .no_dead_strip if (defined->referencedDynamically || defined->noDeadStrip) { - addSym(defined); + marker.addSym(defined); continue; } - // FIXME: When we implement these flags, make symbols from them GC roots: + // FIXME: When we implement these flags, make symbols from them GC + // roots: // * -reexported_symbol(s_list) // * -alias(-list) // * -init @@ -89,80 +142,40 @@ bool externsAreRoots = config->outputType != MH_EXECUTE || config->exportDynamic; if (externsAreRoots && !defined->privateExtern) { - addSym(defined); + marker.addSym(defined); continue; } } } // -u symbols for (Symbol *sym : config->explicitUndefineds) - addSym(sym); + marker.addSym(sym); // local symbols explicitly marked .no_dead_strip for (const InputFile *file : inputFiles) if (auto *objFile = dyn_cast(file)) for (Symbol *sym : objFile->symbols) if (auto *defined = dyn_cast_or_null(sym)) if (!defined->isExternal() && defined->noDeadStrip) - addSym(defined); + marker.addSym(defined); if (auto *stubBinder = dyn_cast_or_null(symtab->find("dyld_stub_binder"))) - addSym(stubBinder); + marker.addSym(stubBinder); for (ConcatInputSection *isec : inputSections) { // Sections marked no_dead_strip if (isec->getFlags() & S_ATTR_NO_DEAD_STRIP) { - enqueue(isec, 0); + marker.enqueue(isec, 0); continue; } // mod_init_funcs, mod_term_funcs sections if (sectionType(isec->getFlags()) == S_MOD_INIT_FUNC_POINTERS || sectionType(isec->getFlags()) == S_MOD_TERM_FUNC_POINTERS) { - enqueue(isec, 0); + marker.enqueue(isec, 0); continue; } } - do { - // Mark things reachable from GC roots as live. - while (!worklist.empty()) { - ConcatInputSection *s = worklist.pop_back_val(); - assert(s->live && "We mark as live when pushing onto the worklist!"); - - // Mark all symbols listed in the relocation table for this section. - for (const Reloc &r : s->relocs) { - if (auto *s = r.referent.dyn_cast()) - addSym(s); - else - enqueue(r.referent.get(), r.addend); - } - for (Defined *d : s->symbols) - addSym(d); - } - - // S_ATTR_LIVE_SUPPORT sections are live if they point _to_ a live section. - // Process them in a second pass. - for (ConcatInputSection *isec : inputSections) { - // FIXME: Check if copying all S_ATTR_LIVE_SUPPORT sections into a - // separate vector and only walking that here is faster. - if (!(isec->getFlags() & S_ATTR_LIVE_SUPPORT) || isec->live) - continue; - - for (const Reloc &r : isec->relocs) { - bool referentLive; - if (auto *s = r.referent.dyn_cast()) - referentLive = s->isLive(); - else - referentLive = r.referent.get()->isLive(r.addend); - if (referentLive) - enqueue(isec, 0); - } - } - - // S_ATTR_LIVE_SUPPORT could have marked additional sections live, - // which in turn could mark additional S_ATTR_LIVE_SUPPORT sections live. - // Iterate. In practice, the second iteration won't mark additional - // S_ATTR_LIVE_SUPPORT sections live. - } while (!worklist.empty()); + marker.markTransitively(); } } // namespace macho