1 //===- ICF.cpp ------------------------------------------------------------===//
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Identical Code Folding is a feature to merge sections not by name (which
11 // is regular comdat handling) but by contents. If two non-writable sections
12 // have the same data, relocations, attributes, etc., then the two
13 // are considered identical and merged by the linker. This optimization
14 // makes outputs smaller.
16 // ICF is theoretically a problem of reducing graphs by merging as many
17 // identical subgraphs as possible if we consider sections as vertices and
18 // relocations as edges. It may sound simple, but it is a bit more
19 // complicated than you might think. The order of processing sections
20 // matters because merging two sections can make other sections, whose
21 // relocations now point to the same section, mergeable. Graphs may contain
22 // cycles. We need a sophisticated algorithm to do this properly and
25 // What we do in this file is this. We split sections into groups. Sections
26 // in the same group are considered identical.
28 // We begin by optimistically putting all sections into a single equivalence
29 // class. Then we apply a series of checks that split this initial
30 // equivalence class into more and more refined equivalence classes based on
31 // the properties by which a section can be distinguished.
33 // We begin by checking that the section contents and flags are the
34 // same. This only needs to be done once since these properties don't depend
35 // on the current equivalence class assignment.
37 // Then we split the equivalence classes based on checking that their
38 // relocations are the same, where relocation targets are compared by their
39 // equivalence class, not the concrete section. This may need to be done
40 // multiple times because as the equivalence classes are refined, two
41 // sections that had a relocation target in the same equivalence class may
42 // now target different equivalence classes, and hence these two sections
43 // must be put in different equivalence classes (whereas in the previous
44 // iteration they were not since the relocation target was the same.)
46 // Our algorithm is smart enough to merge the following mutually-recursive
49 // void foo() { bar(); }
50 // void bar() { foo(); }
52 // This algorithm is so-called "optimistic" algorithm described in
53 // http://research.google.com/pubs/pub36912.html. (Note that what GNU
54 // gold implemented is different from the optimistic algorithm.)
56 //===----------------------------------------------------------------------===//
60 #include "OutputSections.h"
61 #include "SymbolTable.h"
63 #include "llvm/ADT/Hashing.h"
64 #include "llvm/Object/ELF.h"
65 #include "llvm/Support/ELF.h"
66 #include "llvm/Support/raw_ostream.h"
69 using namespace lld::elf;
71 using namespace llvm::ELF;
72 using namespace llvm::object;
76 template <class ELFT> class ICF {
77 typedef typename ELFT::Shdr Elf_Shdr;
78 typedef typename ELFT::Sym Elf_Sym;
79 typedef typename ELFT::uint uintX_t;
80 typedef Elf_Rel_Impl<ELFT, false> Elf_Rel;
82 using Comparator = std::function<bool(const InputSection<ELFT> *,
83 const InputSection<ELFT> *)>;
91 static void setLive(SymbolTable<ELFT> *S);
92 static uint64_t relSize(InputSection<ELFT> *S);
93 static uint64_t getHash(InputSection<ELFT> *S);
94 static bool isEligible(InputSectionBase<ELFT> *Sec);
95 static std::vector<InputSection<ELFT> *> getSections();
97 void segregate(InputSection<ELFT> **Begin, InputSection<ELFT> **End,
100 void forEachGroup(std::vector<InputSection<ELFT> *> &V, Comparator Eq);
102 template <class RelTy>
103 static bool relocationEq(ArrayRef<RelTy> RA, ArrayRef<RelTy> RB);
105 template <class RelTy>
106 static bool variableEq(const InputSection<ELFT> *A,
107 const InputSection<ELFT> *B, ArrayRef<RelTy> RA,
110 static bool equalsConstant(const InputSection<ELFT> *A,
111 const InputSection<ELFT> *B);
113 static bool equalsVariable(const InputSection<ELFT> *A,
114 const InputSection<ELFT> *B);
119 // Returns a hash value for S. Note that the information about
120 // relocation targets is not included in the hash value.
121 template <class ELFT> uint64_t ICF<ELFT>::getHash(InputSection<ELFT> *S) {
122 uint64_t Flags = S->getSectionHdr()->sh_flags;
123 uint64_t H = hash_combine(Flags, S->getSize());
124 for (const Elf_Shdr *Rel : S->RelocSections)
125 H = hash_combine(H, (uint64_t)Rel->sh_size);
129 // Returns true if Sec is subject of ICF.
130 template <class ELFT> bool ICF<ELFT>::isEligible(InputSectionBase<ELFT> *Sec) {
131 if (!Sec || Sec == &InputSection<ELFT>::Discarded || !Sec->Live)
133 auto *S = dyn_cast<InputSection<ELFT>>(Sec);
137 // .init and .fini contains instructions that must be executed to
138 // initialize and finalize the process. They cannot and should not
140 StringRef Name = S->getSectionName();
141 if (Name == ".init" || Name == ".fini")
144 const Elf_Shdr &H = *S->getSectionHdr();
145 return (H.sh_flags & SHF_ALLOC) && (~H.sh_flags & SHF_WRITE);
148 template <class ELFT>
149 std::vector<InputSection<ELFT> *> ICF<ELFT>::getSections() {
150 std::vector<InputSection<ELFT> *> V;
151 for (const std::unique_ptr<ObjectFile<ELFT>> &F :
152 Symtab<ELFT>::X->getObjectFiles())
153 for (InputSectionBase<ELFT> *S : F->getSections())
155 V.push_back(cast<InputSection<ELFT>>(S));
159 // All sections between Begin and End must have the same group ID before
160 // you call this function. This function compare sections between Begin
161 // and End using Eq and assign new group IDs for new groups.
162 template <class ELFT>
163 void ICF<ELFT>::segregate(InputSection<ELFT> **Begin, InputSection<ELFT> **End,
165 // This loop rearranges [Begin, End) so that all sections that are
166 // equal in terms of Eq are contiguous. The algorithm is quadratic in
167 // the worst case, but that is not an issue in practice because the
168 // number of distinct sections in [Begin, End) is usually very small.
169 InputSection<ELFT> **I = Begin;
171 InputSection<ELFT> *Head = *I;
172 auto Bound = std::stable_partition(
173 I + 1, End, [&](InputSection<ELFT> *S) { return Eq(Head, S); });
176 uint64_t Id = NextId++;
177 for (; I != Bound; ++I)
182 template <class ELFT>
183 void ICF<ELFT>::forEachGroup(std::vector<InputSection<ELFT> *> &V,
185 for (InputSection<ELFT> **I = V.data(), **E = I + V.size(); I != E;) {
186 InputSection<ELFT> *Head = *I;
187 auto Bound = std::find_if(I + 1, E, [&](InputSection<ELFT> *S) {
188 return S->GroupId != Head->GroupId;
190 segregate(I, Bound, Eq);
195 // Compare two lists of relocations.
196 template <class ELFT>
197 template <class RelTy>
198 bool ICF<ELFT>::relocationEq(ArrayRef<RelTy> RelsA, ArrayRef<RelTy> RelsB) {
199 const RelTy *IA = RelsA.begin();
200 const RelTy *EA = RelsA.end();
201 const RelTy *IB = RelsB.begin();
202 const RelTy *EB = RelsB.end();
203 if (EA - IA != EB - IB)
205 for (; IA != EA; ++IA, ++IB)
206 if (IA->r_offset != IB->r_offset ||
207 IA->getType(Config->Mips64EL) != IB->getType(Config->Mips64EL) ||
208 getAddend<ELFT>(*IA) != getAddend<ELFT>(*IB))
213 // Compare "non-moving" part of two InputSections, namely everything
214 // except relocation targets.
215 template <class ELFT>
216 bool ICF<ELFT>::equalsConstant(const InputSection<ELFT> *A,
217 const InputSection<ELFT> *B) {
218 if (A->RelocSections.size() != B->RelocSections.size())
221 for (size_t I = 0, E = A->RelocSections.size(); I != E; ++I) {
222 const Elf_Shdr *RA = A->RelocSections[I];
223 const Elf_Shdr *RB = B->RelocSections[I];
224 ELFFile<ELFT> &FileA = A->File->getObj();
225 ELFFile<ELFT> &FileB = B->File->getObj();
226 if (RA->sh_type == SHT_RELA) {
227 if (!relocationEq(FileA.relas(RA), FileB.relas(RB)))
230 if (!relocationEq(FileA.rels(RA), FileB.rels(RB)))
235 return A->getSectionHdr()->sh_flags == B->getSectionHdr()->sh_flags &&
236 A->getSize() == B->getSize() &&
237 A->getSectionData() == B->getSectionData();
240 template <class ELFT>
241 template <class RelTy>
242 bool ICF<ELFT>::variableEq(const InputSection<ELFT> *A,
243 const InputSection<ELFT> *B, ArrayRef<RelTy> RelsA,
244 ArrayRef<RelTy> RelsB) {
245 const RelTy *IA = RelsA.begin();
246 const RelTy *EA = RelsA.end();
247 const RelTy *IB = RelsB.begin();
248 for (; IA != EA; ++IA, ++IB) {
249 SymbolBody &SA = A->File->getRelocTargetSym(*IA);
250 SymbolBody &SB = B->File->getRelocTargetSym(*IB);
254 // Or, the symbols should be pointing to the same section
255 // in terms of the group ID.
256 auto *DA = dyn_cast<DefinedRegular<ELFT>>(&SA);
257 auto *DB = dyn_cast<DefinedRegular<ELFT>>(&SB);
260 if (DA->Value != DB->Value)
262 InputSection<ELFT> *X = dyn_cast<InputSection<ELFT>>(DA->Section);
263 InputSection<ELFT> *Y = dyn_cast<InputSection<ELFT>>(DB->Section);
264 if (X && Y && X->GroupId && X->GroupId == Y->GroupId)
271 // Compare "moving" part of two InputSections, namely relocation targets.
272 template <class ELFT>
273 bool ICF<ELFT>::equalsVariable(const InputSection<ELFT> *A,
274 const InputSection<ELFT> *B) {
275 for (size_t I = 0, E = A->RelocSections.size(); I != E; ++I) {
276 const Elf_Shdr *RA = A->RelocSections[I];
277 const Elf_Shdr *RB = B->RelocSections[I];
278 ELFFile<ELFT> &FileA = A->File->getObj();
279 ELFFile<ELFT> &FileB = B->File->getObj();
280 if (RA->sh_type == SHT_RELA) {
281 if (!variableEq(A, B, FileA.relas(RA), FileB.relas(RB)))
284 if (!variableEq(A, B, FileA.rels(RA), FileB.rels(RB)))
291 // The main function of ICF.
292 template <class ELFT> void ICF<ELFT>::run() {
293 // Initially, we use hash values as section group IDs. Therefore,
294 // if two sections have the same ID, they are likely (but not
295 // guaranteed) to have the same static contents in terms of ICF.
296 std::vector<InputSection<ELFT> *> V = getSections();
297 for (InputSection<ELFT> *S : V)
298 // Set MSB on to avoid collisions with serial group IDs
299 S->GroupId = getHash(S) | (uint64_t(1) << 63);
301 // From now on, sections in V are ordered so that sections in
302 // the same group are consecutive in the vector.
303 std::stable_sort(V.begin(), V.end(),
304 [](InputSection<ELFT> *A, InputSection<ELFT> *B) {
305 return A->GroupId < B->GroupId;
308 // Compare static contents and assign unique IDs for each static content.
309 forEachGroup(V, equalsConstant);
311 // Split groups by comparing relocations until we get a convergence.
315 uint64_t Id = NextId;
316 forEachGroup(V, equalsVariable);
320 log("ICF needed " + Twine(Cnt) + " iterations.");
322 // Merge sections in the same group.
323 for (auto I = V.begin(), E = V.end(); I != E;) {
324 InputSection<ELFT> *Head = *I++;
325 auto Bound = std::find_if(I, E, [&](InputSection<ELFT> *S) {
326 return Head->GroupId != S->GroupId;
330 log("selected " + Head->getSectionName());
332 InputSection<ELFT> *S = *I++;
333 log(" removed " + S->getSectionName());
339 // ICF entry point function.
340 template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
342 template void elf::doIcf<ELF32LE>();
343 template void elf::doIcf<ELF32BE>();
344 template void elf::doIcf<ELF64LE>();
345 template void elf::doIcf<ELF64BE>();