Coverage Report

Created: 2018-06-25 02:00

/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
//                             The LLVM Linker
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// ICF is short for Identical Code Folding. That is a size optimization to
11
// identify and merge two or more read-only sections (typically functions)
12
// that happened to have the same contents. It usually reduces output size
13
// by a few percent.
14
//
15
// On Windows, ICF is enabled by default.
16
//
17
// See ELF/ICF.cpp for the details about the algortihm.
18
//
19
//===----------------------------------------------------------------------===//
20
21
#include "ICF.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/raw_ostream.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
  uint32_t getHash(SectionChunk *C);
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 a hash value for S.
69
126
uint32_t ICF::getHash(SectionChunk *C) {
70
126
  return hash_combine(C->getOutputCharacteristics(), C->SectionName,
71
126
                      C->Relocs.size(), uint32_t(C->Header->SizeOfRawData),
72
126
                      C->Checksum, C->getContents());
73
126
}
74
75
// Returns true if section S is subject of ICF.
76
//
77
// Microsoft's documentation
78
// (https://msdn.microsoft.com/en-us/library/bxwfs976.aspx; visited April
79
// 2017) says that /opt:icf folds both functions and read-only data.
80
// Despite that, the MSVC linker folds only functions. We found
81
// a few instances of programs that are not safe for data merging.
82
// Therefore, we merge only functions just like the MSVC tool. However, we also
83
// merge read-only sections in a couple of cases where the address of the
84
// section is insignificant to the user program and the behaviour matches that
85
// of the Visual C++ linker.
86
905
bool ICF::isEligible(SectionChunk *C) {
87
905
  // Non-comdat chunks, dead chunks, and writable chunks are not elegible.
88
905
  bool Writable = C->getOutputCharacteristics() & llvm::COFF::IMAGE_SCN_MEM_WRITE;
89
905
  if (!C->isCOMDAT() || 
!C->isLive()172
||
Writable154
)
90
756
    return false;
91
149
92
149
  // Code sections are eligible.
93
149
  if (C->getOutputCharacteristics() & llvm::COFF::IMAGE_SCN_MEM_EXECUTE)
94
92
    return true;
95
57
96
57
  // .pdata and .xdata unwind info sections are eligible.
97
57
  StringRef OutSecName = C->getSectionName().split('$').first;
98
57
  if (OutSecName == ".pdata" || 
OutSecName == ".xdata"41
)
99
32
    return true;
100
25
101
25
  // So are vtables.
102
25
  return C->Sym && 
C->Sym->getName().startswith("??_7")20
;
103
25
}
104
105
// Split an equivalence class into smaller classes.
106
200
void ICF::segregate(size_t Begin, size_t End, bool Constant) {
107
402
  while (Begin < End) {
108
202
    // Divide [Begin, End) into two. Let Mid be the start index of the
109
202
    // second group.
110
202
    auto Bound = std::stable_partition(
111
202
        Chunks.begin() + Begin + 1, Chunks.begin() + End, [&](SectionChunk *S) {
112
52
          if (Constant)
113
27
            return equalsConstant(Chunks[Begin], S);
114
25
          return equalsVariable(Chunks[Begin], S);
115
25
        });
116
202
    size_t Mid = Bound - Chunks.begin();
117
202
118
202
    // Split [Begin, End) into [Begin, Mid) and [Mid, End). We use Mid as an
119
202
    // equivalence class ID because every group ends with a unique index.
120
454
    for (size_t I = Begin; I < Mid; 
++I252
)
121
252
      Chunks[I]->Class[(Cnt + 1) % 2] = Mid;
122
202
123
202
    // If we created a group, we need to iterate the main loop again.
124
202
    if (Mid != End)
125
2
      Repeat = true;
126
202
127
202
    Begin = Mid;
128
202
  }
129
200
}
130
131
// Returns true if two sections' associative children are equal.
132
51
bool ICF::assocEquals(const SectionChunk *A, const SectionChunk *B) {
133
102
  auto ChildClasses = [&](const SectionChunk *SC) {
134
102
    std::vector<uint32_t> Classes;
135
102
    for (const SectionChunk *C : SC->children())
136
22
      if (!C->SectionName.startswith(".debug") &&
137
22
          
C->SectionName != ".gfids$y"16
&&
C->SectionName != ".gljmp$y"14
)
138
12
        Classes.push_back(C->Class[Cnt % 2]);
139
102
    return Classes;
140
102
  };
141
51
  return ChildClasses(A) == ChildClasses(B);
142
51
}
143
144
// Compare "non-moving" part of two sections, namely everything
145
// except relocation targets.
146
27
bool ICF::equalsConstant(const SectionChunk *A, const SectionChunk *B) {
147
27
  if (A->Relocs.size() != B->Relocs.size())
148
0
    return false;
149
27
150
27
  // Compare relocations.
151
27
  auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
152
14
    if (R1.Type != R2.Type ||
153
14
        R1.VirtualAddress != R2.VirtualAddress) {
154
0
      return false;
155
0
    }
156
14
    Symbol *B1 = A->File->getSymbol(R1.SymbolTableIndex);
157
14
    Symbol *B2 = B->File->getSymbol(R2.SymbolTableIndex);
158
14
    if (B1 == B2)
159
6
      return true;
160
8
    if (auto *D1 = dyn_cast<DefinedRegular>(B1))
161
8
      if (auto *D2 = dyn_cast<DefinedRegular>(B2))
162
8
        return D1->getValue() == D2->getValue() &&
163
8
               D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
164
0
    return false;
165
0
  };
166
27
  if (!std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq))
167
1
    return false;
168
26
169
26
  // Compare section attributes and contents.
170
26
  return A->getOutputCharacteristics() == B->getOutputCharacteristics() &&
171
26
         A->SectionName == B->SectionName &&
172
26
         A->Header->SizeOfRawData == B->Header->SizeOfRawData &&
173
26
         A->Checksum == B->Checksum && A->getContents() == B->getContents() &&
174
26
         assocEquals(A, B);
175
26
}
176
177
// Compare "moving" part of two sections, namely relocation targets.
178
25
bool ICF::equalsVariable(const SectionChunk *A, const SectionChunk *B) {
179
25
  // Compare relocations.
180
25
  auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
181
9
    Symbol *B1 = A->File->getSymbol(R1.SymbolTableIndex);
182
9
    Symbol *B2 = B->File->getSymbol(R2.SymbolTableIndex);
183
9
    if (B1 == B2)
184
4
      return true;
185
5
    if (auto *D1 = dyn_cast<DefinedRegular>(B1))
186
5
      if (auto *D2 = dyn_cast<DefinedRegular>(B2))
187
5
        return D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
188
0
    return false;
189
0
  };
190
25
  return std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(),
191
25
                    Eq) &&
192
25
         assocEquals(A, B);
193
25
}
194
195
// Find the first Chunk after Begin that has a different class from Begin.
196
301
size_t ICF::findBoundary(size_t Begin, size_t End) {
197
378
  for (size_t I = Begin + 1; I < End; 
++I77
)
198
198
    if (Chunks[Begin]->Class[Cnt % 2] != Chunks[I]->Class[Cnt % 2])
199
121
      return I;
200
301
  
return End180
;
201
301
}
202
203
void ICF::forEachClassRange(size_t Begin, size_t End,
204
885
                            std::function<void(size_t, size_t)> Fn) {
205
1.18k
  while (Begin < End) {
206
301
    size_t Mid = findBoundary(Begin, End);
207
301
    Fn(Begin, Mid);
208
301
    Begin = Mid;
209
301
  }
210
885
}
211
212
// Call Fn on each class group.
213
885
void ICF::forEachClass(std::function<void(size_t, size_t)> Fn) {
214
885
  // If the number of sections are too small to use threading,
215
885
  // call Fn sequentially.
216
885
  if (Chunks.size() < 1024) {
217
885
    forEachClassRange(0, Chunks.size(), Fn);
218
885
    ++Cnt;
219
885
    return;
220
885
  }
221
0
222
0
  // Shard into non-overlapping intervals, and call Fn in parallel.
223
0
  // The sharding must be completed before any calls to Fn are made
224
0
  // so that Fn can modify the Chunks in its shard without causing data
225
0
  // races.
226
0
  const size_t NumShards = 256;
227
0
  size_t Step = Chunks.size() / NumShards;
228
0
  size_t Boundaries[NumShards + 1];
229
0
  Boundaries[0] = 0;
230
0
  Boundaries[NumShards] = Chunks.size();
231
0
  for_each_n(parallel::par, size_t(1), NumShards, [&](size_t I) {
232
0
    Boundaries[I] = findBoundary((I - 1) * Step, Chunks.size());
233
0
  });
234
0
  for_each_n(parallel::par, size_t(1), NumShards + 1, [&](size_t I) {
235
0
    if (Boundaries[I - 1] < Boundaries[I]) {
236
0
      forEachClassRange(Boundaries[I - 1], Boundaries[I], Fn);
237
0
    }
238
0
  });
239
0
  ++Cnt;
240
0
}
241
242
// Merge identical COMDAT sections.
243
// Two sections are considered the same if their section headers,
244
// contents and relocations are all the same.
245
295
void ICF::run(ArrayRef<Chunk *> Vec) {
246
295
  ScopedTimer T(ICFTimer);
247
295
248
295
  // Collect only mergeable sections and group by hash value.
249
295
  uint32_t NextId = 1;
250
916
  for (Chunk *C : Vec) {
251
916
    if (auto *SC = dyn_cast<SectionChunk>(C)) {
252
905
      if (isEligible(SC))
253
126
        Chunks.push_back(SC);
254
779
      else
255
779
        SC->Class[0] = NextId++;
256
905
    }
257
916
  }
258
295
259
295
  // Make sure that ICF doesn't merge sections that are being handled by string
260
295
  // tail merging.
261
295
  for (auto &P : MergeChunk::Instances)
262
2
    for (SectionChunk *SC : P.second->Sections)
263
5
      SC->Class[0] = NextId++;
264
295
265
295
  // Initially, we use hash values to partition sections.
266
295
  for_each(parallel::par, Chunks.begin(), Chunks.end(), [&](SectionChunk *SC) {
267
126
    // Set MSB to 1 to avoid collisions with non-hash classs.
268
126
    SC->Class[0] = getHash(SC) | (1 << 31);
269
126
  });
270
295
271
295
  // From now on, sections in Chunks are ordered so that sections in
272
295
  // the same group are consecutive in the vector.
273
295
  std::stable_sort(Chunks.begin(), Chunks.end(),
274
295
                   [](SectionChunk *A, SectionChunk *B) {
275
118
                     return A->Class[0] < B->Class[0];
276
118
                   });
277
295
278
295
  // Compare static contents and assign unique IDs for each static content.
279
295
  forEachClass([&](size_t Begin, size_t End) 
{ segregate(Begin, End, true); }99
);
280
295
281
295
  // Split groups by comparing relocations until convergence is obtained.
282
295
  do {
283
295
    Repeat = false;
284
295
    forEachClass(
285
295
        [&](size_t Begin, size_t End) 
{ segregate(Begin, End, false); }101
);
286
295
  } while (Repeat);
287
295
288
295
  log("ICF needed " + Twine(Cnt) + " iterations");
289
295
290
295
  // Merge sections in the same classs.
291
295
  forEachClass([&](size_t Begin, size_t End) {
292
101
    if (End - Begin == 1)
293
81
      return;
294
20
295
20
    log("Selected " + Chunks[Begin]->getDebugName());
296
45
    for (size_t I = Begin + 1; I < End; 
++I25
) {
297
25
      log("  Removed " + Chunks[I]->getDebugName());
298
25
      Chunks[Begin]->replace(Chunks[I]);
299
25
    }
300
20
  });
301
295
}
302
303
// Entry point to ICF.
304
295
void doICF(ArrayRef<Chunk *> Chunks) { ICF().run(Chunks); }
305
306
} // namespace coff
307
} // namespace lld