https://github.com/int3 updated https://github.com/llvm/llvm-project/pull/240243
>From e094f27a8baf81e96bd31698870ac52bfd422f4c Mon Sep 17 00:00:00 2001 From: Jez Ng <[email protected]> Date: Sun, 8 Nov 2026 01:12:22 -0800 Subject: [PATCH] [lld-macho] Mark live sections and symbols in parallel --- lld/MachO/InputSection.cpp | 13 ++- lld/MachO/InputSection.h | 24 ++++- lld/MachO/MarkLive.cpp | 181 +++++++++++++++++++++++++------------ lld/MachO/Options.td | 3 +- lld/MachO/Symbols.h | 2 +- lld/test/MachO/why-live.s | 24 ++--- 6 files changed, 164 insertions(+), 83 deletions(-) diff --git a/lld/MachO/InputSection.cpp b/lld/MachO/InputSection.cpp index ebbe5ca5006cf0..1d8bbdc1f88fef 100644 --- a/lld/MachO/InputSection.cpp +++ b/lld/MachO/InputSection.cpp @@ -328,8 +328,8 @@ StringPiece &CStringInputSection::getStringPiece(uint64_t off) { if (off >= data.size()) fatal(toString(this) + ": offset is outside the section"); - auto it = - partition_point(pieces, [=](StringPiece p) { return p.inSecOff <= off; }); + auto it = partition_point( + pieces, [=](const StringPiece &p) { return p.inSecOff <= off; }); return it[-1]; } @@ -341,8 +341,8 @@ size_t CStringInputSection::getStringPieceIndex(uint64_t off) const { if (off >= data.size()) fatal(toString(this) + ": offset is outside the section"); - auto it = - partition_point(pieces, [=](StringPiece p) { return p.inSecOff <= off; }); + auto it = partition_point( + pieces, [=](const StringPiece &p) { return p.inSecOff <= off; }); return std::distance(pieces.begin(), it) - 1; } @@ -370,7 +370,10 @@ WordLiteralInputSection::WordLiteralInputSection(const Section §ion, llvm_unreachable("invalid literal section type"); } - live.resize(data.size() >> power2LiteralSize, !config->deadStrip); + size_t numLiterals = data.size() >> power2LiteralSize; + live = std::make_unique<std::atomic<bool>[]>(numLiterals); + if (!config->deadStrip) + std::fill_n(live.get(), numLiterals, true); } uint64_t WordLiteralInputSection::getOffset(uint64_t off) const { diff --git a/lld/MachO/InputSection.h b/lld/MachO/InputSection.h index 5a58bdc099ede4..349bf1393a3121 100644 --- a/lld/MachO/InputSection.h +++ b/lld/MachO/InputSection.h @@ -16,10 +16,13 @@ #include "lld/Common/LLVM.h" #include "lld/Common/Memory.h" #include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/BitVector.h" #include "llvm/ADT/CachedHashString.h" #include "llvm/ADT/TinyPtrVector.h" #include "llvm/BinaryFormat/MachO.h" +#include "llvm/Support/SwapByteOrder.h" + +#include <atomic> +#include <memory> namespace lld { namespace macho { @@ -190,6 +193,17 @@ struct StringPiece { StringPiece(uint64_t off, uint32_t hash) : inSecOff(off), live(!config->deadStrip), hash(hash) {} + + // Marks the piece live; safe to call from several threads at once. No atomic + // OR is needed: while markLive runs, `hash` does not change and `live` only + // goes from false to true, so threads racing here all store the same value. + void markLive() { + auto *word = reinterpret_cast<std::atomic<uint32_t> *>(&inSecOff + 1); + constexpr uint32_t liveBit = llvm::sys::IsBigEndianHost ? (1U << 31) : 1U; + uint32_t w = word->load(std::memory_order_relaxed); + if (!(w & liveBit)) + word->store(w | liveBit, std::memory_order_relaxed); + } }; static_assert(sizeof(StringPiece) == 16, "StringPiece is too big!"); @@ -213,7 +227,7 @@ class CStringInputSection final : public InputSection { uint64_t getOffset(uint64_t off) const override; bool isLive(uint64_t off) const override { return getStringPiece(off).live; } - void markLive(uint64_t off) override { getStringPiece(off).live = true; } + void markLive(uint64_t off) override { getStringPiece(off).markLive(); } // Find the StringPiece that contains this offset. StringPiece &getStringPiece(uint64_t off); const StringPiece &getStringPiece(uint64_t off) const; @@ -259,10 +273,10 @@ class WordLiteralInputSection final : public InputSection { uint32_t align); uint64_t getOffset(uint64_t off) const override; bool isLive(uint64_t off) const override { - return live[off >> power2LiteralSize]; + return live[off >> power2LiteralSize].load(std::memory_order_relaxed); } void markLive(uint64_t off) override { - live[off >> power2LiteralSize] = true; + live[off >> power2LiteralSize].store(true, std::memory_order_relaxed); } static bool classof(const InputSection *isec) { @@ -272,7 +286,7 @@ class WordLiteralInputSection final : public InputSection { private: unsigned power2LiteralSize; // The liveness of data[off] is tracked by live[off >> power2LiteralSize]. - llvm::BitVector live; + std::unique_ptr<std::atomic<bool>[]> live; }; inline uint8_t sectionType(uint32_t flags) { diff --git a/lld/MachO/MarkLive.cpp b/lld/MachO/MarkLive.cpp index cf348cb22bbf4a..924ba94ad3aef3 100644 --- a/lld/MachO/MarkLive.cpp +++ b/lld/MachO/MarkLive.cpp @@ -15,8 +15,11 @@ #include "UnwindInfoSection.h" #include "lld/Common/ErrorHandler.h" +#include "llvm/Support/Parallel.h" #include "llvm/Support/TimeProfiler.h" +#include <mutex> + namespace lld::macho { using namespace llvm; @@ -41,6 +44,18 @@ class MarkLive { virtual ~MarkLive() = default; }; +// Sets `flag` and returns true if no other thread set it first. C++17 has no +// std::atomic_ref, so the plain bool is accessed as an atomic. +static bool tryClaim(bool &flag) { + auto &atomicFlag = reinterpret_cast<std::atomic<bool> &>(flag); + // Most claims find the flag already set, and the load lets those skip the + // more expensive atomic exchange. + return !atomicFlag.load(std::memory_order_relaxed) && + !atomicFlag.exchange(true, std::memory_order_relaxed); +} + +// Marks liveness on as many threads as are available. -why_live output is +// deterministic only with --threads=1. template <bool RecordWhyLive> class MarkLiveImpl : public MarkLive { public: // -why_live is a rarely used option, so we don't want support for that flag @@ -49,41 +64,49 @@ template <bool RecordWhyLive> class MarkLiveImpl : public MarkLive { // from needless allocations and pointer indirections. using WorklistEntry = std::conditional_t<RecordWhyLive, WhyLiveEntry, InputSection>; + using Worklist = SmallVector<WorklistEntry *, 0>; void enqueue(InputSection *isec, uint64_t off) override { - enqueue(isec, off, nullptr); + enqueue(isec, off, nullptr, nextLevel); } - void addSym(Symbol *s) override { addSym(s, nullptr); } + void addSym(Symbol *s) override { addSym(s, nullptr, nextLevel); } void markTransitively() override; private: - void enqueue(InputSection *isec, uint64_t off, const WorklistEntry *prev); - // Most calls find `s` already used, so keep that check out from behind a + // Several threads call these at once, each passing its own worklist to + // receive the sections it claims. + void enqueue(InputSection *isec, uint64_t off, const WorklistEntry *prev, + Worklist &worklist) const; + // Most calls find `s` already claimed, so keep that check out from behind a // call. - LLVM_ATTRIBUTE_ALWAYS_INLINE void addSym(Symbol *s, - const WorklistEntry *prev); - void visitSymbol(Symbol *s, const WorklistEntry *prev); + LLVM_ATTRIBUTE_ALWAYS_INLINE void addSym(Symbol *s, const WorklistEntry *prev, + Worklist &worklist) const; + void visitSymbol(Symbol *s, const WorklistEntry *prev, + Worklist &worklist) const; + void visit(WorklistEntry *entry, Worklist &worklist) const; + void drain(); const InputSection *getInputSection(const WorklistEntry *) const; WorklistEntry *makeEntry(InputSection *, const WorklistEntry *prev) const; - // 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<WorklistEntry *, 256> worklist; + // Sections that have been marked live and that the next level of drain() will + // visit. Literal sections cannot contain references to other sections, so we + // only store ConcatInputSections here. + Worklist nextLevel; }; +// Marks `isec` (at `off`) live. Only the thread whose claim succeeds queues a +// section. template <bool RecordWhyLive> -void MarkLiveImpl<RecordWhyLive>::enqueue( - InputSection *isec, uint64_t off, - const typename MarkLiveImpl<RecordWhyLive>::WorklistEntry *prev) { - if (isec->isLive(off)) - return; - isec->markLive(off); - if (auto s = dyn_cast<ConcatInputSection>(isec)) { +void MarkLiveImpl<RecordWhyLive>::enqueue(InputSection *isec, uint64_t off, + const WorklistEntry *prev, + Worklist &worklist) const { + if (auto *s = dyn_cast<ConcatInputSection>(isec)) { + if (!tryClaim(s->live)) + return; assert(!s->isCoalescedWeak()); worklist.push_back(makeEntry(s, prev)); + } else { + isec->markLive(off); } } @@ -103,32 +126,90 @@ static void printWhyLive(const Symbol *s, const WhyLiveEntry *prev) { } template <bool RecordWhyLive> -void MarkLiveImpl<RecordWhyLive>::addSym( - Symbol *s, - const typename MarkLiveImpl<RecordWhyLive>::WorklistEntry *prev) { - if (s->used) - return; - s->used = true; - visitSymbol(s, prev); +void MarkLiveImpl<RecordWhyLive>::addSym(Symbol *s, const WorklistEntry *prev, + Worklist &worklist) const { + if (tryClaim(s->used)) + visitSymbol(s, prev, worklist); } -// Marks what `s` keeps alive. This is separate from addSym() because the -// class-stub edge makes it recursive, and GCC won't always-inline a function -// that calls itself. +// Marks what `s` keeps alive. Called by the thread that claimed `s`. This is +// separate from addSym() because the class-stub edge makes it recursive, and +// GCC won't always-inline a function that calls itself. template <bool RecordWhyLive> -void MarkLiveImpl<RecordWhyLive>::visitSymbol( - Symbol *s, - const typename MarkLiveImpl<RecordWhyLive>::WorklistEntry *prev) { +void MarkLiveImpl<RecordWhyLive>::visitSymbol(Symbol *s, + const WorklistEntry *prev, + Worklist &worklist) const { if constexpr (RecordWhyLive) if (!config->whyLive.empty() && config->whyLive.match(s->getName())) printWhyLive(s, prev); if (auto *classSym = in.objcStubs->lookupClassSymbol(s)) - addSym(classSym, prev); + addSym(classSym, prev, worklist); if (auto *d = dyn_cast<Defined>(s)) { if (d->isec()) - enqueue(d->isec(), d->value, prev); + enqueue(d->isec(), d->value, prev, worklist); if (d->unwindEntry()) - enqueue(d->unwindEntry(), 0, prev); + enqueue(d->unwindEntry(), 0, prev, worklist); + } +} + +template <bool RecordWhyLive> +void MarkLiveImpl<RecordWhyLive>::visit(WorklistEntry *entry, + Worklist &worklist) const { + // Entries that get placed onto the worklist always contain + // ConcatInputSections. `WhyLiveEntry::prev` may point to entries that + // contain other types of InputSections (due to S_ATTR_LIVE_SUPPORT), but + // those entries should never be pushed onto the worklist. + auto *isec = cast<ConcatInputSection>(getInputSection(entry)); + assert(isec->live && "We mark as live when pushing onto the worklist!"); + + // Mark all symbols listed in the relocation table for this section. + for (const Relocation &r : isec->relocs) { + if (auto *s = dyn_cast<Symbol *>(r.referent)) + addSym(s, entry, worklist); + else + enqueue(cast<InputSection *>(r.referent), r.getAddend(), entry, worklist); + } + for (Defined *d : isec->symbols) + addSym(d, entry, worklist); +} + +// Visits the sections in nextLevel, one level at a time. Workers take chunks of +// a level, small enough that every worker gets some, and visit them depth-first +// to take advantage of memory locality. Once one worker has run out of chunks, +// the others finish their current visit and move the rest of their stacks to +// nextLevel, so that the level ends and all workers share the rest in the next +// one. With one thread, this reduces to a single depth-first walk. The last +// join makes every live bit visible to the live-support scan, which reads them +// with plain loads. +template <bool RecordWhyLive> void MarkLiveImpl<RecordWhyLive>::drain() { + const size_t numThreads = parallel::getThreadCount(); + while (!nextLevel.empty()) { + Worklist level = std::move(nextLevel); + nextLevel.clear(); + std::mutex nextLevelMutex; + std::atomic<bool> anyWorkerIdle{false}; + size_t chunkSize = + std::clamp<size_t>(level.size() / (4 * numThreads), 1, 64); + // Each worker starts with the chunk at its own index and then claims the + // chunks after the first numThreads. + std::atomic<size_t> next{numThreads * chunkSize}; + parallelFor(0, numThreads, [&](size_t shard) { + Worklist stack; + for (size_t begin = shard * chunkSize; begin < level.size(); + begin = next.fetch_add(chunkSize, std::memory_order_relaxed)) { + size_t end = std::min(begin + chunkSize, level.size()); + stack.append(level.begin() + begin, level.begin() + end); + while (!stack.empty()) { + visit(stack.pop_back_val(), stack); + if (anyWorkerIdle.load(std::memory_order_relaxed)) { + std::lock_guard<std::mutex> lock(nextLevelMutex); + nextLevel.append(stack.begin(), stack.end()); + stack.clear(); + } + } + } + anyWorkerIdle.store(true, std::memory_order_relaxed); + }); } } @@ -151,7 +232,7 @@ MarkLiveImpl<RecordWhyLive>::makeEntry( assert(!prev); return nullptr; } - return make<WhyLiveEntry>(isec, prev); + return makeThreadLocal<WhyLiveEntry>(isec, prev); } else { return isec; } @@ -161,25 +242,7 @@ template <bool RecordWhyLive> void MarkLiveImpl<RecordWhyLive>::markTransitively() { do { // Mark things reachable from GC roots as live. - while (!worklist.empty()) { - WorklistEntry *entry = worklist.pop_back_val(); - // Entries that get placed onto the worklist always contain - // ConcatInputSections. `WhyLiveEntry::prev` may point to entries that - // contain other types of InputSections (due to S_ATTR_LIVE_SUPPORT), but - // those entries should never be pushed onto the worklist. - auto *isec = cast<ConcatInputSection>(getInputSection(entry)); - assert(isec->live && "We mark as live when pushing onto the worklist!"); - - // Mark all symbols listed in the relocation table for this section. - for (const Relocation &r : isec->relocs) { - if (auto *s = dyn_cast<Symbol *>(r.referent)) - addSym(s, entry); - else - enqueue(cast<InputSection *>(r.referent), r.getAddend(), entry); - } - for (Defined *d : getInputSection(entry)->symbols) - addSym(d, entry); - } + drain(); // S_ATTR_LIVE_SUPPORT sections are live if they point _to_ a live // section. Process them in a second pass. @@ -195,12 +258,12 @@ void MarkLiveImpl<RecordWhyLive>::markTransitively() { InputSection *referentIsec = nullptr; if (auto *d = dyn_cast<Defined>(s)) referentIsec = d->isec(); - enqueue(isec, 0, makeEntry(referentIsec, nullptr)); + enqueue(isec, 0, makeEntry(referentIsec, nullptr), nextLevel); } } else { auto *referentIsec = cast<InputSection *>(r.referent); if (referentIsec->isLive(r.getAddend())) - enqueue(isec, 0, makeEntry(referentIsec, nullptr)); + enqueue(isec, 0, makeEntry(referentIsec, nullptr), nextLevel); } } } @@ -209,7 +272,7 @@ void MarkLiveImpl<RecordWhyLive>::markTransitively() { // 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()); + } while (!nextLevel.empty()); } // Set live bit on for each reachable chunk. Unmarked (unreachable) diff --git a/lld/MachO/Options.td b/lld/MachO/Options.td index e5f79dc0f8e751..0e79621a9cae97 100644 --- a/lld/MachO/Options.td +++ b/lld/MachO/Options.td @@ -694,7 +694,8 @@ def whyload : Flag<["-"], "whyload">, Group<grp_introspect>; def why_live : Separate<["-"], "why_live">, MetaVarName<"<symbol>">, - HelpText<"Log a chain of references to <symbol>, for use with -dead_strip">, + HelpText<"Log a chain of references to <symbol>, for use with -dead_strip. " + "The chain is deterministic only with --threads=1">, Group<grp_introspect>; def print_statistics : Flag<["-"], "print_statistics">, HelpText<"Log the linker's memory and CPU usage">, diff --git a/lld/MachO/Symbols.h b/lld/MachO/Symbols.h index cdeef934752229..29b8079ea94e8a 100644 --- a/lld/MachO/Symbols.h +++ b/lld/MachO/Symbols.h @@ -109,7 +109,7 @@ class Symbol { bool isUsedInRegularObj : 1; // True if this symbol is used from a live section. - bool used : 1; + bool used; }; class Defined : public Symbol { diff --git a/lld/test/MachO/why-live.s b/lld/test/MachO/why-live.s index 40d94e9da25c65..4561aded459b88 100644 --- a/lld/test/MachO/why-live.s +++ b/lld/test/MachO/why-live.s @@ -1,27 +1,27 @@ # REQUIRES: x86 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos %s -o %t.o -# RUN: %lld -lSystem -dead_strip -why_live _foo -why_live _undef -U _undef \ -# RUN: -why_live _support -why_live _support_refs_dylib_fun \ +# RUN: %lld -lSystem -dead_strip --threads=1 -why_live _foo -why_live _undef \ +# RUN: -U _undef -why_live _support -why_live _support_refs_dylib_fun \ # RUN: -why_live _abs %t.o -o /dev/null 2>&1 | FileCheck %s ## Due to an implementation detail, LLD is not able to report -why_live info for ## absolute symbols. (ld64 has the same shortcoming.) # CHECK-NOT: _abs -# CHECK: _foo from {{.*}}why-live.s.tmp.o -# CHECK-NEXT: _quux from {{.*}}why-live.s.tmp.o -# CHECK-NEXT: _undef from {{.*}}why-live.s.tmp.o +# CHECK: _undef from {{.*}}why-live.s.tmp.o # CHECK-NEXT: _main from {{.*}}why-live.s.tmp.o -## Our handling of live_support sections can be improved... we should print the -## dylib symbol that keeps _support_refs_dylib_fun alive, instead of printing -## the live_support symbol's name itself. (ld64 seems to have the same issue.) -# CHECK-NEXT: _support_refs_dylib_fun from {{.*}}why-live.s.tmp.o -# CHECK-NEXT: _support_refs_dylib_fun from {{.*}}why-live.s.tmp.o -## Again, this can be improved: we shouldn't be printing _support twice. (ld64 -## seems to have the same issue.) +# CHECK-NEXT: _foo from {{.*}}why-live.s.tmp.o +# CHECK-NEXT: _main from {{.*}}why-live.s.tmp.o +## Our handling of live_support sections can be improved: we shouldn't be +## printing _support twice. (ld64 seems to have the same issue.) # CHECK-NEXT: _support from {{.*}}why-live.s.tmp.o # CHECK-NEXT: _support from {{.*}}why-live.s.tmp.o # CHECK-NEXT: _foo from {{.*}}why-live.s.tmp.o +## Again, this can be improved... we should print the dylib symbol that keeps +## _support_refs_dylib_fun alive, instead of printing the live_support symbol's +## name itself. (ld64 seems to have the same issue.) +# CHECK-NEXT: _support_refs_dylib_fun from {{.*}}why-live.s.tmp.o +# CHECK-NEXT: _support_refs_dylib_fun from {{.*}}why-live.s.tmp.o # CHECK-EMPTY: .text _______________________________________________ llvm-branch-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
