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// ICF is short for Identical Code Folding. This is a size optimization to
10// identify and merge two or more read-only sections (typically functions)
11// that happened to have the same contents. It usually reduces output size
12// by a few percent.
13//
14// In ICF, two sections are considered identical if they have the same
15// section flags, section data, and relocations. Relocations are tricky,
16// because two relocations are considered the same if they have the same
17// relocation types, values, and if they point to the same sections *in
18// terms of ICF*.
19//
20// Here is an example. If foo and bar defined below are compiled to the
21// same machine instructions, ICF can and should merge the two, although
22// their relocations point to each other.
23//
24// void foo() { bar(); }
25// void bar() { foo(); }
26//
27// If you merge the two, their relocations point to the same section and
28// thus you know they are mergeable, but how do you know they are
29// mergeable in the first place? This is not an easy problem to solve.
30//
31// What we are doing in LLD is to partition sections into equivalence
32// classes. Sections in the same equivalence class when the algorithm
33// terminates are considered identical. Here are details:
34//
35// 1. First, we partition sections using their hash values as keys. The hash
36// covers section contents and relocations. A relocation to another ICF
37// candidate contributes the target's hash, propagated for a few rounds,
38// so the hash also covers sections a few relocation hops away.
39//
40// 2. Next, we split each equivalence class by comparing everything except
41// relocation targets (equalsConstant). These properties never change, so
42// this step runs once.
43//
44// 3. Then we split classes by comparing relocation targets (equalsVariable),
45// which are considered equivalent if they are in the same equivalence
46// class. A split may make two relocations that targeted the same class
47// target different classes, so we repeat this step until no class splits.
48//
49// 4. For each equivalence class C, pick an arbitrary section in C, and
50// merge all the other sections in C with it.
51//
52// Step 1 must give identical sections the same hash. A collision only costs
53// step 2 time, and the more relocation hops step 1 covers, the fewer
54// iterations step 3 needs.
55//
56// We parallelize each step so that multiple threads can work on different
57// equivalence classes concurrently.
58//
59//===----------------------------------------------------------------------===//
60
61#include "ICF.h"
62#include "Config.h"
63#include "InputFiles.h"
64#include "LinkerScript.h"
65#include "OutputSections.h"
66#include "SymbolTable.h"
67#include "Symbols.h"
68#include "SyntheticSections.h"
69#include "llvm/BinaryFormat/ELF.h"
70#include "llvm/Support/Parallel.h"
71#include "llvm/Support/TimeProfiler.h"
72#include "llvm/Support/xxhash.h"
73#include <algorithm>
74#include <atomic>
75
76using namespace llvm;
77using namespace llvm::ELF;
78using namespace llvm::object;
79using namespace lld;
80using namespace lld::elf;
81
82namespace {
83template <class ELFT> class ICF {
84public:
85 ICF(Ctx &ctx) : ctx(ctx) {}
86 void run();
87
88private:
89 void segregate(size_t begin, size_t end, uint32_t eqClassBase, bool constant);
90
91 template <class RelTy>
92 bool constantEq(const InputSection *a, Relocs<RelTy> relsA,
93 const InputSection *b, Relocs<RelTy> relsB);
94
95 template <class RelTy>
96 void hashRelocs(const InputSection &sec, uint64_t &h,
97 SmallVectorImpl<uint32_t> &edges, uint32_t eqClassBase,
98 Relocs<RelTy> rels);
99
100 template <class RelTy>
101 bool variableEq(const InputSection *a, Relocs<RelTy> relsA,
102 const InputSection *b, Relocs<RelTy> relsB);
103
104 bool equalsConstant(const InputSection *a, const InputSection *b);
105 bool equalsVariable(const InputSection *a, const InputSection *b);
106
107 size_t findBoundary(size_t begin, size_t end);
108
109 void forEachClassRange(size_t begin, size_t end,
110 llvm::function_ref<void(size_t, size_t)> fn);
111
112 void parallelForEachClass(llvm::function_ref<void(size_t, size_t)> fn);
113
114 Ctx &ctx;
115 SmallVector<InputSection *, 0> sections;
116
117 // We repeat the main loop while `Repeat` is true.
118 std::atomic<bool> repeat;
119
120 // The main loop counter.
121 int cnt = 0;
122
123 // We have two locations for equivalence classes. On the first iteration
124 // of the main loop, Class[0] has a valid value, and Class[1] contains
125 // garbage. We read equivalence classes from slot 0 and write to slot 1.
126 // So, Class[0] represents the current class, and Class[1] represents
127 // the next class. On each iteration, we switch their roles and use them
128 // alternately.
129 //
130 // Why are we doing this? Recall that other threads may be working on
131 // other equivalence classes in parallel. They may read sections that we
132 // are updating. We cannot update equivalence classes in place because
133 // it breaks the invariance that all possibly-identical sections must be
134 // in the same equivalence class at any moment. In other words, the for
135 // loop to update equivalence classes is not atomic, and that is
136 // observable from other threads. By writing new classes to other
137 // places, we can keep the invariance.
138 //
139 // Below, `Current` has the index of the current class, and `Next` has
140 // the index of the next class. If threading is enabled, they are either
141 // (0, 1) or (1, 0).
142 //
143 // Note on single-thread: if that's the case, they are always (0, 0)
144 // because we can safely read the next class without worrying about race
145 // conditions. Using the same location makes this algorithm converge
146 // faster because it uses results of the same iteration earlier.
147 int current = 0;
148 int next = 0;
149};
150} // namespace
151
152// Returns true if section S is subject of ICF.
153static bool isEligible(InputSection *s) {
154 if (!s->isLive() || s->keepUnique || !(s->flags & SHF_ALLOC))
155 return false;
156
157 // Don't merge writable sections. .data.rel.ro sections are marked as writable
158 // but are semantically read-only.
159 if ((s->flags & SHF_WRITE) && s->name != ".data.rel.ro" &&
160 !s->name.starts_with(Prefix: ".data.rel.ro."))
161 return false;
162
163 // SHF_LINK_ORDER sections are ICF'd as a unit with their dependent sections,
164 // so we don't consider them for ICF individually.
165 if (s->flags & SHF_LINK_ORDER)
166 return false;
167
168 // Don't merge synthetic sections as their Data member is not valid and empty.
169 // The Data member needs to be valid for ICF as it is used by ICF to determine
170 // the equality of section contents.
171 if (isa<SyntheticSection>(Val: s))
172 return false;
173
174 // .init and .fini contains instructions that must be executed to initialize
175 // and finalize the process. They cannot and should not be merged.
176 if (s->name == ".init" || s->name == ".fini")
177 return false;
178
179 // A user program may enumerate sections named with a C identifier using
180 // __start_* and __stop_* symbols. We cannot ICF any such sections because
181 // that could change program semantics.
182 if (isValidCIdentifier(s: s->name))
183 return false;
184
185 return true;
186}
187
188// Split an equivalence class into smaller classes.
189template <class ELFT>
190void ICF<ELFT>::segregate(size_t begin, size_t end, uint32_t eqClassBase,
191 bool constant) {
192 // This loop rearranges sections in [Begin, End) so that all sections
193 // that are equal in terms of equals{Constant,Variable} are contiguous
194 // in [Begin, End).
195 //
196 // The algorithm is quadratic in the worst case, but that is not an
197 // issue in practice because the number of the distinct sections in
198 // each range is usually very small.
199
200 while (begin < end) {
201 // Divide [Begin, End) into two. Let Mid be the start index of the
202 // second group.
203 auto bound =
204 std::stable_partition(sections.begin() + begin + 1,
205 sections.begin() + end, [&](InputSection *s) {
206 if (constant)
207 return equalsConstant(a: sections[begin], b: s);
208 return equalsVariable(a: sections[begin], b: s);
209 });
210 size_t mid = bound - sections.begin();
211
212 // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
213 // updating the sections in [Begin, Mid). We use Mid as the basis for
214 // the equivalence class ID because every group ends with a unique index.
215 // Add this to eqClassBase to avoid equality with unique IDs.
216 for (size_t i = begin; i < mid; ++i)
217 sections[i]->eqClass[next] = eqClassBase + mid;
218
219 // If we created a group, we need to iterate the main loop again.
220 if (mid != end)
221 repeat = true;
222
223 begin = mid;
224 }
225}
226
227// Propagation mixes a self-referencing section's hash with itself, so mix(h, h)
228// must not be a constant.
229static uint64_t mix(uint64_t h, uint64_t v) {
230 return (h + v) * 0x9e3779b97f4a7c15;
231}
232
233// Different symbols compare equal only if both values are final: not a linker
234// script placeholder (assigned later) and not preemptible.
235static Defined *getComparableDef(Symbol &sym) {
236 auto *d = dyn_cast<Defined>(Val: &sym);
237 return d && !d->scriptDefined && !d->isPreemptible ? d : nullptr;
238}
239
240// A section symbol's addend is not validated until getSymVA. Return nullopt
241// to conservatively disable folding for such an out-of-range offset.
242static std::optional<uint64_t> getMergeOffset(const Defined &d,
243 uint64_t addend) {
244 auto &ms = cast<MergeInputSection>(Val&: *d.section);
245 if (!d.isSection())
246 return ms.getOffset(offset: d.value) + addend;
247 if (addend >= ms.content().size())
248 return std::nullopt;
249 return ms.getOffset(offset: addend);
250}
251
252// Compare two lists of relocations.
253template <class ELFT>
254template <class RelTy>
255bool ICF<ELFT>::constantEq(const InputSection *secA, Relocs<RelTy> ra,
256 const InputSection *secB, Relocs<RelTy> rb) {
257 if (ra.size() != rb.size())
258 return false;
259 auto rai = ra.begin(), rae = ra.end(), rbi = rb.begin();
260 for (; rai != rae; ++rai, ++rbi) {
261 if (rai->r_offset != rbi->r_offset ||
262 rai->getType(ctx.arg.isMips64EL) != rbi->getType(ctx.arg.isMips64EL))
263 return false;
264
265 uint64_t addA = getAddend<ELFT>(*rai);
266 uint64_t addB = getAddend<ELFT>(*rbi);
267
268 Symbol &sa = secA->file->getRelocTargetSym(*rai);
269 Symbol &sb = secB->file->getRelocTargetSym(*rbi);
270 if (&sa == &sb && addA == addB)
271 continue;
272
273 Defined *da = getComparableDef(sym&: sa), *db = getComparableDef(sym&: sb);
274 if (!da || !db)
275 return false;
276
277 // Relocations referring to absolute symbols are constant-equal if their
278 // values are equal.
279 if (!da->section && !db->section && da->value + addA == db->value + addB)
280 continue;
281 if (!da->section || !db->section)
282 return false;
283
284 if (da->section->kind() != db->section->kind())
285 return false;
286
287 // Relocations referring to InputSections are constant-equal if their
288 // section offsets are equal.
289 if (isa<InputSection>(Val: da->section)) {
290 if (da->value + addA == db->value + addB)
291 continue;
292 return false;
293 }
294
295 // Relocations referring to MergeInputSections are constant-equal if their
296 // offsets in the output section are equal.
297 auto *x = dyn_cast<MergeInputSection>(Val: da->section);
298 if (!x)
299 return false;
300 auto *y = cast<MergeInputSection>(Val: db->section);
301 if (x->getParent() != y->getParent())
302 return false;
303
304 auto offA = getMergeOffset(d: *da, addend: addA);
305 if (!offA || offA != getMergeOffset(d: *db, addend: addB))
306 return false;
307 }
308
309 return true;
310}
311
312// Hash what constantEq compares, plus the class of a non-candidate target,
313// which never changes. Candidate targets are recorded as edges instead.
314template <class ELFT>
315template <class RelTy>
316void ICF<ELFT>::hashRelocs(const InputSection &sec, uint64_t &h,
317 SmallVectorImpl<uint32_t> &edges,
318 uint32_t eqClassBase, Relocs<RelTy> rels) {
319 for (const RelTy &rel : rels) {
320 h = mix(h, rel.r_offset);
321 h = mix(h, rel.getType(ctx.arg.isMips64EL));
322 uint64_t addend = getAddend<ELFT>(rel);
323 Symbol &sym = sec.file->getRelocTargetSym(rel);
324 Defined *d = getComparableDef(sym);
325 if (!d) {
326 h = mix(h, v: xxh3_64bits(data: sym.getName()));
327 h = mix(h, v: addend);
328 continue;
329 }
330 if (isa_and_nonnull<MergeInputSection>(Val: d->section)) {
331 h = mix(h, v: getMergeOffset(d: *d, addend).value_or(u: -1));
332 continue;
333 }
334 h = mix(h, v: d->value + addend);
335 auto *is = dyn_cast_or_null<InputSection>(Val: d->section);
336 if (!is)
337 continue;
338 // A candidate's eqClass[0] - eqClassBase is its index in sections.
339 if (is->eqClass[0] >= eqClassBase)
340 edges.push_back(Elt: is->eqClass[0] - eqClassBase);
341 else
342 h = mix(h, v: is->eqClass[0]);
343 }
344}
345
346// Compare "non-moving" part of two InputSections, namely everything
347// except relocation targets.
348template <class ELFT>
349bool ICF<ELFT>::equalsConstant(const InputSection *a, const InputSection *b) {
350 if (a->flags != b->flags || a->content() != b->content())
351 return false;
352
353 // If two sections have different output sections, we cannot merge them.
354 assert(a->getParent() && b->getParent());
355 if (a->getParent() != b->getParent())
356 return false;
357
358 const RelsOrRelas<ELFT> ra = a->template relsOrRelas<ELFT>();
359 const RelsOrRelas<ELFT> rb = b->template relsOrRelas<ELFT>();
360 if (ra.areRelocsCrel() || rb.areRelocsCrel())
361 return constantEq(a, ra.crels, b, rb.crels);
362 return ra.areRelocsRel() || rb.areRelocsRel()
363 ? constantEq(a, ra.rels, b, rb.rels)
364 : constantEq(a, ra.relas, b, rb.relas);
365}
366
367// Compare two lists of relocations. Returns true if all pairs of
368// relocations point to the same section in terms of ICF.
369template <class ELFT>
370template <class RelTy>
371bool ICF<ELFT>::variableEq(const InputSection *secA, Relocs<RelTy> ra,
372 const InputSection *secB, Relocs<RelTy> rb) {
373 assert(ra.size() == rb.size());
374
375 auto rai = ra.begin(), rae = ra.end(), rbi = rb.begin();
376 for (; rai != rae; ++rai, ++rbi) {
377 // The two sections must be identical.
378 Symbol &sa = secA->file->getRelocTargetSym(*rai);
379 Symbol &sb = secB->file->getRelocTargetSym(*rbi);
380 if (&sa == &sb)
381 continue;
382
383 auto *da = cast<Defined>(Val: &sa);
384 auto *db = cast<Defined>(Val: &sb);
385
386 // We already dealt with absolute and non-InputSection symbols in
387 // constantEq, and for InputSections we have already checked everything
388 // except the equivalence class.
389 auto *x = dyn_cast_or_null<InputSection>(Val: da->section);
390 if (!x)
391 continue;
392 auto *y = cast<InputSection>(Val: db->section);
393
394 // Sections that are in the special equivalence class 0, can never be the
395 // same in terms of the equivalence class.
396 if (x->eqClass[current] == 0)
397 return false;
398 if (x->eqClass[current] != y->eqClass[current])
399 return false;
400 }
401
402 return true;
403}
404
405// Compare "moving" part of two InputSections, namely relocation targets.
406template <class ELFT>
407bool ICF<ELFT>::equalsVariable(const InputSection *a, const InputSection *b) {
408 const RelsOrRelas<ELFT> ra = a->template relsOrRelas<ELFT>();
409 const RelsOrRelas<ELFT> rb = b->template relsOrRelas<ELFT>();
410 if (ra.areRelocsCrel() || rb.areRelocsCrel())
411 return variableEq(a, ra.crels, b, rb.crels);
412 return ra.areRelocsRel() || rb.areRelocsRel()
413 ? variableEq(a, ra.rels, b, rb.rels)
414 : variableEq(a, ra.relas, b, rb.relas);
415}
416
417template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t begin, size_t end) {
418 uint32_t eqClass = sections[begin]->eqClass[current];
419 for (size_t i = begin + 1; i < end; ++i)
420 if (eqClass != sections[i]->eqClass[current])
421 return i;
422 return end;
423}
424
425// Sections in the same equivalence class are contiguous in Sections
426// vector. Therefore, Sections vector can be considered as contiguous
427// groups of sections, grouped by the class.
428//
429// This function calls Fn on every group within [Begin, End).
430template <class ELFT>
431void ICF<ELFT>::forEachClassRange(size_t begin, size_t end,
432 llvm::function_ref<void(size_t, size_t)> fn) {
433 while (begin < end) {
434 size_t mid = findBoundary(begin, end);
435 fn(begin, mid);
436 begin = mid;
437 }
438}
439
440// Call Fn on each equivalence class.
441
442template <class ELFT>
443void ICF<ELFT>::parallelForEachClass(
444 llvm::function_ref<void(size_t, size_t)> fn) {
445 // If threading is disabled or the number of sections are
446 // too small to use threading, call Fn sequentially.
447 if (parallel::strategy.ThreadsRequested == 1 || sections.size() < 1024) {
448 forEachClassRange(begin: 0, end: sections.size(), fn);
449 ++cnt;
450 return;
451 }
452
453 current = cnt % 2;
454 next = (cnt + 1) % 2;
455
456 // Shard into non-overlapping intervals, and call Fn in parallel.
457 // The sharding must be completed before any calls to Fn are made
458 // so that Fn can modify the Chunks in its shard without causing data
459 // races.
460 const size_t numShards = 256;
461 size_t step = sections.size() / numShards;
462 size_t boundaries[numShards + 1];
463 boundaries[0] = 0;
464 boundaries[numShards] = sections.size();
465
466 parallelFor(1, numShards, [&](size_t i) {
467 boundaries[i] = findBoundary(begin: (i - 1) * step, end: sections.size());
468 });
469
470 parallelFor(1, numShards + 1, [&](size_t i) {
471 if (boundaries[i - 1] < boundaries[i])
472 forEachClassRange(begin: boundaries[i - 1], end: boundaries[i], fn);
473 });
474 ++cnt;
475}
476
477// The main function of ICF.
478template <class ELFT> void ICF<ELFT>::run() {
479 // Two text sections may have identical content and relocations but different
480 // LSDA, e.g. the two functions may have catch blocks of different types. If a
481 // text section is referenced by a .eh_frame FDE with LSDA, it is not
482 // eligible. This is implemented by iterating over CIE/FDE and setting
483 // eqClass[0] to the referenced text section from a live FDE.
484 //
485 // If two .gcc_except_table have identical semantics (usually identical
486 // content with PC-relative encoding), we will lose folding opportunity.
487 uint32_t uniqueId = 1;
488 ctx.in.ehFrame->iterateFDEWithLSDA(
489 fn: [&](InputSection &s) { s.eqClass[0] = s.eqClass[1] = uniqueId++; });
490
491 // Assign a temporary class ID (eqClassBase) to eligible sections and assign
492 // unique IDs to ineligible sections. Use eqClassBase as the base for class
493 // IDs. Each ineligible section belongs to an equivalence class of its own.
494 constexpr size_t chunkSize = 1024;
495 ArrayRef<InputSectionBase *> inputs = ctx.inputSections;
496 size_t numInputChunks = divideCeil(Numerator: inputs.size(), Denominator: chunkSize);
497 auto chunkRange = [&](size_t c, size_t total) {
498 auto begin = c * chunkSize;
499 return std::make_pair(x&: begin, y: std::min(a: begin + chunkSize, b: total));
500 };
501 uint32_t eqClassBase = uniqueId + inputs.size();
502 SmallVector<uint32_t, 0> firstIdx(numInputChunks);
503 parallelFor(0, numInputChunks, [&](size_t c) {
504 auto [begin, end] = chunkRange(c, inputs.size());
505 uint32_t n = 0;
506 for (size_t i = begin; i != end; ++i) {
507 auto *s = dyn_cast<InputSection>(Val: inputs[i]);
508 if (s && s->eqClass[0] == 0) {
509 if (isEligible(s)) {
510 s->eqClass[0] = eqClassBase;
511 ++n;
512 } else {
513 s->eqClass[0] = s->eqClass[1] = uniqueId + i;
514 }
515 }
516 }
517 // Temporarily store the number of sections per chunk.
518 firstIdx[c] = n;
519 });
520
521 // Compute the total number of eligible sections and each chunk's left index.
522 size_t numSections = 0;
523 for (size_t c = 0; c != numInputChunks; ++c) {
524 auto n = std::exchange(obj&: firstIdx[c], new_val&: numSections);
525 numSections += n;
526 }
527 sections.resize_for_overwrite(N: numSections);
528 // Update temporary class ID above the unique IDs so that hashRelocs() can
529 // tell them apart.
530 assert(uint64_t(eqClassBase) + numSections <= UINT32_MAX);
531 parallelFor(0, numInputChunks, [&](size_t c) {
532 auto [begin, end] = chunkRange(c, inputs.size());
533 auto idx = firstIdx[c];
534 for (size_t i = begin; i != end; ++i) {
535 auto *s = dyn_cast<InputSection>(Val: inputs[i]);
536 if (s && s->eqClass[0] == eqClassBase) {
537 s->eqClass[0] += idx;
538 sections[idx++] = s;
539 }
540 }
541 });
542
543 // Hash sections in chunks. An edge is a relocation to a candidate, recorded
544 // as the target's index. Each chunk appends its sections' edges to its own
545 // buffer; edgeEnd[i] is where section i's edges end within that buffer.
546 size_t numChunks = divideCeil(Numerator: numSections, Denominator: chunkSize);
547 SmallVector<uint64_t, 0> hashes(numSections, llvm::for_overwrite);
548 SmallVector<uint32_t, 0> edgeEnd(numSections, llvm::for_overwrite);
549 SmallVector<SmallVector<uint32_t, 0>, 0> chunkEdges(numChunks);
550 parallelFor(0, numChunks, [&](size_t c) {
551 SmallVectorImpl<uint32_t> &edges = chunkEdges[c];
552 auto [begin, end] = chunkRange(c, numSections);
553 for (size_t i = begin; i != end; ++i) {
554 InputSection *s = sections[i];
555 uint64_t h = xxh3_64bits(data: s->content());
556 invokeOnRelocs(*s, hashRelocs, *s, h, edges, eqClassBase);
557 hashes[i] = h;
558 edgeEnd[i] = edges.size();
559 }
560 });
561
562 // Propagate hashes over edges for 7 rounds. Each round saves up to one
563 // segregate() pass. 7 is empirical: even Chromium then needs just two passes.
564 SmallVector<uint64_t, 0> nextHashes(numSections, llvm::for_overwrite);
565 for (int round = 7; round--;) {
566 parallelFor(0, numChunks, [&](size_t c) {
567 ArrayRef<uint32_t> edges = chunkEdges[c];
568 auto [begin, end] = chunkRange(c, numSections);
569 size_t j = 0;
570 for (size_t i = begin; i != end; ++i) {
571 uint64_t h = hashes[i];
572 for (size_t e = edgeEnd[i]; j != e; ++j)
573 h = mix(h, v: hashes[edges[j]]);
574 nextHashes[i] = h;
575 }
576 });
577 std::swap(LHS&: hashes, RHS&: nextHashes);
578 }
579
580 // Order sections so that those in the same equivalence class are consecutive.
581 SmallVector<uint64_t, 0> keys(numSections, llvm::for_overwrite);
582 parallelFor(0, numSections, [&](size_t i) {
583 // mix()'s low bits depend only on the inputs' low bits. Fold the high half.
584 uint32_t h = hashes[i] ^ hashes[i] >> 32;
585 sections[i]->eqClass[0] = h;
586 keys[i] = uint64_t(h) << 32 | i;
587 });
588 parallelSort(Start: keys.begin(), End: keys.end());
589 SmallVector<InputSection *, 0> sorted(numSections, llvm::for_overwrite);
590 parallelFor(0, numSections,
591 [&](size_t i) { sorted[i] = sections[uint32_t(keys[i])]; });
592 sections = std::move(sorted);
593
594 // Compare static contents and assign unique equivalence class IDs for each
595 // static content. Use a base offset for these IDs to ensure no overlap with
596 // the unique IDs already assigned.
597 parallelForEachClass(fn: [&](size_t begin, size_t end) {
598 segregate(begin, end, eqClassBase, constant: true);
599 });
600
601 // Split groups by comparing relocations until convergence is obtained.
602 do {
603 repeat = false;
604 parallelForEachClass(fn: [&](size_t begin, size_t end) {
605 segregate(begin, end, eqClassBase, constant: false);
606 });
607 } while (repeat);
608
609 Log(ctx) << "ICF needed " << cnt << " iterations";
610
611 // Merge sections by the equivalence class.
612 parallelForEachClass(fn: [&](size_t begin, size_t end) {
613 for (size_t i = begin + 1; i < end; ++i) {
614 sections[begin]->replace(other: sections[i]);
615
616 // At this point we know sections merged are fully identical and hence
617 // we want to remove duplicate implicit dependencies such as link order
618 // and relocation sections.
619 for (InputSection *isec : sections[i]->dependentSections)
620 isec->markDead();
621 }
622 });
623
624 // Print classes in input order, independent of the hash.
625 if (ctx.arg.printIcfSections) {
626 DenseMap<InputSection *, SmallVector<InputSection *, 0>> folded;
627 for (InputSectionBase *sec : ctx.inputSections)
628 if (auto *s = dyn_cast<InputSection>(Val: sec); s && s->repl != s)
629 folded[s->repl].push_back(Elt: s);
630 for (InputSectionBase *sec : ctx.inputSections) {
631 auto it = folded.find(Val: dyn_cast<InputSection>(Val: sec));
632 if (it == folded.end())
633 continue;
634 Msg(ctx) << "selected section " << sec;
635 for (InputSection *s : it->second)
636 Msg(ctx) << " removing identical section " << s;
637 }
638 }
639
640 // Change Defined symbol's section field to the canonical one.
641 auto fold = [](Symbol *sym) {
642 if (auto *d = dyn_cast<Defined>(Val: sym))
643 if (auto *sec = dyn_cast_or_null<InputSection>(Val: d->section))
644 if (sec->repl != d->section) {
645 d->section = sec->repl;
646 d->folded = true;
647 }
648 };
649 parallelForEach(ctx.symtab->getSymbols(), fold);
650 parallelForEach(ctx.objectFiles, [&](ELFFileBase *file) {
651 for (Symbol *sym : file->getLocalSymbols())
652 fold(sym);
653 });
654
655 // InputSectionDescription::sections is populated by processSectionCommands().
656 // ICF may fold some input sections assigned to output sections. Remove them.
657 for (SectionCommand *cmd : ctx.script->sectionCommands)
658 if (auto *osd = dyn_cast<OutputDesc>(Val: cmd))
659 for (SectionCommand *subCmd : osd->osec.commands)
660 if (auto *isd = dyn_cast<InputSectionDescription>(Val: subCmd))
661 llvm::erase_if(isd->sections,
662 [](InputSection *isec) { return !isec->isLive(); });
663}
664
665// ICF entry point function.
666template <class ELFT> void elf::doIcf(Ctx &ctx) {
667 llvm::TimeTraceScope timeScope("ICF");
668 ICF<ELFT>(ctx).run();
669}
670
671template void elf::doIcf<ELF32LE>(Ctx &);
672template void elf::doIcf<ELF32BE>(Ctx &);
673template void elf::doIcf<ELF64LE>(Ctx &);
674template void elf::doIcf<ELF64BE>(Ctx &);
675