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