1//===- ICF.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 "ICF.h"
10#include "ConcatOutputSection.h"
11#include "Config.h"
12#include "InputSection.h"
13#include "SymbolTable.h"
14#include "Symbols.h"
15
16#include "lld/Common/CommonLinkerContext.h"
17#include "llvm/Support/Parallel.h"
18#include "llvm/Support/TimeProfiler.h"
19#include "llvm/Support/xxhash.h"
20
21#include <atomic>
22
23using namespace llvm;
24using namespace lld;
25using namespace lld::macho;
26
27static constexpr bool verboseDiagnostics = false;
28// This counter is used to generate unique thunk names.
29static uint64_t icfThunkCounter = 0;
30
31class ICF {
32public:
33 ICF(std::vector<ConcatInputSection *> &inputs);
34 void run();
35
36 using EqualsFn = bool (ICF::*)(const ConcatInputSection *,
37 const ConcatInputSection *);
38 void segregate(size_t begin, size_t end, EqualsFn);
39 size_t findBoundary(size_t begin, size_t end);
40 void forEachClassRange(size_t begin, size_t end,
41 llvm::function_ref<void(size_t, size_t)> func);
42 void forEachClass(llvm::function_ref<void(size_t, size_t)> func);
43
44 bool equalsConstant(const ConcatInputSection *ia,
45 const ConcatInputSection *ib);
46 bool equalsVariable(const ConcatInputSection *ia,
47 const ConcatInputSection *ib);
48 void applySafeThunksToRange(size_t begin, size_t end);
49
50 // ICF needs a copy of the inputs vector because its equivalence-class
51 // segregation algorithm destroys the proper sequence.
52 std::vector<ConcatInputSection *> icfInputs;
53
54 unsigned icfPass = 0;
55 std::atomic<bool> icfRepeat{false};
56 std::atomic<uint64_t> equalsConstantCount{0};
57 std::atomic<uint64_t> equalsVariableCount{0};
58};
59
60ICF::ICF(std::vector<ConcatInputSection *> &inputs) {
61 icfInputs.assign(first: inputs.begin(), last: inputs.end());
62}
63
64// ICF = Identical Code Folding
65//
66// We only fold __TEXT,__text, so this is really "code" folding, and not
67// "COMDAT" folding. String and scalar constant literals are deduplicated
68// elsewhere.
69//
70// Summary of segments & sections:
71//
72// The __TEXT segment is readonly at the MMU. Some sections are already
73// deduplicated elsewhere (__TEXT,__cstring & __TEXT,__literal*) and some are
74// synthetic and inherently free of duplicates (__TEXT,__stubs &
75// __TEXT,__unwind_info). Note that we don't yet run ICF on __TEXT,__const,
76// because doing so induces many test failures.
77//
78// The __LINKEDIT segment is readonly at the MMU, yet entirely synthetic, and
79// thus ineligible for ICF.
80//
81// The __DATA_CONST segment is read/write at the MMU, but is logically const to
82// the application after dyld applies fixups to pointer data. We currently
83// fold only the __DATA_CONST,__cfstring section.
84//
85// The __DATA segment is read/write at the MMU, and as application-writeable
86// data, none of its sections are eligible for ICF.
87//
88// Please see the large block comment in lld/ELF/ICF.cpp for an explanation
89// of the segregation algorithm.
90//
91// FIXME(gkm): implement keep-unique attributes
92// FIXME(gkm): implement address-significance tables for MachO object files
93
94static bool isFoldableIgnoringRelocatedBytes(const ConcatInputSection *isec) {
95 return isCfStringSection(isec) || isClassRefsSection(isec) ||
96 isSelRefsSection(isec) || isEhFrameSection(isec) ||
97 isGccExceptTabSection(isec);
98}
99
100// Make a normalized copy of a section's bytes by zeroing out the embedded
101// relocs. Return it in the given &buf
102static void getNormalizedData(const ConcatInputSection *isec,
103 SmallVectorImpl<uint8_t> &buf) {
104 buf.assign(in_start: isec->data.begin(), in_end: isec->data.end());
105 for (size_t i = 0; i < isec->relocs.size(); ++i) {
106 const Relocation &r = isec->relocs[i];
107 size_t size = 1ULL << r.length;
108 if (r.offset + size <= buf.size())
109 memset(s: buf.data() + r.offset, c: 0, n: size);
110 if (target->hasAttr(type: r.type, bit: RelocAttrBits::SUBTRAHEND))
111 ++i; // Skip the paired minuend relocation
112 }
113}
114
115static bool compareData(const ConcatInputSection *ia,
116 const ConcatInputSection *ib) {
117 if (ia->data.size() != ib->data.size())
118 return false;
119 if (ia->data == ib->data)
120 return true;
121 if (!isFoldableIgnoringRelocatedBytes(isec: ia))
122 return false;
123 assert(isFoldableIgnoringRelocatedBytes(ib));
124
125 SmallVector<uint8_t, 64> bufA, bufB;
126 getNormalizedData(isec: ia, buf&: bufA);
127 getNormalizedData(isec: ib, buf&: bufB);
128 return bufA == bufB;
129}
130
131// Compare "non-moving" parts of two ConcatInputSections, namely everything
132// except references to other ConcatInputSections.
133bool ICF::equalsConstant(const ConcatInputSection *ia,
134 const ConcatInputSection *ib) {
135 if (verboseDiagnostics)
136 ++equalsConstantCount;
137 // We can only fold within the same OutputSection.
138 if (ia->parent != ib->parent)
139 return false;
140 if (!compareData(ia, ib))
141 return false;
142 auto f = [](const Relocation &ra, const Relocation &rb) {
143 if (ra.type != rb.type)
144 return false;
145 if (ra.pcrel != rb.pcrel)
146 return false;
147 if (ra.length != rb.length)
148 return false;
149 if (ra.offset != rb.offset)
150 return false;
151 if (isa<Symbol *>(Val: ra.referent) != isa<Symbol *>(Val: rb.referent))
152 return false;
153
154 InputSection *isecA, *isecB;
155
156 uint64_t valueA = 0;
157 uint64_t valueB = 0;
158 if (isa<Symbol *>(Val: ra.referent)) {
159 const auto *sa = cast<Symbol *>(Val: ra.referent);
160 const auto *sb = cast<Symbol *>(Val: rb.referent);
161 if (sa->kind() != sb->kind())
162 return false;
163 // ICF runs before Undefineds are treated (and potentially converted into
164 // DylibSymbols).
165 if (isa<DylibSymbol>(Val: sa) || isa<Undefined>(Val: sa))
166 return sa == sb && ra.addend == rb.addend;
167 assert(isa<Defined>(sa));
168 const auto *da = cast<Defined>(Val: sa);
169 const auto *db = cast<Defined>(Val: sb);
170 if (!da->isec() || !db->isec()) {
171 assert(da->isAbsolute() && db->isAbsolute());
172 return da->value + ra.addend == db->value + rb.addend;
173 }
174 isecA = da->isec();
175 valueA = da->value;
176 isecB = db->isec();
177 valueB = db->value;
178 } else {
179 isecA = cast<InputSection *>(Val: ra.referent);
180 isecB = cast<InputSection *>(Val: rb.referent);
181 }
182
183 // Typically, we should not encounter sections marked with `keepUnique` at
184 // this point as they would have resulted in different hashes and therefore
185 // no need for a full comparison.
186 // However, in `safe_thunks` mode, it's possible for two different
187 // relocations to reference identical `keepUnique` functions that will be
188 // distinguished later via thunks - so we need to handle this case
189 // explicitly.
190 if ((isecA != isecB) && ((isecA->keepUnique && isCodeSection(isecA)) ||
191 (isecB->keepUnique && isCodeSection(isecB))))
192 return false;
193
194 if (isecA->parent != isecB->parent)
195 return false;
196 // Sections with identical parents should be of the same kind.
197 assert(isecA->kind() == isecB->kind());
198 // We will compare ConcatInputSection contents in equalsVariable.
199 if (isa<ConcatInputSection>(Val: isecA))
200 return valueA + ra.addend == valueB + rb.addend;
201 // Else we have two literal sections. References to them are equal iff their
202 // offsets in the output section are equal.
203 if (isa<Symbol *>(Val: ra.referent))
204 // For symbol relocs, we compare the contents at the symbol address. We
205 // don't do `getOffset(value + addend)` because value + addend may not be
206 // a valid offset in the literal section.
207 return isecA->getOffset(off: valueA) == isecB->getOffset(off: valueB) &&
208 ra.addend == rb.addend;
209 assert(valueA == 0 && valueB == 0);
210 // For section relocs, we compare the content at the section offset.
211 return isecA->getOffset(off: ra.addend) == isecB->getOffset(off: rb.addend);
212 };
213 if (!llvm::equal(LRange: ia->relocs, RRange: ib->relocs, P: f))
214 return false;
215
216 // Check unwind info structural compatibility: if there are symbols with
217 // associated unwind info, check that both sections have compatible symbol
218 // layouts. For simplicity, we only attempt folding when all symbols are at
219 // offset zero within the section (which is typically the case with
220 // .subsections_via_symbols.)
221 auto hasUnwind = [](Defined *d) { return d->unwindEntry() != nullptr; };
222 const auto *itA = llvm::find_if(Range: ia->symbols, P: hasUnwind);
223 const auto *itB = llvm::find_if(Range: ib->symbols, P: hasUnwind);
224 if (itA == ia->symbols.end())
225 return itB == ib->symbols.end();
226 if (itB == ib->symbols.end())
227 return false;
228 const Defined *da = *itA;
229 const Defined *db = *itB;
230 if (da->value != 0 || db->value != 0)
231 return false;
232 auto isZero = [](Defined *d) { return d->value == 0; };
233 // Since symbols are stored in order of value, and since we have already
234 // checked that da/db have value zero, we just need to do the isZero check on
235 // the subsequent symbols.
236 return std::find_if_not(first: std::next(x: itA), last: ia->symbols.end(), pred: isZero) ==
237 ia->symbols.end() &&
238 std::find_if_not(first: std::next(x: itB), last: ib->symbols.end(), pred: isZero) ==
239 ib->symbols.end();
240}
241
242// Compare the "moving" parts of two ConcatInputSections -- i.e. everything not
243// handled by equalsConstant().
244bool ICF::equalsVariable(const ConcatInputSection *ia,
245 const ConcatInputSection *ib) {
246 if (verboseDiagnostics)
247 ++equalsVariableCount;
248 assert(ia->relocs.size() == ib->relocs.size());
249 auto f = [this](const Relocation &ra, const Relocation &rb) {
250 // We already filtered out mismatching values/addends in equalsConstant.
251 if (ra.referent == rb.referent)
252 return true;
253 const ConcatInputSection *isecA, *isecB;
254 if (isa<Symbol *>(Val: ra.referent)) {
255 // Matching DylibSymbols are already filtered out by the
256 // identical-referent check above. Non-matching DylibSymbols were filtered
257 // out in equalsConstant(). So we can safely cast to Defined here.
258 const auto *da = cast<Defined>(Val: cast<Symbol *>(Val: ra.referent));
259 const auto *db = cast<Defined>(Val: cast<Symbol *>(Val: rb.referent));
260 if (da->isAbsolute())
261 return true;
262 isecA = dyn_cast<ConcatInputSection>(Val: da->isec());
263 if (!isecA)
264 return true; // literal sections were checked in equalsConstant.
265 isecB = cast<ConcatInputSection>(Val: db->isec());
266 } else {
267 const auto *sa = cast<InputSection *>(Val: ra.referent);
268 const auto *sb = cast<InputSection *>(Val: rb.referent);
269 isecA = dyn_cast<ConcatInputSection>(Val: sa);
270 if (!isecA)
271 return true;
272 isecB = cast<ConcatInputSection>(Val: sb);
273 }
274 return isecA->icfEqClass[icfPass % 2] == isecB->icfEqClass[icfPass % 2];
275 };
276 if (!llvm::equal(LRange: ia->relocs, RRange: ib->relocs, P: f))
277 return false;
278
279 // Compare unwind info equivalence classes.
280 auto hasUnwind = [](Defined *d) { return d->unwindEntry() != nullptr; };
281 const auto *itA = llvm::find_if(Range: ia->symbols, P: hasUnwind);
282 if (itA == ia->symbols.end())
283 return true;
284 const Defined *da = *itA;
285 // equalsConstant() guarantees that both sections have unwind info.
286 const Defined *db = *llvm::find_if(Range: ib->symbols, P: hasUnwind);
287 return da->unwindEntry()->icfEqClass[icfPass % 2] ==
288 db->unwindEntry()->icfEqClass[icfPass % 2];
289}
290
291// Find the first InputSection after BEGIN whose equivalence class differs
292size_t ICF::findBoundary(size_t begin, size_t end) {
293 uint64_t beginHash = icfInputs[begin]->icfEqClass[icfPass % 2];
294 for (size_t i = begin + 1; i < end; ++i)
295 if (beginHash != icfInputs[i]->icfEqClass[icfPass % 2])
296 return i;
297 return end;
298}
299
300// Invoke FUNC on subranges with matching equivalence class
301void ICF::forEachClassRange(size_t begin, size_t end,
302 llvm::function_ref<void(size_t, size_t)> func) {
303 while (begin < end) {
304 size_t mid = findBoundary(begin, end);
305 func(begin, mid);
306 begin = mid;
307 }
308}
309
310// Find or create a symbol at offset 0 in the given section
311static Symbol *getThunkTargetSymbol(ConcatInputSection *isec) {
312 for (Symbol *sym : isec->symbols)
313 if (auto *d = dyn_cast<Defined>(Val: sym))
314 if (d->value == 0)
315 return sym;
316
317 std::string thunkName;
318 if (isec->symbols.size() == 0)
319 thunkName = isec->getName().str() + ".icf.0";
320 else
321 thunkName = isec->getName().str() + "icf.thunk.target" +
322 std::to_string(val: icfThunkCounter++);
323
324 // If no symbol found at offset 0, create one
325 auto *sym = make<Defined>(args&: thunkName, /*file=*/args: nullptr, args&: isec,
326 /*value=*/args: 0, /*size=*/args: isec->getSize(),
327 /*isWeakDef=*/args: false, /*isExternal=*/args: false,
328 /*isPrivateExtern=*/args: false, /*isThumb=*/args: false,
329 /*isReferencedDynamically=*/args: false,
330 /*noDeadStrip=*/args: false);
331 isec->symbols.push_back(NewVal: sym);
332 return sym;
333}
334
335// Given a range of identical icfInputs, replace address significant functions
336// with a thunk that is just a direct branch to the first function in the
337// series. This way we keep only one main body of the function but we still
338// retain the address uniqueness of relevant functions by having them be a
339// direct branch thunk rather than containing a full copy of the actual function
340// body.
341void ICF::applySafeThunksToRange(size_t begin, size_t end) {
342 // When creating a unique ICF thunk, use the first section as the section that
343 // all thunks will branch to.
344 ConcatInputSection *masterIsec = icfInputs[begin];
345
346 // If the first section is not address significant, sorting guarantees that
347 // there are no address significant functions. So we can skip this range.
348 if (!masterIsec->keepUnique)
349 return;
350
351 // Skip anything that is not a code section.
352 if (!isCodeSection(masterIsec))
353 return;
354
355 // If the functions we're dealing with are smaller than the thunk size, then
356 // just leave them all as-is - creating thunks would be a net loss.
357 uint32_t thunkSize = target->getICFSafeThunkSize();
358 if (masterIsec->data.size() <= thunkSize)
359 return;
360
361 // Get the symbol that all thunks will branch to.
362 Symbol *masterSym = getThunkTargetSymbol(isec: masterIsec);
363
364 for (size_t i = begin + 1; i < end; ++i) {
365 ConcatInputSection *isec = icfInputs[i];
366 // When we're done processing keepUnique entries, we can stop. Sorting
367 // guaratees that all keepUnique will be at the front.
368 if (!isec->keepUnique)
369 break;
370
371 ConcatInputSection *thunk =
372 makeSyntheticInputSection(segName: isec->getSegName(), sectName: isec->getName());
373 // A thunk-folded cold function has a cold thunk.
374 thunk->isCold = isec->isCold;
375 addInputSection(inputSection: thunk);
376
377 target->initICFSafeThunkBody(thunk, targetSym: masterSym);
378 thunk->foldIdentical(redundant: isec, foldKind: Symbol::ICFFoldKind::Thunk);
379
380 // Since we're folding the target function into a thunk, we need to adjust
381 // the symbols that now got relocated from the target function to the thunk.
382 // Since the thunk is only one branch, we move all symbols to offset 0 and
383 // make sure that the size of all non-zero-size symbols is equal to the size
384 // of the branch.
385 for (auto *sym : thunk->symbols) {
386 sym->value = 0;
387 if (sym->size != 0)
388 sym->size = thunkSize;
389 }
390 }
391}
392
393// Split icfInputs into shards, then parallelize invocation of FUNC on subranges
394// with matching equivalence class
395void ICF::forEachClass(llvm::function_ref<void(size_t, size_t)> func) {
396 // Only use threads when the benefits outweigh the overhead.
397 const size_t threadingThreshold = 1024;
398 if (icfInputs.size() < threadingThreshold) {
399 forEachClassRange(begin: 0, end: icfInputs.size(), func);
400 ++icfPass;
401 return;
402 }
403
404 // Shard into non-overlapping intervals, and call FUNC in parallel. The
405 // sharding must be completed before any calls to FUNC are made so that FUNC
406 // can modify the InputSection in its shard without causing data races.
407 const size_t shards = 256;
408 size_t step = icfInputs.size() / shards;
409 size_t boundaries[shards + 1];
410 boundaries[0] = 0;
411 boundaries[shards] = icfInputs.size();
412 parallelFor(Begin: 1, End: shards, Fn: [&](size_t i) {
413 boundaries[i] = findBoundary(begin: (i - 1) * step, end: icfInputs.size());
414 });
415 parallelFor(Begin: 1, End: shards + 1, Fn: [&](size_t i) {
416 if (boundaries[i - 1] < boundaries[i]) {
417 forEachClassRange(begin: boundaries[i - 1], end: boundaries[i], func);
418 }
419 });
420 ++icfPass;
421}
422
423void ICF::run() {
424 // Into each origin-section hash, combine all reloc referent section hashes.
425 for (icfPass = 0; icfPass < 2; ++icfPass) {
426 parallelForEach(R&: icfInputs, Fn: [&](ConcatInputSection *isec) {
427 uint32_t hash = isec->icfEqClass[icfPass % 2];
428 for (const Relocation &r : isec->relocs) {
429 if (auto *sym = r.referent.dyn_cast<Symbol *>()) {
430 if (auto *defined = dyn_cast<Defined>(Val: sym)) {
431 if (defined->isec()) {
432 if (auto *referentIsec =
433 dyn_cast<ConcatInputSection>(Val: defined->isec()))
434 hash += defined->value + referentIsec->icfEqClass[icfPass % 2];
435 else
436 hash += defined->isec()->kind() +
437 defined->isec()->getOffset(off: defined->value);
438 } else {
439 hash += defined->value;
440 }
441 } else {
442 // ICF runs before Undefined diags
443 assert(isa<Undefined>(sym) || isa<DylibSymbol>(sym));
444 }
445 }
446 }
447 // Set MSB to 1 to avoid collisions with non-hashed classes.
448 isec->icfEqClass[(icfPass + 1) % 2] = hash | (1ull << 31);
449 });
450 }
451 const bool useSafeThunks = config->icfLevel == ICFLevel::safe_thunks;
452 // Sort by icfEqClass so that inputs in the same equivalence class are
453 // consecutive. When using safe_thunks, also sort by keepUnique (descending)
454 // within a class. This guarantees that within an equivalence class, the
455 // keepUnique inputs are always first. The index in the low bits keeps the
456 // order stable.
457 assert(icfInputs.size() <= (1u << 31));
458 SmallVector<uint64_t, 0> keys(icfInputs.size());
459 parallelFor(Begin: 0, End: icfInputs.size(), Fn: [&](size_t i) {
460 uint64_t key = uint64_t(icfInputs[i]->icfEqClass[0]) << 32 | i;
461 if (useSafeThunks && !icfInputs[i]->keepUnique)
462 key |= 1u << 31;
463 keys[i] = key;
464 });
465 parallelSort(Start: keys.begin(), End: keys.end());
466 std::vector<ConcatInputSection *> sorted;
467 sorted.reserve(n: keys.size());
468 for (uint64_t k : keys)
469 sorted.push_back(x: icfInputs[k & ((1u << 31) - 1)]);
470 icfInputs = std::move(sorted);
471 forEachClass(func: [&](size_t begin, size_t end) {
472 segregate(begin, end, &ICF::equalsConstant);
473 });
474
475 // Split equivalence groups by comparing relocations until convergence
476 do {
477 icfRepeat = false;
478 forEachClass(func: [&](size_t begin, size_t end) {
479 segregate(begin, end, &ICF::equalsVariable);
480 });
481 } while (icfRepeat);
482 log(msg: "ICF needed " + Twine(icfPass) + " iterations");
483 if (verboseDiagnostics) {
484 log(msg: "equalsConstant() called " + Twine(equalsConstantCount) + " times");
485 log(msg: "equalsVariable() called " + Twine(equalsVariableCount) + " times");
486 }
487
488 // When using safe_thunks, we need to create thunks for all keepUnique
489 // functions that can be deduplicated. Since we're creating / adding new
490 // InputSections, we can't paralellize this.
491 if (useSafeThunks)
492 forEachClassRange(begin: 0, end: icfInputs.size(), func: [&](size_t begin, size_t end) {
493 applySafeThunksToRange(begin, end);
494 });
495
496 // Fold sections within equivalence classes
497 forEachClass(func: [&](size_t begin, size_t end) {
498 if (end - begin < 2)
499 return;
500 // For ICF level safe_thunks, replace keepUnique function bodies with
501 // thunks. For all other ICF levels, directly merge the functions.
502
503 ConcatInputSection *beginIsec = icfInputs[begin];
504 for (size_t i = begin + 1; i < end; ++i) {
505 // Skip keepUnique inputs when using safe_thunks (already handled above)
506 if (useSafeThunks && isCodeSection(beginIsec) &&
507 icfInputs[i]->keepUnique) {
508 // Assert keepUnique sections are either small or replaced with thunks.
509 assert(!icfInputs[i]->live ||
510 icfInputs[i]->data.size() <= target->getICFSafeThunkSize());
511 assert(!icfInputs[i]->replacement ||
512 icfInputs[i]->replacement->data.size() ==
513 target->getICFSafeThunkSize());
514 continue;
515 }
516 beginIsec->foldIdentical(redundant: icfInputs[i]);
517 // Make sure we don't fold hot code into cold regions.
518 if (!icfInputs[i]->isCold)
519 beginIsec->isCold = false;
520 }
521 });
522}
523
524// Split an equivalence class into smaller classes.
525void ICF::segregate(size_t begin, size_t end, EqualsFn equals) {
526 while (begin < end) {
527 // Divide [begin, end) into two. Let mid be the start index of the
528 // second group.
529 auto bound = std::stable_partition(
530 first: icfInputs.begin() + begin + 1, last: icfInputs.begin() + end,
531 pred: [&](ConcatInputSection *isec) {
532 return (this->*equals)(icfInputs[begin], isec);
533 });
534 size_t mid = bound - icfInputs.begin();
535
536 // Split [begin, end) into [begin, mid) and [mid, end). We use mid as an
537 // equivalence class ID because every group ends with a unique index.
538 for (size_t i = begin; i < mid; ++i)
539 icfInputs[i]->icfEqClass[(icfPass + 1) % 2] = mid;
540
541 // If we created a group, we need to iterate the main loop again.
542 if (mid != end)
543 icfRepeat = true;
544
545 begin = mid;
546 }
547}
548
549void macho::markSymAsAddrSig(Symbol *s) {
550 if (auto *d = dyn_cast_or_null<Defined>(Val: s))
551 if (d->isec())
552 d->isec()->keepUnique = true;
553}
554
555void macho::markAddrSigSymbols() {
556 TimeTraceScope timeScope("Mark addrsig symbols");
557 for (InputFile *file : inputFiles) {
558 ObjFile *obj = dyn_cast<ObjFile>(Val: file);
559 if (!obj)
560 continue;
561
562 Section *addrSigSection = obj->addrSigSection;
563 if (!addrSigSection) {
564 for (Symbol *sym : obj->symbols)
565 markSymAsAddrSig(s: sym);
566 continue;
567 }
568 assert(addrSigSection->subsections.size() == 1);
569
570 const InputSection *isec = addrSigSection->subsections[0].isec;
571
572 for (const Relocation &r : isec->relocs) {
573 if (auto *sym = r.referent.dyn_cast<Symbol *>())
574 markSymAsAddrSig(s: sym);
575 else
576 error(msg: toString(isec) + ": unexpected section relocation");
577 }
578 }
579}
580
581// Given a symbol that was folded into a thunk, return the symbol pointing to
582// the actual body of the function. We use this approach rather than storing the
583// needed info in the Defined itself in order to minimize memory usage.
584Defined *macho::getBodyForThunkFoldedSym(Defined *foldedSym) {
585 assert(isa<ConcatInputSection>(foldedSym->originalIsec) &&
586 "thunk-folded ICF symbol expected to be on a ConcatInputSection");
587 // foldedSec is the InputSection that was marked as deleted upon fold
588 ConcatInputSection *foldedSec =
589 cast<ConcatInputSection>(Val: foldedSym->originalIsec);
590
591 // thunkBody is the actual live thunk, containing the code that branches to
592 // the actual body of the function.
593 InputSection *thunkBody = foldedSec->replacement;
594
595 // The symbol of the merged body of the function that the thunk jumps to. This
596 // will end up in the final binary.
597 Defined *bodySym = cast<Defined>(Val: target->getThunkBranchTarget(thunk: thunkBody));
598 if (bodySym->branchExtensionThunk) {
599 // For branch extension thunks, follow relocations to get the original body
600 InputSection *thunk = bodySym->isec();
601 assert(thunk && !thunk->relocs.empty());
602 const Relocation &r = thunk->relocs.front();
603 assert(r.addend == 0);
604 bodySym = cast<Defined>(Val: cast<Symbol *>(Val: r.referent));
605 assert(!bodySym->branchExtensionThunk);
606 }
607
608 return bodySym;
609}
610void macho::foldIdenticalSections(bool onlyCfStrings) {
611 TimeTraceScope timeScope("Fold Identical Code Sections");
612 // The ICF equivalence-class segregation algorithm relies on pre-computed
613 // hashes of InputSection::data for the ConcatOutputSection::inputs and all
614 // sections referenced by their relocs. We could recursively traverse the
615 // relocs to find every referenced InputSection, but that precludes easy
616 // parallelization. Therefore, we hash every InputSection here where we have
617 // them all accessible as simple vectors.
618
619 // If an InputSection is ineligible for ICF, we give it a unique ID to force
620 // it into an unfoldable singleton equivalence class. Begin the unique-ID
621 // space at inputSections.size(), so that it will never intersect with
622 // equivalence-class IDs which begin at 0. Since hashes & unique IDs never
623 // coexist with equivalence-class IDs, this is not necessary, but might help
624 // someone keep the numbers straight in case we ever need to debug the
625 // ICF::segregate()
626 std::vector<ConcatInputSection *> foldable;
627 uint64_t icfUniqueID = inputSections.size();
628 // Reset the thunk counter for each run of ICF.
629 icfThunkCounter = 0;
630 for (ConcatInputSection *isec : inputSections) {
631 bool isUnconditionallyCoalescedData = isCfStringSection(isec) ||
632 isClassRefsSection(isec) ||
633 isSelRefsSection(isec);
634 // NOTE: __objc_selrefs is typically marked as no_dead_strip by MC, but we
635 // can still fold it.
636 bool hasFoldableFlags = (isSelRefsSection(isec) ||
637 sectionType(flags: isec->getFlags()) == MachO::S_REGULAR);
638
639 bool isCodeSec = isCodeSection(isec);
640
641 // Determine whether keepUnique forbids folding this section.
642 // - __cfstring / __objc_classrefs / __objc_selrefs always fold
643 // regardless of keepUnique. Compilers currently emit over-broad
644 // __llvm_addrsig entries that can cover non-address-significant data
645 // symbols in these sections; ld64 coalesces them unconditionally, and
646 // we match that behavior.
647 // - Under safe_thunks, keepUnique code sections still fold; the
648 // safe_thunks logic is applied later at merge time based on the
649 // keepUnique flag.
650 // - Otherwise, keepUnique sections are not foldable.
651 bool isSafeThunksCode =
652 config->icfLevel == ICFLevel::safe_thunks && isCodeSec;
653 bool keepUniqueAllowsFolding =
654 !isec->keepUnique || isUnconditionallyCoalescedData || isSafeThunksCode;
655
656 // FIXME: consider non-code __text sections as foldable?
657 bool isFoldable = (!onlyCfStrings || isCfStringSection(isec)) &&
658 (isCodeSec || isFoldableIgnoringRelocatedBytes(isec)) &&
659 keepUniqueAllowsFolding && !isec->hasAltEntry &&
660 !isec->shouldOmitFromOutput() && hasFoldableFlags;
661 if (isFoldable) {
662 foldable.push_back(x: isec);
663 for (Defined *d : isec->symbols)
664 if (d->unwindEntry())
665 foldable.push_back(x: d->unwindEntry());
666 } else if (isEhFrameSection(isec)) {
667 // __eh_frame contains two types of records: FDEs and CIEs.
668 // Functions point to FDEs, which are already collected above via
669 // unwindEntry(). CIEs are shared headers and are not attached to
670 // individual functions. Collect only CIEs here so they can also be hashed
671 // and deduplicated.
672 auto *obj = dyn_cast_or_null<ObjFile>(Val: isec->getFile());
673 if (!onlyCfStrings && obj && !obj->fdes.contains(Val: isec) &&
674 !isec->shouldOmitFromOutput())
675 foldable.push_back(x: isec);
676 } else {
677 // Give a unique ID to everything else.
678 isec->icfEqClass[0] = ++icfUniqueID;
679 }
680 }
681 parallelForEach(R&: foldable, Fn: [](ConcatInputSection *isec) {
682 assert(isec->icfEqClass[0] == 0); // don't overwrite a unique ID!
683 uint64_t hash;
684 if (isFoldableIgnoringRelocatedBytes(isec)) {
685 SmallVector<uint8_t, 64> stackBuf;
686 getNormalizedData(isec, buf&: stackBuf);
687 hash = xxh3_64bits(data: stackBuf);
688 } else {
689 hash = xxh3_64bits(data: isec->data);
690 }
691 // Turn-on the top bit to guarantee that valid hashes have no collisions
692 // with the small-integer unique IDs for ICF-ineligible sections
693 isec->icfEqClass[0] = hash | (1ull << 31);
694 });
695 // Now that every input section is either hashed or marked as unique, run the
696 // segregation algorithm to detect foldable subsections.
697 ICF(foldable).run();
698}
699