diff --git a/lld/MachO/Config.h b/lld/MachO/Config.h --- a/lld/MachO/Config.h +++ b/lld/MachO/Config.h @@ -170,9 +170,6 @@ std::vector sectionAlignments; std::vector segmentProtections; - llvm::MapVector, - uint64_t> - callGraphProfile; bool callGraphProfileSort = false; llvm::StringRef printSymbolOrder; diff --git a/lld/MachO/SectionPriorities.h b/lld/MachO/SectionPriorities.h --- a/lld/MachO/SectionPriorities.h +++ b/lld/MachO/SectionPriorities.h @@ -15,12 +15,33 @@ namespace lld { namespace macho { +struct Edge { + int from; + uint64_t weight; +}; + +struct Cluster { + Cluster(int sec, size_t s) : next(sec), prev(sec), size(s) {} + + double getDensity() const { + if (size == 0) + return 0; + return double(weight) / double(size); + } + + int next; + int prev; + uint64_t size; + uint64_t weight = 0; + uint64_t initialWeight = 0; + Edge bestPred = {-1, 0}; +}; + class PriorityBuilder { public: - // 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(); + PriorityBuilder() : callGraphSort(*this) {} + + void extractCallGraphProfile() { callGraphSort.extractCallGraphProfile(); } // Reads the order file at `path` into config->priorities. // @@ -54,8 +75,34 @@ llvm::DenseMap buildInputSectionPriorities(); private: - llvm::Optional getSymbolPriority(const Defined *sym); + llvm::Optional getSymbolPriority(const Defined *sym) const; llvm::DenseMap priorities; + + class CallGraphSort { + using SectionPair = std::pair; + + public: + CallGraphSort(PriorityBuilder &priorityBuilder); + + llvm::DenseMap run(); + + // 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(); + + const llvm::MapVector &getProfile() { + return profile; + } + + private: + const PriorityBuilder &builder; + std::vector clusters; + std::vector sections; + + llvm::MapVector profile; + } callGraphSort; }; extern std::unique_ptr priorityBuilder; diff --git a/lld/MachO/SectionPriorities.cpp b/lld/MachO/SectionPriorities.cpp --- a/lld/MachO/SectionPriorities.cpp +++ b/lld/MachO/SectionPriorities.cpp @@ -41,50 +41,17 @@ size_t lowestPriority = std::numeric_limits::max(); -struct Edge { - int from; - uint64_t weight; -}; - -struct Cluster { - Cluster(int sec, size_t s) : next(sec), prev(sec), size(s) {} - - double getDensity() const { - if (size == 0) - return 0; - return double(weight) / double(size); - } - - int next; - int prev; - uint64_t size; - uint64_t weight = 0; - uint64_t initialWeight = 0; - Edge bestPred = {-1, 0}; -}; - -class CallGraphSort { -public: - CallGraphSort(); - - DenseMap run(); - -private: - std::vector clusters; - std::vector sections; -}; // Maximum amount the combined cluster density can be worse than the original // cluster to consider merging. 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; +macho::PriorityBuilder::CallGraphSort::CallGraphSort( + PriorityBuilder &priorityBuilder) + : builder(priorityBuilder) { DenseMap secToCluster; auto getOrCreateCluster = [&](const InputSection *isec) -> int { @@ -161,7 +128,8 @@ // Group InputSections into clusters using the Call-Chain Clustering heuristic // then sort the clusters by density. -DenseMap CallGraphSort::run() { +DenseMap +macho::PriorityBuilder::CallGraphSort::run() { const uint64_t maxClusterSize = target->getPageSize(); // Cluster indices sorted by density. @@ -254,7 +222,8 @@ return orderMap; } -Optional macho::PriorityBuilder::getSymbolPriority(const Defined *sym) { +Optional +macho::PriorityBuilder::getSymbolPriority(const Defined *sym) const { if (sym->isAbsolute()) return None; @@ -276,9 +245,9 @@ return std::max(entry.objectFiles.lookup(filename), entry.anyObjectFile); } -void macho::PriorityBuilder::extractCallGraphProfile() { +void macho::PriorityBuilder::CallGraphSort::extractCallGraphProfile() { TimeTraceScope timeScope("Extract call graph profile"); - bool hasOrderFile = !priorities.empty(); + bool hasOrderFile = !builder.priorities.empty(); for (const InputFile *file : inputFiles) { auto *obj = dyn_cast_or_null(file); if (!obj) @@ -289,16 +258,16 @@ auto *fromSym = dyn_cast_or_null(obj->symbols[entry.fromIndex]); auto *toSym = dyn_cast_or_null(obj->symbols[entry.toIndex]); if (!fromSym || !toSym || - (hasOrderFile && - (getSymbolPriority(fromSym) || getSymbolPriority(toSym)))) + (hasOrderFile && (builder.getSymbolPriority(fromSym) || + builder.getSymbolPriority(toSym)))) continue; - config->callGraphProfile[{fromSym->isec, toSym->isec}] += entry.count; + profile[{fromSym->isec, toSym->isec}] += entry.count; } } } void macho::PriorityBuilder::parseOrderFile(StringRef path) { - assert(config->callGraphProfile.empty() && + assert(callGraphSort.getProfile().empty() && "Order file must be parsed before call graph profile is processed"); Optional buffer = readFile(path); if (!buffer) { @@ -354,21 +323,19 @@ 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::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.run(); + } if (priorities.empty()) return sectionPriorities;