Skip to content

Instantly share code, notes, and snippets.

@MaskRay

MaskRay/lld-par-noposition.patch

Last active September 7, 2026 19:51
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save MaskRay/f1fb88fcbaa51404ff0f746dcca67d6a to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save MaskRay/f1fb88fcbaa51404ff0f746dcca67d6a to your computer and use it in GitHub Desktop.
Download ZIP
lld/ELF parallel file parsing pipeline
Raw
lld-par-noposition.patch
From c29fbaee28ba8399fd5225a974c7333048fc5195 Mon Sep 17 00:00:00 2001
From: Fangrui Song <hidden>
Date: Wed, 17 Jun 2026 23:28:54 -0700
Subject: [PATCH] [ELF] Parallelize input file parsing and symbol resolution
(order-independent extraction)
Replace the serial elf::parseFiles loop with a parallel pipeline. Per
batch the pipeline reads symbol records (parallel per file,
counting-sorted into 32 hash buckets), builds a per-bucket name
database, activates archive members, creates and resolves symbols
(parallel per bucket), and wires global symbols into per-file arrays.
Archive member activation uses order-independent extraction: a non-weak
undefined reference pulls in its lazy member, to a fixpoint; the whole
link behaves like one implicit group. Each name resolves in its
strongest tier (strong over weak); within a tier an eager regular
(non-lazy, non-shared) definition is preferred and suppresses
extraction, otherwise the first-seen definition wins and a lazy member
is pulled in. So a regular archive definition is preferred over a shared
one when seen first, an eager regular definition always beats a lazy
one, and a weak archive member is pulled only when nothing stronger
defines the name -- matching ld.bfd. Determinism comes from file index,
not scan order. This abandons GNU positional semantics: backward
references resolve and --start-group is a no-op. Output is deterministic
across thread counts; all of lld/test/ELF passes, with order-dependent
tests (shared-lazy, trace-symbols) updated to the new behavior.
--fortran-common is preserved: when a tentative COMMON is active (in an
eager file or an extracted member) and a lazy member provides a
non-tentative definition of the same name, that member is pulled in to
override the COMMON, tracked by a per-name override worklist in the
activation fixpoint.
Order-independence makes several serial-path constructs dead, removed
here: the actDefIdx lazy-definition cutoff (a member is fully eager once
extracted, so a definition anchors at its file's rank), and the separate
fullRank/lazyRank arrays (merged into one file-index rank).
--warn-backrefs is removed too: with one implicit group every reference
resolves, so backward-reference detection is meaningless; the option,
ctx.backwardReferences, the recordExtractions backref pass, and
InputFile::groupId go with it. --why-extract is retained.
Experimental variant of the parallel-pipeline patch; not for merge.
---
lld/ELF/Config.h | 14 +-
lld/ELF/Driver.cpp | 273 ++-
lld/ELF/InputFiles.cpp | 2040 ++++++++++++-----
lld/ELF/InputFiles.h | 82 +-
lld/ELF/LinkerScript.cpp | 8 +-
lld/ELF/Options.td | 14 +-
lld/ELF/Relocations.cpp | 9 +-
lld/ELF/ScriptParser.cpp | 2 -
lld/ELF/SymbolTable.cpp | 39 +-
lld/ELF/SymbolTable.h | 65 +-
lld/ELF/Symbols.cpp | 142 +-
lld/ELF/Symbols.h | 12 +-
lld/ELF/SyntheticSections.cpp | 9 +-
lld/ELF/Writer.cpp | 3 +-
lld/docs/ELF/warn_backrefs.md | 100 -
lld/docs/index.md | 1 -
lld/docs/ld.lld.1 | 13 -
lld/test/ELF/fortran-common-extract.s | 84 +
lld/test/ELF/interconnected-lazy.s | 12 +-
lld/test/ELF/lto/archive-mixed.test | 5 +-
lld/test/ELF/lto/comdat-mixed-archive.test | 33 +-
lld/test/ELF/lto/lazy-internal.ll | 5 +-
.../lto/thinlto-emit-index-thin-archive.ll | 15 +-
lld/test/ELF/lto/warn-backrefs.ll | 30 -
lld/test/ELF/shared-lazy.s | 22 +-
lld/test/ELF/trace-symbols.s | 21 +-
lld/test/ELF/warn-backrefs.s | 112 -
lld/test/ELF/why-extract.s | 7 +-
lld/test/ELF/wrap-extract-real.s | 20 +
29 files changed, 1963 insertions(+), 1229 deletions(-)
delete mode 100644 lld/docs/ELF/warn_backrefs.md
create mode 100644 lld/test/ELF/fortran-common-extract.s
delete mode 100644 lld/test/ELF/lto/warn-backrefs.ll
delete mode 100644 lld/test/ELF/warn-backrefs.s
diff --git a/lld/ELF/Config.h b/lld/ELF/Config.h
index 54e0aa58591a..f315369c3725 100644
--- a/lld/ELF/Config.h
+++ b/lld/ELF/Config.h
@@ -196,7 +196,6 @@ struct LoadJob {
bool lazy;
bool asNeeded;
bool withLOption;
- uint32_t groupId;
SmallVector<std::unique_ptr<InputFile>, 0> out;
std::vector<std::unique_ptr<llvm::MemoryBuffer>> thinBufs;
SmallVector<std::pair<std::string, llvm::StringRef>, 0> tarEntries;
@@ -232,8 +231,10 @@ private:
SmallVector<std::unique_ptr<InputFile>, 0> files, ltoObjectFiles;
public:
- // See InputFile::groupId.
- uint32_t nextGroupId;
+ // The command-line input files and dependent libraries, some of which may
+ // still be lazy.
+ ArrayRef<std::unique_ptr<InputFile>> getFiles() const { return files; }
+
bool isInGroup;
std::unique_ptr<InputFile> armCmseImpLib;
SmallVector<std::pair<StringRef, unsigned>, 0> archiveFiles;
@@ -422,8 +423,6 @@ struct Config {
bool undefinedVersion;
bool unique;
bool useAndroidRelrTags = false;
- bool warnBackrefs;
- llvm::SmallVector<llvm::GlobPattern, 0> warnBackrefsExclude;
bool warnCommon;
bool warnMissingEntry;
bool warnSymbolOrdering;
@@ -739,11 +738,6 @@ struct Ctx : CommonLinkerContext {
// A tuple of (reference, extractedFile, sym). Used by --why-extract=.
SmallVector<std::tuple<std::string, const InputFile *, const Symbol &>, 0>
whyExtractRecords;
- // A mapping from a symbol to an InputFile referencing it backward. Used by
- // --warn-backrefs.
- llvm::DenseMap<const Symbol *,
- std::pair<const InputFile *, const InputFile *>>
- backwardReferences;
llvm::SmallSet<llvm::StringRef, 0> auxiliaryFiles;
// If --reproduce is specified, all input files are written to this tar
// archive.
diff --git a/lld/ELF/Driver.cpp b/lld/ELF/Driver.cpp
index 0393410b35d4..b2c319c2c71a 100644
--- a/lld/ELF/Driver.cpp
+++ b/lld/ELF/Driver.cpp
@@ -242,7 +242,6 @@ void LinkerDriver::addFile(StringRef path, bool withLOption) {
/*lazy=*/false,
/*asNeeded=*/false,
/*withLOption=*/false,
- nextGroupId,
{},
{},
{}});
@@ -281,13 +280,10 @@ void LinkerDriver::addFile(StringRef path, bool withLOption) {
inLib,
ctx.arg.asNeeded,
withLOption,
- nextGroupId,
{},
{},
{}});
}
- if (!isInGroup)
- ++nextGroupId;
if (!deferLoad)
loadFiles();
}
@@ -1633,8 +1629,6 @@ static void readConfigs(Ctx &ctx, opt::InputArgList &args) {
ctx.arg.unique = args.hasArg(OPT_unique);
ctx.arg.useAndroidRelrTags = args.hasFlag(
OPT_use_android_relr_tags, OPT_no_use_android_relr_tags, false);
- ctx.arg.warnBackrefs =
- args.hasFlag(OPT_warn_backrefs, OPT_no_warn_backrefs, false);
ctx.arg.warnCommon = args.hasFlag(OPT_warn_common, OPT_no_warn_common, false);
ctx.arg.warnSymbolOrdering =
args.hasFlag(OPT_warn_symbol_ordering, OPT_no_warn_symbol_ordering, true);
@@ -1979,15 +1973,6 @@ static void readConfigs(Ctx &ctx, opt::InputArgList &args) {
ctx.arg.retainSymbols->insert(s);
}
- for (opt::Arg *arg : args.filtered(OPT_warn_backrefs_exclude)) {
- StringRef pattern(arg->getValue());
- if (Expected<GlobPattern> pat = GlobPattern::create(pattern))
- ctx.arg.warnBackrefsExclude.push_back(std::move(*pat));
- else
- ErrAlways(ctx) << arg->getSpelling() << ": " << pat.takeError() << ": "
- << pattern;
- }
-
// For -no-pie and -pie, --export-dynamic-symbol specifies defined symbols
// which should be exported. For -shared, references to matched non-local
// STV_DEFAULT symbols are not bound to definitions within the shared object,
@@ -2161,9 +2146,7 @@ void LinkerDriver::loadFiles() {
case LoadJob::Archive: {
// Scan all archive members rather than using the archive symbol
// index. We assume the archive symbol table order matches the order
- // of symbols in the member symbol tables. All files within the
- // archive share the same group ID to allow mutual references for
- // --warn-backrefs.
+ // of symbols in the member symbol tables.
auto members = getArchiveMembers(ctx, job);
job.out.reserve(members.size());
bool lazy = !job.inWholeArchive;
@@ -2196,8 +2179,6 @@ void LinkerDriver::loadFiles() {
job.out.push_back(std::make_unique<BinaryFile>(ctx, job.mbref));
break;
}
- for (auto &m : job.out)
- m->groupId = job.groupId;
});
}
@@ -2230,7 +2211,6 @@ void LinkerDriver::createFiles(opt::InputArgList &args) {
// Iterate over argv to process input files and positional arguments.
std::optional<MemoryBufferRef> defaultScript;
- nextGroupId = 0;
isInGroup = false;
bool hasInput = false, hasScript = false;
for (auto *arg : args) {
@@ -2309,7 +2289,6 @@ void LinkerDriver::createFiles(opt::InputArgList &args) {
if (!isInGroup)
ErrAlways(ctx) << "stray --end-group";
isInGroup = false;
- ++nextGroupId;
break;
case OPT_start_lib:
if (inLib)
@@ -2324,7 +2303,6 @@ void LinkerDriver::createFiles(opt::InputArgList &args) {
ErrAlways(ctx) << "stray --end-lib";
inLib = false;
isInGroup = false;
- ++nextGroupId;
break;
case OPT_push_state:
stack.emplace_back(ctx.arg.asNeeded, ctx.arg.isStatic, inWholeArchive);
@@ -2480,19 +2458,6 @@ static void excludeLibs(Ctx &ctx, opt::InputArgList &args) {
visit(file);
}
-// Force Sym to be entered in the output.
-static void handleUndefined(Ctx &ctx, Symbol *sym, const char *option) {
- // Since a symbol may not be used inside the program, LTO may
- // eliminate it. Mark the symbol as "used" to prevent it.
- sym->isUsedInRegularObj = true;
-
- if (!sym->isLazy())
- return;
- sym->extract(ctx);
- if (!ctx.arg.whyExtract.empty())
- ctx.whyExtractRecords.emplace_back(option, sym->file, *sym);
-}
-
// As an extension to GNU linkers, lld supports a variant of `-u`
// which accepts wildcard patterns. All symbols that match a given
// pattern are handled as if they were given by `-u`.
@@ -2503,24 +2468,19 @@ static void handleUndefinedGlob(Ctx &ctx, StringRef arg) {
return;
}
- // Calling sym->extract() in the loop is not safe because it may add new
- // symbols to the symbol table, invalidating the current iterator.
- SmallVector<Symbol *, 0> syms;
+ // Mark all matches as used (so LTO does not eliminate them) and extract
+ // the lazy ones in a single batch.
+ SmallVector<Symbol *, 0> lazy;
for (Symbol *sym : ctx.symtab->getSymbols())
- if (!sym->isPlaceholder() && pat->match(sym->getName()))
- syms.push_back(sym);
-
- for (Symbol *sym : syms)
- handleUndefined(ctx, sym, "--undefined-glob");
-}
-
-static void handleLibcall(Ctx &ctx, StringRef name) {
- Symbol *sym = ctx.symtab->find(name);
- if (sym && sym->isLazy() && isa<BitcodeFile>(sym->file)) {
- if (!ctx.arg.whyExtract.empty())
- ctx.whyExtractRecords.emplace_back("<libcall>", sym->file, *sym);
- sym->extract(ctx);
- }
+ if (!sym->isPlaceholder() && pat->match(sym->getName())) {
+ sym->isUsedInRegularObj = true;
+ if (sym->isLazy())
+ lazy.push_back(sym);
+ }
+ reactivate(ctx, lazy);
+ if (!ctx.arg.whyExtract.empty())
+ for (Symbol *sym : lazy)
+ ctx.whyExtractRecords.emplace_back("--undefined-glob", sym->file, *sym);
}
static void writeArchiveStats(Ctx &ctx) {
@@ -2571,25 +2531,6 @@ static void writeWhyExtract(Ctx &ctx) {
}
}
-static void reportBackrefs(Ctx &ctx) {
- for (auto &ref : ctx.backwardReferences) {
- const Symbol &sym = *ref.first;
- std::string to = toStr(ctx, ref.second.second);
- // Some libraries have known problems and can cause noise. Filter them out
- // with --warn-backrefs-exclude=. The value may look like (for --start-lib)
- // *.o or (archive member) *.a(*.o).
- bool exclude = false;
- for (const llvm::GlobPattern &pat : ctx.arg.warnBackrefsExclude)
- if (pat.match(to)) {
- exclude = true;
- break;
- }
- if (!exclude)
- Warn(ctx) << "backward reference detected: " << sym.getName() << " in "
- << ref.second.first << " refers to " << to;
- }
-}
-
// Handle --dependency-file=<path>. If that option is given, lld creates a
// file at a given path with the following contents:
//
@@ -2812,10 +2753,18 @@ void LinkerDriver::compileBitcodeFiles(bool skipLinkedOutput) {
markBuffersAsDontNeed(ctx, skipLinkedOutput);
ltoObjectFiles = lto->compile();
+
+ // Resolve the LTO outputs' symbols against the symbol table and register
+ // them in ctx.objectFiles (the parse pipeline, shared with regular objects),
+ // pulling in archive members newly referenced by the LTO outputs (e.g.
+ // runtime libcalls).
+ SmallVector<InputFile *, 0> ltoFiles;
+ for (auto &file : ltoObjectFiles)
+ ltoFiles.push_back(file.get());
+ parseLtoObjectFiles(ctx, ltoFiles);
+
for (auto &file : ltoObjectFiles) {
auto *obj = cast<ObjFile<ELFT>>(file.get());
- obj->parse(/*ignoreComdats=*/true);
-
// This is only needed for AArch64 PAuth to set correct key in AUTH GOT
// entry based on symbol type (STT_FUNC or not).
// TODO: check if PAuth is actually used.
@@ -2839,7 +2788,6 @@ void LinkerDriver::compileBitcodeFiles(bool skipLinkedOutput) {
if (sym->hasVersionSuffix)
sym->parseSymbolVersion(ctx);
}
- ctx.objectFiles.push_back(obj);
}
}
@@ -2867,6 +2815,22 @@ static std::vector<WrappedSymbol> addWrappedSymbols(Ctx &ctx,
std::vector<WrappedSymbol> v;
DenseSet<StringRef> seen;
auto &ss = ctx.saver;
+ // A wrapper (or, when __real_ is referenced, the wrapped symbol) may live in
+ // a lazy archive member. Collect the references of one phase and pull the
+ // members in with a single activation pass.
+ SmallVector<Symbol *, 0> triggers;
+ auto addUndef = [&](StringRef name, uint8_t binding = llvm::ELF::STB_GLOBAL) {
+ Symbol *s = ctx.symtab->addUnusedUndefined(name, binding);
+ if (s->isLazy() && !s->isWeak())
+ triggers.push_back(s);
+ return s;
+ };
+
+ struct Wrap {
+ Symbol *sym, *wrap;
+ StringRef name, realName;
+ };
+ SmallVector<Wrap, 0> wraps;
for (auto *arg : args.filtered(OPT_wrap)) {
StringRef name = arg->getValue();
if (!seen.insert(name).second)
@@ -2876,40 +2840,59 @@ static std::vector<WrappedSymbol> addWrappedSymbols(Ctx &ctx,
if (!sym)
continue;
- Symbol *wrap =
- ctx.symtab->addUnusedUndefined(ss.save("__wrap_" + name), sym->binding);
+ wraps.push_back({sym, addUndef(ss.save("__wrap_" + name), sym->binding),
+ name, ss.save("__real_" + name)});
+ }
+ // Extract the wrappers first, so that a __real_ reference inside one of them
+ // is seen by the check below.
+ reactivate(ctx, triggers);
+ triggers.clear();
- // If __real_ is referenced, pull in the symbol if it is lazy. Do this after
- // processing __wrap_ as that may have referenced __real_.
- StringRef realName = ctx.saver.save("__real_" + name);
- if (Symbol *real = ctx.symtab->find(realName)) {
- ctx.symtab->addUnusedUndefined(name, sym->binding);
+ // If __real_ is referenced, pull in the symbol if it is lazy. A member
+ // extracted for one entry may reference another's __real_, so iterate.
+ SmallVector<uint8_t, 0> hasReal(wraps.size());
+ for (bool changed = true; changed;) {
+ changed = false;
+ for (auto [i, w] : llvm::enumerate(wraps)) {
+ Symbol *real;
+ if (hasReal[i] || !(real = ctx.symtab->find(w.realName)))
+ continue;
+ hasReal[i] = 1;
+ addUndef(w.name, w.sym->binding);
// Update sym's binding, which will replace real's later in
// SymbolTable::wrap.
- sym->binding = real->binding;
+ w.sym->binding = real->binding;
+ changed = true;
}
+ reactivate(ctx, triggers);
+ triggers.clear();
+ }
- Symbol *real = ctx.symtab->addUnusedUndefined(realName);
- v.push_back({sym, real, wrap});
+ for (const Wrap &w : wraps) {
+ Symbol *real = addUndef(w.realName);
+ v.push_back({w.sym, real, w.wrap});
// We want to tell LTO not to inline symbols to be overwritten
// because LTO doesn't know the final symbol contents after renaming.
real->scriptDefined = true;
- sym->scriptDefined = true;
+ w.sym->scriptDefined = true;
+ }
+ reactivate(ctx, triggers);
- // If a symbol is referenced in any object file, bitcode file or shared
- // object, mark its redirection target (foo for __real_foo and __wrap_foo
- // for foo) as referenced after redirection, which will be used to tell LTO
- // to not eliminate the redirection target. If the object file defining the
- // symbol also references it, we cannot easily distinguish the case from
- // cases where the symbol is not referenced. Retain the redirection target
- // in this case because we choose to wrap symbol references regardless of
- // whether the symbol is defined
- // (https://sourceware.org/bugzilla/show_bug.cgi?id=26358).
- if (real->referenced || real->isDefined())
- sym->referencedAfterWrap = true;
- if (sym->referenced || sym->isDefined())
- wrap->referencedAfterWrap = true;
+ // If a symbol is referenced in any object file, bitcode file or shared
+ // object, mark its redirection target (foo for __real_foo and __wrap_foo
+ // for foo) as referenced after redirection, which will be used to tell LTO
+ // to not eliminate the redirection target. If the object file defining the
+ // symbol also references it, we cannot easily distinguish the case from
+ // cases where the symbol is not referenced. Retain the redirection target
+ // in this case because we choose to wrap symbol references regardless of
+ // whether the symbol is defined
+ // (https://sourceware.org/bugzilla/show_bug.cgi?id=26358).
+ for (const WrappedSymbol &w : v) {
+ if (w.real->referenced || w.real->isDefined())
+ w.sym->referencedAfterWrap = true;
+ if (w.sym->referenced || w.sym->isDefined())
+ w.wrap->referencedAfterWrap = true;
}
return v;
}
@@ -3202,25 +3185,6 @@ static void readSecurityNotes(Ctx &ctx) {
<< "dependencies have the GCS marking.";
}
-static void initSectionsAndLocalSyms(ELFFileBase *file, bool ignoreComdats) {
- switch (file->ekind) {
- case ELF32LEKind:
- cast<ObjFile<ELF32LE>>(file)->initSectionsAndLocalSyms(ignoreComdats);
- break;
- case ELF32BEKind:
- cast<ObjFile<ELF32BE>>(file)->initSectionsAndLocalSyms(ignoreComdats);
- break;
- case ELF64LEKind:
- cast<ObjFile<ELF64LE>>(file)->initSectionsAndLocalSyms(ignoreComdats);
- break;
- case ELF64BEKind:
- cast<ObjFile<ELF64BE>>(file)->initSectionsAndLocalSyms(ignoreComdats);
- break;
- default:
- llvm_unreachable("");
- }
-}
-
static void postParseObjectFile(ELFFileBase *file) {
switch (file->ekind) {
case ELF32LEKind:
@@ -3246,6 +3210,7 @@ template <class ELFT> void LinkerDriver::link(opt::InputArgList &args) {
llvm::TimeTraceScope timeScope("Link", StringRef("LinkerDriver::Link"));
// Handle --trace-symbol.
+ ctx.symtab->hasTracedSymbol = args.hasArg(OPT_trace_symbol);
for (auto *arg : args.filtered(OPT_trace_symbol))
ctx.symtab->insert(arg->getValue())->traced = true;
@@ -3270,9 +3235,16 @@ template <class ELFT> void LinkerDriver::link(opt::InputArgList &args) {
ctx.sharedFiles.size() || ctx.arg.shared) &&
ctx.hasDynsym;
- // If an entry symbol is in a static archive, pull out that file now.
- if (Symbol *sym = ctx.symtab->find(ctx.arg.entry))
- handleUndefined(ctx, sym, "--entry");
+ // If an entry symbol is in a static archive, pull out that file now. Mark it
+ // used so that LTO does not eliminate it.
+ if (Symbol *sym = ctx.symtab->find(ctx.arg.entry)) {
+ sym->isUsedInRegularObj = true;
+ if (sym->isLazy()) {
+ reactivate(ctx, ArrayRef(sym));
+ if (!ctx.arg.whyExtract.empty())
+ ctx.whyExtractRecords.emplace_back("--entry", sym->file, *sym);
+ }
+ }
// Handle the `--undefined-glob <pattern>` options.
for (StringRef pat : args::getStrings(args, OPT_undefined_glob))
@@ -3313,8 +3285,16 @@ template <class ELFT> void LinkerDriver::link(opt::InputArgList &args) {
// object file to the link.
if (!ctx.bitcodeFiles.empty()) {
llvm::Triple TT(ctx.bitcodeFiles.front()->obj->getTargetTriple());
- for (auto *s : lto::LTO::getRuntimeLibcallSymbols(TT))
- handleLibcall(ctx, s);
+ SmallVector<Symbol *, 0> libcalls;
+ for (auto *s : lto::LTO::getRuntimeLibcallSymbols(TT)) {
+ Symbol *sym = ctx.symtab->find(s);
+ if (sym && sym->isLazy() && isa<BitcodeFile>(sym->file)) {
+ if (!ctx.arg.whyExtract.empty())
+ ctx.whyExtractRecords.emplace_back("<libcall>", sym->file, *sym);
+ libcalls.push_back(sym);
+ }
+ }
+ reactivate(ctx, libcalls);
}
// Archive members defining __wrap symbols may be extracted.
@@ -3322,9 +3302,6 @@ template <class ELFT> void LinkerDriver::link(opt::InputArgList &args) {
// No more lazy bitcode can be extracted at this point. Do post parse work
// like checking duplicate symbols.
- parallelForEach(ctx.objectFiles, [](ELFFileBase *file) {
- initSectionsAndLocalSyms(file, /*ignoreComdats=*/false);
- });
parallelForEach(ctx.objectFiles, postParseObjectFile);
parallelForEach(ctx.bitcodeFiles,
[](BitcodeFile *file) { file->postParse(); });
@@ -3401,9 +3378,8 @@ template <class ELFT> void LinkerDriver::link(opt::InputArgList &args) {
const size_t numInputFilesBeforeLTO = ctx.driver.files.size();
compileBitcodeFiles<ELFT>(skipLinkedOutput);
- // Symbol resolution finished. Report backward reference problems,
- // --print-archive-stats=, and --why-extract=.
- reportBackrefs(ctx);
+ // Symbol resolution finished. Report --print-archive-stats= and
+ // --why-extract=.
writeArchiveStats(ctx);
writeWhyExtract(ctx);
if (errCount(ctx))
@@ -3416,9 +3392,6 @@ template <class ELFT> void LinkerDriver::link(opt::InputArgList &args) {
// compileBitcodeFiles may have produced lto.tmp object files. After this, no
// more file will be added.
auto newObjectFiles = ArrayRef(ctx.objectFiles).slice(numObjsBeforeLTO);
- parallelForEach(newObjectFiles, [](ELFFileBase *file) {
- initSectionsAndLocalSyms(file, /*ignoreComdats=*/true);
- });
parallelForEach(newObjectFiles, postParseObjectFile);
for (const DuplicateSymbol &d : ctx.duplicates)
reportDuplicate(ctx, *d.sym, d.file, d.section, d.value);
@@ -3455,17 +3428,43 @@ template <class ELFT> void LinkerDriver::link(opt::InputArgList &args) {
llvm::TimeTraceScope timeScope("Aggregate sections");
// Now that we have a complete list of input files.
// Beyond this point, no new files are added.
- // Aggregate all input sections into one place.
- for (InputFile *f : ctx.objectFiles) {
- for (InputSectionBase *s : f->getSections()) {
+ // Aggregate all input sections into one place, preserving the
+ // file-then-section order: count per file in parallel, prefix-sum, then
+ // place each file's sections into its slice.
+ size_t numFiles = ctx.objectFiles.size();
+ SmallVector<uint32_t, 0> secOff(numFiles + 1), ehOff(numFiles + 1);
+ parallelFor(0, numFiles, [&](size_t i) {
+ uint32_t sn = 0, en = 0;
+ for (InputSectionBase *s : ctx.objectFiles[i]->getSections()) {
if (!s || s == &InputSection::discarded)
continue;
if (LLVM_UNLIKELY(isa<EhInputSection>(s)))
- ctx.ehInputSections.push_back(cast<EhInputSection>(s));
+ ++en;
else
- ctx.inputSections.push_back(s);
+ ++sn;
}
+ secOff[i + 1] = sn;
+ ehOff[i + 1] = en;
+ });
+ for (size_t i = 0; i != numFiles; ++i) {
+ secOff[i + 1] += secOff[i];
+ ehOff[i + 1] += ehOff[i];
}
+ size_t secBase = ctx.inputSections.size(),
+ ehBase = ctx.ehInputSections.size();
+ ctx.inputSections.resize(secBase + secOff[numFiles]);
+ ctx.ehInputSections.resize(ehBase + ehOff[numFiles]);
+ parallelFor(0, numFiles, [&](size_t i) {
+ size_t sn = secBase + secOff[i], en = ehBase + ehOff[i];
+ for (InputSectionBase *s : ctx.objectFiles[i]->getSections()) {
+ if (!s || s == &InputSection::discarded)
+ continue;
+ if (LLVM_UNLIKELY(isa<EhInputSection>(s)))
+ ctx.ehInputSections[en++] = cast<EhInputSection>(s);
+ else
+ ctx.inputSections[sn++] = s;
+ }
+ });
for (BinaryFile *f : ctx.binaryFiles)
for (InputSectionBase *s : f->getSections())
ctx.inputSections.push_back(cast<InputSection>(s));
diff --git a/lld/ELF/InputFiles.cpp b/lld/ELF/InputFiles.cpp
index 23649d620071..21f51248bfbc 100644
--- a/lld/ELF/InputFiles.cpp
+++ b/lld/ELF/InputFiles.cpp
@@ -26,9 +26,11 @@
#include "llvm/Support/ARMBuildAttributes.h"
#include "llvm/Support/Endian.h"
#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/Parallel.h"
#include "llvm/Support/Path.h"
#include "llvm/Support/TimeProfiler.h"
#include "llvm/Support/raw_ostream.h"
+#include <numeric>
#include <optional>
using namespace llvm;
@@ -262,8 +264,9 @@ std::optional<MemoryBufferRef> elf::readFile(Ctx &ctx, StringRef path) {
// All input object files must be for the same architecture
// (e.g. it does not make sense to link x86 object files with
-// MIPS object files.) This function checks for that error.
-static bool isCompatible(Ctx &ctx, InputFile *file) {
+// MIPS object files.) This function checks for that error. existing is an
+// already-accepted file named by the fallback diagnostic.
+static bool isCompatible(Ctx &ctx, InputFile *file, InputFile *existing) {
if (!file->isElf() && !isa<BitcodeFile>(file))
return true;
@@ -281,13 +284,6 @@ static bool isCompatible(Ctx &ctx, InputFile *file) {
return false;
}
- InputFile *existing = nullptr;
- if (!ctx.objectFiles.empty())
- existing = ctx.objectFiles[0];
- else if (!ctx.sharedFiles.empty())
- existing = ctx.sharedFiles[0];
- else if (!ctx.bitcodeFiles.empty())
- existing = ctx.bitcodeFiles[0];
auto diag = Err(ctx);
diag << file << " is incompatible";
if (existing)
@@ -295,71 +291,6 @@ static bool isCompatible(Ctx &ctx, InputFile *file) {
return false;
}
-template <class ELFT> static void doParseFile(Ctx &ctx, InputFile *file) {
- if (!isCompatible(ctx, file))
- return;
-
- // Lazy object file
- if (file->lazy) {
- if (auto *f = dyn_cast<BitcodeFile>(file)) {
- ctx.lazyBitcodeFiles.push_back(f);
- f->parseLazy();
- } else {
- cast<ObjFile<ELFT>>(file)->parseLazy();
- }
- return;
- }
-
- if (ctx.arg.trace)
- Msg(ctx) << file;
-
- if (file->kind() == InputFile::ObjKind) {
- ctx.objectFiles.push_back(cast<ELFFileBase>(file));
- cast<ObjFile<ELFT>>(file)->parse();
- } else if (auto *f = dyn_cast<SharedFile>(file)) {
- f->parse<ELFT>();
- } else if (auto *f = dyn_cast<BitcodeFile>(file)) {
- ctx.bitcodeFiles.push_back(f);
- f->parse();
- } else {
- ctx.binaryFiles.push_back(cast<BinaryFile>(file));
- cast<BinaryFile>(file)->parse();
- }
-}
-
-// Add symbols in File to the symbol table.
-void elf::parseFile(Ctx &ctx, InputFile *file) {
- invokeELFT(doParseFile, ctx, file);
-}
-
-// This function is explicitly instantiated in ARM.cpp. Mark it extern here,
-// to avoid warnings when building with MSVC.
-extern template void ObjFile<ELF32LE>::importCmseSymbols();
-extern template void ObjFile<ELF32BE>::importCmseSymbols();
-extern template void ObjFile<ELF64LE>::importCmseSymbols();
-extern template void ObjFile<ELF64BE>::importCmseSymbols();
-
-template <class ELFT>
-static void
-doParseFiles(Ctx &ctx,
- const SmallVector<std::unique_ptr<InputFile>, 0> &files) {
- // Add all files to the symbol table. This will add almost all symbols that we
- // need to the symbol table. This process might add files to the link due to
- // addDependentLibrary.
- for (size_t i = 0; i < files.size(); ++i) {
- llvm::TimeTraceScope timeScope("Parse input files", files[i]->getName());
- doParseFile<ELFT>(ctx, files[i].get());
- }
- if (ctx.driver.armCmseImpLib)
- cast<ObjFile<ELFT>>(*ctx.driver.armCmseImpLib).importCmseSymbols();
-}
-
-void elf::parseFiles(Ctx &ctx,
- const SmallVector<std::unique_ptr<InputFile>, 0> &files) {
- llvm::TimeTraceScope timeScope("Parse input files");
- invokeELFT(doParseFiles, ctx, files);
-}
-
// Concatenates arguments to construct a string representing an error location.
StringRef InputFile::getNameForScript() const {
if (archiveName.empty())
@@ -571,134 +502,112 @@ handleAArch64BAAndGnuProperties(ObjFile<ELFT> *file, Ctx &ctx,
}
}
-template <class ELFT> void ObjFile<ELFT>::parse(bool ignoreComdats) {
- object::ELFFile<ELFT> obj = this->getObj();
- // Read a section table. justSymbols is usually false.
- if (this->justSymbols) {
- initializeJustSymbols();
- initializeSymbols(obj);
- return;
- }
-
- // Handle dependent libraries and selection of section groups as these are not
- // done in parallel.
+template <class ELFT>
+void ObjFile<ELFT>::scanEarlySections() {
ArrayRef<Elf_Shdr> objSections = getELFShdrs<ELFT>();
- StringRef shstrtab = CHECK2(obj.getSectionStringTable(objSections), this);
- uint64_t size = objSections.size();
- sections.resize(size);
- for (size_t i = 0; i != size; ++i) {
+ const llvm::object::ELFFile<ELFT> obj = getObj();
+ typename ELFT::SymRange eSyms = this->getELFSyms<ELFT>();
+ for (size_t i = 0, size = objSections.size(); i != size; ++i) {
const Elf_Shdr &sec = objSections[i];
-
if (LLVM_LIKELY(sec.sh_type == SHT_PROGBITS))
continue;
- if (LLVM_LIKELY(sec.sh_type == SHT_GROUP)) {
- StringRef signature = getShtGroupSignature(objSections, sec);
- ArrayRef<Elf_Word> entries =
- CHECK2(obj.template getSectionContentsAsArray<Elf_Word>(sec), this);
- if (entries.empty())
- Fatal(ctx) << this << ": empty SHT_GROUP";
-
- Elf_Word flag = entries[0];
- if (flag && flag != GRP_COMDAT)
- Fatal(ctx) << this << ": unsupported SHT_GROUP format";
-
- bool keepGroup = !flag || ignoreComdats ||
- ctx.symtab->comdatGroups
- .try_emplace(CachedHashStringRef(signature), this)
- .second;
- if (keepGroup) {
- keptGroups.push_back(i);
- if (!ctx.arg.resolveGroups)
- sections[i] = createInputSection(
- i, sec, check(obj.getSectionName(sec, shstrtab)));
- } else {
- // Otherwise, discard group members.
- for (uint32_t secIndex : entries.slice(1)) {
- if (secIndex >= size)
- Fatal(ctx) << this
- << ": invalid section index in group: " << secIndex;
- sections[secIndex] = &InputSection::discarded;
- }
- }
+ if (sec.sh_type == SHT_GROUP) {
+ // Tolerantly decode the group; initializeSections diagnoses. The
+ // signature name (a strlen and a hash) is deferred to the caller, which
+ // reuses the symbol records; validate st_name so it cannot fail there.
+ Expected<ArrayRef<Elf_Word>> entries =
+ obj.template getSectionContentsAsArray<Elf_Word>(sec);
+ uint32_t sigSym = UINT32_MAX;
+ if (!entries)
+ consumeError(entries.takeError());
+ else if (!entries->empty() && (*entries)[0] == Elf_Word(GRP_COMDAT) &&
+ sec.sh_info < eSyms.size() &&
+ eSyms[sec.sh_info].st_name < stringTable.size())
+ sigSym = sec.sh_info;
+ comdatSecs.push_back({(uint32_t)i, sigSym});
continue;
}
+ if ((sec.sh_type == SHT_LLVM_DEPENDENT_LIBRARIES && !ctx.arg.relocatable) ||
+ (sec.sh_type == SHT_ARM_ATTRIBUTES && ctx.arg.emachine == EM_ARM))
+ needsSerialScan = true;
+ }
+}
+template <class ELFT>
+void ObjFile<ELFT>::processEarlySections() {
+ if (!needsSerialScan)
+ return;
+ object::ELFFile<ELFT> obj = this->getObj();
+ ArrayRef<Elf_Shdr> objSections = getELFShdrs<ELFT>();
+ StringRef shstrtab = CHECK2(obj.getSectionStringTable(objSections), this);
+ for (auto [i, sec] : llvm::enumerate(objSections)) {
if (sec.sh_type == SHT_LLVM_DEPENDENT_LIBRARIES && !ctx.arg.relocatable) {
StringRef name = check(obj.getSectionName(sec, shstrtab));
- ArrayRef<char> data = CHECK2(
- this->getObj().template getSectionContentsAsArray<char>(sec), this);
+ ArrayRef<char> data =
+ CHECK2(obj.template getSectionContentsAsArray<char>(sec), this);
if (!data.empty() && data.back() != '\0') {
Err(ctx)
<< this
<< ": corrupted dependent libraries section (unterminated string): "
<< name;
- } else {
- for (const char *d = data.begin(), *e = data.end(); d < e;) {
- StringRef s(d);
- addDependentLibrary(ctx, s, this);
- d += s.size() + 1;
- }
+ continue;
+ }
+ for (const char *d = data.begin(), *e = data.end(); d < e;) {
+ StringRef s(d);
+ addDependentLibrary(ctx, s, this);
+ d += s.size() + 1;
}
- sections[i] = &InputSection::discarded;
continue;
}
+ if (sec.sh_type != SHT_ARM_ATTRIBUTES || ctx.arg.emachine != EM_ARM)
+ continue;
+ ARMAttributeParser attributes;
+ ArrayRef<uint8_t> contents = check(obj.getSectionContents(sec));
+ StringRef name = check(obj.getSectionName(sec, shstrtab));
+ if (Error e = attributes.parse(contents, ekind == ELF32LEKind
+ ? llvm::endianness::little
+ : llvm::endianness::big)) {
+ InputSection isec(*this, sec, name);
+ Warn(ctx) << &isec << ": " << std::move(e);
+ } else {
+ updateSupportedARMFeatures(ctx, attributes);
+ updateARMVFPArgs(ctx, attributes, this);
- switch (ctx.arg.emachine) {
- case EM_ARM:
- if (sec.sh_type == SHT_ARM_ATTRIBUTES) {
- ARMAttributeParser attributes;
- ArrayRef<uint8_t> contents =
- check(this->getObj().getSectionContents(sec));
- StringRef name = check(obj.getSectionName(sec, shstrtab));
- sections[i] = &InputSection::discarded;
- if (Error e = attributes.parse(contents, ekind == ELF32LEKind
- ? llvm::endianness::little
- : llvm::endianness::big)) {
- InputSection isec(*this, sec, name);
- Warn(ctx) << &isec << ": " << std::move(e);
- } else {
- updateSupportedARMFeatures(ctx, attributes);
- updateARMVFPArgs(ctx, attributes, this);
-
- // FIXME: Retain the first attribute section we see. The eglibc ARM
- // dynamic loaders require the presence of an attribute section for
- // dlopen to work. In a full implementation we would merge all
- // attribute sections.
- if (ctx.in.attributes == nullptr) {
- ctx.in.attributes =
- std::make_unique<InputSection>(*this, sec, name);
- sections[i] = ctx.in.attributes.get();
- }
- }
+ // FIXME: Retain the first attribute section we see. The eglibc ARM
+ // dynamic loaders require the presence of an attribute section for
+ // dlopen to work. In a full implementation we would merge all
+ // attribute sections.
+ if (ctx.in.attributes == nullptr) {
+ ctx.in.attributes = std::make_unique<InputSection>(*this, sec, name);
+ armAttrSecIdx = i;
}
- break;
- case EM_AARCH64:
- // Producing a static binary with MTE globals is not currently supported,
- // remove all SHT_AARCH64_MEMTAG_GLOBALS_STATIC sections as they're unused
- // medatada, and we don't want them to end up in the output file for
- // static executables.
- if (sec.sh_type == SHT_AARCH64_MEMTAG_GLOBALS_STATIC &&
- !canHaveMemtagGlobals(ctx))
- sections[i] = &InputSection::discarded;
- break;
}
}
-
- // Read a symbol table.
- initializeSymbols(obj);
}
// Sections with SHT_GROUP and comdat bits define comdat section groups.
-// They are identified and deduplicated by group name. This function
-// returns a group name.
+// They are identified and deduplicated by group name. Decode a SHT_GROUP
+// section's signature name and entries. scanEarlySections consumes errors;
+// initializeSections diagnoses them.
template <class ELFT>
-StringRef ObjFile<ELFT>::getShtGroupSignature(ArrayRef<Elf_Shdr> sections,
- const Elf_Shdr &sec) {
- typename ELFT::SymRange symbols = this->getELFSyms<ELFT>();
- if (sec.sh_info >= symbols.size())
- Fatal(ctx) << this << ": invalid symbol index";
- const typename ELFT::Sym &sym = symbols[sec.sh_info];
- return CHECK2(sym.getName(this->stringTable), this);
+Expected<std::pair<StringRef, ArrayRef<typename ELFT::Word>>>
+ObjFile<ELFT>::getGroup(const Elf_Shdr &sec) {
+ typename ELFT::SymRange eSyms = this->getELFSyms<ELFT>();
+ if (sec.sh_info >= eSyms.size())
+ return createStringError("invalid symbol index");
+ Expected<StringRef> signature = eSyms[sec.sh_info].getName(stringTable);
+ if (!signature)
+ return signature.takeError();
+ Expected<ArrayRef<Elf_Word>> entries =
+ getObj().template getSectionContentsAsArray<Elf_Word>(sec);
+ if (!entries)
+ return entries.takeError();
+ if (entries->empty())
+ return createStringError("empty SHT_GROUP");
+ Elf_Word flag = (*entries)[0];
+ if (flag && flag != Elf_Word(GRP_COMDAT))
+ return createStringError("unsupported SHT_GROUP format");
+ return std::make_pair(*signature, *entries);
}
template <class ELFT>
@@ -772,9 +681,58 @@ void ObjFile<ELFT>::initializeSections(bool ignoreComdats,
ArrayRef<Elf_Shdr> objSections = getELFShdrs<ELFT>();
StringRef shstrtab = CHECK2(obj.getSectionStringTable(objSections), this);
uint64_t size = objSections.size();
+ this->sections.resize(size);
+
+ // First pass over the SHT_GROUP sections scanned by scanEarlySections:
+ // diagnose malformed groups and discard members of non-prevailing comdat
+ // groups. Comdat group ownership was registered by the parse pipeline
+ // (Pipeline::registerComdats). keptGroups memoizes the verdict for the main
+ // loop below (recomputing it there would re-decode and re-hash every
+ // signature). A decodable GRP_COMDAT group reuses the cached signature hash
+ // and re-reads only the entries.
+ SmallVector<std::pair<uint32_t, ArrayRef<Elf_Word>>, 0> keptGroups;
+ for (const ComdatSec &cs : comdatSecs) {
+ uint32_t i = cs.secIdx;
+ const Elf_Shdr &sec = objSections[i];
+ bool keepGroup;
+ ArrayRef<Elf_Word> entries;
+ if (cs.sigSym != UINT32_MAX) {
+ entries = cantFail(
+ this->getObj().template getSectionContentsAsArray<Elf_Word>(sec));
+ keepGroup = ignoreComdats || cs.prevailing;
+ } else {
+ // Malformed or non-COMDAT group: take the diagnosing path.
+ Expected<std::pair<StringRef, ArrayRef<Elf_Word>>> group = getGroup(sec);
+ if (!group) {
+ Err(ctx) << this << ": " << group.takeError();
+ this->sections[i] = &InputSection::discarded;
+ continue;
+ }
+ entries = group->second;
+ keepGroup = !entries[0] || ignoreComdats ||
+ ctx.symtab->findComdatGroup(
+ CachedHashStringRef(group->first)) == this;
+ }
+ if (keepGroup) {
+ keptGroups.push_back({i, entries});
+ if (!ctx.arg.resolveGroups)
+ this->sections[i] = createInputSection(
+ i, sec, check(obj.getSectionName(sec, shstrtab)));
+ continue;
+ }
+ // Otherwise, discard group members.
+ for (uint32_t secIndex : entries.slice(1)) {
+ if (secIndex >= size) {
+ Err(ctx) << this << ": invalid section index in group: " << secIndex;
+ continue;
+ }
+ this->sections[secIndex] = &InputSection::discarded;
+ }
+ }
+ comdatSecs = {};
+
SmallVector<ArrayRef<Elf_Word>, 0> selectedGroups;
- ArrayRef<uint32_t> keptGroups = this->keptGroups;
- size_t keptIdx = 0;
+ size_t keptGroupIdx = 0;
AArch64BuildAttrSubsections aarch64BAsubSections;
bool hasAArch64BuildAttributes = false;
for (size_t i = 0; i != size; ++i) {
@@ -828,17 +786,40 @@ void ObjFile<ELFT>::initializeSections(bool ignoreComdats,
this->sections[i] = &InputSection::discarded;
continue;
}
+ if (type == SHT_ARM_ATTRIBUTES && ctx.arg.emachine == EM_ARM) {
+ // The retained attribute section (if this file provides it) was created
+ // by processEarlySections.
+ this->sections[i] = i == armAttrSecIdx
+ ? ctx.in.attributes.get()
+ : (InputSectionBase *)&InputSection::discarded;
+ continue;
+ }
+ // Producing a static binary with MTE globals is not currently supported,
+ // remove all SHT_AARCH64_MEMTAG_GLOBALS_STATIC sections as they're unused
+ // medatada, and we don't want them to end up in the output file for
+ // static executables.
+ if (type == SHT_AARCH64_MEMTAG_GLOBALS_STATIC &&
+ ctx.arg.emachine == EM_AARCH64 && !canHaveMemtagGlobals(ctx)) {
+ this->sections[i] = &InputSection::discarded;
+ continue;
+ }
+ if (type == SHT_LLVM_DEPENDENT_LIBRARIES && !ctx.arg.relocatable) {
+ // The contents were processed by processEarlySections.
+ this->sections[i] = &InputSection::discarded;
+ continue;
+ }
switch (type) {
case SHT_GROUP: {
if (!ctx.arg.relocatable)
sections[i] = &InputSection::discarded;
- // Use the verdict parse() recorded for this group instead of repeating
- // the signature hashing and comdatGroups lookup.
- while (keptIdx != keptGroups.size() && keptGroups[keptIdx] < i)
- ++keptIdx;
- if (keptIdx != keptGroups.size() && keptGroups[keptIdx] == i)
- selectedGroups.push_back(
- cantFail(obj.template getSectionContentsAsArray<Elf_Word>(sec)));
+ // The verdict was computed by the first pass above. Kept groups may
+ // have been discarded since (e.g. as a member of another group).
+ while (keptGroupIdx != keptGroups.size() &&
+ keptGroups[keptGroupIdx].first < i)
+ ++keptGroupIdx;
+ if (keptGroupIdx != keptGroups.size() &&
+ keptGroups[keptGroupIdx].first == i)
+ selectedGroups.push_back(keptGroups[keptGroupIdx++].second);
break;
}
case SHT_SYMTAB_SHNDX:
@@ -1188,73 +1169,42 @@ InputSectionBase *ObjFile<ELFT>::createInputSection(uint32_t idx,
return makeThreadLocal<InputSection>(*this, sec, name);
}
-// Initialize symbols. symbols is a parallel array to the corresponding ELF
-// symbol table.
+// Resolve a global symbol: issue the resolve() call for its definition,
+// COMMON, or undefined reference, with the per-symbol side effects of symbol
+// resolution. Called by the parallel parse pipeline.
template <class ELFT>
-void ObjFile<ELFT>::initializeSymbols(const object::ELFFile<ELFT> &obj) {
- ArrayRef<Elf_Sym> eSyms = this->getELFSyms<ELFT>();
- if (!symbols)
- symbols = std::make_unique<Symbol *[]>(numSymbols);
-
- // Some entries have been filled by LazyObjFile.
- auto *symtab = ctx.symtab.get();
- for (size_t i = firstGlobal, end = eSyms.size(); i != end; ++i)
- if (!symbols[i])
- symbols[i] = symtab->insert(CHECK2(eSyms[i].getName(stringTable), this));
-
- // Perform symbol resolution on non-local symbols.
- SmallVector<unsigned, 32> undefineds;
- for (size_t i = firstGlobal, end = eSyms.size(); i != end; ++i) {
- const Elf_Sym &eSym = eSyms[i];
- uint32_t secIdx = eSym.st_shndx;
- if (secIdx == SHN_UNDEF) {
- undefineds.push_back(i);
- continue;
- }
-
- uint8_t binding = eSym.getBinding();
- uint8_t stOther = eSym.st_other;
- uint8_t type = eSym.getType();
+static void resolveSymbol(Ctx &ctx, ObjFile<ELFT> *f,
+ const typename ELFT::Sym &eSym, Symbol &sym) {
+ if (eSym.st_shndx == SHN_UNDEF) {
+ sym.resolve(ctx, Undefined{f, StringRef(), eSym.getBinding(), eSym.st_other,
+ eSym.getType()});
+ sym.isUsedInRegularObj = true;
+ sym.referenced = true;
+ return;
+ }
+ sym.isUsedInRegularObj = true;
+ if (LLVM_UNLIKELY(eSym.st_shndx == SHN_COMMON)) {
uint64_t value = eSym.st_value;
- uint64_t size = eSym.st_size;
-
- Symbol *sym = symbols[i];
- sym->isUsedInRegularObj = true;
- if (LLVM_UNLIKELY(eSym.st_shndx == SHN_COMMON)) {
- if (value == 0 || value >= UINT32_MAX)
- Err(ctx) << this << ": common symbol '" << sym->getName()
- << "' has invalid alignment: " << value;
- hasCommonSyms = true;
- sym->resolve(ctx, CommonSymbol{ctx, this, StringRef(), binding, stOther,
- type, value, size});
- continue;
- }
-
- // Handle global defined symbols. Defined::section will be set in postParse.
- sym->resolve(ctx, Defined{ctx, this, StringRef(), binding, stOther, type,
- value, size, nullptr});
- }
-
- // Undefined symbols (excluding those defined relative to non-prevailing
- // sections) can trigger recursive extract. Process defined symbols first so
- // that the relative order between a defined symbol and an undefined symbol
- // does not change the symbol resolution behavior. In addition, a set of
- // interconnected symbols will all be resolved to the same file, instead of
- // being resolved to different files.
- for (unsigned i : undefineds) {
- const Elf_Sym &eSym = eSyms[i];
- Symbol *sym = symbols[i];
- sym->resolve(ctx, Undefined{this, StringRef(), eSym.getBinding(),
- eSym.st_other, eSym.getType()});
- sym->isUsedInRegularObj = true;
- sym->referenced = true;
+ if (value == 0 || value >= UINT32_MAX)
+ Err(ctx) << f << ": common symbol '" << sym.getName()
+ << "' has invalid alignment: " << value;
+ sym.resolve(ctx, CommonSymbol{ctx, f, StringRef(), eSym.getBinding(),
+ eSym.st_other, eSym.getType(), value,
+ eSym.st_size});
+ return;
}
+ // Defined::section will be set in postParse.
+ sym.resolve(ctx,
+ Defined{ctx, f, StringRef(), eSym.getBinding(), eSym.st_other,
+ eSym.getType(), eSym.st_value, eSym.st_size, nullptr});
}
template <class ELFT>
void ObjFile<ELFT>::initSectionsAndLocalSyms(bool ignoreComdats) {
if (!justSymbols)
initializeSections(ignoreComdats, getObj());
+ else
+ initializeJustSymbols();
if (!firstGlobal)
return;
@@ -1365,73 +1315,6 @@ template <class ELFT> void ObjFile<ELFT>::postParse() {
}
}
-// The handling of tentative definitions (COMMON symbols) in archives is murky.
-// A tentative definition will be promoted to a global definition if there are
-// no non-tentative definitions to dominate it. When we hold a tentative
-// definition to a symbol and are inspecting archive members for inclusion
-// there are 2 ways we can proceed:
-//
-// 1) Consider the tentative definition a 'real' definition (ie promotion from
-// tentative to real definition has already happened) and not inspect
-// archive members for Global/Weak definitions to replace the tentative
-// definition. An archive member would only be included if it satisfies some
-// other undefined symbol. This is the behavior Gold uses.
-//
-// 2) Consider the tentative definition as still undefined (ie the promotion to
-// a real definition happens only after all symbol resolution is done).
-// The linker searches archive members for STB_GLOBAL definitions to
-// replace the tentative definition with. This is the behavior used by
-// GNU ld.
-//
-// The second behavior is inherited from SysVR4, which based it on the FORTRAN
-// COMMON BLOCK model. This behavior is needed for proper initialization in old
-// (pre F90) FORTRAN code that is packaged into an archive.
-//
-// The following functions search archive members for definitions to replace
-// tentative definitions (implementing behavior 2).
-static bool isBitcodeNonCommonDef(MemoryBufferRef mb, StringRef symName,
- StringRef archiveName) {
- IRSymtabFile symtabFile = check(readIRSymtab(mb));
- for (const irsymtab::Reader::SymbolRef &sym :
- symtabFile.TheReader.symbols()) {
- if (sym.isGlobal() && sym.getName() == symName)
- return !sym.isUndefined() && !sym.isWeak() && !sym.isCommon();
- }
- return false;
-}
-
-template <class ELFT>
-static bool isNonCommonDef(Ctx &ctx, ELFKind ekind, MemoryBufferRef mb,
- StringRef symName, StringRef archiveName) {
- ObjFile<ELFT> *obj = make<ObjFile<ELFT>>(ctx, ekind, mb, archiveName);
- obj->init();
- StringRef stringtable = obj->getStringTable();
-
- for (auto sym : obj->template getGlobalELFSyms<ELFT>()) {
- Expected<StringRef> name = sym.getName(stringtable);
- if (name && name.get() == symName)
- return sym.isDefined() && sym.getBinding() == STB_GLOBAL &&
- !sym.isCommon();
- }
- return false;
-}
-
-static bool isNonCommonDef(Ctx &ctx, MemoryBufferRef mb, StringRef symName,
- StringRef archiveName) {
- switch (getELFKind(ctx, mb, archiveName)) {
- case ELF32LEKind:
- return isNonCommonDef<ELF32LE>(ctx, ELF32LEKind, mb, symName, archiveName);
- case ELF32BEKind:
- return isNonCommonDef<ELF32BE>(ctx, ELF32BEKind, mb, symName, archiveName);
- case ELF64LEKind:
- return isNonCommonDef<ELF64LE>(ctx, ELF64LEKind, mb, symName, archiveName);
- case ELF64BEKind:
- return isNonCommonDef<ELF64BE>(ctx, ELF64BEKind, mb, symName, archiveName);
- default:
- llvm_unreachable("getELFKind");
- }
-}
-
SharedFile::SharedFile(Ctx &ctx, MemoryBufferRef m, StringRef defaultSoName)
: ELFFileBase(ctx, SharedKind, getELFKind(ctx, m, ""), m),
soName(defaultSoName), isNeeded(!ctx.arg.asNeeded) {}
@@ -1537,203 +1420,27 @@ static uint64_t getAlignment(ArrayRef<typename ELFT::Shdr> sections,
return (ret > UINT32_MAX) ? 0 : ret;
}
-// Fully parse the shared object file.
-//
-// This function parses symbol versions. If a DSO has version information,
-// the file has a ".gnu.version_d" section which contains symbol version
-// definitions. Each symbol is associated to one version through a table in
-// ".gnu.version" section. That table is a parallel array for the symbol
-// table, and each table entry contains an index in ".gnu.version_d".
-//
-// The special index 0 is reserved for VERF_NDX_LOCAL and 1 is for
-// VER_NDX_GLOBAL. There's no table entry for these special versions in
-// ".gnu.version_d".
-//
-// The file format for symbol versioning is perhaps a bit more complicated
-// than necessary, but you can easily understand the code if you wrap your
-// head around the data structure described above.
-template <class ELFT> void SharedFile::parse() {
- using Elf_Dyn = typename ELFT::Dyn;
- using Elf_Shdr = typename ELFT::Shdr;
- using Elf_Sym = typename ELFT::Sym;
- using Elf_Verdef = typename ELFT::Verdef;
- using Elf_Versym = typename ELFT::Versym;
-
- ArrayRef<Elf_Dyn> dynamicTags;
- const ELFFile<ELFT> obj = this->getObj<ELFT>();
- ArrayRef<Elf_Shdr> sections = getELFShdrs<ELFT>();
-
- const Elf_Shdr *versymSec = nullptr;
- const Elf_Shdr *verdefSec = nullptr;
- const Elf_Shdr *verneedSec = nullptr;
- symbols = std::make_unique<Symbol *[]>(numSymbols);
-
- // Search for .dynsym, .dynamic, .symtab, .gnu.version and .gnu.version_d.
- for (const Elf_Shdr &sec : sections) {
- switch (sec.sh_type) {
- default:
- continue;
- case SHT_DYNAMIC:
- dynamicTags =
- CHECK2(obj.template getSectionContentsAsArray<Elf_Dyn>(sec), this);
- break;
- case SHT_GNU_versym:
- versymSec = &sec;
- break;
- case SHT_GNU_verdef:
- verdefSec = &sec;
- break;
- case SHT_GNU_verneed:
- verneedSec = &sec;
- break;
- }
- }
-
- if (versymSec && numSymbols == 0) {
- ErrAlways(ctx) << "SHT_GNU_versym should be associated with symbol table";
- return;
- }
-
- // Search for a DT_SONAME tag to initialize this->soName.
- for (const Elf_Dyn &dyn : dynamicTags) {
- if (dyn.d_tag == DT_NEEDED) {
- uint64_t val = dyn.getVal();
- if (val >= this->stringTable.size()) {
- Err(ctx) << this << ": invalid DT_NEEDED entry";
- return;
- }
- dtNeeded.push_back(this->stringTable.data() + val);
- } else if (dyn.d_tag == DT_SONAME) {
- uint64_t val = dyn.getVal();
- if (val >= this->stringTable.size()) {
- Err(ctx) << this << ": invalid DT_SONAME entry";
- return;
- }
- soName = this->stringTable.data() + val;
- }
- }
-
- // DSOs are uniquified not by filename but by soname.
- StringSaver &ss = ctx.saver;
- DenseMap<CachedHashStringRef, SharedFile *>::iterator it;
- bool wasInserted;
- std::tie(it, wasInserted) =
- ctx.symtab->soNames.try_emplace(CachedHashStringRef(soName), this);
-
- // If a DSO appears more than once on the command line with and without
- // --as-needed, --no-as-needed takes precedence over --as-needed because a
- // user can add an extra DSO with --no-as-needed to force it to be added to
- // the dependency list.
- if (isNeeded)
- it->second->isNeeded.store(true, std::memory_order_relaxed);
- if (!wasInserted)
- return;
-
- ctx.sharedFiles.push_back(this);
-
- verdefs = parseVerdefs<ELFT>(obj.base(), verdefSec);
- std::vector<uint32_t> verneeds = parseVerneed<ELFT>(obj, verneedSec);
- parseGnuAndFeatures<ELFT>(obj);
-
- // Parse ".gnu.version" section which is a parallel array for the symbol
- // table. If a given file doesn't have a ".gnu.version" section, we use
- // VER_NDX_GLOBAL.
- size_t size = numSymbols - firstGlobal;
- std::vector<uint16_t> versyms(size, VER_NDX_GLOBAL);
- if (versymSec) {
- ArrayRef<Elf_Versym> versym =
- CHECK2(obj.template getSectionContentsAsArray<Elf_Versym>(*versymSec),
- this)
- .slice(firstGlobal);
- for (size_t i = 0; i < size; ++i)
- versyms[i] = versym[i].vs_index;
- }
-
- // System libraries can have a lot of symbols with versions. Using a
- // fixed buffer for computing the versions name (foo@ver) can save a
- // lot of allocations.
- SmallString<0> versionedNameBuffer;
-
- // Add symbols to the symbol table.
- ArrayRef<Elf_Sym> syms = this->getGlobalELFSyms<ELFT>();
- for (size_t i = 0, e = syms.size(); i != e; ++i) {
- const Elf_Sym &sym = syms[i];
-
- // ELF spec requires that all local symbols precede weak or global
- // symbols in each symbol table, and the index of first non-local symbol
- // is stored to sh_info. If a local symbol appears after some non-local
- // symbol, that's a violation of the spec.
- StringRef name = CHECK2(sym.getName(stringTable), this);
- if (sym.getBinding() == STB_LOCAL) {
- Err(ctx) << this << ": invalid local symbol '" << name
- << "' in global part of symbol table";
- continue;
- }
-
- const uint16_t ver = versyms[i], idx = ver & ~VERSYM_HIDDEN;
- if (sym.isUndefined()) {
- // Index 0 (VER_NDX_LOCAL) is used for unversioned undefined symbols.
- // GNU ld versions between 2.35 and 2.45 also generate VER_NDX_GLOBAL
- // for this case (https://sourceware.org/PR33577).
- if (ver != VER_NDX_LOCAL && ver != VER_NDX_GLOBAL) {
- if (idx >= verneeds.size()) {
- ErrAlways(ctx) << "corrupt input file: version need index " << idx
- << " for symbol " << name
- << " is out of bounds\n>>> defined in " << this;
- continue;
- }
- StringRef verName = stringTable.data() + verneeds[idx];
- versionedNameBuffer.clear();
- name = ss.save((name + "@" + verName).toStringRef(versionedNameBuffer));
- }
- Symbol *s = ctx.symtab->addSymbol(
- Undefined{this, name, sym.getBinding(), sym.st_other, sym.getType()});
- s->isExported = true;
- if (sym.getBinding() != STB_WEAK &&
- ctx.arg.unresolvedSymbolsInShlib != UnresolvedPolicy::Ignore)
- requiredSymbols.push_back(s);
- continue;
- }
-
- if (ver == VER_NDX_LOCAL ||
- (ver != VER_NDX_GLOBAL && idx >= verdefs.size())) {
- // In GNU ld < 2.31 (before 3be08ea4728b56d35e136af4e6fd3086ade17764), the
- // MIPS port puts _gp_disp symbol into DSO files and incorrectly assigns
- // VER_NDX_LOCAL. Workaround this bug.
- if (ctx.arg.emachine == EM_MIPS && name == "_gp_disp")
- continue;
- ErrAlways(ctx) << "corrupt input file: version definition index " << idx
- << " for symbol " << name
- << " is out of bounds\n>>> defined in " << this;
- continue;
- }
-
- uint32_t alignment = getAlignment<ELFT>(sections, sym);
- if (ver == idx) {
- auto *s = ctx.symtab->addSymbol(
- SharedSymbol{*this, name, sym.getBinding(), sym.st_other,
- sym.getType(), sym.st_value, sym.st_size, alignment});
- s->dsoDefined = true;
- if (s->file == this)
- s->versionId = ver;
- }
-
- // Also add the symbol with the versioned name to handle undefined symbols
- // with explicit versions.
- if (ver == VER_NDX_GLOBAL)
- continue;
-
- StringRef verName =
- stringTable.data() +
- reinterpret_cast<const Elf_Verdef *>(verdefs[idx])->getAux()->vda_name;
- versionedNameBuffer.clear();
- name = (name + "@" + verName).toStringRef(versionedNameBuffer);
- auto *s = ctx.symtab->addSymbol(
- SharedSymbol{*this, ss.save(name), sym.getBinding(), sym.st_other,
- sym.getType(), sym.st_value, sym.st_size, alignment});
- s->dsoDefined = true;
- if (s->file == this)
- s->versionId = idx;
+// Resolve one dynsym entry of a shared file into sym, mirroring the per-symbol
+// body of SharedFile::parse. Shared by the parallel resolution and the -y
+// traced replay. sym already holds the (possibly versioned) name.
+template <class ELFT>
+static void resolveSharedSymbol(Ctx &ctx, Symbol &sym, SharedFile &sf,
+ uint32_t elfIdx, bool isDef,
+ uint16_t versionId) {
+ const typename ELFT::Sym &eSym = sf.template getELFSyms<ELFT>()[elfIdx];
+ if (!isDef) {
+ sym.resolve(ctx, Undefined{&sf, sym.getName(), eSym.getBinding(),
+ eSym.st_other, eSym.getType()});
+ sym.isExported = true;
+ } else {
+ uint32_t alignment =
+ getAlignment<ELFT>(sf.template getELFShdrs<ELFT>(), eSym);
+ sym.resolve(ctx, SharedSymbol{sf, sym.getName(), eSym.getBinding(),
+ eSym.st_other, eSym.getType(), eSym.st_value,
+ eSym.st_size, alignment});
+ sym.dsoDefined = true;
+ if (sym.file == &sf)
+ sym.versionId = versionId;
}
}
@@ -1894,47 +1601,13 @@ static void createBitcodeSymbol(Ctx &ctx, Symbol *&sym,
}
}
-void BitcodeFile::parse() {
- for (std::pair<StringRef, Comdat::SelectionKind> s : obj->getComdatTable()) {
+// addComdatGroup is owner-idempotent: the parallel parse pipeline may have
+// already registered this file as the owner.
+void BitcodeFile::parseComdats() {
+ for (std::pair<StringRef, Comdat::SelectionKind> s : obj->getComdatTable())
keptComdats.push_back(
s.second == Comdat::NoDeduplicate ||
- ctx.symtab->comdatGroups.try_emplace(CachedHashStringRef(s.first), this)
- .second);
- }
-
- if (numSymbols == 0) {
- numSymbols = obj->symbols().size();
- symbols = std::make_unique<Symbol *[]>(numSymbols);
- }
- // Process defined symbols first. See the comment in
- // ObjFile<ELFT>::initializeSymbols.
- for (auto [i, irSym] : llvm::enumerate(obj->symbols()))
- if (!irSym.isUndefined())
- createBitcodeSymbol(ctx, symbols[i], irSym, *this);
- for (auto [i, irSym] : llvm::enumerate(obj->symbols()))
- if (irSym.isUndefined())
- createBitcodeSymbol(ctx, symbols[i], irSym, *this);
-
- for (auto l : obj->getDependentLibraries())
- addDependentLibrary(ctx, l, this);
-}
-
-void BitcodeFile::parseLazy() {
- numSymbols = obj->symbols().size();
- symbols = std::make_unique<Symbol *[]>(numSymbols);
- for (auto [i, irSym] : llvm::enumerate(obj->symbols())) {
- // Symbols can be duplicated in bitcode files because of '#include' and
- // linkonce_odr. Use uniqueSaver to save symbol names for de-duplication.
- // Update objSym.Name to reference (via StringRef) the string saver's copy;
- // this way LTO can reference the same string saver's copy rather than
- // keeping copies of its own.
- irSym.Name = ctx.uniqueSaver.save(irSym.getName());
- if (!irSym.isUndefined()) {
- auto *sym = ctx.symtab->insert(irSym.getName());
- sym->resolve(ctx, LazySymbol{*this});
- symbols[i] = sym;
- }
- }
+ ctx.symtab->addComdatGroup(CachedHashStringRef(s.first), this) == this);
}
void BitcodeFile::postParse() {
@@ -1981,9 +1654,6 @@ void BinaryFile::parse() {
InputFile *elf::createInternalFile(Ctx &ctx, StringRef name) {
auto *file =
make<InputFile>(ctx, InputFile::InternalKind, MemoryBufferRef("", name));
- // References from an internal file do not lead to --warn-backrefs
- // diagnostics.
- file->groupId = 0;
return file;
}
@@ -2012,32 +1682,6 @@ std::unique_ptr<ELFFileBase> elf::createObjFile(Ctx &ctx, MemoryBufferRef mb,
return f;
}
-template <class ELFT> void ObjFile<ELFT>::parseLazy() {
- const ArrayRef<typename ELFT::Sym> eSyms = this->getELFSyms<ELFT>();
- numSymbols = eSyms.size();
- symbols = std::make_unique<Symbol *[]>(numSymbols);
-
- // resolve() may trigger this->extract() if an existing symbol is an undefined
- // symbol. If that happens, this function has served its purpose, and we can
- // exit from the loop early.
- auto *symtab = ctx.symtab.get();
- for (size_t i = firstGlobal, end = eSyms.size(); i != end; ++i) {
- if (eSyms[i].st_shndx == SHN_UNDEF)
- continue;
- symbols[i] = symtab->insert(CHECK2(eSyms[i].getName(stringTable), this));
- symbols[i]->resolve(ctx, LazySymbol{*this});
- if (!lazy)
- break;
- }
-}
-
-bool InputFile::shouldExtractForCommon(StringRef name) const {
- if (isa<BitcodeFile>(this))
- return isBitcodeNonCommonDef(mb, name, archiveName);
-
- return isNonCommonDef(ctx, mb, name, archiveName);
-}
-
std::string elf::replaceThinLTOSuffix(Ctx &ctx, StringRef path) {
auto [suffix, repl] = ctx.arg.thinLTOObjectSuffixReplace;
if (path.consume_back(suffix))
@@ -2045,12 +1689,1248 @@ std::string elf::replaceThinLTOSuffix(Ctx &ctx, StringRef path) {
return std::string(path);
}
+//===----------------------------------------------------------------------===//
+// Parallel input file parsing and symbol resolution pipeline.
+//
+// Pipeline::run drives one batch of input files: POD symbol records are read
+// per file in parallel and counting-sorted into hash buckets, archive members
+// are extracted to a fixpoint (order-independent, mold/wild-style), and
+// symbols are created and resolved per bucket, then ordered by their serial
+// insertion point so that the output .symtab matches the serial linker.
+// Pipeline::epilogue runs the order-sensitive side effects serially.
+//
+//===----------------------------------------------------------------------===//
+
+namespace {
+constexpr uint32_t numShards = SymbolTable::numShards;
+
+// SymRecord flags.
+enum : uint8_t {
+ FDef = 1, // defined, including COMMON
+ FWeak = 2, // STB_WEAK
+ FBitcode = 4, // from a bitcode file
+ FShared = 8, // from a shared file
+ FCommon = 16, // COMMON definition
+ FHasAt = 32, // the name contains '@'
+};
+
+struct SymRecord {
+ const char *name;
+ uint32_t stemLen; // bucket key length (name minus a @@ suffix)
+ uint32_t nameLen; // full name length
+ uint32_t hash; // DenseMap hash of the stem
+ uint32_t nameId; // index into Bucket::names; written in phase 2
+ uint32_t elfIdx; // symbol index within the file's symbol/IR table
+ uint16_t versionId; // shared symbol version (FShared records only)
+ uint8_t flags;
+
+ StringRef stem() const { return StringRef(name, stemLen); }
+};
+
+// POD mirror of CachedHashStringRef (default-constructible).
+struct CachedName {
+ const char *data;
+ uint32_t size;
+ uint32_t hash;
+ // Index into the source file's comdatSecs (comdat signatures only).
+ uint32_t srcIdx = 0;
+ CachedHashStringRef ref() const {
+ return CachedHashStringRef(StringRef(data, size), hash);
+ }
+};
+
+struct FileData {
+ SmallVector<SymRecord, 0> records; // stably bucketed by hash % numShards
+ uint32_t bucketStart[numShards + 1] = {};
+ // GRP_COMDAT signatures, bucketed by hash; section order within a bucket.
+ SmallVector<CachedName, 0> comdats;
+ uint32_t comdatStart[numShards + 1] = {};
+ bool eligible = false; // participates in the pipeline
+ bool compatible = false; // passed the compatibility check
+ bool dupSoname = false; // DSO whose soname is already registered
+};
+
+// A node of a per-name singly-linked chain. Each name has two disjoint
+// chains, definitions and undefined references, so one link field suffices.
+struct RefNode {
+ uint32_t fileIdx;
+ uint32_t recIdx;
+ uint32_t next = UINT32_MAX;
+};
+
+struct NameInfo {
+ // The last @@-versioned spelling; serial insert() renames on each such
+ // insertion.
+ const char *verName = nullptr;
+ Symbol *sym = nullptr;
+ // Output order key: the earliest resolution event; seeds use (0, seedIdx).
+ // UINT32_MAX rank means no file inserted the name, so it is dropped.
+ uint64_t anchorSub = UINT64_MAX;
+ uint32_t anchorRank = UINT32_MAX;
+ uint32_t firstUndef = UINT32_MAX, lastUndef = UINT32_MAX;
+ uint32_t firstDef = UINT32_MAX, lastDef = UINT32_MAX;
+ uint32_t verNameLen = 0;
+ uint32_t seedIdx = UINT32_MAX; // pre-parseFiles symVector index
+ uint32_t outIdx = UINT32_MAX; // final symVector index
+};
+
+struct Bucket {
+ DenseMap<CachedHashStringRef, int> map;
+ SmallVector<NameInfo, 0> names;
+ SmallVector<RefNode, 0> refs;
+};
+
+// A symbol's serial insertion point, ordering the installed symbol vector.
+struct OrderItem {
+ uint32_t ord;
+ uint64_t sub;
+ uint32_t bucket, nameId;
+ bool operator<(const OrderItem &o) const {
+ return std::tie(ord, sub, bucket, nameId) <
+ std::tie(o.ord, o.sub, o.bucket, o.nameId);
+ }
+};
+
+template <class ELFT> struct Pipeline {
+ Ctx &ctx;
+ SmallVector<InputFile *, 0> files; // the batch to process
+ SmallVector<FileData, 0> fd;
+ std::array<Bucket, numShards> buckets;
+ // Extractions in command-line order, for --why-extract.
+ struct Extraction {
+ uint32_t member, trigFile, bucket, nameId;
+ };
+ SmallVector<Extraction, 0> extractions;
+ uint32_t bucketBase[numShards + 1]; // global name id = base[bucket] + nameId
+ size_t firstObjFile = 0; // this batch's start in ctx.objectFiles
+ // A late batch (dependent libraries, LTO outputs, reactivate) extends the
+ // installed symbol table in place.
+ bool incremental;
+ // LTO outputs are parsed with ignoreComdats: their comdat groups were already
+ // resolved before LTO and must not be re-registered.
+ bool ignoreComdats;
+ // Reactivate: lazy symbols whose members should be extracted. activate seeds
+ // these (only) as pending references, so their members are pulled in.
+ ArrayRef<Symbol *> triggers;
+
+ Pipeline(Ctx &ctx, SmallVector<InputFile *, 0> files, bool incremental,
+ ArrayRef<Symbol *> triggers = {}, bool ignoreComdats = false)
+ : ctx(ctx), files(std::move(files)), incremental(incremental),
+ ignoreComdats(ignoreComdats), triggers(triggers) {}
+
+ void run();
+ void readSymbols();
+ void readObj(uint32_t i);
+ void readShared(uint32_t i);
+ void readBitcode(uint32_t i);
+ void buildNameDB();
+ void activate();
+ void registerComdats();
+ void resolveSymbols();
+ void resolveName(Bucket &b, uint32_t nameId);
+ void applyRecord(Symbol *sym, InputFile *file, const SymRecord &rec,
+ bool isDef);
+ void replayTraced(InputFile *file, const FileData &d, bool phaseSplit,
+ bool defsOnly);
+
+ // The resolved symbol for a record, located via its hash bucket and name id.
+ Symbol *symOf(const SymRecord &rec) {
+ return buckets[rec.hash % numShards].names[rec.nameId].sym;
+ }
+
+ // Any record of the name (all records of a name share the stem and hash).
+ const SymRecord &recOf(const Bucket &bu, const NameInfo &ni) const {
+ const RefNode &node =
+ bu.refs[ni.firstDef != UINT32_MAX ? ni.firstDef : ni.firstUndef];
+ return fd[node.fileIdx].records[node.recIdx];
+ }
+
+ void wireSymbols();
+ void recordExtractions();
+ void epilogue();
+ void initSections();
+
+ void addRecord(SmallVectorImpl<SymRecord> &tmp, StringRef name,
+ uint32_t elfIdx, uint8_t flags, uint16_t versionId = 0) {
+ SymRecord r;
+ r.name = name.data();
+ r.nameLen = name.size();
+ auto [stemLen, hasAt] = getSymbolStem(name);
+ r.stemLen = stemLen;
+ if (hasAt)
+ flags |= FHasAt;
+ r.hash = CachedHashStringRef(StringRef(r.name, r.stemLen)).hash();
+ r.nameId = UINT32_MAX;
+ r.elfIdx = elfIdx;
+ r.versionId = versionId;
+ r.flags = flags;
+ tmp.push_back(r);
+ }
+};
+
+// Stable counting sort into numShards buckets by hash, recording the bucket
+// boundaries in start[].
+template <class T, class HashFn>
+static void bucketSort(SmallVectorImpl<T> &dst, ArrayRef<T> tmp,
+ uint32_t (&start)[numShards + 1], HashFn hash) {
+ uint32_t count[numShards] = {};
+ for (const T &r : tmp)
+ ++count[hash(r) % numShards];
+ uint32_t sum = 0;
+ for (uint32_t i = 0; i != numShards; ++i) {
+ start[i] = sum;
+ sum += count[i];
+ }
+ start[numShards] = sum;
+ uint32_t cursor[numShards];
+ memcpy(cursor, start, sizeof(cursor));
+ dst.resize_for_overwrite(tmp.size());
+ for (const T &r : tmp)
+ dst[cursor[hash(r) % numShards]++] = r;
+}
+
+// Group the records by hash bucket for the parallel phases.
+static void bucketize(FileData &d, ArrayRef<SymRecord> tmp) {
+ bucketSort(d.records, tmp, d.bucketStart,
+ [](const SymRecord &r) { return r.hash; });
+}
+
+static void bucketizeComdats(FileData &d, ArrayRef<CachedName> tmp) {
+ bucketSort(d.comdats, tmp, d.comdatStart,
+ [](const CachedName &s) { return s.hash; });
+}
+
+// Record indices in symbol table order, which the bucketing loses. Only the
+// serial order-sensitive passes need it.
+static SmallVector<uint32_t, 0> symbolOrder(const FileData &d) {
+ SmallVector<uint32_t, 0> order;
+ order.resize_for_overwrite(d.records.size());
+ std::iota(order.begin(), order.end(), 0u);
+ llvm::stable_sort(order, [&d](uint32_t a, uint32_t b) {
+ const SymRecord &x = d.records[a], &y = d.records[b];
+ // A shared file's default-versioned definition emits two records at one
+ // symbol index; the unversioned name is inserted first.
+ return std::make_pair(x.elfIdx, x.flags & FHasAt) <
+ std::make_pair(y.elfIdx, y.flags & FHasAt);
+ });
+ return order;
+}
+
+} // namespace
+
+void elf::parallelForLPT(size_t numItems,
+ llvm::function_ref<uint64_t(uint32_t)> cost,
+ llvm::function_ref<void(uint32_t)> fn) {
+ SmallVector<std::pair<uint64_t, uint32_t>, 0> order;
+ order.resize_for_overwrite(numItems);
+ for (uint32_t i = 0; i != numItems; ++i)
+ order[i] = {cost(i), i};
+ llvm::stable_sort(
+ order, [](const auto &a, const auto &b) { return a.first > b.first; });
+ std::atomic<size_t> next{0};
+ auto worker = [&]() {
+ for (size_t i;
+ (i = next.fetch_add(1, std::memory_order_relaxed)) < numItems;)
+ fn(order[i].second);
+ };
+ parallel::TaskGroup tg;
+ for (size_t i = 0, e = std::min<size_t>(numItems, parallel::getThreadCount());
+ i != e; ++i)
+ tg.spawn(worker);
+}
+
+template <class ELFT> void Pipeline<ELFT>::readSymbols() {
+ fd.resize(files.size());
+
+ // Diagnose incompatible files in command-line order. Bitcode symbol names
+ // are saved here because the string savers are not thread-safe.
+ InputFile *firstObj = nullptr, *firstShared = nullptr, *firstBc = nullptr;
+ for (auto [i, f] : llvm::enumerate(files)) {
+ InputFile *first = firstObj ? firstObj : firstShared;
+ fd[i].compatible = isCompatible(ctx, f, first ? first : firstBc);
+ if (!fd[i].compatible)
+ continue;
+ if (auto *bf = dyn_cast<BitcodeFile>(f)) {
+ for (const lto::InputFile::Symbol &irSym : bf->obj->symbols())
+ irSym.Name = ctx.uniqueSaver.save(irSym.getName());
+ fd[i].eligible = true;
+ } else if (isa<SharedFile>(f) || f->kind() == InputFile::ObjKind) {
+ fd[i].eligible = true;
+ }
+ if (f->lazy)
+ continue;
+ if (f->kind() == InputFile::ObjKind) {
+ if (!firstObj)
+ firstObj = f;
+ } else if (f->kind() == InputFile::SharedKind) {
+ if (!firstShared)
+ firstShared = f;
+ } else if (f->kind() == InputFile::BitcodeKind) {
+ if (!firstBc)
+ firstBc = f;
+ }
+ }
+
+ // Largest symbol tables first: reading a big file last leaves the other
+ // workers idle for its whole duration.
+ auto cost = [&](uint32_t i) -> uint64_t {
+ if (!fd[i].eligible)
+ return 0;
+ if (auto *bf = dyn_cast<BitcodeFile>(files[i]))
+ return bf->obj->symbols().size();
+ return cast<ELFFileBase>(files[i])->template getELFSyms<ELFT>().size();
+ };
+ parallelForLPT(files.size(), cost, [&](uint32_t i) {
+ if (!fd[i].eligible)
+ return;
+ switch (files[i]->kind()) {
+ case InputFile::ObjKind:
+ readObj(i);
+ break;
+ case InputFile::SharedKind:
+ readShared(i);
+ break;
+ case InputFile::BitcodeKind:
+ readBitcode(i);
+ break;
+ default:
+ llvm_unreachable("unexpected file kind");
+ }
+ });
+
+ // DSOs are uniquified by soname; a duplicate only merges isNeeded into the
+ // canonical file. Registering here lets the later phases skip its records.
+ for (auto [i, f] : llvm::enumerate(files)) {
+ auto *sf = dyn_cast<SharedFile>(f);
+ if (!sf || !fd[i].eligible)
+ continue;
+ auto [it, inserted] =
+ ctx.symtab->soNames.try_emplace(CachedHashStringRef(sf->soName), sf);
+ if (sf->isNeeded)
+ it->second->isNeeded.store(true, std::memory_order_relaxed);
+ if (inserted)
+ continue;
+ fd[i].dupSoname = true;
+ fd[i].records.clear();
+ memset(fd[i].bucketStart, 0, sizeof(fd[i].bucketStart));
+ }
+}
+
+template <class ELFT> void Pipeline<ELFT>::readObj(uint32_t i) {
+ auto *f = cast<ObjFile<ELFT>>(files[i]);
+ ArrayRef<typename ELFT::Sym> eSyms = f->template getELFSyms<ELFT>();
+ uint32_t firstGlobal = f->firstGlobal;
+ StringRef strtab = f->getStringTable();
+ SmallVector<SymRecord, 0> tmp;
+ tmp.reserve(eSyms.size() - firstGlobal);
+ for (size_t j = firstGlobal, e = eSyms.size(); j != e; ++j) {
+ const typename ELFT::Sym &eSym = eSyms[j];
+ Expected<StringRef> name = eSym.getName(strtab);
+ if (!name) {
+ Err(ctx) << f << ": " << name.takeError();
+ break;
+ }
+ uint8_t flags = 0;
+ if (eSym.st_shndx != SHN_UNDEF)
+ flags |= FDef;
+ if (eSym.st_shndx == SHN_COMMON) {
+ flags |= FCommon;
+ f->hasCommonSyms = true;
+ }
+ if (eSym.getBinding() == STB_WEAK)
+ flags |= FWeak;
+ addRecord(tmp, *name, j, flags);
+ }
+ if (!f->justSymbols)
+ f->scanEarlySections();
+ // Derive the comdat signatures. A global signature symbol reuses its record's
+ // name and hash; the hash is of the stem, so a '@'-containing name rehashes.
+ auto sigOf = [&](uint32_t symIdx) {
+ if (uint32_t k = symIdx - firstGlobal; k < tmp.size()) {
+ const SymRecord &rec = tmp[k];
+ StringRef name(rec.name, rec.nameLen);
+ return rec.flags & FHasAt ? CachedHashStringRef(name)
+ : CachedHashStringRef(name, rec.hash);
+ }
+ return CachedHashStringRef(
+ StringRef(strtab.data() + eSyms[symIdx].st_name));
+ };
+ SmallVector<CachedName, 0> sigs;
+ sigs.reserve(f->comdatSecs.size());
+ for (auto [j, cs] : llvm::enumerate(f->comdatSecs)) {
+ if (cs.sigSym == UINT32_MAX)
+ continue;
+ CachedHashStringRef sig = sigOf(cs.sigSym);
+ sigs.push_back({sig.val().data(), (uint32_t)sig.val().size(), sig.hash(),
+ (uint32_t)j});
+ }
+ bucketizeComdats(fd[i], sigs);
+ bucketize(fd[i], tmp);
+}
+
+// Read a shared file's dynamic tags and version sections and record its dynsym
+// entries. Resolution runs in resolveName, registration in the epilogue.
+template <class ELFT> void Pipeline<ELFT>::readShared(uint32_t i) {
+ using Elf_Dyn = typename ELFT::Dyn;
+ using Elf_Shdr = typename ELFT::Shdr;
+ using Elf_Sym = typename ELFT::Sym;
+ using Elf_Verdef = typename ELFT::Verdef;
+ using Elf_Versym = typename ELFT::Versym;
+ auto *f = cast<SharedFile>(files[i]);
+ const ELFFile<ELFT> obj = f->template getObj<ELFT>();
+ ArrayRef<Elf_Shdr> sections = f->template getELFShdrs<ELFT>();
+ const Elf_Shdr *versymSec = nullptr, *verdefSec = nullptr,
+ *verneedSec = nullptr;
+ ArrayRef<Elf_Dyn> dynamicTags;
+ for (const Elf_Shdr &sec : sections) {
+ switch (sec.sh_type) {
+ case SHT_DYNAMIC:
+ dynamicTags =
+ CHECK2(obj.template getSectionContentsAsArray<Elf_Dyn>(sec), f);
+ break;
+ case SHT_GNU_versym:
+ versymSec = &sec;
+ break;
+ case SHT_GNU_verdef:
+ verdefSec = &sec;
+ break;
+ case SHT_GNU_verneed:
+ verneedSec = &sec;
+ break;
+ }
+ }
+
+ if (versymSec && f->template getELFSyms<ELFT>().empty()) {
+ ErrAlways(ctx) << "SHT_GNU_versym should be associated with symbol table";
+ return;
+ }
+
+ StringRef strtab = f->getStringTable();
+ // DT_SONAME (the deduplication key) and DT_NEEDED.
+ for (const Elf_Dyn &dyn : dynamicTags) {
+ if (dyn.d_tag == DT_NEEDED) {
+ uint64_t val = dyn.getVal();
+ if (val >= strtab.size()) {
+ Err(ctx) << f << ": invalid DT_NEEDED entry";
+ return;
+ }
+ f->dtNeeded.push_back(strtab.data() + val);
+ } else if (dyn.d_tag == DT_SONAME) {
+ uint64_t val = dyn.getVal();
+ if (val >= strtab.size()) {
+ Err(ctx) << f << ": invalid DT_SONAME entry";
+ return;
+ }
+ f->soName = strtab.data() + val;
+ }
+ }
+
+ f->verdefs = parseVerdefs<ELFT>(obj.base(), verdefSec);
+ std::vector<uint32_t> verneeds =
+ f->template parseVerneed<ELFT>(obj, verneedSec);
+
+ uint32_t firstGlobal = f->firstGlobal;
+ size_t size = f->template getELFSyms<ELFT>().size() - firstGlobal;
+ std::vector<uint16_t> versyms(size, VER_NDX_GLOBAL);
+ if (versymSec && size) {
+ ArrayRef<Elf_Versym> v =
+ CHECK2(obj.template getSectionContentsAsArray<Elf_Versym>(*versymSec),
+ f)
+ .slice(firstGlobal);
+ for (size_t j = 0; j < size; ++j)
+ versyms[j] = v[j].vs_index;
+ }
+
+ // Versioned names (foo@ver) are built in the thread-local arena so they
+ // outlive this parallel phase without touching the shared string saver.
+ auto saveVersioned = [](StringRef name, StringRef ver) {
+ size_t n = name.size() + 1 + ver.size();
+ char *buf = makeThreadLocalN<char>(n);
+ memcpy(buf, name.data(), name.size());
+ buf[name.size()] = '@';
+ memcpy(buf + name.size() + 1, ver.data(), ver.size());
+ return StringRef(buf, n);
+ };
+
+ ArrayRef<Elf_Sym> syms = f->template getGlobalELFSyms<ELFT>();
+ SmallVector<SymRecord, 0> tmp;
+ tmp.reserve(syms.size());
+ for (size_t j = 0, e = syms.size(); j != e; ++j) {
+ const Elf_Sym &sym = syms[j];
+ StringRef name = CHECK2(sym.getName(strtab), f);
+ if (sym.getBinding() == STB_LOCAL) {
+ Err(ctx) << f << ": invalid local symbol '" << name
+ << "' in global part of symbol table";
+ continue;
+ }
+ uint32_t elfIdx = firstGlobal + j;
+ const uint16_t ver = versyms[j], idx = ver & ~VERSYM_HIDDEN;
+ uint8_t base = FShared | (sym.getBinding() == STB_WEAK ? FWeak : 0);
+
+ if (sym.isUndefined()) {
+ // Index 0 (VER_NDX_LOCAL) is used for unversioned undefined symbols. GNU
+ // ld versions between 2.35 and 2.45 also generate VER_NDX_GLOBAL for
+ // this case (https://sourceware.org/PR33577).
+ if (ver != VER_NDX_LOCAL && ver != VER_NDX_GLOBAL) {
+ if (idx >= verneeds.size()) {
+ ErrAlways(ctx) << "corrupt input file: version need index " << idx
+ << " for symbol " << name
+ << " is out of bounds\n>>> defined in " << f;
+ continue;
+ }
+ name = saveVersioned(name, strtab.data() + verneeds[idx]);
+ }
+ addRecord(tmp, name, elfIdx, base);
+ continue;
+ }
+
+ if (ver == VER_NDX_LOCAL ||
+ (ver != VER_NDX_GLOBAL && idx >= f->verdefs.size())) {
+ // In GNU ld < 2.31 the MIPS port put _gp_disp with VER_NDX_LOCAL.
+ if (ctx.arg.emachine == EM_MIPS && name == "_gp_disp")
+ continue;
+ ErrAlways(ctx) << "corrupt input file: version definition index " << idx
+ << " for symbol " << name
+ << " is out of bounds\n>>> defined in " << f;
+ continue;
+ }
+
+ if (ver == idx)
+ addRecord(tmp, name, elfIdx, base | FDef, ver);
+
+ // Also register the versioned name to satisfy explicitly versioned refs.
+ if (ver == VER_NDX_GLOBAL)
+ continue;
+ StringRef verName =
+ strtab.data() + reinterpret_cast<const Elf_Verdef *>(f->verdefs[idx])
+ ->getAux()
+ ->vda_name;
+ addRecord(tmp, saveVersioned(name, verName), elfIdx, base | FDef, idx);
+ }
+ bucketize(fd[i], tmp);
+}
+
+template <class ELFT> void Pipeline<ELFT>::readBitcode(uint32_t i) {
+ auto *f = cast<BitcodeFile>(files[i]);
+ SmallVector<SymRecord, 0> tmp;
+ for (auto [j, irSym] : llvm::enumerate(f->obj->symbols())) {
+ uint8_t flags = FBitcode;
+ if (!irSym.isUndefined())
+ flags |= FDef;
+ if (irSym.isWeak())
+ flags |= FWeak;
+ if (irSym.isCommon())
+ flags |= FCommon;
+ addRecord(tmp, irSym.getName(), j, flags);
+ }
+ bucketize(fd[i], tmp);
+ SmallVector<CachedName, 0> sigs;
+ for (auto s : f->obj->getComdatTable())
+ if (s.second != Comdat::NoDeduplicate)
+ sigs.push_back({s.first.data(), (uint32_t)s.first.size(),
+ CachedHashStringRef(s.first).hash()});
+ bucketizeComdats(fd[i], sigs);
+}
+
+template <class ELFT> void Pipeline<ELFT>::buildNameDB() {
+ // Each bucket draws its seeds from the shard of the same index: shard routing
+ // and bucket routing share the name hash, and both key by the stem. A first
+ // batch replaces the symbol table, so it copies the whole shard; a late batch
+ // only extends it, so it looks up the names it actually sees.
+ ArrayRef<Symbol *> symVec = ctx.symtab->getSymbols();
+ size_t total = 0;
+ uint32_t bucketTotals[numShards] = {};
+ for (const FileData &d : fd) {
+ total += d.records.size();
+ for (uint32_t b = 0; b != numShards; ++b)
+ bucketTotals[b] += d.bucketStart[b + 1] - d.bucketStart[b];
+ }
+
+ parallelFor(0, numShards, [&](size_t b) {
+ Bucket &bu = buckets[b];
+ const auto &shard = ctx.symtab->getShards()[b];
+ // Shard loads deviate several percent from the mean, so size refs exactly
+ // rather than paying a mid-build reallocation.
+ size_t seeds = incremental ? 0 : shard.size();
+ bu.names.reserve(total / numShards / 4 + seeds);
+ bu.refs.reserve(bucketTotals[b]);
+ bu.map.reserve(total / numShards / 4 + seeds);
+ if (!incremental)
+ for (const auto &kv : shard) {
+ bu.map.try_emplace(kv.first, bu.names.size());
+ NameInfo &ni = bu.names.emplace_back();
+ ni.seedIdx = kv.second;
+ ni.sym = symVec[kv.second];
+ }
+ auto append = [&bu](uint32_t &first, uint32_t &last, uint32_t idx) {
+ if (first == UINT32_MAX)
+ first = idx;
+ else
+ bu.refs[last].next = idx;
+ last = idx;
+ };
+ for (auto [i, d] : llvm::enumerate(fd)) {
+ for (uint32_t r = d.bucketStart[b], e = d.bucketStart[b + 1]; r != e;
+ ++r) {
+ SymRecord &rec = d.records[r];
+ CachedHashStringRef key(rec.stem(), rec.hash);
+ auto [it, inserted] = bu.map.try_emplace(key, bu.names.size());
+ if (inserted) {
+ NameInfo &n = bu.names.emplace_back();
+ if (incremental) {
+ if (auto sit = shard.find(key); sit != shard.end()) {
+ n.seedIdx = sit->second;
+ n.sym = symVec[sit->second];
+ }
+ }
+ }
+ uint32_t nameId = it->second;
+ rec.nameId = nameId;
+ NameInfo &ni = bu.names[nameId];
+ uint32_t refIdx = bu.refs.size();
+ RefNode &node = bu.refs.emplace_back();
+ node.fileIdx = i;
+ node.recIdx = r;
+ if (rec.flags & FDef)
+ append(ni.firstDef, ni.lastDef, refIdx);
+ else
+ append(ni.firstUndef, ni.lastUndef, refIdx);
+ if (rec.stemLen != rec.nameLen) {
+ ni.verName = rec.name;
+ ni.verNameLen = rec.nameLen;
+ }
+ }
+ }
+ });
+
+ bucketBase[0] = 0;
+ for (uint32_t b = 0; b != numShards; ++b)
+ bucketBase[b + 1] = bucketBase[b] + buckets[b].names.size();
+}
+
+template <class ELFT> void Pipeline<ELFT>::activate() {
+ // A lazy member is pulled in if a non-weak undefined reference anywhere names
+ // a symbol whose first definition is that member, to a fixpoint. Determinism
+ // comes from file index, not scan order.
+ uint32_t numNames = bucketBase[numShards];
+ const bool fortranCommon = ctx.arg.fortranCommon;
+ auto globalId = [&](const SymRecord &rec) {
+ return bucketBase[rec.hash % numShards] + rec.nameId;
+ };
+ // Snapshot the lazy flags: extraction clears files[i]->lazy, but the
+ // decisions must stay a function of the pre-activation state.
+ SmallVector<uint8_t, 0> wasLazy(files.size());
+ for (auto [i, f] : llvm::enumerate(files))
+ wasLazy[i] = f->lazy;
+
+ // Walk a name's definition chain, summarizing each tier (0 = strong/regular,
+ // 1 = weak/tentative) and the first lazy non-tentative definition (the
+ // --fortran-common override target).
+ struct DefInfo {
+ uint32_t firstFile[2] = {UINT32_MAX, UINT32_MAX};
+ uint32_t lazyStrongDef = UINT32_MAX;
+ bool firstLazy[2] = {false, false};
+ bool eagerReg[2] = {false, false};
+ bool eagerCommon = false; // an eager or extracted file defines it as COMMON
+ };
+ auto summarize = [&](uint32_t b, uint32_t nameId) {
+ DefInfo di;
+ const Bucket &bu = buckets[b];
+ // A late batch does not contain the files parsed before it; the already
+ // resolved symbol stands in for their definitions.
+ const Symbol *seed = bu.names[nameId].seedIdx == UINT32_MAX
+ ? nullptr
+ : bu.names[nameId].sym;
+ if (seed && (seed->isDefined() || seed->isCommon() || seed->isShared())) {
+ unsigned t = seed->isWeak() || seed->isCommon() ? 1 : 0;
+ di.firstFile[t] = files.size();
+ di.eagerReg[t] = !seed->isShared();
+ di.eagerCommon = seed->isCommon();
+ }
+ for (uint32_t r = bu.names[nameId].firstDef; r != UINT32_MAX;
+ r = bu.refs[r].next) {
+ const RefNode &node = bu.refs[r];
+ const SymRecord &rec = fd[node.fileIdx].records[node.recIdx];
+ bool lazy = wasLazy[node.fileIdx];
+ unsigned t = (rec.flags & (FWeak | FCommon)) ? 1 : 0;
+ if (di.firstFile[t] == UINT32_MAX) {
+ di.firstFile[t] = node.fileIdx;
+ di.firstLazy[t] = lazy;
+ }
+ if (!lazy && !(rec.flags & FShared))
+ di.eagerReg[t] = true;
+ // --fortran-common: a COMMON is active once its file is eager or
+ // extracted; only a STB_GLOBAL non-tentative definition overrides it.
+ if (rec.flags & FCommon)
+ di.eagerCommon |= !files[node.fileIdx]->lazy;
+ else if (lazy && di.lazyStrongDef == UINT32_MAX && !(rec.flags & FWeak))
+ di.lazyStrongDef = node.fileIdx;
+ }
+ return di;
+ };
+ // The lazy member to pull in when the name is referenced. A reference
+ // resolves in its strongest tier; within that tier an eager regular
+ // definition wins and suppresses extraction, otherwise the first-seen
+ // definition wins. This matches mold/ld.bfd.
+ auto extractTarget = [](const DefInfo &di) -> uint32_t {
+ unsigned t = di.firstFile[0] != UINT32_MAX ? 0 : 1;
+ if (di.firstFile[t] != UINT32_MAX && !di.eagerReg[t] && di.firstLazy[t])
+ return di.firstFile[t];
+ return UINT32_MAX;
+ };
+
+ // Worklist of names referenced by a live non-weak undefined symbol. Each name
+ // is resolved once; if unsatisfied it extracts its first-seen lazy member,
+ // whose own references join the worklist. trig records the first referrer:
+ // UINT32_MAX until the name is queued, and files.size() for ctx.internalFile.
+ SmallVector<uint32_t, 0> trig(numNames, UINT32_MAX);
+ struct WorkItem {
+ uint32_t bucket, nameId;
+ };
+ SmallVector<WorkItem, 0> work;
+ auto pushName = [&](uint32_t id, uint32_t bucket, uint32_t nameId,
+ uint32_t file) {
+ if (trig[id] == UINT32_MAX) {
+ trig[id] = file;
+ work.push_back({bucket, nameId});
+ }
+ };
+ auto seedKey = [&](CachedHashStringRef key) {
+ uint32_t b = key.hash() % numShards;
+ auto it = buckets[b].map.find(key);
+ if (it != buckets[b].map.end())
+ pushName(bucketBase[b] + it->second, b, it->second,
+ (uint32_t)files.size());
+ };
+ if (!triggers.empty()) {
+ // A reactivate batch pulls in only the members defining the triggers.
+ for (Symbol *t : triggers) {
+ StringRef stem =
+ t->getName().take_front(getSymbolStem(t->getName()).first);
+ seedKey(CachedHashStringRef(stem));
+ }
+ } else {
+ // Already resolved non-weak undefined references (e.g. -u) and every
+ // non-weak undefined reference of an eager (non-lazy) file.
+ for (uint32_t b = 0; b != numShards; ++b)
+ for (auto [id, ni] : llvm::enumerate(buckets[b].names))
+ if (ni.seedIdx != UINT32_MAX && ni.sym->isUndefined() &&
+ !ni.sym->isWeak())
+ pushName(bucketBase[b] + id, b, id, (uint32_t)files.size());
+ for (auto [i, f] : llvm::enumerate(files)) {
+ if (!fd[i].compatible || f->lazy)
+ continue;
+ for (const SymRecord &rec : fd[i].records)
+ if (!(rec.flags & (FDef | FWeak)) ||
+ (fortranCommon && (rec.flags & FCommon)))
+ pushName(globalId(rec), rec.hash % numShards, rec.nameId, i);
+ }
+ }
+
+ while (!work.empty()) {
+ auto [b, nameId] = work.pop_back_val();
+ uint32_t id = bucketBase[b] + nameId;
+ DefInfo di = summarize(b, nameId);
+ uint32_t m = extractTarget(di);
+ // --fortran-common: a lazy non-tentative definition overrides an active
+ // COMMON that nothing else displaces.
+ if (fortranCommon && m == UINT32_MAX && di.eagerCommon &&
+ di.lazyStrongDef != UINT32_MAX)
+ m = di.lazyStrongDef;
+ if (m == UINT32_MAX || !files[m]->lazy)
+ continue; // satisfied, no lazy definition, or already extracted
+ files[m]->lazy = false;
+ extractions.push_back({m, trig[id], b, nameId});
+ for (const SymRecord &rec : fd[m].records)
+ if (!(rec.flags & (FDef | FWeak)) ||
+ (fortranCommon && (rec.flags & FCommon)))
+ pushName(globalId(rec), rec.hash % numShards, rec.nameId, m);
+ }
+}
+
+template <class ELFT> void Pipeline<ELFT>::registerComdats() {
+ if (ignoreComdats)
+ return;
+ // First-parsed file in serial order owns each comdat group.
+ llvm::TimeTraceScope comdatScope("Pre-populate comdat groups");
+ size_t numComdats = 0;
+ for (const FileData &d : fd)
+ numComdats += d.comdats.size();
+ parallelFor(0, numShards, [&](size_t s) {
+ ctx.symtab->comdatGroups[s].reserve(numComdats / numShards / 2);
+ for (auto [fi, f] : llvm::enumerate(files)) {
+ if (!fd[fi].compatible || f->lazy)
+ continue;
+ const FileData &d = fd[fi];
+ // Record the verdict so that initializeSections needs no lookup. Comdat
+ // entries are sharded by hash, so writes to comdatSecs are disjoint.
+ auto *obj =
+ f->kind() == InputFile::ObjKind ? cast<ObjFile<ELFT>>(f) : nullptr;
+ for (uint32_t i = d.comdatStart[s], e = d.comdatStart[s + 1]; i != e;
+ ++i) {
+ const CachedName &cn = d.comdats[i];
+ if (ctx.symtab->addComdatGroup(cn.ref(), f) != f && obj)
+ obj->comdatSecs[cn.srcIdx].prevailing = 0;
+ }
+ }
+ });
+}
+
+// The sole symbol-resolution dispatch, shared by the parallel resolveName and
+// the serial -y traced replay, so the two cannot diverge.
+template <class ELFT>
+void Pipeline<ELFT>::applyRecord(Symbol *sym, InputFile *file,
+ const SymRecord &rec, bool isDef) {
+ if (rec.flags & FShared) {
+ resolveSharedSymbol<ELFT>(ctx, *sym, *cast<SharedFile>(file), rec.elfIdx,
+ isDef, rec.versionId);
+ } else if (file->lazy) {
+ // An unextracted lazy file contributes only LazySymbol definitions; an
+ // earlier shared or bitcode definition suppresses them.
+ sym->resolve(ctx, LazySymbol{*file});
+ } else if (rec.flags & FBitcode) {
+ auto *bf = cast<BitcodeFile>(file);
+ createBitcodeSymbol(ctx, sym, bf->obj->symbols()[rec.elfIdx], *bf);
+ } else {
+ auto *obj = cast<ObjFile<ELFT>>(file);
+ resolveSymbol(ctx, obj, obj->template getELFSyms<ELFT>()[rec.elfIdx], *sym);
+ }
+}
+
+// Replay resolution events for -y traced names in symbol-table order, deferred
+// by resolveName so that the trace output is deterministic. phaseSplit visits
+// definitions first; defsOnly restricts to definitions.
+template <class ELFT>
+void Pipeline<ELFT>::replayTraced(InputFile *file, const FileData &d,
+ bool phaseSplit, bool defsOnly) {
+ SmallVector<uint32_t, 0> order = symbolOrder(d);
+ for (int phase = 0, end = phaseSplit ? 2 : 1; phase != end; ++phase)
+ for (uint32_t ri : order) {
+ const SymRecord &rec = d.records[ri];
+ bool isDef = rec.flags & FDef;
+ if ((defsOnly && !isDef) || (phaseSplit && (phase == 0) != isDef))
+ continue;
+ Symbol *sym = symOf(rec);
+ if (sym->traced)
+ applyRecord(sym, file, rec, isDef);
+ }
+}
+
+template <class ELFT>
+void Pipeline<ELFT>::resolveName(Bucket &bu, uint32_t nameId) {
+ NameInfo &ni = bu.names[nameId];
+ Symbol *sym = ni.sym;
+
+ // Apply the @@ rename and default flags. Serial insert() renames the symbol
+ // on every versioned insertion and flags any name containing '@'.
+ if (ni.verName) {
+ sym->setName(StringRef(ni.verName, ni.verNameLen));
+ sym->hasVersionSuffix = true;
+ } else if (ni.seedIdx == UINT32_MAX && (recOf(bu, ni).flags & FHasAt)) {
+ sym->hasVersionSuffix = true;
+ }
+
+ // Merge the definition and undefined-reference chains into one event stream
+ // ordered by (file, definitions first, symbol index), matching the serial
+ // linker. The output anchor ignores the phase: the file that first inserts
+ // the symbol.
+ uint32_t anchorRank = ni.seedIdx == UINT32_MAX ? UINT32_MAX : 0;
+ uint64_t anchorSub = ni.seedIdx == UINT32_MAX ? UINT64_MAX : ni.seedIdx;
+ const bool traced = sym->traced;
+ bool inserted = ni.seedIdx != UINT32_MAX;
+ auto key = [&](uint32_t r, uint64_t undefPhase) {
+ const RefNode &node = bu.refs[r];
+ return (uint64_t(node.fileIdx + 1) << 33) | (undefPhase << 32) |
+ fd[node.fileIdx].records[node.recIdx].elfIdx;
+ };
+ uint32_t dIt = ni.firstDef, uIt = ni.firstUndef;
+ for (;;) {
+ // An unextracted lazy file never inserts its undefined references.
+ while (uIt != UINT32_MAX && files[bu.refs[uIt].fileIdx]->lazy)
+ uIt = bu.refs[uIt].next;
+ if (dIt == UINT32_MAX && uIt == UINT32_MAX)
+ break;
+ bool isDef =
+ uIt == UINT32_MAX || (dIt != UINT32_MAX && key(dIt, 0) < key(uIt, 1));
+ uint32_t r = isDef ? dIt : uIt;
+ (isDef ? dIt : uIt) = bu.refs[r].next;
+ const RefNode &node = bu.refs[r];
+ uint32_t f = node.fileIdx;
+ const SymRecord &rec = fd[f].records[node.recIdx];
+ uint32_t rank = f + 1;
+ // Sub-order within a file: a bitcode file inserts every definition before
+ // its undefined references; a shared file inserts a symbol's unversioned
+ // name before its versioned one ('@').
+ uint64_t asub;
+ if (rec.flags & FBitcode)
+ asub = (uint64_t(!isDef) << 32) | rec.elfIdx;
+ else if (rec.flags & FShared)
+ asub = (uint64_t(rec.elfIdx) << 1) | bool(rec.flags & FHasAt);
+ else
+ asub = rec.elfIdx;
+ if (rank < anchorRank || (rank == anchorRank && asub < anchorSub)) {
+ anchorRank = rank;
+ anchorSub = asub;
+ }
+ if (traced)
+ continue;
+ inserted = true;
+ applyRecord(sym, files[f], rec, isDef);
+ }
+ ni.anchorRank = anchorRank;
+ ni.anchorSub = anchorSub;
+ if (!traced && !inserted)
+ ni.anchorRank = UINT32_MAX;
+}
+
+template <class ELFT> void Pipeline<ELFT>::resolveSymbols() {
+ // A late batch extends an already-installed symbol table: seeds are resolved
+ // in place and only the new names are ordered and appended.
+ auto isLive = [&](const NameInfo &ni) {
+ return ni.anchorRank != UINT32_MAX &&
+ !(incremental && ni.seedIdx != UINT32_MAX);
+ };
+
+ uint32_t counts[numShards];
+ {
+ llvm::TimeTraceScope scope1("Resolve buckets");
+ parallelFor(0, numShards, [&](size_t b) {
+ Bucket &bu = buckets[b];
+ size_t n = bu.names.size();
+ counts[b] = 0;
+ if (!n)
+ return;
+ SymbolUnion *storage = makeThreadLocalN<SymbolUnion>(n);
+ uint32_t live = 0;
+ for (size_t id = 0; id != n; ++id) {
+ NameInfo &ni = bu.names[id];
+ if (ni.seedIdx != UINT32_MAX) {
+ // A late batch resolves a pre-existing symbol in place so that
+ // references from already-parsed files stay valid.
+ if (!incremental) {
+ SymbolUnion *su = &storage[id];
+ memcpy(static_cast<void *>(su), ni.sym, sizeof(SymbolUnion));
+ ni.sym = reinterpret_cast<Symbol *>(su);
+ }
+ } else {
+ SymbolUnion *su = &storage[id];
+ memset(static_cast<void *>(su), 0, sizeof(SymbolUnion));
+ auto *s = reinterpret_cast<Symbol *>(su);
+ // The map key (any record's stem) is the initial name.
+ s->versionId = VER_NDX_GLOBAL;
+ s->setName(recOf(bu, ni).stem());
+ ni.sym = reinterpret_cast<Symbol *>(su);
+ }
+ resolveName(bu, id);
+ live += isLive(bu.names[id]);
+ }
+ counts[b] = live;
+ });
+ }
+
+ llvm::TimeTraceScope scope2("Order symbols");
+ // Order the live symbols by their serial insertion point and move them into
+ // the final storage. Names that no serial insertion event would have created
+ // are dropped before the sort.
+ uint32_t liveStart[numShards + 1];
+ uint32_t sum = 0;
+ for (uint32_t b = 0; b != numShards; ++b) {
+ liveStart[b] = sum;
+ sum += counts[b];
+ }
+ liveStart[numShards] = sum;
+ size_t live = sum;
+ SmallVector<OrderItem, 0> items;
+ items.resize_for_overwrite(live);
+ parallelFor(0, numShards, [&](size_t b) {
+ Bucket &bu = buckets[b];
+ OrderItem *out = items.begin() + liveStart[b];
+ for (auto [id, ni] : llvm::enumerate(bu.names))
+ if (isLive(ni))
+ *out++ = {ni.anchorRank, ni.anchorSub, (uint32_t)b, (uint32_t)id};
+ });
+ parallelSort(items.begin(), items.end());
+
+ SymbolUnion *out = getSpecificAllocSingleton<SymbolUnion>().Allocate(live);
+ if (incremental) {
+ // Seeds were resolved in place; append the new names, registering each in
+ // its hash shard.
+ for (auto [i, it] : llvm::enumerate(items)) {
+ Bucket &bu = buckets[it.bucket];
+ NameInfo &ni = bu.names[it.nameId];
+ memcpy(static_cast<void *>(&out[i]), ni.sym, sizeof(SymbolUnion));
+ ni.sym = reinterpret_cast<Symbol *>(&out[i]);
+ const SymRecord &rec = recOf(bu, ni);
+ ctx.symtab->appendShardedSymbol(CachedHashStringRef(rec.stem(), rec.hash),
+ ni.sym);
+ }
+ recordExtractions();
+ return;
+ }
+
+ SmallVector<Symbol *, 0> symVector(live);
+ parallelFor(0, live, [&](size_t i) {
+ const OrderItem &it = items[i];
+ NameInfo &ni = buckets[it.bucket].names[it.nameId];
+ memcpy(static_cast<void *>(&out[i]), ni.sym, sizeof(SymbolUnion));
+ ni.sym = reinterpret_cast<Symbol *>(&out[i]);
+ ni.outIdx = i;
+ symVector[i] = ni.sym;
+ });
+
+ // Rewrite the bucket map values to symVector indices and install.
+ parallelFor(0, numShards, [&](size_t b) {
+ Bucket &bu = buckets[b];
+ for (const NameInfo &ni : bu.names)
+ if (ni.outIdx == UINT32_MAX) {
+ const SymRecord &rec = recOf(bu, ni);
+ bu.map.erase(CachedHashStringRef(rec.stem(), rec.hash));
+ }
+ for (auto &kv : bu.map)
+ kv.second = bu.names[kv.second].outIdx;
+ });
+ std::array<DenseMap<CachedHashStringRef, int>, numShards> maps;
+ for (size_t b = 0; b != numShards; ++b)
+ maps[b] = std::move(buckets[b].map);
+ ctx.symtab->installShardedSymbols(maps, std::move(symVector));
+
+ recordExtractions();
+}
+
+template <class ELFT> void Pipeline<ELFT>::recordExtractions() {
+ if (ctx.arg.whyExtract.empty())
+ return;
+ for (const Extraction &ex : extractions) {
+ Symbol *sym = buckets[ex.bucket].names[ex.nameId].sym;
+ InputFile *trigger =
+ ex.trigFile == files.size() ? ctx.internalFile : files[ex.trigFile];
+ ctx.whyExtractRecords.emplace_back(toStr(ctx, trigger), files[ex.member],
+ *sym);
+ }
+}
+
+template <class ELFT> void Pipeline<ELFT>::wireSymbols() {
+ auto cost = [&](uint32_t i) -> uint64_t { return fd[i].records.size(); };
+ parallelForLPT(files.size(), cost, [&](uint32_t i) {
+ if (!fd[i].eligible)
+ return;
+ InputFile *f = files[i];
+ if (f->kind() == InputFile::ObjKind) {
+ bool inactiveLazy = f->lazy;
+ f->allocateSymbols();
+ MutableArrayRef<Symbol *> syms = f->getMutableSymbols();
+ for (const SymRecord &rec : fd[i].records) {
+ // An unextracted lazy file has only its definitions wired.
+ if (inactiveLazy && !(rec.flags & FDef))
+ continue;
+ Bucket &bu = buckets[rec.hash % numShards];
+ syms[rec.elfIdx] = bu.names[rec.nameId].sym;
+ }
+ } else if (f->kind() == InputFile::BitcodeKind) {
+ // resolveName resolved the bitcode symbols in place; wire the array.
+ auto *bf = cast<BitcodeFile>(f);
+ bool inactiveLazy = f->lazy;
+ bf->allocateSymbols(bf->obj->symbols().size());
+ MutableArrayRef<Symbol *> syms = bf->getMutableSymbols();
+ for (const SymRecord &rec : fd[i].records) {
+ if (inactiveLazy && !(rec.flags & FDef))
+ continue;
+ syms[rec.elfIdx] = symOf(rec);
+ }
+ } else if (f->kind() == InputFile::SharedKind &&
+ ctx.arg.unresolvedSymbolsInShlib != UnresolvedPolicy::Ignore) {
+ // Collect the DSO's strong undefined references for
+ // reportUndefinedSymbols.
+ auto *sf = cast<SharedFile>(f);
+ for (uint32_t ri : symbolOrder(fd[i])) {
+ const SymRecord &rec = fd[i].records[ri];
+ if (!(rec.flags & (FDef | FWeak)))
+ sf->requiredSymbols.push_back(symOf(rec));
+ }
+ }
+ });
+}
+
+template <class ELFT> void Pipeline<ELFT>::epilogue() {
+ // Run the order-sensitive side effects in command-line order: file
+ // registration (which determines output section order), dependent libraries,
+ // ARM attributes and -y traced replay.
+ firstObjFile = ctx.objectFiles.size();
+ for (auto [i, f] : llvm::enumerate(files)) {
+ if (!fd[i].compatible)
+ continue;
+ FileData &d = fd[i];
+ if (f->lazy) {
+ if (auto *bf = dyn_cast<BitcodeFile>(f)) {
+ // Unlike a lazy object, parseLazy has no early exit, so all
+ // definitions are visible.
+ ctx.lazyBitcodeFiles.push_back(bf);
+ if (ctx.symtab->hasTracedSymbol)
+ replayTraced(f, d, /*phaseSplit=*/false, /*defsOnly=*/true);
+ continue;
+ }
+ if (ctx.symtab->hasTracedSymbol && f->kind() == InputFile::ObjKind)
+ replayTraced(f, d, /*phaseSplit=*/false, /*defsOnly=*/true);
+ continue;
+ }
+ // -t traces the input files and extracted members, but not LTO outputs.
+ if (ctx.arg.trace && !ignoreComdats)
+ Msg(ctx) << f;
+ if (auto *bf = dyn_cast<BitcodeFile>(f)) {
+ ctx.bitcodeFiles.push_back(bf);
+ bf->parseComdats();
+ if (ctx.symtab->hasTracedSymbol)
+ replayTraced(f, d, /*phaseSplit=*/true, /*defsOnly=*/false);
+ for (auto l : bf->obj->getDependentLibraries())
+ addDependentLibrary(ctx, l, bf);
+ continue;
+ }
+ if (auto *sf = dyn_cast<SharedFile>(f)) {
+ if (d.dupSoname)
+ continue;
+ ctx.sharedFiles.push_back(sf);
+ sf->allocateSymbols();
+ sf->parseGnuAndFeatures<ELFT>(sf->getObj<ELFT>());
+ if (ctx.symtab->hasTracedSymbol)
+ replayTraced(f, d, /*phaseSplit=*/false, /*defsOnly=*/false);
+ continue;
+ }
+ if (auto *bin = dyn_cast<BinaryFile>(f)) {
+ // A binary blob defines _binary_<name>_{start,end,size} directly.
+ ctx.binaryFiles.push_back(bin);
+ bin->parse();
+ continue;
+ }
+ auto *obj = cast<ObjFile<ELFT>>(f);
+ ctx.objectFiles.push_back(obj);
+ if (ctx.symtab->hasTracedSymbol)
+ replayTraced(f, d, /*phaseSplit=*/true, /*defsOnly=*/false);
+ obj->processEarlySections();
+ }
+}
+
+template <class ELFT> void Pipeline<ELFT>::initSections() {
+ // Runs after the epilogue, so that comdat group ownership and
+ // ctx.in.attributes are final, and after the phase-local data is freed.
+ ArrayRef<ELFFileBase *> objs = ArrayRef(ctx.objectFiles).slice(firstObjFile);
+ auto cost = [&](uint32_t i) -> uint64_t {
+ auto *f = cast<ObjFile<ELFT>>(objs[i]);
+ return f->template getELFShdrs<ELFT>().size() + f->firstGlobal;
+ };
+ parallelForLPT(objs.size(), cost, [&](uint32_t i) {
+ cast<ObjFile<ELFT>>(objs[i])->initSectionsAndLocalSyms(ignoreComdats);
+ });
+}
+
+template <class ELFT> void Pipeline<ELFT>::run() {
+ {
+ llvm::TimeTraceScope timeScope("Read symbols");
+ readSymbols();
+ }
+ {
+ llvm::TimeTraceScope timeScope("Build symbol database");
+ buildNameDB();
+ }
+ {
+ llvm::TimeTraceScope timeScope("Activate archive members");
+ activate();
+ }
+ registerComdats();
+ {
+ llvm::TimeTraceScope timeScope("Resolve symbols");
+ resolveSymbols();
+ }
+ {
+ llvm::TimeTraceScope timeScope("Wire symbols");
+ wireSymbols();
+ }
+ {
+ llvm::TimeTraceScope timeScope("Parse non-object files");
+ epilogue();
+ }
+ // Free phase-local data in parallel; serial destruction measurably
+ // serializes the frees.
+ parallelFor(0, fd.size() + numShards, [&](size_t i) {
+ if (i < fd.size()) {
+ fd[i] = FileData();
+ } else {
+ Bucket &bu = buckets[i - fd.size()];
+ bu.names = {};
+ bu.refs = {};
+ }
+ });
+ {
+ llvm::TimeTraceScope timeScope("Initialize sections");
+ initSections();
+ }
+}
+
+template <class ELFT>
+static void runPipeline(Ctx &ctx, SmallVector<InputFile *, 0> files,
+ bool incremental, ArrayRef<Symbol *> triggers = {},
+ bool ignoreComdats = false) {
+ Pipeline<ELFT> p(ctx, std::move(files), incremental, triggers, ignoreComdats);
+ p.run();
+}
+
+template <class ELFT>
+static void
+doParseFiles(Ctx &ctx,
+ const SmallVector<std::unique_ptr<InputFile>, 0> &files) {
+ // Parsing may append files (addDependentLibrary); a new batch seeds its name
+ // database from the symbols resolved so far.
+ for (size_t done = 0; done < files.size();) {
+ size_t end = files.size();
+ SmallVector<InputFile *, 0> batch;
+ batch.reserve(end - done);
+ for (size_t i = done; i != end; ++i)
+ batch.push_back(files[i].get());
+ runPipeline<ELFT>(ctx, std::move(batch), /*incremental=*/done != 0);
+ done = end;
+ }
+ if (ctx.driver.armCmseImpLib)
+ cast<ObjFile<ELFT>>(*ctx.driver.armCmseImpLib).importCmseSymbols();
+}
+
+void elf::parseFiles(Ctx &ctx,
+ const SmallVector<std::unique_ptr<InputFile>, 0> &files) {
+ llvm::TimeTraceScope timeScope("Parse input files");
+ invokeELFT(doParseFiles, ctx, files);
+}
+
+void elf::parseLtoObjectFiles(Ctx &ctx, ArrayRef<InputFile *> files) {
+ if (files.empty())
+ return;
+ invokeELFT(runPipeline, ctx,
+ SmallVector<InputFile *, 0>(files.begin(), files.end()),
+ /*incremental=*/true, /*triggers=*/ArrayRef<Symbol *>(),
+ /*ignoreComdats=*/true);
+
+ // An LTO output may reference a runtime libcall defined in an archive member
+ // not loaded before LTO; extract such members.
+ SmallVector<Symbol *, 0> triggers;
+ for (InputFile *f : files)
+ for (Symbol *sym : cast<ELFFileBase>(f)->getGlobalSymbols())
+ if (sym && sym->isLazy() && !sym->isWeak())
+ triggers.push_back(sym);
+ reactivate(ctx, triggers);
+}
+
+void elf::reactivate(Ctx &ctx, ArrayRef<Symbol *> triggers) {
+ if (triggers.empty())
+ return;
+ SmallVector<InputFile *, 0> lazyFiles;
+ for (auto &f : ctx.driver.getFiles())
+ if (f->lazy)
+ lazyFiles.push_back(f.get());
+ if (lazyFiles.empty())
+ return;
+ invokeELFT(runPipeline, ctx, std::move(lazyFiles), /*incremental=*/true,
+ triggers);
+}
+
template class elf::ObjFile<ELF32LE>;
template class elf::ObjFile<ELF32BE>;
template class elf::ObjFile<ELF64LE>;
template class elf::ObjFile<ELF64BE>;
-template void SharedFile::parse<ELF32LE>();
-template void SharedFile::parse<ELF32BE>();
-template void SharedFile::parse<ELF64LE>();
-template void SharedFile::parse<ELF64BE>();
diff --git a/lld/ELF/InputFiles.h b/lld/ELF/InputFiles.h
index 0ded9b2fa38e..975031aebd85 100644
--- a/lld/ELF/InputFiles.h
+++ b/lld/ELF/InputFiles.h
@@ -15,6 +15,7 @@
#include "lld/Common/LLVM.h"
#include "lld/Common/Reproduce.h"
#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/STLFunctionalExtras.h"
#include "llvm/BinaryFormat/Magic.h"
#include "llvm/Object/ELF.h"
#include "llvm/Support/MemoryBufferRef.h"
@@ -43,8 +44,12 @@ const ELFSyncStream &operator<<(const ELFSyncStream &, const InputFile *);
std::optional<MemoryBufferRef> readFile(Ctx &, StringRef path);
// Add symbols in File to the symbol table.
-void parseFile(Ctx &, InputFile *file);
void parseFiles(Ctx &, const SmallVector<std::unique_ptr<InputFile>, 0> &);
+// Resolve the symbols of LTO output objects against the symbol table.
+void parseLtoObjectFiles(Ctx &, ArrayRef<InputFile *>);
+// Extract still-lazy members defining the trigger symbols and resolve them.
+// References within an extracted member pull in further members transitively.
+void reactivate(Ctx &, ArrayRef<Symbol *> triggers);
// The root class of input files.
class InputFile {
@@ -100,6 +105,19 @@ public:
return {symbols.get(), numSymbols};
}
+ // Allocate the symbols array (zero-initialized) if not already present.
+ void allocateSymbols() {
+ if (!symbols)
+ symbols = std::make_unique<Symbol *[]>(numSymbols);
+ }
+
+ void allocateSymbols(size_t n) {
+ if (!symbols) {
+ numSymbols = n;
+ symbols = std::make_unique<Symbol *[]>(n);
+ }
+ }
+
Symbol &getSymbol(uint32_t symbolIndex) const {
assert(fileKind == ObjKind);
if (symbolIndex >= numSymbols)
@@ -115,10 +133,6 @@ public:
// Get filename to use for linker script processing.
StringRef getNameForScript() const;
- // Check if a non-common symbol should be extracted to override a common
- // definition.
- bool shouldExtractForCommon(StringRef name) const;
-
// .got2 in the current file. This is used by PPC32 -fPIC/-fPIE to compute
// offsets in PLT call stubs.
InputSection *ppc32Got2 = nullptr;
@@ -126,12 +140,6 @@ public:
// Index of MIPS GOT built for this file.
uint32_t mipsGotIndex = -1;
- // groupId is used for --warn-backrefs which is an optional error
- // checking feature. All files within the same --{start,end}-group or
- // --{start,end}-lib get the same group ID. Otherwise, each file gets a new
- // group ID. For more info, see checkDependency() in SymbolTable.cpp.
- uint32_t groupId = 0;
-
// If this is an architecture-specific file, the following members
// have ELF type (i.e. ELF{32,64}{LE,BE}) and target machine type.
uint16_t emachine = llvm::ELF::EM_NONE;
@@ -221,7 +229,6 @@ protected:
const void *elfShdrs = nullptr;
const void *elfSyms = nullptr;
uint32_t numELFShdrs = 0;
- uint32_t firstGlobal = 0;
// Below are ObjFile specific members.
@@ -235,11 +242,19 @@ protected:
public:
// Name of source file obtained from STT_FILE, if present.
StringRef sourceFile;
+ uint32_t firstGlobal = 0;
uint32_t andFeatures = 0;
bool hasCommonSyms = false;
std::optional<AArch64PauthAbiCoreInfo> aarch64PauthAbiCoreInfo;
};
+// Run fn over each item with unit-size dynamic grabs, largest cost first.
+// parallelFor's fixed-size chunks leave a straggler tail when the per-item
+// cost is heavy-tailed.
+void parallelForLPT(size_t numItems,
+ llvm::function_ref<uint64_t(uint32_t)> cost,
+ llvm::function_ref<void(uint32_t)> fn);
+
// .o file.
template <class ELFT> class ObjFile : public ELFFileBase {
LLVM_ELF_IMPORT_TYPES_ELFT(ELFT)
@@ -256,11 +271,8 @@ public:
this->archiveName = archiveName;
}
- void parse(bool ignoreComdats = false);
- void parseLazy();
-
- StringRef getShtGroupSignature(ArrayRef<Elf_Shdr> sections,
- const Elf_Shdr &sec);
+ llvm::Expected<std::pair<StringRef, ArrayRef<Elf_Word>>>
+ getGroup(const Elf_Shdr &sec);
uint32_t getSectionIndex(const Elf_Sym &sym) const;
@@ -290,10 +302,33 @@ public:
void postParse();
void importCmseSymbols();
+ // Tolerantly scan the section headers; diagnostics for malformed groups are
+ // emitted later, in initializeSections.
+ void scanEarlySections();
+ // Process dependent libraries and SHT_ARM_ATTRIBUTES (serial contexts
+ // only: may add input files and create the singleton attributes section).
+ void processEarlySections();
+
+ // Set when the file has a section processEarlySections must handle.
+ bool needsSerialScan = false;
+
+ // A SHT_GROUP section: its index, its signature symbol (UINT32_MAX unless
+ // the group is a decodable GRP_COMDAT), and whether this file owns the
+ // group. initializeSections consumes and frees this.
+ struct ComdatSec {
+ uint32_t secIdx;
+ uint32_t sigSym;
+ uint32_t prevailing = 1;
+ };
+ SmallVector<ComdatSec, 0> comdatSecs;
+
private:
+ // Retained SHT_ARM_ATTRIBUTES section, if this file provides
+ // ctx.in.attributes.
+ uint32_t armAttrSecIdx = UINT32_MAX;
+
void initializeSections(bool ignoreComdats,
const llvm::object::ELFFile<ELFT> &obj);
- void initializeSymbols(const llvm::object::ELFFile<ELFT> &obj);
void initializeJustSymbols();
InputSectionBase *getRelocTarget(uint32_t idx, uint32_t info);
@@ -315,10 +350,6 @@ private:
// The following variable contains the contents of .symtab_shndx.
// If the section does not exist (which is common), the array is empty.
ArrayRef<Elf_Word> shndxTable;
-
- // Section indices of kept SHT_GROUP sections, recorded by parse() in
- // ascending order, to be used by the parallel initializeSections().
- SmallVector<uint32_t, 0> keptGroups;
};
class BitcodeFile : public InputFile {
@@ -326,8 +357,7 @@ public:
BitcodeFile(Ctx &, MemoryBufferRef m, StringRef archiveName,
uint64_t offsetInArchive, bool lazy);
static bool classof(const InputFile *f) { return f->kind() == BitcodeKind; }
- void parse();
- void parseLazy();
+ void parseComdats();
void postParse();
std::unique_ptr<llvm::lto::InputFile> obj;
std::vector<bool> keptComdats;
@@ -357,8 +387,6 @@ public:
static bool classof(const InputFile *f) { return f->kind() == SharedKind; }
- template <typename ELFT> void parse();
-
// Used for --as-needed
std::atomic<bool> isNeeded;
@@ -366,7 +394,7 @@ public:
// parsed. Only filled for `--no-allow-shlib-undefined`.
SmallVector<Symbol *, 0> requiredSymbols;
-private:
+ // Called by the parallel parse pipeline (Pipeline::readShared/epilogue).
template <typename ELFT>
std::vector<uint32_t> parseVerneed(const llvm::object::ELFFile<ELFT> &obj,
const typename ELFT::Shdr *sec);
diff --git a/lld/ELF/LinkerScript.cpp b/lld/ELF/LinkerScript.cpp
index dcc84b8755db..89ff71e184de 100644
--- a/lld/ELF/LinkerScript.cpp
+++ b/lld/ELF/LinkerScript.cpp
@@ -1937,10 +1937,15 @@ void LinkerScript::checkFinalScriptConditions() const {
void LinkerScript::addScriptReferencedSymbolsToSymTable() {
// Some symbols (such as __ehdr_start) are defined lazily only when there
// are undefined symbols for them, so we add these to trigger that logic.
- auto reference = [&ctx = ctx](StringRef name) {
+ // A reference may also name a still-lazy archive member; collect those and
+ // pull them in below.
+ SmallVector<Symbol *, 0> triggers;
+ auto reference = [&](StringRef name) {
Symbol *sym = ctx.symtab->addUnusedUndefined(name);
sym->isUsedInRegularObj = true;
sym->referenced = true;
+ if (sym->isLazy())
+ triggers.push_back(sym);
};
for (StringRef name : referencedSymbols)
reference(name);
@@ -1964,6 +1969,7 @@ void LinkerScript::addScriptReferencedSymbolsToSymTable() {
}
}
}
+ reactivate(ctx, triggers);
}
bool LinkerScript::shouldAddProvideSym(StringRef symName) {
diff --git a/lld/ELF/Options.td b/lld/ELF/Options.td
index 64c42eb49607..3463908a0f20 100644
--- a/lld/ELF/Options.td
+++ b/lld/ELF/Options.td
@@ -222,7 +222,7 @@ def enable_non_contiguous_regions : FF<"enable-non-contiguous-regions">,
HelpText<"Spill input sections to later matching output sections to avoid memory region overflow">;
def end_group: F<"end-group">,
- HelpText<"Ignored for compatibility with GNU unless you pass --warn-backrefs">;
+ HelpText<"Ignored for compatibility with GNU">;
def end_lib: F<"end-lib">,
HelpText<"End a grouping of objects that should be treated as if they were together in an archive">;
@@ -470,7 +470,7 @@ defm sort_section:
Eq<"sort-section", "Specifies sections sorting rule when linkerscript is used">;
def start_group: F<"start-group">,
- HelpText<"Ignored for compatibility with GNU unless you pass --warn-backrefs">;
+ HelpText<"Ignored for compatibility with GNU">;
def start_lib: F<"start-lib">,
HelpText<"Start a grouping of objects that should be treated as if they were together in an archive">;
@@ -551,16 +551,6 @@ def no_power10_stubs: FF<"no-power10-stubs">, Alias<power10_stubs_eq>, AliasArgs
defm version_script: Eq<"version-script", "Read a version script">;
-defm warn_backrefs: BB<"warn-backrefs",
- "Warn about backward symbol references to extract archive members",
- "Do not warn about backward symbol references to extract archive members (default)">;
-
-defm warn_backrefs_exclude
- : EEq<"warn-backrefs-exclude",
- "Glob describing an archive (or an object file within --start-lib) "
- "which should be ignored for --warn-backrefs.">,
- MetaVarName<"<glob>">;
-
defm warn_common: B<"warn-common",
"Warn about duplicate common symbols",
"Do not warn about duplicate common symbols (default)">;
diff --git a/lld/ELF/Relocations.cpp b/lld/ELF/Relocations.cpp
index 7aaae802f4d7..948f5a29c52b 100644
--- a/lld/ELF/Relocations.cpp
+++ b/lld/ELF/Relocations.cpp
@@ -401,9 +401,14 @@ static void maybeReportDiscarded(Ctx &ctx, ELFSyncStream &msg, Undefined &sym) {
return;
// If the discarded section is a COMDAT.
- StringRef signature = file->getShtGroupSignature(objSections, elfSec);
+ auto group = file->getGroup(elfSec);
+ if (!group) {
+ consumeError(group.takeError());
+ return;
+ }
+ StringRef signature = group->first;
if (const InputFile *prevailing =
- ctx.symtab->comdatGroups.lookup(CachedHashStringRef(signature))) {
+ ctx.symtab->findComdatGroup(CachedHashStringRef(signature))) {
msg << "\n>>> section group signature: " << signature
<< "\n>>> prevailing definition is in " << prevailing;
if (sym.nonPrevailing) {
diff --git a/lld/ELF/ScriptParser.cpp b/lld/ELF/ScriptParser.cpp
index 0c54fde48829..1916fb4d6e87 100644
--- a/lld/ELF/ScriptParser.cpp
+++ b/lld/ELF/ScriptParser.cpp
@@ -391,8 +391,6 @@ void ScriptParser::readExtern() {
void ScriptParser::readGroup() {
SaveAndRestore saved(ctx.driver.isInGroup, true);
readInput();
- if (!saved.get())
- ++ctx.driver.nextGroupId;
}
void ScriptParser::readInclude(llvm::function_ref<void()> parse) {
diff --git a/lld/ELF/SymbolTable.cpp b/lld/ELF/SymbolTable.cpp
index da0293e9ec83..290021d7d220 100644
--- a/lld/ELF/SymbolTable.cpp
+++ b/lld/ELF/SymbolTable.cpp
@@ -30,9 +30,11 @@ using namespace lld::elf;
void SymbolTable::wrap(Symbol *sym, Symbol *real, Symbol *wrap) {
// Redirect __real_foo to the original foo and foo to the original __wrap_foo.
- int &idx1 = symMap[CachedHashStringRef(sym->getName())];
- int &idx2 = symMap[CachedHashStringRef(real->getName())];
- int &idx3 = symMap[CachedHashStringRef(wrap->getName())];
+ CachedHashStringRef name1(sym->getName()), name2(real->getName()),
+ name3(wrap->getName());
+ int &idx1 = getMap(name1)[name1];
+ int &idx2 = getMap(name2)[name2];
+ int &idx3 = getMap(name3)[name3];
idx2 = idx1;
idx1 = idx3;
@@ -61,18 +63,11 @@ void SymbolTable::wrap(Symbol *sym, Symbol *real, Symbol *wrap) {
// Find an existing symbol or create a new one.
Symbol *SymbolTable::insert(StringRef name) {
- // <name>@@<version> means the symbol is the default version. In that
- // case <name>@@<version> will be used to resolve references to <name>.
- //
- // Since this is a hot path, the following string search code is
- // optimized for speed. StringRef::find(char) is much faster than
- // StringRef::find(StringRef).
- StringRef stem = name;
- size_t pos = name.find('@');
- if (pos != StringRef::npos && pos + 1 < name.size() && name[pos + 1] == '@')
- stem = name.take_front(pos);
+ auto [stemLen, hasAt] = getSymbolStem(name);
+ StringRef stem = name.take_front(stemLen);
- auto p = symMap.insert({CachedHashStringRef(stem), (int)symVector.size()});
+ CachedHashStringRef chr(stem);
+ auto p = getMap(chr).insert({chr, (int)symVector.size()});
if (!p.second) {
Symbol *sym = symVector[p.first->second];
if (stem.size() != name.size()) {
@@ -89,7 +84,7 @@ Symbol *SymbolTable::insert(StringRef name) {
// are zero. Set the ones that need a non-zero value.
sym->setName(name);
sym->versionId = VER_NDX_GLOBAL;
- if (pos != StringRef::npos)
+ if (hasAt)
sym->hasVersionSuffix = true;
return sym;
}
@@ -106,12 +101,22 @@ Symbol *SymbolTable::addAndCheckDuplicate(Ctx &ctx, const Defined &newSym) {
}
Symbol *SymbolTable::find(StringRef name) {
- auto it = symMap.find(CachedHashStringRef(name));
- if (it == symMap.end())
+ CachedHashStringRef chr(name);
+ auto &map = getMap(chr);
+ auto it = map.find(chr);
+ if (it == map.end())
return nullptr;
return symVector[it->second];
}
+void SymbolTable::installShardedSymbols(
+ MutableArrayRef<DenseMap<CachedHashStringRef, int>> maps,
+ SmallVector<Symbol *, 0> &&syms) {
+ assert(maps.size() == numShards);
+ llvm::move(maps, shards.begin());
+ symVector = std::move(syms);
+}
+
// A version script/dynamic list is only meaningful for a Defined symbol.
// A CommonSymbol will be converted to a Defined in replaceCommonSymbols().
// A lazy symbol may be made Defined if an LTO libcall extracts it.
diff --git a/lld/ELF/SymbolTable.h b/lld/ELF/SymbolTable.h
index e485ad2edb00..b38bf492b21a 100644
--- a/lld/ELF/SymbolTable.h
+++ b/lld/ELF/SymbolTable.h
@@ -13,6 +13,7 @@
#include "llvm/ADT/CachedHashString.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/Support/Compiler.h"
+#include <array>
namespace lld::elf {
struct Ctx;
@@ -24,6 +25,16 @@ struct ArmCmseEntryFunction {
Symbol *sym;
};
+// The symbol table key of <name>@@<version> is <name>: a default version
+// resolves references to the unversioned name. Returns the stem length and
+// whether the name contains '@'.
+inline std::pair<size_t, bool> getSymbolStem(StringRef name) {
+ size_t pos = name.find('@');
+ if (pos != StringRef::npos && pos + 1 < name.size() && name[pos + 1] == '@')
+ return {pos, true};
+ return {name.size(), pos != StringRef::npos};
+}
+
// SymbolTable is a bucket of all known symbols, including defined,
// undefined, or lazy symbols (the last one is symbols in archive
// files whose archive members are not yet loaded).
@@ -38,13 +49,33 @@ struct ArmCmseEntryFunction {
// is one add* function per symbol type.
class SymbolTable {
public:
+ static constexpr size_t numShards = 32;
+
SymbolTable(Ctx &ctx) : ctx(ctx) {}
ArrayRef<Symbol *> getSymbols() const { return symVector; }
+ // The per-shard name maps (key -> symVector index), keyed by the original
+ // registration stem, which may differ from a symbol's current name.
+ ArrayRef<llvm::DenseMap<llvm::CachedHashStringRef, int>> getShards() const {
+ return ArrayRef(shards);
+ }
+
void wrap(Symbol *sym, Symbol *real, Symbol *wrap);
Symbol *insert(StringRef name);
+ // Install the pre-ordered maps and symbol vector built by the parse
+ // pipeline.
+ void installShardedSymbols(
+ MutableArrayRef<llvm::DenseMap<llvm::CachedHashStringRef, int>> maps,
+ SmallVector<Symbol *, 0> &&syms);
+
+ // Append a symbol resolved by a late parse batch, in symVector order.
+ void appendShardedSymbol(llvm::CachedHashStringRef key, Symbol *sym) {
+ shards[key.hash() % numShards].try_emplace(key, (int)symVector.size());
+ symVector.push_back(sym);
+ }
+
template <typename T> Symbol *addSymbol(const T &newSym) {
Symbol *sym = insert(newSym.getName());
sym->resolve(ctx, newSym);
@@ -65,9 +96,22 @@ public:
llvm::DenseMap<llvm::CachedHashStringRef, SharedFile *> soNames;
// Comdat groups define "link once" sections. If two comdat groups have the
- // same name, only one of them is linked, and the other is ignored. This map
- // is used to uniquify them.
- llvm::DenseMap<llvm::CachedHashStringRef, const InputFile *> comdatGroups;
+ // same name, only one of them is linked, and the other is ignored. The maps
+ // are sharded by signature hash so that the parallel parse pipeline can
+ // pre-populate them in parallel; the first registered file owns the group.
+ // Returns the owner.
+ const InputFile *addComdatGroup(llvm::CachedHashStringRef sig,
+ const InputFile *f) {
+ return comdatGroups[sig.hash() % numShards]
+ .try_emplace(sig, f)
+ .first->second;
+ }
+ const InputFile *findComdatGroup(llvm::CachedHashStringRef sig) const {
+ return comdatGroups[sig.hash() % numShards].lookup(sig);
+ }
+ std::array<llvm::DenseMap<llvm::CachedHashStringRef, const InputFile *>,
+ numShards>
+ comdatGroups;
// The Map of __acle_se_<sym>, <sym> pairs found in the input objects.
// Key is the <sym> name.
@@ -81,6 +125,8 @@ public:
// output Arm CMSE import library.
llvm::StringMap<bool> inCMSEOutImpLib;
+ bool hasTracedSymbol = false;
+
private:
SmallVector<Symbol *, 0> findByVersion(SymbolVersion ver);
SmallVector<Symbol *, 0> findAllByVersion(SymbolVersion ver,
@@ -92,10 +138,15 @@ private:
Ctx &ctx;
- // Global symbols and a map from symbol name to the index. The order is not
- // defined. We can use an arbitrary order, but it has to be deterministic even
- // when cross linking.
- llvm::DenseMap<llvm::CachedHashStringRef, int> symMap;
+ llvm::DenseMap<llvm::CachedHashStringRef, int> &
+ getMap(llvm::CachedHashStringRef name) {
+ return shards[name.hash() % numShards];
+ }
+
+ // Global symbols: per-shard maps from name (registration stem) to symVector
+ // index, routed by name hash. The order is not defined. We can use an
+ // arbitrary order, but it has to be deterministic even when cross linking.
+ std::array<llvm::DenseMap<llvm::CachedHashStringRef, int>, numShards> shards;
SmallVector<Symbol *, 0> symVector;
// A map from demangled symbol names to their symbol objects.
diff --git a/lld/ELF/Symbols.cpp b/lld/ELF/Symbols.cpp
index 951041466cec..928164f02442 100644
--- a/lld/ELF/Symbols.cpp
+++ b/lld/ELF/Symbols.cpp
@@ -279,12 +279,6 @@ void Symbol::parseSymbolVersion(Ctx &ctx) {
<< verstr;
}
-void Symbol::extract(Ctx &ctx) const {
- assert(file->lazy);
- file->lazy = false;
- parseFile(ctx, file);
-}
-
uint8_t Symbol::computeBinding(Ctx &ctx) const {
auto v = visibility();
if ((v != STV_DEFAULT && v != STV_PROTECTED) || versionId == VER_NDX_LOCAL)
@@ -311,11 +305,6 @@ void elf::printTraceSymbol(const Symbol &sym, StringRef name) {
Msg(sym.file->ctx) << sym.file << s << name;
}
-static void recordWhyExtract(Ctx &ctx, const InputFile *reference,
- const InputFile &extracted, const Symbol &sym) {
- ctx.whyExtractRecords.emplace_back(toStr(ctx, reference), &extracted, sym);
-}
-
void elf::maybeWarnUnorderableSymbol(Ctx &ctx, const Symbol *sym) {
if (!ctx.arg.warnSymbolOrdering)
return;
@@ -414,17 +403,12 @@ void elf::parseVersionAndComputeIsPreemptible(Ctx &ctx) {
// were not chosen still affect some symbol properties.
void Symbol::mergeProperties(const Symbol &other) {
// DSO symbols do not affect visibility in the output.
- if (!other.isShared() && other.visibility() != STV_DEFAULT) {
- uint8_t v = visibility(), ov = other.visibility();
- setVisibility(v == STV_DEFAULT ? ov : std::min(v, ov));
- }
+ if (!other.isShared())
+ mergeVisibility(other.visibility());
}
void Symbol::resolve(Ctx &ctx, const Undefined &other) {
- if (other.visibility() != STV_DEFAULT) {
- uint8_t v = visibility(), ov = other.visibility();
- setVisibility(v == STV_DEFAULT ? ov : std::min(v, ov));
- }
+ mergeVisibility(other.visibility());
// An undefined symbol with non default visibility must be satisfied
// in the same DSO.
//
@@ -440,81 +424,14 @@ void Symbol::resolve(Ctx &ctx, const Undefined &other) {
printTraceSymbol(other, getName());
if (isLazy()) {
- // An undefined weak will not extract archive members. See comment on Lazy
- // in Symbols.h for the details.
+ // An undefined weak does not extract archive members (see the comment on
+ // Lazy in Symbols.h). A strong reference leaves the lazy symbol in place;
+ // extraction is decided by Pipeline::activate, which also records
+ // --why-extract.
if (other.binding == STB_WEAK) {
binding = STB_WEAK;
type = other.type;
- return;
}
-
- // Do extra check for --warn-backrefs.
- //
- // --warn-backrefs is an option to prevent an undefined reference from
- // extracting an archive member written earlier in the command line. It can
- // be used to keep compatibility with GNU linkers to some degree. I'll
- // explain the feature and why you may find it useful in this comment.
- //
- // lld's symbol resolution semantics is more relaxed than traditional Unix
- // linkers. For example,
- //
- // ld.lld foo.a bar.o
- //
- // succeeds even if bar.o contains an undefined symbol that has to be
- // resolved by some object file in foo.a. Traditional Unix linkers don't
- // allow this kind of backward reference, as they visit each file only once
- // from left to right in the command line while resolving all undefined
- // symbols at the moment of visiting.
- //
- // In the above case, since there's no undefined symbol when a linker visits
- // foo.a, no files are pulled out from foo.a, and because the linker forgets
- // about foo.a after visiting, it can't resolve undefined symbols in bar.o
- // that could have been resolved otherwise.
- //
- // That lld accepts more relaxed form means that (besides it'd make more
- // sense) you can accidentally write a command line or a build file that
- // works only with lld, even if you have a plan to distribute it to wider
- // users who may be using GNU linkers. With --warn-backrefs, you can detect
- // a library order that doesn't work with other Unix linkers.
- //
- // The option is also useful to detect cyclic dependencies between static
- // archives. Again, lld accepts
- //
- // ld.lld foo.a bar.a
- //
- // even if foo.a and bar.a depend on each other. With --warn-backrefs, it is
- // handled as an error.
- //
- // Here is how the option works. We assign a group ID to each file. A file
- // with a smaller group ID can pull out object files from an archive file
- // with an equal or greater group ID. Otherwise, it is a reverse dependency
- // and an error.
- //
- // A file outside --{start,end}-group gets a fresh ID when instantiated. All
- // files within the same --{start,end}-group get the same group ID. E.g.
- //
- // ld.lld A B --start-group C D --end-group E
- //
- // A forms group 0. B form group 1. C and D (including their member object
- // files) form group 2. E forms group 3. I think that you can see how this
- // group assignment rule simulates the traditional linker's semantics.
- bool backref = ctx.arg.warnBackrefs && file->groupId < other.file->groupId;
- extract(ctx);
-
- if (!ctx.arg.whyExtract.empty())
- recordWhyExtract(ctx, other.file, *file, *this);
-
- // We don't report backward references to weak symbols as they can be
- // overridden later.
- //
- // A traditional linker does not error for -ldef1 -lref -ldef2 (linking
- // sandwich), where def2 may or may not be the same as def1. We don't want
- // to warn for this case, so dismiss the warning if we see a subsequent lazy
- // definition. this->file needs to be saved because in the case of LTO it
- // may be reset to internalFile or be replaced with a file named lto.tmp.
- if (backref && !isWeak())
- ctx.backwardReferences.try_emplace(this,
- std::make_pair(other.file, file));
return;
}
@@ -605,10 +522,7 @@ void Symbol::checkDuplicate(Ctx &ctx, const Defined &other) const {
}
void Symbol::resolve(Ctx &ctx, const CommonSymbol &other) {
- if (other.visibility() != STV_DEFAULT) {
- uint8_t v = visibility(), ov = other.visibility();
- setVisibility(v == STV_DEFAULT ? ov : std::min(v, ov));
- }
+ mergeVisibility(other.visibility());
if (isDefined() && !isWeak()) {
if (ctx.arg.warnCommon)
Warn(ctx) << "common " << getName() << " is overridden";
@@ -641,49 +555,27 @@ void Symbol::resolve(Ctx &ctx, const CommonSymbol &other) {
}
void Symbol::resolve(Ctx &ctx, const Defined &other) {
- if (other.visibility() != STV_DEFAULT) {
- uint8_t v = visibility(), ov = other.visibility();
- setVisibility(v == STV_DEFAULT ? ov : std::min(v, ov));
- }
+ mergeVisibility(other.visibility());
if (shouldReplace(ctx, other))
other.overwrite(*this);
}
void Symbol::resolve(Ctx &ctx, const LazySymbol &other) {
+ // A lazy definition takes over only a placeholder or a weak undefined,
+ // which keeps its binding and type (it does not extract archive members;
+ // see the comment on Lazy in Symbols.h) but records the member for
+ // extract-on-demand (e.g. --entry). Anything else leaves the symbol in
+ // place: extraction decisions (including --fortran-common overrides) are
+ // made by Pipeline::activate, and an extracted member resolves as a regular
+ // file.
if (isPlaceholder()) {
other.overwrite(*this);
- return;
- }
-
- if (LLVM_UNLIKELY(!isUndefined())) {
- // See the comment in resolve(Ctx &, const Undefined &).
- if (isDefined()) {
- ctx.backwardReferences.erase(this);
- } else if (isCommon() && ctx.arg.fortranCommon &&
- other.file->shouldExtractForCommon(getName())) {
- // For common objects, we want to look for global or weak definitions that
- // should be extracted as the canonical definition instead.
- ctx.backwardReferences.erase(this);
- other.overwrite(*this);
- other.extract(ctx);
- }
- return;
- }
-
- // An undefined weak will not extract archive members. See comment on Lazy in
- // Symbols.h for the details.
- if (isWeak()) {
+ } else if (isUndefined() && isWeak()) {
uint8_t ty = type;
other.overwrite(*this);
type = ty;
binding = STB_WEAK;
- return;
}
-
- const InputFile *oldFile = file;
- other.extract(ctx);
- if (!ctx.arg.whyExtract.empty())
- recordWhyExtract(ctx, oldFile, *file, *this);
}
void Symbol::resolve(Ctx &ctx, const SharedSymbol &other) {
diff --git a/lld/ELF/Symbols.h b/lld/ELF/Symbols.h
index c489416e1f4d..00cc68d04719 100644
--- a/lld/ELF/Symbols.h
+++ b/lld/ELF/Symbols.h
@@ -151,6 +151,13 @@ public:
void setVisibility(uint8_t visibility) {
stOther = (stOther & ~3) | visibility;
}
+ // Merge an input symbol's visibility: the most constraining one wins.
+ void mergeVisibility(uint8_t ov) {
+ if (ov != llvm::ELF::STV_DEFAULT) {
+ uint8_t v = visibility();
+ setVisibility(v == llvm::ELF::STV_DEFAULT ? ov : std::min(v, ov));
+ }
+ }
uint8_t computeBinding(Ctx &) const;
bool isGlobal() const { return binding == llvm::ELF::STB_GLOBAL; }
@@ -226,11 +233,6 @@ public:
void resolve(Ctx &, const LazySymbol &other);
void resolve(Ctx &, const SharedSymbol &other);
- // If this is a lazy symbol, extract an input file and add the symbol
- // in the file to the symbol table. Calling this function on
- // non-lazy object causes a runtime error.
- void extract(Ctx &) const;
-
void checkDuplicate(Ctx &, const Defined &other) const;
private:
diff --git a/lld/ELF/SyntheticSections.cpp b/lld/ELF/SyntheticSections.cpp
index aa7a859a9da9..2748789e4ebc 100644
--- a/lld/ELF/SyntheticSections.cpp
+++ b/lld/ELF/SyntheticSections.cpp
@@ -3805,8 +3805,13 @@ void MergeNoTailSection::finalizeContents() {
template <class ELFT> void elf::splitSections(Ctx &ctx) {
llvm::TimeTraceScope timeScope("Split sections");
// splitIntoPieces needs to be called on each MergeInputSection
- // before calling finalizeContents().
- parallelForEach(ctx.objectFiles, [](ELFFileBase *file) {
+ // before calling finalizeContents(). Schedule the biggest files first: the
+ // per-file cost is heavy-tailed (one big .debug_str can dominate).
+ auto cost = [&](uint32_t i) -> uint64_t {
+ return ctx.objectFiles[i]->mb.getBufferSize();
+ };
+ parallelForLPT(ctx.objectFiles.size(), cost, [&](uint32_t i) {
+ ELFFileBase *file = ctx.objectFiles[i];
for (InputSectionBase *sec : file->getSections()) {
if (!sec)
continue;
diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp
index 8cf88cd99cf8..cf70c1c9adae 100644
--- a/lld/ELF/Writer.cpp
+++ b/lld/ELF/Writer.cpp
@@ -455,7 +455,8 @@ static void demoteAndCopyLocalSymbols(Ctx &ctx) {
parallelFor(0, ctx.objectFiles.size(), [&](size_t i) {
DenseMap<SectionBase *, size_t> sectionIndexMap;
for (Symbol *b : ctx.objectFiles[i]->getLocalSymbols()) {
- assert(b->isLocal() && "should have been caught in initializeSymbols()");
+ assert(b->isLocal() &&
+ "should have been caught in initSectionsAndLocalSyms()");
auto *dr = dyn_cast<Defined>(b);
if (!dr)
continue;
diff --git a/lld/docs/ELF/warn_backrefs.md b/lld/docs/ELF/warn_backrefs.md
deleted file mode 100644
index 84c43cd21ffd..000000000000
--- a/lld/docs/ELF/warn_backrefs.md
+++ /dev/null
@@ -1,100 +0,0 @@
-# --warn-backrefs
-
-`--warn-backrefs` gives a warning when an undefined symbol reference is
-resolved by a definition in an archive to the left of it on the command line.
-
-A linker such as GNU ld makes a single pass over the input files from left to
-right maintaining the set of undefined symbol references from the files loaded
-so far. When encountering an archive or an object file surrounded by
-`--start-lib` and `--end-lib` that archive will be searched for resolving
-symbol definitions; this may result in input files being loaded, updating the
-set of undefined symbol references. When all resolving definitions have been
-loaded from the archive, the linker moves on the next file and will not return
-to it. This means that if an input file to the right of an archive cannot have
-an undefined symbol resolved by an archive to the left of it. For example:
-
-> ld def.a ref.o
-
-will result in an `undefined reference` error. If there are no cyclic
-references, the archives can be ordered in such a way that there are no
-backward references. If there are cyclic references then the `--start-group`
-and `--end-group` options can be used, or the same archive can be placed on
-the command line twice.
-
-LLD remembers the symbol table of archives that it has previously seen, so if
-there is a reference from an input file to the right of an archive, LLD will
-still search that archive for resolving any undefined references. This means
-that an archive only needs to be included once on the command line and the
-`--start-group` and `--end-group` options are redundant.
-
-A consequence of the differing archive searching semantics is that the same
-linker command line can result in different outcomes. A link may succeed with
-LLD that will fail with GNU ld, or even worse both links succeed but they have
-selected different objects from different archives that both define the same
-symbols.
-
-The `warn-backrefs` option provides information that helps identify cases
-where LLD and GNU ld archive selection may differ.
-
-```console
-% ld.lld --warn-backrefs ... -lB -lA
-ld.lld: warning: backward reference detected: system in A.a(a.o) refers to B.a(b.o)
-
-% ld.lld --warn-backrefs ... --start-lib B/b.o --end-lib --start-lib A/a.o --end-lib
-ld.lld: warning: backward reference detected: system in A/a.o refers to B/b.o
-
-# To suppress the warning, you can specify --warn-backrefs-exclude=<glob> to match B/b.o or B.a(b.o)
-```
-
-The `--warn-backrefs` option can also provide a check to enforce a
-topological order of archives, which can be useful to detect layering
-violations (albeit unable to catch all cases). There are two cases where GNU ld
-will result in an `undefined reference` error:
-
-- If adding the dependency does not form a cycle: conceptually `A` is higher
- level library while `B` is at a lower level. When you are developing an
- application `P` which depends on `A`, but does not directly depend on
- `B`, your link may fail surprisingly with `undefined symbol:
- symbol_defined_in_B` if the used/linked part of `A` happens to need some
- components of `B`. It is inappropriate for `P` to add a dependency on
- `B` since `P` does not use `B` directly.
-- If adding the dependency forms a cycle, e.g. `B->C->A ~> B`. `A`
- is supposed to be at the lowest level while `B` is supposed to be at the
- highest level. When you are developing `C_test` testing `C`, your link may
- fail surprisingly with `undefined symbol` if there is somehow a dependency on
- some components of `B`. You could fix the issue by adding the missing
- dependency (`B`), however, then every test (`A_test`, `B_test`,
- `C_test`) will link against every library. This breaks the motivation
- of splitting `B`, `C` and `A` into separate libraries and makes binaries
- unnecessarily large. Moreover, the layering violation makes lower-level
- libraries (e.g. `A`) vulnerable to changes to higher-level libraries (e.g.
- `B`, `C`).
-
-Resolution:
-
-- Add a dependency from `A` to `B`.
-- The reference may be unintended and can be removed.
-- The dependency may be intentionally omitted because there are multiple
- libraries like `B`. Consider linking `B` with object semantics by
- surrounding it with `--whole-archive` and `--no-whole-archive`.
-- In the case of circular dependency, sometimes merging the libraries are the best.
-
-There are two cases like a library sandwich where GNU ld will select a
-different object.
-
-- `A.a B A2.so`: `A.a` may be used as an interceptor (e.g. it provides some
- optimized libc functions and `A2` is libc). `B` does not need to know
- about `A.a`, and `A.a` may be pulled into the link by other part of the
- program. For linker portability, consider `--whole-archive` and
- `--no-whole-archive`.
-
-- `A.a B A2.a`: similar to the above case but `--warn-backrefs` does not
- flag the problem, because `A2.a` may be a replicate of `A.a`, which is
- redundant but benign. In some cases `A.a` and `B` should be surrounded by
- a pair of `--start-group` and `--end-group`. This is especially common
- among system libraries (e.g. `-lc __isnanl references -lm`, `-lc
- _IO_funlockfile references -lpthread`, `-lc __gcc_personality_v0 references
- -lgcc_eh`, and `-lpthread _Unwind_GetCFA references -lunwind`).
-
- In C++, this is likely an ODR violation. We probably need a dedicated option
- for ODR detection.
diff --git a/lld/docs/index.md b/lld/docs/index.md
index 7dba6f479e99..b699c056d32e 100644
--- a/lld/docs/index.md
+++ b/lld/docs/index.md
@@ -128,7 +128,6 @@ ReleaseNotes
ELF/large_sections
ELF/linker_script
ELF/start-stop-gc
-ELF/warn_backrefs
MachO/index
DTLTO
```
diff --git a/lld/docs/ld.lld.1 b/lld/docs/ld.lld.1
index 7dedf69881b3..1f43c3d99fd3 100644
--- a/lld/docs/ld.lld.1
+++ b/lld/docs/ld.lld.1
@@ -748,14 +748,6 @@ Verbose mode.
.It Fl -version-script Ns = Ns Ar file
Read version script from
.Ar file .
-.It Fl -warn-backrefs
-Warn about reverse or cyclic dependencies to or between static archives.
-This can be used to ensure linker invocation remains compatible with
-traditional Unix-like linkers.
-.It Fl -warn-backrefs-exclude Ns = Ns Ar glob
-Glob describing an archive (or an object file within --start-lib)
-which should be ignored for
-.Fl -warn-backrefs
.It Fl -warn-common
Warn about duplicate common symbols.
.It Fl -warn-ifunc-textrel
@@ -1076,8 +1068,3 @@ may produce different results compared to traditional linkers.
In practice, large bodies of third party software have been linked with
.Nm
without material issues.
-.Pp
-The
-.Fl -warn-backrefs
-option may be used to identify a linker invocation that may be incompatible
-with traditional Unix-like linker behavior.
diff --git a/lld/test/ELF/fortran-common-extract.s b/lld/test/ELF/fortran-common-extract.s
new file mode 100644
index 000000000000..11929548fcf6
--- /dev/null
+++ b/lld/test/ELF/fortran-common-extract.s
@@ -0,0 +1,84 @@
+# REQUIRES: x86
+## --fortran-common pulls in an archive member whose STB_GLOBAL definition
+## overrides an active tentative (COMMON) definition. Check that the decision
+## does not depend on where the COMMON appears among the definitions, and that
+## a member providing only a weak definition (which would not override the
+## COMMON) is not extracted.
+
+# RUN: rm -rf %t && split-file %s %t && cd %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64 main.s -o main.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64 common.s -o common.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64 weak.s -o weak.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64 ref.s -o ref.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64 def.s -o def.o
+# RUN: ld.lld -shared def.o -o d.so
+# RUN: llvm-ar rc cw.a common.o weak.o
+# RUN: llvm-ar rc w.a weak.o
+# RUN: llvm-ar rc d.a def.o
+
+## The COMMON is in an unextracted member, so no COMMON is active.
+# RUN: ld.lld --fortran-common main.o cw.a weak.o ref.o -o a1 --why-extract=- | \
+# RUN: FileCheck %s --check-prefix=NONE
+
+## A weak definition does not override a COMMON, so its member stays lazy.
+# RUN: ld.lld --fortran-common main.o common.o w.a -o a2 --why-extract=- | \
+# RUN: FileCheck %s --check-prefix=NONE
+
+# NONE: reference{{.*}}extracted{{.*}}symbol
+# NONE-NOT: {{.}}
+
+## The override target is found whether the COMMON precedes or follows the weak
+## definition.
+# RUN: ld.lld --fortran-common main.o weak.o common.o d.so d.a -o a3 --why-extract=- | \
+# RUN: FileCheck %s --check-prefix=EXTRACT
+# RUN: ld.lld --fortran-common main.o common.o weak.o d.so d.a -o a4 --why-extract=- | \
+# RUN: FileCheck %s --check-prefix=EXTRACT
+
+# EXTRACT: reference{{.*}}extracted{{.*}}symbol
+# EXTRACT-NEXT: common.o d.a(def.o) foo
+# EXTRACT-NOT: {{.}}
+
+## The COMMON becomes active when its member is extracted for another symbol.
+# RUN: llvm-mc -filetype=obj -triple=x86_64 commonbar.s -o commonbar.o
+# RUN: llvm-ar rc cb.a commonbar.o def.o
+# RUN: ld.lld --fortran-common -u bar main.o d.so cb.a -o a5 --why-extract=- | \
+# RUN: FileCheck %s --check-prefix=LATE
+# RUN: ld.lld --fortran-common -u bar main.o cb.a d.so -o a6 --why-extract=- | \
+# RUN: FileCheck %s --check-prefix=LATE
+
+# LATE: reference{{.*}}extracted{{.*}}symbol
+# LATE-NEXT: <internal> cb.a(commonbar.o) bar
+# LATE-NEXT: cb.a(commonbar.o) cb.a(def.o) foo
+# LATE-NOT: {{.}}
+
+#--- main.s
+.globl _start
+_start:
+ ret
+
+#--- common.s
+.comm foo,4,4
+
+#--- commonbar.s
+.comm foo,4,4
+.globl bar
+bar:
+ ret
+
+#--- weak.s
+.data
+.weak foo
+foo:
+ .long 1
+
+#--- def.s
+.data
+.globl foo
+foo:
+ .long 2
+
+#--- ref.s
+.globl ref
+ref:
+ movl foo(%rip), %eax
+ ret
diff --git a/lld/test/ELF/interconnected-lazy.s b/lld/test/ELF/interconnected-lazy.s
index 0d67318b3fa0..fff77e6727f4 100644
--- a/lld/test/ELF/interconnected-lazy.s
+++ b/lld/test/ELF/interconnected-lazy.s
@@ -7,15 +7,15 @@
## foo and __foo are interconnected and defined in two lazy object files.
## Test we resolve both to the same file.
+## With order-independent archive extraction the live set is computed to a
+## fixpoint and ties break by file index, so the weak foo/__foo resolve to the
+## lower-indexed a.o (instead of b.o's later positional definition winning).
# RUN: ld.lld -y a -y foo -y __foo %t/main.o --start-lib %t/a.o %t/b.o --end-lib -o /dev/null | FileCheck %s
-# CHECK: a.o: lazy definition of a
-# CHECK-NEXT: a.o: lazy definition of foo
-# CHECK-NEXT: a.o: lazy definition of __foo
-# CHECK-NEXT: b.o: definition of foo
-# CHECK-NEXT: b.o: definition of __foo
+# CHECK: a.o: definition of a
+# CHECK-NEXT: a.o: definition of foo
+# CHECK-NEXT: a.o: definition of __foo
# CHECK-NEXT: b.o: reference to a
-# CHECK-NEXT: a.o: definition of a
#--- main.s
.globl _start
diff --git a/lld/test/ELF/lto/archive-mixed.test b/lld/test/ELF/lto/archive-mixed.test
index 6f1db87c89ca..4f174515ea4f 100644
--- a/lld/test/ELF/lto/archive-mixed.test
+++ b/lld/test/ELF/lto/archive-mixed.test
@@ -37,9 +37,12 @@
; RUN: ld.lld --trace ref.o a.o.b.o.a other.o.a | \
; RUN: FileCheck %s --implicit-check-not={{.}}
+;; With order-independent extraction, both members are still pulled regardless
+;; of the bitcode/object mix; they are traced in archive-member order (a then b)
+;; rather than reference-discovery order.
; CHECK: ref.o
-; CHECK-NEXT: a.{{.*}}.b.{{.*}}.a(b.{{.*}})
; CHECK-NEXT: a.{{.*}}.b.{{.*}}.a(a.{{.*}})
+; CHECK-NEXT: a.{{.*}}.b.{{.*}}.a(b.{{.*}})
;--- a.ll
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
diff --git a/lld/test/ELF/lto/comdat-mixed-archive.test b/lld/test/ELF/lto/comdat-mixed-archive.test
index 88e294ed9872..9e8678562367 100644
--- a/lld/test/ELF/lto/comdat-mixed-archive.test
+++ b/lld/test/ELF/lto/comdat-mixed-archive.test
@@ -1,14 +1,15 @@
REQUIRES: x86
;; This checks a case when an archive contains a bitcode and a regular object
-;; files, and a comdat symbol is defined and used in both of them. Previously,
-;; lld could lose the flag that the symbol is used in a regular object file
-;; which led to the LTO backend internalizing the symbol and the linker
-;; reporting an "undefined symbol" error.
+;; files, and a comdat symbol is defined and used in both of them. lld must not
+;; lose the flag that the symbol is used in a regular object file, which would
+;; lead to the LTO backend internalizing the symbol and the linker reporting an
+;; "undefined symbol" error.
-;; In this test, group "foo" in "obj.o" is rejected in favor of "bc.bc" but we
-;; need to prevent LTO from internalizing "foo" as there is still a reference
-;; from outside the group in "obj.o".
+;; With order-independent extraction, both "obj.o" and "bc.bc" are pulled from
+;; the archive. The comdat group for "foo" in "obj.o" wins, but LTO must still
+;; not internalize "foo" as there is a reference from outside the group in
+;; "obj.o". The link succeeds with "foo" defined.
RUN: rm -rf %t.dir
RUN: split-file %s %t.dir
@@ -21,21 +22,17 @@ RUN: llvm-nm bc.bc --no-sort | FileCheck %s --check-prefix=BCSYM
RUN: llvm-ar rc lib.a obj.o bc.bc
RUN: ld.lld start.o lib.a -y foo -y bar -o /dev/null | FileCheck %s --check-prefix=TRACE
-;; "bar" should be encountered before "foo" so that it triggers the loading of
-;; "obj.o" while "foo" is still lazy.
BCSYM: U bar
BCSYM-NEXT: W foo
-;; Check that the symbols are handled in the expected order.
-TRACE: lib.a(obj.o): lazy definition of foo
-TRACE-NEXT: lib.a(obj.o): lazy definition of bar
-TRACE-NEXT: lib.a(bc.bc): definition of foo
-TRACE-NEXT: lib.a(bc.bc): reference to bar
+;; With order-independent extraction both members are pulled. "foo" is defined
+;; by the regular object "obj.o" (its comdat group wins over "bc.bc"); "bar" is
+;; also defined there. The reference to "foo" from outside the group keeps it
+;; from being internalized, so the LTO result references "bar" and the link
+;; succeeds with "foo" defined.
+TRACE: lib.a(obj.o): definition of foo
TRACE-NEXT: lib.a(obj.o): definition of bar
-TRACE-NEXT: lib.a(obj.o): reference to foo
-TRACE-NEXT: <internal>: reference to foo
-;; The definition of "foo" is visible outside the LTO result.
-TRACE-NEXT: {{.*}}.lto.o: definition of foo
+TRACE-NEXT: lib.a(bc.bc): reference to bar
TRACE-NEXT: {{.*}}.lto.o: reference to bar
;--- start.s
diff --git a/lld/test/ELF/lto/lazy-internal.ll b/lld/test/ELF/lto/lazy-internal.ll
index dc1ba45c0d71..26f8cf9a6111 100644
--- a/lld/test/ELF/lto/lazy-internal.ll
+++ b/lld/test/ELF/lto/lazy-internal.ll
@@ -6,8 +6,11 @@
; RUN: ld.lld %t2.a %t1.o -o %t.so -shared -save-temps
; RUN: llvm-dis %t.so.0.2.internalize.bc -o - | FileCheck %s
-; CHECK: define internal void @foo()
+;; Both the lazily-extracted @bar (from %t2.a, the first input) and @foo (from
+;; %t1.o) are internalized. With order-independent extraction the combined LTO
+;; module is ordered by input file index, so @bar precedes @foo.
; CHECK: define internal void @bar()
+; CHECK: define internal void @foo()
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
diff --git a/lld/test/ELF/lto/thinlto-emit-index-thin-archive.ll b/lld/test/ELF/lto/thinlto-emit-index-thin-archive.ll
index bcb90e21a872..d9d274a576b7 100644
--- a/lld/test/ELF/lto/thinlto-emit-index-thin-archive.ll
+++ b/lld/test/ELF/lto/thinlto-emit-index-thin-archive.ll
@@ -18,14 +18,19 @@
; CHECK-UNUSED: lib.a(unused.o at {{[1-9][0-9]+}})
;; Index files emitted from object files in a thin archive should have the
-;; offset in the archive specified to avoid collisions
+;; offset in the archive specified to avoid collisions. The two same-basename
+;; "thin.o" members must get distinct offsets.
+;; With order-independent extraction the archive members are resolved before
+;; ./dir1/main.o (the archive precedes main.o on the command line).
; RUN: FileCheck %s < c.resolution.txt --check-prefix CHECK-COLLISION
+; CHECK-COLLISION: dir2/lib.a(thin.o at [[#%u,FOO:]])
+; CHECK-COLLISION-NEXT: -r=./dir2/lib.a(thin.o at [[#FOO]]),foo,pl
+;; The second "thin.o" member must use a different offset (no collision).
+; CHECK-COLLISION-NOT: thin.o at [[#FOO]])
+; CHECK-COLLISION: dir2/lib.a(thin.o at [[#%u,BLAH:]])
+; CHECK-COLLISION-NEXT: -r=./dir2/lib.a(thin.o at [[#BLAH]]),blah,pl
; CHECK-COLLISION: dir1/main.o
-; CHECK-COLLISION: dir2/lib.a(thin.o at {{[1-9][0-9]+}})
-; CHECK-COLLISION-NEXT: -r=./dir2/lib.a(thin.o at {{[1-9][0-9]+}}),blah,pl
-; CHECK-COLLISION: dir2/lib.a(thin.o at {{[1-9][0-9]+}})
-; CHECK-COLLISION-NEXT: -r=./dir2/lib.a(thin.o at {{[1-9][0-9]+}}),foo,pl
;; Clean up
; RUN: rm -rf ./dir1/*.thinlto.bc
diff --git a/lld/test/ELF/lto/warn-backrefs.ll b/lld/test/ELF/lto/warn-backrefs.ll
deleted file mode 100644
index c63e47a79cdf..000000000000
--- a/lld/test/ELF/lto/warn-backrefs.ll
+++ /dev/null
@@ -1,30 +0,0 @@
-; REQUIRES: x86
-;; Test that the referenced filename is correct (not <internal> or lto.tmp).
-
-; RUN: split-file %s %t
-; RUN: llvm-as %t/a.ll -o %ta.o
-; RUN: llvm-as %t/b.ll -o %tb.o
-; RUN: ld.lld --warn-backrefs --start-lib %tb.o --end-lib %ta.o -o /dev/null 2>&1 | FileCheck %s
-
-; CHECK: warning: backward reference detected: f in {{.*}}a.o refers to {{.*}}b.o
-
-;--- a.ll
-target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
-target triple = "x86_64-unknown-linux-gnu"
-
-declare void @f()
-
-define void @_start() {
-entry:
- call void () @f()
- ret void
-}
-
-;--- b.ll
-target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
-target triple = "x86_64-unknown-linux-gnu"
-
-define void @f() {
-entry:
- ret void
-}
diff --git a/lld/test/ELF/shared-lazy.s b/lld/test/ELF/shared-lazy.s
index 0fa8f06884a3..20d21c7b991a 100644
--- a/lld/test/ELF/shared-lazy.s
+++ b/lld/test/ELF/shared-lazy.s
@@ -6,30 +6,32 @@
# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux ref.s -o ref.o
# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux ref2.s -o ref2.o
# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux weakref2.s -o weakref2.o
-# RUN: ld.lld a.a b.so ref.o -shared -o 1.so
-# RUN: llvm-readelf --dyn-syms 1.so | FileCheck %s
+## A shared definition seen before the archive satisfies the reference, so the
+## archive member is not extracted; the shared definitions are used.
# RUN: ld.lld a.so a.a ref.o -shared -o 1.so
# RUN: llvm-readelf --dyn-syms 1.so | FileCheck %s
-## The definitions from a.so are used and we don't extract a member from the
-## archive.
-
# CHECK: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND x1
# CHECK-NEXT: 0000000000000000 0 NOTYPE GLOBAL DEFAULT UND x2
-## The extracted x1 is defined as STB_GLOBAL.
+## The archive is extracted in preference to a shared definition.
+# RUN: ld.lld a.a b.so ref.o -o 2.so -shared
+# RUN: llvm-readelf --dyn-symbols 2.so | FileCheck %s --check-prefix=CHECK2
# RUN: ld.lld ref.o a.a b.so -o 2.so -shared
# RUN: llvm-readelf --dyn-symbols 2.so | FileCheck %s --check-prefix=CHECK2
# RUN: ld.lld a.a ref.o b.so -o 2.so -shared
# RUN: llvm-readelf --dyn-symbols 2.so | FileCheck %s --check-prefix=CHECK2
+# RUN: ld.lld a.a a.so ref2.o -o 2.so -shared
+# RUN: llvm-readelf --dyn-symbols 2.so | FileCheck %s --check-prefix=CHECK2
# CHECK2: {{.*}} 0 NOTYPE GLOBAL DEFAULT [[#]] x1
# CHECK2-NEXT: {{.*}} 0 NOTYPE WEAK DEFAULT [[#]] x2
-## The extracted x2 is defined as STB_WEAK. x1 is not referenced by any relocatable object file.
-# RUN: ld.lld a.a ref2.o b.so -o 2.so -shared
-# RUN: llvm-readelf --dyn-syms 2.so | FileCheck %s --check-prefix=CHECK2
-# RUN: ld.lld a.a a.so ref2.o -o 3.so -shared
+## ref2.o references only x2. The member is not pulled in when a stronger
+## definition exists (b.so's strong x2) or a shared definition of equal strength
+## is seen first (a.so before a.a); x2 resolves to the shared definition and x1
+## is absent.
+# RUN: ld.lld a.a ref2.o b.so -o 3.so -shared
# RUN: llvm-readelf --dyn-syms 3.so | FileCheck %s --check-prefix=CHECK3
# RUN: ld.lld a.so a.a ref2.o -o 3.so -shared
# RUN: llvm-readelf --dyn-syms 3.so | FileCheck %s --check-prefix=CHECK3
diff --git a/lld/test/ELF/trace-symbols.s b/lld/test/ELF/trace-symbols.s
index 785414e2bd5b..5770086cf43b 100644
--- a/lld/test/ELF/trace-symbols.s
+++ b/lld/test/ELF/trace-symbols.s
@@ -68,9 +68,13 @@
# ARCHIVEDCOMMON-NOT: trace-symbols.s.tmp1.a(trace-symbols.s.tmp1): definition of \
# common
+## Extraction is order-independent: the strong foo from %t2.so satisfies the
+## reference, so the archive member providing a weak foo is not extracted and
+## does not appear in the trace.
# RUN: ld.lld -y foo %t %t1.a %t2.so -o %t3 | \
-# RUN: FileCheck -check-prefix=ARCHIVED1FOO %s
-# ARCHIVED1FOO: trace-symbols.s.tmp1.a(trace-symbols.s.tmp1): definition of foo
+# RUN: FileCheck -check-prefix=ARCHIVED1FOO %s --implicit-check-not=foo
+# ARCHIVED1FOO: trace-symbols.s.tmp: reference to foo
+# ARCHIVED1FOO-NEXT: trace-symbols.s.tmp2.so: shared definition of foo
# RUN: ld.lld -y foo %t %t1.a %t2.a -o %t3 | \
# RUN: FileCheck -check-prefix=ARCHIVED2FOO %s
@@ -84,9 +88,20 @@
# RUN: FileCheck -check-prefix=SHLIBRBAR %s
# SHLIBRBAR: trace-symbols.s.tmp1.so: reference to bar
+## A shared file's default-versioned definition is traced under the unversioned
+## name first.
+# RUN: echo 'v1 { global: foo; local: *; };' > %t.ver
+# RUN: ld.lld -shared --version-script=%t.ver %t2 -o %t4.so
+# RUN: ld.lld -y foo -y foo@v1 %t %t4.so -o %t3 | \
+# RUN: FileCheck -check-prefix=SHLIBDVER %s --implicit-check-not=foo
+# SHLIBDVER: trace-symbols.s.tmp: reference to foo
+# SHLIBDVER-NEXT: trace-symbols.s.tmp4.so: shared definition of foo
+# SHLIBDVER-NEXT: trace-symbols.s.tmp4.so: shared definition of foo@v1
+
# RUN: ld.lld -y foo -y bar %t -u bar --start-lib %t1 %t2 --end-lib -o %t3 | \
# RUN: FileCheck -check-prefix=STARTLIB %s
-# STARTLIB: trace-symbols.s.tmp1: reference to bar
+## bar is defined by %t2 (the strong definition wins), so -u bar extracts %t2.
+# STARTLIB: trace-symbols.s.tmp2: definition of bar
## Check we do not crash when trying to trace special symbol.
# RUN: ld.lld -trace-symbol=_end %t %t1 %t2 -o /dev/null
diff --git a/lld/test/ELF/warn-backrefs.s b/lld/test/ELF/warn-backrefs.s
deleted file mode 100644
index 453017eb1c8e..000000000000
--- a/lld/test/ELF/warn-backrefs.s
+++ /dev/null
@@ -1,112 +0,0 @@
-# REQUIRES: x86
-
-# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t1.o
-# RUN: echo '.globl foo; foo:' | llvm-mc -filetype=obj -triple=x86_64 - -o %t2.o
-# RUN: rm -f %t2.a
-# RUN: llvm-ar rcs %t2.a %t2.o
-# RUN: ld.lld -shared %t2.o -o %t2.so
-
-## A forward reference is accepted by a traditional Unix linker.
-# RUN: ld.lld --fatal-warnings %t1.o %t2.a -o /dev/null
-# RUN: ld.lld --fatal-warnings --warn-backrefs %t1.o %t2.a -o /dev/null
-# RUN: ld.lld --fatal-warnings --warn-backrefs %t1.o --start-lib %t2.o --end-lib -o /dev/null
-
-# RUN: echo 'INPUT("%t1.o" "%t2.a")' > %t1.lds
-# RUN: ld.lld --fatal-warnings --warn-backrefs %t1.lds -o /dev/null
-
-## A backward reference from %t1.o to %t2.a
-## Warn unless the archive is excluded by --warn-backrefs-exclude
-# RUN: ld.lld --fatal-warnings %t2.a %t1.o -o /dev/null
-# RUN: ld.lld --warn-backrefs %t2.a %t1.o -o /dev/null 2>&1 | FileCheck %s
-# RUN: ld.lld --warn-backrefs --no-warn-backrefs %t2.a %t1.o -o /dev/null 2>&1 | count 0
-# RUN: ld.lld --warn-backrefs %t2.a '-(' %t1.o '-)' -o /dev/null 2>&1 | FileCheck %s
-# RUN: ld.lld --warn-backrefs --warn-backrefs-exclude='*3.a' %t2.a %t1.o -o /dev/null 2>&1 | FileCheck %s
-# RUN: ld.lld --fatal-warnings --warn-backrefs --warn-backrefs-exclude='*2.a(*2.o)' %t2.a %t1.o -o /dev/null
-# RUN: ld.lld --fatal-warnings --warn-backrefs --warn-backrefs-exclude '*2.a(*2.o)' \
-# RUN: --warn-backrefs-exclude not_exist %t2.a %t1.o -o /dev/null
-## Without --warn-backrefs, --warn-backrefs-exclude is ignored.
-# RUN: ld.lld --fatal-warnings --warn-backrefs-exclude=not_exist %t2.a %t1.o -o /dev/null
-
-## Placing the definition and the backward reference in a group can suppress the warning.
-# RUN: echo 'GROUP("%t2.a" "%t1.o")' > %t2.lds
-# RUN: ld.lld --fatal-warnings --warn-backrefs %t2.lds -o /dev/null
-# RUN: ld.lld --fatal-warnings --warn-backrefs '-(' %t2.a %t1.o '-)' -o /dev/null
-# RUN: ld.lld --fatal-warnings --warn-backrefs --start-group %t2.a %t1.o --end-group -o /dev/null
-
-## A backward reference from %t1.o to %t2.a (added by %t3.lds).
-# RUN: echo 'GROUP("%t2.a")' > %t3.lds
-# RUN: ld.lld --warn-backrefs %t3.lds %t1.o -o /dev/null 2>&1 | FileCheck %s
-# RUN: ld.lld --fatal-warnings --warn-backrefs '-(' %t3.lds %t1.o '-)' -o /dev/null
-# RUN: ld.lld --fatal-warnings --warn-backrefs --warn-backrefs-exclude='*2.a(*2.o)' -o /dev/null %t3.lds %t1.o
-## If a lazy definition appears after the backward reference, don't warn.
-# RUN: ld.lld --fatal-warnings --warn-backrefs %t3.lds %t1.o %t3.lds -o /dev/null
-
-# CHECK: warning: backward reference detected: foo in {{.*}}1.o refers to {{.*}}2.a
-
-## A backward reference from %t1.o to %t2.o
-## --warn-backrefs-exclude= applies to --start-lib covered object files.
-# RUN: ld.lld --warn-backrefs --start-lib %t2.o --end-lib %t1.o -o /dev/null 2>&1 | \
-# RUN: FileCheck --check-prefix=OBJECT %s
-# RUN: ld.lld --fatal-warnings --warn-backrefs --warn-backrefs-exclude=%/t2.o --start-lib %/t2.o --end-lib %t1.o -o /dev/null
-## If a lazy definition appears after the backward reference, don't warn.
-# RUN: ld.lld --fatal-warnings --warn-backrefs --start-lib %t2.o --end-lib %t1.o --start-lib %t2.o --end-lib -o /dev/null
-
-# OBJECT: warning: backward reference detected: foo in {{.*}}1.o refers to {{.*}}2.o
-
-## Back reference from an fetched --start-lib to a previous --start-lib.
-# RUN: ld.lld -m elf_x86_64 -u _start --warn-backrefs --start-lib %/t2.o --end-lib \
-# RUN: --start-lib %t1.o --end-lib -o /dev/null 2>&1 | FileCheck --check-prefix=OBJECT %s
-## --warn-backrefs-exclude=%/t2.o can be used for a fetched --start-lib.
-# RUN: ld.lld --fatal-warnings -m elf_x86_64 -u _start --warn-backrefs --warn-backrefs-exclude=%/t2.o --start-lib %/t2.o --end-lib --start-lib %t1.o --end-lib -o /dev/null
-
-## Don't warn if the definition and the backward reference are in a group.
-# RUN: echo '.globl bar; bar:' | llvm-mc -filetype=obj -triple=x86_64 - -o %t3.o
-# RUN: echo '.globl foo; foo: call bar' | llvm-mc -filetype=obj -triple=x86_64 - -o %t4.o
-# RUN: ld.lld --fatal-warnings --warn-backrefs %t1.o --start-lib %t3.o %t4.o --end-lib -o /dev/null
-# RUN: rm -f %t34.a && llvm-ar rcS %t34.a %t3.o %t4.o
-# RUN: ld.lld --fatal-warnings --warn-backrefs %t1.o %t34.a -o /dev/null
-
-## We don't report backward references to weak symbols as they can be overridden later.
-# RUN: echo '.weak foo; foo:' | llvm-mc -filetype=obj -triple=x86_64 - -o %tweak.o
-# RUN: ld.lld --fatal-warnings --warn-backrefs --start-lib %tweak.o --end-lib %t1.o %t2.o -o /dev/null
-
-## Check common symbols. A common sym might later be replaced by a non-common definition.
-# RUN: echo '.comm obj, 4' | llvm-mc -filetype=obj -triple=x86_64 -o %tcomm.o
-# RUN: echo '.type obj,@object; .data; .globl obj; .p2align 2; obj: .long 55; .size obj, 4' | llvm-mc -filetype=obj -triple=x86_64 -o %tstrong.o
-# RUN: echo '.globl foo; foo: movl obj(%rip), %eax' | llvm-mc -triple=x86_64 -filetype=obj -o %t5.o
-# RUN: llvm-ar rcs %tcomm.a %tcomm.o
-# RUN: llvm-ar rcs %tstrong.a %tstrong.o
-# RUN: ld.lld --warn-backrefs %tcomm.a %t1.o %t5.o 2>&1 -o /dev/null | FileCheck --check-prefix=COMM %s
-# RUN: ld.lld --fatal-warnings --fortran-common --warn-backrefs %tcomm.a %t1.o %t5.o %tstrong.a 2>&1 -o /dev/null
-# RUN: ld.lld --warn-backrefs --no-fortran-common %tcomm.a %t1.o %t5.o %tstrong.a 2>&1 -o /dev/null | FileCheck --check-prefix=COMM %s
-
-# COMM: ld.lld: warning: backward reference detected: obj in {{.*}}5.o refers to {{.*}}comm.a
-
-## If a lazy definition appears after the backward reference, don't warn.
-## A traditional Unix linker will resolve the reference to the later definition.
-# RUN: ld.lld --fatal-warnings --warn-backrefs %t2.a %t1.o %t2.a -o /dev/null
-
-## lld fetches the archive while GNU ld resolves the reference to the shared definition.
-## Warn because the resolution rules are different.
-# RUN: ld.lld --warn-backrefs %t2.a %t1.o %t2.so -o /dev/null 2>&1 | FileCheck %s
-
-## This is a limitation. The resolution rules are different but
-## --warn-backrefs does not warn.
-# RUN: ld.lld --fatal-warnings --warn-backrefs %t2.a %t1.o %t2.so %t2.a -o /dev/null
-
-## In GNU linkers, -u does not make a backward reference.
-# RUN: ld.lld --fatal-warnings --warn-backrefs -u foo %t2.a %t1.o -o /dev/null
-
-## -u does not make a backward reference.
-# RUN: ld.lld --fatal-warnings --warn-backrefs -u foo %t2.a %t1.o -o /dev/null
-
-## --defsym does not make a backward reference, but it does not suppress the warning due to another file.
-# RUN: ld.lld --fatal-warnings --warn-backrefs --defsym=x=foo -e 0 %t2.a -o /dev/null
-# RUN: ld.lld --warn-backrefs --defsym=x=foo %t2.a %t1.o -o /dev/null 2>&1 | FileCheck %s
-
-# RUN: not ld.lld --warn-backrefs-exclude='[' 2>&1 | FileCheck --check-prefix=INVALID %s
-# INVALID: error: --warn-backrefs-exclude: invalid glob pattern, unmatched '[': [
-
-.globl _start, foo
-_start:
- call foo
diff --git a/lld/test/ELF/why-extract.s b/lld/test/ELF/why-extract.s
index 3235bce5a716..d1270192a4ae 100644
--- a/lld/test/ELF/why-extract.s
+++ b/lld/test/ELF/why-extract.s
@@ -26,6 +26,11 @@
# RUN: rm -f why2.txt && not ld.lld main.o a_b.a b.a err.o --why-extract=why2.txt
# RUN: FileCheck %s --input-file=why2.txt --check-prefix=CHECK2 --match-full-lines --strict-whitespace
+## -y replays a traced symbol's resolution serially; the extraction is still
+## recorded.
+# RUN: rm -f why2.txt && ld.lld main.o a_b.a b.a -y a -y _Z1bv --why-extract=why2.txt
+# RUN: FileCheck %s --input-file=why2.txt --check-prefix=CHECK2 --match-full-lines --strict-whitespace
+
# CHECK2:reference extracted symbol
# CHECK2-NEXT:main.o a_b.a(a_b.o) a
# CHECK2-NEXT:a_b.a(a_b.o) b.a(b.o) b()
@@ -42,8 +47,8 @@
# CHECK3-NEXT:main.o a_b.a(a_b.o) a
# CHECK4:reference extracted symbol
-# CHECK4-NEXT:a_b.a(a_b.o) b.a(b.o) b()
# CHECK4-NEXT:main.o a_b.a(a_b.o) a
+# CHECK4-NEXT:a_b.a(a_b.o) b.a(b.o) b()
# RUN: ld.lld main.o a_b.a b.a --no-demangle --why-extract=- | FileCheck %s --check-prefix=MANGLED
diff --git a/lld/test/ELF/wrap-extract-real.s b/lld/test/ELF/wrap-extract-real.s
index 52f98e5a82fc..ad08d850e319 100644
--- a/lld/test/ELF/wrap-extract-real.s
+++ b/lld/test/ELF/wrap-extract-real.s
@@ -29,6 +29,20 @@
# WRAP_REAL-NEXT: {{.*}} 0 NOTYPE GLOBAL DEFAULT [[#]] __wrap_foo
# WRAP_REAL-NEXT: {{.*}} 0 NOTYPE GLOBAL DEFAULT [[#]] foo
+## A __real_ reference inside a member extracted for another --wrap entry is
+## seen as well, whatever the --wrap order.
+# RUN: llvm-mc -filetype=obj -triple=x86_64 foo_real_bar.s -o foo_real_bar.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64 bar.s -o bar.o
+# RUN: ld.lld _start.o ref__real_foo.o --start-lib foo_real_bar.o --end-lib \
+# RUN: --start-lib bar.o --end-lib --wrap foo --wrap bar -o cross1.elf
+# RUN: llvm-readelf --symbols cross1.elf | FileCheck %s --check-prefix=CROSS
+# RUN: ld.lld _start.o ref__real_foo.o --start-lib foo_real_bar.o --end-lib \
+# RUN: --start-lib bar.o --end-lib --wrap bar --wrap foo -o cross2.elf
+# RUN: llvm-readelf --symbols cross2.elf | FileCheck %s --check-prefix=CROSS
+
+# CROSS-DAG: {{.*}} 0 NOTYPE GLOBAL DEFAULT [[#]] foo
+# CROSS-DAG: {{.*}} 0 NOTYPE GLOBAL DEFAULT [[#]] bar
+
#--- _start.s
.global _start; _start:; ret
@@ -40,3 +54,9 @@ call __real_foo
#--- foo.s
.global foo; foo:; ret
+
+#--- foo_real_bar.s
+.global foo; foo:; call __real_bar
+
+#--- bar.s
+.global bar; bar:; ret
base-commit: 271af38dfc3aa02e329821daf46730686e52fb1c
--
2.55.0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment