Coverage Report

Created: 2017-09-21 03:39

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/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 "Error.h"
23
#include "Symbols.h"
24
#include "llvm/ADT/Hashing.h"
25
#include "llvm/Support/Debug.h"
26
#include "llvm/Support/Parallel.h"
27
#include "llvm/Support/raw_ostream.h"
28
#include <algorithm>
29
#include <atomic>
30
#include <vector>
31
32
using namespace llvm;
33
34
namespace lld {
35
namespace coff {
36
37
class ICF {
38
public:
39
  void run(const std::vector<Chunk *> &V);
40
41
private:
42
  void segregate(size_t Begin, size_t End, bool Constant);
43
44
  bool equalsConstant(const SectionChunk *A, const SectionChunk *B);
45
  bool equalsVariable(const SectionChunk *A, const SectionChunk *B);
46
47
  uint32_t getHash(SectionChunk *C);
48
  bool isEligible(SectionChunk *C);
49
50
  size_t findBoundary(size_t Begin, size_t End);
51
52
  void forEachClassRange(size_t Begin, size_t End,
53
                         std::function<void(size_t, size_t)> Fn);
54
55
  void forEachClass(std::function<void(size_t, size_t)> Fn);
56
57
  std::vector<SectionChunk *> Chunks;
58
  int Cnt = 0;
59
  std::atomic<bool> Repeat = {false};
60
};
61
62
// Returns a hash value for S.
63
30
uint32_t ICF::getHash(SectionChunk *C) {
64
30
  return hash_combine(C->getPermissions(), hash_value(C->SectionName),
65
30
                      C->NumRelocs, C->Alignment,
66
30
                      uint32_t(C->Header->SizeOfRawData), C->Checksum);
67
30
}
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.
77
712
bool ICF::isEligible(SectionChunk *C) {
78
57
  bool Global = C->Sym && C->Sym->isExternal();
79
712
  bool Executable = C->getPermissions() & llvm::COFF::IMAGE_SCN_MEM_EXECUTE;
80
712
  bool Writable = C->getPermissions() & llvm::COFF::IMAGE_SCN_MEM_WRITE;
81
712
  return C->isCOMDAT() && 
C->isLive()62
&&
Global42
&&
Executable35
&&
!Writable30
;
82
712
}
83
84
// Split an equivalence class into smaller classes.
85
46
void ICF::segregate(size_t Begin, size_t End, bool Constant) {
86
92
  while (
Begin < End92
) {
87
46
    // Divide [Begin, End) into two. Let Mid be the start index of the
88
46
    // second group.
89
46
    auto Bound = std::stable_partition(
90
14
        Chunks.begin() + Begin + 1, Chunks.begin() + End, [&](SectionChunk *S) {
91
14
          if (Constant)
92
7
            return equalsConstant(Chunks[Begin], S);
93
7
          return equalsVariable(Chunks[Begin], S);
94
7
        });
95
46
    size_t Mid = Bound - Chunks.begin();
96
46
97
46
    // Split [Begin, End) into [Begin, Mid) and [Mid, End). We use Mid as an
98
46
    // equivalence class ID because every group ends with a unique index.
99
106
    for (size_t I = Begin; 
I < Mid106
;
++I60
)
100
60
      Chunks[I]->Class[(Cnt + 1) % 2] = Mid;
101
46
102
46
    // If we created a group, we need to iterate the main loop again.
103
46
    if (Mid != End)
104
0
      Repeat = true;
105
46
106
46
    Begin = Mid;
107
46
  }
108
46
}
109
110
// Compare "non-moving" part of two sections, namely everything
111
// except relocation targets.
112
7
bool ICF::equalsConstant(const SectionChunk *A, const SectionChunk *B) {
113
7
  if (A->NumRelocs != B->NumRelocs)
114
0
    return false;
115
7
116
7
  // Compare relocations.
117
7
  
auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) 7
{
118
3
    if (R1.Type != R2.Type ||
119
3
        
R1.VirtualAddress != R2.VirtualAddress3
) {
120
0
      return false;
121
0
    }
122
3
    SymbolBody *B1 = A->File->getSymbolBody(R1.SymbolTableIndex);
123
3
    SymbolBody *B2 = B->File->getSymbolBody(R2.SymbolTableIndex);
124
3
    if (B1 == B2)
125
2
      return true;
126
1
    
if (auto *1
D11
= dyn_cast<DefinedRegular>(B1))
127
1
      
if (auto *1
D21
= dyn_cast<DefinedRegular>(B2))
128
1
        return D1->getValue() == D2->getValue() &&
129
1
               D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
130
0
    return false;
131
0
  };
132
7
  if (!std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq))
133
0
    return false;
134
7
135
7
  // Compare section attributes and contents.
136
7
  return A->getPermissions() == B->getPermissions() &&
137
7
         
A->SectionName == B->SectionName7
&&
A->Alignment == B->Alignment7
&&
138
7
         A->Header->SizeOfRawData == B->Header->SizeOfRawData &&
139
7
         
A->Checksum == B->Checksum7
&&
A->getContents() == B->getContents()7
;
140
7
}
141
142
// Compare "moving" part of two sections, namely relocation targets.
143
7
bool ICF::equalsVariable(const SectionChunk *A, const SectionChunk *B) {
144
7
  // Compare relocations.
145
3
  auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
146
3
    SymbolBody *B1 = A->File->getSymbolBody(R1.SymbolTableIndex);
147
3
    SymbolBody *B2 = B->File->getSymbolBody(R2.SymbolTableIndex);
148
3
    if (B1 == B2)
149
2
      return true;
150
1
    
if (auto *1
D11
= dyn_cast<DefinedRegular>(B1))
151
1
      
if (auto *1
D21
= dyn_cast<DefinedRegular>(B2))
152
1
        return D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
153
0
    return false;
154
0
  };
155
7
  return std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq);
156
7
}
157
158
69
size_t ICF::findBoundary(size_t Begin, size_t End) {
159
90
  for (size_t I = Begin + 1; 
I < End90
;
++I21
)
160
24
    
if (24
Chunks[Begin]->Class[Cnt % 2] != Chunks[I]->Class[Cnt % 2]24
)
161
3
      return I;
162
66
  return End;
163
69
}
164
165
void ICF::forEachClassRange(size_t Begin, size_t End,
166
747
                            std::function<void(size_t, size_t)> Fn) {
167
747
  if (Begin > 0)
168
0
    Begin = findBoundary(Begin - 1, End);
169
747
170
816
  while (
Begin < End816
) {
171
69
    size_t Mid = findBoundary(Begin, Chunks.size());
172
69
    Fn(Begin, Mid);
173
69
    Begin = Mid;
174
69
  }
175
747
}
176
177
// Call Fn on each class group.
178
747
void ICF::forEachClass(std::function<void(size_t, size_t)> Fn) {
179
747
  // If the number of sections are too small to use threading,
180
747
  // call Fn sequentially.
181
747
  if (
Chunks.size() < 1024747
) {
182
747
    forEachClassRange(0, Chunks.size(), Fn);
183
747
    ++Cnt;
184
747
    return;
185
747
  }
186
0
187
0
  // Split sections into 256 shards and call Fn in parallel.
188
0
  size_t NumShards = 256;
189
0
  size_t Step = Chunks.size() / NumShards;
190
0
  for_each_n(parallel::par, size_t(0), NumShards, [&](size_t I) {
191
0
    size_t End = (I == NumShards - 1) ? 
Chunks.size()0
:
(I + 1) * Step0
;
192
0
    forEachClassRange(I * Step, End, Fn);
193
0
  });
194
747
  ++Cnt;
195
747
}
196
197
// Merge identical COMDAT sections.
198
// Two sections are considered the same if their section headers,
199
// contents and relocations are all the same.
200
249
void ICF::run(const std::vector<Chunk *> &Vec) {
201
249
  // Collect only mergeable sections and group by hash value.
202
249
  uint32_t NextId = 1;
203
722
  for (Chunk *C : Vec) {
204
722
    if (auto *
SC722
= dyn_cast<SectionChunk>(C)) {
205
712
      if (isEligible(SC))
206
30
        Chunks.push_back(SC);
207
712
      else
208
682
        SC->Class[0] = NextId++;
209
712
    }
210
722
  }
211
249
212
249
  // Initially, we use hash values to partition sections.
213
249
  for (SectionChunk *SC : Chunks)
214
249
    // Set MSB to 1 to avoid collisions with non-hash classs.
215
30
    SC->Class[0] = getHash(SC) | (1 << 31);
216
249
217
249
  // From now on, sections in Chunks are ordered so that sections in
218
249
  // the same group are consecutive in the vector.
219
249
  std::stable_sort(Chunks.begin(), Chunks.end(),
220
8
                   [](SectionChunk *A, SectionChunk *B) {
221
8
                     return A->Class[0] < B->Class[0];
222
8
                   });
223
249
224
249
  // Compare static contents and assign unique IDs for each static content.
225
23
  forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
226
249
227
249
  // Split groups by comparing relocations until convergence is obtained.
228
249
  do {
229
249
    Repeat = false;
230
249
    forEachClass(
231
23
        [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
232
249
  } while (Repeat);
233
249
234
249
  log("ICF needed " + Twine(Cnt) + " iterations");
235
249
236
249
  // Merge sections in the same classs.
237
23
  forEachClass([&](size_t Begin, size_t End) {
238
23
    if (End - Begin == 1)
239
17
      return;
240
6
241
6
    log("Selected " + Chunks[Begin]->getDebugName());
242
13
    for (size_t I = Begin + 1; 
I < End13
;
++I7
) {
243
7
      log("  Removed " + Chunks[I]->getDebugName());
244
7
      Chunks[Begin]->replace(Chunks[I]);
245
7
    }
246
23
  });
247
249
}
248
249
// Entry point to ICF.
250
249
void doICF(const std::vector<Chunk *> &Chunks) { ICF().run(Chunks); }
251
252
} // namespace coff
253
} // namespace lld