llvm-project

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/ErrorHandler.h"
25
#include "lld/Common/Timer.h"
26
#include "llvm/ADT/Hashing.h"
27
#include "llvm/Support/Debug.h"
28
#include "llvm/Support/Parallel.h"
29
#include "llvm/Support/TimeProfiler.h"
30
#include "llvm/Support/raw_ostream.h"
31
#include "llvm/Support/xxhash.h"
32
#include <algorithm>
33
#include <atomic>
34
#include <vector>
35

36
using namespace llvm;
37

38
namespace lld::coff {
39

40
class ICF {
41
public:
42
  ICF(COFFLinkerContext &c) : ctx(c){};
43
  void run();
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
  COFFLinkerContext &ctx;
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 ((ctx.config.doICF == 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
  const char *itaniumVtablePrefix =
98
      ctx.config.machine == I386 ? "__ZTV" : "_ZTV";
99
  if (c->sym && (c->sym->getName().starts_with("??_7") ||
100
                 c->sym->getName().starts_with(itaniumVtablePrefix)))
101
    return true;
102

103
  // Anything else not in an address-significance table is eligible.
104
  return !c->keepUnique;
105
}
106

107
// Split an equivalence class into smaller classes.
108
void ICF::segregate(size_t begin, size_t end, bool constant) {
109
  while (begin < end) {
110
    // Divide [Begin, End) into two. Let Mid be the start index of the
111
    // second group.
112
    auto bound = std::stable_partition(
113
        chunks.begin() + begin + 1, chunks.begin() + end, [&](SectionChunk *s) {
114
          if (constant)
115
            return equalsConstant(chunks[begin], s);
116
          return equalsVariable(chunks[begin], s);
117
        });
118
    size_t mid = bound - chunks.begin();
119

120
    // Split [Begin, End) into [Begin, Mid) and [Mid, End). We use Mid as an
121
    // equivalence class ID because every group ends with a unique index.
122
    for (size_t i = begin; i < mid; ++i)
123
      chunks[i]->eqClass[(cnt + 1) % 2] = mid;
124

125
    // If we created a group, we need to iterate the main loop again.
126
    if (mid != end)
127
      repeat = true;
128

129
    begin = mid;
130
  }
131
}
132

133
// Returns true if two sections' associative children are equal.
134
bool ICF::assocEquals(const SectionChunk *a, const SectionChunk *b) {
135
  // Ignore associated metadata sections that don't participate in ICF, such as
136
  // debug info and CFGuard metadata.
137
  auto considerForICF = [](const SectionChunk &assoc) {
138
    StringRef Name = assoc.getSectionName();
139
    return !(Name.starts_with(".debug") || Name == ".gfids$y" ||
140
             Name == ".giats$y" || Name == ".gljmp$y");
141
  };
142
  auto ra = make_filter_range(a->children(), considerForICF);
143
  auto rb = make_filter_range(b->children(), considerForICF);
144
  return std::equal(ra.begin(), ra.end(), rb.begin(), rb.end(),
145
                    [&](const SectionChunk &ia, const SectionChunk &ib) {
146
                      return ia.eqClass[cnt % 2] == ib.eqClass[cnt % 2];
147
                    });
148
}
149

150
// Compare "non-moving" part of two sections, namely everything
151
// except relocation targets.
152
bool ICF::equalsConstant(const SectionChunk *a, const SectionChunk *b) {
153
  if (a->relocsSize != b->relocsSize)
154
    return false;
155

156
  // Compare relocations.
157
  auto eq = [&](const coff_relocation &r1, const coff_relocation &r2) {
158
    if (r1.Type != r2.Type ||
159
        r1.VirtualAddress != r2.VirtualAddress) {
160
      return false;
161
    }
162
    Symbol *b1 = a->file->getSymbol(r1.SymbolTableIndex);
163
    Symbol *b2 = b->file->getSymbol(r2.SymbolTableIndex);
164
    if (b1 == b2)
165
      return true;
166
    if (auto *d1 = dyn_cast<DefinedRegular>(b1))
167
      if (auto *d2 = dyn_cast<DefinedRegular>(b2))
168
        return d1->getValue() == d2->getValue() &&
169
               d1->getChunk()->eqClass[cnt % 2] == d2->getChunk()->eqClass[cnt % 2];
170
    return false;
171
  };
172
  if (!std::equal(a->getRelocs().begin(), a->getRelocs().end(),
173
                  b->getRelocs().begin(), eq))
174
    return false;
175

176
  // Compare section attributes and contents.
177
  return a->getOutputCharacteristics() == b->getOutputCharacteristics() &&
178
         a->getSectionName() == b->getSectionName() &&
179
         a->header->SizeOfRawData == b->header->SizeOfRawData &&
180
         a->checksum == b->checksum && a->getContents() == b->getContents() &&
181
         a->getMachine() == b->getMachine() && assocEquals(a, b);
182
}
183

184
// Compare "moving" part of two sections, namely relocation targets.
185
bool ICF::equalsVariable(const SectionChunk *a, const SectionChunk *b) {
186
  // Compare relocations.
187
  auto eqSym = [&](Symbol *b1, Symbol *b2) {
188
    if (b1 == b2)
189
      return true;
190
    if (auto *d1 = dyn_cast<DefinedRegular>(b1))
191
      if (auto *d2 = dyn_cast<DefinedRegular>(b2))
192
        return d1->getChunk()->eqClass[cnt % 2] == d2->getChunk()->eqClass[cnt % 2];
193
    return false;
194
  };
195
  auto eq = [&](const coff_relocation &r1, const coff_relocation &r2) {
196
    Symbol *b1 = a->file->getSymbol(r1.SymbolTableIndex);
197
    Symbol *b2 = b->file->getSymbol(r2.SymbolTableIndex);
198
    return eqSym(b1, b2);
199
  };
200

201
  Symbol *e1 = a->getEntryThunk();
202
  Symbol *e2 = b->getEntryThunk();
203
  if ((e1 || e2) && (!e1 || !e2 || !eqSym(e1, e2)))
204
    return false;
205

206
  return std::equal(a->getRelocs().begin(), a->getRelocs().end(),
207
                    b->getRelocs().begin(), eq) &&
208
         assocEquals(a, b);
209
}
210

211
// Find the first Chunk after Begin that has a different class from Begin.
212
size_t ICF::findBoundary(size_t begin, size_t end) {
213
  for (size_t i = begin + 1; i < end; ++i)
214
    if (chunks[begin]->eqClass[cnt % 2] != chunks[i]->eqClass[cnt % 2])
215
      return i;
216
  return end;
217
}
218

219
void ICF::forEachClassRange(size_t begin, size_t end,
220
                            std::function<void(size_t, size_t)> fn) {
221
  while (begin < end) {
222
    size_t mid = findBoundary(begin, end);
223
    fn(begin, mid);
224
    begin = mid;
225
  }
226
}
227

228
// Call Fn on each class group.
229
void ICF::forEachClass(std::function<void(size_t, size_t)> fn) {
230
  // If the number of sections are too small to use threading,
231
  // call Fn sequentially.
232
  if (chunks.size() < 1024) {
233
    forEachClassRange(0, chunks.size(), fn);
234
    ++cnt;
235
    return;
236
  }
237

238
  // Shard into non-overlapping intervals, and call Fn in parallel.
239
  // The sharding must be completed before any calls to Fn are made
240
  // so that Fn can modify the Chunks in its shard without causing data
241
  // races.
242
  const size_t numShards = 256;
243
  size_t step = chunks.size() / numShards;
244
  size_t boundaries[numShards + 1];
245
  boundaries[0] = 0;
246
  boundaries[numShards] = chunks.size();
247
  parallelFor(1, numShards, [&](size_t i) {
248
    boundaries[i] = findBoundary((i - 1) * step, chunks.size());
249
  });
250
  parallelFor(1, numShards + 1, [&](size_t i) {
251
    if (boundaries[i - 1] < boundaries[i]) {
252
      forEachClassRange(boundaries[i - 1], boundaries[i], fn);
253
    }
254
  });
255
  ++cnt;
256
}
257

258
// Merge identical COMDAT sections.
259
// Two sections are considered the same if their section headers,
260
// contents and relocations are all the same.
261
void ICF::run() {
262
  llvm::TimeTraceScope timeScope("ICF");
263
  ScopedTimer t(ctx.icfTimer);
264

265
  // Collect only mergeable sections and group by hash value.
266
  uint32_t nextId = 1;
267
  for (Chunk *c : ctx.symtab.getChunks()) {
268
    if (auto *sc = dyn_cast<SectionChunk>(c)) {
269
      if (isEligible(sc))
270
        chunks.push_back(sc);
271
      else
272
        sc->eqClass[0] = nextId++;
273
    }
274
  }
275

276
  // Make sure that ICF doesn't merge sections that are being handled by string
277
  // tail merging.
278
  for (MergeChunk *mc : ctx.mergeChunkInstances)
279
    if (mc)
280
      for (SectionChunk *sc : mc->sections)
281
        sc->eqClass[0] = nextId++;
282

283
  // Initially, we use hash values to partition sections.
284
  parallelForEach(chunks, [&](SectionChunk *sc) {
285
    sc->eqClass[0] = xxh3_64bits(sc->getContents());
286
  });
287

288
  // Combine the hashes of the sections referenced by each section into its
289
  // hash.
290
  for (unsigned cnt = 0; cnt != 2; ++cnt) {
291
    parallelForEach(chunks, [&](SectionChunk *sc) {
292
      uint32_t hash = sc->eqClass[cnt % 2];
293
      for (Symbol *b : sc->symbols())
294
        if (auto *sym = dyn_cast_or_null<DefinedRegular>(b))
295
          hash += sym->getChunk()->eqClass[cnt % 2];
296
      // Set MSB to 1 to avoid collisions with non-hash classes.
297
      sc->eqClass[(cnt + 1) % 2] = hash | (1U << 31);
298
    });
299
  }
300

301
  // From now on, sections in Chunks are ordered so that sections in
302
  // the same group are consecutive in the vector.
303
  llvm::stable_sort(chunks, [](const SectionChunk *a, const SectionChunk *b) {
304
    return a->eqClass[0] < b->eqClass[0];
305
  });
306

307
  // Compare static contents and assign unique IDs for each static content.
308
  forEachClass([&](size_t begin, size_t end) { segregate(begin, end, true); });
309

310
  // Split groups by comparing relocations until convergence is obtained.
311
  do {
312
    repeat = false;
313
    forEachClass(
314
        [&](size_t begin, size_t end) { segregate(begin, end, false); });
315
  } while (repeat);
316

317
  log("ICF needed " + Twine(cnt) + " iterations");
318

319
  // Merge sections in the same classes.
320
  forEachClass([&](size_t begin, size_t end) {
321
    if (end - begin == 1)
322
      return;
323

324
    log("Selected " + chunks[begin]->getDebugName());
325
    for (size_t i = begin + 1; i < end; ++i) {
326
      log("  Removed " + chunks[i]->getDebugName());
327
      chunks[begin]->replace(chunks[i]);
328
    }
329
  });
330
}
331

332
// Entry point to ICF.
333
void doICF(COFFLinkerContext &ctx) { ICF(ctx).run(); }
334

335
} // namespace lld::coff
336