1 //===- BPSectionOrderer.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 #include "BPSectionOrderer.h"
10 #include "InputSection.h"
11 #include "Relocations.h"
12 #include "Symbols.h"
13 #include "lld/Common/BPSectionOrdererBase.inc"
14 #include "llvm/ADT/DenseMap.h"
15 #include "llvm/ADT/StableHashing.h"
16 #include "llvm/Support/Endian.h"
17 #include "llvm/Support/xxhash.h"
18
19 #define DEBUG_TYPE "bp-section-orderer"
20
21 using namespace llvm;
22 using namespace lld::macho;
23
24 namespace {
25 struct BPOrdererMachO;
26 }
27 template <> struct lld::BPOrdererTraits<struct BPOrdererMachO> {
28 using Section = macho::InputSection;
29 using Defined = macho::Defined;
30 };
31 namespace {
32 struct BPOrdererMachO : lld::BPOrderer<BPOrdererMachO> {
getSize__anon7447d87c0211::BPOrdererMachO33 static uint64_t getSize(const Section &sec) { return sec.getSize(); }
isCodeSection__anon7447d87c0211::BPOrdererMachO34 static bool isCodeSection(const Section &sec) {
35 return macho::isCodeSection(&sec);
36 }
getSymbols__anon7447d87c0211::BPOrdererMachO37 static ArrayRef<Defined *> getSymbols(const Section &sec) {
38 return sec.symbols;
39 }
40
41 // Linkage names can be prefixed with "_" or "l_" on Mach-O. See
42 // Mangler::getNameWithPrefix() for details.
getResolvedLinkageName__anon7447d87c0211::BPOrdererMachO43 std::optional<StringRef> static getResolvedLinkageName(llvm::StringRef name) {
44 if (name.consume_front("_") || name.consume_front("l_"))
45 return name;
46 return {};
47 }
48
49 static void
getSectionHashes__anon7447d87c0211::BPOrdererMachO50 getSectionHashes(const Section &sec, llvm::SmallVectorImpl<uint64_t> &hashes,
51 const llvm::DenseMap<const void *, uint64_t> §ionToIdx) {
52 constexpr unsigned windowSize = 4;
53
54 // Calculate content hashes: k-mers and the last k-1 bytes.
55 ArrayRef<uint8_t> data = sec.data;
56 if (data.size() >= windowSize)
57 for (size_t i = 0; i <= data.size() - windowSize; ++i)
58 hashes.push_back(llvm::support::endian::read32le(data.data() + i));
59 for (uint8_t byte : data.take_back(windowSize - 1))
60 hashes.push_back(byte);
61
62 // Calculate relocation hashes
63 for (const auto &r : sec.relocs) {
64 if (r.length == 0 || r.referent.isNull() || r.offset >= data.size())
65 continue;
66
67 uint64_t relocHash = getRelocHash(r, sectionToIdx);
68 uint32_t start = (r.offset < windowSize) ? 0 : r.offset - windowSize + 1;
69 for (uint32_t i = start; i < r.offset + r.length; i++) {
70 auto window = data.drop_front(i).take_front(windowSize);
71 hashes.push_back(xxh3_64bits(window) ^ relocHash);
72 }
73 }
74
75 llvm::sort(hashes);
76 hashes.erase(llvm::unique(hashes), hashes.end());
77 }
78
getSymName__anon7447d87c0211::BPOrdererMachO79 static llvm::StringRef getSymName(const Defined &sym) {
80 return sym.getName();
81 }
getSymValue__anon7447d87c0211::BPOrdererMachO82 static uint64_t getSymValue(const Defined &sym) { return sym.value; }
getSymSize__anon7447d87c0211::BPOrdererMachO83 static uint64_t getSymSize(const Defined &sym) { return sym.size; }
84
85 private:
86 static uint64_t
getRelocHash__anon7447d87c0211::BPOrdererMachO87 getRelocHash(const macho::Reloc &reloc,
88 const llvm::DenseMap<const void *, uint64_t> §ionToIdx) {
89 auto *isec = reloc.getReferentInputSection();
90 std::optional<uint64_t> sectionIdx;
91 if (auto it = sectionToIdx.find(isec); it != sectionToIdx.end())
92 sectionIdx = it->second;
93 uint64_t kind = -1, value = 0;
94 if (isec)
95 kind = uint64_t(isec->kind());
96
97 if (auto *sym = reloc.referent.dyn_cast<Symbol *>()) {
98 kind = (kind << 8) | uint8_t(sym->kind());
99 if (auto *d = llvm::dyn_cast<Defined>(sym))
100 value = d->value;
101 }
102 return llvm::stable_hash_combine(kind, sectionIdx.value_or(0), value,
103 reloc.addend);
104 }
105 };
106 } // namespace
107
runBalancedPartitioning(StringRef profilePath,bool forFunctionCompression,bool forDataCompression,bool compressionSortStartupFunctions,bool verbose)108 DenseMap<const InputSection *, int> lld::macho::runBalancedPartitioning(
109 StringRef profilePath, bool forFunctionCompression, bool forDataCompression,
110 bool compressionSortStartupFunctions, bool verbose) {
111 // Collect candidate sections and associated symbols.
112 SmallVector<InputSection *> sections;
113 DenseMap<CachedHashStringRef, std::set<unsigned>> rootSymbolToSectionIdxs;
114 for (const auto *file : inputFiles) {
115 for (auto *sec : file->sections) {
116 for (auto &subsec : sec->subsections) {
117 auto *isec = subsec.isec;
118 if (!isec || isec->data.empty() || !isec->data.data())
119 continue;
120 // ConcatInputSections are entirely live or dead, so the offset is
121 // irrelevant.
122 if (isa<ConcatInputSection>(isec) && !isec->isLive(0))
123 continue;
124 size_t idx = sections.size();
125 sections.emplace_back(isec);
126 for (auto *sym : BPOrdererMachO::getSymbols(*isec)) {
127 auto rootName = lld::utils::getRootSymbol(sym->getName());
128 rootSymbolToSectionIdxs[CachedHashStringRef(rootName)].insert(idx);
129 if (auto linkageName =
130 BPOrdererMachO::getResolvedLinkageName(rootName))
131 rootSymbolToSectionIdxs[CachedHashStringRef(*linkageName)].insert(
132 idx);
133 }
134 }
135 }
136 }
137
138 return BPOrdererMachO().computeOrder(profilePath, forFunctionCompression,
139 forDataCompression,
140 compressionSortStartupFunctions, verbose,
141 sections, rootSymbolToSectionIdxs);
142 }
143