Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/lld/lib/Core/SymbolTable.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- Core/SymbolTable.cpp - Main Symbol Table ---------------------------===//
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
#include "lld/Core/SymbolTable.h"
11
#include "lld/Core/AbsoluteAtom.h"
12
#include "lld/Core/Atom.h"
13
#include "lld/Core/DefinedAtom.h"
14
#include "lld/Core/File.h"
15
#include "lld/Core/LLVM.h"
16
#include "lld/Core/LinkingContext.h"
17
#include "lld/Core/Resolver.h"
18
#include "lld/Core/SharedLibraryAtom.h"
19
#include "lld/Core/UndefinedAtom.h"
20
#include "llvm/ADT/ArrayRef.h"
21
#include "llvm/ADT/DenseMapInfo.h"
22
#include "llvm/ADT/Hashing.h"
23
#include "llvm/Support/ErrorHandling.h"
24
#include "llvm/Support/raw_ostream.h"
25
#include <algorithm>
26
#include <cassert>
27
#include <cstdlib>
28
#include <vector>
29
30
namespace lld {
31
337
bool SymbolTable::add(const UndefinedAtom &atom) { return addByName(atom); }
32
33
142
bool SymbolTable::add(const SharedLibraryAtom &atom) { return addByName(atom); }
34
35
0
bool SymbolTable::add(const AbsoluteAtom &atom) { return addByName(atom); }
36
37
752
bool SymbolTable::add(const DefinedAtom &atom) {
38
752
  if (!atom.name().empty() &&
39
752
      
atom.scope() != DefinedAtom::scopeTranslationUnit585
) {
40
487
    // Named atoms cannot be merged by content.
41
487
    assert(atom.merge() != DefinedAtom::mergeByContent);
42
487
    // Track named atoms that are not scoped to file (static).
43
487
    return addByName(atom);
44
487
  }
45
265
  
if (265
atom.merge() == DefinedAtom::mergeByContent265
) {
46
48
    // Named atoms cannot be merged by content.
47
48
    assert(atom.name().empty());
48
48
    // Currently only read-only constants can be merged.
49
48
    if (atom.permissions() == DefinedAtom::permR__)
50
36
      return addByContent(atom);
51
229
    // TODO: support mergeByContent of data atoms by comparing content & fixups.
52
229
  }
53
229
  return false;
54
229
}
55
56
enum NameCollisionResolution {
57
  NCR_First,
58
  NCR_Second,
59
  NCR_DupDef,
60
  NCR_DupUndef,
61
  NCR_DupShLib,
62
  NCR_Error
63
};
64
65
static NameCollisionResolution cases[4][4] = {
66
  //regular     absolute    undef      sharedLib
67
  {
68
    // first is regular
69
    NCR_DupDef, NCR_Error,   NCR_First, NCR_First
70
  },
71
  {
72
    // first is absolute
73
    NCR_Error,  NCR_Error,  NCR_First, NCR_First
74
  },
75
  {
76
    // first is undef
77
    NCR_Second, NCR_Second, NCR_DupUndef, NCR_Second
78
  },
79
  {
80
    // first is sharedLib
81
    NCR_Second, NCR_Second, NCR_First, NCR_DupShLib
82
  }
83
};
84
85
static NameCollisionResolution collide(Atom::Definition first,
86
283
                                       Atom::Definition second) {
87
283
  return cases[first][second];
88
283
}
89
90
enum MergeResolution {
91
  MCR_First,
92
  MCR_Second,
93
  MCR_Largest,
94
  MCR_SameSize,
95
  MCR_Error
96
};
97
98
static MergeResolution mergeCases[][6] = {
99
  // no          tentative      weak          weakAddress   sameNameAndSize largest
100
  {MCR_Error,    MCR_First,     MCR_First,    MCR_First,    MCR_SameSize,   MCR_Largest},  // no
101
  {MCR_Second,   MCR_Largest,   MCR_Second,   MCR_Second,   MCR_SameSize,   MCR_Largest},  // tentative
102
  {MCR_Second,   MCR_First,     MCR_First,    MCR_Second,   MCR_SameSize,   MCR_Largest},  // weak
103
  {MCR_Second,   MCR_First,     MCR_First,    MCR_First,    MCR_SameSize,   MCR_Largest},  // weakAddress
104
  {MCR_SameSize, MCR_SameSize,  MCR_SameSize, MCR_SameSize, MCR_SameSize,   MCR_SameSize}, // sameSize
105
  {MCR_Largest,  MCR_Largest,   MCR_Largest,  MCR_Largest,  MCR_SameSize,   MCR_Largest},  // largest
106
};
107
108
static MergeResolution mergeSelect(DefinedAtom::Merge first,
109
0
                                   DefinedAtom::Merge second) {
110
0
  assert(first != DefinedAtom::mergeByContent);
111
0
  assert(second != DefinedAtom::mergeByContent);
112
0
  return mergeCases[first][second];
113
0
}
114
115
966
bool SymbolTable::addByName(const Atom &newAtom) {
116
966
  StringRef name = newAtom.name();
117
966
  assert(!name.empty());
118
966
  const Atom *existing = findByName(name);
119
966
  if (
existing == nullptr966
) {
120
683
    // Name is not in symbol table yet, add it associate with this atom.
121
683
    _nameTable[name] = &newAtom;
122
683
    return true;
123
683
  }
124
283
125
283
  // Do nothing if the same object is added more than once.
126
283
  
if (283
existing == &newAtom283
)
127
0
    return false;
128
283
129
283
  // Name is already in symbol table and associated with another atom.
130
283
  bool useNew = true;
131
283
  switch (collide(existing->definition(), newAtom.definition())) {
132
11
  case NCR_First:
133
11
    useNew = false;
134
11
    break;
135
218
  case NCR_Second:
136
218
    useNew = true;
137
218
    break;
138
0
  case NCR_DupDef: {
139
0
    const auto *existingDef = cast<DefinedAtom>(existing);
140
0
    const auto *newDef = cast<DefinedAtom>(&newAtom);
141
0
    switch (mergeSelect(existingDef->merge(), newDef->merge())) {
142
0
    case MCR_First:
143
0
      useNew = false;
144
0
      break;
145
0
    case MCR_Second:
146
0
      useNew = true;
147
0
      break;
148
0
    case MCR_Largest: {
149
0
      uint64_t existingSize = existingDef->sectionSize();
150
0
      uint64_t newSize = newDef->sectionSize();
151
0
      useNew = (newSize >= existingSize);
152
0
      break;
153
0
    }
154
0
    case MCR_SameSize: {
155
0
      uint64_t existingSize = existingDef->sectionSize();
156
0
      uint64_t newSize = newDef->sectionSize();
157
0
      if (
existingSize == newSize0
) {
158
0
        useNew = true;
159
0
        break;
160
0
      }
161
0
      llvm::errs() << "Size mismatch: "
162
0
                   << existing->name() << " (" << existingSize << ") "
163
0
                   << newAtom.name() << " (" << newSize << ")\n";
164
0
      LLVM_FALLTHROUGH;
165
0
    }
166
0
    case MCR_Error:
167
0
      llvm::errs() << "Duplicate symbols: "
168
0
                   << existing->name()
169
0
                   << ":"
170
0
                   << existing->file().path()
171
0
                   << " and "
172
0
                   << newAtom.name()
173
0
                   << ":"
174
0
                   << newAtom.file().path()
175
0
                   << "\n";
176
0
      llvm::report_fatal_error("duplicate symbol error");
177
0
      break;
178
0
    }
179
0
    break;
180
0
  }
181
54
  case NCR_DupUndef: {
182
54
    const UndefinedAtom* existingUndef = cast<UndefinedAtom>(existing);
183
54
    const UndefinedAtom* newUndef = cast<UndefinedAtom>(&newAtom);
184
54
185
54
    bool sameCanBeNull = (existingUndef->canBeNull() == newUndef->canBeNull());
186
54
    if (sameCanBeNull)
187
54
      useNew = false;
188
54
    else
189
0
      useNew = (newUndef->canBeNull() < existingUndef->canBeNull());
190
54
    break;
191
0
  }
192
0
  case NCR_DupShLib: {
193
0
    useNew = false;
194
0
    break;
195
0
  }
196
0
  case NCR_Error:
197
0
    llvm::errs() << "SymbolTable: error while merging " << name << "\n";
198
0
    llvm::report_fatal_error("duplicate symbol error");
199
0
    break;
200
283
  }
201
283
202
283
  
if (283
useNew283
) {
203
218
    // Update name table to use new atom.
204
218
    _nameTable[name] = &newAtom;
205
218
    // Add existing atom to replacement table.
206
218
    _replacedAtoms[existing] = &newAtom;
207
283
  } else {
208
65
    // New atom is not being used.  Add it to replacement table.
209
65
    _replacedAtoms[&newAtom] = existing;
210
65
  }
211
966
  return false;
212
966
}
213
214
54
unsigned SymbolTable::AtomMappingInfo::getHashValue(const DefinedAtom *atom) {
215
54
  auto content = atom->rawContent();
216
54
  return llvm::hash_combine(atom->size(),
217
54
                            atom->contentType(),
218
54
                            llvm::hash_combine_range(content.begin(),
219
54
                                                     content.end()));
220
54
}
221
222
bool SymbolTable::AtomMappingInfo::isEqual(const DefinedAtom * const l,
223
1.36k
                                           const DefinedAtom * const r) {
224
1.36k
  if (l == r)
225
1.20k
    return true;
226
156
  
if (156
l == getEmptyKey() || 156
r == getEmptyKey()156
)
227
100
    return false;
228
56
  
if (56
l == getTombstoneKey() || 56
r == getTombstoneKey()56
)
229
46
    return false;
230
10
  
if (10
l->contentType() != r->contentType()10
)
231
4
    return false;
232
6
  
if (6
l->size() != r->size()6
)
233
0
    return false;
234
6
  
if (6
l->sectionChoice() != r->sectionChoice()6
)
235
4
    return false;
236
2
  
if (2
l->sectionChoice() == DefinedAtom::sectionCustomRequired2
) {
237
2
    if (!l->customSectionName().equals(r->customSectionName()))
238
2
      return false;
239
0
  }
240
0
  ArrayRef<uint8_t> lc = l->rawContent();
241
0
  ArrayRef<uint8_t> rc = r->rawContent();
242
0
  return memcmp(lc.data(), rc.data(), lc.size()) == 0;
243
0
}
244
245
36
bool SymbolTable::addByContent(const DefinedAtom &newAtom) {
246
36
  AtomContentSet::iterator pos = _contentTable.find(&newAtom);
247
36
  if (
pos == _contentTable.end()36
) {
248
36
    _contentTable.insert(&newAtom);
249
36
    return true;
250
36
  }
251
0
  const Atom* existing = *pos;
252
0
  // New atom is not being used.  Add it to replacement table.
253
0
  _replacedAtoms[&newAtom] = existing;
254
0
  return false;
255
0
}
256
257
1.25k
const Atom *SymbolTable::findByName(StringRef sym) {
258
1.25k
  NameToAtom::iterator pos = _nameTable.find(sym);
259
1.25k
  if (pos == _nameTable.end())
260
683
    return nullptr;
261
568
  return pos->second;
262
568
}
263
264
608
const Atom *SymbolTable::replacement(const Atom *atom) {
265
608
  // Find the replacement for a given atom. Atoms in _replacedAtoms
266
608
  // may be chained, so find the last one.
267
679
  for (;;) {
268
679
    AtomToAtom::iterator pos = _replacedAtoms.find(atom);
269
679
    if (pos == _replacedAtoms.end())
270
608
      return atom;
271
71
    atom = pos->second;
272
71
  }
273
608
}
274
275
1.39k
bool SymbolTable::isCoalescedAway(const Atom *atom) {
276
1.39k
  return _replacedAtoms.count(atom) > 0;
277
1.39k
}
278
279
172
std::vector<const UndefinedAtom *> SymbolTable::undefines() {
280
172
  std::vector<const UndefinedAtom *> ret;
281
678
  for (auto it : _nameTable) {
282
678
    const Atom *atom = it.second;
283
678
    assert(atom != nullptr);
284
678
    if (const auto *undef = dyn_cast<const UndefinedAtom>(atom))
285
52
      
if (52
_replacedAtoms.count(undef) == 052
)
286
52
        ret.push_back(undef);
287
678
  }
288
172
  return ret;
289
172
}
290
291
} // namespace lld