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 "llvm/ADT/Hashing.h"
81 #include "llvm/Object/ELF.h"
82 #include "llvm/Support/ELF.h"
87 using namespace lld::elf;
89 using namespace llvm::ELF;
90 using namespace llvm::object;
93 template <class ELFT> class ICF {
98 void segregate(size_t Begin, size_t End, bool Constant);
100 template <class RelTy>
101 bool constantEq(ArrayRef<RelTy> RelsA, ArrayRef<RelTy> RelsB);
103 template <class RelTy>
104 bool variableEq(const InputSection *A, ArrayRef<RelTy> RelsA,
105 const InputSection *B, ArrayRef<RelTy> RelsB);
107 bool equalsConstant(const InputSection *A, const InputSection *B);
108 bool equalsVariable(const InputSection *A, const InputSection *B);
110 size_t findBoundary(size_t Begin, size_t End);
112 void forEachClassRange(size_t Begin, size_t End,
113 std::function<void(size_t, size_t)> Fn);
115 void forEachClass(std::function<void(size_t, size_t)> Fn);
117 std::vector<InputSection *> Sections;
119 // We repeat the main loop while `Repeat` is true.
120 std::atomic<bool> Repeat;
122 // The main loop counter.
125 // We have two locations for equivalence classes. On the first iteration
126 // of the main loop, Class[0] has a valid value, and Class[1] contains
127 // garbage. We read equivalence classes from slot 0 and write to slot 1.
128 // So, Class[0] represents the current class, and Class[1] represents
129 // the next class. On each iteration, we switch their roles and use them
132 // Why are we doing this? Recall that other threads may be working on
133 // other equivalence classes in parallel. They may read sections that we
134 // are updating. We cannot update equivalence classes in place because
135 // it breaks the invariance that all possibly-identical sections must be
136 // in the same equivalence class at any moment. In other words, the for
137 // loop to update equivalence classes is not atomic, and that is
138 // observable from other threads. By writing new classes to other
139 // places, we can keep the invariance.
141 // Below, `Current` has the index of the current class, and `Next` has
142 // the index of the next class. If threading is enabled, they are either
145 // Note on single-thread: if that's the case, they are always (0, 0)
146 // because we can safely read the next class without worrying about race
147 // conditions. Using the same location makes this algorithm converge
148 // faster because it uses results of the same iteration earlier.
154 // Returns a hash value for S. Note that the information about
155 // relocation targets is not included in the hash value.
156 template <class ELFT> static uint32_t getHash(InputSection *S) {
157 return hash_combine(S->Flags, S->getSize(), S->NumRelocations);
160 // Returns true if section S is subject of ICF.
161 static bool isEligible(InputSection *S) {
162 // .init and .fini contains instructions that must be executed to
163 // initialize and finalize the process. They cannot and should not
165 return S->Live && (S->Flags & SHF_ALLOC) && (S->Flags & SHF_EXECINSTR) &&
166 !(S->Flags & SHF_WRITE) && S->Name != ".init" && S->Name != ".fini";
169 // Split an equivalence class into smaller classes.
170 template <class ELFT>
171 void ICF<ELFT>::segregate(size_t Begin, size_t End, bool Constant) {
172 // This loop rearranges sections in [Begin, End) so that all sections
173 // that are equal in terms of equals{Constant,Variable} are contiguous
176 // The algorithm is quadratic in the worst case, but that is not an
177 // issue in practice because the number of the distinct sections in
178 // each range is usually very small.
180 while (Begin < End) {
181 // Divide [Begin, End) into two. Let Mid be the start index of the
184 std::stable_partition(Sections.begin() + Begin + 1,
185 Sections.begin() + End, [&](InputSection *S) {
187 return equalsConstant(Sections[Begin], S);
188 return equalsVariable(Sections[Begin], S);
190 size_t Mid = Bound - Sections.begin();
192 // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
193 // updating the sections in [Begin, Mid). We use Mid as an equivalence
194 // class ID because every group ends with a unique index.
195 for (size_t I = Begin; I < Mid; ++I)
196 Sections[I]->Class[Next] = Mid;
198 // If we created a group, we need to iterate the main loop again.
206 // Compare two lists of relocations.
207 template <class ELFT>
208 template <class RelTy>
209 bool ICF<ELFT>::constantEq(ArrayRef<RelTy> RelsA, ArrayRef<RelTy> RelsB) {
210 auto Eq = [](const RelTy &A, const RelTy &B) {
211 return A.r_offset == B.r_offset &&
212 A.getType(Config->IsMips64EL) == B.getType(Config->IsMips64EL) &&
213 getAddend<ELFT>(A) == getAddend<ELFT>(B);
216 return RelsA.size() == RelsB.size() &&
217 std::equal(RelsA.begin(), RelsA.end(), RelsB.begin(), Eq);
220 // Compare "non-moving" part of two InputSections, namely everything
221 // except relocation targets.
222 template <class ELFT>
223 bool ICF<ELFT>::equalsConstant(const InputSection *A, const InputSection *B) {
224 if (A->NumRelocations != B->NumRelocations || A->Flags != B->Flags ||
225 A->getSize() != B->getSize() || A->Data != B->Data)
228 if (A->AreRelocsRela)
229 return constantEq(A->template relas<ELFT>(), B->template relas<ELFT>());
230 return constantEq(A->template rels<ELFT>(), B->template rels<ELFT>());
233 // Compare two lists of relocations. Returns true if all pairs of
234 // relocations point to the same section in terms of ICF.
235 template <class ELFT>
236 template <class RelTy>
237 bool ICF<ELFT>::variableEq(const InputSection *A, ArrayRef<RelTy> RelsA,
238 const InputSection *B, ArrayRef<RelTy> RelsB) {
239 auto Eq = [&](const RelTy &RA, const RelTy &RB) {
240 // The two sections must be identical.
241 SymbolBody &SA = A->template getFile<ELFT>()->getRelocTargetSym(RA);
242 SymbolBody &SB = B->template getFile<ELFT>()->getRelocTargetSym(RB);
246 auto *DA = dyn_cast<DefinedRegular>(&SA);
247 auto *DB = dyn_cast<DefinedRegular>(&SB);
250 if (DA->Value != DB->Value)
253 // Either both symbols must be absolute...
254 if (!DA->Section || !DB->Section)
255 return !DA->Section && !DB->Section;
257 // Or the two sections must be in the same equivalence class.
258 auto *X = dyn_cast<InputSection>(DA->Section);
259 auto *Y = dyn_cast<InputSection>(DB->Section);
263 // Ineligible sections are in the special equivalence class 0.
264 // They can never be the same in terms of the equivalence class.
265 if (X->Class[Current] == 0)
268 return X->Class[Current] == Y->Class[Current];
271 return std::equal(RelsA.begin(), RelsA.end(), RelsB.begin(), Eq);
274 // Compare "moving" part of two InputSections, namely relocation targets.
275 template <class ELFT>
276 bool ICF<ELFT>::equalsVariable(const InputSection *A, const InputSection *B) {
277 if (A->AreRelocsRela)
278 return variableEq(A, A->template relas<ELFT>(), B,
279 B->template relas<ELFT>());
280 return variableEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
283 template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t Begin, size_t End) {
284 uint32_t Class = Sections[Begin]->Class[Current];
285 for (size_t I = Begin + 1; I < End; ++I)
286 if (Class != Sections[I]->Class[Current])
291 // Sections in the same equivalence class are contiguous in Sections
292 // vector. Therefore, Sections vector can be considered as contiguous
293 // groups of sections, grouped by the class.
295 // This function calls Fn on every group that starts within [Begin, End).
296 // Note that a group must start in that range but doesn't necessarily
297 // have to end before End.
298 template <class ELFT>
299 void ICF<ELFT>::forEachClassRange(size_t Begin, size_t End,
300 std::function<void(size_t, size_t)> Fn) {
302 Begin = findBoundary(Begin - 1, End);
304 while (Begin < End) {
305 size_t Mid = findBoundary(Begin, Sections.size());
311 // Call Fn on each equivalence class.
312 template <class ELFT>
313 void ICF<ELFT>::forEachClass(std::function<void(size_t, size_t)> Fn) {
314 // If threading is disabled or the number of sections are
315 // too small to use threading, call Fn sequentially.
316 if (!Config->Threads || Sections.size() < 1024) {
317 forEachClassRange(0, Sections.size(), Fn);
323 Next = (Cnt + 1) % 2;
325 // Split sections into 256 shards and call Fn in parallel.
326 size_t NumShards = 256;
327 size_t Step = Sections.size() / NumShards;
328 parallelFor(0, NumShards, [&](size_t I) {
329 forEachClassRange(I * Step, (I + 1) * Step, Fn);
331 forEachClassRange(Step * NumShards, Sections.size(), Fn);
335 // The main function of ICF.
336 template <class ELFT> void ICF<ELFT>::run() {
337 // Collect sections to merge.
338 for (InputSectionBase *Sec : InputSections)
339 if (auto *S = dyn_cast<InputSection>(Sec))
341 Sections.push_back(S);
343 // Initially, we use hash values to partition sections.
344 for (InputSection *S : Sections)
345 // Set MSB to 1 to avoid collisions with non-hash IDs.
346 S->Class[0] = getHash<ELFT>(S) | (1 << 31);
348 // From now on, sections in Sections vector are ordered so that sections
349 // in the same equivalence class are consecutive in the vector.
350 std::stable_sort(Sections.begin(), Sections.end(),
351 [](InputSection *A, InputSection *B) {
352 return A->Class[0] < B->Class[0];
355 // Compare static contents and assign unique IDs for each static content.
356 forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
358 // Split groups by comparing relocations until convergence is obtained.
362 [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
365 log("ICF needed " + Twine(Cnt) + " iterations");
367 // Merge sections by the equivalence class.
368 forEachClass([&](size_t Begin, size_t End) {
369 if (End - Begin == 1)
372 log("selected " + Sections[Begin]->Name);
373 for (size_t I = Begin + 1; I < End; ++I) {
374 log(" removed " + Sections[I]->Name);
375 Sections[Begin]->replace(Sections[I]);
379 // Mark ARM Exception Index table sections that refer to folded code
380 // sections as not live. These sections have an implict dependency
381 // via the link order dependency.
382 if (Config->EMachine == EM_ARM)
383 for (InputSectionBase *Sec : InputSections)
384 if (auto *S = dyn_cast<InputSection>(Sec))
385 if (S->Flags & SHF_LINK_ORDER)
386 S->Live = S->getLinkOrderDep()->Live;
389 // ICF entry point function.
390 template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
392 template void elf::doIcf<ELF32LE>();
393 template void elf::doIcf<ELF32BE>();
394 template void elf::doIcf<ELF64LE>();
395 template void elf::doIcf<ELF64BE>();