Coverage Report

Created: 2019-07-24 05:18

/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
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// ICF is short for Identical Code Folding. This is a size optimization to
10
// identify and merge two or more read-only sections (typically functions)
11
// that happened to have the same contents. It usually reduces output size
12
// by a few percent.
13
//
14
// In ICF, two sections are considered identical if they have the same
15
// section flags, section data, and relocations. Relocations are tricky,
16
// because two relocations are considered the same if they have the same
17
// relocation types, values, and if they point to the same sections *in
18
// terms of ICF*.
19
//
20
// Here is an example. If foo and bar defined below are compiled to the
21
// same machine instructions, ICF can and should merge the two, although
22
// their relocations point to each other.
23
//
24
//   void foo() { bar(); }
25
//   void bar() { foo(); }
26
//
27
// If you merge the two, their relocations point to the same section and
28
// thus you know they are mergeable, but how do you know they are
29
// mergeable in the first place? This is not an easy problem to solve.
30
//
31
// What we are doing in LLD is to partition sections into equivalence
32
// classes. Sections in the same equivalence class when the algorithm
33
// terminates are considered identical. Here are details:
34
//
35
// 1. First, we partition sections using their hash values as keys. Hash
36
//    values contain section types, section contents and numbers of
37
//    relocations. During this step, relocation targets are not taken into
38
//    account. We just put sections that apparently differ into different
39
//    equivalence classes.
40
//
41
// 2. Next, for each equivalence class, we visit sections to compare
42
//    relocation targets. Relocation targets are considered equivalent if
43
//    their targets are in the same equivalence class. Sections with
44
//    different relocation targets are put into different equivalence
45
//    clases.
46
//
47
// 3. If we split an equivalence class in step 2, two relocations
48
//    previously target the same equivalence class may now target
49
//    different equivalence classes. Therefore, we repeat step 2 until a
50
//    convergence is obtained.
51
//
52
// 4. For each equivalence class C, pick an arbitrary section in C, and
53
//    merge all the other sections in C with it.
54
//
55
// For small programs, this algorithm needs 3-5 iterations. For large
56
// programs such as Chromium, it takes more than 20 iterations.
57
//
58
// This algorithm was mentioned as an "optimistic algorithm" in [1],
59
// though gold implements a different algorithm than this.
60
//
61
// We parallelize each step so that multiple threads can work on different
62
// equivalence classes concurrently. That gave us a large performance
63
// boost when applying ICF on large programs. For example, MSVC link.exe
64
// or GNU gold takes 10-20 seconds to apply ICF on Chromium, whose output
65
// size is about 1.5 GB, but LLD can finish it in less than 2 seconds on a
66
// 2.8 GHz 40 core machine. Even without threading, LLD's ICF is still
67
// faster than MSVC or gold though.
68
//
69
// [1] Safe ICF: Pointer Safe and Unwinding aware Identical Code Folding
70
// in the Gold Linker
71
// http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/36912.pdf
72
//
73
//===----------------------------------------------------------------------===//
74
75
#include "ICF.h"
76
#include "Config.h"
77
#include "SymbolTable.h"
78
#include "Symbols.h"
79
#include "SyntheticSections.h"
80
#include "Writer.h"
81
#include "lld/Common/Threads.h"
82
#include "llvm/ADT/StringExtras.h"
83
#include "llvm/BinaryFormat/ELF.h"
84
#include "llvm/Object/ELF.h"
85
#include "llvm/Support/xxhash.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 true if section S is subject of ICF.
159
2.46k
static bool isEligible(InputSection *s) {
160
2.46k
  if (!s->isLive() || 
s->keepUnique2.46k
||
!(s->flags & SHF_ALLOC)2.38k
)
161
151
    return false;
162
2.31k
163
2.31k
  // Don't merge writable sections. .data.rel.ro sections are marked as writable
164
2.31k
  // but are semantically read-only.
165
2.31k
  if ((s->flags & SHF_WRITE) && 
s->name != ".data.rel.ro"3
&&
166
2.31k
      
!s->name.startswith(".data.rel.ro.")2
)
167
1
    return false;
168
2.31k
169
2.31k
  // SHF_LINK_ORDER sections are ICF'd as a unit with their dependent sections,
170
2.31k
  // so we don't consider them for ICF individually.
171
2.31k
  if (s->flags & SHF_LINK_ORDER)
172
4
    return false;
173
2.31k
174
2.31k
  // Don't merge synthetic sections as their Data member is not valid and empty.
175
2.31k
  // The Data member needs to be valid for ICF as it is used by ICF to determine
176
2.31k
  // the equality of section contents.
177
2.31k
  if (isa<SyntheticSection>(s))
178
9
    return false;
179
2.30k
180
2.30k
  // .init and .fini contains instructions that must be executed to initialize
181
2.30k
  // and finalize the process. They cannot and should not be merged.
182
2.30k
  if (s->name == ".init" || 
s->name == ".fini"2.30k
)
183
2
    return false;
184
2.30k
185
2.30k
  // A user program may enumerate sections named with a C identifier using
186
2.30k
  // __start_* and __stop_* symbols. We cannot ICF any such sections because
187
2.30k
  // that could change program semantics.
188
2.30k
  if (isValidCIdentifier(s->name))
189
2
    return false;
190
2.30k
191
2.30k
  return true;
192
2.30k
}
193
194
// Split an equivalence class into smaller classes.
195
template <class ELFT>
196
2.37k
void ICF<ELFT>::segregate(size_t begin, size_t end, bool constant) {
197
2.37k
  // This loop rearranges sections in [Begin, End) so that all sections
198
2.37k
  // that are equal in terms of equals{Constant,Variable} are contiguous
199
2.37k
  // in [Begin, End).
200
2.37k
  //
201
2.37k
  // The algorithm is quadratic in the worst case, but that is not an
202
2.37k
  // issue in practice because the number of the distinct sections in
203
2.37k
  // each range is usually very small.
204
2.37k
205
6.80k
  while (begin < end) {
206
4.43k
    // Divide [Begin, End) into two. Let Mid be the start index of the
207
4.43k
    // second group.
208
4.43k
    auto bound =
209
4.43k
        std::stable_partition(sections.begin() + begin + 1,
210
2.09M
                              sections.begin() + end, [&](InputSection *s) {
211
2.09M
                                if (constant)
212
2.09M
                                  return equalsConstant(sections[begin], s);
213
83
                                return equalsVariable(sections[begin], s);
214
83
                              });
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
210
6
                              sections.begin() + end, [&](InputSection *s) {
211
6
                                if (constant)
212
3
                                  return equalsConstant(sections[begin], s);
213
3
                                return equalsVariable(sections[begin], s);
214
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
210
2.09M
                              sections.begin() + end, [&](InputSection *s) {
211
2.09M
                                if (constant)
212
2.09M
                                  return equalsConstant(sections[begin], s);
213
80
                                return equalsVariable(sections[begin], s);
214
80
                              });
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
215
4.43k
    size_t mid = bound - sections.begin();
216
4.43k
217
4.43k
    // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
218
4.43k
    // updating the sections in [Begin, Mid). We use Mid as an equivalence
219
4.43k
    // class ID because every group ends with a unique index.
220
9.03k
    for (size_t i = begin; i < mid; 
++i4.60k
)
221
4.60k
      sections[i]->eqClass[next] = mid;
222
4.43k
223
4.43k
    // If we created a group, we need to iterate the main loop again.
224
4.43k
    if (mid != end)
225
2.06k
      repeat = true;
226
4.43k
227
4.43k
    begin = mid;
228
4.43k
  }
229
2.37k
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::segregate(unsigned long, unsigned long, bool)
Line
Count
Source
196
20
void ICF<ELFT>::segregate(size_t begin, size_t end, bool constant) {
197
20
  // This loop rearranges sections in [Begin, End) so that all sections
198
20
  // that are equal in terms of equals{Constant,Variable} are contiguous
199
20
  // in [Begin, End).
200
20
  //
201
20
  // The algorithm is quadratic in the worst case, but that is not an
202
20
  // issue in practice because the number of the distinct sections in
203
20
  // each range is usually very small.
204
20
205
40
  while (begin < end) {
206
20
    // Divide [Begin, End) into two. Let Mid be the start index of the
207
20
    // second group.
208
20
    auto bound =
209
20
        std::stable_partition(sections.begin() + begin + 1,
210
20
                              sections.begin() + end, [&](InputSection *s) {
211
20
                                if (constant)
212
20
                                  return equalsConstant(sections[begin], s);
213
20
                                return equalsVariable(sections[begin], s);
214
20
                              });
215
20
    size_t mid = bound - sections.begin();
216
20
217
20
    // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
218
20
    // updating the sections in [Begin, Mid). We use Mid as an equivalence
219
20
    // class ID because every group ends with a unique index.
220
46
    for (size_t i = begin; i < mid; 
++i26
)
221
26
      sections[i]->eqClass[next] = mid;
222
20
223
20
    // If we created a group, we need to iterate the main loop again.
224
20
    if (mid != end)
225
0
      repeat = true;
226
20
227
20
    begin = mid;
228
20
  }
229
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
196
2.35k
void ICF<ELFT>::segregate(size_t begin, size_t end, bool constant) {
197
2.35k
  // This loop rearranges sections in [Begin, End) so that all sections
198
2.35k
  // that are equal in terms of equals{Constant,Variable} are contiguous
199
2.35k
  // in [Begin, End).
200
2.35k
  //
201
2.35k
  // The algorithm is quadratic in the worst case, but that is not an
202
2.35k
  // issue in practice because the number of the distinct sections in
203
2.35k
  // each range is usually very small.
204
2.35k
205
6.76k
  while (begin < end) {
206
4.41k
    // Divide [Begin, End) into two. Let Mid be the start index of the
207
4.41k
    // second group.
208
4.41k
    auto bound =
209
4.41k
        std::stable_partition(sections.begin() + begin + 1,
210
4.41k
                              sections.begin() + end, [&](InputSection *s) {
211
4.41k
                                if (constant)
212
4.41k
                                  return equalsConstant(sections[begin], s);
213
4.41k
                                return equalsVariable(sections[begin], s);
214
4.41k
                              });
215
4.41k
    size_t mid = bound - sections.begin();
216
4.41k
217
4.41k
    // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
218
4.41k
    // updating the sections in [Begin, Mid). We use Mid as an equivalence
219
4.41k
    // class ID because every group ends with a unique index.
220
8.98k
    for (size_t i = begin; i < mid; 
++i4.57k
)
221
4.57k
      sections[i]->eqClass[next] = mid;
222
4.41k
223
4.41k
    // If we created a group, we need to iterate the main loop again.
224
4.41k
    if (mid != end)
225
2.06k
      repeat = true;
226
4.41k
227
4.41k
    begin = mid;
228
4.41k
  }
229
2.35k
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::segregate(unsigned long, unsigned long, bool)
230
231
// Compare two lists of relocations.
232
template <class ELFT>
233
template <class RelTy>
234
bool ICF<ELFT>::constantEq(const InputSection *secA, ArrayRef<RelTy> ra,
235
92
                           const InputSection *secB, ArrayRef<RelTy> rb) {
236
105
  for (size_t i = 0; i < ra.size(); 
++i13
) {
237
22
    if (ra[i].r_offset != rb[i].r_offset ||
238
22
        
ra[i].getType(config->isMips64EL) != rb[i].getType(config->isMips64EL)21
)
239
1
      return false;
240
21
241
21
    uint64_t addA = getAddend<ELFT>(ra[i]);
242
21
    uint64_t addB = getAddend<ELFT>(rb[i]);
243
21
244
21
    Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]);
245
21
    Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]);
246
21
    if (&sa == &sb) {
247
7
      if (addA == addB)
248
6
        continue;
249
1
      return false;
250
1
    }
251
14
252
14
    auto *da = dyn_cast<Defined>(&sa);
253
14
    auto *db = dyn_cast<Defined>(&sb);
254
14
255
14
    // Placeholder symbols generated by linker scripts look the same now but
256
14
    // may have different values later.
257
14
    if (!da || !db || da->scriptDefined || 
db->scriptDefined13
)
258
1
      return false;
259
13
260
13
    // Relocations referring to absolute symbols are constant-equal if their
261
13
    // values are equal.
262
13
    if (!da->section && 
!db->section2
&&
da->value + addA == db->value + addB2
)
263
1
      continue;
264
12
    if (!da->section || 
!db->section11
)
265
1
      return false;
266
11
267
11
    if (da->section->kind() != db->section->kind())
268
0
      return false;
269
11
270
11
    // Relocations referring to InputSections are constant-equal if their
271
11
    // section offsets are equal.
272
11
    if (isa<InputSection>(da->section)) {
273
5
      if (da->value + addA == db->value + addB)
274
4
        continue;
275
1
      return false;
276
1
    }
277
6
278
6
    // Relocations referring to MergeInputSections are constant-equal if their
279
6
    // offsets in the output section are equal.
280
6
    auto *x = dyn_cast<MergeInputSection>(da->section);
281
6
    if (!x)
282
1
      return false;
283
5
    auto *y = cast<MergeInputSection>(db->section);
284
5
    if (x->getParent() != y->getParent())
285
1
      return false;
286
4
287
4
    uint64_t offsetA =
288
4
        sa.isSection() ? 
x->getOffset(addA)1
:
x->getOffset(da->value) + addA3
;
289
4
    uint64_t offsetB =
290
4
        sb.isSection() ? 
y->getOffset(addB)1
:
y->getOffset(db->value) + addB3
;
291
4
    if (offsetA != offsetB)
292
2
      return false;
293
4
  }
294
92
295
92
  
return true83
;
296
92
}
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
235
3
                           const InputSection *secB, ArrayRef<RelTy> rb) {
236
4
  for (size_t i = 0; i < ra.size(); 
++i1
) {
237
1
    if (ra[i].r_offset != rb[i].r_offset ||
238
1
        ra[i].getType(config->isMips64EL) != rb[i].getType(config->isMips64EL))
239
0
      return false;
240
1
241
1
    uint64_t addA = getAddend<ELFT>(ra[i]);
242
1
    uint64_t addB = getAddend<ELFT>(rb[i]);
243
1
244
1
    Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]);
245
1
    Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]);
246
1
    if (&sa == &sb) {
247
1
      if (addA == addB)
248
1
        continue;
249
0
      return false;
250
0
    }
251
0
252
0
    auto *da = dyn_cast<Defined>(&sa);
253
0
    auto *db = dyn_cast<Defined>(&sb);
254
0
255
0
    // Placeholder symbols generated by linker scripts look the same now but
256
0
    // may have different values later.
257
0
    if (!da || !db || da->scriptDefined || db->scriptDefined)
258
0
      return false;
259
0
260
0
    // Relocations referring to absolute symbols are constant-equal if their
261
0
    // values are equal.
262
0
    if (!da->section && !db->section && da->value + addA == db->value + addB)
263
0
      continue;
264
0
    if (!da->section || !db->section)
265
0
      return false;
266
0
267
0
    if (da->section->kind() != db->section->kind())
268
0
      return false;
269
0
270
0
    // Relocations referring to InputSections are constant-equal if their
271
0
    // section offsets are equal.
272
0
    if (isa<InputSection>(da->section)) {
273
0
      if (da->value + addA == db->value + addB)
274
0
        continue;
275
0
      return false;
276
0
    }
277
0
278
0
    // Relocations referring to MergeInputSections are constant-equal if their
279
0
    // offsets in the output section are equal.
280
0
    auto *x = dyn_cast<MergeInputSection>(da->section);
281
0
    if (!x)
282
0
      return false;
283
0
    auto *y = cast<MergeInputSection>(db->section);
284
0
    if (x->getParent() != y->getParent())
285
0
      return false;
286
0
287
0
    uint64_t offsetA =
288
0
        sa.isSection() ? x->getOffset(addA) : x->getOffset(da->value) + addA;
289
0
    uint64_t offsetB =
290
0
        sb.isSection() ? y->getOffset(addB) : y->getOffset(db->value) + addB;
291
0
    if (offsetA != offsetB)
292
0
      return false;
293
0
  }
294
3
295
3
  return true;
296
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
235
20
                           const InputSection *secB, ArrayRef<RelTy> rb) {
236
32
  for (size_t i = 0; i < ra.size(); 
++i12
) {
237
21
    if (ra[i].r_offset != rb[i].r_offset ||
238
21
        
ra[i].getType(config->isMips64EL) != rb[i].getType(config->isMips64EL)20
)
239
1
      return false;
240
20
241
20
    uint64_t addA = getAddend<ELFT>(ra[i]);
242
20
    uint64_t addB = getAddend<ELFT>(rb[i]);
243
20
244
20
    Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]);
245
20
    Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]);
246
20
    if (&sa == &sb) {
247
6
      if (addA == addB)
248
5
        continue;
249
1
      return false;
250
1
    }
251
14
252
14
    auto *da = dyn_cast<Defined>(&sa);
253
14
    auto *db = dyn_cast<Defined>(&sb);
254
14
255
14
    // Placeholder symbols generated by linker scripts look the same now but
256
14
    // may have different values later.
257
14
    if (!da || !db || da->scriptDefined || 
db->scriptDefined13
)
258
1
      return false;
259
13
260
13
    // Relocations referring to absolute symbols are constant-equal if their
261
13
    // values are equal.
262
13
    if (!da->section && 
!db->section2
&&
da->value + addA == db->value + addB2
)
263
1
      continue;
264
12
    if (!da->section || 
!db->section11
)
265
1
      return false;
266
11
267
11
    if (da->section->kind() != db->section->kind())
268
0
      return false;
269
11
270
11
    // Relocations referring to InputSections are constant-equal if their
271
11
    // section offsets are equal.
272
11
    if (isa<InputSection>(da->section)) {
273
5
      if (da->value + addA == db->value + addB)
274
4
        continue;
275
1
      return false;
276
1
    }
277
6
278
6
    // Relocations referring to MergeInputSections are constant-equal if their
279
6
    // offsets in the output section are equal.
280
6
    auto *x = dyn_cast<MergeInputSection>(da->section);
281
6
    if (!x)
282
1
      return false;
283
5
    auto *y = cast<MergeInputSection>(db->section);
284
5
    if (x->getParent() != y->getParent())
285
1
      return false;
286
4
287
4
    uint64_t offsetA =
288
4
        sa.isSection() ? 
x->getOffset(addA)1
:
x->getOffset(da->value) + addA3
;
289
4
    uint64_t offsetB =
290
4
        sb.isSection() ? 
y->getOffset(addB)1
:
y->getOffset(db->value) + addB3
;
291
4
    if (offsetA != offsetB)
292
2
      return false;
293
4
  }
294
20
295
20
  
return true11
;
296
20
}
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
235
69
                           const InputSection *secB, ArrayRef<RelTy> rb) {
236
69
  for (size_t i = 0; i < ra.size(); 
++i0
) {
237
0
    if (ra[i].r_offset != rb[i].r_offset ||
238
0
        ra[i].getType(config->isMips64EL) != rb[i].getType(config->isMips64EL))
239
0
      return false;
240
0
241
0
    uint64_t addA = getAddend<ELFT>(ra[i]);
242
0
    uint64_t addB = getAddend<ELFT>(rb[i]);
243
0
244
0
    Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]);
245
0
    Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]);
246
0
    if (&sa == &sb) {
247
0
      if (addA == addB)
248
0
        continue;
249
0
      return false;
250
0
    }
251
0
252
0
    auto *da = dyn_cast<Defined>(&sa);
253
0
    auto *db = dyn_cast<Defined>(&sb);
254
0
255
0
    // Placeholder symbols generated by linker scripts look the same now but
256
0
    // may have different values later.
257
0
    if (!da || !db || da->scriptDefined || db->scriptDefined)
258
0
      return false;
259
0
260
0
    // Relocations referring to absolute symbols are constant-equal if their
261
0
    // values are equal.
262
0
    if (!da->section && !db->section && da->value + addA == db->value + addB)
263
0
      continue;
264
0
    if (!da->section || !db->section)
265
0
      return false;
266
0
267
0
    if (da->section->kind() != db->section->kind())
268
0
      return false;
269
0
270
0
    // Relocations referring to InputSections are constant-equal if their
271
0
    // section offsets are equal.
272
0
    if (isa<InputSection>(da->section)) {
273
0
      if (da->value + addA == db->value + addB)
274
0
        continue;
275
0
      return false;
276
0
    }
277
0
278
0
    // Relocations referring to MergeInputSections are constant-equal if their
279
0
    // offsets in the output section are equal.
280
0
    auto *x = dyn_cast<MergeInputSection>(da->section);
281
0
    if (!x)
282
0
      return false;
283
0
    auto *y = cast<MergeInputSection>(db->section);
284
0
    if (x->getParent() != y->getParent())
285
0
      return false;
286
0
287
0
    uint64_t offsetA =
288
0
        sa.isSection() ? x->getOffset(addA) : x->getOffset(da->value) + addA;
289
0
    uint64_t offsetB =
290
0
        sb.isSection() ? y->getOffset(addB) : y->getOffset(db->value) + addB;
291
0
    if (offsetA != offsetB)
292
0
      return false;
293
0
  }
294
69
295
69
  return true;
296
69
}
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> >)
297
298
// Compare "non-moving" part of two InputSections, namely everything
299
// except relocation targets.
300
template <class ELFT>
301
2.09M
bool ICF<ELFT>::equalsConstant(const InputSection *a, const InputSection *b) {
302
2.09M
  if (a->numRelocations != b->numRelocations || a->flags != b->flags ||
303
2.09M
      
a->getSize() != b->getSize()2.09M
||
a->data() != b->data()2.09M
)
304
2
    return false;
305
2.09M
306
2.09M
  // If two sections have different output sections, we cannot merge them.
307
2.09M
  // FIXME: This doesn't do the right thing in the case where there is a linker
308
2.09M
  // script. We probably need to move output section assignment before ICF to
309
2.09M
  // get the correct behaviour here.
310
2.09M
  if (getOutputSectionName(a) != getOutputSectionName(b))
311
2.09M
    return false;
312
92
313
92
  if (a->areRelocsRela)
314
20
    return constantEq(a, a->template relas<ELFT>(), b,
315
20
                      b->template relas<ELFT>());
316
72
  return constantEq(a, a->template rels<ELFT>(), b, b->template rels<ELFT>());
317
72
}
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
301
3
bool ICF<ELFT>::equalsConstant(const InputSection *a, const InputSection *b) {
302
3
  if (a->numRelocations != b->numRelocations || a->flags != b->flags ||
303
3
      a->getSize() != b->getSize() || a->data() != b->data())
304
0
    return false;
305
3
306
3
  // If two sections have different output sections, we cannot merge them.
307
3
  // FIXME: This doesn't do the right thing in the case where there is a linker
308
3
  // script. We probably need to move output section assignment before ICF to
309
3
  // get the correct behaviour here.
310
3
  if (getOutputSectionName(a) != getOutputSectionName(b))
311
0
    return false;
312
3
313
3
  if (a->areRelocsRela)
314
0
    return constantEq(a, a->template relas<ELFT>(), b,
315
0
                      b->template relas<ELFT>());
316
3
  return constantEq(a, a->template rels<ELFT>(), b, b->template rels<ELFT>());
317
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
301
2.09M
bool ICF<ELFT>::equalsConstant(const InputSection *a, const InputSection *b) {
302
2.09M
  if (a->numRelocations != b->numRelocations || a->flags != b->flags ||
303
2.09M
      
a->getSize() != b->getSize()2.09M
||
a->data() != b->data()2.09M
)
304
2
    return false;
305
2.09M
306
2.09M
  // If two sections have different output sections, we cannot merge them.
307
2.09M
  // FIXME: This doesn't do the right thing in the case where there is a linker
308
2.09M
  // script. We probably need to move output section assignment before ICF to
309
2.09M
  // get the correct behaviour here.
310
2.09M
  if (getOutputSectionName(a) != getOutputSectionName(b))
311
2.09M
    return false;
312
89
313
89
  if (a->areRelocsRela)
314
20
    return constantEq(a, a->template relas<ELFT>(), b,
315
20
                      b->template relas<ELFT>());
316
69
  return constantEq(a, a->template rels<ELFT>(), b, b->template rels<ELFT>());
317
69
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::equalsConstant(lld::elf::InputSection const*, lld::elf::InputSection const*)
318
319
// Compare two lists of relocations. Returns true if all pairs of
320
// relocations point to the same section in terms of ICF.
321
template <class ELFT>
322
template <class RelTy>
323
bool ICF<ELFT>::variableEq(const InputSection *secA, ArrayRef<RelTy> ra,
324
83
                           const InputSection *secB, ArrayRef<RelTy> rb) {
325
83
  assert(ra.size() == rb.size());
326
83
327
95
  for (size_t i = 0; i < ra.size(); 
++i12
) {
328
13
    // The two sections must be identical.
329
13
    Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]);
330
13
    Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]);
331
13
    if (&sa == &sb)
332
6
      continue;
333
7
334
7
    auto *da = cast<Defined>(&sa);
335
7
    auto *db = cast<Defined>(&sb);
336
7
337
7
    // We already dealt with absolute and non-InputSection symbols in
338
7
    // constantEq, and for InputSections we have already checked everything
339
7
    // except the equivalence class.
340
7
    if (!da->section)
341
1
      continue;
342
6
    auto *x = dyn_cast<InputSection>(da->section);
343
6
    if (!x)
344
2
      continue;
345
4
    auto *y = cast<InputSection>(db->section);
346
4
347
4
    // Ineligible sections are in the special equivalence class 0.
348
4
    // They can never be the same in terms of the equivalence class.
349
4
    if (x->eqClass[current] == 0)
350
1
      return false;
351
3
    if (x->eqClass[current] != y->eqClass[current])
352
0
      return false;
353
82
  };
354
82
355
82
  return true;
356
83
}
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
324
3
                           const InputSection *secB, ArrayRef<RelTy> rb) {
325
3
  assert(ra.size() == rb.size());
326
3
327
4
  for (size_t i = 0; i < ra.size(); 
++i1
) {
328
1
    // The two sections must be identical.
329
1
    Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]);
330
1
    Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]);
331
1
    if (&sa == &sb)
332
1
      continue;
333
0
334
0
    auto *da = cast<Defined>(&sa);
335
0
    auto *db = cast<Defined>(&sb);
336
0
337
0
    // We already dealt with absolute and non-InputSection symbols in
338
0
    // constantEq, and for InputSections we have already checked everything
339
0
    // except the equivalence class.
340
0
    if (!da->section)
341
0
      continue;
342
0
    auto *x = dyn_cast<InputSection>(da->section);
343
0
    if (!x)
344
0
      continue;
345
0
    auto *y = cast<InputSection>(db->section);
346
0
347
0
    // Ineligible sections are in the special equivalence class 0.
348
0
    // They can never be the same in terms of the equivalence class.
349
0
    if (x->eqClass[current] == 0)
350
0
      return false;
351
0
    if (x->eqClass[current] != y->eqClass[current])
352
0
      return false;
353
3
  };
354
3
355
3
  return true;
356
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
324
11
                           const InputSection *secB, ArrayRef<RelTy> rb) {
325
11
  assert(ra.size() == rb.size());
326
11
327
22
  for (size_t i = 0; i < ra.size(); 
++i11
) {
328
12
    // The two sections must be identical.
329
12
    Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]);
330
12
    Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]);
331
12
    if (&sa == &sb)
332
5
      continue;
333
7
334
7
    auto *da = cast<Defined>(&sa);
335
7
    auto *db = cast<Defined>(&sb);
336
7
337
7
    // We already dealt with absolute and non-InputSection symbols in
338
7
    // constantEq, and for InputSections we have already checked everything
339
7
    // except the equivalence class.
340
7
    if (!da->section)
341
1
      continue;
342
6
    auto *x = dyn_cast<InputSection>(da->section);
343
6
    if (!x)
344
2
      continue;
345
4
    auto *y = cast<InputSection>(db->section);
346
4
347
4
    // Ineligible sections are in the special equivalence class 0.
348
4
    // They can never be the same in terms of the equivalence class.
349
4
    if (x->eqClass[current] == 0)
350
1
      return false;
351
3
    if (x->eqClass[current] != y->eqClass[current])
352
0
      return false;
353
10
  };
354
10
355
10
  return true;
356
11
}
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
324
69
                           const InputSection *secB, ArrayRef<RelTy> rb) {
325
69
  assert(ra.size() == rb.size());
326
69
327
69
  for (size_t i = 0; i < ra.size(); 
++i0
) {
328
0
    // The two sections must be identical.
329
0
    Symbol &sa = secA->template getFile<ELFT>()->getRelocTargetSym(ra[i]);
330
0
    Symbol &sb = secB->template getFile<ELFT>()->getRelocTargetSym(rb[i]);
331
0
    if (&sa == &sb)
332
0
      continue;
333
0
334
0
    auto *da = cast<Defined>(&sa);
335
0
    auto *db = cast<Defined>(&sb);
336
0
337
0
    // We already dealt with absolute and non-InputSection symbols in
338
0
    // constantEq, and for InputSections we have already checked everything
339
0
    // except the equivalence class.
340
0
    if (!da->section)
341
0
      continue;
342
0
    auto *x = dyn_cast<InputSection>(da->section);
343
0
    if (!x)
344
0
      continue;
345
0
    auto *y = cast<InputSection>(db->section);
346
0
347
0
    // Ineligible sections are in the special equivalence class 0.
348
0
    // They can never be the same in terms of the equivalence class.
349
0
    if (x->eqClass[current] == 0)
350
0
      return false;
351
0
    if (x->eqClass[current] != y->eqClass[current])
352
0
      return false;
353
69
  };
354
69
355
69
  return true;
356
69
}
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> >)
357
358
// Compare "moving" part of two InputSections, namely relocation targets.
359
template <class ELFT>
360
83
bool ICF<ELFT>::equalsVariable(const InputSection *a, const InputSection *b) {
361
83
  if (a->areRelocsRela)
362
11
    return variableEq(a, a->template relas<ELFT>(), b,
363
11
                      b->template relas<ELFT>());
364
72
  return variableEq(a, a->template rels<ELFT>(), b, b->template rels<ELFT>());
365
72
}
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
360
3
bool ICF<ELFT>::equalsVariable(const InputSection *a, const InputSection *b) {
361
3
  if (a->areRelocsRela)
362
0
    return variableEq(a, a->template relas<ELFT>(), b,
363
0
                      b->template relas<ELFT>());
364
3
  return variableEq(a, a->template rels<ELFT>(), b, b->template rels<ELFT>());
365
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
360
80
bool ICF<ELFT>::equalsVariable(const InputSection *a, const InputSection *b) {
361
80
  if (a->areRelocsRela)
362
11
    return variableEq(a, a->template relas<ELFT>(), b,
363
11
                      b->template relas<ELFT>());
364
69
  return variableEq(a, a->template rels<ELFT>(), b, b->template rels<ELFT>());
365
69
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::equalsVariable(lld::elf::InputSection const*, lld::elf::InputSection const*)
366
367
5.09k
template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t begin, size_t end) {
368
5.09k
  uint32_t eqClass = sections[begin]->eqClass[current];
369
199k
  for (size_t i = begin + 1; i < end; 
++i194k
)
370
198k
    if (eqClass != sections[i]->eqClass[current])
371
4.40k
      return i;
372
5.09k
  
return end692
;
373
5.09k
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::findBoundary(unsigned long, unsigned long)
Line
Count
Source
367
30
template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t begin, size_t end) {
368
30
  uint32_t eqClass = sections[begin]->eqClass[current];
369
39
  for (size_t i = begin + 1; i < end; 
++i9
)
370
30
    if (eqClass != sections[i]->eqClass[current])
371
21
      return i;
372
30
  
return end9
;
373
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
367
5.06k
template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t begin, size_t end) {
368
5.06k
  uint32_t eqClass = sections[begin]->eqClass[current];
369
199k
  for (size_t i = begin + 1; i < end; 
++i194k
)
370
198k
    if (eqClass != sections[i]->eqClass[current])
371
4.38k
      return i;
372
5.06k
  
return end683
;
373
5.06k
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::findBoundary(unsigned long, unsigned long)
374
375
// Sections in the same equivalence class are contiguous in Sections
376
// vector. Therefore, Sections vector can be considered as contiguous
377
// groups of sections, grouped by the class.
378
//
379
// This function calls Fn on every group within [Begin, End).
380
template <class ELFT>
381
void ICF<ELFT>::forEachClassRange(size_t begin, size_t end,
382
439
                                  llvm::function_ref<void(size_t, size_t)> fn) {
383
5.02k
  while (begin < end) {
384
4.58k
    size_t mid = findBoundary(begin, end);
385
4.58k
    fn(begin, mid);
386
4.58k
    begin = mid;
387
4.58k
  }
388
439
}
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
382
9
                                  llvm::function_ref<void(size_t, size_t)> fn) {
383
39
  while (begin < end) {
384
30
    size_t mid = findBoundary(begin, end);
385
30
    fn(begin, mid);
386
30
    begin = mid;
387
30
  }
388
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
382
430
                                  llvm::function_ref<void(size_t, size_t)> fn) {
383
4.98k
  while (begin < end) {
384
4.55k
    size_t mid = findBoundary(begin, end);
385
4.55k
    fn(begin, mid);
386
4.55k
    begin = mid;
387
4.55k
  }
388
430
}
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)>)
389
390
// Call Fn on each equivalence class.
391
template <class ELFT>
392
123
void ICF<ELFT>::forEachClass(llvm::function_ref<void(size_t, size_t)> fn) {
393
123
  // If threading is disabled or the number of sections are
394
123
  // too small to use threading, call Fn sequentially.
395
123
  if (!threadsEnabled || sections.size() < 1024) {
396
121
    forEachClassRange(0, sections.size(), fn);
397
121
    ++cnt;
398
121
    return;
399
121
  }
400
2
401
2
  current = cnt % 2;
402
2
  next = (cnt + 1) % 2;
403
2
404
2
  // Shard into non-overlapping intervals, and call Fn in parallel.
405
2
  // The sharding must be completed before any calls to Fn are made
406
2
  // so that Fn can modify the Chunks in its shard without causing data
407
2
  // races.
408
2
  const size_t numShards = 256;
409
2
  size_t step = sections.size() / numShards;
410
2
  size_t boundaries[numShards + 1];
411
2
  boundaries[0] = 0;
412
2
  boundaries[numShards] = sections.size();
413
2
414
508
  parallelForEachN(1, numShards, [&](size_t i) {
415
508
    boundaries[i] = findBoundary((i - 1) * step, sections.size());
416
508
  });
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
414
508
  parallelForEachN(1, numShards, [&](size_t i) {
415
508
    boundaries[i] = findBoundary((i - 1) * step, sections.size());
416
508
  });
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
417
2
418
512
  parallelForEachN(1, numShards + 1, [&](size_t i) {
419
512
    if (boundaries[i - 1] < boundaries[i])
420
257
      forEachClassRange(boundaries[i - 1], boundaries[i], fn);
421
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
418
512
  parallelForEachN(1, numShards + 1, [&](size_t i) {
419
512
    if (boundaries[i - 1] < boundaries[i])
420
257
      forEachClassRange(boundaries[i - 1], boundaries[i], fn);
421
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
422
2
  ++cnt;
423
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
392
6
void ICF<ELFT>::forEachClass(llvm::function_ref<void(size_t, size_t)> fn) {
393
6
  // If threading is disabled or the number of sections are
394
6
  // too small to use threading, call Fn sequentially.
395
6
  if (!threadsEnabled || sections.size() < 1024) {
396
6
    forEachClassRange(0, sections.size(), fn);
397
6
    ++cnt;
398
6
    return;
399
6
  }
400
0
401
0
  current = cnt % 2;
402
0
  next = (cnt + 1) % 2;
403
0
404
0
  // Shard into non-overlapping intervals, and call Fn in parallel.
405
0
  // The sharding must be completed before any calls to Fn are made
406
0
  // so that Fn can modify the Chunks in its shard without causing data
407
0
  // races.
408
0
  const size_t numShards = 256;
409
0
  size_t step = sections.size() / numShards;
410
0
  size_t boundaries[numShards + 1];
411
0
  boundaries[0] = 0;
412
0
  boundaries[numShards] = sections.size();
413
0
414
0
  parallelForEachN(1, numShards, [&](size_t i) {
415
0
    boundaries[i] = findBoundary((i - 1) * step, sections.size());
416
0
  });
417
0
418
0
  parallelForEachN(1, numShards + 1, [&](size_t i) {
419
0
    if (boundaries[i - 1] < boundaries[i])
420
0
      forEachClassRange(boundaries[i - 1], boundaries[i], fn);
421
0
  });
422
0
  ++cnt;
423
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
392
117
void ICF<ELFT>::forEachClass(llvm::function_ref<void(size_t, size_t)> fn) {
393
117
  // If threading is disabled or the number of sections are
394
117
  // too small to use threading, call Fn sequentially.
395
117
  if (!threadsEnabled || sections.size() < 1024) {
396
115
    forEachClassRange(0, sections.size(), fn);
397
115
    ++cnt;
398
115
    return;
399
115
  }
400
2
401
2
  current = cnt % 2;
402
2
  next = (cnt + 1) % 2;
403
2
404
2
  // Shard into non-overlapping intervals, and call Fn in parallel.
405
2
  // The sharding must be completed before any calls to Fn are made
406
2
  // so that Fn can modify the Chunks in its shard without causing data
407
2
  // races.
408
2
  const size_t numShards = 256;
409
2
  size_t step = sections.size() / numShards;
410
2
  size_t boundaries[numShards + 1];
411
2
  boundaries[0] = 0;
412
2
  boundaries[numShards] = sections.size();
413
2
414
2
  parallelForEachN(1, numShards, [&](size_t i) {
415
2
    boundaries[i] = findBoundary((i - 1) * step, sections.size());
416
2
  });
417
2
418
2
  parallelForEachN(1, numShards + 1, [&](size_t i) {
419
2
    if (boundaries[i - 1] < boundaries[i])
420
2
      forEachClassRange(boundaries[i - 1], boundaries[i], fn);
421
2
  });
422
2
  ++cnt;
423
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)>)
424
425
// Combine the hashes of the sections referenced by the given section into its
426
// hash.
427
template <class ELFT, class RelTy>
428
static void combineRelocHashes(unsigned cnt, InputSection *isec,
429
4.60k
                               ArrayRef<RelTy> rels) {
430
4.60k
  uint32_t hash = isec->eqClass[cnt % 2];
431
4.60k
  for (RelTy rel : rels) {
432
134
    Symbol &s = isec->template getFile<ELFT>()->getRelocTargetSym(rel);
433
134
    if (auto *d = dyn_cast<Defined>(&s))
434
108
      if (auto *relSec = dyn_cast_or_null<InputSection>(d->section))
435
66
        hash += relSec->eqClass[cnt % 2];
436
134
  }
437
4.60k
  // Set MSB to 1 to avoid collisions with non-hash IDs.
438
4.60k
  isec->eqClass[(cnt + 1) % 2] = hash | (1U << 31);
439
4.60k
}
Unexecuted instantiation: ICF.cpp:void combineRelocHashes<llvm::object::ELFType<(llvm::support::endianness)1, false>, llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, false>, true> >(unsigned int, lld::elf::InputSection*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, false>, true> >)
ICF.cpp:void combineRelocHashes<llvm::object::ELFType<(llvm::support::endianness)1, false>, llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, false>, false> >(unsigned int, lld::elf::InputSection*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, false>, false> >)
Line
Count
Source
429
26
                               ArrayRef<RelTy> rels) {
430
26
  uint32_t hash = isec->eqClass[cnt % 2];
431
26
  for (RelTy rel : rels) {
432
14
    Symbol &s = isec->template getFile<ELFT>()->getRelocTargetSym(rel);
433
14
    if (auto *d = dyn_cast<Defined>(&s))
434
8
      if (auto *relSec = dyn_cast_or_null<InputSection>(d->section))
435
8
        hash += relSec->eqClass[cnt % 2];
436
14
  }
437
26
  // Set MSB to 1 to avoid collisions with non-hash IDs.
438
26
  isec->eqClass[(cnt + 1) % 2] = hash | (1U << 31);
439
26
}
Unexecuted instantiation: ICF.cpp:void combineRelocHashes<llvm::object::ELFType<(llvm::support::endianness)0, false>, llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, false>, true> >(unsigned int, lld::elf::InputSection*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, false>, true> >)
Unexecuted instantiation: ICF.cpp:void combineRelocHashes<llvm::object::ELFType<(llvm::support::endianness)0, false>, llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, false>, false> >(unsigned int, lld::elf::InputSection*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, false>, false> >)
ICF.cpp:void combineRelocHashes<llvm::object::ELFType<(llvm::support::endianness)1, true>, llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, true> >(unsigned int, lld::elf::InputSection*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, true> >)
Line
Count
Source
429
112
                               ArrayRef<RelTy> rels) {
430
112
  uint32_t hash = isec->eqClass[cnt % 2];
431
120
  for (RelTy rel : rels) {
432
120
    Symbol &s = isec->template getFile<ELFT>()->getRelocTargetSym(rel);
433
120
    if (auto *d = dyn_cast<Defined>(&s))
434
100
      if (auto *relSec = dyn_cast_or_null<InputSection>(d->section))
435
58
        hash += relSec->eqClass[cnt % 2];
436
120
  }
437
112
  // Set MSB to 1 to avoid collisions with non-hash IDs.
438
112
  isec->eqClass[(cnt + 1) % 2] = hash | (1U << 31);
439
112
}
ICF.cpp:void combineRelocHashes<llvm::object::ELFType<(llvm::support::endianness)1, true>, llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, false> >(unsigned int, lld::elf::InputSection*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)1, true>, false> >)
Line
Count
Source
429
4.46k
                               ArrayRef<RelTy> rels) {
430
4.46k
  uint32_t hash = isec->eqClass[cnt % 2];
431
4.46k
  for (RelTy rel : rels) {
432
0
    Symbol &s = isec->template getFile<ELFT>()->getRelocTargetSym(rel);
433
0
    if (auto *d = dyn_cast<Defined>(&s))
434
0
      if (auto *relSec = dyn_cast_or_null<InputSection>(d->section))
435
0
        hash += relSec->eqClass[cnt % 2];
436
0
  }
437
4.46k
  // Set MSB to 1 to avoid collisions with non-hash IDs.
438
4.46k
  isec->eqClass[(cnt + 1) % 2] = hash | (1U << 31);
439
4.46k
}
Unexecuted instantiation: ICF.cpp:void combineRelocHashes<llvm::object::ELFType<(llvm::support::endianness)0, true>, llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, true>, true> >(unsigned int, lld::elf::InputSection*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, true>, true> >)
Unexecuted instantiation: ICF.cpp:void combineRelocHashes<llvm::object::ELFType<(llvm::support::endianness)0, true>, llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, true>, false> >(unsigned int, lld::elf::InputSection*, llvm::ArrayRef<llvm::object::Elf_Rel_Impl<llvm::object::ELFType<(llvm::support::endianness)0, true>, false> >)
440
441
143
static void print(const Twine &s) {
442
143
  if (config->printIcfSections)
443
98
    message(s);
444
143
}
445
446
// The main function of ICF.
447
61
template <class ELFT> void ICF<ELFT>::run() {
448
61
  // Collect sections to merge.
449
61
  for (InputSectionBase *sec : inputSections)
450
2.47k
    if (auto *s = dyn_cast<InputSection>(sec))
451
2.46k
      if (isEligible(s))
452
2.30k
        sections.push_back(s);
453
61
454
61
  // Initially, we use hash values to partition sections.
455
2.30k
  parallelForEach(sections, [&](InputSection *s) {
456
2.30k
    s->eqClass[0] = xxHash64(s->data());
457
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
455
13
  parallelForEach(sections, [&](InputSection *s) {
456
13
    s->eqClass[0] = xxHash64(s->data());
457
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
455
2.28k
  parallelForEach(sections, [&](InputSection *s) {
456
2.28k
    s->eqClass[0] = xxHash64(s->data());
457
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
458
61
459
183
  for (unsigned cnt = 0; cnt != 2; 
++cnt122
) {
460
4.60k
    parallelForEach(sections, [&](InputSection *s) {
461
4.60k
      if (s->areRelocsRela)
462
112
        combineRelocHashes<ELFT>(cnt, s, s->template relas<ELFT>());
463
4.48k
      else
464
4.48k
        combineRelocHashes<ELFT>(cnt, s, s->template rels<ELFT>());
465
4.60k
    });
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::run()::'lambda0'(lld::elf::InputSection*)::operator()(lld::elf::InputSection*) const
Line
Count
Source
460
26
    parallelForEach(sections, [&](InputSection *s) {
461
26
      if (s->areRelocsRela)
462
0
        combineRelocHashes<ELFT>(cnt, s, s->template relas<ELFT>());
463
26
      else
464
26
        combineRelocHashes<ELFT>(cnt, s, s->template rels<ELFT>());
465
26
    });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::run()::'lambda0'(lld::elf::InputSection*)::operator()(lld::elf::InputSection*) const
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::run()::'lambda0'(lld::elf::InputSection*)::operator()(lld::elf::InputSection*) const
Line
Count
Source
460
4.57k
    parallelForEach(sections, [&](InputSection *s) {
461
4.57k
      if (s->areRelocsRela)
462
112
        combineRelocHashes<ELFT>(cnt, s, s->template relas<ELFT>());
463
4.46k
      else
464
4.46k
        combineRelocHashes<ELFT>(cnt, s, s->template rels<ELFT>());
465
4.57k
    });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::run()::'lambda0'(lld::elf::InputSection*)::operator()(lld::elf::InputSection*) const
466
122
  }
467
61
468
61
  // From now on, sections in Sections vector are ordered so that sections
469
61
  // in the same equivalence class are consecutive in the vector.
470
6.66k
  llvm::stable_sort(sections, [](const InputSection *a, const InputSection *b) {
471
6.66k
    return a->eqClass[0] < b->eqClass[0];
472
6.66k
  });
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::run()::'lambda'(lld::elf::InputSection const*, lld::elf::InputSection const*)::operator()(lld::elf::InputSection const*, lld::elf::InputSection const*) const
Line
Count
Source
470
16
  llvm::stable_sort(sections, [](const InputSection *a, const InputSection *b) {
471
16
    return a->eqClass[0] < b->eqClass[0];
472
16
  });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::run()::'lambda'(lld::elf::InputSection const*, lld::elf::InputSection const*)::operator()(lld::elf::InputSection const*, lld::elf::InputSection const*) const
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::run()::'lambda'(lld::elf::InputSection const*, lld::elf::InputSection const*)::operator()(lld::elf::InputSection const*, lld::elf::InputSection const*) const
Line
Count
Source
470
6.64k
  llvm::stable_sort(sections, [](const InputSection *a, const InputSection *b) {
471
6.64k
    return a->eqClass[0] < b->eqClass[0];
472
6.64k
  });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::run()::'lambda'(lld::elf::InputSection const*, lld::elf::InputSection const*)::operator()(lld::elf::InputSection const*, lld::elf::InputSection const*) const
473
61
474
61
  // Compare static contents and assign unique IDs for each static content.
475
156
  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
475
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
475
146
  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
476
61
477
61
  // Split groups by comparing relocations until convergence is obtained.
478
62
  do {
479
62
    repeat = false;
480
62
    forEachClass(
481
2.21k
        [&](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
481
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
481
2.20k
        [&](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
482
62
  } while (repeat);
483
61
484
61
  log("ICF needed " + Twine(cnt) + " iterations");
485
61
486
61
  // Merge sections by the equivalence class.
487
2.21k
  forEachClassRange(0, sections.size(), [&](size_t begin, size_t end) {
488
2.21k
    if (end - begin == 1)
489
2.15k
      return;
490
61
    print("selected section " + toString(sections[begin]));
491
143
    for (size_t i = begin + 1; i < end; 
++i82
) {
492
82
      print("  removing identical section " + toString(sections[i]));
493
82
      sections[begin]->replace(sections[i]);
494
82
495
82
      // At this point we know sections merged are fully identical and hence
496
82
      // we want to remove duplicate implicit dependencies such as link order
497
82
      // and relocation sections.
498
82
      for (InputSection *isec : sections[i]->dependentSections)
499
4
        isec->markDead();
500
82
    }
501
61
  });
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
487
10
  forEachClassRange(0, sections.size(), [&](size_t begin, size_t end) {
488
10
    if (end - begin == 1)
489
7
      return;
490
3
    print("selected section " + toString(sections[begin]));
491
6
    for (size_t i = begin + 1; i < end; 
++i3
) {
492
3
      print("  removing identical section " + toString(sections[i]));
493
3
      sections[begin]->replace(sections[i]);
494
3
495
3
      // At this point we know sections merged are fully identical and hence
496
3
      // we want to remove duplicate implicit dependencies such as link order
497
3
      // and relocation sections.
498
3
      for (InputSection *isec : sections[i]->dependentSections)
499
1
        isec->markDead();
500
3
    }
501
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
487
2.20k
  forEachClassRange(0, sections.size(), [&](size_t begin, size_t end) {
488
2.20k
    if (end - begin == 1)
489
2.15k
      return;
490
58
    print("selected section " + toString(sections[begin]));
491
137
    for (size_t i = begin + 1; i < end; 
++i79
) {
492
79
      print("  removing identical section " + toString(sections[i]));
493
79
      sections[begin]->replace(sections[i]);
494
79
495
79
      // At this point we know sections merged are fully identical and hence
496
79
      // we want to remove duplicate implicit dependencies such as link order
497
79
      // and relocation sections.
498
79
      for (InputSection *isec : sections[i]->dependentSections)
499
3
        isec->markDead();
500
79
    }
501
58
  });
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
502
61
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::run()
Line
Count
Source
447
3
template <class ELFT> void ICF<ELFT>::run() {
448
3
  // Collect sections to merge.
449
3
  for (InputSectionBase *sec : inputSections)
450
19
    if (auto *s = dyn_cast<InputSection>(sec))
451
19
      if (isEligible(s))
452
13
        sections.push_back(s);
453
3
454
3
  // Initially, we use hash values to partition sections.
455
3
  parallelForEach(sections, [&](InputSection *s) {
456
3
    s->eqClass[0] = xxHash64(s->data());
457
3
  });
458
3
459
9
  for (unsigned cnt = 0; cnt != 2; 
++cnt6
) {
460
6
    parallelForEach(sections, [&](InputSection *s) {
461
6
      if (s->areRelocsRela)
462
6
        combineRelocHashes<ELFT>(cnt, s, s->template relas<ELFT>());
463
6
      else
464
6
        combineRelocHashes<ELFT>(cnt, s, s->template rels<ELFT>());
465
6
    });
466
6
  }
467
3
468
3
  // From now on, sections in Sections vector are ordered so that sections
469
3
  // in the same equivalence class are consecutive in the vector.
470
3
  llvm::stable_sort(sections, [](const InputSection *a, const InputSection *b) {
471
3
    return a->eqClass[0] < b->eqClass[0];
472
3
  });
473
3
474
3
  // Compare static contents and assign unique IDs for each static content.
475
3
  forEachClass([&](size_t begin, size_t end) { segregate(begin, end, true); });
476
3
477
3
  // Split groups by comparing relocations until convergence is obtained.
478
3
  do {
479
3
    repeat = false;
480
3
    forEachClass(
481
3
        [&](size_t begin, size_t end) { segregate(begin, end, false); });
482
3
  } while (repeat);
483
3
484
3
  log("ICF needed " + Twine(cnt) + " iterations");
485
3
486
3
  // Merge sections by the equivalence class.
487
3
  forEachClassRange(0, sections.size(), [&](size_t begin, size_t end) {
488
3
    if (end - begin == 1)
489
3
      return;
490
3
    print("selected section " + toString(sections[begin]));
491
3
    for (size_t i = begin + 1; i < end; ++i) {
492
3
      print("  removing identical section " + toString(sections[i]));
493
3
      sections[begin]->replace(sections[i]);
494
3
495
3
      // At this point we know sections merged are fully identical and hence
496
3
      // we want to remove duplicate implicit dependencies such as link order
497
3
      // and relocation sections.
498
3
      for (InputSection *isec : sections[i]->dependentSections)
499
3
        isec->markDead();
500
3
    }
501
3
  });
502
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
447
58
template <class ELFT> void ICF<ELFT>::run() {
448
58
  // Collect sections to merge.
449
58
  for (InputSectionBase *sec : inputSections)
450
2.45k
    if (auto *s = dyn_cast<InputSection>(sec))
451
2.45k
      if (isEligible(s))
452
2.28k
        sections.push_back(s);
453
58
454
58
  // Initially, we use hash values to partition sections.
455
58
  parallelForEach(sections, [&](InputSection *s) {
456
58
    s->eqClass[0] = xxHash64(s->data());
457
58
  });
458
58
459
174
  for (unsigned cnt = 0; cnt != 2; 
++cnt116
) {
460
116
    parallelForEach(sections, [&](InputSection *s) {
461
116
      if (s->areRelocsRela)
462
116
        combineRelocHashes<ELFT>(cnt, s, s->template relas<ELFT>());
463
116
      else
464
116
        combineRelocHashes<ELFT>(cnt, s, s->template rels<ELFT>());
465
116
    });
466
116
  }
467
58
468
58
  // From now on, sections in Sections vector are ordered so that sections
469
58
  // in the same equivalence class are consecutive in the vector.
470
58
  llvm::stable_sort(sections, [](const InputSection *a, const InputSection *b) {
471
58
    return a->eqClass[0] < b->eqClass[0];
472
58
  });
473
58
474
58
  // Compare static contents and assign unique IDs for each static content.
475
58
  forEachClass([&](size_t begin, size_t end) { segregate(begin, end, true); });
476
58
477
58
  // Split groups by comparing relocations until convergence is obtained.
478
59
  do {
479
59
    repeat = false;
480
59
    forEachClass(
481
59
        [&](size_t begin, size_t end) { segregate(begin, end, false); });
482
59
  } while (repeat);
483
58
484
58
  log("ICF needed " + Twine(cnt) + " iterations");
485
58
486
58
  // Merge sections by the equivalence class.
487
58
  forEachClassRange(0, sections.size(), [&](size_t begin, size_t end) {
488
58
    if (end - begin == 1)
489
58
      return;
490
58
    print("selected section " + toString(sections[begin]));
491
58
    for (size_t i = begin + 1; i < end; ++i) {
492
58
      print("  removing identical section " + toString(sections[i]));
493
58
      sections[begin]->replace(sections[i]);
494
58
495
58
      // At this point we know sections merged are fully identical and hence
496
58
      // we want to remove duplicate implicit dependencies such as link order
497
58
      // and relocation sections.
498
58
      for (InputSection *isec : sections[i]->dependentSections)
499
58
        isec->markDead();
500
58
    }
501
58
  });
502
58
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::run()
503
504
// ICF entry point function.
505
61
template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
void lld::elf::doIcf<llvm::object::ELFType<(llvm::support::endianness)1, false> >()
Line
Count
Source
505
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
505
58
template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
Unexecuted instantiation: void lld::elf::doIcf<llvm::object::ELFType<(llvm::support::endianness)0, true> >()
506
507
template void elf::doIcf<ELF32LE>();
508
template void elf::doIcf<ELF32BE>();
509
template void elf::doIcf<ELF64LE>();
510
template void elf::doIcf<ELF64BE>();