1 //===- ICF.cpp ------------------------------------------------------------===//
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // ICF is short for Identical Code Folding. This is a size optimization to
11 // identify and merge two or more read-only sections (typically functions)
12 // that happened to have the same contents. It usually reduces output size
15 // In ICF, two sections are considered identical if they have the same
16 // section flags, section data, and relocations. Relocations are tricky,
17 // because two relocations are considered the same if they have the same
18 // relocation types, values, and if they point to the same sections *in
21 // Here is an example. If foo and bar defined below are compiled to the
22 // same machine instructions, ICF can and should merge the two, although
23 // their relocations point to each other.
25 // void foo() { bar(); }
26 // void bar() { foo(); }
28 // If you merge the two, their relocations point to the same section and
29 // thus you know they are mergeable, but how do you know they are
30 // mergeable in the first place? This is not an easy problem to solve.
32 // What we are doing in LLD is to partition sections into equivalence
33 // classes. Sections in the same equivalence class when the algorithm
34 // terminates are considered identical. Here are details:
36 // 1. First, we partition sections using their hash values as keys. Hash
37 // values contain section types, section contents and numbers of
38 // relocations. During this step, relocation targets are not taken into
39 // account. We just put sections that apparently differ into different
40 // equivalence classes.
42 // 2. Next, for each equivalence class, we visit sections to compare
43 // relocation targets. Relocation targets are considered equivalent if
44 // their targets are in the same equivalence class. Sections with
45 // different relocation targets are put into different equivalence
48 // 3. If we split an equivalence class in step 2, two relocations
49 // previously target the same equivalence class may now target
50 // different equivalence classes. Therefore, we repeat step 2 until a
51 // convergence is obtained.
53 // 4. For each equivalence class C, pick an arbitrary section in C, and
54 // merge all the other sections in C with it.
56 // For small programs, this algorithm needs 3-5 iterations. For large
57 // programs such as Chromium, it takes more than 20 iterations.
59 // This algorithm was mentioned as an "optimistic algorithm" in [1],
60 // though gold implements a different algorithm than this.
62 // We parallelize each step so that multiple threads can work on different
63 // equivalence classes concurrently. That gave us a large performance
64 // boost when applying ICF on large programs. For example, MSVC link.exe
65 // or GNU gold takes 10-20 seconds to apply ICF on Chromium, whose output
66 // size is about 1.5 GB, but LLD can finish it in less than 2 seconds on a
67 // 2.8 GHz 40 core machine. Even without threading, LLD's ICF is still
68 // faster than MSVC or gold though.
70 // [1] Safe ICF: Pointer Safe and Unwinding aware Identical Code Folding
72 // http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/36912.pdf
74 //===----------------------------------------------------------------------===//
78 #include "SymbolTable.h"
80 #include "lld/Common/Threads.h"
81 #include "llvm/ADT/Hashing.h"
82 #include "llvm/BinaryFormat/ELF.h"
83 #include "llvm/Object/ELF.h"
88 using namespace lld::elf;
90 using namespace llvm::ELF;
91 using namespace llvm::object;
94 template <class ELFT> class ICF {
99 void segregate(size_t Begin, size_t End, bool Constant);
101 template <class RelTy>
102 bool constantEq(const InputSection *A, ArrayRef<RelTy> RelsA,
103 const InputSection *B, ArrayRef<RelTy> RelsB);
105 template <class RelTy>
106 bool variableEq(const InputSection *A, ArrayRef<RelTy> RelsA,
107 const InputSection *B, ArrayRef<RelTy> RelsB);
109 bool equalsConstant(const InputSection *A, const InputSection *B);
110 bool equalsVariable(const InputSection *A, const InputSection *B);
112 size_t findBoundary(size_t Begin, size_t End);
114 void forEachClassRange(size_t Begin, size_t End,
115 std::function<void(size_t, size_t)> Fn);
117 void forEachClass(std::function<void(size_t, size_t)> Fn);
119 std::vector<InputSection *> Sections;
121 // We repeat the main loop while `Repeat` is true.
122 std::atomic<bool> Repeat;
124 // The main loop counter.
127 // We have two locations for equivalence classes. On the first iteration
128 // of the main loop, Class[0] has a valid value, and Class[1] contains
129 // garbage. We read equivalence classes from slot 0 and write to slot 1.
130 // So, Class[0] represents the current class, and Class[1] represents
131 // the next class. On each iteration, we switch their roles and use them
134 // Why are we doing this? Recall that other threads may be working on
135 // other equivalence classes in parallel. They may read sections that we
136 // are updating. We cannot update equivalence classes in place because
137 // it breaks the invariance that all possibly-identical sections must be
138 // in the same equivalence class at any moment. In other words, the for
139 // loop to update equivalence classes is not atomic, and that is
140 // observable from other threads. By writing new classes to other
141 // places, we can keep the invariance.
143 // Below, `Current` has the index of the current class, and `Next` has
144 // the index of the next class. If threading is enabled, they are either
147 // Note on single-thread: if that's the case, they are always (0, 0)
148 // because we can safely read the next class without worrying about race
149 // conditions. Using the same location makes this algorithm converge
150 // faster because it uses results of the same iteration earlier.
156 // Returns a hash value for S. Note that the information about
157 // relocation targets is not included in the hash value.
158 template <class ELFT> static uint32_t getHash(InputSection *S) {
159 return hash_combine(S->Flags, S->getSize(), S->NumRelocations, S->Data);
162 // Returns true if section S is subject of ICF.
163 static bool isEligible(InputSection *S) {
164 // Don't merge read only data sections unless --icf-data was passed.
165 if (!(S->Flags & SHF_EXECINSTR) && !Config->ICFData)
168 // .init and .fini contains instructions that must be executed to
169 // initialize and finalize the process. They cannot and should not
171 return S->Live && (S->Flags & SHF_ALLOC) && !(S->Flags & SHF_WRITE) &&
172 S->Name != ".init" && S->Name != ".fini";
175 // Split an equivalence class into smaller classes.
176 template <class ELFT>
177 void ICF<ELFT>::segregate(size_t Begin, size_t End, bool Constant) {
178 // This loop rearranges sections in [Begin, End) so that all sections
179 // that are equal in terms of equals{Constant,Variable} are contiguous
182 // The algorithm is quadratic in the worst case, but that is not an
183 // issue in practice because the number of the distinct sections in
184 // each range is usually very small.
186 while (Begin < End) {
187 // Divide [Begin, End) into two. Let Mid be the start index of the
190 std::stable_partition(Sections.begin() + Begin + 1,
191 Sections.begin() + End, [&](InputSection *S) {
193 return equalsConstant(Sections[Begin], S);
194 return equalsVariable(Sections[Begin], S);
196 size_t Mid = Bound - Sections.begin();
198 // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
199 // updating the sections in [Begin, Mid). We use Mid as an equivalence
200 // class ID because every group ends with a unique index.
201 for (size_t I = Begin; I < Mid; ++I)
202 Sections[I]->Class[Next] = Mid;
204 // If we created a group, we need to iterate the main loop again.
212 // Compare two lists of relocations.
213 template <class ELFT>
214 template <class RelTy>
215 bool ICF<ELFT>::constantEq(const InputSection *SecA, ArrayRef<RelTy> RA,
216 const InputSection *SecB, ArrayRef<RelTy> RB) {
217 if (RA.size() != RB.size())
220 for (size_t I = 0; I < RA.size(); ++I) {
221 if (RA[I].r_offset != RB[I].r_offset ||
222 RA[I].getType(Config->IsMips64EL) != RB[I].getType(Config->IsMips64EL))
225 uint64_t AddA = getAddend<ELFT>(RA[I]);
226 uint64_t AddB = getAddend<ELFT>(RB[I]);
228 Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
229 Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
236 auto *DA = dyn_cast<Defined>(&SA);
237 auto *DB = dyn_cast<Defined>(&SB);
241 // Relocations referring to absolute symbols are constant-equal if their
243 if (!DA->Section && !DB->Section && DA->Value + AddA == DB->Value + AddB)
245 if (!DA->Section || !DB->Section)
248 if (DA->Section->kind() != DB->Section->kind())
251 // Relocations referring to InputSections are constant-equal if their
252 // section offsets are equal.
253 if (isa<InputSection>(DA->Section)) {
254 if (DA->Value + AddA == DB->Value + AddB)
259 // Relocations referring to MergeInputSections are constant-equal if their
260 // offsets in the output section are equal.
261 auto *X = dyn_cast<MergeInputSection>(DA->Section);
264 auto *Y = cast<MergeInputSection>(DB->Section);
265 if (X->getParent() != Y->getParent())
269 SA.isSection() ? X->getOffset(AddA) : X->getOffset(DA->Value) + AddA;
271 SB.isSection() ? Y->getOffset(AddB) : Y->getOffset(DB->Value) + AddB;
272 if (OffsetA != OffsetB)
279 // Compare "non-moving" part of two InputSections, namely everything
280 // except relocation targets.
281 template <class ELFT>
282 bool ICF<ELFT>::equalsConstant(const InputSection *A, const InputSection *B) {
283 if (A->NumRelocations != B->NumRelocations || A->Flags != B->Flags ||
284 A->getSize() != B->getSize() || A->Data != B->Data)
287 if (A->AreRelocsRela)
288 return constantEq(A, A->template relas<ELFT>(), B,
289 B->template relas<ELFT>());
290 return constantEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
293 // Compare two lists of relocations. Returns true if all pairs of
294 // relocations point to the same section in terms of ICF.
295 template <class ELFT>
296 template <class RelTy>
297 bool ICF<ELFT>::variableEq(const InputSection *SecA, ArrayRef<RelTy> RA,
298 const InputSection *SecB, ArrayRef<RelTy> RB) {
299 assert(RA.size() == RB.size());
301 for (size_t I = 0; I < RA.size(); ++I) {
302 // The two sections must be identical.
303 Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
304 Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
308 auto *DA = cast<Defined>(&SA);
309 auto *DB = cast<Defined>(&SB);
311 // We already dealt with absolute and non-InputSection symbols in
312 // constantEq, and for InputSections we have already checked everything
313 // except the equivalence class.
316 auto *X = dyn_cast<InputSection>(DA->Section);
319 auto *Y = cast<InputSection>(DB->Section);
321 // Ineligible sections are in the special equivalence class 0.
322 // They can never be the same in terms of the equivalence class.
323 if (X->Class[Current] == 0)
325 if (X->Class[Current] != Y->Class[Current])
332 // Compare "moving" part of two InputSections, namely relocation targets.
333 template <class ELFT>
334 bool ICF<ELFT>::equalsVariable(const InputSection *A, const InputSection *B) {
335 if (A->AreRelocsRela)
336 return variableEq(A, A->template relas<ELFT>(), B,
337 B->template relas<ELFT>());
338 return variableEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
341 template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t Begin, size_t End) {
342 uint32_t Class = Sections[Begin]->Class[Current];
343 for (size_t I = Begin + 1; I < End; ++I)
344 if (Class != Sections[I]->Class[Current])
349 // Sections in the same equivalence class are contiguous in Sections
350 // vector. Therefore, Sections vector can be considered as contiguous
351 // groups of sections, grouped by the class.
353 // This function calls Fn on every group that starts within [Begin, End).
354 // Note that a group must start in that range but doesn't necessarily
355 // have to end before End.
356 template <class ELFT>
357 void ICF<ELFT>::forEachClassRange(size_t Begin, size_t End,
358 std::function<void(size_t, size_t)> Fn) {
360 Begin = findBoundary(Begin - 1, End);
362 while (Begin < End) {
363 size_t Mid = findBoundary(Begin, Sections.size());
369 // Call Fn on each equivalence class.
370 template <class ELFT>
371 void ICF<ELFT>::forEachClass(std::function<void(size_t, size_t)> Fn) {
372 // If threading is disabled or the number of sections are
373 // too small to use threading, call Fn sequentially.
374 if (!ThreadsEnabled || Sections.size() < 1024) {
375 forEachClassRange(0, Sections.size(), Fn);
381 Next = (Cnt + 1) % 2;
383 // Split sections into 256 shards and call Fn in parallel.
384 size_t NumShards = 256;
385 size_t Step = Sections.size() / NumShards;
386 parallelForEachN(0, NumShards, [&](size_t I) {
387 size_t End = (I == NumShards - 1) ? Sections.size() : (I + 1) * Step;
388 forEachClassRange(I * Step, End, Fn);
393 // The main function of ICF.
394 template <class ELFT> void ICF<ELFT>::run() {
395 // Collect sections to merge.
396 for (InputSectionBase *Sec : InputSections)
397 if (auto *S = dyn_cast<InputSection>(Sec))
399 Sections.push_back(S);
401 // Initially, we use hash values to partition sections.
402 parallelForEach(Sections, [&](InputSection *S) {
403 // Set MSB to 1 to avoid collisions with non-hash IDs.
404 S->Class[0] = getHash<ELFT>(S) | (1 << 31);
407 // From now on, sections in Sections vector are ordered so that sections
408 // in the same equivalence class are consecutive in the vector.
409 std::stable_sort(Sections.begin(), Sections.end(),
410 [](InputSection *A, InputSection *B) {
411 return A->Class[0] < B->Class[0];
414 // Compare static contents and assign unique IDs for each static content.
415 forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
417 // Split groups by comparing relocations until convergence is obtained.
421 [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
424 log("ICF needed " + Twine(Cnt) + " iterations");
426 // Merge sections by the equivalence class.
427 forEachClass([&](size_t Begin, size_t End) {
428 if (End - Begin == 1)
431 log("selected " + Sections[Begin]->Name);
432 for (size_t I = Begin + 1; I < End; ++I) {
433 log(" removed " + Sections[I]->Name);
434 Sections[Begin]->replace(Sections[I]);
438 // Mark ARM Exception Index table sections that refer to folded code
439 // sections as not live. These sections have an implict dependency
440 // via the link order dependency.
441 if (Config->EMachine == EM_ARM)
442 for (InputSectionBase *Sec : InputSections)
443 if (auto *S = dyn_cast<InputSection>(Sec))
444 if (S->Flags & SHF_LINK_ORDER)
445 S->Live = S->getLinkOrderDep()->Live;
448 // ICF entry point function.
449 template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
451 template void elf::doIcf<ELF32LE>();
452 template void elf::doIcf<ELF32BE>();
453 template void elf::doIcf<ELF64LE>();
454 template void elf::doIcf<ELF64BE>();