Coverage Report

Created: 2018-06-25 02:00

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/lld/ELF/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. This 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
// In ICF, two sections are considered identical if they have the same
16
// section flags, section data, and relocations. Relocations are tricky,
17
// because two relocations are considered the same if they have the same
18
// relocation types, values, and if they point to the same sections *in
19
// terms of ICF*.
20
//
21
// Here is an example. If foo and bar defined below are compiled to the
22
// same machine instructions, ICF can and should merge the two, although
23
// their relocations point to each other.
24
//
25
//   void foo() { bar(); }
26
//   void bar() { foo(); }
27
//
28
// If you merge the two, their relocations point to the same section and
29
// thus you know they are mergeable, but how do you know they are
30
// mergeable in the first place? This is not an easy problem to solve.
31
//
32
// What we are doing in LLD is to partition sections into equivalence
33
// classes. Sections in the same equivalence class when the algorithm
34
// terminates are considered identical. Here are details:
35
//
36
// 1. First, we partition sections using their hash values as keys. Hash
37
//    values contain section types, section contents and numbers of
38
//    relocations. During this step, relocation targets are not taken into
39
//    account. We just put sections that apparently differ into different
40
//    equivalence classes.
41
//
42
// 2. Next, for each equivalence class, we visit sections to compare
43
//    relocation targets. Relocation targets are considered equivalent if
44
//    their targets are in the same equivalence class. Sections with
45
//    different relocation targets are put into different equivalence
46
//    clases.
47
//
48
// 3. If we split an equivalence class in step 2, two relocations
49
//    previously target the same equivalence class may now target
50
//    different equivalence classes. Therefore, we repeat step 2 until a
51
//    convergence is obtained.
52
//
53
// 4. For each equivalence class C, pick an arbitrary section in C, and
54
//    merge all the other sections in C with it.
55
//
56
// For small programs, this algorithm needs 3-5 iterations. For large
57
// programs such as Chromium, it takes more than 20 iterations.
58
//
59
// This algorithm was mentioned as an "optimistic algorithm" in [1],
60
// though gold implements a different algorithm than this.
61
//
62
// We parallelize each step so that multiple threads can work on different
63
// equivalence classes concurrently. That gave us a large performance
64
// boost when applying ICF on large programs. For example, MSVC link.exe
65
// or GNU gold takes 10-20 seconds to apply ICF on Chromium, whose output
66
// size is about 1.5 GB, but LLD can finish it in less than 2 seconds on a
67
// 2.8 GHz 40 core machine. Even without threading, LLD's ICF is still
68
// faster than MSVC or gold though.
69
//
70
// [1] Safe ICF: Pointer Safe and Unwinding aware Identical Code Folding
71
// in the Gold Linker
72
// http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/36912.pdf
73
//
74
//===----------------------------------------------------------------------===//
75
76
#include "ICF.h"
77
#include "Config.h"
78
#include "SymbolTable.h"
79
#include "Symbols.h"
80
#include "SyntheticSections.h"
81
#include "Writer.h"
82
#include "lld/Common/Threads.h"
83
#include "llvm/ADT/Hashing.h"
84
#include "llvm/BinaryFormat/ELF.h"
85
#include "llvm/Object/ELF.h"
86
#include <algorithm>
87
#include <atomic>
88
89
using namespace lld;
90
using namespace lld::elf;
91
using namespace llvm;
92
using namespace llvm::ELF;
93
using namespace llvm::object;
94
95
namespace {
96
template <class ELFT> class ICF {
97
public:
98
  void run();
99
100
private:
101
  void segregate(size_t Begin, size_t End, bool Constant);
102
103
  template <class RelTy>
104
  bool constantEq(const InputSection *A, ArrayRef<RelTy> RelsA,
105
                  const InputSection *B, ArrayRef<RelTy> RelsB);
106
107
  template <class RelTy>
108
  bool variableEq(const InputSection *A, ArrayRef<RelTy> RelsA,
109
                  const InputSection *B, ArrayRef<RelTy> RelsB);
110
111
  bool equalsConstant(const InputSection *A, const InputSection *B);
112
  bool equalsVariable(const InputSection *A, const InputSection *B);
113
114
  size_t findBoundary(size_t Begin, size_t End);
115
116
  void forEachClassRange(size_t Begin, size_t End,
117
                         llvm::function_ref<void(size_t, size_t)> Fn);
118
119
  void forEachClass(llvm::function_ref<void(size_t, size_t)> Fn);
120
121
  std::vector<InputSection *> Sections;
122
123
  // We repeat the main loop while `Repeat` is true.
124
  std::atomic<bool> Repeat;
125
126
  // The main loop counter.
127
  int Cnt = 0;
128
129
  // We have two locations for equivalence classes. On the first iteration
130
  // of the main loop, Class[0] has a valid value, and Class[1] contains
131
  // garbage. We read equivalence classes from slot 0 and write to slot 1.
132
  // So, Class[0] represents the current class, and Class[1] represents
133
  // the next class. On each iteration, we switch their roles and use them
134
  // alternately.
135
  //
136
  // Why are we doing this? Recall that other threads may be working on
137
  // other equivalence classes in parallel. They may read sections that we
138
  // are updating. We cannot update equivalence classes in place because
139
  // it breaks the invariance that all possibly-identical sections must be
140
  // in the same equivalence class at any moment. In other words, the for
141
  // loop to update equivalence classes is not atomic, and that is
142
  // observable from other threads. By writing new classes to other
143
  // places, we can keep the invariance.
144
  //
145
  // Below, `Current` has the index of the current class, and `Next` has
146
  // the index of the next class. If threading is enabled, they are either
147
  // (0, 1) or (1, 0).
148
  //
149
  // Note on single-thread: if that's the case, they are always (0, 0)
150
  // because we can safely read the next class without worrying about race
151
  // conditions. Using the same location makes this algorithm converge
152
  // faster because it uses results of the same iteration earlier.
153
  int Current = 0;
154
  int Next = 0;
155
};
156
}
157
158
// Returns a hash value for S. Note that the information about
159
// relocation targets is not included in the hash value.
160
165
template <class ELFT> static uint32_t getHash(InputSection *S) {
161
165
  return hash_combine(S->Flags, S->getSize(), S->NumRelocations, S->Data);
162
165
}
ICF.cpp:unsigned int getHash<llvm::object::ELFType<(llvm::support::endianness)1, false> >(lld::elf::InputSection*)
Line
Count
Source
160
13
template <class ELFT> static uint32_t getHash(InputSection *S) {
161
13
  return hash_combine(S->Flags, S->getSize(), S->NumRelocations, S->Data);
162
13
}
Unexecuted instantiation: ICF.cpp:unsigned int getHash<llvm::object::ELFType<(llvm::support::endianness)0, false> >(lld::elf::InputSection*)
ICF.cpp:unsigned int getHash<llvm::object::ELFType<(llvm::support::endianness)1, true> >(lld::elf::InputSection*)
Line
Count
Source
160
152
template <class ELFT> static uint32_t getHash(InputSection *S) {
161
152
  return hash_combine(S->Flags, S->getSize(), S->NumRelocations, S->Data);
162
152
}
Unexecuted instantiation: ICF.cpp:unsigned int getHash<llvm::object::ELFType<(llvm::support::endianness)0, true> >(lld::elf::InputSection*)
163
164
// Returns true if section S is subject of ICF.
165
230
static bool isEligible(InputSection *S) {
166
230
  if (!S->Live || S->KeepUnique || 
!(S->Flags & SHF_ALLOC)228
)
167
46
    return false;
168
184
169
184
  // Don't merge writable sections. .data.rel.ro sections are marked as writable
170
184
  // but are semantically read-only.
171
184
  if ((S->Flags & SHF_WRITE) && 
S->Name != ".data.rel.ro"5
&&
172
184
      
!S->Name.startswith(".data.rel.ro.")4
)
173
3
    return false;
174
181
175
181
  // Don't merge read only data sections unless
176
181
  // --ignore-data-address-equality was passed.
177
181
  if (!(S->Flags & SHF_EXECINSTR) && 
!Config->IgnoreDataAddressEquality16
)
178
10
    return false;
179
171
180
171
  // Don't merge synthetic sections as their Data member is not valid and empty.
181
171
  // The Data member needs to be valid for ICF as it is used by ICF to determine
182
171
  // the equality of section contents.
183
171
  if (isa<SyntheticSection>(S))
184
2
    return false;
185
169
186
169
  // .init and .fini contains instructions that must be executed to initialize
187
169
  // and finalize the process. They cannot and should not be merged.
188
169
  if (S->Name == ".init" || 
S->Name == ".fini"168
)
189
2
    return false;
190
167
191
167
  // A user program may enumerate sections named with a C identifier using
192
167
  // __start_* and __stop_* symbols. We cannot ICF any such sections because
193
167
  // that could change program semantics.
194
167
  if (isValidCIdentifier(S->Name))
195
2
    return false;
196
165
197
165
  return true;
198
165
}
199
200
// Split an equivalence class into smaller classes.
201
template <class ELFT>
202
220
void ICF<ELFT>::segregate(size_t Begin, size_t End, bool Constant) {
203
220
  // This loop rearranges sections in [Begin, End) so that all sections
204
220
  // that are equal in terms of equals{Constant,Variable} are contiguous
205
220
  // in [Begin, End).
206
220
  //
207
220
  // The algorithm is quadratic in the worst case, but that is not an
208
220
  // issue in practice because the number of the distinct sections in
209
220
  // each range is usually very small.
210
220
211
449
  while (Begin < End) {
212
229
    // Divide [Begin, End) into two. Let Mid be the start index of the
213
229
    // second group.
214
229
    auto Bound =
215
229
        std::stable_partition(Sections.begin() + Begin + 1,
216
229
                              Sections.begin() + End, [&](InputSection *S) {
217
114
                                if (Constant)
218
61
                                  return equalsConstant(Sections[Begin], S);
219
53
                                return equalsVariable(Sections[Begin], S);
220
53
                              });
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::segregate(unsigned long, unsigned long, bool)::'lambda'(lld::elf::InputSection*)::operator()(lld::elf::InputSection*) const
Line
Count
Source
216
6
                              Sections.begin() + End, [&](InputSection *S) {
217
6
                                if (Constant)
218
3
                                  return equalsConstant(Sections[Begin], S);
219
3
                                return equalsVariable(Sections[Begin], S);
220
3
                              });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::segregate(unsigned long, unsigned long, bool)::'lambda'(lld::elf::InputSection*)::operator()(lld::elf::InputSection*) const
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::segregate(unsigned long, unsigned long, bool)::'lambda'(lld::elf::InputSection*)::operator()(lld::elf::InputSection*) const
Line
Count
Source
216
108
                              Sections.begin() + End, [&](InputSection *S) {
217
108
                                if (Constant)
218
58
                                  return equalsConstant(Sections[Begin], S);
219
50
                                return equalsVariable(Sections[Begin], S);
220
50
                              });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::segregate(unsigned long, unsigned long, bool)::'lambda'(lld::elf::InputSection*)::operator()(lld::elf::InputSection*) const
221
229
    size_t Mid = Bound - Sections.begin();
222
229
223
229
    // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
224
229
    // updating the sections in [Begin, Mid). We use Mid as an equivalence
225
229
    // class ID because every group ends with a unique index.
226
563
    for (size_t I = Begin; I < Mid; 
++I334
)
227
334
      Sections[I]->Class[Next] = Mid;
228
229
229
229
    // If we created a group, we need to iterate the main loop again.
230
229
    if (Mid != End)
231
9
      Repeat = true;
232
229
233
229
    Begin = Mid;
234
229
  }
235
220
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::segregate(unsigned long, unsigned long, bool)
Line
Count
Source
202
20
void ICF<ELFT>::segregate(size_t Begin, size_t End, bool Constant) {
203
20
  // This loop rearranges sections in [Begin, End) so that all sections
204
20
  // that are equal in terms of equals{Constant,Variable} are contiguous
205
20
  // in [Begin, End).
206
20
  //
207
20
  // The algorithm is quadratic in the worst case, but that is not an
208
20
  // issue in practice because the number of the distinct sections in
209
20
  // each range is usually very small.
210
20
211
40
  while (Begin < End) {
212
20
    // Divide [Begin, End) into two. Let Mid be the start index of the
213
20
    // second group.
214
20
    auto Bound =
215
20
        std::stable_partition(Sections.begin() + Begin + 1,
216
20
                              Sections.begin() + End, [&](InputSection *S) {
217
20
                                if (Constant)
218
20
                                  return equalsConstant(Sections[Begin], S);
219
20
                                return equalsVariable(Sections[Begin], S);
220
20
                              });
221
20
    size_t Mid = Bound - Sections.begin();
222
20
223
20
    // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
224
20
    // updating the sections in [Begin, Mid). We use Mid as an equivalence
225
20
    // class ID because every group ends with a unique index.
226
46
    for (size_t I = Begin; I < Mid; 
++I26
)
227
26
      Sections[I]->Class[Next] = Mid;
228
20
229
20
    // If we created a group, we need to iterate the main loop again.
230
20
    if (Mid != End)
231
0
      Repeat = true;
232
20
233
20
    Begin = Mid;
234
20
  }
235
20
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::segregate(unsigned long, unsigned long, bool)
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::segregate(unsigned long, unsigned long, bool)
Line
Count
Source
202
200
void ICF<ELFT>::segregate(size_t Begin, size_t End, bool Constant) {
203
200
  // This loop rearranges sections in [Begin, End) so that all sections
204
200
  // that are equal in terms of equals{Constant,Variable} are contiguous
205
200
  // in [Begin, End).
206
200
  //
207
200
  // The algorithm is quadratic in the worst case, but that is not an
208
200
  // issue in practice because the number of the distinct sections in
209
200
  // each range is usually very small.
210
200
211
409
  while (Begin < End) {
212
209
    // Divide [Begin, End) into two. Let Mid be the start index of the
213
209
    // second group.
214
209
    auto Bound =
215
209
        std::stable_partition(Sections.begin() + Begin + 1,
216
209
                              Sections.begin() + End, [&](InputSection *S) {
217
209
                                if (Constant)
218
209
                                  return equalsConstant(Sections[Begin], S);
219
209
                                return equalsVariable(Sections[Begin], S);
220
209
                              });
221
209
    size_t Mid = Bound - Sections.begin();
222
209
223
209
    // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
224
209
    // updating the sections in [Begin, Mid). We use Mid as an equivalence
225
209
    // class ID because every group ends with a unique index.
226
517
    for (size_t I = Begin; I < Mid; 
++I308
)
227
308
      Sections[I]->Class[Next] = Mid;
228
209
229
209
    // If we created a group, we need to iterate the main loop again.
230
209
    if (Mid != End)
231
9
      Repeat = true;
232
209
233
209
    Begin = Mid;
234
209
  }
235
200
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::segregate(unsigned long, unsigned long, bool)
236
237
// Compare two lists of relocations.
238
template <class ELFT>
239
template <class RelTy>
240
bool ICF<ELFT>::constantEq(const InputSection *SecA, ArrayRef<RelTy> RA,
241
59
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
242
69
  for (size_t I = 0; I < RA.size(); 
++I10
) {
243
16
    if (RA[I].r_offset != RB[I].r_offset ||
244
16
        
RA[I].getType(Config->IsMips64EL) != RB[I].getType(Config->IsMips64EL)15
)
245
2
      return false;
246
14
247
14
    uint64_t AddA = getAddend<ELFT>(RA[I]);
248
14
    uint64_t AddB = getAddend<ELFT>(RB[I]);
249
14
250
14
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
251
14
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
252
14
    if (&SA == &SB) {
253
4
      if (AddA == AddB)
254
3
        continue;
255
1
      return false;
256
1
    }
257
10
258
10
    auto *DA = dyn_cast<Defined>(&SA);
259
10
    auto *DB = dyn_cast<Defined>(&SB);
260
10
    if (!DA || !DB)
261
0
      return false;
262
10
263
10
    // Relocations referring to absolute symbols are constant-equal if their
264
10
    // values are equal.
265
10
    if (!DA->Section && 
!DB->Section1
&&
DA->Value + AddA == DB->Value + AddB1
)
266
1
      continue;
267
9
    if (!DA->Section || !DB->Section)
268
0
      return false;
269
9
270
9
    if (DA->Section->kind() != DB->Section->kind())
271
0
      return false;
272
9
273
9
    // Relocations referring to InputSections are constant-equal if their
274
9
    // section offsets are equal.
275
9
    if (isa<InputSection>(DA->Section)) {
276
4
      if (DA->Value + AddA == DB->Value + AddB)
277
4
        continue;
278
0
      return false;
279
0
    }
280
5
281
5
    // Relocations referring to MergeInputSections are constant-equal if their
282
5
    // offsets in the output section are equal.
283
5
    auto *X = dyn_cast<MergeInputSection>(DA->Section);
284
5
    if (!X)
285
0
      return false;
286
5
    auto *Y = cast<MergeInputSection>(DB->Section);
287
5
    if (X->getParent() != Y->getParent())
288
1
      return false;
289
4
290
4
    uint64_t OffsetA =
291
4
        SA.isSection() ? 
X->getOffset(AddA)1
:
X->getOffset(DA->Value) + AddA3
;
292
4
    uint64_t OffsetB =
293
4
        SB.isSection() ? 
Y->getOffset(AddB)1
:
Y->getOffset(DB->Value) + AddB3
;
294
4
    if (OffsetA != OffsetB)
295
2
      return false;
296
4
  }
297
59
298
59
  
return true53
;
299
59
}
Unexecuted instantiation: ICF.cpp:bool (anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::constantEq<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, false>, true> >(lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, false>, true> >, lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, false>, true> >)
ICF.cpp:bool (anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::constantEq<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, false>, false> >(lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, false>, false> >, lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, false>, false> >)
Line
Count
Source
241
3
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
242
4
  for (size_t I = 0; I < RA.size(); 
++I1
) {
243
1
    if (RA[I].r_offset != RB[I].r_offset ||
244
1
        RA[I].getType(Config->IsMips64EL) != RB[I].getType(Config->IsMips64EL))
245
0
      return false;
246
1
247
1
    uint64_t AddA = getAddend<ELFT>(RA[I]);
248
1
    uint64_t AddB = getAddend<ELFT>(RB[I]);
249
1
250
1
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
251
1
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
252
1
    if (&SA == &SB) {
253
1
      if (AddA == AddB)
254
1
        continue;
255
0
      return false;
256
0
    }
257
0
258
0
    auto *DA = dyn_cast<Defined>(&SA);
259
0
    auto *DB = dyn_cast<Defined>(&SB);
260
0
    if (!DA || !DB)
261
0
      return false;
262
0
263
0
    // Relocations referring to absolute symbols are constant-equal if their
264
0
    // values are equal.
265
0
    if (!DA->Section && !DB->Section && DA->Value + AddA == DB->Value + AddB)
266
0
      continue;
267
0
    if (!DA->Section || !DB->Section)
268
0
      return false;
269
0
270
0
    if (DA->Section->kind() != DB->Section->kind())
271
0
      return false;
272
0
273
0
    // Relocations referring to InputSections are constant-equal if their
274
0
    // section offsets are equal.
275
0
    if (isa<InputSection>(DA->Section)) {
276
0
      if (DA->Value + AddA == DB->Value + AddB)
277
0
        continue;
278
0
      return false;
279
0
    }
280
0
281
0
    // Relocations referring to MergeInputSections are constant-equal if their
282
0
    // offsets in the output section are equal.
283
0
    auto *X = dyn_cast<MergeInputSection>(DA->Section);
284
0
    if (!X)
285
0
      return false;
286
0
    auto *Y = cast<MergeInputSection>(DB->Section);
287
0
    if (X->getParent() != Y->getParent())
288
0
      return false;
289
0
290
0
    uint64_t OffsetA =
291
0
        SA.isSection() ? X->getOffset(AddA) : X->getOffset(DA->Value) + AddA;
292
0
    uint64_t OffsetB =
293
0
        SB.isSection() ? Y->getOffset(AddB) : Y->getOffset(DB->Value) + AddB;
294
0
    if (OffsetA != OffsetB)
295
0
      return false;
296
0
  }
297
3
298
3
  return true;
299
3
}
Unexecuted instantiation: ICF.cpp:bool (anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::constantEq<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, false>, true> >(lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, false>, true> >, lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, false>, true> >)
Unexecuted instantiation: ICF.cpp:bool (anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::constantEq<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, false>, false> >(lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, false>, false> >, lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, false>, false> >)
ICF.cpp:bool (anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::constantEq<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, true> >(lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, true> >, lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, true> >)
Line
Count
Source
241
14
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
242
23
  for (size_t I = 0; I < RA.size(); 
++I9
) {
243
15
    if (RA[I].r_offset != RB[I].r_offset ||
244
15
        
RA[I].getType(Config->IsMips64EL) != RB[I].getType(Config->IsMips64EL)14
)
245
2
      return false;
246
13
247
13
    uint64_t AddA = getAddend<ELFT>(RA[I]);
248
13
    uint64_t AddB = getAddend<ELFT>(RB[I]);
249
13
250
13
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
251
13
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
252
13
    if (&SA == &SB) {
253
3
      if (AddA == AddB)
254
2
        continue;
255
1
      return false;
256
1
    }
257
10
258
10
    auto *DA = dyn_cast<Defined>(&SA);
259
10
    auto *DB = dyn_cast<Defined>(&SB);
260
10
    if (!DA || !DB)
261
0
      return false;
262
10
263
10
    // Relocations referring to absolute symbols are constant-equal if their
264
10
    // values are equal.
265
10
    if (!DA->Section && 
!DB->Section1
&&
DA->Value + AddA == DB->Value + AddB1
)
266
1
      continue;
267
9
    if (!DA->Section || !DB->Section)
268
0
      return false;
269
9
270
9
    if (DA->Section->kind() != DB->Section->kind())
271
0
      return false;
272
9
273
9
    // Relocations referring to InputSections are constant-equal if their
274
9
    // section offsets are equal.
275
9
    if (isa<InputSection>(DA->Section)) {
276
4
      if (DA->Value + AddA == DB->Value + AddB)
277
4
        continue;
278
0
      return false;
279
0
    }
280
5
281
5
    // Relocations referring to MergeInputSections are constant-equal if their
282
5
    // offsets in the output section are equal.
283
5
    auto *X = dyn_cast<MergeInputSection>(DA->Section);
284
5
    if (!X)
285
0
      return false;
286
5
    auto *Y = cast<MergeInputSection>(DB->Section);
287
5
    if (X->getParent() != Y->getParent())
288
1
      return false;
289
4
290
4
    uint64_t OffsetA =
291
4
        SA.isSection() ? 
X->getOffset(AddA)1
:
X->getOffset(DA->Value) + AddA3
;
292
4
    uint64_t OffsetB =
293
4
        SB.isSection() ? 
Y->getOffset(AddB)1
:
Y->getOffset(DB->Value) + AddB3
;
294
4
    if (OffsetA != OffsetB)
295
2
      return false;
296
4
  }
297
14
298
14
  
return true8
;
299
14
}
ICF.cpp:bool (anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::constantEq<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, false> >(lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, false> >, lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, false> >)
Line
Count
Source
241
42
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
242
42
  for (size_t I = 0; I < RA.size(); 
++I0
) {
243
0
    if (RA[I].r_offset != RB[I].r_offset ||
244
0
        RA[I].getType(Config->IsMips64EL) != RB[I].getType(Config->IsMips64EL))
245
0
      return false;
246
0
247
0
    uint64_t AddA = getAddend<ELFT>(RA[I]);
248
0
    uint64_t AddB = getAddend<ELFT>(RB[I]);
249
0
250
0
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
251
0
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
252
0
    if (&SA == &SB) {
253
0
      if (AddA == AddB)
254
0
        continue;
255
0
      return false;
256
0
    }
257
0
258
0
    auto *DA = dyn_cast<Defined>(&SA);
259
0
    auto *DB = dyn_cast<Defined>(&SB);
260
0
    if (!DA || !DB)
261
0
      return false;
262
0
263
0
    // Relocations referring to absolute symbols are constant-equal if their
264
0
    // values are equal.
265
0
    if (!DA->Section && !DB->Section && DA->Value + AddA == DB->Value + AddB)
266
0
      continue;
267
0
    if (!DA->Section || !DB->Section)
268
0
      return false;
269
0
270
0
    if (DA->Section->kind() != DB->Section->kind())
271
0
      return false;
272
0
273
0
    // Relocations referring to InputSections are constant-equal if their
274
0
    // section offsets are equal.
275
0
    if (isa<InputSection>(DA->Section)) {
276
0
      if (DA->Value + AddA == DB->Value + AddB)
277
0
        continue;
278
0
      return false;
279
0
    }
280
0
281
0
    // Relocations referring to MergeInputSections are constant-equal if their
282
0
    // offsets in the output section are equal.
283
0
    auto *X = dyn_cast<MergeInputSection>(DA->Section);
284
0
    if (!X)
285
0
      return false;
286
0
    auto *Y = cast<MergeInputSection>(DB->Section);
287
0
    if (X->getParent() != Y->getParent())
288
0
      return false;
289
0
290
0
    uint64_t OffsetA =
291
0
        SA.isSection() ? X->getOffset(AddA) : X->getOffset(DA->Value) + AddA;
292
0
    uint64_t OffsetB =
293
0
        SB.isSection() ? Y->getOffset(AddB) : Y->getOffset(DB->Value) + AddB;
294
0
    if (OffsetA != OffsetB)
295
0
      return false;
296
0
  }
297
42
298
42
  return true;
299
42
}
Unexecuted instantiation: ICF.cpp:bool (anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::constantEq<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, true>, true> >(lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, true>, true> >, lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, true>, true> >)
Unexecuted instantiation: ICF.cpp:bool (anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::constantEq<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, true>, false> >(lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, true>, false> >, lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, true>, false> >)
300
301
// Compare "non-moving" part of two InputSections, namely everything
302
// except relocation targets.
303
template <class ELFT>
304
61
bool ICF<ELFT>::equalsConstant(const InputSection *A, const InputSection *B) {
305
61
  if (A->NumRelocations != B->NumRelocations || A->Flags != B->Flags ||
306
61
      A->getSize() != B->getSize() || A->Data != B->Data)
307
0
    return false;
308
61
309
61
  // If two sections have different output sections, we cannot merge them.
310
61
  // FIXME: This doesn't do the right thing in the case where there is a linker
311
61
  // script. We probably need to move output section assignment before ICF to
312
61
  // get the correct behaviour here.
313
61
  if (getOutputSectionName(A) != getOutputSectionName(B))
314
2
    return false;
315
59
316
59
  if (A->AreRelocsRela)
317
14
    return constantEq(A, A->template relas<ELFT>(), B,
318
14
                      B->template relas<ELFT>());
319
45
  return constantEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
320
45
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::equalsConstant(lld::elf::InputSection const*, lld::elf::InputSection const*)
Line
Count
Source
304
3
bool ICF<ELFT>::equalsConstant(const InputSection *A, const InputSection *B) {
305
3
  if (A->NumRelocations != B->NumRelocations || A->Flags != B->Flags ||
306
3
      A->getSize() != B->getSize() || A->Data != B->Data)
307
0
    return false;
308
3
309
3
  // If two sections have different output sections, we cannot merge them.
310
3
  // FIXME: This doesn't do the right thing in the case where there is a linker
311
3
  // script. We probably need to move output section assignment before ICF to
312
3
  // get the correct behaviour here.
313
3
  if (getOutputSectionName(A) != getOutputSectionName(B))
314
0
    return false;
315
3
316
3
  if (A->AreRelocsRela)
317
0
    return constantEq(A, A->template relas<ELFT>(), B,
318
0
                      B->template relas<ELFT>());
319
3
  return constantEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
320
3
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::equalsConstant(lld::elf::InputSection const*, lld::elf::InputSection const*)
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::equalsConstant(lld::elf::InputSection const*, lld::elf::InputSection const*)
Line
Count
Source
304
58
bool ICF<ELFT>::equalsConstant(const InputSection *A, const InputSection *B) {
305
58
  if (A->NumRelocations != B->NumRelocations || A->Flags != B->Flags ||
306
58
      A->getSize() != B->getSize() || A->Data != B->Data)
307
0
    return false;
308
58
309
58
  // If two sections have different output sections, we cannot merge them.
310
58
  // FIXME: This doesn't do the right thing in the case where there is a linker
311
58
  // script. We probably need to move output section assignment before ICF to
312
58
  // get the correct behaviour here.
313
58
  if (getOutputSectionName(A) != getOutputSectionName(B))
314
2
    return false;
315
56
316
56
  if (A->AreRelocsRela)
317
14
    return constantEq(A, A->template relas<ELFT>(), B,
318
14
                      B->template relas<ELFT>());
319
42
  return constantEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
320
42
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::equalsConstant(lld::elf::InputSection const*, lld::elf::InputSection const*)
321
322
// Compare two lists of relocations. Returns true if all pairs of
323
// relocations point to the same section in terms of ICF.
324
template <class ELFT>
325
template <class RelTy>
326
bool ICF<ELFT>::variableEq(const InputSection *SecA, ArrayRef<RelTy> RA,
327
53
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
328
53
  assert(RA.size() == RB.size());
329
53
330
62
  for (size_t I = 0; I < RA.size(); 
++I9
) {
331
10
    // The two sections must be identical.
332
10
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
333
10
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
334
10
    if (&SA == &SB)
335
3
      continue;
336
7
337
7
    auto *DA = cast<Defined>(&SA);
338
7
    auto *DB = cast<Defined>(&SB);
339
7
340
7
    // We already dealt with absolute and non-InputSection symbols in
341
7
    // constantEq, and for InputSections we have already checked everything
342
7
    // except the equivalence class.
343
7
    if (!DA->Section)
344
1
      continue;
345
6
    auto *X = dyn_cast<InputSection>(DA->Section);
346
6
    if (!X)
347
2
      continue;
348
4
    auto *Y = cast<InputSection>(DB->Section);
349
4
350
4
    // Ineligible sections are in the special equivalence class 0.
351
4
    // They can never be the same in terms of the equivalence class.
352
4
    if (X->Class[Current] == 0)
353
1
      return false;
354
3
    if (X->Class[Current] != Y->Class[Current])
355
0
      return false;
356
52
  };
357
52
358
52
  return true;
359
53
}
Unexecuted instantiation: ICF.cpp:bool (anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::variableEq<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, false>, true> >(lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, false>, true> >, lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, false>, true> >)
ICF.cpp:bool (anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::variableEq<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, false>, false> >(lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, false>, false> >, lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, false>, false> >)
Line
Count
Source
327
3
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
328
3
  assert(RA.size() == RB.size());
329
3
330
4
  for (size_t I = 0; I < RA.size(); 
++I1
) {
331
1
    // The two sections must be identical.
332
1
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
333
1
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
334
1
    if (&SA == &SB)
335
1
      continue;
336
0
337
0
    auto *DA = cast<Defined>(&SA);
338
0
    auto *DB = cast<Defined>(&SB);
339
0
340
0
    // We already dealt with absolute and non-InputSection symbols in
341
0
    // constantEq, and for InputSections we have already checked everything
342
0
    // except the equivalence class.
343
0
    if (!DA->Section)
344
0
      continue;
345
0
    auto *X = dyn_cast<InputSection>(DA->Section);
346
0
    if (!X)
347
0
      continue;
348
0
    auto *Y = cast<InputSection>(DB->Section);
349
0
350
0
    // Ineligible sections are in the special equivalence class 0.
351
0
    // They can never be the same in terms of the equivalence class.
352
0
    if (X->Class[Current] == 0)
353
0
      return false;
354
0
    if (X->Class[Current] != Y->Class[Current])
355
0
      return false;
356
3
  };
357
3
358
3
  return true;
359
3
}
Unexecuted instantiation: ICF.cpp:bool (anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::variableEq<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, false>, true> >(lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, false>, true> >, lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, false>, true> >)
Unexecuted instantiation: ICF.cpp:bool (anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::variableEq<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, false>, false> >(lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, false>, false> >, lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, false>, false> >)
ICF.cpp:bool (anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::variableEq<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, true> >(lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, true> >, lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, true> >)
Line
Count
Source
327
8
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
328
8
  assert(RA.size() == RB.size());
329
8
330
16
  for (size_t I = 0; I < RA.size(); 
++I8
) {
331
9
    // The two sections must be identical.
332
9
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
333
9
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
334
9
    if (&SA == &SB)
335
2
      continue;
336
7
337
7
    auto *DA = cast<Defined>(&SA);
338
7
    auto *DB = cast<Defined>(&SB);
339
7
340
7
    // We already dealt with absolute and non-InputSection symbols in
341
7
    // constantEq, and for InputSections we have already checked everything
342
7
    // except the equivalence class.
343
7
    if (!DA->Section)
344
1
      continue;
345
6
    auto *X = dyn_cast<InputSection>(DA->Section);
346
6
    if (!X)
347
2
      continue;
348
4
    auto *Y = cast<InputSection>(DB->Section);
349
4
350
4
    // Ineligible sections are in the special equivalence class 0.
351
4
    // They can never be the same in terms of the equivalence class.
352
4
    if (X->Class[Current] == 0)
353
1
      return false;
354
3
    if (X->Class[Current] != Y->Class[Current])
355
0
      return false;
356
7
  };
357
7
358
7
  return true;
359
8
}
ICF.cpp:bool (anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::variableEq<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, false> >(lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, false> >, lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, false> >)
Line
Count
Source
327
42
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
328
42
  assert(RA.size() == RB.size());
329
42
330
42
  for (size_t I = 0; I < RA.size(); 
++I0
) {
331
0
    // The two sections must be identical.
332
0
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
333
0
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
334
0
    if (&SA == &SB)
335
0
      continue;
336
0
337
0
    auto *DA = cast<Defined>(&SA);
338
0
    auto *DB = cast<Defined>(&SB);
339
0
340
0
    // We already dealt with absolute and non-InputSection symbols in
341
0
    // constantEq, and for InputSections we have already checked everything
342
0
    // except the equivalence class.
343
0
    if (!DA->Section)
344
0
      continue;
345
0
    auto *X = dyn_cast<InputSection>(DA->Section);
346
0
    if (!X)
347
0
      continue;
348
0
    auto *Y = cast<InputSection>(DB->Section);
349
0
350
0
    // Ineligible sections are in the special equivalence class 0.
351
0
    // They can never be the same in terms of the equivalence class.
352
0
    if (X->Class[Current] == 0)
353
0
      return false;
354
0
    if (X->Class[Current] != Y->Class[Current])
355
0
      return false;
356
42
  };
357
42
358
42
  return true;
359
42
}
Unexecuted instantiation: ICF.cpp:bool (anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::variableEq<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, true>, true> >(lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, true>, true> >, lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, true>, true> >)
Unexecuted instantiation: ICF.cpp:bool (anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::variableEq<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, true>, false> >(lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, true>, false> >, lld::elf::InputSection const*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, true>, false> >)
360
361
// Compare "moving" part of two InputSections, namely relocation targets.
362
template <class ELFT>
363
53
bool ICF<ELFT>::equalsVariable(const InputSection *A, const InputSection *B) {
364
53
  if (A->AreRelocsRela)
365
8
    return variableEq(A, A->template relas<ELFT>(), B,
366
8
                      B->template relas<ELFT>());
367
45
  return variableEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
368
45
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::equalsVariable(lld::elf::InputSection const*, lld::elf::InputSection const*)
Line
Count
Source
363
3
bool ICF<ELFT>::equalsVariable(const InputSection *A, const InputSection *B) {
364
3
  if (A->AreRelocsRela)
365
0
    return variableEq(A, A->template relas<ELFT>(), B,
366
0
                      B->template relas<ELFT>());
367
3
  return variableEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
368
3
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::equalsVariable(lld::elf::InputSection const*, lld::elf::InputSection const*)
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::equalsVariable(lld::elf::InputSection const*, lld::elf::InputSection const*)
Line
Count
Source
363
50
bool ICF<ELFT>::equalsVariable(const InputSection *A, const InputSection *B) {
364
50
  if (A->AreRelocsRela)
365
8
    return variableEq(A, A->template relas<ELFT>(), B,
366
8
                      B->template relas<ELFT>());
367
42
  return variableEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
368
42
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::equalsVariable(lld::elf::InputSection const*, lld::elf::InputSection const*)
369
370
333
template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t Begin, size_t End) {
371
333
  uint32_t Class = Sections[Begin]->Class[Current];
372
499
  for (size_t I = Begin + 1; I < End; 
++I166
)
373
372
    if (Class != Sections[I]->Class[Current])
374
206
      return I;
375
333
  
return End127
;
376
333
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::findBoundary(unsigned long, unsigned long)
Line
Count
Source
370
30
template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t Begin, size_t End) {
371
30
  uint32_t Class = Sections[Begin]->Class[Current];
372
39
  for (size_t I = Begin + 1; I < End; 
++I9
)
373
30
    if (Class != Sections[I]->Class[Current])
374
21
      return I;
375
30
  
return End9
;
376
30
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::findBoundary(unsigned long, unsigned long)
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::findBoundary(unsigned long, unsigned long)
Line
Count
Source
370
303
template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t Begin, size_t End) {
371
303
  uint32_t Class = Sections[Begin]->Class[Current];
372
460
  for (size_t I = Begin + 1; I < End; 
++I157
)
373
342
    if (Class != Sections[I]->Class[Current])
374
185
      return I;
375
303
  
return End118
;
376
303
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::findBoundary(unsigned long, unsigned long)
377
378
// Sections in the same equivalence class are contiguous in Sections
379
// vector. Therefore, Sections vector can be considered as contiguous
380
// groups of sections, grouped by the class.
381
//
382
// This function calls Fn on every group within [Begin, End).
383
template <class ELFT>
384
void ICF<ELFT>::forEachClassRange(size_t Begin, size_t End,
385
127
                                  llvm::function_ref<void(size_t, size_t)> Fn) {
386
460
  while (Begin < End) {
387
333
    size_t Mid = findBoundary(Begin, End);
388
333
    Fn(Begin, Mid);
389
333
    Begin = Mid;
390
333
  }
391
127
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::forEachClassRange(unsigned long, unsigned long, llvm::function_ref<void (unsigned long, unsigned long)>)
Line
Count
Source
385
9
                                  llvm::function_ref<void(size_t, size_t)> Fn) {
386
39
  while (Begin < End) {
387
30
    size_t Mid = findBoundary(Begin, End);
388
30
    Fn(Begin, Mid);
389
30
    Begin = Mid;
390
30
  }
391
9
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::forEachClassRange(unsigned long, unsigned long, llvm::function_ref<void (unsigned long, unsigned long)>)
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::forEachClassRange(unsigned long, unsigned long, llvm::function_ref<void (unsigned long, unsigned long)>)
Line
Count
Source
385
118
                                  llvm::function_ref<void(size_t, size_t)> Fn) {
386
421
  while (Begin < End) {
387
303
    size_t Mid = findBoundary(Begin, End);
388
303
    Fn(Begin, Mid);
389
303
    Begin = Mid;
390
303
  }
391
118
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::forEachClassRange(unsigned long, unsigned long, llvm::function_ref<void (unsigned long, unsigned long)>)
392
393
// Call Fn on each equivalence class.
394
template <class ELFT>
395
85
void ICF<ELFT>::forEachClass(llvm::function_ref<void(size_t, size_t)> Fn) {
396
85
  // If threading is disabled or the number of sections are
397
85
  // too small to use threading, call Fn sequentially.
398
85
  if (!ThreadsEnabled || Sections.size() < 1024) {
399
85
    forEachClassRange(0, Sections.size(), Fn);
400
85
    ++Cnt;
401
85
    return;
402
85
  }
403
0
404
0
  Current = Cnt % 2;
405
0
  Next = (Cnt + 1) % 2;
406
0
407
0
  // Shard into non-overlapping intervals, and call Fn in parallel.
408
0
  // The sharding must be completed before any calls to Fn are made
409
0
  // so that Fn can modify the Chunks in its shard without causing data
410
0
  // races.
411
0
  const size_t NumShards = 256;
412
0
  size_t Step = Sections.size() / NumShards;
413
0
  size_t Boundaries[NumShards + 1];
414
0
  Boundaries[0] = 0;
415
0
  Boundaries[NumShards] = Sections.size();
416
0
417
0
  parallelForEachN(1, NumShards, [&](size_t I) {
418
0
    Boundaries[I] = findBoundary((I - 1) * Step, Sections.size());
419
0
  });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::forEachClass(llvm::function_ref<void (unsigned long, unsigned long)>)::'lambda'(unsigned long)::operator()(unsigned long) const
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::forEachClass(llvm::function_ref<void (unsigned long, unsigned long)>)::'lambda'(unsigned long)::operator()(unsigned long) const
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::forEachClass(llvm::function_ref<void (unsigned long, unsigned long)>)::'lambda'(unsigned long)::operator()(unsigned long) const
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::forEachClass(llvm::function_ref<void (unsigned long, unsigned long)>)::'lambda'(unsigned long)::operator()(unsigned long) const
420
0
421
0
  parallelForEachN(1, NumShards + 1, [&](size_t I) {
422
0
    if (Boundaries[I - 1] < Boundaries[I])
423
0
      forEachClassRange(Boundaries[I - 1], Boundaries[I], Fn);
424
0
  });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::forEachClass(llvm::function_ref<void (unsigned long, unsigned long)>)::'lambda0'(unsigned long)::operator()(unsigned long) const
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::forEachClass(llvm::function_ref<void (unsigned long, unsigned long)>)::'lambda0'(unsigned long)::operator()(unsigned long) const
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::forEachClass(llvm::function_ref<void (unsigned long, unsigned long)>)::'lambda0'(unsigned long)::operator()(unsigned long) const
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::forEachClass(llvm::function_ref<void (unsigned long, unsigned long)>)::'lambda0'(unsigned long)::operator()(unsigned long) const
425
0
  ++Cnt;
426
0
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::forEachClass(llvm::function_ref<void (unsigned long, unsigned long)>)
Line
Count
Source
395
6
void ICF<ELFT>::forEachClass(llvm::function_ref<void(size_t, size_t)> Fn) {
396
6
  // If threading is disabled or the number of sections are
397
6
  // too small to use threading, call Fn sequentially.
398
6
  if (!ThreadsEnabled || Sections.size() < 1024) {
399
6
    forEachClassRange(0, Sections.size(), Fn);
400
6
    ++Cnt;
401
6
    return;
402
6
  }
403
0
404
0
  Current = Cnt % 2;
405
0
  Next = (Cnt + 1) % 2;
406
0
407
0
  // Shard into non-overlapping intervals, and call Fn in parallel.
408
0
  // The sharding must be completed before any calls to Fn are made
409
0
  // so that Fn can modify the Chunks in its shard without causing data
410
0
  // races.
411
0
  const size_t NumShards = 256;
412
0
  size_t Step = Sections.size() / NumShards;
413
0
  size_t Boundaries[NumShards + 1];
414
0
  Boundaries[0] = 0;
415
0
  Boundaries[NumShards] = Sections.size();
416
0
417
0
  parallelForEachN(1, NumShards, [&](size_t I) {
418
0
    Boundaries[I] = findBoundary((I - 1) * Step, Sections.size());
419
0
  });
420
0
421
0
  parallelForEachN(1, NumShards + 1, [&](size_t I) {
422
0
    if (Boundaries[I - 1] < Boundaries[I])
423
0
      forEachClassRange(Boundaries[I - 1], Boundaries[I], Fn);
424
0
  });
425
0
  ++Cnt;
426
0
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::forEachClass(llvm::function_ref<void (unsigned long, unsigned long)>)
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::forEachClass(llvm::function_ref<void (unsigned long, unsigned long)>)
Line
Count
Source
395
79
void ICF<ELFT>::forEachClass(llvm::function_ref<void(size_t, size_t)> Fn) {
396
79
  // If threading is disabled or the number of sections are
397
79
  // too small to use threading, call Fn sequentially.
398
79
  if (!ThreadsEnabled || Sections.size() < 1024) {
399
79
    forEachClassRange(0, Sections.size(), Fn);
400
79
    ++Cnt;
401
79
    return;
402
79
  }
403
0
404
0
  Current = Cnt % 2;
405
0
  Next = (Cnt + 1) % 2;
406
0
407
0
  // Shard into non-overlapping intervals, and call Fn in parallel.
408
0
  // The sharding must be completed before any calls to Fn are made
409
0
  // so that Fn can modify the Chunks in its shard without causing data
410
0
  // races.
411
0
  const size_t NumShards = 256;
412
0
  size_t Step = Sections.size() / NumShards;
413
0
  size_t Boundaries[NumShards + 1];
414
0
  Boundaries[0] = 0;
415
0
  Boundaries[NumShards] = Sections.size();
416
0
417
0
  parallelForEachN(1, NumShards, [&](size_t I) {
418
0
    Boundaries[I] = findBoundary((I - 1) * Step, Sections.size());
419
0
  });
420
0
421
0
  parallelForEachN(1, NumShards + 1, [&](size_t I) {
422
0
    if (Boundaries[I - 1] < Boundaries[I])
423
0
      forEachClassRange(Boundaries[I - 1], Boundaries[I], Fn);
424
0
  });
425
0
  ++Cnt;
426
0
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::forEachClass(llvm::function_ref<void (unsigned long, unsigned long)>)
427
428
87
static void print(const Twine &S) {
429
87
  if (Config->PrintIcfSections)
430
50
    message(S);
431
87
}
432
433
// The main function of ICF.
434
42
template <class ELFT> void ICF<ELFT>::run() {
435
42
  // Collect sections to merge.
436
42
  for (InputSectionBase *Sec : InputSections)
437
232
    if (auto *S = dyn_cast<InputSection>(Sec))
438
230
      if (isEligible(S))
439
165
        Sections.push_back(S);
440
42
441
42
  // Initially, we use hash values to partition sections.
442
165
  parallelForEach(Sections, [&](InputSection *S) {
443
165
    // Set MSB to 1 to avoid collisions with non-hash IDs.
444
165
    S->Class[0] = getHash<ELFT>(S) | (1U << 31);
445
165
  });
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::run()::'lambda'(lld::elf::InputSection*)::operator()(lld::elf::InputSection*) const
Line
Count
Source
442
13
  parallelForEach(Sections, [&](InputSection *S) {
443
13
    // Set MSB to 1 to avoid collisions with non-hash IDs.
444
13
    S->Class[0] = getHash<ELFT>(S) | (1U << 31);
445
13
  });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::run()::'lambda'(lld::elf::InputSection*)::operator()(lld::elf::InputSection*) const
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::run()::'lambda'(lld::elf::InputSection*)::operator()(lld::elf::InputSection*) const
Line
Count
Source
442
152
  parallelForEach(Sections, [&](InputSection *S) {
443
152
    // Set MSB to 1 to avoid collisions with non-hash IDs.
444
152
    S->Class[0] = getHash<ELFT>(S) | (1U << 31);
445
152
  });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::run()::'lambda'(lld::elf::InputSection*)::operator()(lld::elf::InputSection*) const
446
42
447
42
  // From now on, sections in Sections vector are ordered so that sections
448
42
  // in the same equivalence class are consecutive in the vector.
449
42
  std::stable_sort(Sections.begin(), Sections.end(),
450
228
                   [](InputSection *A, InputSection *B) {
451
228
                     return A->Class[0] < B->Class[0];
452
228
                   });
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::run()::'lambda'(lld::elf::InputSection*, lld::elf::InputSection*)::operator()(lld::elf::InputSection*, lld::elf::InputSection*) const
Line
Count
Source
450
19
                   [](InputSection *A, InputSection *B) {
451
19
                     return A->Class[0] < B->Class[0];
452
19
                   });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::run()::'lambda'(lld::elf::InputSection*, lld::elf::InputSection*)::operator()(lld::elf::InputSection*, lld::elf::InputSection*) const
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::run()::'lambda'(lld::elf::InputSection*, lld::elf::InputSection*)::operator()(lld::elf::InputSection*, lld::elf::InputSection*) const
Line
Count
Source
450
209
                   [](InputSection *A, InputSection *B) {
451
209
                     return A->Class[0] < B->Class[0];
452
209
                   });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::run()::'lambda'(lld::elf::InputSection*, lld::elf::InputSection*)::operator()(lld::elf::InputSection*, lld::elf::InputSection*) const
453
42
454
42
  // Compare static contents and assign unique IDs for each static content.
455
104
  forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::run()::'lambda'(unsigned long, unsigned long)::operator()(unsigned long, unsigned long) const
Line
Count
Source
455
10
  forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::run()::'lambda'(unsigned long, unsigned long)::operator()(unsigned long, unsigned long) const
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::run()::'lambda'(unsigned long, unsigned long)::operator()(unsigned long, unsigned long) const
Line
Count
Source
455
94
  forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::run()::'lambda'(unsigned long, unsigned long)::operator()(unsigned long, unsigned long) const
456
42
457
42
  // Split groups by comparing relocations until convergence is obtained.
458
43
  do {
459
43
    Repeat = false;
460
43
    forEachClass(
461
116
        [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::run()::'lambda0'(unsigned long, unsigned long)::operator()(unsigned long, unsigned long) const
Line
Count
Source
461
10
        [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::run()::'lambda0'(unsigned long, unsigned long)::operator()(unsigned long, unsigned long) const
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::run()::'lambda0'(unsigned long, unsigned long)::operator()(unsigned long, unsigned long) const
Line
Count
Source
461
106
        [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::run()::'lambda0'(unsigned long, unsigned long)::operator()(unsigned long, unsigned long) const
462
43
  } while (Repeat);
463
42
464
42
  log("ICF needed " + Twine(Cnt) + " iterations");
465
42
466
42
  // Merge sections by the equivalence class.
467
113
  forEachClassRange(0, Sections.size(), [&](size_t Begin, size_t End) {
468
113
    if (End - Begin == 1)
469
78
      return;
470
35
    print("selected section " + toString(Sections[Begin]));
471
87
    for (size_t I = Begin + 1; I < End; 
++I52
) {
472
52
      print("  removing identical section " + toString(Sections[I]));
473
52
      Sections[Begin]->replace(Sections[I]);
474
52
475
52
      // At this point we know sections merged are fully identical and hence
476
52
      // we want to remove duplicate implicit dependencies such as link order
477
52
      // and relocation sections.
478
52
      for (InputSection *IS : Sections[I]->DependentSections)
479
2
        IS->Live = false;
480
52
    }
481
35
  });
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::run()::'lambda1'(unsigned long, unsigned long)::operator()(unsigned long, unsigned long) const
Line
Count
Source
467
10
  forEachClassRange(0, Sections.size(), [&](size_t Begin, size_t End) {
468
10
    if (End - Begin == 1)
469
7
      return;
470
3
    print("selected section " + toString(Sections[Begin]));
471
6
    for (size_t I = Begin + 1; I < End; 
++I3
) {
472
3
      print("  removing identical section " + toString(Sections[I]));
473
3
      Sections[Begin]->replace(Sections[I]);
474
3
475
3
      // At this point we know sections merged are fully identical and hence
476
3
      // we want to remove duplicate implicit dependencies such as link order
477
3
      // and relocation sections.
478
3
      for (InputSection *IS : Sections[I]->DependentSections)
479
1
        IS->Live = false;
480
3
    }
481
3
  });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::run()::'lambda1'(unsigned long, unsigned long)::operator()(unsigned long, unsigned long) const
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::run()::'lambda1'(unsigned long, unsigned long)::operator()(unsigned long, unsigned long) const
Line
Count
Source
467
103
  forEachClassRange(0, Sections.size(), [&](size_t Begin, size_t End) {
468
103
    if (End - Begin == 1)
469
71
      return;
470
32
    print("selected section " + toString(Sections[Begin]));
471
81
    for (size_t I = Begin + 1; I < End; 
++I49
) {
472
49
      print("  removing identical section " + toString(Sections[I]));
473
49
      Sections[Begin]->replace(Sections[I]);
474
49
475
49
      // At this point we know sections merged are fully identical and hence
476
49
      // we want to remove duplicate implicit dependencies such as link order
477
49
      // and relocation sections.
478
49
      for (InputSection *IS : Sections[I]->DependentSections)
479
1
        IS->Live = false;
480
49
    }
481
32
  });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::run()::'lambda1'(unsigned long, unsigned long)::operator()(unsigned long, unsigned long) const
482
42
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::run()
Line
Count
Source
434
3
template <class ELFT> void ICF<ELFT>::run() {
435
3
  // Collect sections to merge.
436
3
  for (InputSectionBase *Sec : InputSections)
437
18
    if (auto *S = dyn_cast<InputSection>(Sec))
438
18
      if (isEligible(S))
439
13
        Sections.push_back(S);
440
3
441
3
  // Initially, we use hash values to partition sections.
442
3
  parallelForEach(Sections, [&](InputSection *S) {
443
3
    // Set MSB to 1 to avoid collisions with non-hash IDs.
444
3
    S->Class[0] = getHash<ELFT>(S) | (1U << 31);
445
3
  });
446
3
447
3
  // From now on, sections in Sections vector are ordered so that sections
448
3
  // in the same equivalence class are consecutive in the vector.
449
3
  std::stable_sort(Sections.begin(), Sections.end(),
450
3
                   [](InputSection *A, InputSection *B) {
451
3
                     return A->Class[0] < B->Class[0];
452
3
                   });
453
3
454
3
  // Compare static contents and assign unique IDs for each static content.
455
3
  forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
456
3
457
3
  // Split groups by comparing relocations until convergence is obtained.
458
3
  do {
459
3
    Repeat = false;
460
3
    forEachClass(
461
3
        [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
462
3
  } while (Repeat);
463
3
464
3
  log("ICF needed " + Twine(Cnt) + " iterations");
465
3
466
3
  // Merge sections by the equivalence class.
467
3
  forEachClassRange(0, Sections.size(), [&](size_t Begin, size_t End) {
468
3
    if (End - Begin == 1)
469
3
      return;
470
3
    print("selected section " + toString(Sections[Begin]));
471
3
    for (size_t I = Begin + 1; I < End; ++I) {
472
3
      print("  removing identical section " + toString(Sections[I]));
473
3
      Sections[Begin]->replace(Sections[I]);
474
3
475
3
      // At this point we know sections merged are fully identical and hence
476
3
      // we want to remove duplicate implicit dependencies such as link order
477
3
      // and relocation sections.
478
3
      for (InputSection *IS : Sections[I]->DependentSections)
479
3
        IS->Live = false;
480
3
    }
481
3
  });
482
3
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::run()
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::run()
Line
Count
Source
434
39
template <class ELFT> void ICF<ELFT>::run() {
435
39
  // Collect sections to merge.
436
39
  for (InputSectionBase *Sec : InputSections)
437
214
    if (auto *S = dyn_cast<InputSection>(Sec))
438
212
      if (isEligible(S))
439
152
        Sections.push_back(S);
440
39
441
39
  // Initially, we use hash values to partition sections.
442
39
  parallelForEach(Sections, [&](InputSection *S) {
443
39
    // Set MSB to 1 to avoid collisions with non-hash IDs.
444
39
    S->Class[0] = getHash<ELFT>(S) | (1U << 31);
445
39
  });
446
39
447
39
  // From now on, sections in Sections vector are ordered so that sections
448
39
  // in the same equivalence class are consecutive in the vector.
449
39
  std::stable_sort(Sections.begin(), Sections.end(),
450
39
                   [](InputSection *A, InputSection *B) {
451
39
                     return A->Class[0] < B->Class[0];
452
39
                   });
453
39
454
39
  // Compare static contents and assign unique IDs for each static content.
455
39
  forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
456
39
457
39
  // Split groups by comparing relocations until convergence is obtained.
458
40
  do {
459
40
    Repeat = false;
460
40
    forEachClass(
461
40
        [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
462
40
  } while (Repeat);
463
39
464
39
  log("ICF needed " + Twine(Cnt) + " iterations");
465
39
466
39
  // Merge sections by the equivalence class.
467
39
  forEachClassRange(0, Sections.size(), [&](size_t Begin, size_t End) {
468
39
    if (End - Begin == 1)
469
39
      return;
470
39
    print("selected section " + toString(Sections[Begin]));
471
39
    for (size_t I = Begin + 1; I < End; ++I) {
472
39
      print("  removing identical section " + toString(Sections[I]));
473
39
      Sections[Begin]->replace(Sections[I]);
474
39
475
39
      // At this point we know sections merged are fully identical and hence
476
39
      // we want to remove duplicate implicit dependencies such as link order
477
39
      // and relocation sections.
478
39
      for (InputSection *IS : Sections[I]->DependentSections)
479
39
        IS->Live = false;
480
39
    }
481
39
  });
482
39
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::run()
483
484
// ICF entry point function.
485
42
template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
void lld::elf::doIcf<llvm::object::ELFType<(llvm::support::endianness)1, false> >()
Line
Count
Source
485
3
template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
Unexecuted instantiation: void lld::elf::doIcf<llvm::object::ELFType<(llvm::support::endianness)0, false> >()
void lld::elf::doIcf<llvm::object::ELFType<(llvm::support::endianness)1, true> >()
Line
Count
Source
485
39
template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
Unexecuted instantiation: void lld::elf::doIcf<llvm::object::ELFType<(llvm::support::endianness)0, true> >()
486
487
template void elf::doIcf<ELF32LE>();
488
template void elf::doIcf<ELF32BE>();
489
template void elf::doIcf<ELF64LE>();
490
template void elf::doIcf<ELF64BE>();