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