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
94// Compare "non-moving" parts of two ConcatInputSections, namely everything
95// except references to other ConcatInputSections.
96bool ICF::equalsConstant(const ConcatInputSection *ia,
97 const ConcatInputSection *ib) {
98 if (verboseDiagnostics)
99 ++equalsConstantCount;
100 // We can only fold within the same OutputSection.
101 if (ia->parent != ib->parent)
102 return false;
103 if (ia->data.size() != ib->data.size())
104 return false;
105 if (ia->data != ib->data)
106 return false;
107 if (ia->relocs.size() != ib->relocs.size())
108 return false;
109 auto f = [](const Relocation &ra, const Relocation &rb) {
110 if (ra.type != rb.type)
111 return false;
112 if (ra.pcrel != rb.pcrel)
113 return false;
114 if (ra.length != rb.length)
115 return false;
116 if (ra.offset != rb.offset)
117 return false;
118 if (isa<Symbol *>(Val: ra.referent) != isa<Symbol *>(Val: rb.referent))
119 return false;
120
121 InputSection *isecA, *isecB;
122
123 uint64_t valueA = 0;
124 uint64_t valueB = 0;
125 if (isa<Symbol *>(Val: ra.referent)) {
126 const auto *sa = cast<Symbol *>(Val: ra.referent);
127 const auto *sb = cast<Symbol *>(Val: rb.referent);
128 if (sa->kind() != sb->kind())
129 return false;
130 // ICF runs before Undefineds are treated (and potentially converted into
131 // DylibSymbols).
132 if (isa<DylibSymbol>(Val: sa) || isa<Undefined>(Val: sa))
133 return sa == sb && ra.addend == rb.addend;
134 assert(isa<Defined>(sa));
135 const auto *da = cast<Defined>(Val: sa);
136 const auto *db = cast<Defined>(Val: sb);
137 if (!da->isec() || !db->isec()) {
138 assert(da->isAbsolute() && db->isAbsolute());
139 return da->value + ra.addend == db->value + rb.addend;
140 }
141 isecA = da->isec();
142 valueA = da->value;
143 isecB = db->isec();
144 valueB = db->value;
145 } else {
146 isecA = cast<InputSection *>(Val: ra.referent);
147 isecB = cast<InputSection *>(Val: rb.referent);
148 }
149
150 // Typically, we should not encounter sections marked with `keepUnique` at
151 // this point as they would have resulted in different hashes and therefore
152 // no need for a full comparison.
153 // However, in `safe_thunks` mode, it's possible for two different
154 // relocations to reference identical `keepUnique` functions that will be
155 // distinguished later via thunks - so we need to handle this case
156 // explicitly.
157 if ((isecA != isecB) && ((isecA->keepUnique && isCodeSection(isecA)) ||
158 (isecB->keepUnique && isCodeSection(isecB))))
159 return false;
160
161 if (isecA->parent != isecB->parent)
162 return false;
163 // Sections with identical parents should be of the same kind.
164 assert(isecA->kind() == isecB->kind());
165 // We will compare ConcatInputSection contents in equalsVariable.
166 if (isa<ConcatInputSection>(Val: isecA))
167 return ra.addend == rb.addend;
168 // Else we have two literal sections. References to them are equal iff their
169 // offsets in the output section are equal.
170 if (isa<Symbol *>(Val: ra.referent))
171 // For symbol relocs, we compare the contents at the symbol address. We
172 // don't do `getOffset(value + addend)` because value + addend may not be
173 // a valid offset in the literal section.
174 return isecA->getOffset(off: valueA) == isecB->getOffset(off: valueB) &&
175 ra.addend == rb.addend;
176 assert(valueA == 0 && valueB == 0);
177 // For section relocs, we compare the content at the section offset.
178 return isecA->getOffset(off: ra.addend) == isecB->getOffset(off: rb.addend);
179 };
180 if (!llvm::equal(LRange: ia->relocs, RRange: ib->relocs, P: f))
181 return false;
182
183 // Check unwind info structural compatibility: if there are symbols with
184 // associated unwind info, check that both sections have compatible symbol
185 // layouts. For simplicity, we only attempt folding when all symbols are at
186 // offset zero within the section (which is typically the case with
187 // .subsections_via_symbols.)
188 auto hasUnwind = [](Defined *d) { return d->unwindEntry() != nullptr; };
189 const auto *itA = llvm::find_if(Range: ia->symbols, P: hasUnwind);
190 const auto *itB = llvm::find_if(Range: ib->symbols, P: hasUnwind);
191 if (itA == ia->symbols.end())
192 return itB == ib->symbols.end();
193 if (itB == ib->symbols.end())
194 return false;
195 const Defined *da = *itA;
196 const Defined *db = *itB;
197 if (da->value != 0 || db->value != 0)
198 return false;
199 auto isZero = [](Defined *d) { return d->value == 0; };
200 // Since symbols are stored in order of value, and since we have already
201 // checked that da/db have value zero, we just need to do the isZero check on
202 // the subsequent symbols.
203 return std::find_if_not(first: std::next(x: itA), last: ia->symbols.end(), pred: isZero) ==
204 ia->symbols.end() &&
205 std::find_if_not(first: std::next(x: itB), last: ib->symbols.end(), pred: isZero) ==
206 ib->symbols.end();
207}
208
209// Compare the "moving" parts of two ConcatInputSections -- i.e. everything not
210// handled by equalsConstant().
211bool ICF::equalsVariable(const ConcatInputSection *ia,
212 const ConcatInputSection *ib) {
213 if (verboseDiagnostics)
214 ++equalsVariableCount;
215 assert(ia->relocs.size() == ib->relocs.size());
216 auto f = [this](const Relocation &ra, const Relocation &rb) {
217 // We already filtered out mismatching values/addends in equalsConstant.
218 if (ra.referent == rb.referent)
219 return true;
220 const ConcatInputSection *isecA, *isecB;
221 if (isa<Symbol *>(Val: ra.referent)) {
222 // Matching DylibSymbols are already filtered out by the
223 // identical-referent check above. Non-matching DylibSymbols were filtered
224 // out in equalsConstant(). So we can safely cast to Defined here.
225 const auto *da = cast<Defined>(Val: cast<Symbol *>(Val: ra.referent));
226 const auto *db = cast<Defined>(Val: cast<Symbol *>(Val: rb.referent));
227 if (da->isAbsolute())
228 return true;
229 isecA = dyn_cast<ConcatInputSection>(Val: da->isec());
230 if (!isecA)
231 return true; // literal sections were checked in equalsConstant.
232 isecB = cast<ConcatInputSection>(Val: db->isec());
233 } else {
234 const auto *sa = cast<InputSection *>(Val: ra.referent);
235 const auto *sb = cast<InputSection *>(Val: rb.referent);
236 isecA = dyn_cast<ConcatInputSection>(Val: sa);
237 if (!isecA)
238 return true;
239 isecB = cast<ConcatInputSection>(Val: sb);
240 }
241 return isecA->icfEqClass[icfPass % 2] == isecB->icfEqClass[icfPass % 2];
242 };
243 if (!llvm::equal(LRange: ia->relocs, RRange: ib->relocs, P: f))
244 return false;
245
246 // Compare unwind info equivalence classes.
247 auto hasUnwind = [](Defined *d) { return d->unwindEntry() != nullptr; };
248 const auto *itA = llvm::find_if(Range: ia->symbols, P: hasUnwind);
249 if (itA == ia->symbols.end())
250 return true;
251 const Defined *da = *itA;
252 // equalsConstant() guarantees that both sections have unwind info.
253 const Defined *db = *llvm::find_if(Range: ib->symbols, P: hasUnwind);
254 return da->unwindEntry()->icfEqClass[icfPass % 2] ==
255 db->unwindEntry()->icfEqClass[icfPass % 2];
256}
257
258// Find the first InputSection after BEGIN whose equivalence class differs
259size_t ICF::findBoundary(size_t begin, size_t end) {
260 uint64_t beginHash = icfInputs[begin]->icfEqClass[icfPass % 2];
261 for (size_t i = begin + 1; i < end; ++i)
262 if (beginHash != icfInputs[i]->icfEqClass[icfPass % 2])
263 return i;
264 return end;
265}
266
267// Invoke FUNC on subranges with matching equivalence class
268void ICF::forEachClassRange(size_t begin, size_t end,
269 llvm::function_ref<void(size_t, size_t)> func) {
270 while (begin < end) {
271 size_t mid = findBoundary(begin, end);
272 func(begin, mid);
273 begin = mid;
274 }
275}
276
277// Find or create a symbol at offset 0 in the given section
278static Symbol *getThunkTargetSymbol(ConcatInputSection *isec) {
279 for (Symbol *sym : isec->symbols)
280 if (auto *d = dyn_cast<Defined>(Val: sym))
281 if (d->value == 0)
282 return sym;
283
284 std::string thunkName;
285 if (isec->symbols.size() == 0)
286 thunkName = isec->getName().str() + ".icf.0";
287 else
288 thunkName = isec->getName().str() + "icf.thunk.target" +
289 std::to_string(val: icfThunkCounter++);
290
291 // If no symbol found at offset 0, create one
292 auto *sym = make<Defined>(args&: thunkName, /*file=*/args: nullptr, args&: isec,
293 /*value=*/args: 0, /*size=*/args: isec->getSize(),
294 /*isWeakDef=*/args: false, /*isExternal=*/args: false,
295 /*isPrivateExtern=*/args: false, /*isThumb=*/args: false,
296 /*isReferencedDynamically=*/args: false,
297 /*noDeadStrip=*/args: false);
298 isec->symbols.push_back(NewVal: sym);
299 return sym;
300}
301
302// Given a range of identical icfInputs, replace address significant functions
303// with a thunk that is just a direct branch to the first function in the
304// series. This way we keep only one main body of the function but we still
305// retain the address uniqueness of relevant functions by having them be a
306// direct branch thunk rather than containing a full copy of the actual function
307// body.
308void ICF::applySafeThunksToRange(size_t begin, size_t end) {
309 // When creating a unique ICF thunk, use the first section as the section that
310 // all thunks will branch to.
311 ConcatInputSection *masterIsec = icfInputs[begin];
312
313 // If the first section is not address significant, sorting guarantees that
314 // there are no address significant functions. So we can skip this range.
315 if (!masterIsec->keepUnique)
316 return;
317
318 // Skip anything that is not a code section.
319 if (!isCodeSection(masterIsec))
320 return;
321
322 // If the functions we're dealing with are smaller than the thunk size, then
323 // just leave them all as-is - creating thunks would be a net loss.
324 uint32_t thunkSize = target->getICFSafeThunkSize();
325 if (masterIsec->data.size() <= thunkSize)
326 return;
327
328 // Get the symbol that all thunks will branch to.
329 Symbol *masterSym = getThunkTargetSymbol(isec: masterIsec);
330
331 for (size_t i = begin + 1; i < end; ++i) {
332 ConcatInputSection *isec = icfInputs[i];
333 // When we're done processing keepUnique entries, we can stop. Sorting
334 // guaratees that all keepUnique will be at the front.
335 if (!isec->keepUnique)
336 break;
337
338 ConcatInputSection *thunk =
339 makeSyntheticInputSection(segName: isec->getSegName(), sectName: isec->getName());
340 addInputSection(inputSection: thunk);
341
342 target->initICFSafeThunkBody(thunk, targetSym: masterSym);
343 thunk->foldIdentical(redundant: isec, foldKind: Symbol::ICFFoldKind::Thunk);
344
345 // Since we're folding the target function into a thunk, we need to adjust
346 // the symbols that now got relocated from the target function to the thunk.
347 // Since the thunk is only one branch, we move all symbols to offset 0 and
348 // make sure that the size of all non-zero-size symbols is equal to the size
349 // of the branch.
350 for (auto *sym : thunk->symbols) {
351 sym->value = 0;
352 if (sym->size != 0)
353 sym->size = thunkSize;
354 }
355 }
356}
357
358// Split icfInputs into shards, then parallelize invocation of FUNC on subranges
359// with matching equivalence class
360void ICF::forEachClass(llvm::function_ref<void(size_t, size_t)> func) {
361 // Only use threads when the benefits outweigh the overhead.
362 const size_t threadingThreshold = 1024;
363 if (icfInputs.size() < threadingThreshold) {
364 forEachClassRange(begin: 0, end: icfInputs.size(), func);
365 ++icfPass;
366 return;
367 }
368
369 // Shard into non-overlapping intervals, and call FUNC in parallel. The
370 // sharding must be completed before any calls to FUNC are made so that FUNC
371 // can modify the InputSection in its shard without causing data races.
372 const size_t shards = 256;
373 size_t step = icfInputs.size() / shards;
374 size_t boundaries[shards + 1];
375 boundaries[0] = 0;
376 boundaries[shards] = icfInputs.size();
377 parallelFor(Begin: 1, End: shards, Fn: [&](size_t i) {
378 boundaries[i] = findBoundary(begin: (i - 1) * step, end: icfInputs.size());
379 });
380 parallelFor(Begin: 1, End: shards + 1, Fn: [&](size_t i) {
381 if (boundaries[i - 1] < boundaries[i]) {
382 forEachClassRange(begin: boundaries[i - 1], end: boundaries[i], func);
383 }
384 });
385 ++icfPass;
386}
387
388void ICF::run() {
389 // Into each origin-section hash, combine all reloc referent section hashes.
390 for (icfPass = 0; icfPass < 2; ++icfPass) {
391 parallelForEach(R&: icfInputs, Fn: [&](ConcatInputSection *isec) {
392 uint32_t hash = isec->icfEqClass[icfPass % 2];
393 for (const Relocation &r : isec->relocs) {
394 if (auto *sym = r.referent.dyn_cast<Symbol *>()) {
395 if (auto *defined = dyn_cast<Defined>(Val: sym)) {
396 if (defined->isec()) {
397 if (auto *referentIsec =
398 dyn_cast<ConcatInputSection>(Val: defined->isec()))
399 hash += defined->value + referentIsec->icfEqClass[icfPass % 2];
400 else
401 hash += defined->isec()->kind() +
402 defined->isec()->getOffset(off: defined->value);
403 } else {
404 hash += defined->value;
405 }
406 } else {
407 // ICF runs before Undefined diags
408 assert(isa<Undefined>(sym) || isa<DylibSymbol>(sym));
409 }
410 }
411 }
412 // Set MSB to 1 to avoid collisions with non-hashed classes.
413 isec->icfEqClass[(icfPass + 1) % 2] = hash | (1ull << 31);
414 });
415 }
416
417 llvm::stable_sort(
418 Range&: icfInputs, C: [](const ConcatInputSection *a, const ConcatInputSection *b) {
419 // When using safe_thunks, ensure that we first sort by icfEqClass and
420 // then by keepUnique (descending). This guarantees that within an
421 // equivalence class, the keepUnique inputs are always first.
422 if (config->icfLevel == ICFLevel::safe_thunks)
423 if (a->icfEqClass[0] == b->icfEqClass[0])
424 return a->keepUnique > b->keepUnique;
425 return a->icfEqClass[0] < b->icfEqClass[0];
426 });
427 forEachClass(func: [&](size_t begin, size_t end) {
428 segregate(begin, end, &ICF::equalsConstant);
429 });
430
431 // Split equivalence groups by comparing relocations until convergence
432 do {
433 icfRepeat = false;
434 forEachClass(func: [&](size_t begin, size_t end) {
435 segregate(begin, end, &ICF::equalsVariable);
436 });
437 } while (icfRepeat);
438 log(msg: "ICF needed " + Twine(icfPass) + " iterations");
439 if (verboseDiagnostics) {
440 log(msg: "equalsConstant() called " + Twine(equalsConstantCount) + " times");
441 log(msg: "equalsVariable() called " + Twine(equalsVariableCount) + " times");
442 }
443
444 // When using safe_thunks, we need to create thunks for all keepUnique
445 // functions that can be deduplicated. Since we're creating / adding new
446 // InputSections, we can't paralellize this.
447 if (config->icfLevel == ICFLevel::safe_thunks)
448 forEachClassRange(begin: 0, end: icfInputs.size(), func: [&](size_t begin, size_t end) {
449 applySafeThunksToRange(begin, end);
450 });
451
452 // Fold sections within equivalence classes
453 forEachClass(func: [&](size_t begin, size_t end) {
454 if (end - begin < 2)
455 return;
456 bool useSafeThunks = config->icfLevel == ICFLevel::safe_thunks;
457
458 // For ICF level safe_thunks, replace keepUnique function bodies with
459 // thunks. For all other ICF levles, directly merge the functions.
460
461 ConcatInputSection *beginIsec = icfInputs[begin];
462 for (size_t i = begin + 1; i < end; ++i) {
463 // Skip keepUnique inputs when using safe_thunks (already handled above)
464 if (useSafeThunks && icfInputs[i]->keepUnique) {
465 // Assert keepUnique sections are either small or replaced with thunks.
466 assert(!icfInputs[i]->live ||
467 icfInputs[i]->data.size() <= target->getICFSafeThunkSize());
468 assert(!icfInputs[i]->replacement ||
469 icfInputs[i]->replacement->data.size() ==
470 target->getICFSafeThunkSize());
471 continue;
472 }
473 beginIsec->foldIdentical(redundant: icfInputs[i]);
474 }
475 });
476}
477
478// Split an equivalence class into smaller classes.
479void ICF::segregate(size_t begin, size_t end, EqualsFn equals) {
480 while (begin < end) {
481 // Divide [begin, end) into two. Let mid be the start index of the
482 // second group.
483 auto bound = std::stable_partition(
484 first: icfInputs.begin() + begin + 1, last: icfInputs.begin() + end,
485 pred: [&](ConcatInputSection *isec) {
486 return (this->*equals)(icfInputs[begin], isec);
487 });
488 size_t mid = bound - icfInputs.begin();
489
490 // Split [begin, end) into [begin, mid) and [mid, end). We use mid as an
491 // equivalence class ID because every group ends with a unique index.
492 for (size_t i = begin; i < mid; ++i)
493 icfInputs[i]->icfEqClass[(icfPass + 1) % 2] = mid;
494
495 // If we created a group, we need to iterate the main loop again.
496 if (mid != end)
497 icfRepeat = true;
498
499 begin = mid;
500 }
501}
502
503void macho::markSymAsAddrSig(Symbol *s) {
504 if (auto *d = dyn_cast_or_null<Defined>(Val: s))
505 if (d->isec())
506 d->isec()->keepUnique = true;
507}
508
509void macho::markAddrSigSymbols() {
510 TimeTraceScope timeScope("Mark addrsig symbols");
511 for (InputFile *file : inputFiles) {
512 ObjFile *obj = dyn_cast<ObjFile>(Val: file);
513 if (!obj)
514 continue;
515
516 Section *addrSigSection = obj->addrSigSection;
517 if (!addrSigSection)
518 continue;
519 assert(addrSigSection->subsections.size() == 1);
520
521 const InputSection *isec = addrSigSection->subsections[0].isec;
522
523 for (const Relocation &r : isec->relocs) {
524 if (auto *sym = r.referent.dyn_cast<Symbol *>())
525 markSymAsAddrSig(s: sym);
526 else
527 error(msg: toString(isec) + ": unexpected section relocation");
528 }
529 }
530}
531
532// Given a symbol that was folded into a thunk, return the symbol pointing to
533// the actual body of the function. We use this approach rather than storing the
534// needed info in the Defined itself in order to minimize memory usage.
535Defined *macho::getBodyForThunkFoldedSym(Defined *foldedSym) {
536 assert(isa<ConcatInputSection>(foldedSym->originalIsec) &&
537 "thunk-folded ICF symbol expected to be on a ConcatInputSection");
538 // foldedSec is the InputSection that was marked as deleted upon fold
539 ConcatInputSection *foldedSec =
540 cast<ConcatInputSection>(Val: foldedSym->originalIsec);
541
542 // thunkBody is the actual live thunk, containing the code that branches to
543 // the actual body of the function.
544 InputSection *thunkBody = foldedSec->replacement;
545
546 // The symbol of the merged body of the function that the thunk jumps to. This
547 // will end up in the final binary.
548 Symbol *targetSym = target->getThunkBranchTarget(thunk: thunkBody);
549
550 return cast<Defined>(Val: targetSym);
551}
552void macho::foldIdenticalSections(bool onlyCfStrings) {
553 TimeTraceScope timeScope("Fold Identical Code Sections");
554 // The ICF equivalence-class segregation algorithm relies on pre-computed
555 // hashes of InputSection::data for the ConcatOutputSection::inputs and all
556 // sections referenced by their relocs. We could recursively traverse the
557 // relocs to find every referenced InputSection, but that precludes easy
558 // parallelization. Therefore, we hash every InputSection here where we have
559 // them all accessible as simple vectors.
560
561 // If an InputSection is ineligible for ICF, we give it a unique ID to force
562 // it into an unfoldable singleton equivalence class. Begin the unique-ID
563 // space at inputSections.size(), so that it will never intersect with
564 // equivalence-class IDs which begin at 0. Since hashes & unique IDs never
565 // coexist with equivalence-class IDs, this is not necessary, but might help
566 // someone keep the numbers straight in case we ever need to debug the
567 // ICF::segregate()
568 std::vector<ConcatInputSection *> foldable;
569 uint64_t icfUniqueID = inputSections.size();
570 // Reset the thunk counter for each run of ICF.
571 icfThunkCounter = 0;
572 for (ConcatInputSection *isec : inputSections) {
573 bool isFoldableWithAddendsRemoved = isCfStringSection(isec) ||
574 isClassRefsSection(isec) ||
575 isSelRefsSection(isec);
576 // NOTE: __objc_selrefs is typically marked as no_dead_strip by MC, but we
577 // can still fold it.
578 bool hasFoldableFlags = (isSelRefsSection(isec) ||
579 sectionType(flags: isec->getFlags()) == MachO::S_REGULAR);
580
581 bool isCodeSec = isCodeSection(isec);
582
583 // When keepUnique is true, the section is not foldable. Unless we are at
584 // icf level safe_thunks, in which case we still want to fold code sections.
585 // When using safe_thunks we'll apply the safe_thunks logic at merge time
586 // based on the 'keepUnique' flag.
587 bool noUniqueRequirement =
588 !isec->keepUnique ||
589 ((config->icfLevel == ICFLevel::safe_thunks) && isCodeSec);
590
591 // FIXME: consider non-code __text sections as foldable?
592 bool isFoldable = (!onlyCfStrings || isCfStringSection(isec)) &&
593 (isCodeSec || isFoldableWithAddendsRemoved ||
594 isGccExceptTabSection(isec)) &&
595 noUniqueRequirement && !isec->hasAltEntry &&
596 !isec->shouldOmitFromOutput() && hasFoldableFlags;
597 if (isFoldable) {
598 foldable.push_back(x: isec);
599 for (Defined *d : isec->symbols)
600 if (d->unwindEntry())
601 foldable.push_back(x: d->unwindEntry());
602
603 // Some sections have embedded addends that foil ICF's hashing / equality
604 // checks. (We can ignore embedded addends when doing ICF because the same
605 // information gets recorded in our Reloc structs.) We therefore create a
606 // mutable copy of the section data and zero out the embedded addends
607 // before performing any hashing / equality checks.
608 if (isFoldableWithAddendsRemoved) {
609 // We have to do this copying serially as the BumpPtrAllocator is not
610 // thread-safe. FIXME: Make a thread-safe allocator.
611 MutableArrayRef<uint8_t> copy = isec->data.copy(A&: bAlloc());
612 for (const Relocation &r : isec->relocs)
613 target->relocateOne(loc: copy.data() + r.offset, r, /*va=*/0,
614 /*relocVA=*/0);
615 isec->data = copy;
616 }
617 } else if (!isEhFrameSection(isec)) {
618 // EH frames are gathered as foldables from unwindEntry above; give a
619 // unique ID to everything else.
620 isec->icfEqClass[0] = ++icfUniqueID;
621 }
622 }
623 parallelForEach(R&: foldable, Fn: [](ConcatInputSection *isec) {
624 assert(isec->icfEqClass[0] == 0); // don't overwrite a unique ID!
625 // Turn-on the top bit to guarantee that valid hashes have no collisions
626 // with the small-integer unique IDs for ICF-ineligible sections
627 isec->icfEqClass[0] = xxh3_64bits(data: isec->data) | (1ull << 31);
628 });
629 // Now that every input section is either hashed or marked as unique, run the
630 // segregation algorithm to detect foldable subsections.
631 ICF(foldable).run();
632}
633