|
150
|
1 //===- CallGraphSort.cpp --------------------------------------------------===//
|
|
|
2 //
|
|
|
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
|
|
|
6 //
|
|
|
7 //===----------------------------------------------------------------------===//
|
|
|
8 ///
|
|
|
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
|
|
|
12 ///
|
|
|
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.
|
|
|
16 ///
|
|
|
17 /// Definitions:
|
|
|
18 /// * Cluster
|
|
|
19 /// * An ordered list of input sections which are laid 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 incoming
|
|
|
22 /// edges.
|
|
|
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.
|
|
|
27 /// * Density
|
|
|
28 /// * The weight of the cluster divided by the size of the cluster. This is a
|
|
|
29 /// proxy for the amount of execution time spent per byte of the cluster.
|
|
|
30 ///
|
|
|
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
|
|
|
37 /// a density.
|
|
|
38 /// * If not, then combine the clusters.
|
|
|
39 /// * Sort non-empty clusters by density
|
|
|
40 ///
|
|
|
41 //===----------------------------------------------------------------------===//
|
|
|
42
|
|
|
43 #include "CallGraphSort.h"
|
|
|
44 #include "OutputSections.h"
|
|
|
45 #include "SymbolTable.h"
|
|
|
46 #include "Symbols.h"
|
|
|
47
|
|
|
48 #include <numeric>
|
|
|
49
|
|
|
50 using namespace llvm;
|
|
173
|
51 using namespace lld;
|
|
|
52 using namespace lld::elf;
|
|
150
|
53
|
|
|
54 namespace {
|
|
|
55 struct Edge {
|
|
|
56 int from;
|
|
|
57 uint64_t weight;
|
|
|
58 };
|
|
|
59
|
|
|
60 struct Cluster {
|
|
|
61 Cluster(int sec, size_t s) : next(sec), prev(sec), size(s) {}
|
|
|
62
|
|
|
63 double getDensity() const {
|
|
|
64 if (size == 0)
|
|
|
65 return 0;
|
|
|
66 return double(weight) / double(size);
|
|
|
67 }
|
|
|
68
|
|
|
69 int next;
|
|
|
70 int prev;
|
|
|
71 size_t size = 0;
|
|
|
72 uint64_t weight = 0;
|
|
|
73 uint64_t initialWeight = 0;
|
|
|
74 Edge bestPred = {-1, 0};
|
|
|
75 };
|
|
|
76
|
|
|
77 class CallGraphSort {
|
|
|
78 public:
|
|
|
79 CallGraphSort();
|
|
|
80
|
|
|
81 DenseMap<const InputSectionBase *, int> run();
|
|
|
82
|
|
|
83 private:
|
|
|
84 std::vector<Cluster> clusters;
|
|
|
85 std::vector<const InputSectionBase *> sections;
|
|
|
86 };
|
|
|
87
|
|
|
88 // Maximum amount the combined cluster density can be worse than the original
|
|
|
89 // cluster to consider merging.
|
|
|
90 constexpr int MAX_DENSITY_DEGRADATION = 8;
|
|
|
91
|
|
|
92 // Maximum cluster size in bytes.
|
|
|
93 constexpr uint64_t MAX_CLUSTER_SIZE = 1024 * 1024;
|
|
|
94 } // end anonymous namespace
|
|
|
95
|
|
|
96 using SectionPair =
|
|
|
97 std::pair<const InputSectionBase *, const InputSectionBase *>;
|
|
|
98
|
|
|
99 // Take the edge list in Config->CallGraphProfile, resolve symbol names to
|
|
|
100 // Symbols, and generate a graph between InputSections with the provided
|
|
|
101 // weights.
|
|
|
102 CallGraphSort::CallGraphSort() {
|
|
|
103 MapVector<SectionPair, uint64_t> &profile = config->callGraphProfile;
|
|
|
104 DenseMap<const InputSectionBase *, int> secToCluster;
|
|
|
105
|
|
|
106 auto getOrCreateNode = [&](const InputSectionBase *isec) -> int {
|
|
|
107 auto res = secToCluster.try_emplace(isec, clusters.size());
|
|
|
108 if (res.second) {
|
|
|
109 sections.push_back(isec);
|
|
|
110 clusters.emplace_back(clusters.size(), isec->getSize());
|
|
|
111 }
|
|
|
112 return res.first->second;
|
|
|
113 };
|
|
|
114
|
|
|
115 // Create the graph.
|
|
|
116 for (std::pair<SectionPair, uint64_t> &c : profile) {
|
|
|
117 const auto *fromSB = cast<InputSectionBase>(c.first.first->repl);
|
|
|
118 const auto *toSB = cast<InputSectionBase>(c.first.second->repl);
|
|
|
119 uint64_t weight = c.second;
|
|
|
120
|
|
|
121 // Ignore edges between input sections belonging to different output
|
|
|
122 // sections. This is done because otherwise we would end up with clusters
|
|
|
123 // containing input sections that can't actually be placed adjacently in the
|
|
|
124 // output. This messes with the cluster size and density calculations. We
|
|
|
125 // would also end up moving input sections in other output sections without
|
|
|
126 // moving them closer to what calls them.
|
|
|
127 if (fromSB->getOutputSection() != toSB->getOutputSection())
|
|
|
128 continue;
|
|
|
129
|
|
|
130 int from = getOrCreateNode(fromSB);
|
|
|
131 int to = getOrCreateNode(toSB);
|
|
|
132
|
|
|
133 clusters[to].weight += weight;
|
|
|
134
|
|
|
135 if (from == to)
|
|
|
136 continue;
|
|
|
137
|
|
|
138 // Remember the best edge.
|
|
|
139 Cluster &toC = clusters[to];
|
|
|
140 if (toC.bestPred.from == -1 || toC.bestPred.weight < weight) {
|
|
|
141 toC.bestPred.from = from;
|
|
|
142 toC.bestPred.weight = weight;
|
|
|
143 }
|
|
|
144 }
|
|
|
145 for (Cluster &c : clusters)
|
|
|
146 c.initialWeight = c.weight;
|
|
|
147 }
|
|
|
148
|
|
|
149 // It's bad to merge clusters which would degrade the density too much.
|
|
|
150 static bool isNewDensityBad(Cluster &a, Cluster &b) {
|
|
|
151 double newDensity = double(a.weight + b.weight) / double(a.size + b.size);
|
|
|
152 return newDensity < a.getDensity() / MAX_DENSITY_DEGRADATION;
|
|
|
153 }
|
|
|
154
|
|
|
155 // Find the leader of V's belonged cluster (represented as an equivalence
|
|
|
156 // class). We apply union-find path-halving technique (simple to implement) in
|
|
|
157 // the meantime as it decreases depths and the time complexity.
|
|
|
158 static int getLeader(std::vector<int> &leaders, int v) {
|
|
|
159 while (leaders[v] != v) {
|
|
|
160 leaders[v] = leaders[leaders[v]];
|
|
|
161 v = leaders[v];
|
|
|
162 }
|
|
|
163 return v;
|
|
|
164 }
|
|
|
165
|
|
|
166 static void mergeClusters(std::vector<Cluster> &cs, Cluster &into, int intoIdx,
|
|
|
167 Cluster &from, int fromIdx) {
|
|
|
168 int tail1 = into.prev, tail2 = from.prev;
|
|
|
169 into.prev = tail2;
|
|
|
170 cs[tail2].next = intoIdx;
|
|
|
171 from.prev = tail1;
|
|
|
172 cs[tail1].next = fromIdx;
|
|
|
173 into.size += from.size;
|
|
|
174 into.weight += from.weight;
|
|
|
175 from.size = 0;
|
|
|
176 from.weight = 0;
|
|
|
177 }
|
|
|
178
|
|
|
179 // Group InputSections into clusters using the Call-Chain Clustering heuristic
|
|
|
180 // then sort the clusters by density.
|
|
|
181 DenseMap<const InputSectionBase *, int> CallGraphSort::run() {
|
|
|
182 std::vector<int> sorted(clusters.size());
|
|
|
183 std::vector<int> leaders(clusters.size());
|
|
|
184
|
|
|
185 std::iota(leaders.begin(), leaders.end(), 0);
|
|
|
186 std::iota(sorted.begin(), sorted.end(), 0);
|
|
|
187 llvm::stable_sort(sorted, [&](int a, int b) {
|
|
|
188 return clusters[a].getDensity() > clusters[b].getDensity();
|
|
|
189 });
|
|
|
190
|
|
|
191 for (int l : sorted) {
|
|
|
192 // The cluster index is the same as the index of its leader here because
|
|
|
193 // clusters[L] has not been merged into another cluster yet.
|
|
|
194 Cluster &c = clusters[l];
|
|
|
195
|
|
|
196 // Don't consider merging if the edge is unlikely.
|
|
|
197 if (c.bestPred.from == -1 || c.bestPred.weight * 10 <= c.initialWeight)
|
|
|
198 continue;
|
|
|
199
|
|
|
200 int predL = getLeader(leaders, c.bestPred.from);
|
|
|
201 if (l == predL)
|
|
|
202 continue;
|
|
|
203
|
|
|
204 Cluster *predC = &clusters[predL];
|
|
|
205 if (c.size + predC->size > MAX_CLUSTER_SIZE)
|
|
|
206 continue;
|
|
|
207
|
|
|
208 if (isNewDensityBad(*predC, c))
|
|
|
209 continue;
|
|
|
210
|
|
|
211 leaders[l] = predL;
|
|
|
212 mergeClusters(clusters, *predC, predL, c, l);
|
|
|
213 }
|
|
|
214
|
|
|
215 // Sort remaining non-empty clusters by density.
|
|
|
216 sorted.clear();
|
|
|
217 for (int i = 0, e = (int)clusters.size(); i != e; ++i)
|
|
|
218 if (clusters[i].size > 0)
|
|
|
219 sorted.push_back(i);
|
|
|
220 llvm::stable_sort(sorted, [&](int a, int b) {
|
|
|
221 return clusters[a].getDensity() > clusters[b].getDensity();
|
|
|
222 });
|
|
|
223
|
|
|
224 DenseMap<const InputSectionBase *, int> orderMap;
|
|
|
225 int curOrder = 1;
|
|
|
226 for (int leader : sorted)
|
|
|
227 for (int i = leader;;) {
|
|
|
228 orderMap[sections[i]] = curOrder++;
|
|
|
229 i = clusters[i].next;
|
|
|
230 if (i == leader)
|
|
|
231 break;
|
|
|
232 }
|
|
|
233
|
|
|
234 if (!config->printSymbolOrder.empty()) {
|
|
|
235 std::error_code ec;
|
|
|
236 raw_fd_ostream os(config->printSymbolOrder, ec, sys::fs::OF_None);
|
|
|
237 if (ec) {
|
|
|
238 error("cannot open " + config->printSymbolOrder + ": " + ec.message());
|
|
|
239 return orderMap;
|
|
|
240 }
|
|
|
241
|
|
|
242 // Print the symbols ordered by C3, in the order of increasing curOrder
|
|
|
243 // Instead of sorting all the orderMap, just repeat the loops above.
|
|
|
244 for (int leader : sorted)
|
|
|
245 for (int i = leader;;) {
|
|
|
246 // Search all the symbols in the file of the section
|
|
|
247 // and find out a Defined symbol with name that is within the section.
|
|
|
248 for (Symbol *sym : sections[i]->file->getSymbols())
|
|
|
249 if (!sym->isSection()) // Filter out section-type symbols here.
|
|
|
250 if (auto *d = dyn_cast<Defined>(sym))
|
|
|
251 if (sections[i] == d->section)
|
|
|
252 os << sym->getName() << "\n";
|
|
|
253 i = clusters[i].next;
|
|
|
254 if (i == leader)
|
|
|
255 break;
|
|
|
256 }
|
|
|
257 }
|
|
|
258
|
|
|
259 return orderMap;
|
|
|
260 }
|
|
|
261
|
|
|
262 // Sort sections by the profile data provided by -callgraph-profile-file
|
|
|
263 //
|
|
|
264 // This first builds a call graph based on the profile data then merges sections
|
|
173
|
265 // according to the C³ heuristic. All clusters are then sorted by a density
|
|
150
|
266 // metric to further improve locality.
|
|
173
|
267 DenseMap<const InputSectionBase *, int> elf::computeCallGraphProfileOrder() {
|
|
150
|
268 return CallGraphSort().run();
|
|
|
269 }
|
