1 //===- ICF.cpp ------------------------------------------------------------===//
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
7 //===----------------------------------------------------------------------===//
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
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
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.
24 // void foo() { bar(); }
25 // void bar() { foo(); }
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.
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:
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.
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
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.
52 // 4. For each equivalence class C, pick an arbitrary section in C, and
53 // merge all the other sections in C with it.
55 // For small programs, this algorithm needs 3-5 iterations. For large
56 // programs such as Chromium, it takes more than 20 iterations.
58 // This algorithm was mentioned as an "optimistic algorithm" in [1],
59 // though gold implements a different algorithm than this.
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.
69 // [1] Safe ICF: Pointer Safe and Unwinding aware Identical Code Folding
71 // http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/36912.pdf
73 //===----------------------------------------------------------------------===//
77 #include "SymbolTable.h"
79 #include "SyntheticSections.h"
81 #include "lld/Common/Threads.h"
82 #include "llvm/ADT/StringExtras.h"
83 #include "llvm/BinaryFormat/ELF.h"
84 #include "llvm/Object/ELF.h"
85 #include "llvm/Support/xxhash.h"
90 using namespace lld::elf;
92 using namespace llvm::ELF;
93 using namespace llvm::object;
96 template <class ELFT> class ICF {
101 void segregate(size_t begin, size_t end, bool constant);
103 template <class RelTy>
104 bool constantEq(const InputSection *a, ArrayRef<RelTy> relsA,
105 const InputSection *b, ArrayRef<RelTy> relsB);
107 template <class RelTy>
108 bool variableEq(const InputSection *a, ArrayRef<RelTy> relsA,
109 const InputSection *b, ArrayRef<RelTy> relsB);
111 bool equalsConstant(const InputSection *a, const InputSection *b);
112 bool equalsVariable(const InputSection *a, const InputSection *b);
114 size_t findBoundary(size_t begin, size_t end);
116 void forEachClassRange(size_t begin, size_t end,
117 llvm::function_ref<void(size_t, size_t)> fn);
119 void forEachClass(llvm::function_ref<void(size_t, size_t)> fn);
121 std::vector<InputSection *> sections;
123 // We repeat the main loop while `Repeat` is true.
124 std::atomic<bool> repeat;
126 // The main loop counter.
129 // We have two locations for equivalence classes. On the first iteration
130 // of the main loop, Class[0] has a valid value, and Class[1] contains
131 // garbage. We read equivalence classes from slot 0 and write to slot 1.
132 // So, Class[0] represents the current class, and Class[1] represents
133 // the next class. On each iteration, we switch their roles and use them
136 // Why are we doing this? Recall that other threads may be working on
137 // other equivalence classes in parallel. They may read sections that we
138 // are updating. We cannot update equivalence classes in place because
139 // it breaks the invariance that all possibly-identical sections must be
140 // in the same equivalence class at any moment. In other words, the for
141 // loop to update equivalence classes is not atomic, and that is
142 // observable from other threads. By writing new classes to other
143 // places, we can keep the invariance.
145 // Below, `Current` has the index of the current class, and `Next` has
146 // the index of the next class. If threading is enabled, they are either
149 // Note on single-thread: if that's the case, they are always (0, 0)
150 // because we can safely read the next class without worrying about race
151 // conditions. Using the same location makes this algorithm converge
152 // faster because it uses results of the same iteration earlier.
158 // Returns true if section S is subject of ICF.
159 static bool isEligible(InputSection *s) {
160 if (!s->isLive() || s->keepUnique || !(s->flags & SHF_ALLOC))
163 // Don't merge writable sections. .data.rel.ro sections are marked as writable
164 // but are semantically read-only.
165 if ((s->flags & SHF_WRITE) && s->name != ".data.rel.ro" &&
166 !s->name.startswith(".data.rel.ro."))
169 // SHF_LINK_ORDER sections are ICF'd as a unit with their dependent sections,
170 // so we don't consider them for ICF individually.
171 if (s->flags & SHF_LINK_ORDER)
174 // Don't merge synthetic sections as their Data member is not valid and empty.
175 // The Data member needs to be valid for ICF as it is used by ICF to determine
176 // the equality of section contents.
177 if (isa<SyntheticSection>(s))
180 // .init and .fini contains instructions that must be executed to initialize
181 // and finalize the process. They cannot and should not be merged.
182 if (s->name == ".init" || s->name == ".fini")
185 // A user program may enumerate sections named with a C identifier using
186 // __start_* and __stop_* symbols. We cannot ICF any such sections because
187 // that could change program semantics.
188 if (isValidCIdentifier(s->name))
194 // Split an equivalence class into smaller classes.
195 template <class ELFT>
196 void ICF<ELFT>::segregate(size_t begin, size_t end, bool constant) {
197 // This loop rearranges sections in [Begin, End) so that all sections
198 // that are equal in terms of equals{Constant,Variable} are contiguous
201 // The algorithm is quadratic in the worst case, but that is not an
202 // issue in practice because the number of the distinct sections in
203 // each range is usually very small.
205 while (begin < end) {
206 // Divide [Begin, End) into two. Let Mid be the start index of the
209 std::stable_partition(sections.begin() + begin + 1,
210 sections.begin() + end, [&](InputSection *s) {
212 return equalsConstant(sections[begin], s);
213 return equalsVariable(sections[begin], s);
215 size_t mid = bound - sections.begin();
217 // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
218 // updating the sections in [Begin, Mid). We use Mid as an equivalence
219 // class ID because every group ends with a unique index.
220 for (size_t i = begin; i < mid; ++i)
221 sections[i]->eqClass[next] = mid;
223 // If we created a group, we need to iterate the main loop again.
231 // Compare two lists of relocations.
232 template <class ELFT>
233 template <class RelTy>
234 bool ICF<ELFT>::constantEq(const InputSection *secA, ArrayRef<RelTy> ra,
235 const InputSection *secB, ArrayRef<RelTy> rb) {
236 for (size_t i = 0; i < ra.size(); ++i) {
237 if (ra[i].r_offset != rb[i].r_offset ||
238 ra[i].getType(config->isMips64EL) != rb[i].getType(config->isMips64EL))
241 uint64_t addA = getAddend<ELFT>(ra[i]);
242 uint64_t addB = getAddend<ELFT>(rb[i]);
244 Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]);
245 Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]);
252 auto *da = dyn_cast<Defined>(&sa);
253 auto *db = dyn_cast<Defined>(&sb);
255 // Placeholder symbols generated by linker scripts look the same now but
256 // may have different values later.
257 if (!da || !db || da->scriptDefined || db->scriptDefined)
260 // Relocations referring to absolute symbols are constant-equal if their
262 if (!da->section && !db->section && da->value + addA == db->value + addB)
264 if (!da->section || !db->section)
267 if (da->section->kind() != db->section->kind())
270 // Relocations referring to InputSections are constant-equal if their
271 // section offsets are equal.
272 if (isa<InputSection>(da->section)) {
273 if (da->value + addA == db->value + addB)
278 // Relocations referring to MergeInputSections are constant-equal if their
279 // offsets in the output section are equal.
280 auto *x = dyn_cast<MergeInputSection>(da->section);
283 auto *y = cast<MergeInputSection>(db->section);
284 if (x->getParent() != y->getParent())
288 sa.isSection() ? x->getOffset(addA) : x->getOffset(da->value) + addA;
290 sb.isSection() ? y->getOffset(addB) : y->getOffset(db->value) + addB;
291 if (offsetA != offsetB)
298 // Compare "non-moving" part of two InputSections, namely everything
299 // except relocation targets.
300 template <class ELFT>
301 bool ICF<ELFT>::equalsConstant(const InputSection *a, const InputSection *b) {
302 if (a->numRelocations != b->numRelocations || a->flags != b->flags ||
303 a->getSize() != b->getSize() || a->data() != b->data())
306 // If two sections have different output sections, we cannot merge them.
307 // FIXME: This doesn't do the right thing in the case where there is a linker
308 // script. We probably need to move output section assignment before ICF to
309 // get the correct behaviour here.
310 if (getOutputSectionName(a) != getOutputSectionName(b))
313 if (a->areRelocsRela)
314 return constantEq(a, a->template relas<ELFT>(), b,
315 b->template relas<ELFT>());
316 return constantEq(a, a->template rels<ELFT>(), b, b->template rels<ELFT>());
319 // Compare two lists of relocations. Returns true if all pairs of
320 // relocations point to the same section in terms of ICF.
321 template <class ELFT>
322 template <class RelTy>
323 bool ICF<ELFT>::variableEq(const InputSection *secA, ArrayRef<RelTy> ra,
324 const InputSection *secB, ArrayRef<RelTy> rb) {
325 assert(ra.size() == rb.size());
327 for (size_t i = 0; i < ra.size(); ++i) {
328 // The two sections must be identical.
329 Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]);
330 Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]);
334 auto *da = cast<Defined>(&sa);
335 auto *db = cast<Defined>(&sb);
337 // We already dealt with absolute and non-InputSection symbols in
338 // constantEq, and for InputSections we have already checked everything
339 // except the equivalence class.
342 auto *x = dyn_cast<InputSection>(da->section);
345 auto *y = cast<InputSection>(db->section);
347 // Ineligible sections are in the special equivalence class 0.
348 // They can never be the same in terms of the equivalence class.
349 if (x->eqClass[current] == 0)
351 if (x->eqClass[current] != y->eqClass[current])
358 // Compare "moving" part of two InputSections, namely relocation targets.
359 template <class ELFT>
360 bool ICF<ELFT>::equalsVariable(const InputSection *a, const InputSection *b) {
361 if (a->areRelocsRela)
362 return variableEq(a, a->template relas<ELFT>(), b,
363 b->template relas<ELFT>());
364 return variableEq(a, a->template rels<ELFT>(), b, b->template rels<ELFT>());
367 template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t begin, size_t end) {
368 uint32_t eqClass = sections[begin]->eqClass[current];
369 for (size_t i = begin + 1; i < end; ++i)
370 if (eqClass != sections[i]->eqClass[current])
375 // Sections in the same equivalence class are contiguous in Sections
376 // vector. Therefore, Sections vector can be considered as contiguous
377 // groups of sections, grouped by the class.
379 // This function calls Fn on every group within [Begin, End).
380 template <class ELFT>
381 void ICF<ELFT>::forEachClassRange(size_t begin, size_t end,
382 llvm::function_ref<void(size_t, size_t)> fn) {
383 while (begin < end) {
384 size_t mid = findBoundary(begin, end);
390 // Call Fn on each equivalence class.
391 template <class ELFT>
392 void ICF<ELFT>::forEachClass(llvm::function_ref<void(size_t, size_t)> fn) {
393 // If threading is disabled or the number of sections are
394 // too small to use threading, call Fn sequentially.
395 if (!threadsEnabled || sections.size() < 1024) {
396 forEachClassRange(0, sections.size(), fn);
402 next = (cnt + 1) % 2;
404 // Shard into non-overlapping intervals, and call Fn in parallel.
405 // The sharding must be completed before any calls to Fn are made
406 // so that Fn can modify the Chunks in its shard without causing data
408 const size_t numShards = 256;
409 size_t step = sections.size() / numShards;
410 size_t boundaries[numShards + 1];
412 boundaries[numShards] = sections.size();
414 parallelForEachN(1, numShards, [&](size_t i) {
415 boundaries[i] = findBoundary((i - 1) * step, sections.size());
418 parallelForEachN(1, numShards + 1, [&](size_t i) {
419 if (boundaries[i - 1] < boundaries[i])
420 forEachClassRange(boundaries[i - 1], boundaries[i], fn);
425 // Combine the hashes of the sections referenced by the given section into its
427 template <class ELFT, class RelTy>
428 static void combineRelocHashes(unsigned cnt, InputSection *isec,
429 ArrayRef<RelTy> rels) {
430 uint32_t hash = isec->eqClass[cnt % 2];
431 for (RelTy rel : rels) {
432 Symbol &s = isec->template getFile<ELFT>()->getRelocTargetSym(rel);
433 if (auto *d = dyn_cast<Defined>(&s))
434 if (auto *relSec = dyn_cast_or_null<InputSection>(d->section))
435 hash += relSec->eqClass[cnt % 2];
437 // Set MSB to 1 to avoid collisions with non-hash IDs.
438 isec->eqClass[(cnt + 1) % 2] = hash | (1U << 31);
441 static void print(const Twine &s) {
442 if (config->printIcfSections)
446 // The main function of ICF.
447 template <class ELFT> void ICF<ELFT>::run() {
448 // Collect sections to merge.
449 for (InputSectionBase *sec : inputSections)
450 if (auto *s = dyn_cast<InputSection>(sec))
452 sections.push_back(s);
454 // Initially, we use hash values to partition sections.
455 parallelForEach(sections, [&](InputSection *s) {
456 s->eqClass[0] = xxHash64(s->data());
459 for (unsigned cnt = 0; cnt != 2; ++cnt) {
460 parallelForEach(sections, [&](InputSection *s) {
461 if (s->areRelocsRela)
462 combineRelocHashes<ELFT>(cnt, s, s->template relas<ELFT>());
464 combineRelocHashes<ELFT>(cnt, s, s->template rels<ELFT>());
468 // From now on, sections in Sections vector are ordered so that sections
469 // in the same equivalence class are consecutive in the vector.
470 llvm::stable_sort(sections, [](const InputSection *a, const InputSection *b) {
471 return a->eqClass[0] < b->eqClass[0];
474 // Compare static contents and assign unique IDs for each static content.
475 forEachClass([&](size_t begin, size_t end) { segregate(begin, end, true); });
477 // Split groups by comparing relocations until convergence is obtained.
481 [&](size_t begin, size_t end) { segregate(begin, end, false); });
484 log("ICF needed " + Twine(cnt) + " iterations");
486 // Merge sections by the equivalence class.
487 forEachClassRange(0, sections.size(), [&](size_t begin, size_t end) {
488 if (end - begin == 1)
490 print("selected section " + toString(sections[begin]));
491 for (size_t i = begin + 1; i < end; ++i) {
492 print(" removing identical section " + toString(sections[i]));
493 sections[begin]->replace(sections[i]);
495 // At this point we know sections merged are fully identical and hence
496 // we want to remove duplicate implicit dependencies such as link order
497 // and relocation sections.
498 for (InputSection *isec : sections[i]->dependentSections)
504 // ICF entry point function.
505 template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
507 template void elf::doIcf<ELF32LE>();
508 template void elf::doIcf<ELF32BE>();
509 template void elf::doIcf<ELF64LE>();
510 template void elf::doIcf<ELF64BE>();