Coverage Report

Created: 2019-07-24 05:18

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