diff options
Diffstat (limited to 'contrib/llvm-project/lld/ELF/ICF.cpp')
| -rw-r--r-- | contrib/llvm-project/lld/ELF/ICF.cpp | 510 |
1 files changed, 510 insertions, 0 deletions
diff --git a/contrib/llvm-project/lld/ELF/ICF.cpp b/contrib/llvm-project/lld/ELF/ICF.cpp new file mode 100644 index 000000000000..8b01d06b0248 --- /dev/null +++ b/contrib/llvm-project/lld/ELF/ICF.cpp @@ -0,0 +1,510 @@ +//===- ICF.cpp ------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// ICF is short for Identical Code Folding. This is a size optimization to +// identify and merge two or more read-only sections (typically functions) +// that happened to have the same contents. It usually reduces output size +// by a few percent. +// +// In ICF, two sections are considered identical if they have the same +// section flags, section data, and relocations. Relocations are tricky, +// because two relocations are considered the same if they have the same +// relocation types, values, and if they point to the same sections *in +// terms of ICF*. +// +// Here is an example. If foo and bar defined below are compiled to the +// same machine instructions, ICF can and should merge the two, although +// their relocations point to each other. +// +// void foo() { bar(); } +// void bar() { foo(); } +// +// If you merge the two, their relocations point to the same section and +// thus you know they are mergeable, but how do you know they are +// mergeable in the first place? This is not an easy problem to solve. +// +// What we are doing in LLD is to partition sections into equivalence +// classes. Sections in the same equivalence class when the algorithm +// terminates are considered identical. Here are details: +// +// 1. First, we partition sections using their hash values as keys. Hash +// values contain section types, section contents and numbers of +// relocations. During this step, relocation targets are not taken into +// account. We just put sections that apparently differ into different +// equivalence classes. +// +// 2. Next, for each equivalence class, we visit sections to compare +// relocation targets. Relocation targets are considered equivalent if +// their targets are in the same equivalence class. Sections with +// different relocation targets are put into different equivalence +// clases. +// +// 3. If we split an equivalence class in step 2, two relocations +// previously target the same equivalence class may now target +// different equivalence classes. Therefore, we repeat step 2 until a +// convergence is obtained. +// +// 4. For each equivalence class C, pick an arbitrary section in C, and +// merge all the other sections in C with it. +// +// For small programs, this algorithm needs 3-5 iterations. For large +// programs such as Chromium, it takes more than 20 iterations. +// +// This algorithm was mentioned as an "optimistic algorithm" in [1], +// though gold implements a different algorithm than this. +// +// We parallelize each step so that multiple threads can work on different +// equivalence classes concurrently. That gave us a large performance +// boost when applying ICF on large programs. For example, MSVC link.exe +// or GNU gold takes 10-20 seconds to apply ICF on Chromium, whose output +// size is about 1.5 GB, but LLD can finish it in less than 2 seconds on a +// 2.8 GHz 40 core machine. Even without threading, LLD's ICF is still +// faster than MSVC or gold though. +// +// [1] Safe ICF: Pointer Safe and Unwinding aware Identical Code Folding +// in the Gold Linker +// http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/36912.pdf +// +//===----------------------------------------------------------------------===// + +#include "ICF.h" +#include "Config.h" +#include "SymbolTable.h" +#include "Symbols.h" +#include "SyntheticSections.h" +#include "Writer.h" +#include "lld/Common/Threads.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/BinaryFormat/ELF.h" +#include "llvm/Object/ELF.h" +#include "llvm/Support/xxhash.h" +#include <algorithm> +#include <atomic> + +using namespace lld; +using namespace lld::elf; +using namespace llvm; +using namespace llvm::ELF; +using namespace llvm::object; + +namespace { +template <class ELFT> class ICF { +public: + void run(); + +private: + void segregate(size_t begin, size_t end, bool constant); + + template <class RelTy> + bool constantEq(const InputSection *a, ArrayRef<RelTy> relsA, + const InputSection *b, ArrayRef<RelTy> relsB); + + template <class RelTy> + bool variableEq(const InputSection *a, ArrayRef<RelTy> relsA, + const InputSection *b, ArrayRef<RelTy> relsB); + + bool equalsConstant(const InputSection *a, const InputSection *b); + bool equalsVariable(const InputSection *a, const InputSection *b); + + size_t findBoundary(size_t begin, size_t end); + + void forEachClassRange(size_t begin, size_t end, + llvm::function_ref<void(size_t, size_t)> fn); + + void forEachClass(llvm::function_ref<void(size_t, size_t)> fn); + + std::vector<InputSection *> sections; + + // We repeat the main loop while `Repeat` is true. + std::atomic<bool> repeat; + + // The main loop counter. + int cnt = 0; + + // We have two locations for equivalence classes. On the first iteration + // of the main loop, Class[0] has a valid value, and Class[1] contains + // garbage. We read equivalence classes from slot 0 and write to slot 1. + // So, Class[0] represents the current class, and Class[1] represents + // the next class. On each iteration, we switch their roles and use them + // alternately. + // + // Why are we doing this? Recall that other threads may be working on + // other equivalence classes in parallel. They may read sections that we + // are updating. We cannot update equivalence classes in place because + // it breaks the invariance that all possibly-identical sections must be + // in the same equivalence class at any moment. In other words, the for + // loop to update equivalence classes is not atomic, and that is + // observable from other threads. By writing new classes to other + // places, we can keep the invariance. + // + // Below, `Current` has the index of the current class, and `Next` has + // the index of the next class. If threading is enabled, they are either + // (0, 1) or (1, 0). + // + // Note on single-thread: if that's the case, they are always (0, 0) + // because we can safely read the next class without worrying about race + // conditions. Using the same location makes this algorithm converge + // faster because it uses results of the same iteration earlier. + int current = 0; + int next = 0; +}; +} + +// Returns true if section S is subject of ICF. +static bool isEligible(InputSection *s) { + if (!s->isLive() || s->keepUnique || !(s->flags & SHF_ALLOC)) + return false; + + // Don't merge writable sections. .data.rel.ro sections are marked as writable + // but are semantically read-only. + if ((s->flags & SHF_WRITE) && s->name != ".data.rel.ro" && + !s->name.startswith(".data.rel.ro.")) + return false; + + // SHF_LINK_ORDER sections are ICF'd as a unit with their dependent sections, + // so we don't consider them for ICF individually. + if (s->flags & SHF_LINK_ORDER) + return false; + + // Don't merge synthetic sections as their Data member is not valid and empty. + // The Data member needs to be valid for ICF as it is used by ICF to determine + // the equality of section contents. + if (isa<SyntheticSection>(s)) + return false; + + // .init and .fini contains instructions that must be executed to initialize + // and finalize the process. They cannot and should not be merged. + if (s->name == ".init" || s->name == ".fini") + return false; + + // A user program may enumerate sections named with a C identifier using + // __start_* and __stop_* symbols. We cannot ICF any such sections because + // that could change program semantics. + if (isValidCIdentifier(s->name)) + return false; + + return true; +} + +// Split an equivalence class into smaller classes. +template <class ELFT> +void ICF<ELFT>::segregate(size_t begin, size_t end, bool constant) { + // This loop rearranges sections in [Begin, End) so that all sections + // that are equal in terms of equals{Constant,Variable} are contiguous + // in [Begin, End). + // + // The algorithm is quadratic in the worst case, but that is not an + // issue in practice because the number of the distinct sections in + // each range is usually very small. + + while (begin < end) { + // Divide [Begin, End) into two. Let Mid be the start index of the + // second group. + auto bound = + std::stable_partition(sections.begin() + begin + 1, + sections.begin() + end, [&](InputSection *s) { + if (constant) + return equalsConstant(sections[begin], s); + return equalsVariable(sections[begin], s); + }); + size_t mid = bound - sections.begin(); + + // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by + // updating the sections in [Begin, Mid). We use Mid as an equivalence + // class ID because every group ends with a unique index. + for (size_t i = begin; i < mid; ++i) + sections[i]->eqClass[next] = mid; + + // If we created a group, we need to iterate the main loop again. + if (mid != end) + repeat = true; + + begin = mid; + } +} + +// Compare two lists of relocations. +template <class ELFT> +template <class RelTy> +bool ICF<ELFT>::constantEq(const InputSection *secA, ArrayRef<RelTy> ra, + const InputSection *secB, ArrayRef<RelTy> rb) { + for (size_t i = 0; i < ra.size(); ++i) { + if (ra[i].r_offset != rb[i].r_offset || + ra[i].getType(config->isMips64EL) != rb[i].getType(config->isMips64EL)) + return false; + + uint64_t addA = getAddend<ELFT>(ra[i]); + uint64_t addB = getAddend<ELFT>(rb[i]); + + Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]); + Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]); + if (&sa == &sb) { + if (addA == addB) + continue; + return false; + } + + auto *da = dyn_cast<Defined>(&sa); + auto *db = dyn_cast<Defined>(&sb); + + // Placeholder symbols generated by linker scripts look the same now but + // may have different values later. + if (!da || !db || da->scriptDefined || db->scriptDefined) + return false; + + // Relocations referring to absolute symbols are constant-equal if their + // values are equal. + if (!da->section && !db->section && da->value + addA == db->value + addB) + continue; + if (!da->section || !db->section) + return false; + + if (da->section->kind() != db->section->kind()) + return false; + + // Relocations referring to InputSections are constant-equal if their + // section offsets are equal. + if (isa<InputSection>(da->section)) { + if (da->value + addA == db->value + addB) + continue; + return false; + } + + // Relocations referring to MergeInputSections are constant-equal if their + // offsets in the output section are equal. + auto *x = dyn_cast<MergeInputSection>(da->section); + if (!x) + return false; + auto *y = cast<MergeInputSection>(db->section); + if (x->getParent() != y->getParent()) + return false; + + uint64_t offsetA = + sa.isSection() ? x->getOffset(addA) : x->getOffset(da->value) + addA; + uint64_t offsetB = + sb.isSection() ? y->getOffset(addB) : y->getOffset(db->value) + addB; + if (offsetA != offsetB) + return false; + } + + return true; +} + +// Compare "non-moving" part of two InputSections, namely everything +// except relocation targets. +template <class ELFT> +bool ICF<ELFT>::equalsConstant(const InputSection *a, const InputSection *b) { + if (a->numRelocations != b->numRelocations || a->flags != b->flags || + a->getSize() != b->getSize() || a->data() != b->data()) + return false; + + // If two sections have different output sections, we cannot merge them. + // FIXME: This doesn't do the right thing in the case where there is a linker + // script. We probably need to move output section assignment before ICF to + // get the correct behaviour here. + if (getOutputSectionName(a) != getOutputSectionName(b)) + return false; + + if (a->areRelocsRela) + return constantEq(a, a->template relas<ELFT>(), b, + b->template relas<ELFT>()); + return constantEq(a, a->template rels<ELFT>(), b, b->template rels<ELFT>()); +} + +// Compare two lists of relocations. Returns true if all pairs of +// relocations point to the same section in terms of ICF. +template <class ELFT> +template <class RelTy> +bool ICF<ELFT>::variableEq(const InputSection *secA, ArrayRef<RelTy> ra, + const InputSection *secB, ArrayRef<RelTy> rb) { + assert(ra.size() == rb.size()); + + for (size_t i = 0; i < ra.size(); ++i) { + // The two sections must be identical. + Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]); + Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]); + if (&sa == &sb) + continue; + + auto *da = cast<Defined>(&sa); + auto *db = cast<Defined>(&sb); + + // We already dealt with absolute and non-InputSection symbols in + // constantEq, and for InputSections we have already checked everything + // except the equivalence class. + if (!da->section) + continue; + auto *x = dyn_cast<InputSection>(da->section); + if (!x) + continue; + auto *y = cast<InputSection>(db->section); + + // Ineligible sections are in the special equivalence class 0. + // They can never be the same in terms of the equivalence class. + if (x->eqClass[current] == 0) + return false; + if (x->eqClass[current] != y->eqClass[current]) + return false; + }; + + return true; +} + +// Compare "moving" part of two InputSections, namely relocation targets. +template <class ELFT> +bool ICF<ELFT>::equalsVariable(const InputSection *a, const InputSection *b) { + if (a->areRelocsRela) + return variableEq(a, a->template relas<ELFT>(), b, + b->template relas<ELFT>()); + return variableEq(a, a->template rels<ELFT>(), b, b->template rels<ELFT>()); +} + +template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t begin, size_t end) { + uint32_t eqClass = sections[begin]->eqClass[current]; + for (size_t i = begin + 1; i < end; ++i) + if (eqClass != sections[i]->eqClass[current]) + return i; + return end; +} + +// Sections in the same equivalence class are contiguous in Sections +// vector. Therefore, Sections vector can be considered as contiguous +// groups of sections, grouped by the class. +// +// This function calls Fn on every group within [Begin, End). +template <class ELFT> +void ICF<ELFT>::forEachClassRange(size_t begin, size_t end, + llvm::function_ref<void(size_t, size_t)> fn) { + while (begin < end) { + size_t mid = findBoundary(begin, end); + fn(begin, mid); + begin = mid; + } +} + +// Call Fn on each equivalence class. +template <class ELFT> +void ICF<ELFT>::forEachClass(llvm::function_ref<void(size_t, size_t)> fn) { + // If threading is disabled or the number of sections are + // too small to use threading, call Fn sequentially. + if (!threadsEnabled || sections.size() < 1024) { + forEachClassRange(0, sections.size(), fn); + ++cnt; + return; + } + + current = cnt % 2; + next = (cnt + 1) % 2; + + // Shard into non-overlapping intervals, and call Fn in parallel. + // The sharding must be completed before any calls to Fn are made + // so that Fn can modify the Chunks in its shard without causing data + // races. + const size_t numShards = 256; + size_t step = sections.size() / numShards; + size_t boundaries[numShards + 1]; + boundaries[0] = 0; + boundaries[numShards] = sections.size(); + + parallelForEachN(1, numShards, [&](size_t i) { + boundaries[i] = findBoundary((i - 1) * step, sections.size()); + }); + + parallelForEachN(1, numShards + 1, [&](size_t i) { + if (boundaries[i - 1] < boundaries[i]) + forEachClassRange(boundaries[i - 1], boundaries[i], fn); + }); + ++cnt; +} + +// Combine the hashes of the sections referenced by the given section into its +// hash. +template <class ELFT, class RelTy> +static void combineRelocHashes(unsigned cnt, InputSection *isec, + ArrayRef<RelTy> rels) { + uint32_t hash = isec->eqClass[cnt % 2]; + for (RelTy rel : rels) { + Symbol &s = isec->template getFile<ELFT>()->getRelocTargetSym(rel); + if (auto *d = dyn_cast<Defined>(&s)) + if (auto *relSec = dyn_cast_or_null<InputSection>(d->section)) + hash += relSec->eqClass[cnt % 2]; + } + // Set MSB to 1 to avoid collisions with non-hash IDs. + isec->eqClass[(cnt + 1) % 2] = hash | (1U << 31); +} + +static void print(const Twine &s) { + if (config->printIcfSections) + message(s); +} + +// The main function of ICF. +template <class ELFT> void ICF<ELFT>::run() { + // Collect sections to merge. + for (InputSectionBase *sec : inputSections) + if (auto *s = dyn_cast<InputSection>(sec)) + if (isEligible(s)) + sections.push_back(s); + + // Initially, we use hash values to partition sections. + parallelForEach(sections, [&](InputSection *s) { + s->eqClass[0] = xxHash64(s->data()); + }); + + for (unsigned cnt = 0; cnt != 2; ++cnt) { + parallelForEach(sections, [&](InputSection *s) { + if (s->areRelocsRela) + combineRelocHashes<ELFT>(cnt, s, s->template relas<ELFT>()); + else + combineRelocHashes<ELFT>(cnt, s, s->template rels<ELFT>()); + }); + } + + // From now on, sections in Sections vector are ordered so that sections + // in the same equivalence class are consecutive in the vector. + llvm::stable_sort(sections, [](const InputSection *a, const InputSection *b) { + return a->eqClass[0] < b->eqClass[0]; + }); + + // Compare static contents and assign unique IDs for each static content. + forEachClass([&](size_t begin, size_t end) { segregate(begin, end, true); }); + + // Split groups by comparing relocations until convergence is obtained. + do { + repeat = false; + forEachClass( + [&](size_t begin, size_t end) { segregate(begin, end, false); }); + } while (repeat); + + log("ICF needed " + Twine(cnt) + " iterations"); + + // Merge sections by the equivalence class. + forEachClassRange(0, sections.size(), [&](size_t begin, size_t end) { + if (end - begin == 1) + return; + print("selected section " + toString(sections[begin])); + for (size_t i = begin + 1; i < end; ++i) { + print(" removing identical section " + toString(sections[i])); + sections[begin]->replace(sections[i]); + + // At this point we know sections merged are fully identical and hence + // we want to remove duplicate implicit dependencies such as link order + // and relocation sections. + for (InputSection *isec : sections[i]->dependentSections) + isec->markDead(); + } + }); +} + +// ICF entry point function. +template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); } + +template void elf::doIcf<ELF32LE>(); +template void elf::doIcf<ELF32BE>(); +template void elf::doIcf<ELF64LE>(); +template void elf::doIcf<ELF64BE>(); |