xref: /freebsd/contrib/llvm-project/lld/ELF/ICF.cpp (revision 77a1348b3c1cfe8547be49a121b56299a1e18b69)
1 //===- ICF.cpp ------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // ICF is short for Identical Code Folding. This is a size optimization to
10 // identify and merge two or more read-only sections (typically functions)
11 // that happened to have the same contents. It usually reduces output size
12 // by a few percent.
13 //
14 // In ICF, two sections are considered identical if they have the same
15 // section flags, section data, and relocations. Relocations are tricky,
16 // because two relocations are considered the same if they have the same
17 // relocation types, values, and if they point to the same sections *in
18 // terms of ICF*.
19 //
20 // Here is an example. If foo and bar defined below are compiled to the
21 // same machine instructions, ICF can and should merge the two, although
22 // their relocations point to each other.
23 //
24 //   void foo() { bar(); }
25 //   void bar() { foo(); }
26 //
27 // If you merge the two, their relocations point to the same section and
28 // thus you know they are mergeable, but how do you know they are
29 // mergeable in the first place? This is not an easy problem to solve.
30 //
31 // What we are doing in LLD is to partition sections into equivalence
32 // classes. Sections in the same equivalence class when the algorithm
33 // terminates are considered identical. Here are details:
34 //
35 // 1. First, we partition sections using their hash values as keys. Hash
36 //    values contain section types, section contents and numbers of
37 //    relocations. During this step, relocation targets are not taken into
38 //    account. We just put sections that apparently differ into different
39 //    equivalence classes.
40 //
41 // 2. Next, for each equivalence class, we visit sections to compare
42 //    relocation targets. Relocation targets are considered equivalent if
43 //    their targets are in the same equivalence class. Sections with
44 //    different relocation targets are put into different equivalence
45 //    classes.
46 //
47 // 3. If we split an equivalence class in step 2, two relocations
48 //    previously target the same equivalence class may now target
49 //    different equivalence classes. Therefore, we repeat step 2 until a
50 //    convergence is obtained.
51 //
52 // 4. For each equivalence class C, pick an arbitrary section in C, and
53 //    merge all the other sections in C with it.
54 //
55 // For small programs, this algorithm needs 3-5 iterations. For large
56 // programs such as Chromium, it takes more than 20 iterations.
57 //
58 // This algorithm was mentioned as an "optimistic algorithm" in [1],
59 // though gold implements a different algorithm than this.
60 //
61 // We parallelize each step so that multiple threads can work on different
62 // equivalence classes concurrently. That gave us a large performance
63 // boost when applying ICF on large programs. For example, MSVC link.exe
64 // or GNU gold takes 10-20 seconds to apply ICF on Chromium, whose output
65 // size is about 1.5 GB, but LLD can finish it in less than 2 seconds on a
66 // 2.8 GHz 40 core machine. Even without threading, LLD's ICF is still
67 // faster than MSVC or gold though.
68 //
69 // [1] Safe ICF: Pointer Safe and Unwinding aware Identical Code Folding
70 // in the Gold Linker
71 // http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/36912.pdf
72 //
73 //===----------------------------------------------------------------------===//
74 
75 #include "ICF.h"
76 #include "Config.h"
77 #include "LinkerScript.h"
78 #include "OutputSections.h"
79 #include "SymbolTable.h"
80 #include "Symbols.h"
81 #include "SyntheticSections.h"
82 #include "Writer.h"
83 #include "lld/Common/Threads.h"
84 #include "llvm/ADT/StringExtras.h"
85 #include "llvm/BinaryFormat/ELF.h"
86 #include "llvm/Object/ELF.h"
87 #include "llvm/Support/xxhash.h"
88 #include <algorithm>
89 #include <atomic>
90 
91 using namespace llvm;
92 using namespace llvm::ELF;
93 using namespace llvm::object;
94 
95 namespace lld {
96 namespace elf {
97 namespace {
98 template <class ELFT> class ICF {
99 public:
100   void run();
101 
102 private:
103   void segregate(size_t begin, size_t end, bool constant);
104 
105   template <class RelTy>
106   bool constantEq(const InputSection *a, ArrayRef<RelTy> relsA,
107                   const InputSection *b, ArrayRef<RelTy> relsB);
108 
109   template <class RelTy>
110   bool variableEq(const InputSection *a, ArrayRef<RelTy> relsA,
111                   const InputSection *b, ArrayRef<RelTy> relsB);
112 
113   bool equalsConstant(const InputSection *a, const InputSection *b);
114   bool equalsVariable(const InputSection *a, const InputSection *b);
115 
116   size_t findBoundary(size_t begin, size_t end);
117 
118   void forEachClassRange(size_t begin, size_t end,
119                          llvm::function_ref<void(size_t, size_t)> fn);
120 
121   void forEachClass(llvm::function_ref<void(size_t, size_t)> fn);
122 
123   std::vector<InputSection *> sections;
124 
125   // We repeat the main loop while `Repeat` is true.
126   std::atomic<bool> repeat;
127 
128   // The main loop counter.
129   int cnt = 0;
130 
131   // We have two locations for equivalence classes. On the first iteration
132   // of the main loop, Class[0] has a valid value, and Class[1] contains
133   // garbage. We read equivalence classes from slot 0 and write to slot 1.
134   // So, Class[0] represents the current class, and Class[1] represents
135   // the next class. On each iteration, we switch their roles and use them
136   // alternately.
137   //
138   // Why are we doing this? Recall that other threads may be working on
139   // other equivalence classes in parallel. They may read sections that we
140   // are updating. We cannot update equivalence classes in place because
141   // it breaks the invariance that all possibly-identical sections must be
142   // in the same equivalence class at any moment. In other words, the for
143   // loop to update equivalence classes is not atomic, and that is
144   // observable from other threads. By writing new classes to other
145   // places, we can keep the invariance.
146   //
147   // Below, `Current` has the index of the current class, and `Next` has
148   // the index of the next class. If threading is enabled, they are either
149   // (0, 1) or (1, 0).
150   //
151   // Note on single-thread: if that's the case, they are always (0, 0)
152   // because we can safely read the next class without worrying about race
153   // conditions. Using the same location makes this algorithm converge
154   // faster because it uses results of the same iteration earlier.
155   int current = 0;
156   int next = 0;
157 };
158 }
159 
160 // Returns true if section S is subject of ICF.
161 static bool isEligible(InputSection *s) {
162   if (!s->isLive() || s->keepUnique || !(s->flags & SHF_ALLOC))
163     return false;
164 
165   // Don't merge writable sections. .data.rel.ro sections are marked as writable
166   // but are semantically read-only.
167   if ((s->flags & SHF_WRITE) && s->name != ".data.rel.ro" &&
168       !s->name.startswith(".data.rel.ro."))
169     return false;
170 
171   // SHF_LINK_ORDER sections are ICF'd as a unit with their dependent sections,
172   // so we don't consider them for ICF individually.
173   if (s->flags & SHF_LINK_ORDER)
174     return false;
175 
176   // Don't merge synthetic sections as their Data member is not valid and empty.
177   // The Data member needs to be valid for ICF as it is used by ICF to determine
178   // the equality of section contents.
179   if (isa<SyntheticSection>(s))
180     return false;
181 
182   // .init and .fini contains instructions that must be executed to initialize
183   // and finalize the process. They cannot and should not be merged.
184   if (s->name == ".init" || s->name == ".fini")
185     return false;
186 
187   // A user program may enumerate sections named with a C identifier using
188   // __start_* and __stop_* symbols. We cannot ICF any such sections because
189   // that could change program semantics.
190   if (isValidCIdentifier(s->name))
191     return false;
192 
193   return true;
194 }
195 
196 // Split an equivalence class into smaller classes.
197 template <class ELFT>
198 void ICF<ELFT>::segregate(size_t begin, size_t end, bool constant) {
199   // This loop rearranges sections in [Begin, End) so that all sections
200   // that are equal in terms of equals{Constant,Variable} are contiguous
201   // in [Begin, End).
202   //
203   // The algorithm is quadratic in the worst case, but that is not an
204   // issue in practice because the number of the distinct sections in
205   // each range is usually very small.
206 
207   while (begin < end) {
208     // Divide [Begin, End) into two. Let Mid be the start index of the
209     // second group.
210     auto bound =
211         std::stable_partition(sections.begin() + begin + 1,
212                               sections.begin() + end, [&](InputSection *s) {
213                                 if (constant)
214                                   return equalsConstant(sections[begin], s);
215                                 return equalsVariable(sections[begin], s);
216                               });
217     size_t mid = bound - sections.begin();
218 
219     // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
220     // updating the sections in [Begin, Mid). We use Mid as an equivalence
221     // class ID because every group ends with a unique index.
222     for (size_t i = begin; i < mid; ++i)
223       sections[i]->eqClass[next] = mid;
224 
225     // If we created a group, we need to iterate the main loop again.
226     if (mid != end)
227       repeat = true;
228 
229     begin = mid;
230   }
231 }
232 
233 // Compare two lists of relocations.
234 template <class ELFT>
235 template <class RelTy>
236 bool ICF<ELFT>::constantEq(const InputSection *secA, ArrayRef<RelTy> ra,
237                            const InputSection *secB, ArrayRef<RelTy> rb) {
238   for (size_t i = 0; i < ra.size(); ++i) {
239     if (ra[i].r_offset != rb[i].r_offset ||
240         ra[i].getType(config->isMips64EL) != rb[i].getType(config->isMips64EL))
241       return false;
242 
243     uint64_t addA = getAddend<ELFT>(ra[i]);
244     uint64_t addB = getAddend<ELFT>(rb[i]);
245 
246     Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]);
247     Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]);
248     if (&sa == &sb) {
249       if (addA == addB)
250         continue;
251       return false;
252     }
253 
254     auto *da = dyn_cast<Defined>(&sa);
255     auto *db = dyn_cast<Defined>(&sb);
256 
257     // Placeholder symbols generated by linker scripts look the same now but
258     // may have different values later.
259     if (!da || !db || da->scriptDefined || db->scriptDefined)
260       return false;
261 
262     // When comparing a pair of relocations, if they refer to different symbols,
263     // and either symbol is preemptible, the containing sections should be
264     // considered different. This is because even if the sections are identical
265     // in this DSO, they may not be after preemption.
266     if (da->isPreemptible || db->isPreemptible)
267       return false;
268 
269     // Relocations referring to absolute symbols are constant-equal if their
270     // values are equal.
271     if (!da->section && !db->section && da->value + addA == db->value + addB)
272       continue;
273     if (!da->section || !db->section)
274       return false;
275 
276     if (da->section->kind() != db->section->kind())
277       return false;
278 
279     // Relocations referring to InputSections are constant-equal if their
280     // section offsets are equal.
281     if (isa<InputSection>(da->section)) {
282       if (da->value + addA == db->value + addB)
283         continue;
284       return false;
285     }
286 
287     // Relocations referring to MergeInputSections are constant-equal if their
288     // offsets in the output section are equal.
289     auto *x = dyn_cast<MergeInputSection>(da->section);
290     if (!x)
291       return false;
292     auto *y = cast<MergeInputSection>(db->section);
293     if (x->getParent() != y->getParent())
294       return false;
295 
296     uint64_t offsetA =
297         sa.isSection() ? x->getOffset(addA) : x->getOffset(da->value) + addA;
298     uint64_t offsetB =
299         sb.isSection() ? y->getOffset(addB) : y->getOffset(db->value) + addB;
300     if (offsetA != offsetB)
301       return false;
302   }
303 
304   return true;
305 }
306 
307 // Compare "non-moving" part of two InputSections, namely everything
308 // except relocation targets.
309 template <class ELFT>
310 bool ICF<ELFT>::equalsConstant(const InputSection *a, const InputSection *b) {
311   if (a->numRelocations != b->numRelocations || a->flags != b->flags ||
312       a->getSize() != b->getSize() || a->data() != b->data())
313     return false;
314 
315   // If two sections have different output sections, we cannot merge them.
316   assert(a->getParent() && b->getParent());
317   if (a->getParent() != b->getParent())
318     return false;
319 
320   if (a->areRelocsRela)
321     return constantEq(a, a->template relas<ELFT>(), b,
322                       b->template relas<ELFT>());
323   return constantEq(a, a->template rels<ELFT>(), b, b->template rels<ELFT>());
324 }
325 
326 // Compare two lists of relocations. Returns true if all pairs of
327 // relocations point to the same section in terms of ICF.
328 template <class ELFT>
329 template <class RelTy>
330 bool ICF<ELFT>::variableEq(const InputSection *secA, ArrayRef<RelTy> ra,
331                            const InputSection *secB, ArrayRef<RelTy> rb) {
332   assert(ra.size() == rb.size());
333 
334   for (size_t i = 0; i < ra.size(); ++i) {
335     // The two sections must be identical.
336     Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]);
337     Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]);
338     if (&sa == &sb)
339       continue;
340 
341     auto *da = cast<Defined>(&sa);
342     auto *db = cast<Defined>(&sb);
343 
344     // We already dealt with absolute and non-InputSection symbols in
345     // constantEq, and for InputSections we have already checked everything
346     // except the equivalence class.
347     if (!da->section)
348       continue;
349     auto *x = dyn_cast<InputSection>(da->section);
350     if (!x)
351       continue;
352     auto *y = cast<InputSection>(db->section);
353 
354     // Ineligible sections are in the special equivalence class 0.
355     // They can never be the same in terms of the equivalence class.
356     if (x->eqClass[current] == 0)
357       return false;
358     if (x->eqClass[current] != y->eqClass[current])
359       return false;
360   };
361 
362   return true;
363 }
364 
365 // Compare "moving" part of two InputSections, namely relocation targets.
366 template <class ELFT>
367 bool ICF<ELFT>::equalsVariable(const InputSection *a, const InputSection *b) {
368   if (a->areRelocsRela)
369     return variableEq(a, a->template relas<ELFT>(), b,
370                       b->template relas<ELFT>());
371   return variableEq(a, a->template rels<ELFT>(), b, b->template rels<ELFT>());
372 }
373 
374 template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t begin, size_t end) {
375   uint32_t eqClass = sections[begin]->eqClass[current];
376   for (size_t i = begin + 1; i < end; ++i)
377     if (eqClass != sections[i]->eqClass[current])
378       return i;
379   return end;
380 }
381 
382 // Sections in the same equivalence class are contiguous in Sections
383 // vector. Therefore, Sections vector can be considered as contiguous
384 // groups of sections, grouped by the class.
385 //
386 // This function calls Fn on every group within [Begin, End).
387 template <class ELFT>
388 void ICF<ELFT>::forEachClassRange(size_t begin, size_t end,
389                                   llvm::function_ref<void(size_t, size_t)> fn) {
390   while (begin < end) {
391     size_t mid = findBoundary(begin, end);
392     fn(begin, mid);
393     begin = mid;
394   }
395 }
396 
397 // Call Fn on each equivalence class.
398 template <class ELFT>
399 void ICF<ELFT>::forEachClass(llvm::function_ref<void(size_t, size_t)> fn) {
400   // If threading is disabled or the number of sections are
401   // too small to use threading, call Fn sequentially.
402   if (!threadsEnabled || sections.size() < 1024) {
403     forEachClassRange(0, sections.size(), fn);
404     ++cnt;
405     return;
406   }
407 
408   current = cnt % 2;
409   next = (cnt + 1) % 2;
410 
411   // Shard into non-overlapping intervals, and call Fn in parallel.
412   // The sharding must be completed before any calls to Fn are made
413   // so that Fn can modify the Chunks in its shard without causing data
414   // races.
415   const size_t numShards = 256;
416   size_t step = sections.size() / numShards;
417   size_t boundaries[numShards + 1];
418   boundaries[0] = 0;
419   boundaries[numShards] = sections.size();
420 
421   parallelForEachN(1, numShards, [&](size_t i) {
422     boundaries[i] = findBoundary((i - 1) * step, sections.size());
423   });
424 
425   parallelForEachN(1, numShards + 1, [&](size_t i) {
426     if (boundaries[i - 1] < boundaries[i])
427       forEachClassRange(boundaries[i - 1], boundaries[i], fn);
428   });
429   ++cnt;
430 }
431 
432 // Combine the hashes of the sections referenced by the given section into its
433 // hash.
434 template <class ELFT, class RelTy>
435 static void combineRelocHashes(unsigned cnt, InputSection *isec,
436                                ArrayRef<RelTy> rels) {
437   uint32_t hash = isec->eqClass[cnt % 2];
438   for (RelTy rel : rels) {
439     Symbol &s = isec->template getFile<ELFT>()->getRelocTargetSym(rel);
440     if (auto *d = dyn_cast<Defined>(&s))
441       if (auto *relSec = dyn_cast_or_null<InputSection>(d->section))
442         hash += relSec->eqClass[cnt % 2];
443   }
444   // Set MSB to 1 to avoid collisions with non-hash IDs.
445   isec->eqClass[(cnt + 1) % 2] = hash | (1U << 31);
446 }
447 
448 static void print(const Twine &s) {
449   if (config->printIcfSections)
450     message(s);
451 }
452 
453 // The main function of ICF.
454 template <class ELFT> void ICF<ELFT>::run() {
455   // Compute isPreemptible early. We may add more symbols later, so this loop
456   // cannot be merged with the later computeIsPreemptible() pass which is used
457   // by scanRelocations().
458   for (Symbol *sym : symtab->symbols())
459     sym->isPreemptible = computeIsPreemptible(*sym);
460 
461   // Collect sections to merge.
462   for (InputSectionBase *sec : inputSections) {
463     auto *s = cast<InputSection>(sec);
464     if (isEligible(s))
465       sections.push_back(s);
466   }
467 
468   // Initially, we use hash values to partition sections.
469   parallelForEach(sections, [&](InputSection *s) {
470     s->eqClass[0] = xxHash64(s->data());
471   });
472 
473   for (unsigned cnt = 0; cnt != 2; ++cnt) {
474     parallelForEach(sections, [&](InputSection *s) {
475       if (s->areRelocsRela)
476         combineRelocHashes<ELFT>(cnt, s, s->template relas<ELFT>());
477       else
478         combineRelocHashes<ELFT>(cnt, s, s->template rels<ELFT>());
479     });
480   }
481 
482   // From now on, sections in Sections vector are ordered so that sections
483   // in the same equivalence class are consecutive in the vector.
484   llvm::stable_sort(sections, [](const InputSection *a, const InputSection *b) {
485     return a->eqClass[0] < b->eqClass[0];
486   });
487 
488   // Compare static contents and assign unique IDs for each static content.
489   forEachClass([&](size_t begin, size_t end) { segregate(begin, end, true); });
490 
491   // Split groups by comparing relocations until convergence is obtained.
492   do {
493     repeat = false;
494     forEachClass(
495         [&](size_t begin, size_t end) { segregate(begin, end, false); });
496   } while (repeat);
497 
498   log("ICF needed " + Twine(cnt) + " iterations");
499 
500   // Merge sections by the equivalence class.
501   forEachClassRange(0, sections.size(), [&](size_t begin, size_t end) {
502     if (end - begin == 1)
503       return;
504     print("selected section " + toString(sections[begin]));
505     for (size_t i = begin + 1; i < end; ++i) {
506       print("  removing identical section " + toString(sections[i]));
507       sections[begin]->replace(sections[i]);
508 
509       // At this point we know sections merged are fully identical and hence
510       // we want to remove duplicate implicit dependencies such as link order
511       // and relocation sections.
512       for (InputSection *isec : sections[i]->dependentSections)
513         isec->markDead();
514     }
515   });
516 
517   // InputSectionDescription::sections is populated by processSectionCommands().
518   // ICF may fold some input sections assigned to output sections. Remove them.
519   for (BaseCommand *base : script->sectionCommands)
520     if (auto *sec = dyn_cast<OutputSection>(base))
521       for (BaseCommand *sub_base : sec->sectionCommands)
522         if (auto *isd = dyn_cast<InputSectionDescription>(sub_base))
523           llvm::erase_if(isd->sections,
524                          [](InputSection *isec) { return !isec->isLive(); });
525 }
526 
527 // ICF entry point function.
528 template <class ELFT> void doIcf() { ICF<ELFT>().run(); }
529 
530 template void doIcf<ELF32LE>();
531 template void doIcf<ELF32BE>();
532 template void doIcf<ELF64LE>();
533 template void doIcf<ELF64BE>();
534 
535 } // namespace elf
536 } // namespace lld
537