xref: /freebsd/contrib/llvm-project/lld/COFF/ICF.cpp (revision e9e8876a4d6afc1ad5315faaa191b25121a813d7)
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. That 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 // On Windows, ICF is enabled by default.
15 //
16 // See ELF/ICF.cpp for the details about the algorithm.
17 //
18 //===----------------------------------------------------------------------===//
19 
20 #include "ICF.h"
21 #include "Chunks.h"
22 #include "Symbols.h"
23 #include "lld/Common/ErrorHandler.h"
24 #include "lld/Common/Timer.h"
25 #include "llvm/ADT/Hashing.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/Parallel.h"
28 #include "llvm/Support/raw_ostream.h"
29 #include "llvm/Support/xxhash.h"
30 #include <algorithm>
31 #include <atomic>
32 #include <vector>
33 
34 using namespace llvm;
35 
36 namespace lld {
37 namespace coff {
38 
39 static Timer icfTimer("ICF", Timer::root());
40 
41 class ICF {
42 public:
43   ICF(ICFLevel icfLevel) : icfLevel(icfLevel){};
44   void run(ArrayRef<Chunk *> v);
45 
46 private:
47   void segregate(size_t begin, size_t end, bool constant);
48 
49   bool assocEquals(const SectionChunk *a, const SectionChunk *b);
50 
51   bool equalsConstant(const SectionChunk *a, const SectionChunk *b);
52   bool equalsVariable(const SectionChunk *a, const SectionChunk *b);
53 
54   bool isEligible(SectionChunk *c);
55 
56   size_t findBoundary(size_t begin, size_t end);
57 
58   void forEachClassRange(size_t begin, size_t end,
59                          std::function<void(size_t, size_t)> fn);
60 
61   void forEachClass(std::function<void(size_t, size_t)> fn);
62 
63   std::vector<SectionChunk *> chunks;
64   int cnt = 0;
65   std::atomic<bool> repeat = {false};
66   ICFLevel icfLevel = ICFLevel::All;
67 };
68 
69 // Returns true if section S is subject of ICF.
70 //
71 // Microsoft's documentation
72 // (https://msdn.microsoft.com/en-us/library/bxwfs976.aspx; visited April
73 // 2017) says that /opt:icf folds both functions and read-only data.
74 // Despite that, the MSVC linker folds only functions. We found
75 // a few instances of programs that are not safe for data merging.
76 // Therefore, we merge only functions just like the MSVC tool. However, we also
77 // merge read-only sections in a couple of cases where the address of the
78 // section is insignificant to the user program and the behaviour matches that
79 // of the Visual C++ linker.
80 bool ICF::isEligible(SectionChunk *c) {
81   // Non-comdat chunks, dead chunks, and writable chunks are not eligible.
82   bool writable = c->getOutputCharacteristics() & llvm::COFF::IMAGE_SCN_MEM_WRITE;
83   if (!c->isCOMDAT() || !c->live || writable)
84     return false;
85 
86   // Under regular (not safe) ICF, all code sections are eligible.
87   if ((icfLevel == ICFLevel::All) &&
88       c->getOutputCharacteristics() & llvm::COFF::IMAGE_SCN_MEM_EXECUTE)
89     return true;
90 
91   // .pdata and .xdata unwind info sections are eligible.
92   StringRef outSecName = c->getSectionName().split('$').first;
93   if (outSecName == ".pdata" || outSecName == ".xdata")
94     return true;
95 
96   // So are vtables.
97   if (c->sym && c->sym->getName().startswith("??_7"))
98     return true;
99 
100   // Anything else not in an address-significance table is eligible.
101   return !c->keepUnique;
102 }
103 
104 // Split an equivalence class into smaller classes.
105 void ICF::segregate(size_t begin, size_t end, bool constant) {
106   while (begin < end) {
107     // Divide [Begin, End) into two. Let Mid be the start index of the
108     // second group.
109     auto bound = std::stable_partition(
110         chunks.begin() + begin + 1, chunks.begin() + end, [&](SectionChunk *s) {
111           if (constant)
112             return equalsConstant(chunks[begin], s);
113           return equalsVariable(chunks[begin], s);
114         });
115     size_t mid = bound - chunks.begin();
116 
117     // Split [Begin, End) into [Begin, Mid) and [Mid, End). We use Mid as an
118     // equivalence class ID because every group ends with a unique index.
119     for (size_t i = begin; i < mid; ++i)
120       chunks[i]->eqClass[(cnt + 1) % 2] = mid;
121 
122     // If we created a group, we need to iterate the main loop again.
123     if (mid != end)
124       repeat = true;
125 
126     begin = mid;
127   }
128 }
129 
130 // Returns true if two sections' associative children are equal.
131 bool ICF::assocEquals(const SectionChunk *a, const SectionChunk *b) {
132   // Ignore associated metadata sections that don't participate in ICF, such as
133   // debug info and CFGuard metadata.
134   auto considerForICF = [](const SectionChunk &assoc) {
135     StringRef Name = assoc.getSectionName();
136     return !(Name.startswith(".debug") || Name == ".gfids$y" ||
137              Name == ".giats$y" || Name == ".gljmp$y");
138   };
139   auto ra = make_filter_range(a->children(), considerForICF);
140   auto rb = make_filter_range(b->children(), considerForICF);
141   return std::equal(ra.begin(), ra.end(), rb.begin(), rb.end(),
142                     [&](const SectionChunk &ia, const SectionChunk &ib) {
143                       return ia.eqClass[cnt % 2] == ib.eqClass[cnt % 2];
144                     });
145 }
146 
147 // Compare "non-moving" part of two sections, namely everything
148 // except relocation targets.
149 bool ICF::equalsConstant(const SectionChunk *a, const SectionChunk *b) {
150   if (a->relocsSize != b->relocsSize)
151     return false;
152 
153   // Compare relocations.
154   auto eq = [&](const coff_relocation &r1, const coff_relocation &r2) {
155     if (r1.Type != r2.Type ||
156         r1.VirtualAddress != r2.VirtualAddress) {
157       return false;
158     }
159     Symbol *b1 = a->file->getSymbol(r1.SymbolTableIndex);
160     Symbol *b2 = b->file->getSymbol(r2.SymbolTableIndex);
161     if (b1 == b2)
162       return true;
163     if (auto *d1 = dyn_cast<DefinedRegular>(b1))
164       if (auto *d2 = dyn_cast<DefinedRegular>(b2))
165         return d1->getValue() == d2->getValue() &&
166                d1->getChunk()->eqClass[cnt % 2] == d2->getChunk()->eqClass[cnt % 2];
167     return false;
168   };
169   if (!std::equal(a->getRelocs().begin(), a->getRelocs().end(),
170                   b->getRelocs().begin(), eq))
171     return false;
172 
173   // Compare section attributes and contents.
174   return a->getOutputCharacteristics() == b->getOutputCharacteristics() &&
175          a->getSectionName() == b->getSectionName() &&
176          a->header->SizeOfRawData == b->header->SizeOfRawData &&
177          a->checksum == b->checksum && a->getContents() == b->getContents() &&
178          assocEquals(a, b);
179 }
180 
181 // Compare "moving" part of two sections, namely relocation targets.
182 bool ICF::equalsVariable(const SectionChunk *a, const SectionChunk *b) {
183   // Compare relocations.
184   auto eq = [&](const coff_relocation &r1, const coff_relocation &r2) {
185     Symbol *b1 = a->file->getSymbol(r1.SymbolTableIndex);
186     Symbol *b2 = b->file->getSymbol(r2.SymbolTableIndex);
187     if (b1 == b2)
188       return true;
189     if (auto *d1 = dyn_cast<DefinedRegular>(b1))
190       if (auto *d2 = dyn_cast<DefinedRegular>(b2))
191         return d1->getChunk()->eqClass[cnt % 2] == d2->getChunk()->eqClass[cnt % 2];
192     return false;
193   };
194   return std::equal(a->getRelocs().begin(), a->getRelocs().end(),
195                     b->getRelocs().begin(), eq) &&
196          assocEquals(a, b);
197 }
198 
199 // Find the first Chunk after Begin that has a different class from Begin.
200 size_t ICF::findBoundary(size_t begin, size_t end) {
201   for (size_t i = begin + 1; i < end; ++i)
202     if (chunks[begin]->eqClass[cnt % 2] != chunks[i]->eqClass[cnt % 2])
203       return i;
204   return end;
205 }
206 
207 void ICF::forEachClassRange(size_t begin, size_t end,
208                             std::function<void(size_t, size_t)> fn) {
209   while (begin < end) {
210     size_t mid = findBoundary(begin, end);
211     fn(begin, mid);
212     begin = mid;
213   }
214 }
215 
216 // Call Fn on each class group.
217 void ICF::forEachClass(std::function<void(size_t, size_t)> fn) {
218   // If the number of sections are too small to use threading,
219   // call Fn sequentially.
220   if (chunks.size() < 1024) {
221     forEachClassRange(0, chunks.size(), fn);
222     ++cnt;
223     return;
224   }
225 
226   // Shard into non-overlapping intervals, and call Fn in parallel.
227   // The sharding must be completed before any calls to Fn are made
228   // so that Fn can modify the Chunks in its shard without causing data
229   // races.
230   const size_t numShards = 256;
231   size_t step = chunks.size() / numShards;
232   size_t boundaries[numShards + 1];
233   boundaries[0] = 0;
234   boundaries[numShards] = chunks.size();
235   parallelForEachN(1, numShards, [&](size_t i) {
236     boundaries[i] = findBoundary((i - 1) * step, chunks.size());
237   });
238   parallelForEachN(1, numShards + 1, [&](size_t i) {
239     if (boundaries[i - 1] < boundaries[i]) {
240       forEachClassRange(boundaries[i - 1], boundaries[i], fn);
241     }
242   });
243   ++cnt;
244 }
245 
246 // Merge identical COMDAT sections.
247 // Two sections are considered the same if their section headers,
248 // contents and relocations are all the same.
249 void ICF::run(ArrayRef<Chunk *> vec) {
250   ScopedTimer t(icfTimer);
251 
252   // Collect only mergeable sections and group by hash value.
253   uint32_t nextId = 1;
254   for (Chunk *c : vec) {
255     if (auto *sc = dyn_cast<SectionChunk>(c)) {
256       if (isEligible(sc))
257         chunks.push_back(sc);
258       else
259         sc->eqClass[0] = nextId++;
260     }
261   }
262 
263   // Make sure that ICF doesn't merge sections that are being handled by string
264   // tail merging.
265   for (MergeChunk *mc : MergeChunk::instances)
266     if (mc)
267       for (SectionChunk *sc : mc->sections)
268         sc->eqClass[0] = nextId++;
269 
270   // Initially, we use hash values to partition sections.
271   parallelForEach(chunks, [&](SectionChunk *sc) {
272     sc->eqClass[0] = xxHash64(sc->getContents());
273   });
274 
275   // Combine the hashes of the sections referenced by each section into its
276   // hash.
277   for (unsigned cnt = 0; cnt != 2; ++cnt) {
278     parallelForEach(chunks, [&](SectionChunk *sc) {
279       uint32_t hash = sc->eqClass[cnt % 2];
280       for (Symbol *b : sc->symbols())
281         if (auto *sym = dyn_cast_or_null<DefinedRegular>(b))
282           hash += sym->getChunk()->eqClass[cnt % 2];
283       // Set MSB to 1 to avoid collisions with non-hash classes.
284       sc->eqClass[(cnt + 1) % 2] = hash | (1U << 31);
285     });
286   }
287 
288   // From now on, sections in Chunks are ordered so that sections in
289   // the same group are consecutive in the vector.
290   llvm::stable_sort(chunks, [](const SectionChunk *a, const SectionChunk *b) {
291     return a->eqClass[0] < b->eqClass[0];
292   });
293 
294   // Compare static contents and assign unique IDs for each static content.
295   forEachClass([&](size_t begin, size_t end) { segregate(begin, end, true); });
296 
297   // Split groups by comparing relocations until convergence is obtained.
298   do {
299     repeat = false;
300     forEachClass(
301         [&](size_t begin, size_t end) { segregate(begin, end, false); });
302   } while (repeat);
303 
304   log("ICF needed " + Twine(cnt) + " iterations");
305 
306   // Merge sections in the same classes.
307   forEachClass([&](size_t begin, size_t end) {
308     if (end - begin == 1)
309       return;
310 
311     log("Selected " + chunks[begin]->getDebugName());
312     for (size_t i = begin + 1; i < end; ++i) {
313       log("  Removed " + chunks[i]->getDebugName());
314       chunks[begin]->replace(chunks[i]);
315     }
316   });
317 }
318 
319 // Entry point to ICF.
320 void doICF(ArrayRef<Chunk *> chunks, ICFLevel icfLevel) {
321   ICF(icfLevel).run(chunks);
322 }
323 
324 } // namespace coff
325 } // namespace lld
326