Coverage Report

Created: 2019-05-22 02:55

/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
804
bool ICF::isEligible(SectionChunk *C) {
80
804
  // Non-comdat chunks, dead chunks, and writable chunks are not elegible.
81
804
  bool Writable = C->getOutputCharacteristics() & llvm::COFF::IMAGE_SCN_MEM_WRITE;
82
804
  if (!C->isCOMDAT() || 
!C->Live130
||
Writable105
)
83
716
    return false;
84
88
85
88
  // Code sections are eligible.
86
88
  if (C->getOutputCharacteristics() & llvm::COFF::IMAGE_SCN_MEM_EXECUTE)
87
60
    return true;
88
28
89
28
  // .pdata and .xdata unwind info sections are eligible.
90
28
  StringRef OutSecName = C->getSectionName().split('$').first;
91
28
  if (OutSecName == ".pdata" || 
OutSecName == ".xdata"22
)
92
12
    return true;
93
16
94
16
  // So are vtables.
95
16
  if (C->Sym && 
C->Sym->getName().startswith("??_7")12
)
96
2
    return true;
97
14
98
14
  // Anything else not in an address-significance table is eligible.
99
14
  return !C->KeepUnique;
100
14
}
101
102
// Split an equivalence class into smaller classes.
103
119
void ICF::segregate(size_t Begin, size_t End, bool Constant) {
104
239
  while (Begin < End) {
105
120
    // Divide [Begin, End) into two. Let Mid be the start index of the
106
120
    // second group.
107
120
    auto Bound = std::stable_partition(
108
120
        Chunks.begin() + Begin + 1, Chunks.begin() + End, [&](SectionChunk *S) {
109
29
          if (Constant)
110
15
            return equalsConstant(Chunks[Begin], S);
111
14
          return equalsVariable(Chunks[Begin], S);
112
14
        });
113
120
    size_t Mid = Bound - Chunks.begin();
114
120
115
120
    // Split [Begin, End) into [Begin, Mid) and [Mid, End). We use Mid as an
116
120
    // equivalence class ID because every group ends with a unique index.
117
268
    for (size_t I = Begin; I < Mid; 
++I148
)
118
148
      Chunks[I]->Class[(Cnt + 1) % 2] = Mid;
119
120
120
120
    // If we created a group, we need to iterate the main loop again.
121
120
    if (Mid != End)
122
1
      Repeat = true;
123
120
124
120
    Begin = Mid;
125
120
  }
126
119
}
127
128
// Returns true if two sections' associative children are equal.
129
29
bool ICF::assocEquals(const SectionChunk *A, const SectionChunk *B) {
130
58
  auto ChildClasses = [&](const SectionChunk *SC) {
131
58
    std::vector<uint32_t> Classes;
132
58
    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.Class[Cnt % 2]);
136
58
    return Classes;
137
58
  };
138
29
  return ChildClasses(A) == ChildClasses(B);
139
29
}
140
141
// Compare "non-moving" part of two sections, namely everything
142
// except relocation targets.
143
15
bool ICF::equalsConstant(const SectionChunk *A, const SectionChunk *B) {
144
15
  if (A->RelocsSize != B->RelocsSize)
145
0
    return false;
146
15
147
15
  // Compare relocations.
148
15
  auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
149
9
    if (R1.Type != R2.Type ||
150
9
        R1.VirtualAddress != R2.VirtualAddress) {
151
0
      return false;
152
0
    }
153
9
    Symbol *B1 = A->File->getSymbol(R1.SymbolTableIndex);
154
9
    Symbol *B2 = B->File->getSymbol(R2.SymbolTableIndex);
155
9
    if (B1 == B2)
156
5
      return true;
157
4
    if (auto *D1 = dyn_cast<DefinedRegular>(B1))
158
4
      if (auto *D2 = dyn_cast<DefinedRegular>(B2))
159
4
        return D1->getValue() == D2->getValue() &&
160
4
               D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
161
0
    return false;
162
0
  };
163
15
  if (!std::equal(A->getRelocs().begin(), A->getRelocs().end(),
164
15
                  B->getRelocs().begin(), Eq))
165
0
    return false;
166
15
167
15
  // Compare section attributes and contents.
168
15
  return A->getOutputCharacteristics() == B->getOutputCharacteristics() &&
169
15
         A->getSectionName() == B->getSectionName() &&
170
15
         A->Header->SizeOfRawData == B->Header->SizeOfRawData &&
171
15
         A->Checksum == B->Checksum && A->getContents() == B->getContents() &&
172
15
         assocEquals(A, B);
173
15
}
174
175
// Compare "moving" part of two sections, namely relocation targets.
176
14
bool ICF::equalsVariable(const SectionChunk *A, const SectionChunk *B) {
177
14
  // Compare relocations.
178
14
  auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
179
7
    Symbol *B1 = A->File->getSymbol(R1.SymbolTableIndex);
180
7
    Symbol *B2 = B->File->getSymbol(R2.SymbolTableIndex);
181
7
    if (B1 == B2)
182
3
      return true;
183
4
    if (auto *D1 = dyn_cast<DefinedRegular>(B1))
184
4
      if (auto *D2 = dyn_cast<DefinedRegular>(B2))
185
4
        return D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
186
0
    return false;
187
0
  };
188
14
  return std::equal(A->getRelocs().begin(), A->getRelocs().end(),
189
14
                    B->getRelocs().begin(), Eq) &&
190
14
         assocEquals(A, B);
191
14
}
192
193
// Find the first Chunk after Begin that has a different class from Begin.
194
179
size_t ICF::findBoundary(size_t Begin, size_t End) {
195
222
  for (size_t I = Begin + 1; I < End; 
++I43
)
196
105
    if (Chunks[Begin]->Class[Cnt % 2] != Chunks[I]->Class[Cnt % 2])
197
62
      return I;
198
179
  
return End117
;
199
179
}
200
201
void ICF::forEachClassRange(size_t Begin, size_t End,
202
648
                            std::function<void(size_t, size_t)> Fn) {
203
827
  while (Begin < End) {
204
179
    size_t Mid = findBoundary(Begin, End);
205
179
    Fn(Begin, Mid);
206
179
    Begin = Mid;
207
179
  }
208
648
}
209
210
// Call Fn on each class group.
211
648
void ICF::forEachClass(std::function<void(size_t, size_t)> Fn) {
212
648
  // If the number of sections are too small to use threading,
213
648
  // call Fn sequentially.
214
648
  if (Chunks.size() < 1024) {
215
648
    forEachClassRange(0, Chunks.size(), Fn);
216
648
    ++Cnt;
217
648
    return;
218
648
  }
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
216
void ICF::run(ArrayRef<Chunk *> Vec) {
244
216
  ScopedTimer T(ICFTimer);
245
216
246
216
  // Collect only mergeable sections and group by hash value.
247
216
  uint32_t NextId = 1;
248
815
  for (Chunk *C : Vec) {
249
815
    if (auto *SC = dyn_cast<SectionChunk>(C)) {
250
804
      if (isEligible(SC))
251
74
        Chunks.push_back(SC);
252
730
      else
253
730
        SC->Class[0] = NextId++;
254
804
    }
255
815
  }
256
216
257
216
  // Make sure that ICF doesn't merge sections that are being handled by string
258
216
  // tail merging.
259
216
  for (auto &P : MergeChunk::Instances)
260
2
    for (SectionChunk *SC : P.second->Sections)
261
5
      SC->Class[0] = NextId++;
262
216
263
216
  // Initially, we use hash values to partition sections.
264
216
  parallelForEach(Chunks, [&](SectionChunk *SC) {
265
74
    SC->Class[0] = xxHash64(SC->getContents());
266
74
  });
267
216
268
216
  // Combine the hashes of the sections referenced by each section into its
269
216
  // hash.
270
648
  for (unsigned Cnt = 0; Cnt != 2; 
++Cnt432
) {
271
432
    parallelForEach(Chunks, [&](SectionChunk *SC) {
272
148
      uint32_t Hash = SC->Class[Cnt % 2];
273
148
      for (Symbol *B : SC->symbols())
274
86
        if (auto *Sym = dyn_cast_or_null<DefinedRegular>(B))
275
86
          Hash += Sym->getChunk()->Class[Cnt % 2];
276
148
      // Set MSB to 1 to avoid collisions with non-hash classs.
277
148
      SC->Class[(Cnt + 1) % 2] = Hash | (1U << 31);
278
148
    });
279
432
  }
280
216
281
216
  // From now on, sections in Chunks are ordered so that sections in
282
216
  // the same group are consecutive in the vector.
283
216
  llvm::stable_sort(Chunks, [](const SectionChunk *A, const SectionChunk *B) {
284
48
    return A->Class[0] < B->Class[0];
285
48
  });
286
216
287
216
  // Compare static contents and assign unique IDs for each static content.
288
216
  forEachClass([&](size_t Begin, size_t End) 
{ segregate(Begin, End, true); }59
);
289
216
290
216
  // Split groups by comparing relocations until convergence is obtained.
291
216
  do {
292
216
    Repeat = false;
293
216
    forEachClass(
294
216
        [&](size_t Begin, size_t End) 
{ segregate(Begin, End, false); }60
);
295
216
  } while (Repeat);
296
216
297
216
  log("ICF needed " + Twine(Cnt) + " iterations");
298
216
299
216
  // Merge sections in the same classs.
300
216
  forEachClass([&](size_t Begin, size_t End) {
301
60
    if (End - Begin == 1)
302
47
      return;
303
13
304
13
    log("Selected " + Chunks[Begin]->getDebugName());
305
27
    for (size_t I = Begin + 1; I < End; 
++I14
) {
306
14
      log("  Removed " + Chunks[I]->getDebugName());
307
14
      Chunks[Begin]->replace(Chunks[I]);
308
14
    }
309
13
  });
310
216
}
311
312
// Entry point to ICF.
313
216
void doICF(ArrayRef<Chunk *> Chunks) { ICF().run(Chunks); }
314
315
} // namespace coff
316
} // namespace lld