1//===- SectionPriorities.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 "SectionPriorities.h"
15#include "BPSectionOrderer.h"
16#include "Config.h"
17#include "InputFiles.h"
18#include "Symbols.h"
19#include "Target.h"
20
21#include "lld/Common/Args.h"
22#include "lld/Common/CommonLinkerContext.h"
23#include "lld/Common/ErrorHandler.h"
24#include "lld/Common/Utils.h"
25#include "llvm/ADT/DenseMap.h"
26#include "llvm/ADT/MapVector.h"
27#include "llvm/Support/Parallel.h"
28#include "llvm/Support/Path.h"
29#include "llvm/Support/TimeProfiler.h"
30#include "llvm/Support/raw_ostream.h"
31#include "llvm/Support/xxhash.h"
32
33#include <numeric>
34
35using namespace llvm;
36using namespace llvm::MachO;
37using namespace llvm::sys;
38using namespace lld;
39using namespace lld::macho;
40
41PriorityBuilder macho::priorityBuilder;
42
43namespace {
44struct Edge {
45 int from;
46 uint64_t weight;
47};
48
49struct Cluster {
50 Cluster(int sec, size_t s) : next(sec), prev(sec), size(s) {}
51
52 double getDensity() const {
53 if (size == 0)
54 return 0;
55 return double(weight) / double(size);
56 }
57
58 int next;
59 int prev;
60 uint64_t size;
61 uint64_t weight = 0;
62 uint64_t initialWeight = 0;
63 Edge bestPred = {.from: -1, .weight: 0};
64};
65
66class CallGraphSort {
67public:
68 CallGraphSort(const MapVector<SectionPair, uint64_t> &profile);
69
70 DenseMap<const InputSection *, int> run();
71
72private:
73 std::vector<Cluster> clusters;
74 std::vector<const InputSection *> sections;
75};
76// Maximum amount the combined cluster density can be worse than the original
77// cluster to consider merging.
78constexpr int MAX_DENSITY_DEGRADATION = 8;
79} // end anonymous namespace
80
81// Take the edge list in callGraphProfile, resolve symbol names to Symbols, and
82// generate a graph between InputSections with the provided weights.
83CallGraphSort::CallGraphSort(const MapVector<SectionPair, uint64_t> &profile) {
84 DenseMap<const InputSection *, int> secToCluster;
85
86 auto getOrCreateCluster = [&](const InputSection *isec) -> int {
87 auto res = secToCluster.try_emplace(Key: isec, Args: clusters.size());
88 if (res.second) {
89 sections.push_back(x: isec);
90 clusters.emplace_back(args: clusters.size(), args: isec->getSize());
91 }
92 return res.first->second;
93 };
94
95 // Create the graph
96 for (const std::pair<SectionPair, uint64_t> &c : profile) {
97 const auto fromSec = c.first.first->canonical();
98 const auto toSec = c.first.second->canonical();
99 uint64_t weight = c.second;
100 // Ignore edges between input sections belonging to different output
101 // sections. This is done because otherwise we would end up with clusters
102 // containing input sections that can't actually be placed adjacently in the
103 // output. This messes with the cluster size and density calculations. We
104 // would also end up moving input sections in other output sections without
105 // moving them closer to what calls them.
106 if (fromSec->parent != toSec->parent)
107 continue;
108
109 int from = getOrCreateCluster(fromSec);
110 int to = getOrCreateCluster(toSec);
111
112 clusters[to].weight += weight;
113
114 if (from == to)
115 continue;
116
117 // Remember the best edge.
118 Cluster &toC = clusters[to];
119 if (toC.bestPred.from == -1 || toC.bestPred.weight < weight) {
120 toC.bestPred.from = from;
121 toC.bestPred.weight = weight;
122 }
123 }
124 for (Cluster &c : clusters)
125 c.initialWeight = c.weight;
126}
127
128// It's bad to merge clusters which would degrade the density too much.
129static bool isNewDensityBad(Cluster &a, Cluster &b) {
130 double newDensity = double(a.weight + b.weight) / double(a.size + b.size);
131 return newDensity < a.getDensity() / MAX_DENSITY_DEGRADATION;
132}
133
134// Find the leader of V's belonged cluster (represented as an equivalence
135// class). We apply union-find path-halving technique (simple to implement) in
136// the meantime as it decreases depths and the time complexity.
137static int getLeader(std::vector<int> &leaders, int v) {
138 while (leaders[v] != v) {
139 leaders[v] = leaders[leaders[v]];
140 v = leaders[v];
141 }
142 return v;
143}
144
145static void mergeClusters(std::vector<Cluster> &cs, Cluster &into, int intoIdx,
146 Cluster &from, int fromIdx) {
147 int tail1 = into.prev, tail2 = from.prev;
148 into.prev = tail2;
149 cs[tail2].next = intoIdx;
150 from.prev = tail1;
151 cs[tail1].next = fromIdx;
152 into.size += from.size;
153 into.weight += from.weight;
154 from.size = 0;
155 from.weight = 0;
156}
157
158// Group InputSections into clusters using the Call-Chain Clustering heuristic
159// then sort the clusters by density.
160DenseMap<const InputSection *, int> CallGraphSort::run() {
161 const uint64_t maxClusterSize = target->getPageSize();
162
163 // Cluster indices sorted by density.
164 std::vector<int> sorted(clusters.size());
165 // For union-find.
166 std::vector<int> leaders(clusters.size());
167
168 std::iota(first: leaders.begin(), last: leaders.end(), value: 0);
169 std::iota(first: sorted.begin(), last: sorted.end(), value: 0);
170
171 llvm::stable_sort(Range&: sorted, C: [&](int a, int b) {
172 return clusters[a].getDensity() > clusters[b].getDensity();
173 });
174
175 for (int l : sorted) {
176 // The cluster index is the same as the index of its leader here because
177 // clusters[L] has not been merged into another cluster yet.
178 Cluster &c = clusters[l];
179
180 // Don't consider merging if the edge is unlikely.
181 if (c.bestPred.from == -1 || c.bestPred.weight * 10 <= c.initialWeight)
182 continue;
183
184 int predL = getLeader(leaders, v: c.bestPred.from);
185 // Already in the same cluster.
186 if (l == predL)
187 continue;
188
189 Cluster *predC = &clusters[predL];
190 if (c.size + predC->size > maxClusterSize)
191 continue;
192
193 if (isNewDensityBad(a&: *predC, b&: c))
194 continue;
195
196 leaders[l] = predL;
197 mergeClusters(cs&: clusters, into&: *predC, intoIdx: predL, from&: c, fromIdx: l);
198 }
199 // Sort remaining non-empty clusters by density.
200 sorted.clear();
201 for (int i = 0, e = (int)clusters.size(); i != e; ++i)
202 if (clusters[i].size > 0)
203 sorted.push_back(x: i);
204 llvm::stable_sort(Range&: sorted, C: [&](int a, int b) {
205 return clusters[a].getDensity() > clusters[b].getDensity();
206 });
207
208 DenseMap<const InputSection *, int> orderMap;
209
210 // Sections will be sorted by decreasing order. Absent sections will have
211 // priority 0 and be placed at the end of sections.
212 int curOrder = -clusters.size();
213 for (int leader : sorted) {
214 for (int i = leader;;) {
215 orderMap[sections[i]] = curOrder++;
216 i = clusters[i].next;
217 if (i == leader)
218 break;
219 }
220 }
221 if (!config->printSymbolOrder.empty()) {
222 std::error_code ec;
223 raw_fd_ostream os(config->printSymbolOrder, ec, sys::fs::OF_None);
224 if (ec) {
225 error(msg: "cannot open " + config->printSymbolOrder + ": " + ec.message());
226 return orderMap;
227 }
228 // Print the symbols ordered by C3, in the order of decreasing curOrder
229 // Instead of sorting all the orderMap, just repeat the loops above.
230 for (int leader : sorted)
231 for (int i = leader;;) {
232 const InputSection *isec = sections[i];
233 // Search all the symbols in the file of the section
234 // and find out a Defined symbol with name that is within the
235 // section.
236 for (Symbol *sym : isec->getFile()->symbols) {
237 if (auto *d = dyn_cast_or_null<Defined>(Val: sym)) {
238 if (d->isec() == isec)
239 os << sym->getName() << "\n";
240 }
241 }
242 i = clusters[i].next;
243 if (i == leader)
244 break;
245 }
246 }
247
248 return orderMap;
249}
250
251void macho::PriorityBuilder::SymbolPriorityEntry::setPriority(
252 int priority, StringRef objectFile) {
253 if (!objectFile.empty())
254 objectFiles.try_emplace(Key: objectFile, Args&: priority);
255 else
256 anyObjectFile = std::min(a: anyObjectFile, b: priority);
257}
258
259int macho::PriorityBuilder::SymbolPriorityEntry::getPriority(
260 const InputFile *f) const {
261 if (!f || objectFiles.empty())
262 return anyObjectFile;
263 // We don't use toString(InputFile *) here because it returns the full path
264 // for object files, and we only want the basename.
265 StringRef basename = path::filename(path: f->getName());
266 SmallString<128> buf;
267 StringRef filename =
268 f->archiveName.empty()
269 ? basename
270 : (path::filename(path: f->archiveName) + "(" + basename + ")")
271 .toStringRef(Out&: buf);
272 return std::min(a: objectFiles.lookup(Val: filename), b: anyObjectFile);
273}
274
275std::optional<int>
276macho::PriorityBuilder::getCStringPriority(uint32_t hash,
277 const InputFile *f) const {
278 auto it = cStringPriorities.find(Val: hash);
279 if (it == cStringPriorities.end())
280 return std::nullopt;
281 return it->second.getPriority(f);
282}
283
284std::optional<int>
285macho::PriorityBuilder::getSymbolPriority(const Defined *sym) const {
286 if (sym->isAbsolute())
287 return std::nullopt;
288 auto it = priorities.find(Val: utils::getRootSymbol(Name: sym->getName()));
289 if (it == priorities.end())
290 return std::nullopt;
291 return it->second.getPriority(f: sym->isec()->getFile());
292}
293
294void macho::PriorityBuilder::extractCallGraphProfile() {
295 TimeTraceScope timeScope("Extract call graph profile");
296 bool hasOrderFile = !priorities.empty();
297 for (const InputFile *file : inputFiles) {
298 auto *obj = dyn_cast_or_null<ObjFile>(Val: file);
299 if (!obj)
300 continue;
301 for (const CallGraphEntry &entry : obj->callGraph) {
302 assert(entry.fromIndex < obj->symbols.size() &&
303 entry.toIndex < obj->symbols.size());
304 auto *fromSym = dyn_cast_or_null<Defined>(Val: obj->symbols[entry.fromIndex]);
305 auto *toSym = dyn_cast_or_null<Defined>(Val: obj->symbols[entry.toIndex]);
306 if (fromSym && toSym &&
307 (!hasOrderFile ||
308 (!getSymbolPriority(sym: fromSym) && !getSymbolPriority(sym: toSym))))
309 callGraphProfile[{fromSym->isec(), toSym->isec()}] += entry.count;
310 }
311 }
312}
313
314void macho::PriorityBuilder::parseOrderFile(StringRef path) {
315 assert(callGraphProfile.empty() &&
316 "Order file must be parsed before call graph profile is processed");
317 std::optional<MemoryBufferRef> buffer = readFile(path);
318 if (!buffer) {
319 error(msg: "Could not read order file at " + path);
320 return;
321 }
322
323 int prio = std::numeric_limits<int>::min();
324 MemoryBufferRef mbref = *buffer;
325 for (StringRef line : args::getLines(mb: mbref)) {
326 StringRef objectFile;
327 line = line.take_until(F: [](char c) { return c == '#'; }); // ignore comments
328 line = line.ltrim();
329
330 CPUType cpuType = StringSwitch<CPUType>(line)
331 .StartsWith(S: "i386:", Value: CPU_TYPE_I386)
332 .StartsWith(S: "x86_64:", Value: CPU_TYPE_X86_64)
333 .StartsWith(S: "arm:", Value: CPU_TYPE_ARM)
334 .StartsWith(S: "arm64:", Value: CPU_TYPE_ARM64)
335 .StartsWith(S: "ppc:", Value: CPU_TYPE_POWERPC)
336 .StartsWith(S: "ppc64:", Value: CPU_TYPE_POWERPC64)
337 .Default(Value: CPU_TYPE_ANY);
338
339 if (cpuType != CPU_TYPE_ANY && cpuType != target->cpuType)
340 continue;
341 // Drop the CPU type as well as the colon
342 if (cpuType != CPU_TYPE_ANY)
343 line = line.drop_until(F: [](char c) { return c == ':'; }).drop_front();
344
345 constexpr std::array<StringRef, 2> fileEnds = {".o:", ".o):"};
346 for (StringRef fileEnd : fileEnds) {
347 size_t pos = line.find(Str: fileEnd);
348 if (pos != StringRef::npos) {
349 // Split the string around the colon
350 objectFile = line.take_front(N: pos + fileEnd.size() - 1);
351 line = line.drop_front(N: pos + fileEnd.size());
352 break;
353 }
354 }
355
356 // The rest of the line is either <symbol name> or
357 // cStringEntryPrefix<cstring hash>
358 line = line.trim();
359 if (line.consume_front(Prefix: cStringEntryPrefix)) {
360 uint32_t hash = 0;
361 // Only accept hex (0x prefix) or decimal format
362 if (line.consume_front_insensitive(Prefix: "0x") ? !line.getAsInteger(Radix: 16, Result&: hash)
363 : !line.getAsInteger(Radix: 10, Result&: hash))
364 cStringPriorities[hash].setPriority(priority: prio, objectFile);
365 } else {
366 StringRef symbol = utils::getRootSymbol(Name: line);
367 if (!symbol.empty())
368 priorities[symbol].setPriority(priority: prio, objectFile);
369 }
370
371 ++prio;
372 }
373}
374
375DenseMap<const InputSection *, int>
376macho::PriorityBuilder::buildInputSectionPriorities() {
377 DenseMap<const InputSection *, int> sectionPriorities;
378 if (config->bpStartupFunctionSort || config->bpFunctionOrderForCompression ||
379 config->bpDataOrderForCompression ||
380 !config->bpCompressionSortSpecs.empty()) {
381 TimeTraceScope timeScope("Balanced Partitioning Section Orderer");
382 sectionPriorities = runBalancedPartitioning(
383 profilePath: config->bpStartupFunctionSort ? config->irpgoProfilePath : "",
384 compressionSortSpecs: config->bpCompressionSortSpecs, forFunctionCompression: config->bpFunctionOrderForCompression,
385 forDataCompression: config->bpDataOrderForCompression,
386 compressionSortStartupFunctions: config->bpCompressionSortStartupFunctions,
387 verbose: config->bpVerboseSectionOrderer);
388 } else if (config->callGraphProfileSort) {
389 // Sort sections by the profile data provided by __LLVM,__cg_profile
390 // sections.
391 //
392 // This first builds a call graph based on the profile data then merges
393 // sections according to the C³ heuristic. All clusters are then sorted by a
394 // density metric to further improve locality.
395 TimeTraceScope timeScope("Call graph profile sort");
396 sectionPriorities = CallGraphSort(callGraphProfile).run();
397 }
398
399 if (priorities.empty())
400 return sectionPriorities;
401
402 // getSymbolPriority() is expensive, and there are many object files and
403 // symbols, so parallelize getSymbolPriority() over object files.
404 using Matches = std::vector<std::pair<InputSection *, int>>;
405 std::vector<std::pair<const ObjFile *, Matches>> fileMatches;
406 for (const InputFile *file : inputFiles)
407 if (auto *obj = dyn_cast<ObjFile>(Val: file))
408 fileMatches.emplace_back(args&: obj, args: Matches());
409
410 parallelForEach(R&: fileMatches, Fn: [&](auto &pair) {
411 auto &[file, matches] = pair;
412 for (Symbol *sym : file->symbols)
413 if (auto *d = dyn_cast_or_null<Defined>(Val: sym))
414 if (std::optional<int> priority = getSymbolPriority(sym: d))
415 matches.emplace_back(d->isec(), *priority);
416 });
417
418 // TODO: Make sure this handles weak symbols correctly.
419 for (const auto &[_, matches] : fileMatches)
420 for (auto [isec, symbolPriority] : matches) {
421 int &priority = sectionPriorities[isec];
422 priority = std::min(a: priority, b: symbolPriority);
423 // Order file takes precedence over cold partitioning.
424 isec->isCold = false;
425 }
426
427 return sectionPriorities;
428}
429
430void macho::PriorityBuilder::forEachStringPiece(
431 ArrayRef<CStringInputSection *> inputs,
432 std::function<void(CStringInputSection &, StringPiece &, size_t)> f,
433 bool forceInputOrder, bool computeHash) const {
434 std::vector<std::tuple<int, CStringInputSection *, size_t>> orderedPieces;
435 std::vector<std::pair<CStringInputSection *, size_t>> unorderedPieces;
436 for (CStringInputSection *isec : inputs) {
437 for (const auto &[stringPieceIdx, piece] : llvm::enumerate(First&: isec->pieces)) {
438 if (!piece.live)
439 continue;
440 // Process pieces in input order if we have no cstrings in our orderfile
441 if (forceInputOrder || cStringPriorities.empty()) {
442 f(*isec, piece, stringPieceIdx);
443 continue;
444 }
445 uint32_t hash =
446 computeHash
447 ? (xxh3_64bits(data: isec->getStringRef(i: stringPieceIdx)) & 0x7fffffff)
448 : piece.hash;
449 if (auto priority = getCStringPriority(hash, f: isec->getFile()))
450 orderedPieces.emplace_back(args&: *priority, args&: isec, args&: stringPieceIdx);
451 else
452 unorderedPieces.emplace_back(args&: isec, args&: stringPieceIdx);
453 }
454 }
455 if (orderedPieces.empty() && unorderedPieces.empty())
456 return;
457 llvm::stable_sort(Range&: orderedPieces, C: [](const auto &left, const auto &right) {
458 return std::get<0>(left) < std::get<0>(right);
459 });
460 for (auto &[priority, isec, pieceIdx] : orderedPieces)
461 f(*isec, isec->pieces[pieceIdx], pieceIdx);
462 // TODO: Add option to order the remaining cstrings for compression
463 for (auto &[isec, pieceIdx] : unorderedPieces)
464 f(*isec, isec->pieces[pieceIdx], pieceIdx);
465}
466