Coverage Report

Created: 2018-01-17 17:22

/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 "lld/Common/Threads.h"
81
#include "llvm/ADT/Hashing.h"
82
#include "llvm/BinaryFormat/ELF.h"
83
#include "llvm/Object/ELF.h"
84
#include <algorithm>
85
#include <atomic>
86
87
using namespace lld;
88
using namespace lld::elf;
89
using namespace llvm;
90
using namespace llvm::ELF;
91
using namespace llvm::object;
92
93
namespace {
94
template <class ELFT> class ICF {
95
public:
96
  void run();
97
98
private:
99
  void segregate(size_t Begin, size_t End, bool Constant);
100
101
  template <class RelTy>
102
  bool constantEq(const InputSection *A, ArrayRef<RelTy> RelsA,
103
                  const InputSection *B, ArrayRef<RelTy> RelsB);
104
105
  template <class RelTy>
106
  bool variableEq(const InputSection *A, ArrayRef<RelTy> RelsA,
107
                  const InputSection *B, ArrayRef<RelTy> RelsB);
108
109
  bool equalsConstant(const InputSection *A, const InputSection *B);
110
  bool equalsVariable(const InputSection *A, const InputSection *B);
111
112
  size_t findBoundary(size_t Begin, size_t End);
113
114
  void forEachClassRange(size_t Begin, size_t End,
115
                         std::function<void(size_t, size_t)> Fn);
116
117
  void forEachClass(std::function<void(size_t, size_t)> Fn);
118
119
  std::vector<InputSection *> Sections;
120
121
  // We repeat the main loop while `Repeat` is true.
122
  std::atomic<bool> Repeat;
123
124
  // The main loop counter.
125
  int Cnt = 0;
126
127
  // We have two locations for equivalence classes. On the first iteration
128
  // of the main loop, Class[0] has a valid value, and Class[1] contains
129
  // garbage. We read equivalence classes from slot 0 and write to slot 1.
130
  // So, Class[0] represents the current class, and Class[1] represents
131
  // the next class. On each iteration, we switch their roles and use them
132
  // alternately.
133
  //
134
  // Why are we doing this? Recall that other threads may be working on
135
  // other equivalence classes in parallel. They may read sections that we
136
  // are updating. We cannot update equivalence classes in place because
137
  // it breaks the invariance that all possibly-identical sections must be
138
  // in the same equivalence class at any moment. In other words, the for
139
  // loop to update equivalence classes is not atomic, and that is
140
  // observable from other threads. By writing new classes to other
141
  // places, we can keep the invariance.
142
  //
143
  // Below, `Current` has the index of the current class, and `Next` has
144
  // the index of the next class. If threading is enabled, they are either
145
  // (0, 1) or (1, 0).
146
  //
147
  // Note on single-thread: if that's the case, they are always (0, 0)
148
  // because we can safely read the next class without worrying about race
149
  // conditions. Using the same location makes this algorithm converge
150
  // faster because it uses results of the same iteration earlier.
151
  int Current = 0;
152
  int Next = 0;
153
};
154
}
155
156
// Returns a hash value for S. Note that the information about
157
// relocation targets is not included in the hash value.
158
71
template <class ELFT> static uint32_t getHash(InputSection *S) {
159
71
  return hash_combine(S->Flags, S->getSize(), S->NumRelocations, S->Data);
160
71
}
ICF.cpp:unsigned int getHash<llvm::object::ELFType<(llvm::support::endianness)1, false> >(lld::elf::InputSection*)
Line
Count
Source
158
8
template <class ELFT> static uint32_t getHash(InputSection *S) {
159
8
  return hash_combine(S->Flags, S->getSize(), S->NumRelocations, S->Data);
160
8
}
Unexecuted instantiation: ICF.cpp:unsigned int getHash<llvm::object::ELFType<(llvm::support::endianness)0, false> >(lld::elf::InputSection*)
ICF.cpp:unsigned int getHash<llvm::object::ELFType<(llvm::support::endianness)1, true> >(lld::elf::InputSection*)
Line
Count
Source
158
63
template <class ELFT> static uint32_t getHash(InputSection *S) {
159
63
  return hash_combine(S->Flags, S->getSize(), S->NumRelocations, S->Data);
160
63
}
Unexecuted instantiation: ICF.cpp:unsigned int getHash<llvm::object::ELFType<(llvm::support::endianness)0, true> >(lld::elf::InputSection*)
161
162
// Returns true if section S is subject of ICF.
163
106
static bool isEligible(InputSection *S) {
164
106
  // Don't merge read only data sections unless
165
106
  // --ignore-data-address-equality was passed.
166
106
  if (!(S->Flags & SHF_EXECINSTR) && 
!Config->IgnoreDataAddressEquality34
)
167
31
    return false;
168
75
169
75
  // .init and .fini contains instructions that must be executed to
170
75
  // initialize and finalize the process. They cannot and should not
171
75
  // be merged.
172
75
  return S->Live && (S->Flags & SHF_ALLOC) && 
!(S->Flags & SHF_WRITE)74
&&
173
75
         
S->Name != ".init"73
&&
S->Name != ".fini"72
;
174
75
}
175
176
// Split an equivalence class into smaller classes.
177
template <class ELFT>
178
106
void ICF<ELFT>::segregate(size_t Begin, size_t End, bool Constant) {
179
106
  // This loop rearranges sections in [Begin, End) so that all sections
180
106
  // that are equal in terms of equals{Constant,Variable} are contiguous
181
106
  // in [Begin, End).
182
106
  //
183
106
  // The algorithm is quadratic in the worst case, but that is not an
184
106
  // issue in practice because the number of the distinct sections in
185
106
  // each range is usually very small.
186
106
187
215
  while (Begin < End) {
188
109
    // Divide [Begin, End) into two. Let Mid be the start index of the
189
109
    // second group.
190
109
    auto Bound =
191
109
        std::stable_partition(Sections.begin() + Begin + 1,
192
109
                              Sections.begin() + End, [&](InputSection *S) {
193
40
                                if (Constant)
194
21
                                  return equalsConstant(Sections[Begin], S);
195
19
                                return equalsVariable(Sections[Begin], S);
196
19
                              });
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
192
4
                              Sections.begin() + End, [&](InputSection *S) {
193
4
                                if (Constant)
194
2
                                  return equalsConstant(Sections[Begin], S);
195
2
                                return equalsVariable(Sections[Begin], S);
196
2
                              });
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
192
36
                              Sections.begin() + End, [&](InputSection *S) {
193
36
                                if (Constant)
194
19
                                  return equalsConstant(Sections[Begin], S);
195
17
                                return equalsVariable(Sections[Begin], S);
196
17
                              });
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
197
109
    size_t Mid = Bound - Sections.begin();
198
109
199
109
    // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
200
109
    // updating the sections in [Begin, Mid). We use Mid as an equivalence
201
109
    // class ID because every group ends with a unique index.
202
255
    for (size_t I = Begin; I < Mid; 
++I146
)
203
146
      Sections[I]->Class[Next] = Mid;
204
109
205
109
    // If we created a group, we need to iterate the main loop again.
206
109
    if (Mid != End)
207
3
      Repeat = true;
208
109
209
109
    Begin = Mid;
210
109
  }
211
106
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::segregate(unsigned long, unsigned long, bool)
Line
Count
Source
178
12
void ICF<ELFT>::segregate(size_t Begin, size_t End, bool Constant) {
179
12
  // This loop rearranges sections in [Begin, End) so that all sections
180
12
  // that are equal in terms of equals{Constant,Variable} are contiguous
181
12
  // in [Begin, End).
182
12
  //
183
12
  // The algorithm is quadratic in the worst case, but that is not an
184
12
  // issue in practice because the number of the distinct sections in
185
12
  // each range is usually very small.
186
12
187
24
  while (Begin < End) {
188
12
    // Divide [Begin, End) into two. Let Mid be the start index of the
189
12
    // second group.
190
12
    auto Bound =
191
12
        std::stable_partition(Sections.begin() + Begin + 1,
192
12
                              Sections.begin() + End, [&](InputSection *S) {
193
12
                                if (Constant)
194
12
                                  return equalsConstant(Sections[Begin], S);
195
12
                                return equalsVariable(Sections[Begin], S);
196
12
                              });
197
12
    size_t Mid = Bound - Sections.begin();
198
12
199
12
    // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
200
12
    // updating the sections in [Begin, Mid). We use Mid as an equivalence
201
12
    // class ID because every group ends with a unique index.
202
28
    for (size_t I = Begin; I < Mid; 
++I16
)
203
16
      Sections[I]->Class[Next] = Mid;
204
12
205
12
    // If we created a group, we need to iterate the main loop again.
206
12
    if (Mid != End)
207
0
      Repeat = true;
208
12
209
12
    Begin = Mid;
210
12
  }
211
12
}
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
178
94
void ICF<ELFT>::segregate(size_t Begin, size_t End, bool Constant) {
179
94
  // This loop rearranges sections in [Begin, End) so that all sections
180
94
  // that are equal in terms of equals{Constant,Variable} are contiguous
181
94
  // in [Begin, End).
182
94
  //
183
94
  // The algorithm is quadratic in the worst case, but that is not an
184
94
  // issue in practice because the number of the distinct sections in
185
94
  // each range is usually very small.
186
94
187
191
  while (Begin < End) {
188
97
    // Divide [Begin, End) into two. Let Mid be the start index of the
189
97
    // second group.
190
97
    auto Bound =
191
97
        std::stable_partition(Sections.begin() + Begin + 1,
192
97
                              Sections.begin() + End, [&](InputSection *S) {
193
97
                                if (Constant)
194
97
                                  return equalsConstant(Sections[Begin], S);
195
97
                                return equalsVariable(Sections[Begin], S);
196
97
                              });
197
97
    size_t Mid = Bound - Sections.begin();
198
97
199
97
    // Now we split [Begin, End) into [Begin, Mid) and [Mid, End) by
200
97
    // updating the sections in [Begin, Mid). We use Mid as an equivalence
201
97
    // class ID because every group ends with a unique index.
202
227
    for (size_t I = Begin; I < Mid; 
++I130
)
203
130
      Sections[I]->Class[Next] = Mid;
204
97
205
97
    // If we created a group, we need to iterate the main loop again.
206
97
    if (Mid != End)
207
3
      Repeat = true;
208
97
209
97
    Begin = Mid;
210
97
  }
211
94
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::segregate(unsigned long, unsigned long, bool)
212
213
// Compare two lists of relocations.
214
template <class ELFT>
215
template <class RelTy>
216
bool ICF<ELFT>::constantEq(const InputSection *SecA, ArrayRef<RelTy> RA,
217
21
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
218
21
  if (RA.size() != RB.size())
219
0
    return false;
220
21
221
26
  
for (size_t I = 0; 21
I < RA.size();
++I5
) {
222
7
    if (RA[I].r_offset != RB[I].r_offset ||
223
7
        RA[I].getType(Config->IsMips64EL) != RB[I].getType(Config->IsMips64EL))
224
0
      return false;
225
7
226
7
    uint64_t AddA = getAddend<ELFT>(RA[I]);
227
7
    uint64_t AddB = getAddend<ELFT>(RB[I]);
228
7
229
7
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
230
7
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
231
7
    if (&SA == &SB) {
232
0
      if (AddA == AddB)
233
0
        continue;
234
0
      return false;
235
0
    }
236
7
237
7
    auto *DA = dyn_cast<Defined>(&SA);
238
7
    auto *DB = dyn_cast<Defined>(&SB);
239
7
    if (!DA || !DB)
240
0
      return false;
241
7
242
7
    // Relocations referring to absolute symbols are constant-equal if their
243
7
    // values are equal.
244
7
    if (!DA->Section && 
!DB->Section1
&&
DA->Value + AddA == DB->Value + AddB1
)
245
1
      continue;
246
6
    if (!DA->Section || !DB->Section)
247
0
      return false;
248
6
249
6
    if (DA->Section->kind() != DB->Section->kind())
250
0
      return false;
251
6
252
6
    // Relocations referring to InputSections are constant-equal if their
253
6
    // section offsets are equal.
254
6
    if (isa<InputSection>(DA->Section)) {
255
2
      if (DA->Value + AddA == DB->Value + AddB)
256
2
        continue;
257
0
      return false;
258
0
    }
259
4
260
4
    // Relocations referring to MergeInputSections are constant-equal if their
261
4
    // offsets in the output section are equal.
262
4
    auto *X = dyn_cast<MergeInputSection>(DA->Section);
263
4
    if (!X)
264
0
      return false;
265
4
    auto *Y = cast<MergeInputSection>(DB->Section);
266
4
    if (X->getParent() != Y->getParent())
267
0
      return false;
268
4
269
4
    uint64_t OffsetA =
270
4
        SA.isSection() ? 
X->getOffset(AddA)1
:
X->getOffset(DA->Value) + AddA3
;
271
4
    uint64_t OffsetB =
272
4
        SB.isSection() ? 
Y->getOffset(AddB)1
:
Y->getOffset(DB->Value) + AddB3
;
273
4
    if (OffsetA != OffsetB)
274
2
      return false;
275
4
  }
276
21
277
21
  
return true19
;
278
21
}
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
217
2
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
218
2
  if (RA.size() != RB.size())
219
0
    return false;
220
2
221
2
  for (size_t I = 0; I < RA.size(); 
++I0
) {
222
0
    if (RA[I].r_offset != RB[I].r_offset ||
223
0
        RA[I].getType(Config->IsMips64EL) != RB[I].getType(Config->IsMips64EL))
224
0
      return false;
225
0
226
0
    uint64_t AddA = getAddend<ELFT>(RA[I]);
227
0
    uint64_t AddB = getAddend<ELFT>(RB[I]);
228
0
229
0
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
230
0
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
231
0
    if (&SA == &SB) {
232
0
      if (AddA == AddB)
233
0
        continue;
234
0
      return false;
235
0
    }
236
0
237
0
    auto *DA = dyn_cast<Defined>(&SA);
238
0
    auto *DB = dyn_cast<Defined>(&SB);
239
0
    if (!DA || !DB)
240
0
      return false;
241
0
242
0
    // Relocations referring to absolute symbols are constant-equal if their
243
0
    // values are equal.
244
0
    if (!DA->Section && !DB->Section && DA->Value + AddA == DB->Value + AddB)
245
0
      continue;
246
0
    if (!DA->Section || !DB->Section)
247
0
      return false;
248
0
249
0
    if (DA->Section->kind() != DB->Section->kind())
250
0
      return false;
251
0
252
0
    // Relocations referring to InputSections are constant-equal if their
253
0
    // section offsets are equal.
254
0
    if (isa<InputSection>(DA->Section)) {
255
0
      if (DA->Value + AddA == DB->Value + AddB)
256
0
        continue;
257
0
      return false;
258
0
    }
259
0
260
0
    // Relocations referring to MergeInputSections are constant-equal if their
261
0
    // offsets in the output section are equal.
262
0
    auto *X = dyn_cast<MergeInputSection>(DA->Section);
263
0
    if (!X)
264
0
      return false;
265
0
    auto *Y = cast<MergeInputSection>(DB->Section);
266
0
    if (X->getParent() != Y->getParent())
267
0
      return false;
268
0
269
0
    uint64_t OffsetA =
270
0
        SA.isSection() ? X->getOffset(AddA) : X->getOffset(DA->Value) + AddA;
271
0
    uint64_t OffsetB =
272
0
        SB.isSection() ? Y->getOffset(AddB) : Y->getOffset(DB->Value) + AddB;
273
0
    if (OffsetA != OffsetB)
274
0
      return false;
275
0
  }
276
2
277
2
  return true;
278
2
}
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
217
7
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
218
7
  if (RA.size() != RB.size())
219
0
    return false;
220
7
221
12
  
for (size_t I = 0; 7
I < RA.size();
++I5
) {
222
7
    if (RA[I].r_offset != RB[I].r_offset ||
223
7
        RA[I].getType(Config->IsMips64EL) != RB[I].getType(Config->IsMips64EL))
224
0
      return false;
225
7
226
7
    uint64_t AddA = getAddend<ELFT>(RA[I]);
227
7
    uint64_t AddB = getAddend<ELFT>(RB[I]);
228
7
229
7
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
230
7
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
231
7
    if (&SA == &SB) {
232
0
      if (AddA == AddB)
233
0
        continue;
234
0
      return false;
235
0
    }
236
7
237
7
    auto *DA = dyn_cast<Defined>(&SA);
238
7
    auto *DB = dyn_cast<Defined>(&SB);
239
7
    if (!DA || !DB)
240
0
      return false;
241
7
242
7
    // Relocations referring to absolute symbols are constant-equal if their
243
7
    // values are equal.
244
7
    if (!DA->Section && 
!DB->Section1
&&
DA->Value + AddA == DB->Value + AddB1
)
245
1
      continue;
246
6
    if (!DA->Section || !DB->Section)
247
0
      return false;
248
6
249
6
    if (DA->Section->kind() != DB->Section->kind())
250
0
      return false;
251
6
252
6
    // Relocations referring to InputSections are constant-equal if their
253
6
    // section offsets are equal.
254
6
    if (isa<InputSection>(DA->Section)) {
255
2
      if (DA->Value + AddA == DB->Value + AddB)
256
2
        continue;
257
0
      return false;
258
0
    }
259
4
260
4
    // Relocations referring to MergeInputSections are constant-equal if their
261
4
    // offsets in the output section are equal.
262
4
    auto *X = dyn_cast<MergeInputSection>(DA->Section);
263
4
    if (!X)
264
0
      return false;
265
4
    auto *Y = cast<MergeInputSection>(DB->Section);
266
4
    if (X->getParent() != Y->getParent())
267
0
      return false;
268
4
269
4
    uint64_t OffsetA =
270
4
        SA.isSection() ? 
X->getOffset(AddA)1
:
X->getOffset(DA->Value) + AddA3
;
271
4
    uint64_t OffsetB =
272
4
        SB.isSection() ? 
Y->getOffset(AddB)1
:
Y->getOffset(DB->Value) + AddB3
;
273
4
    if (OffsetA != OffsetB)
274
2
      return false;
275
4
  }
276
7
277
7
  
return true5
;
278
7
}
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
217
12
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
218
12
  if (RA.size() != RB.size())
219
0
    return false;
220
12
221
12
  for (size_t I = 0; I < RA.size(); 
++I0
) {
222
0
    if (RA[I].r_offset != RB[I].r_offset ||
223
0
        RA[I].getType(Config->IsMips64EL) != RB[I].getType(Config->IsMips64EL))
224
0
      return false;
225
0
226
0
    uint64_t AddA = getAddend<ELFT>(RA[I]);
227
0
    uint64_t AddB = getAddend<ELFT>(RB[I]);
228
0
229
0
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
230
0
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
231
0
    if (&SA == &SB) {
232
0
      if (AddA == AddB)
233
0
        continue;
234
0
      return false;
235
0
    }
236
0
237
0
    auto *DA = dyn_cast<Defined>(&SA);
238
0
    auto *DB = dyn_cast<Defined>(&SB);
239
0
    if (!DA || !DB)
240
0
      return false;
241
0
242
0
    // Relocations referring to absolute symbols are constant-equal if their
243
0
    // values are equal.
244
0
    if (!DA->Section && !DB->Section && DA->Value + AddA == DB->Value + AddB)
245
0
      continue;
246
0
    if (!DA->Section || !DB->Section)
247
0
      return false;
248
0
249
0
    if (DA->Section->kind() != DB->Section->kind())
250
0
      return false;
251
0
252
0
    // Relocations referring to InputSections are constant-equal if their
253
0
    // section offsets are equal.
254
0
    if (isa<InputSection>(DA->Section)) {
255
0
      if (DA->Value + AddA == DB->Value + AddB)
256
0
        continue;
257
0
      return false;
258
0
    }
259
0
260
0
    // Relocations referring to MergeInputSections are constant-equal if their
261
0
    // offsets in the output section are equal.
262
0
    auto *X = dyn_cast<MergeInputSection>(DA->Section);
263
0
    if (!X)
264
0
      return false;
265
0
    auto *Y = cast<MergeInputSection>(DB->Section);
266
0
    if (X->getParent() != Y->getParent())
267
0
      return false;
268
0
269
0
    uint64_t OffsetA =
270
0
        SA.isSection() ? X->getOffset(AddA) : X->getOffset(DA->Value) + AddA;
271
0
    uint64_t OffsetB =
272
0
        SB.isSection() ? Y->getOffset(AddB) : Y->getOffset(DB->Value) + AddB;
273
0
    if (OffsetA != OffsetB)
274
0
      return false;
275
0
  }
276
12
277
12
  return true;
278
12
}
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> >)
279
280
// Compare "non-moving" part of two InputSections, namely everything
281
// except relocation targets.
282
template <class ELFT>
283
21
bool ICF<ELFT>::equalsConstant(const InputSection *A, const InputSection *B) {
284
21
  if (A->NumRelocations != B->NumRelocations || A->Flags != B->Flags ||
285
21
      A->getSize() != B->getSize() || A->Data != B->Data)
286
0
    return false;
287
21
288
21
  if (A->AreRelocsRela)
289
7
    return constantEq(A, A->template relas<ELFT>(), B,
290
7
                      B->template relas<ELFT>());
291
14
  return constantEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
292
14
}
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
283
2
bool ICF<ELFT>::equalsConstant(const InputSection *A, const InputSection *B) {
284
2
  if (A->NumRelocations != B->NumRelocations || A->Flags != B->Flags ||
285
2
      A->getSize() != B->getSize() || A->Data != B->Data)
286
0
    return false;
287
2
288
2
  if (A->AreRelocsRela)
289
0
    return constantEq(A, A->template relas<ELFT>(), B,
290
0
                      B->template relas<ELFT>());
291
2
  return constantEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
292
2
}
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
283
19
bool ICF<ELFT>::equalsConstant(const InputSection *A, const InputSection *B) {
284
19
  if (A->NumRelocations != B->NumRelocations || A->Flags != B->Flags ||
285
19
      A->getSize() != B->getSize() || A->Data != B->Data)
286
0
    return false;
287
19
288
19
  if (A->AreRelocsRela)
289
7
    return constantEq(A, A->template relas<ELFT>(), B,
290
7
                      B->template relas<ELFT>());
291
12
  return constantEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
292
12
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::equalsConstant(lld::elf::InputSection const*, lld::elf::InputSection const*)
293
294
// Compare two lists of relocations. Returns true if all pairs of
295
// relocations point to the same section in terms of ICF.
296
template <class ELFT>
297
template <class RelTy>
298
bool ICF<ELFT>::variableEq(const InputSection *SecA, ArrayRef<RelTy> RA,
299
19
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
300
19
  assert(RA.size() == RB.size());
301
19
302
23
  for (size_t I = 0; I < RA.size(); 
++I4
) {
303
5
    // The two sections must be identical.
304
5
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
305
5
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
306
5
    if (&SA == &SB)
307
0
      continue;
308
5
309
5
    auto *DA = cast<Defined>(&SA);
310
5
    auto *DB = cast<Defined>(&SB);
311
5
312
5
    // We already dealt with absolute and non-InputSection symbols in
313
5
    // constantEq, and for InputSections we have already checked everything
314
5
    // except the equivalence class.
315
5
    if (!DA->Section)
316
1
      continue;
317
4
    auto *X = dyn_cast<InputSection>(DA->Section);
318
4
    if (!X)
319
2
      continue;
320
2
    auto *Y = cast<InputSection>(DB->Section);
321
2
322
2
    // Ineligible sections are in the special equivalence class 0.
323
2
    // They can never be the same in terms of the equivalence class.
324
2
    if (X->Class[Current] == 0)
325
1
      return false;
326
1
    if (X->Class[Current] != Y->Class[Current])
327
0
      return false;
328
18
  };
329
18
330
18
  return true;
331
19
}
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
299
2
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
300
2
  assert(RA.size() == RB.size());
301
2
302
2
  for (size_t I = 0; I < RA.size(); 
++I0
) {
303
0
    // The two sections must be identical.
304
0
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
305
0
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
306
0
    if (&SA == &SB)
307
0
      continue;
308
0
309
0
    auto *DA = cast<Defined>(&SA);
310
0
    auto *DB = cast<Defined>(&SB);
311
0
312
0
    // We already dealt with absolute and non-InputSection symbols in
313
0
    // constantEq, and for InputSections we have already checked everything
314
0
    // except the equivalence class.
315
0
    if (!DA->Section)
316
0
      continue;
317
0
    auto *X = dyn_cast<InputSection>(DA->Section);
318
0
    if (!X)
319
0
      continue;
320
0
    auto *Y = cast<InputSection>(DB->Section);
321
0
322
0
    // Ineligible sections are in the special equivalence class 0.
323
0
    // They can never be the same in terms of the equivalence class.
324
0
    if (X->Class[Current] == 0)
325
0
      return false;
326
0
    if (X->Class[Current] != Y->Class[Current])
327
0
      return false;
328
2
  };
329
2
330
2
  return true;
331
2
}
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
299
5
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
300
5
  assert(RA.size() == RB.size());
301
5
302
9
  for (size_t I = 0; I < RA.size(); 
++I4
) {
303
5
    // The two sections must be identical.
304
5
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
305
5
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
306
5
    if (&SA == &SB)
307
0
      continue;
308
5
309
5
    auto *DA = cast<Defined>(&SA);
310
5
    auto *DB = cast<Defined>(&SB);
311
5
312
5
    // We already dealt with absolute and non-InputSection symbols in
313
5
    // constantEq, and for InputSections we have already checked everything
314
5
    // except the equivalence class.
315
5
    if (!DA->Section)
316
1
      continue;
317
4
    auto *X = dyn_cast<InputSection>(DA->Section);
318
4
    if (!X)
319
2
      continue;
320
2
    auto *Y = cast<InputSection>(DB->Section);
321
2
322
2
    // Ineligible sections are in the special equivalence class 0.
323
2
    // They can never be the same in terms of the equivalence class.
324
2
    if (X->Class[Current] == 0)
325
1
      return false;
326
1
    if (X->Class[Current] != Y->Class[Current])
327
0
      return false;
328
4
  };
329
4
330
4
  return true;
331
5
}
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
299
12
                           const InputSection *SecB, ArrayRef<RelTy> RB) {
300
12
  assert(RA.size() == RB.size());
301
12
302
12
  for (size_t I = 0; I < RA.size(); 
++I0
) {
303
0
    // The two sections must be identical.
304
0
    Symbol &SA = SecA->template getFile<ELFT>()->getRelocTargetSym(RA[I]);
305
0
    Symbol &SB = SecB->template getFile<ELFT>()->getRelocTargetSym(RB[I]);
306
0
    if (&SA == &SB)
307
0
      continue;
308
0
309
0
    auto *DA = cast<Defined>(&SA);
310
0
    auto *DB = cast<Defined>(&SB);
311
0
312
0
    // We already dealt with absolute and non-InputSection symbols in
313
0
    // constantEq, and for InputSections we have already checked everything
314
0
    // except the equivalence class.
315
0
    if (!DA->Section)
316
0
      continue;
317
0
    auto *X = dyn_cast<InputSection>(DA->Section);
318
0
    if (!X)
319
0
      continue;
320
0
    auto *Y = cast<InputSection>(DB->Section);
321
0
322
0
    // Ineligible sections are in the special equivalence class 0.
323
0
    // They can never be the same in terms of the equivalence class.
324
0
    if (X->Class[Current] == 0)
325
0
      return false;
326
0
    if (X->Class[Current] != Y->Class[Current])
327
0
      return false;
328
12
  };
329
12
330
12
  return true;
331
12
}
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> >)
332
333
// Compare "moving" part of two InputSections, namely relocation targets.
334
template <class ELFT>
335
19
bool ICF<ELFT>::equalsVariable(const InputSection *A, const InputSection *B) {
336
19
  if (A->AreRelocsRela)
337
5
    return variableEq(A, A->template relas<ELFT>(), B,
338
5
                      B->template relas<ELFT>());
339
14
  return variableEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
340
14
}
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
335
2
bool ICF<ELFT>::equalsVariable(const InputSection *A, const InputSection *B) {
336
2
  if (A->AreRelocsRela)
337
0
    return variableEq(A, A->template relas<ELFT>(), B,
338
0
                      B->template relas<ELFT>());
339
2
  return variableEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
340
2
}
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
335
17
bool ICF<ELFT>::equalsVariable(const InputSection *A, const InputSection *B) {
336
17
  if (A->AreRelocsRela)
337
5
    return variableEq(A, A->template relas<ELFT>(), B,
338
5
                      B->template relas<ELFT>());
339
12
  return variableEq(A, A->template rels<ELFT>(), B, B->template rels<ELFT>());
340
12
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::equalsVariable(lld::elf::InputSection const*, lld::elf::InputSection const*)
341
342
159
template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t Begin, size_t End) {
343
159
  uint32_t Class = Sections[Begin]->Class[Current];
344
217
  for (size_t I = Begin + 1; I < End; 
++I58
)
345
150
    if (Class != Sections[I]->Class[Current])
346
92
      return I;
347
159
  
return End67
;
348
159
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::findBoundary(unsigned long, unsigned long)
Line
Count
Source
342
18
template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t Begin, size_t End) {
343
18
  uint32_t Class = Sections[Begin]->Class[Current];
344
24
  for (size_t I = Begin + 1; I < End; 
++I6
)
345
18
    if (Class != Sections[I]->Class[Current])
346
12
      return I;
347
18
  
return End6
;
348
18
}
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
342
141
template <class ELFT> size_t ICF<ELFT>::findBoundary(size_t Begin, size_t End) {
343
141
  uint32_t Class = Sections[Begin]->Class[Current];
344
193
  for (size_t I = Begin + 1; I < End; 
++I52
)
345
132
    if (Class != Sections[I]->Class[Current])
346
80
      return I;
347
141
  
return End61
;
348
141
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::findBoundary(unsigned long, unsigned long)
349
350
// Sections in the same equivalence class are contiguous in Sections
351
// vector. Therefore, Sections vector can be considered as contiguous
352
// groups of sections, grouped by the class.
353
//
354
// This function calls Fn on every group that starts within [Begin, End).
355
// Note that a group must start in that range but doesn't necessarily
356
// have to end before End.
357
template <class ELFT>
358
void ICF<ELFT>::forEachClassRange(size_t Begin, size_t End,
359
67
                                  std::function<void(size_t, size_t)> Fn) {
360
67
  if (Begin > 0)
361
0
    Begin = findBoundary(Begin - 1, End);
362
67
363
226
  while (Begin < End) {
364
159
    size_t Mid = findBoundary(Begin, Sections.size());
365
159
    Fn(Begin, Mid);
366
159
    Begin = Mid;
367
159
  }
368
67
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::forEachClassRange(unsigned long, unsigned long, std::__1::function<void (unsigned long, unsigned long)>)
Line
Count
Source
359
6
                                  std::function<void(size_t, size_t)> Fn) {
360
6
  if (Begin > 0)
361
0
    Begin = findBoundary(Begin - 1, End);
362
6
363
24
  while (Begin < End) {
364
18
    size_t Mid = findBoundary(Begin, Sections.size());
365
18
    Fn(Begin, Mid);
366
18
    Begin = Mid;
367
18
  }
368
6
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::forEachClassRange(unsigned long, unsigned long, std::__1::function<void (unsigned long, unsigned long)>)
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::forEachClassRange(unsigned long, unsigned long, std::__1::function<void (unsigned long, unsigned long)>)
Line
Count
Source
359
61
                                  std::function<void(size_t, size_t)> Fn) {
360
61
  if (Begin > 0)
361
0
    Begin = findBoundary(Begin - 1, End);
362
61
363
202
  while (Begin < End) {
364
141
    size_t Mid = findBoundary(Begin, Sections.size());
365
141
    Fn(Begin, Mid);
366
141
    Begin = Mid;
367
141
  }
368
61
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::forEachClassRange(unsigned long, unsigned long, std::__1::function<void (unsigned long, unsigned long)>)
369
370
// Call Fn on each equivalence class.
371
template <class ELFT>
372
67
void ICF<ELFT>::forEachClass(std::function<void(size_t, size_t)> Fn) {
373
67
  // If threading is disabled or the number of sections are
374
67
  // too small to use threading, call Fn sequentially.
375
67
  if (!ThreadsEnabled || Sections.size() < 1024) {
376
67
    forEachClassRange(0, Sections.size(), Fn);
377
67
    ++Cnt;
378
67
    return;
379
67
  }
380
0
381
0
  Current = Cnt % 2;
382
0
  Next = (Cnt + 1) % 2;
383
0
384
0
  // Split sections into 256 shards and call Fn in parallel.
385
0
  size_t NumShards = 256;
386
0
  size_t Step = Sections.size() / NumShards;
387
0
  parallelForEachN(0, NumShards, [&](size_t I) {
388
0
    size_t End = (I == NumShards - 1) ? Sections.size() : (I + 1) * Step;
389
0
    forEachClassRange(I * Step, End, Fn);
390
0
  });
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::forEachClass(std::__1::function<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(std::__1::function<void (unsigned long, unsigned long)>)::'lambda'(unsigned long)::operator()(unsigned long) const
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::forEachClass(std::__1::function<void (unsigned long, unsigned long)>)::'lambda'(unsigned long)::operator()(unsigned long) const
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::forEachClass(std::__1::function<void (unsigned long, unsigned long)>)::'lambda'(unsigned long)::operator()(unsigned long) const
391
0
  ++Cnt;
392
0
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::forEachClass(std::__1::function<void (unsigned long, unsigned long)>)
Line
Count
Source
372
6
void ICF<ELFT>::forEachClass(std::function<void(size_t, size_t)> Fn) {
373
6
  // If threading is disabled or the number of sections are
374
6
  // too small to use threading, call Fn sequentially.
375
6
  if (!ThreadsEnabled || Sections.size() < 1024) {
376
6
    forEachClassRange(0, Sections.size(), Fn);
377
6
    ++Cnt;
378
6
    return;
379
6
  }
380
0
381
0
  Current = Cnt % 2;
382
0
  Next = (Cnt + 1) % 2;
383
0
384
0
  // Split sections into 256 shards and call Fn in parallel.
385
0
  size_t NumShards = 256;
386
0
  size_t Step = Sections.size() / NumShards;
387
0
  parallelForEachN(0, NumShards, [&](size_t I) {
388
0
    size_t End = (I == NumShards - 1) ? Sections.size() : (I + 1) * Step;
389
0
    forEachClassRange(I * Step, End, Fn);
390
0
  });
391
0
  ++Cnt;
392
0
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, false> >::forEachClass(std::__1::function<void (unsigned long, unsigned long)>)
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, true> >::forEachClass(std::__1::function<void (unsigned long, unsigned long)>)
Line
Count
Source
372
61
void ICF<ELFT>::forEachClass(std::function<void(size_t, size_t)> Fn) {
373
61
  // If threading is disabled or the number of sections are
374
61
  // too small to use threading, call Fn sequentially.
375
61
  if (!ThreadsEnabled || Sections.size() < 1024) {
376
61
    forEachClassRange(0, Sections.size(), Fn);
377
61
    ++Cnt;
378
61
    return;
379
61
  }
380
0
381
0
  Current = Cnt % 2;
382
0
  Next = (Cnt + 1) % 2;
383
0
384
0
  // Split sections into 256 shards and call Fn in parallel.
385
0
  size_t NumShards = 256;
386
0
  size_t Step = Sections.size() / NumShards;
387
0
  parallelForEachN(0, NumShards, [&](size_t I) {
388
0
    size_t End = (I == NumShards - 1) ? Sections.size() : (I + 1) * Step;
389
0
    forEachClassRange(I * Step, End, Fn);
390
0
  });
391
0
  ++Cnt;
392
0
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::forEachClass(std::__1::function<void (unsigned long, unsigned long)>)
393
394
// The main function of ICF.
395
22
template <class ELFT> void ICF<ELFT>::run() {
396
22
  // Collect sections to merge.
397
22
  for (InputSectionBase *Sec : InputSections)
398
108
    if (auto *S = dyn_cast<InputSection>(Sec))
399
106
      if (isEligible(S))
400
71
        Sections.push_back(S);
401
22
402
22
  // Initially, we use hash values to partition sections.
403
71
  parallelForEach(Sections, [&](InputSection *S) {
404
71
    // Set MSB to 1 to avoid collisions with non-hash IDs.
405
71
    S->Class[0] = getHash<ELFT>(S) | (1 << 31);
406
71
  });
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
403
8
  parallelForEach(Sections, [&](InputSection *S) {
404
8
    // Set MSB to 1 to avoid collisions with non-hash IDs.
405
8
    S->Class[0] = getHash<ELFT>(S) | (1 << 31);
406
8
  });
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
403
63
  parallelForEach(Sections, [&](InputSection *S) {
404
63
    // Set MSB to 1 to avoid collisions with non-hash IDs.
405
63
    S->Class[0] = getHash<ELFT>(S) | (1 << 31);
406
63
  });
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
407
22
408
22
  // From now on, sections in Sections vector are ordered so that sections
409
22
  // in the same equivalence class are consecutive in the vector.
410
22
  std::stable_sort(Sections.begin(), Sections.end(),
411
70
                   [](InputSection *A, InputSection *B) {
412
70
                     return A->Class[0] < B->Class[0];
413
70
                   });
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
411
10
                   [](InputSection *A, InputSection *B) {
412
10
                     return A->Class[0] < B->Class[0];
413
10
                   });
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
411
60
                   [](InputSection *A, InputSection *B) {
412
60
                     return A->Class[0] < B->Class[0];
413
60
                   });
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
414
22
415
22
  // Compare static contents and assign unique IDs for each static content.
416
50
  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
416
6
  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
416
44
  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
417
22
418
22
  // Split groups by comparing relocations until convergence is obtained.
419
23
  do {
420
23
    Repeat = false;
421
23
    forEachClass(
422
56
        [&](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
422
6
        [&](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
422
50
        [&](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
423
23
  } while (Repeat);
424
22
425
22
  log("ICF needed " + Twine(Cnt) + " iterations");
426
22
427
22
  // Merge sections by the equivalence class.
428
53
  forEachClass([&](size_t Begin, size_t End) {
429
53
    if (End - Begin == 1)
430
35
      return;
431
18
432
18
    log("selected " + Sections[Begin]->Name);
433
36
    for (size_t I = Begin + 1; I < End; 
++I18
) {
434
18
      log("  removed " + Sections[I]->Name);
435
18
      Sections[Begin]->replace(Sections[I]);
436
18
    }
437
18
  });
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
428
6
  forEachClass([&](size_t Begin, size_t End) {
429
6
    if (End - Begin == 1)
430
4
      return;
431
2
432
2
    log("selected " + Sections[Begin]->Name);
433
4
    for (size_t I = Begin + 1; I < End; 
++I2
) {
434
2
      log("  removed " + Sections[I]->Name);
435
2
      Sections[Begin]->replace(Sections[I]);
436
2
    }
437
2
  });
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
428
47
  forEachClass([&](size_t Begin, size_t End) {
429
47
    if (End - Begin == 1)
430
31
      return;
431
16
432
16
    log("selected " + Sections[Begin]->Name);
433
32
    for (size_t I = Begin + 1; I < End; 
++I16
) {
434
16
      log("  removed " + Sections[I]->Name);
435
16
      Sections[Begin]->replace(Sections[I]);
436
16
    }
437
16
  });
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
438
22
439
22
  // Mark ARM Exception Index table sections that refer to folded code
440
22
  // sections as not live. These sections have an implict dependency
441
22
  // via the link order dependency.
442
22
  if (Config->EMachine == EM_ARM)
443
1
    for (InputSectionBase *Sec : InputSections)
444
7
      if (auto *S = dyn_cast<InputSection>(Sec))
445
7
        if (S->Flags & SHF_LINK_ORDER)
446
2
          S->Live = S->getLinkOrderDep()->Live;
447
22
}
ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)1, false> >::run()
Line
Count
Source
395
2
template <class ELFT> void ICF<ELFT>::run() {
396
2
  // Collect sections to merge.
397
2
  for (InputSectionBase *Sec : InputSections)
398
12
    if (auto *S = dyn_cast<InputSection>(Sec))
399
12
      if (isEligible(S))
400
8
        Sections.push_back(S);
401
2
402
2
  // Initially, we use hash values to partition sections.
403
2
  parallelForEach(Sections, [&](InputSection *S) {
404
2
    // Set MSB to 1 to avoid collisions with non-hash IDs.
405
2
    S->Class[0] = getHash<ELFT>(S) | (1 << 31);
406
2
  });
407
2
408
2
  // From now on, sections in Sections vector are ordered so that sections
409
2
  // in the same equivalence class are consecutive in the vector.
410
2
  std::stable_sort(Sections.begin(), Sections.end(),
411
2
                   [](InputSection *A, InputSection *B) {
412
2
                     return A->Class[0] < B->Class[0];
413
2
                   });
414
2
415
2
  // Compare static contents and assign unique IDs for each static content.
416
2
  forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
417
2
418
2
  // Split groups by comparing relocations until convergence is obtained.
419
2
  do {
420
2
    Repeat = false;
421
2
    forEachClass(
422
2
        [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
423
2
  } while (Repeat);
424
2
425
2
  log("ICF needed " + Twine(Cnt) + " iterations");
426
2
427
2
  // Merge sections by the equivalence class.
428
2
  forEachClass([&](size_t Begin, size_t End) {
429
2
    if (End - Begin == 1)
430
2
      return;
431
2
432
2
    log("selected " + Sections[Begin]->Name);
433
2
    for (size_t I = Begin + 1; I < End; ++I) {
434
2
      log("  removed " + Sections[I]->Name);
435
2
      Sections[Begin]->replace(Sections[I]);
436
2
    }
437
2
  });
438
2
439
2
  // Mark ARM Exception Index table sections that refer to folded code
440
2
  // sections as not live. These sections have an implict dependency
441
2
  // via the link order dependency.
442
2
  if (Config->EMachine == EM_ARM)
443
1
    for (InputSectionBase *Sec : InputSections)
444
7
      if (auto *S = dyn_cast<InputSection>(Sec))
445
7
        if (S->Flags & SHF_LINK_ORDER)
446
2
          S->Live = S->getLinkOrderDep()->Live;
447
2
}
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
395
20
template <class ELFT> void ICF<ELFT>::run() {
396
20
  // Collect sections to merge.
397
20
  for (InputSectionBase *Sec : InputSections)
398
96
    if (auto *S = dyn_cast<InputSection>(Sec))
399
94
      if (isEligible(S))
400
63
        Sections.push_back(S);
401
20
402
20
  // Initially, we use hash values to partition sections.
403
20
  parallelForEach(Sections, [&](InputSection *S) {
404
20
    // Set MSB to 1 to avoid collisions with non-hash IDs.
405
20
    S->Class[0] = getHash<ELFT>(S) | (1 << 31);
406
20
  });
407
20
408
20
  // From now on, sections in Sections vector are ordered so that sections
409
20
  // in the same equivalence class are consecutive in the vector.
410
20
  std::stable_sort(Sections.begin(), Sections.end(),
411
20
                   [](InputSection *A, InputSection *B) {
412
20
                     return A->Class[0] < B->Class[0];
413
20
                   });
414
20
415
20
  // Compare static contents and assign unique IDs for each static content.
416
20
  forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
417
20
418
20
  // Split groups by comparing relocations until convergence is obtained.
419
21
  do {
420
21
    Repeat = false;
421
21
    forEachClass(
422
21
        [&](size_t Begin, size_t End) { segregate(Begin, End, false); });
423
21
  } while (Repeat);
424
20
425
20
  log("ICF needed " + Twine(Cnt) + " iterations");
426
20
427
20
  // Merge sections by the equivalence class.
428
20
  forEachClass([&](size_t Begin, size_t End) {
429
20
    if (End - Begin == 1)
430
20
      return;
431
20
432
20
    log("selected " + Sections[Begin]->Name);
433
20
    for (size_t I = Begin + 1; I < End; ++I) {
434
20
      log("  removed " + Sections[I]->Name);
435
20
      Sections[Begin]->replace(Sections[I]);
436
20
    }
437
20
  });
438
20
439
20
  // Mark ARM Exception Index table sections that refer to folded code
440
20
  // sections as not live. These sections have an implict dependency
441
20
  // via the link order dependency.
442
20
  if (Config->EMachine == EM_ARM)
443
0
    for (InputSectionBase *Sec : InputSections)
444
0
      if (auto *S = dyn_cast<InputSection>(Sec))
445
0
        if (S->Flags & SHF_LINK_ORDER)
446
0
          S->Live = S->getLinkOrderDep()->Live;
447
20
}
Unexecuted instantiation: ICF.cpp:(anonymous namespace)::ICF<llvm::object::ELFType<(llvm::support::endianness)0, true> >::run()
448
449
// ICF entry point function.
450
22
template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
void lld::elf::doIcf<llvm::object::ELFType<(llvm::support::endianness)1, false> >()
Line
Count
Source
450
2
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
450
20
template <class ELFT> void elf::doIcf() { ICF<ELFT>().run(); }
Unexecuted instantiation: void lld::elf::doIcf<llvm::object::ELFType<(llvm::support::endianness)0, true> >()
451
452
template void elf::doIcf<ELF32LE>();
453
template void elf::doIcf<ELF32BE>();
454
template void elf::doIcf<ELF64LE>();
455
template void elf::doIcf<ELF64BE>();