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