Coverage Report

Created: 2018-01-17 21:32

/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 "Chunks.h"
22
#include "Symbols.h"
23
#include "lld/Common/ErrorHandler.h"
24
#include "lld/Common/Timer.h"
25
#include "llvm/ADT/Hashing.h"
26
#include "llvm/Support/Debug.h"
27
#include "llvm/Support/Parallel.h"
28
#include "llvm/Support/raw_ostream.h"
29
#include <algorithm>
30
#include <atomic>
31
#include <vector>
32
33
using namespace llvm;
34
35
namespace lld {
36
namespace coff {
37
38
static Timer ICFTimer("ICF", Timer::root());
39
40
class ICF {
41
public:
42
  void run(ArrayRef<Chunk *> V);
43
44
private:
45
  void segregate(size_t Begin, size_t End, bool Constant);
46
47
  bool equalsConstant(const SectionChunk *A, const SectionChunk *B);
48
  bool equalsVariable(const SectionChunk *A, const SectionChunk *B);
49
50
  uint32_t getHash(SectionChunk *C);
51
  bool isEligible(SectionChunk *C);
52
53
  size_t findBoundary(size_t Begin, size_t End);
54
55
  void forEachClassRange(size_t Begin, size_t End,
56
                         std::function<void(size_t, size_t)> Fn);
57
58
  void forEachClass(std::function<void(size_t, size_t)> Fn);
59
60
  std::vector<SectionChunk *> Chunks;
61
  int Cnt = 0;
62
  std::atomic<bool> Repeat = {false};
63
};
64
65
// Returns a hash value for S.
66
0
uint32_t ICF::getHash(SectionChunk *C) {
67
0
  return hash_combine(C->getPermissions(), C->SectionName, C->NumRelocs,
68
0
                      C->Alignment, uint32_t(C->Header->SizeOfRawData),
69
0
                      C->Checksum, C->getContents());
70
0
}
71
72
// Returns true if section S is subject of ICF.
73
//
74
// Microsoft's documentation
75
// (https://msdn.microsoft.com/en-us/library/bxwfs976.aspx; visited April
76
// 2017) says that /opt:icf folds both functions and read-only data.
77
// Despite that, the MSVC linker folds only functions. We found
78
// a few instances of programs that are not safe for data merging.
79
// Therefore, we merge only functions just like the MSVC tool. However, we merge
80
// identical .xdata sections, because the address of unwind information is
81
// insignificant to the user program and the Visual C++ linker does this.
82
0
bool ICF::isEligible(SectionChunk *C) {
83
0
  // Non-comdat chunks, dead chunks, and writable chunks are not elegible.
84
0
  bool Writable = C->getPermissions() & llvm::COFF::IMAGE_SCN_MEM_WRITE;
85
0
  if (!C->isCOMDAT() || !C->isLive() || Writable)
86
0
    return false;
87
0
88
0
  // Code sections are eligible.
89
0
  if (C->getPermissions() & llvm::COFF::IMAGE_SCN_MEM_EXECUTE)
90
0
    return true;
91
0
92
0
  // .xdata unwind info sections are eligble.
93
0
  return C->getSectionName().split('$').first == ".xdata";
94
0
}
95
96
// Split an equivalence class into smaller classes.
97
0
void ICF::segregate(size_t Begin, size_t End, bool Constant) {
98
0
  while (Begin < End) {
99
0
    // Divide [Begin, End) into two. Let Mid be the start index of the
100
0
    // second group.
101
0
    auto Bound = std::stable_partition(
102
0
        Chunks.begin() + Begin + 1, Chunks.begin() + End, [&](SectionChunk *S) {
103
0
          if (Constant)
104
0
            return equalsConstant(Chunks[Begin], S);
105
0
          return equalsVariable(Chunks[Begin], S);
106
0
        });
107
0
    size_t Mid = Bound - Chunks.begin();
108
0
109
0
    // Split [Begin, End) into [Begin, Mid) and [Mid, End). We use Mid as an
110
0
    // equivalence class ID because every group ends with a unique index.
111
0
    for (size_t I = Begin; I < Mid; ++I)
112
0
      Chunks[I]->Class[(Cnt + 1) % 2] = Mid;
113
0
114
0
    // If we created a group, we need to iterate the main loop again.
115
0
    if (Mid != End)
116
0
      Repeat = true;
117
0
118
0
    Begin = Mid;
119
0
  }
120
0
}
121
122
// Compare "non-moving" part of two sections, namely everything
123
// except relocation targets.
124
0
bool ICF::equalsConstant(const SectionChunk *A, const SectionChunk *B) {
125
0
  if (A->NumRelocs != B->NumRelocs)
126
0
    return false;
127
0
128
0
  // Compare relocations.
129
0
  auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
130
0
    if (R1.Type != R2.Type ||
131
0
        R1.VirtualAddress != R2.VirtualAddress) {
132
0
      return false;
133
0
    }
134
0
    Symbol *B1 = A->File->getSymbol(R1.SymbolTableIndex);
135
0
    Symbol *B2 = B->File->getSymbol(R2.SymbolTableIndex);
136
0
    if (B1 == B2)
137
0
      return true;
138
0
    if (auto *D1 = dyn_cast<DefinedRegular>(B1))
139
0
      if (auto *D2 = dyn_cast<DefinedRegular>(B2))
140
0
        return D1->getValue() == D2->getValue() &&
141
0
               D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
142
0
    return false;
143
0
  };
144
0
  if (!std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq))
145
0
    return false;
146
0
147
0
  // Compare section attributes and contents.
148
0
  return A->getPermissions() == B->getPermissions() &&
149
0
         A->SectionName == B->SectionName && A->Alignment == B->Alignment &&
150
0
         A->Header->SizeOfRawData == B->Header->SizeOfRawData &&
151
0
         A->Checksum == B->Checksum && A->getContents() == B->getContents();
152
0
}
153
154
// Compare "moving" part of two sections, namely relocation targets.
155
0
bool ICF::equalsVariable(const SectionChunk *A, const SectionChunk *B) {
156
0
  // Compare relocations.
157
0
  auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
158
0
    Symbol *B1 = A->File->getSymbol(R1.SymbolTableIndex);
159
0
    Symbol *B2 = B->File->getSymbol(R2.SymbolTableIndex);
160
0
    if (B1 == B2)
161
0
      return true;
162
0
    if (auto *D1 = dyn_cast<DefinedRegular>(B1))
163
0
      if (auto *D2 = dyn_cast<DefinedRegular>(B2))
164
0
        return D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
165
0
    return false;
166
0
  };
167
0
  return std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq);
168
0
}
169
170
0
size_t ICF::findBoundary(size_t Begin, size_t End) {
171
0
  for (size_t I = Begin + 1; I < End; ++I)
172
0
    if (Chunks[Begin]->Class[Cnt % 2] != Chunks[I]->Class[Cnt % 2])
173
0
      return I;
174
0
  return End;
175
0
}
176
177
void ICF::forEachClassRange(size_t Begin, size_t End,
178
0
                            std::function<void(size_t, size_t)> Fn) {
179
0
  if (Begin > 0)
180
0
    Begin = findBoundary(Begin - 1, End);
181
0
182
0
  while (Begin < End) {
183
0
    size_t Mid = findBoundary(Begin, Chunks.size());
184
0
    Fn(Begin, Mid);
185
0
    Begin = Mid;
186
0
  }
187
0
}
188
189
// Call Fn on each class group.
190
0
void ICF::forEachClass(std::function<void(size_t, size_t)> Fn) {
191
0
  // If the number of sections are too small to use threading,
192
0
  // call Fn sequentially.
193
0
  if (Chunks.size() < 1024) {
194
0
    forEachClassRange(0, Chunks.size(), Fn);
195
0
    ++Cnt;
196
0
    return;
197
0
  }
198
0
199
0
  // Split sections into 256 shards and call Fn in parallel.
200
0
  size_t NumShards = 256;
201
0
  size_t Step = Chunks.size() / NumShards;
202
0
  for_each_n(parallel::par, size_t(0), NumShards, [&](size_t I) {
203
0
    size_t End = (I == NumShards - 1) ? Chunks.size() : (I + 1) * Step;
204
0
    forEachClassRange(I * Step, End, Fn);
205
0
  });
206
0
  ++Cnt;
207
0
}
208
209
// Merge identical COMDAT sections.
210
// Two sections are considered the same if their section headers,
211
// contents and relocations are all the same.
212
0
void ICF::run(ArrayRef<Chunk *> Vec) {
213
0
  ScopedTimer T(ICFTimer);
214
0
215
0
  // Collect only mergeable sections and group by hash value.
216
0
  uint32_t NextId = 1;
217
0
  for (Chunk *C : Vec) {
218
0
    if (auto *SC = dyn_cast<SectionChunk>(C)) {
219
0
      if (isEligible(SC))
220
0
        Chunks.push_back(SC);
221
0
      else
222
0
        SC->Class[0] = NextId++;
223
0
    }
224
0
  }
225
0
226
0
  // Initially, we use hash values to partition sections.
227
0
  for_each(parallel::par, Chunks.begin(), Chunks.end(), [&](SectionChunk *SC) {
228
0
    // Set MSB to 1 to avoid collisions with non-hash classs.
229
0
    SC->Class[0] = getHash(SC) | (1 << 31);
230
0
  });
231
0
232
0
  // From now on, sections in Chunks are ordered so that sections in
233
0
  // the same group are consecutive in the vector.
234
0
  std::stable_sort(Chunks.begin(), Chunks.end(),
235
0
                   [](SectionChunk *A, SectionChunk *B) {
236
0
                     return A->Class[0] < B->Class[0];
237
0
                   });
238
0
239
0
  // Compare static contents and assign unique IDs for each static content.
240
0
  forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
241
0
242
0
  // Split groups by comparing relocations until convergence is obtained.
243
0
  do {
244
0
    Repeat = false;
245
0
    forEachClass(
246
0
        [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
247
0
  } while (Repeat);
248
0
249
0
  log("ICF needed " + Twine(Cnt) + " iterations");
250
0
251
0
  // Merge sections in the same classs.
252
0
  forEachClass([&](size_t Begin, size_t End) {
253
0
    if (End - Begin == 1)
254
0
      return;
255
0
256
0
    log("Selected " + Chunks[Begin]->getDebugName());
257
0
    for (size_t I = Begin + 1; I < End; ++I) {
258
0
      log("  Removed " + Chunks[I]->getDebugName());
259
0
      Chunks[Begin]->replace(Chunks[I]);
260
0
    }
261
0
  });
262
0
}
263
264
// Entry point to ICF.
265
0
void doICF(ArrayRef<Chunk *> Chunks) { ICF().run(Chunks); }
266
267
} // namespace coff
268
} // namespace lld