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. Hash
36// values contain section types, section contents and numbers of
37// relocations. During this step, relocation targets are not taken into
38// account. We just put sections that apparently differ into different
39// equivalence classes.
40//
41// 2. Next, for each equivalence class, we visit sections to compare
42// relocation targets. Relocation targets are considered equivalent if
43// their targets are in the same equivalence class. Sections with
44// different relocation targets are put into different equivalence
45// classes.
46//
47// 3. If we split an equivalence class in step 2, two relocations
48// previously target the same equivalence class may now target
49// different equivalence classes. Therefore, we repeat step 2 until a
50// convergence is obtained.
51//
52// 4. For each equivalence class C, pick an arbitrary section in C, and
53// merge all the other sections in C with it.
54//
55// For small programs, this algorithm needs 3-5 iterations. For large
56// programs such as Chromium, it takes more than 20 iterations.
57//
58// This algorithm was mentioned as an "optimistic algorithm" in [1],
59// though gold implements a different algorithm than this.
60//
61// We parallelize each step so that multiple threads can work on different
62// equivalence classes concurrently. That gave us a large performance
63// boost when applying ICF on large programs. For example, MSVC link.exe
64// or GNU gold takes 10-20 seconds to apply ICF on Chromium, whose output
65// size is about 1.5 GB, but LLD can finish it in less than 2 seconds on a
66// 2.8 GHz 40 core machine. Even without threading, LLD's ICF is still
67// faster than MSVC or gold though.
68//
69// [1] Safe ICF: Pointer Safe and Unwinding aware Identical Code Folding
70// in the Gold Linker
71// http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/36912.pdf
72//
73//===----------------------------------------------------------------------===//
74
75#include "ICF.h"
76#include "Config.h"
77#include "InputFiles.h"
78#include "LinkerScript.h"
79#include "OutputSections.h"
80#include "SymbolTable.h"
81#include "Symbols.h"
82#include "SyntheticSections.h"
83#include "llvm/BinaryFormat/ELF.h"
84#include "llvm/Support/Parallel.h"
85#include "llvm/Support/TimeProfiler.h"
86#include "llvm/Support/xxhash.h"
87#include <algorithm>
88#include <atomic>
89
90using namespace llvm;
91using namespace llvm::ELF;
92using namespace llvm::object;
93using namespace lld;
94using namespace lld::elf;
95
96namespace {
97template <class ELFT> class ICF {
98public:
99 ICF(Ctx &ctx) : ctx(ctx) {}
100 void run();
101
102private:
103 void segregate(size_t begin, size_t end, uint32_t eqClassBase, bool constant);
104
105 template <class RelTy>
106 bool constantEq(const InputSection *a, Relocs<RelTy> relsA,
107 const InputSection *b, Relocs<RelTy> relsB);
108
109 template <class RelTy>
110 bool variableEq(const InputSection *a, Relocs<RelTy> relsA,
111 const InputSection *b, Relocs<RelTy> relsB);
112
113 bool equalsConstant(const InputSection *a, const InputSection *b);
114 bool equalsVariable(const InputSection *a, const InputSection *b);
115
116 size_t findBoundary(size_t begin, size_t end);
117
118 void forEachClassRange(size_t begin, size_t end,
119 llvm::function_ref<void(size_t, size_t)> fn);
120
121 void parallelForEachClass(llvm::function_ref<void(size_t, size_t)> fn);
122
123 Ctx &ctx;
124 SmallVector<InputSection *, 0> sections;
125
126 // We repeat the main loop while `Repeat` is true.
127 std::atomic<bool> repeat;
128
129 // The main loop counter.
130 int cnt = 0;
131
132 // We have two locations for equivalence classes. On the first iteration
133 // of the main loop, Class[0] has a valid value, and Class[1] contains
134 // garbage. We read equivalence classes from slot 0 and write to slot 1.
135 // So, Class[0] represents the current class, and Class[1] represents
136 // the next class. On each iteration, we switch their roles and use them
137 // alternately.
138 //
139 // Why are we doing this? Recall that other threads may be working on
140 // other equivalence classes in parallel. They may read sections that we
141 // are updating. We cannot update equivalence classes in place because
142 // it breaks the invariance that all possibly-identical sections must be
143 // in the same equivalence class at any moment. In other words, the for
144 // loop to update equivalence classes is not atomic, and that is
145 // observable from other threads. By writing new classes to other
146 // places, we can keep the invariance.
147 //
148 // Below, `Current` has the index of the current class, and `Next` has
149 // the index of the next class. If threading is enabled, they are either
150 // (0, 1) or (1, 0).
151 //
152 // Note on single-thread: if that's the case, they are always (0, 0)
153 // because we can safely read the next class without worrying about race
154 // conditions. Using the same location makes this algorithm converge
155 // faster because it uses results of the same iteration earlier.
156 int current = 0;
157 int next = 0;
158};
159}
160
161// Returns true if section S is subject of ICF.
162static bool isEligible(InputSection *s) {
163 if (!s->isLive() || s->keepUnique || !(s->flags & SHF_ALLOC))
164 return false;
165
166 // Don't merge writable sections. .data.rel.ro sections are marked as writable
167 // but are semantically read-only.
168 if ((s->flags & SHF_WRITE) && s->name != ".data.rel.ro" &&
169 !s->name.starts_with(Prefix: ".data.rel.ro."))
170 return false;
171
172 // SHF_LINK_ORDER sections are ICF'd as a unit with their dependent sections,
173 // so we don't consider them for ICF individually.
174 if (s->flags & SHF_LINK_ORDER)
175 return false;
176
177 // Don't merge synthetic sections as their Data member is not valid and empty.
178 // The Data member needs to be valid for ICF as it is used by ICF to determine
179 // the equality of section contents.
180 if (isa<SyntheticSection>(Val: s))
181 return false;
182
183 // .init and .fini contains instructions that must be executed to initialize
184 // and finalize the process. They cannot and should not be merged.
185 if (s->name == ".init" || s->name == ".fini")
186 return false;
187
188 // A user program may enumerate sections named with a C identifier using
189 // __start_* and __stop_* symbols. We cannot ICF any such sections because
190 // that could change program semantics.
191 if (isValidCIdentifier(s: s->name))
192 return false;
193
194 return true;
195}
196
197// Split an equivalence class into smaller classes.
198template <class ELFT>
199void ICF<ELFT>::segregate(size_t begin, size_t end, uint32_t eqClassBase,
200 bool constant) {
201 // This loop rearranges sections in [Begin, End) so that all sections
202 // that are equal in terms of equals{Constant,Variable} are contiguous
203 // in [Begin, End).
204 //
205 // The algorithm is quadratic in the worst case, but that is not an
206 // issue in practice because the number of the distinct sections in
207 // each range is usually very small.
208
209 while (begin < end) {
210 // Divide [Begin, End) into two. Let Mid be the start index of the
211 // second group.
212 auto bound =
213 std::stable_partition(sections.begin() + begin + 1,
214 sections.begin() + end, [&](InputSection *s) {
215 if (constant)
216 return equalsConstant(a: sections[begin], b: s);
217 return equalsVariable(a: sections[begin], b: s);
218 });
219 size_t mid = bound - sections.begin();
220
221 // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
222 // updating the sections in [Begin, Mid). We use Mid as the basis for
223 // the equivalence class ID because every group ends with a unique index.
224 // Add this to eqClassBase to avoid equality with unique IDs.
225 for (size_t i = begin; i < mid; ++i)
226 sections[i]->eqClass[next] = eqClassBase + mid;
227
228 // If we created a group, we need to iterate the main loop again.
229 if (mid != end)
230 repeat = true;
231
232 begin = mid;
233 }
234}
235
236// A section symbol's addend is not validated until getSymVA. Return nullopt
237// to conservatively disable folding for such an out-of-range offset.
238static std::optional<uint64_t> getMergeOffset(const Defined &d,
239 uint64_t addend) {
240 auto &ms = cast<MergeInputSection>(Val&: *d.section);
241 if (!d.isSection())
242 return ms.getOffset(offset: d.value) + addend;
243 if (addend >= ms.content().size())
244 return std::nullopt;
245 return ms.getOffset(offset: addend);
246}
247
248// Compare two lists of relocations.
249template <class ELFT>
250template <class RelTy>
251bool ICF<ELFT>::constantEq(const InputSection *secA, Relocs<RelTy> ra,
252 const InputSection *secB, Relocs<RelTy> rb) {
253 if (ra.size() != rb.size())
254 return false;
255 auto rai = ra.begin(), rae = ra.end(), rbi = rb.begin();
256 for (; rai != rae; ++rai, ++rbi) {
257 if (rai->r_offset != rbi->r_offset ||
258 rai->getType(ctx.arg.isMips64EL) != rbi->getType(ctx.arg.isMips64EL))
259 return false;
260
261 uint64_t addA = getAddend<ELFT>(*rai);
262 uint64_t addB = getAddend<ELFT>(*rbi);
263
264 Symbol &sa = secA->file->getRelocTargetSym(*rai);
265 Symbol &sb = secB->file->getRelocTargetSym(*rbi);
266 if (&sa == &sb && addA == addB)
267 continue;
268
269 auto *da = dyn_cast<Defined>(Val: &sa);
270 auto *db = dyn_cast<Defined>(Val: &sb);
271
272 // Placeholder symbols generated by linker scripts look the same now but
273 // may have different values later.
274 if (!da || !db || da->scriptDefined || db->scriptDefined)
275 return false;
276
277 // When comparing a pair of relocations, if they refer to different symbols,
278 // and either symbol is preemptible, the containing sections should be
279 // considered different. This is because even if the sections are identical
280 // in this DSO, they may not be after preemption.
281 if (da->isPreemptible || db->isPreemptible)
282 return false;
283
284 // Relocations referring to absolute symbols are constant-equal if their
285 // values are equal.
286 if (!da->section && !db->section && da->value + addA == db->value + addB)
287 continue;
288 if (!da->section || !db->section)
289 return false;
290
291 if (da->section->kind() != db->section->kind())
292 return false;
293
294 // Relocations referring to InputSections are constant-equal if their
295 // section offsets are equal.
296 if (isa<InputSection>(Val: da->section)) {
297 if (da->value + addA == db->value + addB)
298 continue;
299 return false;
300 }
301
302 // Relocations referring to MergeInputSections are constant-equal if their
303 // offsets in the output section are equal.
304 auto *x = dyn_cast<MergeInputSection>(Val: da->section);
305 if (!x)
306 return false;
307 auto *y = cast<MergeInputSection>(Val: db->section);
308 if (x->getParent() != y->getParent())
309 return false;
310
311 auto offA = getMergeOffset(d: *da, addend: addA);
312 if (!offA || offA != getMergeOffset(d: *db, addend: addB))
313 return false;
314 }
315
316 return true;
317}
318
319// Compare "non-moving" part of two InputSections, namely everything
320// except relocation targets.
321template <class ELFT>
322bool ICF<ELFT>::equalsConstant(const InputSection *a, const InputSection *b) {
323 if (a->flags != b->flags || a->getSize() != b->getSize() ||
324 a->content() != b->content())
325 return false;
326
327 // If two sections have different output sections, we cannot merge them.
328 assert(a->getParent() && b->getParent());
329 if (a->getParent() != b->getParent())
330 return false;
331
332 const RelsOrRelas<ELFT> ra = a->template relsOrRelas<ELFT>();
333 const RelsOrRelas<ELFT> rb = b->template relsOrRelas<ELFT>();
334 if (ra.areRelocsCrel() || rb.areRelocsCrel())
335 return constantEq(a, ra.crels, b, rb.crels);
336 return ra.areRelocsRel() || rb.areRelocsRel()
337 ? constantEq(a, ra.rels, b, rb.rels)
338 : constantEq(a, ra.relas, b, rb.relas);
339}
340
341// Compare two lists of relocations. Returns true if all pairs of
342// relocations point to the same section in terms of ICF.
343template <class ELFT>
344template <class RelTy>
345bool ICF<ELFT>::variableEq(const InputSection *secA, Relocs<RelTy> ra,
346 const InputSection *secB, Relocs<RelTy> rb) {
347 assert(ra.size() == rb.size());
348
349 auto rai = ra.begin(), rae = ra.end(), rbi = rb.begin();
350 for (; rai != rae; ++rai, ++rbi) {
351 // The two sections must be identical.
352 Symbol &sa = secA->file->getRelocTargetSym(*rai);
353 Symbol &sb = secB->file->getRelocTargetSym(*rbi);
354 if (&sa == &sb)
355 continue;
356
357 auto *da = cast<Defined>(Val: &sa);
358 auto *db = cast<Defined>(Val: &sb);
359
360 // We already dealt with absolute and non-InputSection symbols in
361 // constantEq, and for InputSections we have already checked everything
362 // except the equivalence class.
363 if (!da->section)
364 continue;
365 auto *x = dyn_cast<InputSection>(Val: da->section);
366 if (!x)
367 continue;
368 auto *y = cast<InputSection>(Val: db->section);
369
370 // Sections that are in the special equivalence class 0, can never be the
371 // same in terms of the equivalence class.
372 if (x->eqClass[current] == 0)
373 return false;
374 if (x->eqClass[current] != y->eqClass[current])
375 return false;
376 };
377
378 return true;
379}
380
381// Compare "moving" part of two InputSections, namely relocation targets.
382template <class ELFT>
383bool ICF<ELFT>::equalsVariable(const InputSection *a, const InputSection *b) {
384 const RelsOrRelas<ELFT> ra = a->template relsOrRelas<ELFT>();
385 const RelsOrRelas<ELFT> rb = b->template relsOrRelas<ELFT>();
386 if (ra.areRelocsCrel() || rb.areRelocsCrel())
387 return variableEq(a, ra.crels, b, rb.crels);
388 return ra.areRelocsRel() || rb.areRelocsRel()
389 ? variableEq(a, ra.rels, b, rb.rels)
390 : variableEq(a, ra.relas, b, rb.relas);
391}
392
393template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t begin, size_t end) {
394 uint32_t eqClass = sections[begin]->eqClass[current];
395 for (size_t i = begin + 1; i < end; ++i)
396 if (eqClass != sections[i]->eqClass[current])
397 return i;
398 return end;
399}
400
401// Sections in the same equivalence class are contiguous in Sections
402// vector. Therefore, Sections vector can be considered as contiguous
403// groups of sections, grouped by the class.
404//
405// This function calls Fn on every group within [Begin, End).
406template <class ELFT>
407void ICF<ELFT>::forEachClassRange(size_t begin, size_t end,
408 llvm::function_ref<void(size_t, size_t)> fn) {
409 while (begin < end) {
410 size_t mid = findBoundary(begin, end);
411 fn(begin, mid);
412 begin = mid;
413 }
414}
415
416// Call Fn on each equivalence class.
417
418template <class ELFT>
419void ICF<ELFT>::parallelForEachClass(
420 llvm::function_ref<void(size_t, size_t)> fn) {
421 // If threading is disabled or the number of sections are
422 // too small to use threading, call Fn sequentially.
423 if (parallel::strategy.ThreadsRequested == 1 || sections.size() < 1024) {
424 forEachClassRange(begin: 0, end: sections.size(), fn);
425 ++cnt;
426 return;
427 }
428
429 current = cnt % 2;
430 next = (cnt + 1) % 2;
431
432 // Shard into non-overlapping intervals, and call Fn in parallel.
433 // The sharding must be completed before any calls to Fn are made
434 // so that Fn can modify the Chunks in its shard without causing data
435 // races.
436 const size_t numShards = 256;
437 size_t step = sections.size() / numShards;
438 size_t boundaries[numShards + 1];
439 boundaries[0] = 0;
440 boundaries[numShards] = sections.size();
441
442 parallelFor(1, numShards, [&](size_t i) {
443 boundaries[i] = findBoundary(begin: (i - 1) * step, end: sections.size());
444 });
445
446 parallelFor(1, numShards + 1, [&](size_t i) {
447 if (boundaries[i - 1] < boundaries[i])
448 forEachClassRange(begin: boundaries[i - 1], end: boundaries[i], fn);
449 });
450 ++cnt;
451}
452
453// Combine the hashes of the sections referenced by the given section into its
454// hash.
455template <class RelTy>
456static void combineRelocHashes(unsigned cnt, InputSection *isec,
457 Relocs<RelTy> rels) {
458 uint32_t hash = isec->eqClass[cnt % 2];
459 for (RelTy rel : rels) {
460 Symbol &s = isec->file->getRelocTargetSym(rel);
461 if (auto *d = dyn_cast<Defined>(Val: &s))
462 if (auto *relSec = dyn_cast_or_null<InputSection>(Val: d->section))
463 hash += relSec->eqClass[cnt % 2];
464 }
465 // Set MSB to 1 to avoid collisions with unique IDs.
466 isec->eqClass[(cnt + 1) % 2] = hash | (1U << 31);
467}
468
469// The main function of ICF.
470template <class ELFT> void ICF<ELFT>::run() {
471 // Two text sections may have identical content and relocations but different
472 // LSDA, e.g. the two functions may have catch blocks of different types. If a
473 // text section is referenced by a .eh_frame FDE with LSDA, it is not
474 // eligible. This is implemented by iterating over CIE/FDE and setting
475 // eqClass[0] to the referenced text section from a live FDE.
476 //
477 // If two .gcc_except_table have identical semantics (usually identical
478 // content with PC-relative encoding), we will lose folding opportunity.
479 uint32_t uniqueId = 0;
480 ctx.in.ehFrame->iterateFDEWithLSDA<ELFT>(
481 [&](InputSection &s) { s.eqClass[0] = s.eqClass[1] = ++uniqueId; });
482
483 // Collect sections to merge.
484 for (InputSectionBase *sec : ctx.inputSections) {
485 auto *s = dyn_cast<InputSection>(Val: sec);
486 if (s && s->eqClass[0] == 0) {
487 if (isEligible(s))
488 sections.push_back(Elt: s);
489 else
490 // Ineligible sections are assigned unique IDs, i.e. each section
491 // belongs to an equivalence class of its own.
492 s->eqClass[0] = s->eqClass[1] = ++uniqueId;
493 }
494 }
495
496 // Initially, we use hash values to partition sections.
497 parallelForEach(sections, [&](InputSection *s) {
498 // Set MSB to 1 to avoid collisions with unique IDs.
499 s->eqClass[0] = xxh3_64bits(data: s->content()) | (1U << 31);
500 });
501
502 // Perform 2 rounds of relocation hash propagation. 2 is an empirical value to
503 // reduce the average sizes of equivalence classes, i.e. segregate() which has
504 // a large time complexity will have less work to do.
505 for (unsigned cnt = 0; cnt != 2; ++cnt) {
506 parallelForEach(sections, [&](InputSection *s) {
507 const RelsOrRelas<ELFT> rels = s->template relsOrRelas<ELFT>();
508 if (rels.areRelocsCrel())
509 combineRelocHashes(cnt, s, rels.crels);
510 else if (rels.areRelocsRel())
511 combineRelocHashes(cnt, s, rels.rels);
512 else
513 combineRelocHashes(cnt, s, rels.relas);
514 });
515 }
516
517 // From now on, sections in Sections vector are ordered so that sections
518 // in the same equivalence class are consecutive in the vector.
519 SmallVector<uint64_t, 0> keys(sections.size());
520 parallelFor(0, sections.size(), [&](size_t i) {
521 keys[i] = uint64_t(sections[i]->eqClass[0]) << 32 | i;
522 });
523 parallelSort(Start: keys.begin(), End: keys.end());
524 SmallVector<InputSection *, 0> sorted;
525 sorted.reserve(N: keys.size());
526 for (uint64_t k : keys)
527 sorted.push_back(Elt: sections[uint32_t(k)]);
528 sections = std::move(sorted);
529
530 // Compare static contents and assign unique equivalence class IDs for each
531 // static content. Use a base offset for these IDs to ensure no overlap with
532 // the unique IDs already assigned.
533 uint32_t eqClassBase = ++uniqueId;
534 parallelForEachClass(fn: [&](size_t begin, size_t end) {
535 segregate(begin, end, eqClassBase, constant: true);
536 });
537
538 // Split groups by comparing relocations until convergence is obtained.
539 do {
540 repeat = false;
541 parallelForEachClass(fn: [&](size_t begin, size_t end) {
542 segregate(begin, end, eqClassBase, constant: false);
543 });
544 } while (repeat);
545
546 Log(ctx) << "ICF needed " << cnt << " iterations";
547
548 // Merge sections by the equivalence class.
549 forEachClassRange(begin: 0, end: sections.size(), fn: [&](size_t begin, size_t end) {
550 for (size_t i = begin + 1; i < end; ++i) {
551 sections[begin]->replace(other: sections[i]);
552
553 // At this point we know sections merged are fully identical and hence
554 // we want to remove duplicate implicit dependencies such as link order
555 // and relocation sections.
556 for (InputSection *isec : sections[i]->dependentSections)
557 isec->markDead();
558 }
559 });
560
561 // Print classes in input order, independent of the hash.
562 if (ctx.arg.printIcfSections) {
563 DenseMap<InputSection *, SmallVector<InputSection *, 0>> folded;
564 for (InputSectionBase *sec : ctx.inputSections)
565 if (auto *s = dyn_cast<InputSection>(Val: sec); s && s->repl != s)
566 folded[s->repl].push_back(Elt: s);
567 for (InputSectionBase *sec : ctx.inputSections) {
568 auto it = folded.find(Val: dyn_cast<InputSection>(Val: sec));
569 if (it == folded.end())
570 continue;
571 Msg(ctx) << "selected section " << sec;
572 for (InputSection *s : it->second)
573 Msg(ctx) << " removing identical section " << s;
574 }
575 }
576
577 // Change Defined symbol's section field to the canonical one.
578 auto fold = [](Symbol *sym) {
579 if (auto *d = dyn_cast<Defined>(Val: sym))
580 if (auto *sec = dyn_cast_or_null<InputSection>(Val: d->section))
581 if (sec->repl != d->section) {
582 d->section = sec->repl;
583 d->folded = true;
584 }
585 };
586 for (Symbol *sym : ctx.symtab->getSymbols())
587 fold(sym);
588 parallelForEach(ctx.objectFiles, [&](ELFFileBase *file) {
589 for (Symbol *sym : file->getLocalSymbols())
590 fold(sym);
591 });
592
593 // InputSectionDescription::sections is populated by processSectionCommands().
594 // ICF may fold some input sections assigned to output sections. Remove them.
595 for (SectionCommand *cmd : ctx.script->sectionCommands)
596 if (auto *osd = dyn_cast<OutputDesc>(Val: cmd))
597 for (SectionCommand *subCmd : osd->osec.commands)
598 if (auto *isd = dyn_cast<InputSectionDescription>(Val: subCmd))
599 llvm::erase_if(isd->sections,
600 [](InputSection *isec) { return !isec->isLive(); });
601}
602
603// ICF entry point function.
604template <class ELFT> void elf::doIcf(Ctx &ctx) {
605 llvm::TimeTraceScope timeScope("ICF");
606 ICF<ELFT>(ctx).run();
607}
608
609template void elf::doIcf<ELF32LE>(Ctx &);
610template void elf::doIcf<ELF32BE>(Ctx &);
611template void elf::doIcf<ELF64LE>(Ctx &);
612template void elf::doIcf<ELF64BE>(Ctx &);
613