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 "OutputSegment.h"
12#include "Relocations.h"
13#include "Symbols.h"
14#include "Target.h"
15#include "lld/Common/BPSectionOrdererBase.inc"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/StableHashing.h"
19#include "llvm/Support/Endian.h"
20#include "llvm/Support/xxhash.h"
21
22#define DEBUG_TYPE "bp-section-orderer"
23
24using namespace llvm;
25using namespace lld::macho;
26
27namespace {
28struct BPOrdererMachO;
29}
30template <> struct lld::BPOrdererTraits<struct BPOrdererMachO> {
31 using Section = macho::InputSection;
32 using Defined = macho::Defined;
33};
34namespace {
35struct BPOrdererMachO : lld::BPOrderer<BPOrdererMachO> {
36 static uint64_t getSize(const Section &sec) { return sec.getSize(); }
37 static bool isCodeSection(const Section &sec) {
38 return macho::isCodeSection(&sec);
39 }
40 static std::string getSectionName(const Section &sec) {
41 return (sec.getSegName() + sec.getName()).str();
42 }
43 static std::string getCompressionSubgroupKey(const Section &sec) {
44 return sec.isCold ? ":cold" : "";
45 }
46 static ArrayRef<Defined *> getSymbols(const Section &sec) {
47 return sec.symbols;
48 }
49
50 // Linkage names can be prefixed with "_" or "l_" on Mach-O. See
51 // Mangler::getNameWithPrefix() for details.
52 std::optional<StringRef> static getResolvedLinkageName(llvm::StringRef name) {
53 if (name.consume_front(Prefix: "_") || name.consume_front(Prefix: "l_"))
54 return name;
55 return {};
56 }
57
58 static void
59 getSectionHashes(const Section &sec, llvm::SmallVectorImpl<uint64_t> &hashes,
60 const llvm::DenseMap<const void *, uint64_t> &sectionToIdx) {
61 constexpr unsigned windowSize = 4;
62
63 // Calculate content hashes: k-mers and the last k-1 bytes.
64 ArrayRef<uint8_t> data = sec.data;
65 if (data.size() >= windowSize)
66 for (size_t i = 0; i <= data.size() - windowSize; ++i)
67 hashes.push_back(Elt: llvm::support::endian::read32le(P: data.data() + i));
68 for (uint8_t byte : data.take_back(N: windowSize - 1))
69 hashes.push_back(Elt: byte);
70
71 // Calculate relocation hashes
72 for (const auto &r : sec.relocs) {
73 uint32_t relocLength = 1 << r.length;
74 if (r.referent.isNull() || r.offset + relocLength > data.size())
75 continue;
76
77 uint64_t relocHash = getRelocHash(reloc: r, sectionToIdx);
78 uint32_t start = (r.offset < windowSize) ? 0 : r.offset - windowSize + 1;
79 for (uint32_t i = start; i < r.offset + relocLength; i++) {
80 auto window = data.drop_front(N: i).take_front(N: windowSize);
81 hashes.push_back(Elt: xxh3_64bits(data: window) ^ relocHash);
82 }
83 }
84
85 llvm::sort(C&: hashes);
86 hashes.erase(CS: llvm::unique(R&: hashes), CE: hashes.end());
87 }
88
89 static llvm::StringRef getSymName(const Defined &sym) {
90 return sym.getName();
91 }
92 static uint64_t getSymValue(const Defined &sym) { return sym.value; }
93 static uint64_t getSymSize(const Defined &sym) { return sym.size; }
94
95private:
96 static uint64_t
97 getRelocHash(const Relocation &reloc,
98 const llvm::DenseMap<const void *, uint64_t> &sectionToIdx) {
99 auto *isec = reloc.getReferentInputSection();
100 std::optional<uint64_t> sectionIdx;
101 if (auto it = sectionToIdx.find(Val: isec); it != sectionToIdx.end())
102 sectionIdx = it->second;
103 uint64_t kind = -1, value = 0;
104 if (isec)
105 kind = uint64_t(isec->kind());
106
107 if (auto *sym = reloc.referent.dyn_cast<Symbol *>()) {
108 kind = (kind << 8) | uint8_t(sym->kind());
109 if (auto *d = llvm::dyn_cast<Defined>(Val: sym))
110 value = d->value;
111 }
112 return llvm::stable_hash_combine(A: kind, B: sectionIdx.value_or(u: 0), C: value,
113 D: reloc.addend);
114 }
115};
116} // namespace
117
118DenseMap<const InputSection *, int> lld::macho::runBalancedPartitioning(
119 StringRef profilePath, ArrayRef<BPCompressionSortSpec> compressionSortSpecs,
120 bool forFunctionCompression, bool forDataCompression,
121 bool compressionSortStartupFunctions, bool verbose) {
122 // Collect candidate sections and associated symbols.
123 SmallVector<InputSection *> sections;
124 DenseMap<const InputSection *, unsigned> sectionToIdx;
125 DenseMap<CachedHashStringRef, std::set<unsigned>> rootSymbolToSectionIdxs;
126 auto addSection = [&](InputSection *isec) {
127 if (!isec || isec->data.empty() || !isec->data.data())
128 return;
129 // CString section order is handled by
130 // {Deduplicated}CStringSection::finalizeContents()
131 if (isa<CStringInputSection>(Val: isec) || isec->isFinal)
132 return;
133 // ConcatInputSections are entirely live or dead, so the offset is
134 // irrelevant.
135 if (isa<ConcatInputSection>(Val: isec) && !isec->isLive(off: 0))
136 return;
137 unsigned idx = sections.size();
138 if (!sectionToIdx.try_emplace(Key: isec, Args&: idx).second)
139 return;
140 sections.emplace_back(Args&: isec);
141 for (auto *sym : isec->symbols) {
142 auto rootName = lld::utils::getRootSymbol(Name: sym->getName());
143 rootSymbolToSectionIdxs[CachedHashStringRef(rootName)].insert(x: idx);
144 if (auto linkageName = BPOrdererMachO::getResolvedLinkageName(name: rootName))
145 rootSymbolToSectionIdxs[CachedHashStringRef(*linkageName)].insert(x: idx);
146 }
147 };
148 for (const auto *file : inputFiles) {
149 for (auto *sec : file->sections) {
150 if (sec->name == section_names::ehFrame &&
151 sec->segname == segment_names::text)
152 continue;
153 for (auto &subsec : sec->subsections) {
154 addSection(subsec.isec);
155 if (subsec.isec && subsec.isec->canonical() != subsec.isec)
156 addSection(subsec.isec->canonical());
157 }
158 }
159 }
160
161 // A temporal profile naming an ICF thunk describes execution of both the
162 // thunk and the shared body it branches to. Add the body to each name that
163 // resolves to a thunk.
164 for (auto &[symbol, sectionIdxs] : rootSymbolToSectionIdxs) {
165 for (unsigned idx : sectionIdxs) {
166 InputSection *isec = sections[idx];
167 if (!llvm::any_of(Range&: isec->symbols, P: [](Defined *sym) {
168 return sym->identicalCodeFoldingKind == Symbol::ICFFoldKind::Thunk;
169 }))
170 continue;
171 auto *bodySym = cast<Defined>(Val: target->getThunkBranchTarget(thunk: isec));
172 auto bodyIdx = sectionToIdx.find(Val: bodySym->isec());
173 if (bodyIdx != sectionToIdx.end())
174 sectionIdxs.insert(x: bodyIdx->second);
175 }
176 }
177
178 auto result = BPOrdererMachO().computeOrder(
179 profilePath, compressionSortSpecs, forFunctionCompression,
180 forDataCompression, compressionSortStartupFunctions, verbose, sections,
181 rootSymbolToSectionIdxs);
182 // BP already orders cold sections after non-cold via separate buckets.
183 // Unset isCold on sections that received a BP priority so Writer.cpp's
184 // stable_partition doesn't re-partition them. Sections without a BP priority
185 // (e.g. non-startup cold sections when only --bp-startup-sort is used) keep
186 // their isCold flag for Writer.cpp to handle.
187 for (auto *isec : sections)
188 if (result.contains(Val: isec))
189 isec->isCold = false;
190 return result;
191}
192