/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 |