Coverage Report

Created: 2018-10-20 12:32

/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/StringExtras.h"
84
#include "llvm/BinaryFormat/ELF.h"
85
#include "llvm/Object/ELF.h"
86
#include "llvm/Support/xxhash.h"
87
#include <algorithm>
88
#include <atomic>
89
90
using namespace lld;
91
using namespace lld::elf;
92
using namespace llvm;
93
using namespace llvm::ELF;
94
using namespace llvm::object;
95
96
namespace {
97
template <class ELFT> class ICF {
98
public:
99
  void run();
100
101
private:
102
  void segregate(size_t Begin, size_t End, bool Constant);
103
104
  template <class RelTy>
105
  bool constantEq(const InputSection *A, ArrayRef<RelTy> RelsA,
106
                  const InputSection *B, ArrayRef<RelTy> RelsB);
107
108
  template <class RelTy>
109
  bool variableEq(const InputSection *A, ArrayRef<RelTy> RelsA,
110
                  const InputSection *B, ArrayRef<RelTy> RelsB);
111
112
  bool equalsConstant(const InputSection *A, const InputSection *B);
113
  bool equalsVariable(const InputSection *A, const InputSection *B);
114
115
  size_t findBoundary(size_t Begin, size_t End);
116
117
  void forEachClassRange(size_t Begin, size_t End,
118
                         llvm::function_ref<void(size_t, size_t)> Fn);
119
120
  void forEachClass(llvm::function_ref<void(size_t, size_t)> Fn);
121
122
  std::vector<InputSection *> Sections;
123
124
  // We repeat the main loop while `Repeat` is true.
125
  std::atomic<bool> Repeat;
126
127
  // The main loop counter.
128
  int Cnt = 0;
129
130
  // We have two locations for equivalence classes. On the first iteration
131
  // of the main loop, Class[0] has a valid value, and Class[1] contains
132
  // garbage. We read equivalence classes from slot 0 and write to slot 1.
133
  // So, Class[0] represents the current class, and Class[1] represents
134
  // the next class. On each iteration, we switch their roles and use them
135
  // alternately.
136
  //
137
  // Why are we doing this? Recall that other threads may be working on
138
  // other equivalence classes in parallel. They may read sections that we
139
  // are updating. We cannot update equivalence classes in place because
140
  // it breaks the invariance that all possibly-identical sections must be
141
  // in the same equivalence class at any moment. In other words, the for
142
  // loop to update equivalence classes is not atomic, and that is
143
  // observable from other threads. By writing new classes to other
144
  // places, we can keep the invariance.
145
  //
146
  // Below, `Current` has the index of the current class, and `Next` has
147
  // the index of the next class. If threading is enabled, they are either
148
  // (0, 1) or (1, 0).
149
  //
150
  // Note on single-thread: if that's the case, they are always (0, 0)
151
  // because we can safely read the next class without worrying about race
152
  // conditions. Using the same location makes this algorithm converge
153
  // faster because it uses results of the same iteration earlier.
154
  int Current = 0;
155
  int Next = 0;
156
};
157
}
158
159
// Returns true if section S is subject of ICF.
160
2.47k
static bool isEligible(InputSection *S) {
161
2.47k
  if (!S->Live || 
S->KeepUnique2.46k
||
!(S->Flags & SHF_ALLOC)2.39k
)
162
151
    return false;
163
2.31k
164
2.31k
  // Don't merge writable sections. .data.rel.ro sections are marked as writable
165
2.31k
  // but are semantically read-only.
166
2.31k
  if ((S->Flags & SHF_WRITE) && 
S->Name != ".data.rel.ro"3
&&
167
2.31k
      
!S->Name.startswith(".data.rel.ro.")2
)
168
1
    return false;
169
2.31k
170
2.31k
  // SHF_LINK_ORDER sections are ICF'd as a unit with their dependent sections,
171
2.31k
  // so we don't consider them for ICF individually.
172
2.31k
  if (S->Flags & SHF_LINK_ORDER)
173
4
    return false;
174
2.31k
175
2.31k
  // Don't merge synthetic sections as their Data member is not valid and empty.
176
2.31k
  // The Data member needs to be valid for ICF as it is used by ICF to determine
177
2.31k
  // the equality of section contents.
178
2.31k
  if (isa<SyntheticSection>(S))
179
9
    return false;
180
2.30k
181
2.30k
  // .init and .fini contains instructions that must be executed to initialize
182
2.30k
  // and finalize the process. They cannot and should not be merged.
183
2.30k
  if (S->Name == ".init" || 
S->Name == ".fini"2.30k
)
184
2
    return false;
185
2.30k
186
2.30k
  // A user program may enumerate sections named with a C identifier using
187
2.30k
  // __start_* and __stop_* symbols. We cannot ICF any such sections because
188
2.30k
  // that could change program semantics.
189
2.30k
  if (isValidCIdentifier(S->Name))
190
2
    return false;
191
2.30k
192
2.30k
  return true;
193
2.30k
}
194
195
// Split an equivalence class into smaller classes.
196
template <class ELFT>
197
2.37k
void ICF<ELFT>::segregate(size_t Begin, size_t End, bool Constant) {
198
2.37k
  // This loop rearranges sections in [Begin, End) so that all sections
199
2.37k
  // that are equal in terms of equals{Constant,Variable} are contiguous
200
2.37k
  // in [Begin, End).
201
2.37k
  //
202
2.37k
  // The algorithm is quadratic in the worst case, but that is not an
203
2.37k
  // issue in practice because the number of the distinct sections in
204
2.37k
  // each range is usually very small.
205
2.37k
206
6.81k
  while (Begin < End) {
207
4.43k
    // Divide [Begin, End) into two. Let Mid be the start index of the
208
4.43k
    // second group.
209
4.43k
    auto Bound =
210
4.43k
        std::stable_partition(Sections.begin() + Begin + 1,
211
2.09M
                              Sections.begin() + End, [&](InputSection *S) {
212
2.09M
                                if (Constant)
213
2.09M
                                  return equalsConstant(Sections[Begin], S);
214
84
                                return equalsVariable(Sections[Begin], S);
215
84
                              });
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
211
6
                              Sections.begin() + End, [&](InputSection *S) {
212
6
                                if (Constant)
213
3
                                  return equalsConstant(Sections[Begin], S);
214
3
                                return equalsVariable(Sections[Begin], S);
215
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
211
2.09M
                              Sections.begin() + End, [&](InputSection *S) {
212
2.09M
                                if (Constant)
213
2.09M
                                  return equalsConstant(Sections[Begin], S);
214
81
                                return equalsVariable(Sections[Begin], S);
215
81
                              });
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
216
4.43k
    size_t Mid = Bound - Sections.begin();
217
4.43k
218
4.43k
    // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
219
4.43k
    // updating the sections in [Begin, Mid). We use Mid as an equivalence
220
4.43k
    // class ID because every group ends with a unique index.
221
9.04k
    for (size_t I = Begin; I < Mid; 
++I4.60k
)
222
4.60k
      Sections[I]->Class[Next] = Mid;
223
4.43k
224
4.43k
    // If we created a group, we need to iterate the main loop again.
225
4.43k
    if (Mid != End)
226
2.06k
      Repeat = true;
227
4.43k
228
4.43k
    Begin = Mid;
229
4.43k
  }
230
2.37k
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::segregate(unsigned long, unsigned long, bool)
Line
Count
Source
197
20
void ICF<ELFT>::segregate(size_t Begin, size_t End, bool Constant) {
198
20
  // This loop rearranges sections in [Begin, End) so that all sections
199
20
  // that are equal in terms of equals{Constant,Variable} are contiguous
200
20
  // in [Begin, End).
201
20
  //
202
20
  // The algorithm is quadratic in the worst case, but that is not an
203
20
  // issue in practice because the number of the distinct sections in
204
20
  // each range is usually very small.
205
20
206
40
  while (Begin < End) {
207
20
    // Divide [Begin, End) into two. Let Mid be the start index of the
208
20
    // second group.
209
20
    auto Bound =
210
20
        std::stable_partition(Sections.begin() + Begin + 1,
211
20
                              Sections.begin() + End, [&](InputSection *S) {
212
20
                                if (Constant)
213
20
                                  return equalsConstant(Sections[Begin], S);
214
20
                                return equalsVariable(Sections[Begin], S);
215
20
                              });
216
20
    size_t Mid = Bound - Sections.begin();
217
20
218
20
    // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
219
20
    // updating the sections in [Begin, Mid). We use Mid as an equivalence
220
20
    // class ID because every group ends with a unique index.
221
46
    for (size_t I = Begin; I < Mid; 
++I26
)
222
26
      Sections[I]->Class[Next] = Mid;
223
20
224
20
    // If we created a group, we need to iterate the main loop again.
225
20
    if (Mid != End)
226
0
      Repeat = true;
227
20
228
20
    Begin = Mid;
229
20
  }
230
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
197
2.35k
void ICF<ELFT>::segregate(size_t Begin, size_t End, bool Constant) {
198
2.35k
  // This loop rearranges sections in [Begin, End) so that all sections
199
2.35k
  // that are equal in terms of equals{Constant,Variable} are contiguous
200
2.35k
  // in [Begin, End).
201
2.35k
  //
202
2.35k
  // The algorithm is quadratic in the worst case, but that is not an
203
2.35k
  // issue in practice because the number of the distinct sections in
204
2.35k
  // each range is usually very small.
205
2.35k
206
6.77k
  while (Begin < End) {
207
4.41k
    // Divide [Begin, End) into two. Let Mid be the start index of the
208
4.41k
    // second group.
209
4.41k
    auto Bound =
210
4.41k
        std::stable_partition(Sections.begin() + Begin + 1,
211
4.41k
                              Sections.begin() + End, [&](InputSection *S) {
212
4.41k
                                if (Constant)
213
4.41k
                                  return equalsConstant(Sections[Begin], S);
214
4.41k
                                return equalsVariable(Sections[Begin], S);
215
4.41k
                              });
216
4.41k
    size_t Mid = Bound - Sections.begin();
217
4.41k
218
4.41k
    // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
219
4.41k
    // updating the sections in [Begin, Mid). We use Mid as an equivalence
220
4.41k
    // class ID because every group ends with a unique index.
221
8.99k
    for (size_t I = Begin; I < Mid; 
++I4.58k
)
222
4.58k
      Sections[I]->Class[Next] = Mid;
223
4.41k
224
4.41k
    // If we created a group, we need to iterate the main loop again.
225
4.41k
    if (Mid != End)
226
2.06k
      Repeat = true;
227
4.41k
228
4.41k
    Begin = Mid;
229
4.41k
  }
230
2.35k
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::segregate(unsigned long, unsigned long, bool)
231
232
// Compare two lists of relocations.
233
template <class ELFT>
234
template <class RelTy>
235
bool ICF<ELFT>::constantEq(const InputSection *SecA, ArrayRef<RelTy> RA,
236
96
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
237
111
  for (size_t I = 0; I < RA.size(); 
++I15
) {
238
27
    if (RA[I].r_offset != RB[I].r_offset ||
239
27
        
RA[I].getType(Config->IsMips64EL) != RB[I].getType(Config->IsMips64EL)26
)
240
2
      return false;
241
25
242
25
    uint64_t AddA = getAddend<ELFT>(RA[I]);
243
25
    uint64_t AddB = getAddend<ELFT>(RB[I]);
244
25
245
25
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
246
25
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
247
25
    if (&SA == &SB) {
248
9
      if (AddA == AddB)
249
8
        continue;
250
1
      return false;
251
1
    }
252
16
253
16
    auto *DA = dyn_cast<Defined>(&SA);
254
16
    auto *DB = dyn_cast<Defined>(&SB);
255
16
256
16
    // Placeholder symbols generated by linker scripts look the same now but
257
16
    // may have different values later.
258
16
    if (!DA || !DB || 
DA->ScriptDefined15
||
DB->ScriptDefined14
)
259
2
      return false;
260
14
261
14
    // Relocations referring to absolute symbols are constant-equal if their
262
14
    // values are equal.
263
14
    if (!DA->Section && 
!DB->Section2
&&
DA->Value + AddA == DB->Value + AddB2
)
264
1
      continue;
265
13
    if (!DA->Section || 
!DB->Section12
)
266
1
      return false;
267
12
268
12
    if (DA->Section->kind() != DB->Section->kind())
269
1
      return false;
270
11
271
11
    // Relocations referring to InputSections are constant-equal if their
272
11
    // section offsets are equal.
273
11
    if (isa<InputSection>(DA->Section)) {
274
5
      if (DA->Value + AddA == DB->Value + AddB)
275
4
        continue;
276
1
      return false;
277
1
    }
278
6
279
6
    // Relocations referring to MergeInputSections are constant-equal if their
280
6
    // offsets in the output section are equal.
281
6
    auto *X = dyn_cast<MergeInputSection>(DA->Section);
282
6
    if (!X)
283
1
      return false;
284
5
    auto *Y = cast<MergeInputSection>(DB->Section);
285
5
    if (X->getParent() != Y->getParent())
286
1
      return false;
287
4
288
4
    uint64_t OffsetA =
289
4
        SA.isSection() ? 
X->getOffset(AddA)1
:
X->getOffset(DA->Value) + AddA3
;
290
4
    uint64_t OffsetB =
291
4
        SB.isSection() ? 
Y->getOffset(AddB)1
:
Y->getOffset(DB->Value) + AddB3
;
292
4
    if (OffsetA != OffsetB)
293
2
      return false;
294
4
  }
295
96
296
96
  
return true84
;
297
96
}
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
236
3
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
237
4
  for (size_t I = 0; I < RA.size(); 
++I1
) {
238
1
    if (RA[I].r_offset != RB[I].r_offset ||
239
1
        RA[I].getType(Config->IsMips64EL) != RB[I].getType(Config->IsMips64EL))
240
0
      return false;
241
1
242
1
    uint64_t AddA = getAddend<ELFT>(RA[I]);
243
1
    uint64_t AddB = getAddend<ELFT>(RB[I]);
244
1
245
1
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
246
1
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
247
1
    if (&SA == &SB) {
248
1
      if (AddA == AddB)
249
1
        continue;
250
0
      return false;
251
0
    }
252
0
253
0
    auto *DA = dyn_cast<Defined>(&SA);
254
0
    auto *DB = dyn_cast<Defined>(&SB);
255
0
256
0
    // Placeholder symbols generated by linker scripts look the same now but
257
0
    // may have different values later.
258
0
    if (!DA || !DB || DA->ScriptDefined || DB->ScriptDefined)
259
0
      return false;
260
0
261
0
    // Relocations referring to absolute symbols are constant-equal if their
262
0
    // values are equal.
263
0
    if (!DA->Section && !DB->Section && DA->Value + AddA == DB->Value + AddB)
264
0
      continue;
265
0
    if (!DA->Section || !DB->Section)
266
0
      return false;
267
0
268
0
    if (DA->Section->kind() != DB->Section->kind())
269
0
      return false;
270
0
271
0
    // Relocations referring to InputSections are constant-equal if their
272
0
    // section offsets are equal.
273
0
    if (isa<InputSection>(DA->Section)) {
274
0
      if (DA->Value + AddA == DB->Value + AddB)
275
0
        continue;
276
0
      return false;
277
0
    }
278
0
279
0
    // Relocations referring to MergeInputSections are constant-equal if their
280
0
    // offsets in the output section are equal.
281
0
    auto *X = dyn_cast<MergeInputSection>(DA->Section);
282
0
    if (!X)
283
0
      return false;
284
0
    auto *Y = cast<MergeInputSection>(DB->Section);
285
0
    if (X->getParent() != Y->getParent())
286
0
      return false;
287
0
288
0
    uint64_t OffsetA =
289
0
        SA.isSection() ? X->getOffset(AddA) : X->getOffset(DA->Value) + AddA;
290
0
    uint64_t OffsetB =
291
0
        SB.isSection() ? Y->getOffset(AddB) : Y->getOffset(DB->Value) + AddB;
292
0
    if (OffsetA != OffsetB)
293
0
      return false;
294
0
  }
295
3
296
3
  return true;
297
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
236
25
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
237
39
  for (size_t I = 0; I < RA.size(); 
++I14
) {
238
26
    if (RA[I].r_offset != RB[I].r_offset ||
239
26
        
RA[I].getType(Config->IsMips64EL) != RB[I].getType(Config->IsMips64EL)25
)
240
2
      return false;
241
24
242
24
    uint64_t AddA = getAddend<ELFT>(RA[I]);
243
24
    uint64_t AddB = getAddend<ELFT>(RB[I]);
244
24
245
24
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
246
24
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
247
24
    if (&SA == &SB) {
248
8
      if (AddA == AddB)
249
7
        continue;
250
1
      return false;
251
1
    }
252
16
253
16
    auto *DA = dyn_cast<Defined>(&SA);
254
16
    auto *DB = dyn_cast<Defined>(&SB);
255
16
256
16
    // Placeholder symbols generated by linker scripts look the same now but
257
16
    // may have different values later.
258
16
    if (!DA || !DB || 
DA->ScriptDefined15
||
DB->ScriptDefined14
)
259
2
      return false;
260
14
261
14
    // Relocations referring to absolute symbols are constant-equal if their
262
14
    // values are equal.
263
14
    if (!DA->Section && 
!DB->Section2
&&
DA->Value + AddA == DB->Value + AddB2
)
264
1
      continue;
265
13
    if (!DA->Section || 
!DB->Section12
)
266
1
      return false;
267
12
268
12
    if (DA->Section->kind() != DB->Section->kind())
269
1
      return false;
270
11
271
11
    // Relocations referring to InputSections are constant-equal if their
272
11
    // section offsets are equal.
273
11
    if (isa<InputSection>(DA->Section)) {
274
5
      if (DA->Value + AddA == DB->Value + AddB)
275
4
        continue;
276
1
      return false;
277
1
    }
278
6
279
6
    // Relocations referring to MergeInputSections are constant-equal if their
280
6
    // offsets in the output section are equal.
281
6
    auto *X = dyn_cast<MergeInputSection>(DA->Section);
282
6
    if (!X)
283
1
      return false;
284
5
    auto *Y = cast<MergeInputSection>(DB->Section);
285
5
    if (X->getParent() != Y->getParent())
286
1
      return false;
287
4
288
4
    uint64_t OffsetA =
289
4
        SA.isSection() ? 
X->getOffset(AddA)1
:
X->getOffset(DA->Value) + AddA3
;
290
4
    uint64_t OffsetB =
291
4
        SB.isSection() ? 
Y->getOffset(AddB)1
:
Y->getOffset(DB->Value) + AddB3
;
292
4
    if (OffsetA != OffsetB)
293
2
      return false;
294
4
  }
295
25
296
25
  
return true13
;
297
25
}
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
236
68
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
237
68
  for (size_t I = 0; I < RA.size(); 
++I0
) {
238
0
    if (RA[I].r_offset != RB[I].r_offset ||
239
0
        RA[I].getType(Config->IsMips64EL) != RB[I].getType(Config->IsMips64EL))
240
0
      return false;
241
0
242
0
    uint64_t AddA = getAddend<ELFT>(RA[I]);
243
0
    uint64_t AddB = getAddend<ELFT>(RB[I]);
244
0
245
0
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
246
0
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
247
0
    if (&SA == &SB) {
248
0
      if (AddA == AddB)
249
0
        continue;
250
0
      return false;
251
0
    }
252
0
253
0
    auto *DA = dyn_cast<Defined>(&SA);
254
0
    auto *DB = dyn_cast<Defined>(&SB);
255
0
256
0
    // Placeholder symbols generated by linker scripts look the same now but
257
0
    // may have different values later.
258
0
    if (!DA || !DB || DA->ScriptDefined || DB->ScriptDefined)
259
0
      return false;
260
0
261
0
    // Relocations referring to absolute symbols are constant-equal if their
262
0
    // values are equal.
263
0
    if (!DA->Section && !DB->Section && DA->Value + AddA == DB->Value + AddB)
264
0
      continue;
265
0
    if (!DA->Section || !DB->Section)
266
0
      return false;
267
0
268
0
    if (DA->Section->kind() != DB->Section->kind())
269
0
      return false;
270
0
271
0
    // Relocations referring to InputSections are constant-equal if their
272
0
    // section offsets are equal.
273
0
    if (isa<InputSection>(DA->Section)) {
274
0
      if (DA->Value + AddA == DB->Value + AddB)
275
0
        continue;
276
0
      return false;
277
0
    }
278
0
279
0
    // Relocations referring to MergeInputSections are constant-equal if their
280
0
    // offsets in the output section are equal.
281
0
    auto *X = dyn_cast<MergeInputSection>(DA->Section);
282
0
    if (!X)
283
0
      return false;
284
0
    auto *Y = cast<MergeInputSection>(DB->Section);
285
0
    if (X->getParent() != Y->getParent())
286
0
      return false;
287
0
288
0
    uint64_t OffsetA =
289
0
        SA.isSection() ? X->getOffset(AddA) : X->getOffset(DA->Value) + AddA;
290
0
    uint64_t OffsetB =
291
0
        SB.isSection() ? Y->getOffset(AddB) : Y->getOffset(DB->Value) + AddB;
292
0
    if (OffsetA != OffsetB)
293
0
      return false;
294
0
  }
295
68
296
68
  return true;
297
68
}
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> >)
298
299
// Compare "non-moving" part of two InputSections, namely everything
300
// except relocation targets.
301
template <class ELFT>
302
2.09M
bool ICF<ELFT>::equalsConstant(const InputSection *A, const InputSection *B) {
303
2.09M
  if (A->NumRelocations != B->NumRelocations || A->Flags != B->Flags ||
304
2.09M
      
A->getSize() != B->getSize()2.09M
||
A->data() != B->data()2.09M
)
305
1
    return false;
306
2.09M
307
2.09M
  // If two sections have different output sections, we cannot merge them.
308
2.09M
  // FIXME: This doesn't do the right thing in the case where there is a linker
309
2.09M
  // script. We probably need to move output section assignment before ICF to
310
2.09M
  // get the correct behaviour here.
311
2.09M
  if (getOutputSectionName(A) != getOutputSectionName(B))
312
2.09M
    return false;
313
96
314
96
  if (A->AreRelocsRela)
315
25
    return constantEq(A, A->template relas<ELFT>(), B,
316
25
                      B->template relas<ELFT>());
317
71
  return constantEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
318
71
}
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
302
3
bool ICF<ELFT>::equalsConstant(const InputSection *A, const InputSection *B) {
303
3
  if (A->NumRelocations != B->NumRelocations || A->Flags != B->Flags ||
304
3
      A->getSize() != B->getSize() || A->data() != B->data())
305
0
    return false;
306
3
307
3
  // If two sections have different output sections, we cannot merge them.
308
3
  // FIXME: This doesn't do the right thing in the case where there is a linker
309
3
  // script. We probably need to move output section assignment before ICF to
310
3
  // get the correct behaviour here.
311
3
  if (getOutputSectionName(A) != getOutputSectionName(B))
312
0
    return false;
313
3
314
3
  if (A->AreRelocsRela)
315
0
    return constantEq(A, A->template relas<ELFT>(), B,
316
0
                      B->template relas<ELFT>());
317
3
  return constantEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
318
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
302
2.09M
bool ICF<ELFT>::equalsConstant(const InputSection *A, const InputSection *B) {
303
2.09M
  if (A->NumRelocations != B->NumRelocations || A->Flags != B->Flags ||
304
2.09M
      
A->getSize() != B->getSize()2.09M
||
A->data() != B->data()2.09M
)
305
1
    return false;
306
2.09M
307
2.09M
  // If two sections have different output sections, we cannot merge them.
308
2.09M
  // FIXME: This doesn't do the right thing in the case where there is a linker
309
2.09M
  // script. We probably need to move output section assignment before ICF to
310
2.09M
  // get the correct behaviour here.
311
2.09M
  if (getOutputSectionName(A) != getOutputSectionName(B))
312
2.09M
    return false;
313
93
314
93
  if (A->AreRelocsRela)
315
25
    return constantEq(A, A->template relas<ELFT>(), B,
316
25
                      B->template relas<ELFT>());
317
68
  return constantEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
318
68
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::equalsConstant(lld::elf::InputSection const*, lld::elf::InputSection const*)
319
320
// Compare two lists of relocations. Returns true if all pairs of
321
// relocations point to the same section in terms of ICF.
322
template <class ELFT>
323
template <class RelTy>
324
bool ICF<ELFT>::variableEq(const InputSection *SecA, ArrayRef<RelTy> RA,
325
84
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
326
84
  assert(RA.size() == RB.size());
327
84
328
98
  for (size_t I = 0; I < RA.size(); 
++I14
) {
329
15
    // The two sections must be identical.
330
15
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
331
15
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
332
15
    if (&SA == &SB)
333
8
      continue;
334
7
335
7
    auto *DA = cast<Defined>(&SA);
336
7
    auto *DB = cast<Defined>(&SB);
337
7
338
7
    // We already dealt with absolute and non-InputSection symbols in
339
7
    // constantEq, and for InputSections we have already checked everything
340
7
    // except the equivalence class.
341
7
    if (!DA->Section)
342
1
      continue;
343
6
    auto *X = dyn_cast<InputSection>(DA->Section);
344
6
    if (!X)
345
2
      continue;
346
4
    auto *Y = cast<InputSection>(DB->Section);
347
4
348
4
    // Ineligible sections are in the special equivalence class 0.
349
4
    // They can never be the same in terms of the equivalence class.
350
4
    if (X->Class[Current] == 0)
351
1
      return false;
352
3
    if (X->Class[Current] != Y->Class[Current])
353
0
      return false;
354
83
  };
355
83
356
83
  return true;
357
84
}
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
325
3
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
326
3
  assert(RA.size() == RB.size());
327
3
328
4
  for (size_t I = 0; I < RA.size(); 
++I1
) {
329
1
    // The two sections must be identical.
330
1
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
331
1
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
332
1
    if (&SA == &SB)
333
1
      continue;
334
0
335
0
    auto *DA = cast<Defined>(&SA);
336
0
    auto *DB = cast<Defined>(&SB);
337
0
338
0
    // We already dealt with absolute and non-InputSection symbols in
339
0
    // constantEq, and for InputSections we have already checked everything
340
0
    // except the equivalence class.
341
0
    if (!DA->Section)
342
0
      continue;
343
0
    auto *X = dyn_cast<InputSection>(DA->Section);
344
0
    if (!X)
345
0
      continue;
346
0
    auto *Y = cast<InputSection>(DB->Section);
347
0
348
0
    // Ineligible sections are in the special equivalence class 0.
349
0
    // They can never be the same in terms of the equivalence class.
350
0
    if (X->Class[Current] == 0)
351
0
      return false;
352
0
    if (X->Class[Current] != Y->Class[Current])
353
0
      return false;
354
3
  };
355
3
356
3
  return true;
357
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
325
13
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
326
13
  assert(RA.size() == RB.size());
327
13
328
26
  for (size_t I = 0; I < RA.size(); 
++I13
) {
329
14
    // The two sections must be identical.
330
14
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
331
14
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
332
14
    if (&SA == &SB)
333
7
      continue;
334
7
335
7
    auto *DA = cast<Defined>(&SA);
336
7
    auto *DB = cast<Defined>(&SB);
337
7
338
7
    // We already dealt with absolute and non-InputSection symbols in
339
7
    // constantEq, and for InputSections we have already checked everything
340
7
    // except the equivalence class.
341
7
    if (!DA->Section)
342
1
      continue;
343
6
    auto *X = dyn_cast<InputSection>(DA->Section);
344
6
    if (!X)
345
2
      continue;
346
4
    auto *Y = cast<InputSection>(DB->Section);
347
4
348
4
    // Ineligible sections are in the special equivalence class 0.
349
4
    // They can never be the same in terms of the equivalence class.
350
4
    if (X->Class[Current] == 0)
351
1
      return false;
352
3
    if (X->Class[Current] != Y->Class[Current])
353
0
      return false;
354
12
  };
355
12
356
12
  return true;
357
13
}
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
325
68
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
326
68
  assert(RA.size() == RB.size());
327
68
328
68
  for (size_t I = 0; I < RA.size(); 
++I0
) {
329
0
    // The two sections must be identical.
330
0
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
331
0
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
332
0
    if (&SA == &SB)
333
0
      continue;
334
0
335
0
    auto *DA = cast<Defined>(&SA);
336
0
    auto *DB = cast<Defined>(&SB);
337
0
338
0
    // We already dealt with absolute and non-InputSection symbols in
339
0
    // constantEq, and for InputSections we have already checked everything
340
0
    // except the equivalence class.
341
0
    if (!DA->Section)
342
0
      continue;
343
0
    auto *X = dyn_cast<InputSection>(DA->Section);
344
0
    if (!X)
345
0
      continue;
346
0
    auto *Y = cast<InputSection>(DB->Section);
347
0
348
0
    // Ineligible sections are in the special equivalence class 0.
349
0
    // They can never be the same in terms of the equivalence class.
350
0
    if (X->Class[Current] == 0)
351
0
      return false;
352
0
    if (X->Class[Current] != Y->Class[Current])
353
0
      return false;
354
68
  };
355
68
356
68
  return true;
357
68
}
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> >)
358
359
// Compare "moving" part of two InputSections, namely relocation targets.
360
template <class ELFT>
361
84
bool ICF<ELFT>::equalsVariable(const InputSection *A, const InputSection *B) {
362
84
  if (A->AreRelocsRela)
363
13
    return variableEq(A, A->template relas<ELFT>(), B,
364
13
                      B->template relas<ELFT>());
365
71
  return variableEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
366
71
}
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
361
3
bool ICF<ELFT>::equalsVariable(const InputSection *A, const InputSection *B) {
362
3
  if (A->AreRelocsRela)
363
0
    return variableEq(A, A->template relas<ELFT>(), B,
364
0
                      B->template relas<ELFT>());
365
3
  return variableEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
366
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
361
81
bool ICF<ELFT>::equalsVariable(const InputSection *A, const InputSection *B) {
362
81
  if (A->AreRelocsRela)
363
13
    return variableEq(A, A->template relas<ELFT>(), B,
364
13
                      B->template relas<ELFT>());
365
68
  return variableEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
366
68
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::equalsVariable(lld::elf::InputSection const*, lld::elf::InputSection const*)
367
368
5.10k
template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t Begin, size_t End) {
369
5.10k
  uint32_t Class = Sections[Begin]->Class[Current];
370
247k
  for (size_t I = Begin + 1; I < End; 
++I242k
)
371
247k
    if (Class != Sections[I]->Class[Current])
372
4.40k
      return I;
373
5.10k
  
return End697
;
374
5.10k
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::findBoundary(unsigned long, unsigned long)
Line
Count
Source
368
30
template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t Begin, size_t End) {
369
30
  uint32_t Class = Sections[Begin]->Class[Current];
370
39
  for (size_t I = Begin + 1; I < End; 
++I9
)
371
30
    if (Class != Sections[I]->Class[Current])
372
21
      return I;
373
30
  
return End9
;
374
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
368
5.07k
template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t Begin, size_t End) {
369
5.07k
  uint32_t Class = Sections[Begin]->Class[Current];
370
247k
  for (size_t I = Begin + 1; I < End; 
++I242k
)
371
247k
    if (Class != Sections[I]->Class[Current])
372
4.38k
      return I;
373
5.07k
  
return End688
;
374
5.07k
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::findBoundary(unsigned long, unsigned long)
375
376
// Sections in the same equivalence class are contiguous in Sections
377
// vector. Therefore, Sections vector can be considered as contiguous
378
// groups of sections, grouped by the class.
379
//
380
// This function calls Fn on every group within [Begin, End).
381
template <class ELFT>
382
void ICF<ELFT>::forEachClassRange(size_t Begin, size_t End,
383
442
                                  llvm::function_ref<void(size_t, size_t)> Fn) {
384
5.03k
  while (Begin < End) {
385
4.59k
    size_t Mid = findBoundary(Begin, End);
386
4.59k
    Fn(Begin, Mid);
387
4.59k
    Begin = Mid;
388
4.59k
  }
389
442
}
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
383
9
                                  llvm::function_ref<void(size_t, size_t)> Fn) {
384
39
  while (Begin < End) {
385
30
    size_t Mid = findBoundary(Begin, End);
386
30
    Fn(Begin, Mid);
387
30
    Begin = Mid;
388
30
  }
389
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
383
433
                                  llvm::function_ref<void(size_t, size_t)> Fn) {
384
4.99k
  while (Begin < End) {
385
4.56k
    size_t Mid = findBoundary(Begin, End);
386
4.56k
    Fn(Begin, Mid);
387
4.56k
    Begin = Mid;
388
4.56k
  }
389
433
}
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)>)
390
391
// Call Fn on each equivalence class.
392
template <class ELFT>
393
125
void ICF<ELFT>::forEachClass(llvm::function_ref<void(size_t, size_t)> Fn) {
394
125
  // If threading is disabled or the number of sections are
395
125
  // too small to use threading, call Fn sequentially.
396
125
  if (!ThreadsEnabled || Sections.size() < 1024) {
397
123
    forEachClassRange(0, Sections.size(), Fn);
398
123
    ++Cnt;
399
123
    return;
400
123
  }
401
2
402
2
  Current = Cnt % 2;
403
2
  Next = (Cnt + 1) % 2;
404
2
405
2
  // Shard into non-overlapping intervals, and call Fn in parallel.
406
2
  // The sharding must be completed before any calls to Fn are made
407
2
  // so that Fn can modify the Chunks in its shard without causing data
408
2
  // races.
409
2
  const size_t NumShards = 256;
410
2
  size_t Step = Sections.size() / NumShards;
411
2
  size_t Boundaries[NumShards + 1];
412
2
  Boundaries[0] = 0;
413
2
  Boundaries[NumShards] = Sections.size();
414
2
415
510
  parallelForEachN(1, NumShards, [&](size_t I) {
416
510
    Boundaries[I] = findBoundary((I - 1) * Step, Sections.size());
417
510
  });
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
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
Line
Count
Source
415
510
  parallelForEachN(1, NumShards, [&](size_t I) {
416
510
    Boundaries[I] = findBoundary((I - 1) * Step, Sections.size());
417
510
  });
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
418
2
419
512
  parallelForEachN(1, NumShards + 1, [&](size_t I) {
420
512
    if (Boundaries[I - 1] < Boundaries[I])
421
257
      forEachClassRange(Boundaries[I - 1], Boundaries[I], Fn);
422
512
  });
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
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
Line
Count
Source
419
512
  parallelForEachN(1, NumShards + 1, [&](size_t I) {
420
512
    if (Boundaries[I - 1] < Boundaries[I])
421
257
      forEachClassRange(Boundaries[I - 1], Boundaries[I], Fn);
422
512
  });
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
423
2
  ++Cnt;
424
2
}
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
393
6
void ICF<ELFT>::forEachClass(llvm::function_ref<void(size_t, size_t)> Fn) {
394
6
  // If threading is disabled or the number of sections are
395
6
  // too small to use threading, call Fn sequentially.
396
6
  if (!ThreadsEnabled || Sections.size() < 1024) {
397
6
    forEachClassRange(0, Sections.size(), Fn);
398
6
    ++Cnt;
399
6
    return;
400
6
  }
401
0
402
0
  Current = Cnt % 2;
403
0
  Next = (Cnt + 1) % 2;
404
0
405
0
  // Shard into non-overlapping intervals, and call Fn in parallel.
406
0
  // The sharding must be completed before any calls to Fn are made
407
0
  // so that Fn can modify the Chunks in its shard without causing data
408
0
  // races.
409
0
  const size_t NumShards = 256;
410
0
  size_t Step = Sections.size() / NumShards;
411
0
  size_t Boundaries[NumShards + 1];
412
0
  Boundaries[0] = 0;
413
0
  Boundaries[NumShards] = Sections.size();
414
0
415
0
  parallelForEachN(1, NumShards, [&](size_t I) {
416
0
    Boundaries[I] = findBoundary((I - 1) * Step, Sections.size());
417
0
  });
418
0
419
0
  parallelForEachN(1, NumShards + 1, [&](size_t I) {
420
0
    if (Boundaries[I - 1] < Boundaries[I])
421
0
      forEachClassRange(Boundaries[I - 1], Boundaries[I], Fn);
422
0
  });
423
0
  ++Cnt;
424
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
393
119
void ICF<ELFT>::forEachClass(llvm::function_ref<void(size_t, size_t)> Fn) {
394
119
  // If threading is disabled or the number of sections are
395
119
  // too small to use threading, call Fn sequentially.
396
119
  if (!ThreadsEnabled || Sections.size() < 1024) {
397
117
    forEachClassRange(0, Sections.size(), Fn);
398
117
    ++Cnt;
399
117
    return;
400
117
  }
401
2
402
2
  Current = Cnt % 2;
403
2
  Next = (Cnt + 1) % 2;
404
2
405
2
  // Shard into non-overlapping intervals, and call Fn in parallel.
406
2
  // The sharding must be completed before any calls to Fn are made
407
2
  // so that Fn can modify the Chunks in its shard without causing data
408
2
  // races.
409
2
  const size_t NumShards = 256;
410
2
  size_t Step = Sections.size() / NumShards;
411
2
  size_t Boundaries[NumShards + 1];
412
2
  Boundaries[0] = 0;
413
2
  Boundaries[NumShards] = Sections.size();
414
2
415
2
  parallelForEachN(1, NumShards, [&](size_t I) {
416
2
    Boundaries[I] = findBoundary((I - 1) * Step, Sections.size());
417
2
  });
418
2
419
2
  parallelForEachN(1, NumShards + 1, [&](size_t I) {
420
2
    if (Boundaries[I - 1] < Boundaries[I])
421
2
      forEachClassRange(Boundaries[I - 1], Boundaries[I], Fn);
422
2
  });
423
2
  ++Cnt;
424
2
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::forEachClass(llvm::function_ref<void (unsigned long, unsigned long)>)
425
426
145
static void print(const Twine &S) {
427
145
  if (Config->PrintIcfSections)
428
98
    message(S);
429
145
}
430
431
// The main function of ICF.
432
62
template <class ELFT> void ICF<ELFT>::run() {
433
62
  // Collect sections to merge.
434
62
  for (InputSectionBase *Sec : InputSections)
435
2.47k
    if (auto *S = dyn_cast<InputSection>(Sec))
436
2.47k
      if (isEligible(S))
437
2.30k
        Sections.push_back(S);
438
62
439
62
  // Initially, we use hash values to partition sections.
440
2.30k
  parallelForEach(Sections, [&](InputSection *S) {
441
2.30k
    // Set MSB to 1 to avoid collisions with non-hash IDs.
442
2.30k
    S->Class[0] = xxHash64(S->data()) | (1U << 31);
443
2.30k
  });
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
440
13
  parallelForEach(Sections, [&](InputSection *S) {
441
13
    // Set MSB to 1 to avoid collisions with non-hash IDs.
442
13
    S->Class[0] = xxHash64(S->data()) | (1U << 31);
443
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
440
2.28k
  parallelForEach(Sections, [&](InputSection *S) {
441
2.28k
    // Set MSB to 1 to avoid collisions with non-hash IDs.
442
2.28k
    S->Class[0] = xxHash64(S->data()) | (1U << 31);
443
2.28k
  });
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
444
62
445
62
  // From now on, sections in Sections vector are ordered so that sections
446
62
  // in the same equivalence class are consecutive in the vector.
447
62
  std::stable_sort(Sections.begin(), Sections.end(),
448
6.66k
                   [](InputSection *A, InputSection *B) {
449
6.66k
                     return A->Class[0] < B->Class[0];
450
6.66k
                   });
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
448
16
                   [](InputSection *A, InputSection *B) {
449
16
                     return A->Class[0] < B->Class[0];
450
16
                   });
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
448
6.64k
                   [](InputSection *A, InputSection *B) {
449
6.64k
                     return A->Class[0] < B->Class[0];
450
6.64k
                   });
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
451
62
452
62
  // Compare static contents and assign unique IDs for each static content.
453
154
  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
453
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
453
144
  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
454
62
455
62
  // Split groups by comparing relocations until convergence is obtained.
456
63
  do {
457
63
    Repeat = false;
458
63
    forEachClass(
459
2.22k
        [&](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
459
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
459
2.21k
        [&](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
460
63
  } while (Repeat);
461
62
462
62
  log("ICF needed " + Twine(Cnt) + " iterations");
463
62
464
62
  // Merge sections by the equivalence class.
465
2.21k
  forEachClassRange(0, Sections.size(), [&](size_t Begin, size_t End) {
466
2.21k
    if (End - Begin == 1)
467
2.15k
      return;
468
62
    print("selected section " + toString(Sections[Begin]));
469
145
    for (size_t I = Begin + 1; I < End; 
++I83
) {
470
83
      print("  removing identical section " + toString(Sections[I]));
471
83
      Sections[Begin]->replace(Sections[I]);
472
83
473
83
      // At this point we know sections merged are fully identical and hence
474
83
      // we want to remove duplicate implicit dependencies such as link order
475
83
      // and relocation sections.
476
83
      for (InputSection *IS : Sections[I]->DependentSections)
477
4
        IS->Live = false;
478
83
    }
479
62
  });
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
465
10
  forEachClassRange(0, Sections.size(), [&](size_t Begin, size_t End) {
466
10
    if (End - Begin == 1)
467
7
      return;
468
3
    print("selected section " + toString(Sections[Begin]));
469
6
    for (size_t I = Begin + 1; I < End; 
++I3
) {
470
3
      print("  removing identical section " + toString(Sections[I]));
471
3
      Sections[Begin]->replace(Sections[I]);
472
3
473
3
      // At this point we know sections merged are fully identical and hence
474
3
      // we want to remove duplicate implicit dependencies such as link order
475
3
      // and relocation sections.
476
3
      for (InputSection *IS : Sections[I]->DependentSections)
477
1
        IS->Live = false;
478
3
    }
479
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
465
2.20k
  forEachClassRange(0, Sections.size(), [&](size_t Begin, size_t End) {
466
2.20k
    if (End - Begin == 1)
467
2.14k
      return;
468
59
    print("selected section " + toString(Sections[Begin]));
469
139
    for (size_t I = Begin + 1; I < End; 
++I80
) {
470
80
      print("  removing identical section " + toString(Sections[I]));
471
80
      Sections[Begin]->replace(Sections[I]);
472
80
473
80
      // At this point we know sections merged are fully identical and hence
474
80
      // we want to remove duplicate implicit dependencies such as link order
475
80
      // and relocation sections.
476
80
      for (InputSection *IS : Sections[I]->DependentSections)
477
3
        IS->Live = false;
478
80
    }
479
59
  });
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
480
62
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::run()
Line
Count
Source
432
3
template <class ELFT> void ICF<ELFT>::run() {
433
3
  // Collect sections to merge.
434
3
  for (InputSectionBase *Sec : InputSections)
435
19
    if (auto *S = dyn_cast<InputSection>(Sec))
436
19
      if (isEligible(S))
437
13
        Sections.push_back(S);
438
3
439
3
  // Initially, we use hash values to partition sections.
440
3
  parallelForEach(Sections, [&](InputSection *S) {
441
3
    // Set MSB to 1 to avoid collisions with non-hash IDs.
442
3
    S->Class[0] = xxHash64(S->data()) | (1U << 31);
443
3
  });
444
3
445
3
  // From now on, sections in Sections vector are ordered so that sections
446
3
  // in the same equivalence class are consecutive in the vector.
447
3
  std::stable_sort(Sections.begin(), Sections.end(),
448
3
                   [](InputSection *A, InputSection *B) {
449
3
                     return A->Class[0] < B->Class[0];
450
3
                   });
451
3
452
3
  // Compare static contents and assign unique IDs for each static content.
453
3
  forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
454
3
455
3
  // Split groups by comparing relocations until convergence is obtained.
456
3
  do {
457
3
    Repeat = false;
458
3
    forEachClass(
459
3
        [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
460
3
  } while (Repeat);
461
3
462
3
  log("ICF needed " + Twine(Cnt) + " iterations");
463
3
464
3
  // Merge sections by the equivalence class.
465
3
  forEachClassRange(0, Sections.size(), [&](size_t Begin, size_t End) {
466
3
    if (End - Begin == 1)
467
3
      return;
468
3
    print("selected section " + toString(Sections[Begin]));
469
3
    for (size_t I = Begin + 1; I < End; ++I) {
470
3
      print("  removing identical section " + toString(Sections[I]));
471
3
      Sections[Begin]->replace(Sections[I]);
472
3
473
3
      // At this point we know sections merged are fully identical and hence
474
3
      // we want to remove duplicate implicit dependencies such as link order
475
3
      // and relocation sections.
476
3
      for (InputSection *IS : Sections[I]->DependentSections)
477
3
        IS->Live = false;
478
3
    }
479
3
  });
480
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
432
59
template <class ELFT> void ICF<ELFT>::run() {
433
59
  // Collect sections to merge.
434
59
  for (InputSectionBase *Sec : InputSections)
435
2.45k
    if (auto *S = dyn_cast<InputSection>(Sec))
436
2.45k
      if (isEligible(S))
437
2.28k
        Sections.push_back(S);
438
59
439
59
  // Initially, we use hash values to partition sections.
440
59
  parallelForEach(Sections, [&](InputSection *S) {
441
59
    // Set MSB to 1 to avoid collisions with non-hash IDs.
442
59
    S->Class[0] = xxHash64(S->data()) | (1U << 31);
443
59
  });
444
59
445
59
  // From now on, sections in Sections vector are ordered so that sections
446
59
  // in the same equivalence class are consecutive in the vector.
447
59
  std::stable_sort(Sections.begin(), Sections.end(),
448
59
                   [](InputSection *A, InputSection *B) {
449
59
                     return A->Class[0] < B->Class[0];
450
59
                   });
451
59
452
59
  // Compare static contents and assign unique IDs for each static content.
453
59
  forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
454
59
455
59
  // Split groups by comparing relocations until convergence is obtained.
456
60
  do {
457
60
    Repeat = false;
458
60
    forEachClass(
459
60
        [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
460
60
  } while (Repeat);
461
59
462
59
  log("ICF needed " + Twine(Cnt) + " iterations");
463
59
464
59
  // Merge sections by the equivalence class.
465
59
  forEachClassRange(0, Sections.size(), [&](size_t Begin, size_t End) {
466
59
    if (End - Begin == 1)
467
59
      return;
468
59
    print("selected section " + toString(Sections[Begin]));
469
59
    for (size_t I = Begin + 1; I < End; ++I) {
470
59
      print("  removing identical section " + toString(Sections[I]));
471
59
      Sections[Begin]->replace(Sections[I]);
472
59
473
59
      // At this point we know sections merged are fully identical and hence
474
59
      // we want to remove duplicate implicit dependencies such as link order
475
59
      // and relocation sections.
476
59
      for (InputSection *IS : Sections[I]->DependentSections)
477
59
        IS->Live = false;
478
59
    }
479
59
  });
480
59
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::run()
481
482
// ICF entry point function.
483
62
template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
void lld::elf::doIcf<llvm::object::ELFType<(llvm::support::endianness)1, false> >()
Line
Count
Source
483
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
483
59
template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
Unexecuted instantiation: void lld::elf::doIcf<llvm::object::ELFType<(llvm::support::endianness)0, true> >()
484
485
template void elf::doIcf<ELF32LE>();
486
template void elf::doIcf<ELF32BE>();
487
template void elf::doIcf<ELF64LE>();
488
template void elf::doIcf<ELF64BE>();