xref: /freebsd/contrib/llvm-project/lld/ELF/ICF.cpp (revision 85868e8a1daeaae7a0e48effb2ea2310ae3b02c6)
10b57cec5SDimitry Andric //===- ICF.cpp ------------------------------------------------------------===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric // ICF is short for Identical Code Folding. This is a size optimization to
100b57cec5SDimitry Andric // identify and merge two or more read-only sections (typically functions)
110b57cec5SDimitry Andric // that happened to have the same contents. It usually reduces output size
120b57cec5SDimitry Andric // by a few percent.
130b57cec5SDimitry Andric //
140b57cec5SDimitry Andric // In ICF, two sections are considered identical if they have the same
150b57cec5SDimitry Andric // section flags, section data, and relocations. Relocations are tricky,
160b57cec5SDimitry Andric // because two relocations are considered the same if they have the same
170b57cec5SDimitry Andric // relocation types, values, and if they point to the same sections *in
180b57cec5SDimitry Andric // terms of ICF*.
190b57cec5SDimitry Andric //
200b57cec5SDimitry Andric // Here is an example. If foo and bar defined below are compiled to the
210b57cec5SDimitry Andric // same machine instructions, ICF can and should merge the two, although
220b57cec5SDimitry Andric // their relocations point to each other.
230b57cec5SDimitry Andric //
240b57cec5SDimitry Andric //   void foo() { bar(); }
250b57cec5SDimitry Andric //   void bar() { foo(); }
260b57cec5SDimitry Andric //
270b57cec5SDimitry Andric // If you merge the two, their relocations point to the same section and
280b57cec5SDimitry Andric // thus you know they are mergeable, but how do you know they are
290b57cec5SDimitry Andric // mergeable in the first place? This is not an easy problem to solve.
300b57cec5SDimitry Andric //
310b57cec5SDimitry Andric // What we are doing in LLD is to partition sections into equivalence
320b57cec5SDimitry Andric // classes. Sections in the same equivalence class when the algorithm
330b57cec5SDimitry Andric // terminates are considered identical. Here are details:
340b57cec5SDimitry Andric //
350b57cec5SDimitry Andric // 1. First, we partition sections using their hash values as keys. Hash
360b57cec5SDimitry Andric //    values contain section types, section contents and numbers of
370b57cec5SDimitry Andric //    relocations. During this step, relocation targets are not taken into
380b57cec5SDimitry Andric //    account. We just put sections that apparently differ into different
390b57cec5SDimitry Andric //    equivalence classes.
400b57cec5SDimitry Andric //
410b57cec5SDimitry Andric // 2. Next, for each equivalence class, we visit sections to compare
420b57cec5SDimitry Andric //    relocation targets. Relocation targets are considered equivalent if
430b57cec5SDimitry Andric //    their targets are in the same equivalence class. Sections with
440b57cec5SDimitry Andric //    different relocation targets are put into different equivalence
450b57cec5SDimitry Andric //    clases.
460b57cec5SDimitry Andric //
470b57cec5SDimitry Andric // 3. If we split an equivalence class in step 2, two relocations
480b57cec5SDimitry Andric //    previously target the same equivalence class may now target
490b57cec5SDimitry Andric //    different equivalence classes. Therefore, we repeat step 2 until a
500b57cec5SDimitry Andric //    convergence is obtained.
510b57cec5SDimitry Andric //
520b57cec5SDimitry Andric // 4. For each equivalence class C, pick an arbitrary section in C, and
530b57cec5SDimitry Andric //    merge all the other sections in C with it.
540b57cec5SDimitry Andric //
550b57cec5SDimitry Andric // For small programs, this algorithm needs 3-5 iterations. For large
560b57cec5SDimitry Andric // programs such as Chromium, it takes more than 20 iterations.
570b57cec5SDimitry Andric //
580b57cec5SDimitry Andric // This algorithm was mentioned as an "optimistic algorithm" in [1],
590b57cec5SDimitry Andric // though gold implements a different algorithm than this.
600b57cec5SDimitry Andric //
610b57cec5SDimitry Andric // We parallelize each step so that multiple threads can work on different
620b57cec5SDimitry Andric // equivalence classes concurrently. That gave us a large performance
630b57cec5SDimitry Andric // boost when applying ICF on large programs. For example, MSVC link.exe
640b57cec5SDimitry Andric // or GNU gold takes 10-20 seconds to apply ICF on Chromium, whose output
650b57cec5SDimitry Andric // size is about 1.5 GB, but LLD can finish it in less than 2 seconds on a
660b57cec5SDimitry Andric // 2.8 GHz 40 core machine. Even without threading, LLD's ICF is still
670b57cec5SDimitry Andric // faster than MSVC or gold though.
680b57cec5SDimitry Andric //
690b57cec5SDimitry Andric // [1] Safe ICF: Pointer Safe and Unwinding aware Identical Code Folding
700b57cec5SDimitry Andric // in the Gold Linker
710b57cec5SDimitry Andric // http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/36912.pdf
720b57cec5SDimitry Andric //
730b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
740b57cec5SDimitry Andric 
750b57cec5SDimitry Andric #include "ICF.h"
760b57cec5SDimitry Andric #include "Config.h"
77*85868e8aSDimitry Andric #include "LinkerScript.h"
78*85868e8aSDimitry Andric #include "OutputSections.h"
790b57cec5SDimitry Andric #include "SymbolTable.h"
800b57cec5SDimitry Andric #include "Symbols.h"
810b57cec5SDimitry Andric #include "SyntheticSections.h"
820b57cec5SDimitry Andric #include "Writer.h"
830b57cec5SDimitry Andric #include "lld/Common/Threads.h"
840b57cec5SDimitry Andric #include "llvm/ADT/StringExtras.h"
850b57cec5SDimitry Andric #include "llvm/BinaryFormat/ELF.h"
860b57cec5SDimitry Andric #include "llvm/Object/ELF.h"
870b57cec5SDimitry Andric #include "llvm/Support/xxhash.h"
880b57cec5SDimitry Andric #include <algorithm>
890b57cec5SDimitry Andric #include <atomic>
900b57cec5SDimitry Andric 
910b57cec5SDimitry Andric using namespace llvm;
920b57cec5SDimitry Andric using namespace llvm::ELF;
930b57cec5SDimitry Andric using namespace llvm::object;
940b57cec5SDimitry Andric 
95*85868e8aSDimitry Andric namespace lld {
96*85868e8aSDimitry Andric namespace elf {
970b57cec5SDimitry Andric namespace {
980b57cec5SDimitry Andric template <class ELFT> class ICF {
990b57cec5SDimitry Andric public:
1000b57cec5SDimitry Andric   void run();
1010b57cec5SDimitry Andric 
1020b57cec5SDimitry Andric private:
1030b57cec5SDimitry Andric   void segregate(size_t begin, size_t end, bool constant);
1040b57cec5SDimitry Andric 
1050b57cec5SDimitry Andric   template <class RelTy>
1060b57cec5SDimitry Andric   bool constantEq(const InputSection *a, ArrayRef<RelTy> relsA,
1070b57cec5SDimitry Andric                   const InputSection *b, ArrayRef<RelTy> relsB);
1080b57cec5SDimitry Andric 
1090b57cec5SDimitry Andric   template <class RelTy>
1100b57cec5SDimitry Andric   bool variableEq(const InputSection *a, ArrayRef<RelTy> relsA,
1110b57cec5SDimitry Andric                   const InputSection *b, ArrayRef<RelTy> relsB);
1120b57cec5SDimitry Andric 
1130b57cec5SDimitry Andric   bool equalsConstant(const InputSection *a, const InputSection *b);
1140b57cec5SDimitry Andric   bool equalsVariable(const InputSection *a, const InputSection *b);
1150b57cec5SDimitry Andric 
1160b57cec5SDimitry Andric   size_t findBoundary(size_t begin, size_t end);
1170b57cec5SDimitry Andric 
1180b57cec5SDimitry Andric   void forEachClassRange(size_t begin, size_t end,
1190b57cec5SDimitry Andric                          llvm::function_ref<void(size_t, size_t)> fn);
1200b57cec5SDimitry Andric 
1210b57cec5SDimitry Andric   void forEachClass(llvm::function_ref<void(size_t, size_t)> fn);
1220b57cec5SDimitry Andric 
1230b57cec5SDimitry Andric   std::vector<InputSection *> sections;
1240b57cec5SDimitry Andric 
1250b57cec5SDimitry Andric   // We repeat the main loop while `Repeat` is true.
1260b57cec5SDimitry Andric   std::atomic<bool> repeat;
1270b57cec5SDimitry Andric 
1280b57cec5SDimitry Andric   // The main loop counter.
1290b57cec5SDimitry Andric   int cnt = 0;
1300b57cec5SDimitry Andric 
1310b57cec5SDimitry Andric   // We have two locations for equivalence classes. On the first iteration
1320b57cec5SDimitry Andric   // of the main loop, Class[0] has a valid value, and Class[1] contains
1330b57cec5SDimitry Andric   // garbage. We read equivalence classes from slot 0 and write to slot 1.
1340b57cec5SDimitry Andric   // So, Class[0] represents the current class, and Class[1] represents
1350b57cec5SDimitry Andric   // the next class. On each iteration, we switch their roles and use them
1360b57cec5SDimitry Andric   // alternately.
1370b57cec5SDimitry Andric   //
1380b57cec5SDimitry Andric   // Why are we doing this? Recall that other threads may be working on
1390b57cec5SDimitry Andric   // other equivalence classes in parallel. They may read sections that we
1400b57cec5SDimitry Andric   // are updating. We cannot update equivalence classes in place because
1410b57cec5SDimitry Andric   // it breaks the invariance that all possibly-identical sections must be
1420b57cec5SDimitry Andric   // in the same equivalence class at any moment. In other words, the for
1430b57cec5SDimitry Andric   // loop to update equivalence classes is not atomic, and that is
1440b57cec5SDimitry Andric   // observable from other threads. By writing new classes to other
1450b57cec5SDimitry Andric   // places, we can keep the invariance.
1460b57cec5SDimitry Andric   //
1470b57cec5SDimitry Andric   // Below, `Current` has the index of the current class, and `Next` has
1480b57cec5SDimitry Andric   // the index of the next class. If threading is enabled, they are either
1490b57cec5SDimitry Andric   // (0, 1) or (1, 0).
1500b57cec5SDimitry Andric   //
1510b57cec5SDimitry Andric   // Note on single-thread: if that's the case, they are always (0, 0)
1520b57cec5SDimitry Andric   // because we can safely read the next class without worrying about race
1530b57cec5SDimitry Andric   // conditions. Using the same location makes this algorithm converge
1540b57cec5SDimitry Andric   // faster because it uses results of the same iteration earlier.
1550b57cec5SDimitry Andric   int current = 0;
1560b57cec5SDimitry Andric   int next = 0;
1570b57cec5SDimitry Andric };
1580b57cec5SDimitry Andric }
1590b57cec5SDimitry Andric 
1600b57cec5SDimitry Andric // Returns true if section S is subject of ICF.
1610b57cec5SDimitry Andric static bool isEligible(InputSection *s) {
1620b57cec5SDimitry Andric   if (!s->isLive() || s->keepUnique || !(s->flags & SHF_ALLOC))
1630b57cec5SDimitry Andric     return false;
1640b57cec5SDimitry Andric 
1650b57cec5SDimitry Andric   // Don't merge writable sections. .data.rel.ro sections are marked as writable
1660b57cec5SDimitry Andric   // but are semantically read-only.
1670b57cec5SDimitry Andric   if ((s->flags & SHF_WRITE) && s->name != ".data.rel.ro" &&
1680b57cec5SDimitry Andric       !s->name.startswith(".data.rel.ro."))
1690b57cec5SDimitry Andric     return false;
1700b57cec5SDimitry Andric 
1710b57cec5SDimitry Andric   // SHF_LINK_ORDER sections are ICF'd as a unit with their dependent sections,
1720b57cec5SDimitry Andric   // so we don't consider them for ICF individually.
1730b57cec5SDimitry Andric   if (s->flags & SHF_LINK_ORDER)
1740b57cec5SDimitry Andric     return false;
1750b57cec5SDimitry Andric 
1760b57cec5SDimitry Andric   // Don't merge synthetic sections as their Data member is not valid and empty.
1770b57cec5SDimitry Andric   // The Data member needs to be valid for ICF as it is used by ICF to determine
1780b57cec5SDimitry Andric   // the equality of section contents.
1790b57cec5SDimitry Andric   if (isa<SyntheticSection>(s))
1800b57cec5SDimitry Andric     return false;
1810b57cec5SDimitry Andric 
1820b57cec5SDimitry Andric   // .init and .fini contains instructions that must be executed to initialize
1830b57cec5SDimitry Andric   // and finalize the process. They cannot and should not be merged.
1840b57cec5SDimitry Andric   if (s->name == ".init" || s->name == ".fini")
1850b57cec5SDimitry Andric     return false;
1860b57cec5SDimitry Andric 
1870b57cec5SDimitry Andric   // A user program may enumerate sections named with a C identifier using
1880b57cec5SDimitry Andric   // __start_* and __stop_* symbols. We cannot ICF any such sections because
1890b57cec5SDimitry Andric   // that could change program semantics.
1900b57cec5SDimitry Andric   if (isValidCIdentifier(s->name))
1910b57cec5SDimitry Andric     return false;
1920b57cec5SDimitry Andric 
1930b57cec5SDimitry Andric   return true;
1940b57cec5SDimitry Andric }
1950b57cec5SDimitry Andric 
1960b57cec5SDimitry Andric // Split an equivalence class into smaller classes.
1970b57cec5SDimitry Andric template <class ELFT>
1980b57cec5SDimitry Andric void ICF<ELFT>::segregate(size_t begin, size_t end, bool constant) {
1990b57cec5SDimitry Andric   // This loop rearranges sections in [Begin, End) so that all sections
2000b57cec5SDimitry Andric   // that are equal in terms of equals{Constant,Variable} are contiguous
2010b57cec5SDimitry Andric   // in [Begin, End).
2020b57cec5SDimitry Andric   //
2030b57cec5SDimitry Andric   // The algorithm is quadratic in the worst case, but that is not an
2040b57cec5SDimitry Andric   // issue in practice because the number of the distinct sections in
2050b57cec5SDimitry Andric   // each range is usually very small.
2060b57cec5SDimitry Andric 
2070b57cec5SDimitry Andric   while (begin < end) {
2080b57cec5SDimitry Andric     // Divide [Begin, End) into two. Let Mid be the start index of the
2090b57cec5SDimitry Andric     // second group.
2100b57cec5SDimitry Andric     auto bound =
2110b57cec5SDimitry Andric         std::stable_partition(sections.begin() + begin + 1,
2120b57cec5SDimitry Andric                               sections.begin() + end, [&](InputSection *s) {
2130b57cec5SDimitry Andric                                 if (constant)
2140b57cec5SDimitry Andric                                   return equalsConstant(sections[begin], s);
2150b57cec5SDimitry Andric                                 return equalsVariable(sections[begin], s);
2160b57cec5SDimitry Andric                               });
2170b57cec5SDimitry Andric     size_t mid = bound - sections.begin();
2180b57cec5SDimitry Andric 
2190b57cec5SDimitry Andric     // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
2200b57cec5SDimitry Andric     // updating the sections in [Begin, Mid). We use Mid as an equivalence
2210b57cec5SDimitry Andric     // class ID because every group ends with a unique index.
2220b57cec5SDimitry Andric     for (size_t i = begin; i < mid; ++i)
2230b57cec5SDimitry Andric       sections[i]->eqClass[next] = mid;
2240b57cec5SDimitry Andric 
2250b57cec5SDimitry Andric     // If we created a group, we need to iterate the main loop again.
2260b57cec5SDimitry Andric     if (mid != end)
2270b57cec5SDimitry Andric       repeat = true;
2280b57cec5SDimitry Andric 
2290b57cec5SDimitry Andric     begin = mid;
2300b57cec5SDimitry Andric   }
2310b57cec5SDimitry Andric }
2320b57cec5SDimitry Andric 
2330b57cec5SDimitry Andric // Compare two lists of relocations.
2340b57cec5SDimitry Andric template <class ELFT>
2350b57cec5SDimitry Andric template <class RelTy>
2360b57cec5SDimitry Andric bool ICF<ELFT>::constantEq(const InputSection *secA, ArrayRef<RelTy> ra,
2370b57cec5SDimitry Andric                            const InputSection *secB, ArrayRef<RelTy> rb) {
2380b57cec5SDimitry Andric   for (size_t i = 0; i < ra.size(); ++i) {
2390b57cec5SDimitry Andric     if (ra[i].r_offset != rb[i].r_offset ||
2400b57cec5SDimitry Andric         ra[i].getType(config->isMips64EL) != rb[i].getType(config->isMips64EL))
2410b57cec5SDimitry Andric       return false;
2420b57cec5SDimitry Andric 
2430b57cec5SDimitry Andric     uint64_t addA = getAddend<ELFT>(ra[i]);
2440b57cec5SDimitry Andric     uint64_t addB = getAddend<ELFT>(rb[i]);
2450b57cec5SDimitry Andric 
2460b57cec5SDimitry Andric     Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]);
2470b57cec5SDimitry Andric     Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]);
2480b57cec5SDimitry Andric     if (&sa == &sb) {
2490b57cec5SDimitry Andric       if (addA == addB)
2500b57cec5SDimitry Andric         continue;
2510b57cec5SDimitry Andric       return false;
2520b57cec5SDimitry Andric     }
2530b57cec5SDimitry Andric 
2540b57cec5SDimitry Andric     auto *da = dyn_cast<Defined>(&sa);
2550b57cec5SDimitry Andric     auto *db = dyn_cast<Defined>(&sb);
2560b57cec5SDimitry Andric 
2570b57cec5SDimitry Andric     // Placeholder symbols generated by linker scripts look the same now but
2580b57cec5SDimitry Andric     // may have different values later.
2590b57cec5SDimitry Andric     if (!da || !db || da->scriptDefined || db->scriptDefined)
2600b57cec5SDimitry Andric       return false;
2610b57cec5SDimitry Andric 
2620b57cec5SDimitry Andric     // Relocations referring to absolute symbols are constant-equal if their
2630b57cec5SDimitry Andric     // values are equal.
2640b57cec5SDimitry Andric     if (!da->section && !db->section && da->value + addA == db->value + addB)
2650b57cec5SDimitry Andric       continue;
2660b57cec5SDimitry Andric     if (!da->section || !db->section)
2670b57cec5SDimitry Andric       return false;
2680b57cec5SDimitry Andric 
2690b57cec5SDimitry Andric     if (da->section->kind() != db->section->kind())
2700b57cec5SDimitry Andric       return false;
2710b57cec5SDimitry Andric 
2720b57cec5SDimitry Andric     // Relocations referring to InputSections are constant-equal if their
2730b57cec5SDimitry Andric     // section offsets are equal.
2740b57cec5SDimitry Andric     if (isa<InputSection>(da->section)) {
2750b57cec5SDimitry Andric       if (da->value + addA == db->value + addB)
2760b57cec5SDimitry Andric         continue;
2770b57cec5SDimitry Andric       return false;
2780b57cec5SDimitry Andric     }
2790b57cec5SDimitry Andric 
2800b57cec5SDimitry Andric     // Relocations referring to MergeInputSections are constant-equal if their
2810b57cec5SDimitry Andric     // offsets in the output section are equal.
2820b57cec5SDimitry Andric     auto *x = dyn_cast<MergeInputSection>(da->section);
2830b57cec5SDimitry Andric     if (!x)
2840b57cec5SDimitry Andric       return false;
2850b57cec5SDimitry Andric     auto *y = cast<MergeInputSection>(db->section);
2860b57cec5SDimitry Andric     if (x->getParent() != y->getParent())
2870b57cec5SDimitry Andric       return false;
2880b57cec5SDimitry Andric 
2890b57cec5SDimitry Andric     uint64_t offsetA =
2900b57cec5SDimitry Andric         sa.isSection() ? x->getOffset(addA) : x->getOffset(da->value) + addA;
2910b57cec5SDimitry Andric     uint64_t offsetB =
2920b57cec5SDimitry Andric         sb.isSection() ? y->getOffset(addB) : y->getOffset(db->value) + addB;
2930b57cec5SDimitry Andric     if (offsetA != offsetB)
2940b57cec5SDimitry Andric       return false;
2950b57cec5SDimitry Andric   }
2960b57cec5SDimitry Andric 
2970b57cec5SDimitry Andric   return true;
2980b57cec5SDimitry Andric }
2990b57cec5SDimitry Andric 
3000b57cec5SDimitry Andric // Compare "non-moving" part of two InputSections, namely everything
3010b57cec5SDimitry Andric // except relocation targets.
3020b57cec5SDimitry Andric template <class ELFT>
3030b57cec5SDimitry Andric bool ICF<ELFT>::equalsConstant(const InputSection *a, const InputSection *b) {
3040b57cec5SDimitry Andric   if (a->numRelocations != b->numRelocations || a->flags != b->flags ||
3050b57cec5SDimitry Andric       a->getSize() != b->getSize() || a->data() != b->data())
3060b57cec5SDimitry Andric     return false;
3070b57cec5SDimitry Andric 
3080b57cec5SDimitry Andric   // If two sections have different output sections, we cannot merge them.
309*85868e8aSDimitry Andric   assert(a->getParent() && b->getParent());
310*85868e8aSDimitry Andric   if (a->getParent() != b->getParent())
3110b57cec5SDimitry Andric     return false;
3120b57cec5SDimitry Andric 
3130b57cec5SDimitry Andric   if (a->areRelocsRela)
3140b57cec5SDimitry Andric     return constantEq(a, a->template relas<ELFT>(), b,
3150b57cec5SDimitry Andric                       b->template relas<ELFT>());
3160b57cec5SDimitry Andric   return constantEq(a, a->template rels<ELFT>(), b, b->template rels<ELFT>());
3170b57cec5SDimitry Andric }
3180b57cec5SDimitry Andric 
3190b57cec5SDimitry Andric // Compare two lists of relocations. Returns true if all pairs of
3200b57cec5SDimitry Andric // relocations point to the same section in terms of ICF.
3210b57cec5SDimitry Andric template <class ELFT>
3220b57cec5SDimitry Andric template <class RelTy>
3230b57cec5SDimitry Andric bool ICF<ELFT>::variableEq(const InputSection *secA, ArrayRef<RelTy> ra,
3240b57cec5SDimitry Andric                            const InputSection *secB, ArrayRef<RelTy> rb) {
3250b57cec5SDimitry Andric   assert(ra.size() == rb.size());
3260b57cec5SDimitry Andric 
3270b57cec5SDimitry Andric   for (size_t i = 0; i < ra.size(); ++i) {
3280b57cec5SDimitry Andric     // The two sections must be identical.
3290b57cec5SDimitry Andric     Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]);
3300b57cec5SDimitry Andric     Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]);
3310b57cec5SDimitry Andric     if (&sa == &sb)
3320b57cec5SDimitry Andric       continue;
3330b57cec5SDimitry Andric 
3340b57cec5SDimitry Andric     auto *da = cast<Defined>(&sa);
3350b57cec5SDimitry Andric     auto *db = cast<Defined>(&sb);
3360b57cec5SDimitry Andric 
3370b57cec5SDimitry Andric     // We already dealt with absolute and non-InputSection symbols in
3380b57cec5SDimitry Andric     // constantEq, and for InputSections we have already checked everything
3390b57cec5SDimitry Andric     // except the equivalence class.
3400b57cec5SDimitry Andric     if (!da->section)
3410b57cec5SDimitry Andric       continue;
3420b57cec5SDimitry Andric     auto *x = dyn_cast<InputSection>(da->section);
3430b57cec5SDimitry Andric     if (!x)
3440b57cec5SDimitry Andric       continue;
3450b57cec5SDimitry Andric     auto *y = cast<InputSection>(db->section);
3460b57cec5SDimitry Andric 
3470b57cec5SDimitry Andric     // Ineligible sections are in the special equivalence class 0.
3480b57cec5SDimitry Andric     // They can never be the same in terms of the equivalence class.
3490b57cec5SDimitry Andric     if (x->eqClass[current] == 0)
3500b57cec5SDimitry Andric       return false;
3510b57cec5SDimitry Andric     if (x->eqClass[current] != y->eqClass[current])
3520b57cec5SDimitry Andric       return false;
3530b57cec5SDimitry Andric   };
3540b57cec5SDimitry Andric 
3550b57cec5SDimitry Andric   return true;
3560b57cec5SDimitry Andric }
3570b57cec5SDimitry Andric 
3580b57cec5SDimitry Andric // Compare "moving" part of two InputSections, namely relocation targets.
3590b57cec5SDimitry Andric template <class ELFT>
3600b57cec5SDimitry Andric bool ICF<ELFT>::equalsVariable(const InputSection *a, const InputSection *b) {
3610b57cec5SDimitry Andric   if (a->areRelocsRela)
3620b57cec5SDimitry Andric     return variableEq(a, a->template relas<ELFT>(), b,
3630b57cec5SDimitry Andric                       b->template relas<ELFT>());
3640b57cec5SDimitry Andric   return variableEq(a, a->template rels<ELFT>(), b, b->template rels<ELFT>());
3650b57cec5SDimitry Andric }
3660b57cec5SDimitry Andric 
3670b57cec5SDimitry Andric template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t begin, size_t end) {
3680b57cec5SDimitry Andric   uint32_t eqClass = sections[begin]->eqClass[current];
3690b57cec5SDimitry Andric   for (size_t i = begin + 1; i < end; ++i)
3700b57cec5SDimitry Andric     if (eqClass != sections[i]->eqClass[current])
3710b57cec5SDimitry Andric       return i;
3720b57cec5SDimitry Andric   return end;
3730b57cec5SDimitry Andric }
3740b57cec5SDimitry Andric 
3750b57cec5SDimitry Andric // Sections in the same equivalence class are contiguous in Sections
3760b57cec5SDimitry Andric // vector. Therefore, Sections vector can be considered as contiguous
3770b57cec5SDimitry Andric // groups of sections, grouped by the class.
3780b57cec5SDimitry Andric //
3790b57cec5SDimitry Andric // This function calls Fn on every group within [Begin, End).
3800b57cec5SDimitry Andric template <class ELFT>
3810b57cec5SDimitry Andric void ICF<ELFT>::forEachClassRange(size_t begin, size_t end,
3820b57cec5SDimitry Andric                                   llvm::function_ref<void(size_t, size_t)> fn) {
3830b57cec5SDimitry Andric   while (begin < end) {
3840b57cec5SDimitry Andric     size_t mid = findBoundary(begin, end);
3850b57cec5SDimitry Andric     fn(begin, mid);
3860b57cec5SDimitry Andric     begin = mid;
3870b57cec5SDimitry Andric   }
3880b57cec5SDimitry Andric }
3890b57cec5SDimitry Andric 
3900b57cec5SDimitry Andric // Call Fn on each equivalence class.
3910b57cec5SDimitry Andric template <class ELFT>
3920b57cec5SDimitry Andric void ICF<ELFT>::forEachClass(llvm::function_ref<void(size_t, size_t)> fn) {
3930b57cec5SDimitry Andric   // If threading is disabled or the number of sections are
3940b57cec5SDimitry Andric   // too small to use threading, call Fn sequentially.
3950b57cec5SDimitry Andric   if (!threadsEnabled || sections.size() < 1024) {
3960b57cec5SDimitry Andric     forEachClassRange(0, sections.size(), fn);
3970b57cec5SDimitry Andric     ++cnt;
3980b57cec5SDimitry Andric     return;
3990b57cec5SDimitry Andric   }
4000b57cec5SDimitry Andric 
4010b57cec5SDimitry Andric   current = cnt % 2;
4020b57cec5SDimitry Andric   next = (cnt + 1) % 2;
4030b57cec5SDimitry Andric 
4040b57cec5SDimitry Andric   // Shard into non-overlapping intervals, and call Fn in parallel.
4050b57cec5SDimitry Andric   // The sharding must be completed before any calls to Fn are made
4060b57cec5SDimitry Andric   // so that Fn can modify the Chunks in its shard without causing data
4070b57cec5SDimitry Andric   // races.
4080b57cec5SDimitry Andric   const size_t numShards = 256;
4090b57cec5SDimitry Andric   size_t step = sections.size() / numShards;
4100b57cec5SDimitry Andric   size_t boundaries[numShards + 1];
4110b57cec5SDimitry Andric   boundaries[0] = 0;
4120b57cec5SDimitry Andric   boundaries[numShards] = sections.size();
4130b57cec5SDimitry Andric 
4140b57cec5SDimitry Andric   parallelForEachN(1, numShards, [&](size_t i) {
4150b57cec5SDimitry Andric     boundaries[i] = findBoundary((i - 1) * step, sections.size());
4160b57cec5SDimitry Andric   });
4170b57cec5SDimitry Andric 
4180b57cec5SDimitry Andric   parallelForEachN(1, numShards + 1, [&](size_t i) {
4190b57cec5SDimitry Andric     if (boundaries[i - 1] < boundaries[i])
4200b57cec5SDimitry Andric       forEachClassRange(boundaries[i - 1], boundaries[i], fn);
4210b57cec5SDimitry Andric   });
4220b57cec5SDimitry Andric   ++cnt;
4230b57cec5SDimitry Andric }
4240b57cec5SDimitry Andric 
4250b57cec5SDimitry Andric // Combine the hashes of the sections referenced by the given section into its
4260b57cec5SDimitry Andric // hash.
4270b57cec5SDimitry Andric template <class ELFT, class RelTy>
4280b57cec5SDimitry Andric static void combineRelocHashes(unsigned cnt, InputSection *isec,
4290b57cec5SDimitry Andric                                ArrayRef<RelTy> rels) {
4300b57cec5SDimitry Andric   uint32_t hash = isec->eqClass[cnt % 2];
4310b57cec5SDimitry Andric   for (RelTy rel : rels) {
4320b57cec5SDimitry Andric     Symbol &s = isec->template getFile<ELFT>()->getRelocTargetSym(rel);
4330b57cec5SDimitry Andric     if (auto *d = dyn_cast<Defined>(&s))
4340b57cec5SDimitry Andric       if (auto *relSec = dyn_cast_or_null<InputSection>(d->section))
4350b57cec5SDimitry Andric         hash += relSec->eqClass[cnt % 2];
4360b57cec5SDimitry Andric   }
4370b57cec5SDimitry Andric   // Set MSB to 1 to avoid collisions with non-hash IDs.
4380b57cec5SDimitry Andric   isec->eqClass[(cnt + 1) % 2] = hash | (1U << 31);
4390b57cec5SDimitry Andric }
4400b57cec5SDimitry Andric 
4410b57cec5SDimitry Andric static void print(const Twine &s) {
4420b57cec5SDimitry Andric   if (config->printIcfSections)
4430b57cec5SDimitry Andric     message(s);
4440b57cec5SDimitry Andric }
4450b57cec5SDimitry Andric 
4460b57cec5SDimitry Andric // The main function of ICF.
4470b57cec5SDimitry Andric template <class ELFT> void ICF<ELFT>::run() {
4480b57cec5SDimitry Andric   // Collect sections to merge.
449*85868e8aSDimitry Andric   for (InputSectionBase *sec : inputSections) {
450*85868e8aSDimitry Andric     auto *s = cast<InputSection>(sec);
4510b57cec5SDimitry Andric     if (isEligible(s))
4520b57cec5SDimitry Andric       sections.push_back(s);
453*85868e8aSDimitry Andric   }
4540b57cec5SDimitry Andric 
4550b57cec5SDimitry Andric   // Initially, we use hash values to partition sections.
4560b57cec5SDimitry Andric   parallelForEach(sections, [&](InputSection *s) {
4570b57cec5SDimitry Andric     s->eqClass[0] = xxHash64(s->data());
4580b57cec5SDimitry Andric   });
4590b57cec5SDimitry Andric 
4600b57cec5SDimitry Andric   for (unsigned cnt = 0; cnt != 2; ++cnt) {
4610b57cec5SDimitry Andric     parallelForEach(sections, [&](InputSection *s) {
4620b57cec5SDimitry Andric       if (s->areRelocsRela)
4630b57cec5SDimitry Andric         combineRelocHashes<ELFT>(cnt, s, s->template relas<ELFT>());
4640b57cec5SDimitry Andric       else
4650b57cec5SDimitry Andric         combineRelocHashes<ELFT>(cnt, s, s->template rels<ELFT>());
4660b57cec5SDimitry Andric     });
4670b57cec5SDimitry Andric   }
4680b57cec5SDimitry Andric 
4690b57cec5SDimitry Andric   // From now on, sections in Sections vector are ordered so that sections
4700b57cec5SDimitry Andric   // in the same equivalence class are consecutive in the vector.
4710b57cec5SDimitry Andric   llvm::stable_sort(sections, [](const InputSection *a, const InputSection *b) {
4720b57cec5SDimitry Andric     return a->eqClass[0] < b->eqClass[0];
4730b57cec5SDimitry Andric   });
4740b57cec5SDimitry Andric 
4750b57cec5SDimitry Andric   // Compare static contents and assign unique IDs for each static content.
4760b57cec5SDimitry Andric   forEachClass([&](size_t begin, size_t end) { segregate(begin, end, true); });
4770b57cec5SDimitry Andric 
4780b57cec5SDimitry Andric   // Split groups by comparing relocations until convergence is obtained.
4790b57cec5SDimitry Andric   do {
4800b57cec5SDimitry Andric     repeat = false;
4810b57cec5SDimitry Andric     forEachClass(
4820b57cec5SDimitry Andric         [&](size_t begin, size_t end) { segregate(begin, end, false); });
4830b57cec5SDimitry Andric   } while (repeat);
4840b57cec5SDimitry Andric 
4850b57cec5SDimitry Andric   log("ICF needed " + Twine(cnt) + " iterations");
4860b57cec5SDimitry Andric 
4870b57cec5SDimitry Andric   // Merge sections by the equivalence class.
4880b57cec5SDimitry Andric   forEachClassRange(0, sections.size(), [&](size_t begin, size_t end) {
4890b57cec5SDimitry Andric     if (end - begin == 1)
4900b57cec5SDimitry Andric       return;
4910b57cec5SDimitry Andric     print("selected section " + toString(sections[begin]));
4920b57cec5SDimitry Andric     for (size_t i = begin + 1; i < end; ++i) {
4930b57cec5SDimitry Andric       print("  removing identical section " + toString(sections[i]));
4940b57cec5SDimitry Andric       sections[begin]->replace(sections[i]);
4950b57cec5SDimitry Andric 
4960b57cec5SDimitry Andric       // At this point we know sections merged are fully identical and hence
4970b57cec5SDimitry Andric       // we want to remove duplicate implicit dependencies such as link order
4980b57cec5SDimitry Andric       // and relocation sections.
4990b57cec5SDimitry Andric       for (InputSection *isec : sections[i]->dependentSections)
5000b57cec5SDimitry Andric         isec->markDead();
5010b57cec5SDimitry Andric     }
5020b57cec5SDimitry Andric   });
503*85868e8aSDimitry Andric 
504*85868e8aSDimitry Andric   // InputSectionDescription::sections is populated by processSectionCommands().
505*85868e8aSDimitry Andric   // ICF may fold some input sections assigned to output sections. Remove them.
506*85868e8aSDimitry Andric   for (BaseCommand *base : script->sectionCommands)
507*85868e8aSDimitry Andric     if (auto *sec = dyn_cast<OutputSection>(base))
508*85868e8aSDimitry Andric       for (BaseCommand *sub_base : sec->sectionCommands)
509*85868e8aSDimitry Andric         if (auto *isd = dyn_cast<InputSectionDescription>(sub_base))
510*85868e8aSDimitry Andric           llvm::erase_if(isd->sections,
511*85868e8aSDimitry Andric                          [](InputSection *isec) { return !isec->isLive(); });
5120b57cec5SDimitry Andric }
5130b57cec5SDimitry Andric 
5140b57cec5SDimitry Andric // ICF entry point function.
515*85868e8aSDimitry Andric template <class ELFT> void doIcf() { ICF<ELFT>().run(); }
5160b57cec5SDimitry Andric 
517*85868e8aSDimitry Andric template void doIcf<ELF32LE>();
518*85868e8aSDimitry Andric template void doIcf<ELF32BE>();
519*85868e8aSDimitry Andric template void doIcf<ELF64LE>();
520*85868e8aSDimitry Andric template void doIcf<ELF64BE>();
521*85868e8aSDimitry Andric 
522*85868e8aSDimitry Andric } // namespace elf
523*85868e8aSDimitry Andric } // namespace lld
524