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