diff --git a/lld/MachO/Config.h b/lld/MachO/Config.h --- a/lld/MachO/Config.h +++ b/lld/MachO/Config.h @@ -170,10 +170,6 @@ std::vector sectionAlignments; std::vector segmentProtections; - llvm::DenseMap priorities; - llvm::MapVector, - uint64_t> - callGraphProfile; bool callGraphProfileSort = false; llvm::StringRef printSymbolOrder; diff --git a/lld/MachO/Driver.cpp b/lld/MachO/Driver.cpp --- a/lld/MachO/Driver.cpp +++ b/lld/MachO/Driver.cpp @@ -1453,7 +1453,7 @@ StringRef orderFile = args.getLastArgValue(OPT_order_file); if (!orderFile.empty()) - parseOrderFile(orderFile); + priorityBuilder.parseOrderFile(orderFile); referenceStubBinder(); @@ -1510,7 +1510,7 @@ gatherInputSections(); if (config->callGraphProfileSort) - extractCallGraphProfile(); + priorityBuilder.extractCallGraphProfile(); if (config->deadStrip) markLive(); diff --git a/lld/MachO/SectionPriorities.h b/lld/MachO/SectionPriorities.h --- a/lld/MachO/SectionPriorities.h +++ b/lld/MachO/SectionPriorities.h @@ -15,41 +15,53 @@ namespace lld { namespace macho { -// Reads every input section's call graph profile, and combines them into -// config->callGraphProfile. If an order file is present, any edges where one -// or both of the vertices are specified in the order file are discarded. -void extractCallGraphProfile(); +using SectionPair = std::pair; -// Reads the order file at `path` into config->priorities. -// -// An order file has one entry per line, in the following format: -// -// :: -// -// and are optional. If not specified, then that entry -// matches any symbol of that name. Parsing this format is not quite -// straightforward because the symbol name itself can contain colons, so when -// encountering a colon, we consider the preceding characters to decide if it -// can be a valid CPU type or file path. -// -// If a symbol is matched by multiple entries, then it takes the lowest-ordered -// entry (the one nearest to the front of the list.) -// -// The file can also have line comments that start with '#'. -void parseOrderFile(StringRef path); +class PriorityBuilder { +public: + // Reads every input section's call graph profile, and combines them into + // callGraphProfile. If an order file is present, any edges where one or both + // of the vertices are specified in the order file are discarded. + void extractCallGraphProfile(); -// Returns layout priorities for some or all input sections. Sections are laid -// out in decreasing order; that is, a higher priority section will be closer -// to the beginning of its output section. -// -// If either an order file or a call graph profile are present, this is used -// as the source of priorities. If both are present, the order file takes -// precedence, but the call graph profile is still used for symbols that don't -// appear in the order file. If neither is present, an empty map is returned. -// -// Each section gets assigned the priority of the highest-priority symbol it -// contains. -llvm::DenseMap buildInputSectionPriorities(); + // Reads the order file at `path` into config->priorities. + // + // An order file has one entry per line, in the following format: + // + // :: + // + // and are optional. If not specified, then that entry + // matches any symbol of that name. Parsing this format is not quite + // straightforward because the symbol name itself can contain colons, so when + // encountering a colon, we consider the preceding characters to decide if it + // can be a valid CPU type or file path. + // + // If a symbol is matched by multiple entries, then it takes the + // lowest-ordered entry (the one nearest to the front of the list.) + // + // The file can also have line comments that start with '#'. + void parseOrderFile(StringRef path); + + // Returns layout priorities for some or all input sections. Sections are laid + // out in decreasing order; that is, a higher priority section will be closer + // to the beginning of its output section. + // + // If either an order file or a call graph profile are present, this is used + // as the source of priorities. If both are present, the order file takes + // precedence, but the call graph profile is still used for symbols that don't + // appear in the order file. If neither is present, an empty map is returned. + // + // Each section gets assigned the priority of the highest-priority symbol it + // contains. + llvm::DenseMap buildInputSectionPriorities(); + +private: + llvm::Optional getSymbolPriority(const Defined *sym); + llvm::DenseMap priorities; + llvm::MapVector callGraphProfile; +}; + +extern PriorityBuilder priorityBuilder; } // namespace macho } // namespace lld diff --git a/lld/MachO/SectionPriorities.cpp b/lld/MachO/SectionPriorities.cpp --- a/lld/MachO/SectionPriorities.cpp +++ b/lld/MachO/SectionPriorities.cpp @@ -34,9 +34,11 @@ using namespace lld; using namespace lld::macho; +PriorityBuilder macho::priorityBuilder; + namespace { -size_t lowestPriority = std::numeric_limits::max(); +size_t highestAvailablePriority = std::numeric_limits::max(); struct Edge { int from; @@ -62,7 +64,7 @@ class CallGraphSort { public: - CallGraphSort(); + CallGraphSort(const MapVector &profile); DenseMap run(); @@ -75,13 +77,9 @@ constexpr int MAX_DENSITY_DEGRADATION = 8; } // end anonymous namespace -using SectionPair = std::pair; - -// Take the edge list in config->callGraphProfile, resolve symbol names to -// Symbols, and generate a graph between InputSections with the provided -// weights. -CallGraphSort::CallGraphSort() { - MapVector &profile = config->callGraphProfile; +// Take the edge list in callGraphProfile, resolve symbol names to Symbols, and +// generate a graph between InputSections with the provided weights. +CallGraphSort::CallGraphSort(const MapVector &profile) { DenseMap secToCluster; auto getOrCreateCluster = [&](const InputSection *isec) -> int { @@ -94,7 +92,7 @@ }; // Create the graph - for (std::pair &c : profile) { + for (const std::pair &c : profile) { const auto fromSec = c.first.first->canonical(); const auto toSec = c.first.second->canonical(); uint64_t weight = c.second; @@ -212,7 +210,7 @@ // priority 0 and be placed at the end of sections. // NB: This is opposite from COFF/ELF to be compatible with the existing // order-file code. - int curOrder = lowestPriority; + int curOrder = highestAvailablePriority; for (int leader : sorted) { for (int i = leader;;) { orderMap[sections[i]] = curOrder--; @@ -251,12 +249,12 @@ return orderMap; } -static Optional getSymbolPriority(const Defined *sym) { +Optional macho::PriorityBuilder::getSymbolPriority(const Defined *sym) { if (sym->isAbsolute()) return None; - auto it = config->priorities.find(sym->getName()); - if (it == config->priorities.end()) + auto it = priorities.find(sym->getName()); + if (it == priorities.end()) return None; const SymbolPriorityEntry &entry = it->second; const InputFile *f = sym->isec->getFile(); @@ -273,9 +271,9 @@ return std::max(entry.objectFiles.lookup(filename), entry.anyObjectFile); } -void macho::extractCallGraphProfile() { +void macho::PriorityBuilder::extractCallGraphProfile() { TimeTraceScope timeScope("Extract call graph profile"); - bool hasOrderFile = !config->priorities.empty(); + bool hasOrderFile = !priorities.empty(); for (const InputFile *file : inputFiles) { auto *obj = dyn_cast_or_null(file); if (!obj) @@ -289,13 +287,13 @@ (hasOrderFile && (getSymbolPriority(fromSym) || getSymbolPriority(toSym)))) continue; - config->callGraphProfile[{fromSym->isec, toSym->isec}] += entry.count; + callGraphProfile[{fromSym->isec, toSym->isec}] += entry.count; } } } -void macho::parseOrderFile(StringRef path) { - assert(config->callGraphProfile.empty() && +void macho::PriorityBuilder::parseOrderFile(StringRef path) { + assert(callGraphProfile.empty() && "Order file must be parsed before call graph profile is processed"); Optional buffer = readFile(path); if (!buffer) { @@ -304,7 +302,6 @@ } MemoryBufferRef mbref = *buffer; - size_t priority = std::numeric_limits::max(); for (StringRef line : args::getLines(mbref)) { StringRef objectFile, symbol; line = line.take_until([](char c) { return c == '#'; }); // ignore comments @@ -339,34 +336,34 @@ symbol = line.trim(); if (!symbol.empty()) { - SymbolPriorityEntry &entry = config->priorities[symbol]; + SymbolPriorityEntry &entry = priorities[symbol]; if (!objectFile.empty()) - entry.objectFiles.insert(std::make_pair(objectFile, priority)); + entry.objectFiles.insert( + std::make_pair(objectFile, highestAvailablePriority)); else - entry.anyObjectFile = std::max(entry.anyObjectFile, priority); + entry.anyObjectFile = + std::max(entry.anyObjectFile, highestAvailablePriority); } - --priority; + --highestAvailablePriority; } - lowestPriority = priority; -} - -// Sort sections by the profile data provided by __LLVM,__cg_profile sections. -// -// This first builds a call graph based on the profile data then merges sections -// according to the C³ heuristic. All clusters are then sorted by a density -// metric to further improve locality. -static DenseMap computeCallGraphProfileOrder() { - TimeTraceScope timeScope("Call graph profile sort"); - return CallGraphSort().run(); } -DenseMap macho::buildInputSectionPriorities() { +DenseMap +macho::PriorityBuilder::buildInputSectionPriorities() { DenseMap sectionPriorities; - if (config->callGraphProfileSort) - sectionPriorities = computeCallGraphProfileOrder(); + if (config->callGraphProfileSort) { + // Sort sections by the profile data provided by __LLVM,__cg_profile + // sections. + // + // This first builds a call graph based on the profile data then merges + // sections according to the C³ heuristic. All clusters are then sorted by a + // density metric to further improve locality. + TimeTraceScope timeScope("Call graph profile sort"); + sectionPriorities = CallGraphSort(callGraphProfile).run(); + } - if (config->priorities.empty()) + if (priorities.empty()) return sectionPriorities; auto addSym = [&](const Defined *sym) { diff --git a/lld/MachO/Writer.cpp b/lld/MachO/Writer.cpp --- a/lld/MachO/Writer.cpp +++ b/lld/MachO/Writer.cpp @@ -860,7 +860,7 @@ sortOutputSegments(); DenseMap isecPriorities = - buildInputSectionPriorities(); + priorityBuilder.buildInputSectionPriorities(); uint32_t sectionIndex = 0; for (OutputSegment *seg : outputSegments) {