Coverage Report

Created: 2019-05-19 14:56

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