1 //===- CallGraphSort.cpp --------------------------------------------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 /// Implementation of Call-Chain Clustering from: Optimizing Function Placement
10 /// for Large-Scale Data-Center Applications
11 /// https://research.fb.com/wp-content/uploads/2017/01/cgo2017-hfsort-final1.pdf
13 /// The goal of this algorithm is to improve runtime performance of the final
14 /// executable by arranging code sections such that page table and i-cache
15 /// misses are minimized.
19 /// * An ordered list of input sections which are layed out as a unit. At the
20 /// beginning of the algorithm each input section has its own cluster and
21 /// the weight of the cluster is the sum of the weight of all incomming
23 /// * Call-Chain Clustering (C³) Heuristic
24 /// * Defines when and how clusters are combined. Pick the highest weighted
25 /// input section then add it to its most likely predecessor if it wouldn't
26 /// penalize it too much.
28 /// * The weight of the cluster divided by the size of the cluster. This is a
29 /// proxy for the ammount of execution time spent per byte of the cluster.
31 /// It does so given a call graph profile by the following:
32 /// * Build a weighted call graph from the call graph profile
33 /// * Sort input sections by weight
34 /// * For each input section starting with the highest weight
35 /// * Find its most likely predecessor cluster
36 /// * Check if the combined cluster would be too large, or would have too low
38 /// * If not, then combine the clusters.
39 /// * Sort non-empty clusters by density
41 //===----------------------------------------------------------------------===//
43 #include "CallGraphSort.h"
44 #include "OutputSections.h"
45 #include "SymbolTable.h"
50 using namespace lld::elf;
59 Cluster(int sec, size_t s) : sections{sec}, size(s) {}
61 double getDensity() const {
64 return double(weight) / double(size);
67 std::vector<int> sections;
70 uint64_t initialWeight = 0;
71 Edge bestPred = {-1, 0};
78 DenseMap<const InputSectionBase *, int> run();
81 std::vector<Cluster> clusters;
82 std::vector<const InputSectionBase *> sections;
87 // Maximum ammount the combined cluster density can be worse than the original
88 // cluster to consider merging.
89 constexpr int MAX_DENSITY_DEGRADATION = 8;
91 // Maximum cluster size in bytes.
92 constexpr uint64_t MAX_CLUSTER_SIZE = 1024 * 1024;
93 } // end anonymous namespace
96 std::pair<const InputSectionBase *, const InputSectionBase *>;
98 // Take the edge list in Config->CallGraphProfile, resolve symbol names to
99 // Symbols, and generate a graph between InputSections with the provided
101 CallGraphSort::CallGraphSort() {
102 MapVector<SectionPair, uint64_t> &profile = config->callGraphProfile;
103 DenseMap<const InputSectionBase *, int> secToCluster;
105 auto getOrCreateNode = [&](const InputSectionBase *isec) -> int {
106 auto res = secToCluster.insert(std::make_pair(isec, clusters.size()));
108 sections.push_back(isec);
109 clusters.emplace_back(clusters.size(), isec->getSize());
111 return res.first->second;
115 for (std::pair<SectionPair, uint64_t> &c : profile) {
116 const auto *fromSB = cast<InputSectionBase>(c.first.first->repl);
117 const auto *toSB = cast<InputSectionBase>(c.first.second->repl);
118 uint64_t weight = c.second;
120 // Ignore edges between input sections belonging to different output
121 // sections. This is done because otherwise we would end up with clusters
122 // containing input sections that can't actually be placed adjacently in the
123 // output. This messes with the cluster size and density calculations. We
124 // would also end up moving input sections in other output sections without
125 // moving them closer to what calls them.
126 if (fromSB->getOutputSection() != toSB->getOutputSection())
129 int from = getOrCreateNode(fromSB);
130 int to = getOrCreateNode(toSB);
132 clusters[to].weight += weight;
137 // Remember the best edge.
138 Cluster &toC = clusters[to];
139 if (toC.bestPred.from == -1 || toC.bestPred.weight < weight) {
140 toC.bestPred.from = from;
141 toC.bestPred.weight = weight;
144 for (Cluster &c : clusters)
145 c.initialWeight = c.weight;
148 // It's bad to merge clusters which would degrade the density too much.
149 static bool isNewDensityBad(Cluster &a, Cluster &b) {
150 double newDensity = double(a.weight + b.weight) / double(a.size + b.size);
151 return newDensity < a.getDensity() / MAX_DENSITY_DEGRADATION;
154 static void mergeClusters(Cluster &into, Cluster &from) {
155 into.sections.insert(into.sections.end(), from.sections.begin(),
156 from.sections.end());
157 into.size += from.size;
158 into.weight += from.weight;
159 from.sections.clear();
164 // Group InputSections into clusters using the Call-Chain Clustering heuristic
165 // then sort the clusters by density.
166 void CallGraphSort::groupClusters() {
167 std::vector<int> sortedSecs(clusters.size());
168 std::vector<Cluster *> secToCluster(clusters.size());
170 for (size_t i = 0; i < clusters.size(); ++i) {
172 secToCluster[i] = &clusters[i];
175 llvm::stable_sort(sortedSecs, [&](int a, int b) {
176 return clusters[a].getDensity() > clusters[b].getDensity();
179 for (int si : sortedSecs) {
180 // clusters[si] is the same as secToClusters[si] here because it has not
181 // been merged into another cluster yet.
182 Cluster &c = clusters[si];
184 // Don't consider merging if the edge is unlikely.
185 if (c.bestPred.from == -1 || c.bestPred.weight * 10 <= c.initialWeight)
188 Cluster *predC = secToCluster[c.bestPred.from];
192 if (c.size + predC->size > MAX_CLUSTER_SIZE)
195 if (isNewDensityBad(*predC, c))
198 // NOTE: Consider using a disjoint-set to track section -> cluster mapping
199 // if this is ever slow.
200 for (int si : c.sections)
201 secToCluster[si] = predC;
203 mergeClusters(*predC, c);
206 // Remove empty or dead nodes. Invalidates all cluster indices.
207 llvm::erase_if(clusters, [](const Cluster &c) {
208 return c.size == 0 || c.sections.empty();
212 llvm::stable_sort(clusters, [](const Cluster &a, const Cluster &b) {
213 return a.getDensity() > b.getDensity();
217 DenseMap<const InputSectionBase *, int> CallGraphSort::run() {
221 DenseMap<const InputSectionBase *, int> orderMap;
222 ssize_t curOrder = 1;
224 for (const Cluster &c : clusters)
225 for (int secIndex : c.sections)
226 orderMap[sections[secIndex]] = curOrder++;
228 if (!config->printSymbolOrder.empty()) {
230 raw_fd_ostream os(config->printSymbolOrder, ec, sys::fs::F_None);
232 error("cannot open " + config->printSymbolOrder + ": " + ec.message());
236 // Print the symbols ordered by C3, in the order of increasing curOrder
237 // Instead of sorting all the orderMap, just repeat the loops above.
238 for (const Cluster &c : clusters)
239 for (int secIndex : c.sections)
240 // Search all the symbols in the file of the section
241 // and find out a Defined symbol with name that is within the section.
242 for (Symbol *sym: sections[secIndex]->file->getSymbols())
243 if (!sym->isSection()) // Filter out section-type symbols here.
244 if (auto *d = dyn_cast<Defined>(sym))
245 if (sections[secIndex] == d->section)
246 os << sym->getName() << "\n";
252 // Sort sections by the profile data provided by -callgraph-profile-file
254 // This first builds a call graph based on the profile data then merges sections
255 // according to the C³ huristic. All clusters are then sorted by a density
256 // metric to further improve locality.
257 DenseMap<const InputSectionBase *, int> elf::computeCallGraphProfileOrder() {
258 return CallGraphSort().run();