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