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"
81 #include "llvm/ADT/Hashing.h"
82 #include "llvm/Object/ELF.h"
83 #include "llvm/Support/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(ArrayRef<RelTy> RelsA, ArrayRef<RelTy> RelsB);
104 template <class RelTy>
105 bool variableEq(const InputSection<ELFT> *A, ArrayRef<RelTy> RelsA,
106 const InputSection<ELFT> *B, ArrayRef<RelTy> RelsB);
108 bool equalsConstant(const InputSection<ELFT> *A, const InputSection<ELFT> *B);
109 bool equalsVariable(const InputSection<ELFT> *A, const InputSection<ELFT> *B);
111 size_t findBoundary(size_t Begin, size_t End);
113 void forEachClassRange(size_t Begin, size_t End,
114 std::function<void(size_t, size_t)> Fn);
116 void forEachClass(std::function<void(size_t, size_t)> Fn);
118 std::vector<InputSection<ELFT> *> Sections;
120 // We repeat the main loop while `Repeat` is true.
121 std::atomic<bool> Repeat;
123 // The main loop counter.
126 // We have two locations for equivalence classes. On the first iteration
127 // of the main loop, Class[0] has a valid value, and Class[1] contains
128 // garbage. We read equivalence classes from slot 0 and write to slot 1.
129 // So, Class[0] represents the current class, and Class[1] represents
130 // the next class. On each iteration, we switch their roles and use them
133 // Why are we doing this? Recall that other threads may be working on
134 // other equivalence classes in parallel. They may read sections that we
135 // are updating. We cannot update equivalence classes in place because
136 // it breaks the invariance that all possibly-identical sections must be
137 // in the same equivalence class at any moment. In other words, the for
138 // loop to update equivalence classes is not atomic, and that is
139 // observable from other threads. By writing new classes to other
140 // places, we can keep the invariance.
142 // Below, `Current` has the index of the current class, and `Next` has
143 // the index of the next class. If threading is enabled, they are either
146 // Note on single-thread: if that's the case, they are always (0, 0)
147 // because we can safely read the next class without worrying about race
148 // conditions. Using the same location makes this algorithm converge
149 // faster because it uses results of the same iteration earlier.
155 // Returns a hash value for S. Note that the information about
156 // relocation targets is not included in the hash value.
157 template <class ELFT> static uint32_t getHash(InputSection<ELFT> *S) {
158 return hash_combine(S->Flags, S->getSize(), S->NumRelocations);
161 // Returns true if section S is subject of ICF.
162 template <class ELFT> static bool isEligible(InputSection<ELFT> *S) {
163 // .init and .fini contains instructions that must be executed to
164 // initialize and finalize the process. They cannot and should not
166 return S->Live && (S->Flags & SHF_ALLOC) && !(S->Flags & SHF_WRITE) &&
167 S->Name != ".init" && S->Name != ".fini";
170 // Split an equivalence class into smaller classes.
171 template <class ELFT>
172 void ICF<ELFT>::segregate(size_t Begin, size_t End, bool Constant) {
173 // This loop rearranges sections in [Begin, End) so that all sections
174 // that are equal in terms of equals{Constant,Variable} are contiguous
177 // The algorithm is quadratic in the worst case, but that is not an
178 // issue in practice because the number of the distinct sections in
179 // each range is usually very small.
181 while (Begin < End) {
182 // Divide [Begin, End) into two. Let Mid be the start index of the
184 auto Bound = std::stable_partition(
185 Sections.begin() + Begin + 1, Sections.begin() + End,
186 [&](InputSection<ELFT> *S) {
188 return equalsConstant(Sections[Begin], S);
189 return equalsVariable(Sections[Begin], S);
191 size_t Mid = Bound - Sections.begin();
193 // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
194 // updating the sections in [Begin, End). We use Mid as an equivalence
195 // class ID because every group ends with a unique index.
196 for (size_t I = Begin; I < Mid; ++I)
197 Sections[I]->Class[Next] = Mid;
199 // If we created a group, we need to iterate the main loop again.
207 // Compare two lists of relocations.
208 template <class ELFT>
209 template <class RelTy>
210 bool ICF<ELFT>::constantEq(ArrayRef<RelTy> RelsA, ArrayRef<RelTy> RelsB) {
211 auto Eq = [](const RelTy &A, const RelTy &B) {
212 return A.r_offset == B.r_offset &&
213 A.getType(Config->Mips64EL) == B.getType(Config->Mips64EL) &&
214 getAddend<ELFT>(A) == getAddend<ELFT>(B);
217 return RelsA.size() == RelsB.size() &&
218 std::equal(RelsA.begin(), RelsA.end(), RelsB.begin(), Eq);
221 // Compare "non-moving" part of two InputSections, namely everything
222 // except relocation targets.
223 template <class ELFT>
224 bool ICF<ELFT>::equalsConstant(const InputSection<ELFT> *A,
225 const InputSection<ELFT> *B) {
226 if (A->NumRelocations != B->NumRelocations || A->Flags != B->Flags ||
227 A->getSize() != B->getSize() || A->Data != B->Data)
230 if (A->AreRelocsRela)
231 return constantEq(A->relas(), B->relas());
232 return constantEq(A->rels(), B->rels());
235 // Compare two lists of relocations. Returns true if all pairs of
236 // relocations point to the same section in terms of ICF.
237 template <class ELFT>
238 template <class RelTy>
239 bool ICF<ELFT>::variableEq(const InputSection<ELFT> *A, ArrayRef<RelTy> RelsA,
240 const InputSection<ELFT> *B, ArrayRef<RelTy> RelsB) {
241 auto Eq = [&](const RelTy &RA, const RelTy &RB) {
242 // The two sections must be identical.
243 SymbolBody &SA = A->getFile()->getRelocTargetSym(RA);
244 SymbolBody &SB = B->getFile()->getRelocTargetSym(RB);
248 // Or, the two sections must be in the same equivalence class.
249 auto *DA = dyn_cast<DefinedRegular<ELFT>>(&SA);
250 auto *DB = dyn_cast<DefinedRegular<ELFT>>(&SB);
253 if (DA->Value != DB->Value)
256 auto *X = dyn_cast<InputSection<ELFT>>(DA->Section);
257 auto *Y = dyn_cast<InputSection<ELFT>>(DB->Section);
261 // Ineligible sections are in the special equivalence class 0.
262 // They can never be the same in terms of the equivalence class.
263 if (X->Class[Current] == 0)
266 return X->Class[Current] == Y->Class[Current];
269 return std::equal(RelsA.begin(), RelsA.end(), RelsB.begin(), Eq);
272 // Compare "moving" part of two InputSections, namely relocation targets.
273 template <class ELFT>
274 bool ICF<ELFT>::equalsVariable(const InputSection<ELFT> *A,
275 const InputSection<ELFT> *B) {
276 if (A->AreRelocsRela)
277 return variableEq(A, A->relas(), B, B->relas());
278 return variableEq(A, A->rels(), B, B->rels());
281 template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t Begin, size_t End) {
282 uint32_t Class = Sections[Begin]->Class[Current];
283 for (size_t I = Begin + 1; I < End; ++I)
284 if (Class != Sections[I]->Class[Current])
289 // Sections in the same equivalence class are contiguous in Sections
290 // vector. Therefore, Sections vector can be considered as contiguous
291 // groups of sections, grouped by the class.
293 // This function calls Fn on every group that starts within [Begin, End).
294 // Note that a group must starts in that range but doesn't necessarily
295 // have to end before End.
296 template <class ELFT>
297 void ICF<ELFT>::forEachClassRange(size_t Begin, size_t End,
298 std::function<void(size_t, size_t)> Fn) {
300 Begin = findBoundary(Begin - 1, End);
302 while (Begin < End) {
303 size_t Mid = findBoundary(Begin, Sections.size());
309 // Call Fn on each equivalence class.
310 template <class ELFT>
311 void ICF<ELFT>::forEachClass(std::function<void(size_t, size_t)> Fn) {
312 // If threading is disabled or the number of sections are
313 // too small to use threading, call Fn sequentially.
314 if (!Config->Threads || Sections.size() < 1024) {
315 forEachClassRange(0, Sections.size(), Fn);
321 Next = (Cnt + 1) % 2;
323 // Split sections into 256 shards and call Fn in parallel.
324 size_t NumShards = 256;
325 size_t Step = Sections.size() / NumShards;
326 forLoop(0, NumShards,
327 [&](size_t I) { forEachClassRange(I * Step, (I + 1) * Step, Fn); });
328 forEachClassRange(Step * NumShards, Sections.size(), Fn);
332 // The main function of ICF.
333 template <class ELFT> void ICF<ELFT>::run() {
334 // Collect sections to merge.
335 for (InputSectionBase<ELFT> *Sec : Symtab<ELFT>::X->Sections)
336 if (auto *S = dyn_cast<InputSection<ELFT>>(Sec))
338 Sections.push_back(S);
340 // Initially, we use hash values to partition sections.
341 for (InputSection<ELFT> *S : Sections)
342 // Set MSB to 1 to avoid collisions with non-hash IDs.
343 S->Class[0] = getHash(S) | (1 << 31);
345 // From now on, sections in Sections vector are ordered so that sections
346 // in the same equivalence class are consecutive in the vector.
347 std::stable_sort(Sections.begin(), Sections.end(),
348 [](InputSection<ELFT> *A, InputSection<ELFT> *B) {
349 return A->Class[0] < B->Class[0];
352 // Compare static contents and assign unique IDs for each static content.
353 forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
355 // Split groups by comparing relocations until convergence is obtained.
359 [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
362 log("ICF needed " + Twine(Cnt) + " iterations");
364 // Merge sections by the equivalence class.
365 forEachClass([&](size_t Begin, size_t End) {
366 if (End - Begin == 1)
369 log("selected " + Sections[Begin]->Name);
370 for (size_t I = Begin + 1; I < End; ++I) {
371 log(" removed " + Sections[I]->Name);
372 Sections[Begin]->replace(Sections[I]);
377 // ICF entry point function.
378 template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
380 template void elf::doIcf<ELF32LE>();
381 template void elf::doIcf<ELF32BE>();
382 template void elf::doIcf<ELF64LE>();
383 template void elf::doIcf<ELF64BE>();