Coverage Report

Created: 2017-09-21 03:39

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