Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 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" |
Nick Kledzik | 6bc04c6 | 2012-02-22 21:56:59 +0000 | [diff] [blame] | 11 | #include "lld/Core/AbsoluteAtom.h" |
Michael J. Spencer | 4586fbc | 2013-01-22 20:49:42 +0000 | [diff] [blame] | 12 | #include "lld/Core/Atom.h" |
Michael J. Spencer | cfd029f | 2012-03-28 19:04:02 +0000 | [diff] [blame] | 13 | #include "lld/Core/DefinedAtom.h" |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 14 | #include "lld/Core/File.h" |
Michael J. Spencer | e6203a5 | 2012-04-03 18:39:40 +0000 | [diff] [blame] | 15 | #include "lld/Core/LLVM.h" |
Shankar Easwaran | 2b67fca | 2014-10-18 05:33:55 +0000 | [diff] [blame] | 16 | #include "lld/Core/LinkingContext.h" |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 17 | #include "lld/Core/Resolver.h" |
Michael J. Spencer | cfd029f | 2012-03-28 19:04:02 +0000 | [diff] [blame] | 18 | #include "lld/Core/SharedLibraryAtom.h" |
| 19 | #include "lld/Core/UndefinedAtom.h" |
Nick Kledzik | bfedfc1 | 2012-01-09 20:18:15 +0000 | [diff] [blame] | 20 | #include "llvm/ADT/ArrayRef.h" |
Michael J. Spencer | cfd029f | 2012-03-28 19:04:02 +0000 | [diff] [blame] | 21 | #include "llvm/ADT/DenseMapInfo.h" |
Michael J. Spencer | 67f2527 | 2013-03-20 22:18:22 +0000 | [diff] [blame] | 22 | #include "llvm/ADT/Hashing.h" |
Michael J. Spencer | cfd029f | 2012-03-28 19:04:02 +0000 | [diff] [blame] | 23 | #include "llvm/Support/ErrorHandling.h" |
Nick Kledzik | bb963df | 2012-04-18 21:55:06 +0000 | [diff] [blame] | 24 | #include "llvm/Support/raw_ostream.h" |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 25 | #include <algorithm> |
| 26 | #include <cassert> |
Michael J. Spencer | cfd029f | 2012-03-28 19:04:02 +0000 | [diff] [blame] | 27 | #include <cstdlib> |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 28 | #include <vector> |
| 29 | |
| 30 | namespace lld { |
Rui Ueyama | aabd7ca | 2015-04-10 21:40:59 +0000 | [diff] [blame] | 31 | SymbolTable::SymbolTable(LinkingContext &context) : _ctx(context) {} |
Nick Kledzik | 38eec3d | 2011-12-22 02:38:01 +0000 | [diff] [blame] | 32 | |
Rui Ueyama | 2a52251 | 2014-05-14 17:29:27 +0000 | [diff] [blame] | 33 | bool SymbolTable::add(const UndefinedAtom &atom) { return addByName(atom); } |
Nick Kledzik | f4fb2c5 | 2012-01-11 01:06:19 +0000 | [diff] [blame] | 34 | |
Rui Ueyama | 2a52251 | 2014-05-14 17:29:27 +0000 | [diff] [blame] | 35 | bool SymbolTable::add(const SharedLibraryAtom &atom) { return addByName(atom); } |
Michael J. Spencer | 765792d | 2012-04-03 18:40:27 +0000 | [diff] [blame] | 36 | |
Rui Ueyama | 2a52251 | 2014-05-14 17:29:27 +0000 | [diff] [blame] | 37 | bool SymbolTable::add(const AbsoluteAtom &atom) { return addByName(atom); } |
Nick Kledzik | 6bc04c6 | 2012-02-22 21:56:59 +0000 | [diff] [blame] | 38 | |
Rui Ueyama | 2a52251 | 2014-05-14 17:29:27 +0000 | [diff] [blame] | 39 | bool SymbolTable::add(const DefinedAtom &atom) { |
Shankar Easwaran | 8962feb | 2013-03-14 16:09:49 +0000 | [diff] [blame] | 40 | if (!atom.name().empty() && |
Rui Ueyama | 8b08c37 | 2013-11-25 17:09:29 +0000 | [diff] [blame] | 41 | atom.scope() != DefinedAtom::scopeTranslationUnit) { |
Nick Kledzik | 233f537 | 2013-01-15 00:17:57 +0000 | [diff] [blame] | 42 | // Named atoms cannot be merged by content. |
| 43 | assert(atom.merge() != DefinedAtom::mergeByContent); |
| 44 | // Track named atoms that are not scoped to file (static). |
Rui Ueyama | 2a52251 | 2014-05-14 17:29:27 +0000 | [diff] [blame] | 45 | return addByName(atom); |
Rui Ueyama | 8b08c37 | 2013-11-25 17:09:29 +0000 | [diff] [blame] | 46 | } |
| 47 | if (atom.merge() == DefinedAtom::mergeByContent) { |
Nick Kledzik | 233f537 | 2013-01-15 00:17:57 +0000 | [diff] [blame] | 48 | // Named atoms cannot be merged by content. |
| 49 | assert(atom.name().empty()); |
Nick Kledzik | 388f3d0 | 2014-05-28 01:16:35 +0000 | [diff] [blame] | 50 | // Currently only read-only constants can be merged. |
| 51 | if (atom.permissions() == DefinedAtom::permR__) |
| 52 | return addByContent(atom); |
| 53 | // TODO: support mergeByContent of data atoms by comparing content & fixups. |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 54 | } |
Rui Ueyama | 2a52251 | 2014-05-14 17:29:27 +0000 | [diff] [blame] | 55 | return false; |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 56 | } |
| 57 | |
| 58 | enum NameCollisionResolution { |
| 59 | NCR_First, |
| 60 | NCR_Second, |
Nick Kledzik | 6bc04c6 | 2012-02-22 21:56:59 +0000 | [diff] [blame] | 61 | NCR_DupDef, |
| 62 | NCR_DupUndef, |
| 63 | NCR_DupShLib, |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 64 | NCR_Error |
| 65 | }; |
| 66 | |
Nick Kledzik | f4fb2c5 | 2012-01-11 01:06:19 +0000 | [diff] [blame] | 67 | static NameCollisionResolution cases[4][4] = { |
| 68 | //regular absolute undef sharedLib |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 69 | { |
| 70 | // first is regular |
Nick Kledzik | 6bc04c6 | 2012-02-22 21:56:59 +0000 | [diff] [blame] | 71 | NCR_DupDef, NCR_Error, NCR_First, NCR_First |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 72 | }, |
| 73 | { |
| 74 | // first is absolute |
Nick Kledzik | f4fb2c5 | 2012-01-11 01:06:19 +0000 | [diff] [blame] | 75 | NCR_Error, NCR_Error, NCR_First, NCR_First |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 76 | }, |
| 77 | { |
| 78 | // first is undef |
Nick Kledzik | 6bc04c6 | 2012-02-22 21:56:59 +0000 | [diff] [blame] | 79 | NCR_Second, NCR_Second, NCR_DupUndef, NCR_Second |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 80 | }, |
| 81 | { |
| 82 | // first is sharedLib |
Nick Kledzik | 6bc04c6 | 2012-02-22 21:56:59 +0000 | [diff] [blame] | 83 | NCR_Second, NCR_Second, NCR_First, NCR_DupShLib |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 84 | } |
| 85 | }; |
| 86 | |
| 87 | static NameCollisionResolution collide(Atom::Definition first, |
| 88 | Atom::Definition second) { |
| 89 | return cases[first][second]; |
| 90 | } |
| 91 | |
Nick Kledzik | f4fb2c5 | 2012-01-11 01:06:19 +0000 | [diff] [blame] | 92 | enum MergeResolution { |
| 93 | MCR_First, |
| 94 | MCR_Second, |
| 95 | MCR_Largest, |
Rui Ueyama | c79dd2f | 2014-03-07 23:05:10 +0000 | [diff] [blame] | 96 | MCR_SameSize, |
Nick Kledzik | f4fb2c5 | 2012-01-11 01:06:19 +0000 | [diff] [blame] | 97 | MCR_Error |
| 98 | }; |
| 99 | |
Rui Ueyama | 7ad72eb | 2014-03-18 19:37:50 +0000 | [diff] [blame] | 100 | static MergeResolution mergeCases[][6] = { |
| 101 | // no tentative weak weakAddress sameNameAndSize largest |
| 102 | {MCR_Error, MCR_First, MCR_First, MCR_First, MCR_SameSize, MCR_Largest}, // no |
| 103 | {MCR_Second, MCR_Largest, MCR_Second, MCR_Second, MCR_SameSize, MCR_Largest}, // tentative |
| 104 | {MCR_Second, MCR_First, MCR_First, MCR_Second, MCR_SameSize, MCR_Largest}, // weak |
| 105 | {MCR_Second, MCR_First, MCR_First, MCR_First, MCR_SameSize, MCR_Largest}, // weakAddress |
| 106 | {MCR_SameSize, MCR_SameSize, MCR_SameSize, MCR_SameSize, MCR_SameSize, MCR_SameSize}, // sameSize |
| 107 | {MCR_Largest, MCR_Largest, MCR_Largest, MCR_Largest, MCR_SameSize, MCR_Largest}, // largest |
Nick Kledzik | f4fb2c5 | 2012-01-11 01:06:19 +0000 | [diff] [blame] | 108 | }; |
| 109 | |
Michael J. Spencer | 765792d | 2012-04-03 18:40:27 +0000 | [diff] [blame] | 110 | static MergeResolution mergeSelect(DefinedAtom::Merge first, |
Nick Kledzik | f4fb2c5 | 2012-01-11 01:06:19 +0000 | [diff] [blame] | 111 | DefinedAtom::Merge second) { |
Rui Ueyama | 7caea31 | 2014-03-08 00:44:01 +0000 | [diff] [blame] | 112 | assert(first != DefinedAtom::mergeByContent); |
| 113 | assert(second != DefinedAtom::mergeByContent); |
Nick Kledzik | f4fb2c5 | 2012-01-11 01:06:19 +0000 | [diff] [blame] | 114 | return mergeCases[first][second]; |
| 115 | } |
| 116 | |
Rui Ueyama | 2a52251 | 2014-05-14 17:29:27 +0000 | [diff] [blame] | 117 | bool SymbolTable::addByName(const Atom &newAtom) { |
Michael J. Spencer | e6203a5 | 2012-04-03 18:39:40 +0000 | [diff] [blame] | 118 | StringRef name = newAtom.name(); |
Nick Kledzik | 233f537 | 2013-01-15 00:17:57 +0000 | [diff] [blame] | 119 | assert(!name.empty()); |
Shankar Easwaran | 7ac2a3d | 2014-03-26 16:37:13 +0000 | [diff] [blame] | 120 | const Atom *existing = findByName(name); |
Michael J. Spencer | c9d2506 | 2012-03-29 19:39:14 +0000 | [diff] [blame] | 121 | if (existing == nullptr) { |
Nick Kledzik | 7735a7d | 2012-01-04 23:58:17 +0000 | [diff] [blame] | 122 | // Name is not in symbol table yet, add it associate with this atom. |
Nick Kledzik | 38eec3d | 2011-12-22 02:38:01 +0000 | [diff] [blame] | 123 | _nameTable[name] = &newAtom; |
Rui Ueyama | 2a52251 | 2014-05-14 17:29:27 +0000 | [diff] [blame] | 124 | return true; |
Michael J. Spencer | 765792d | 2012-04-03 18:40:27 +0000 | [diff] [blame] | 125 | } |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 126 | |
Rui Ueyama | 2a52251 | 2014-05-14 17:29:27 +0000 | [diff] [blame] | 127 | // Do nothing if the same object is added more than once. |
| 128 | if (existing == &newAtom) |
| 129 | return false; |
| 130 | |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 131 | // Name is already in symbol table and associated with another atom. |
| 132 | bool useNew = true; |
| 133 | switch (collide(existing->definition(), newAtom.definition())) { |
| 134 | case NCR_First: |
| 135 | useNew = false; |
| 136 | break; |
| 137 | case NCR_Second: |
| 138 | useNew = true; |
| 139 | break; |
Simon Atanasyan | 55c2699 | 2014-11-14 07:15:43 +0000 | [diff] [blame] | 140 | case NCR_DupDef: { |
| 141 | const auto *existingDef = cast<DefinedAtom>(existing); |
| 142 | const auto *newDef = cast<DefinedAtom>(&newAtom); |
| 143 | switch (mergeSelect(existingDef->merge(), newDef->merge())) { |
Rui Ueyama | 5a3804f | 2013-11-25 17:09:25 +0000 | [diff] [blame] | 144 | case MCR_First: |
| 145 | useNew = false; |
| 146 | break; |
| 147 | case MCR_Second: |
| 148 | useNew = true; |
| 149 | break; |
Rui Ueyama | 7ad72eb | 2014-03-18 19:37:50 +0000 | [diff] [blame] | 150 | case MCR_Largest: { |
Rui Ueyama | 77a4da1 | 2015-03-04 21:40:46 +0000 | [diff] [blame] | 151 | uint64_t existingSize = existingDef->sectionSize(); |
| 152 | uint64_t newSize = newDef->sectionSize(); |
Rui Ueyama | 7ad72eb | 2014-03-18 19:37:50 +0000 | [diff] [blame] | 153 | useNew = (newSize >= existingSize); |
Rui Ueyama | 5a3804f | 2013-11-25 17:09:25 +0000 | [diff] [blame] | 154 | break; |
Rui Ueyama | 7ad72eb | 2014-03-18 19:37:50 +0000 | [diff] [blame] | 155 | } |
Rui Ueyama | c79dd2f | 2014-03-07 23:05:10 +0000 | [diff] [blame] | 156 | case MCR_SameSize: { |
Rui Ueyama | 77a4da1 | 2015-03-04 21:40:46 +0000 | [diff] [blame] | 157 | uint64_t existingSize = existingDef->sectionSize(); |
| 158 | uint64_t newSize = newDef->sectionSize(); |
Rui Ueyama | 7ad72eb | 2014-03-18 19:37:50 +0000 | [diff] [blame] | 159 | if (existingSize == newSize) { |
Rui Ueyama | c79dd2f | 2014-03-07 23:05:10 +0000 | [diff] [blame] | 160 | useNew = true; |
| 161 | break; |
| 162 | } |
| 163 | llvm::errs() << "Size mismatch: " |
Rui Ueyama | 7ad72eb | 2014-03-18 19:37:50 +0000 | [diff] [blame] | 164 | << existing->name() << " (" << existingSize << ") " |
| 165 | << newAtom.name() << " (" << newSize << ")\n"; |
Rui Ueyama | c79dd2f | 2014-03-07 23:05:10 +0000 | [diff] [blame] | 166 | // fallthrough |
| 167 | } |
Rui Ueyama | 5a3804f | 2013-11-25 17:09:25 +0000 | [diff] [blame] | 168 | case MCR_Error: |
Rui Ueyama | aabd7ca | 2015-04-10 21:40:59 +0000 | [diff] [blame] | 169 | if (!_ctx.getAllowDuplicates()) { |
Rui Ueyama | a9a5129 | 2014-03-28 16:26:38 +0000 | [diff] [blame] | 170 | llvm::errs() << "Duplicate symbols: " |
| 171 | << existing->name() |
| 172 | << ":" |
| 173 | << existing->file().path() |
| 174 | << " and " |
| 175 | << newAtom.name() |
| 176 | << ":" |
| 177 | << newAtom.file().path() |
| 178 | << "\n"; |
| 179 | llvm::report_fatal_error("duplicate symbol error"); |
| 180 | } |
| 181 | useNew = false; |
Rui Ueyama | 5a3804f | 2013-11-25 17:09:25 +0000 | [diff] [blame] | 182 | break; |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 183 | } |
| 184 | break; |
Simon Atanasyan | 55c2699 | 2014-11-14 07:15:43 +0000 | [diff] [blame] | 185 | } |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 186 | case NCR_DupUndef: { |
Rui Ueyama | 01cc718 | 2014-04-04 18:21:51 +0000 | [diff] [blame] | 187 | const UndefinedAtom* existingUndef = cast<UndefinedAtom>(existing); |
| 188 | const UndefinedAtom* newUndef = cast<UndefinedAtom>(&newAtom); |
Rui Ueyama | b4dca7f | 2013-11-15 03:12:24 +0000 | [diff] [blame] | 189 | |
| 190 | bool sameCanBeNull = (existingUndef->canBeNull() == newUndef->canBeNull()); |
Rui Ueyama | aabd7ca | 2015-04-10 21:40:59 +0000 | [diff] [blame] | 191 | if (!sameCanBeNull && _ctx.warnIfCoalesableAtomsHaveDifferentCanBeNull()) { |
Rui Ueyama | b4dca7f | 2013-11-15 03:12:24 +0000 | [diff] [blame] | 192 | llvm::errs() << "lld warning: undefined symbol " |
| 193 | << existingUndef->name() |
| 194 | << " has different weakness in " |
| 195 | << existingUndef->file().path() |
| 196 | << " and in " << newUndef->file().path() << "\n"; |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 197 | } |
Rui Ueyama | b4dca7f | 2013-11-15 03:12:24 +0000 | [diff] [blame] | 198 | |
| 199 | const UndefinedAtom *existingFallback = existingUndef->fallback(); |
| 200 | const UndefinedAtom *newFallback = newUndef->fallback(); |
| 201 | bool hasDifferentFallback = |
| 202 | (existingFallback && newFallback && |
| 203 | existingFallback->name() != newFallback->name()); |
| 204 | if (hasDifferentFallback) { |
| 205 | llvm::errs() << "lld warning: undefined symbol " |
| 206 | << existingUndef->name() << " has different fallback: " |
| 207 | << existingFallback->name() << " in " |
| 208 | << existingUndef->file().path() << " and " |
| 209 | << newFallback->name() << " in " |
| 210 | << newUndef->file().path() << "\n"; |
| 211 | } |
| 212 | |
| 213 | bool hasNewFallback = newUndef->fallback(); |
| 214 | if (sameCanBeNull) |
| 215 | useNew = hasNewFallback; |
| 216 | else |
| 217 | useNew = (newUndef->canBeNull() < existingUndef->canBeNull()); |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 218 | break; |
Rui Ueyama | b4dca7f | 2013-11-15 03:12:24 +0000 | [diff] [blame] | 219 | } |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 220 | case NCR_DupShLib: { |
Rui Ueyama | 01cc718 | 2014-04-04 18:21:51 +0000 | [diff] [blame] | 221 | const SharedLibraryAtom *curShLib = cast<SharedLibraryAtom>(existing); |
| 222 | const SharedLibraryAtom *newShLib = cast<SharedLibraryAtom>(&newAtom); |
Rui Ueyama | fb7936d | 2014-04-04 18:12:27 +0000 | [diff] [blame] | 223 | bool sameNullness = |
| 224 | (curShLib->canBeNullAtRuntime() == newShLib->canBeNullAtRuntime()); |
| 225 | bool sameName = curShLib->loadName().equals(newShLib->loadName()); |
Rui Ueyama | e8af3e4 | 2014-04-04 18:21:53 +0000 | [diff] [blame] | 226 | if (sameName && !sameNullness && |
Rui Ueyama | aabd7ca | 2015-04-10 21:40:59 +0000 | [diff] [blame] | 227 | _ctx.warnIfCoalesableAtomsHaveDifferentCanBeNull()) { |
Rui Ueyama | e8af3e4 | 2014-04-04 18:21:53 +0000 | [diff] [blame] | 228 | // FIXME: need diagonstics interface for writing warning messages |
| 229 | llvm::errs() << "lld warning: shared library symbol " |
| 230 | << curShLib->name() << " has different weakness in " |
| 231 | << curShLib->file().path() << " and in " |
| 232 | << newShLib->file().path(); |
Nick Kledzik | 7735a7d | 2012-01-04 23:58:17 +0000 | [diff] [blame] | 233 | } |
Rui Ueyama | aabd7ca | 2015-04-10 21:40:59 +0000 | [diff] [blame] | 234 | if (!sameName && _ctx.warnIfCoalesableAtomsHaveDifferentLoadName()) { |
Rui Ueyama | e8af3e4 | 2014-04-04 18:21:53 +0000 | [diff] [blame] | 235 | // FIXME: need diagonstics interface for writing warning messages |
| 236 | llvm::errs() << "lld warning: shared library symbol " |
| 237 | << curShLib->name() << " has different load path in " |
| 238 | << curShLib->file().path() << " and in " |
| 239 | << newShLib->file().path(); |
| 240 | } |
| 241 | useNew = false; |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 242 | break; |
Rui Ueyama | fb7936d | 2014-04-04 18:12:27 +0000 | [diff] [blame] | 243 | } |
Rui Ueyama | bcccb5d | 2013-11-13 23:23:38 +0000 | [diff] [blame] | 244 | case NCR_Error: |
| 245 | llvm::errs() << "SymbolTable: error while merging " << name << "\n"; |
Rui Ueyama | 9310e01 | 2013-11-14 06:39:31 +0000 | [diff] [blame] | 246 | llvm::report_fatal_error("duplicate symbol error"); |
| 247 | break; |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 248 | } |
Rui Ueyama | bcccb5d | 2013-11-13 23:23:38 +0000 | [diff] [blame] | 249 | |
Nick Kledzik | bb38f7b | 2014-08-20 20:46:28 +0000 | [diff] [blame] | 250 | // Give context a chance to change which is kept. |
Rui Ueyama | aabd7ca | 2015-04-10 21:40:59 +0000 | [diff] [blame] | 251 | _ctx.notifySymbolTableCoalesce(existing, &newAtom, useNew); |
Nick Kledzik | bb38f7b | 2014-08-20 20:46:28 +0000 | [diff] [blame] | 252 | |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 253 | if (useNew) { |
| 254 | // Update name table to use new atom. |
| 255 | _nameTable[name] = &newAtom; |
| 256 | // Add existing atom to replacement table. |
| 257 | _replacedAtoms[existing] = &newAtom; |
| 258 | } else { |
| 259 | // New atom is not being used. Add it to replacement table. |
| 260 | _replacedAtoms[&newAtom] = existing; |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 261 | } |
Rui Ueyama | 2a52251 | 2014-05-14 17:29:27 +0000 | [diff] [blame] | 262 | return false; |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 263 | } |
| 264 | |
Michael J. Spencer | 67f2527 | 2013-03-20 22:18:22 +0000 | [diff] [blame] | 265 | unsigned SymbolTable::AtomMappingInfo::getHashValue(const DefinedAtom *atom) { |
| 266 | auto content = atom->rawContent(); |
| 267 | return llvm::hash_combine(atom->size(), |
| 268 | atom->contentType(), |
| 269 | llvm::hash_combine_range(content.begin(), |
| 270 | content.end())); |
Nick Kledzik | bfedfc1 | 2012-01-09 20:18:15 +0000 | [diff] [blame] | 271 | } |
| 272 | |
Michael J. Spencer | 765792d | 2012-04-03 18:40:27 +0000 | [diff] [blame] | 273 | bool SymbolTable::AtomMappingInfo::isEqual(const DefinedAtom * const l, |
Michael J. Spencer | 67f2527 | 2013-03-20 22:18:22 +0000 | [diff] [blame] | 274 | const DefinedAtom * const r) { |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 275 | if (l == r) |
Nick Kledzik | bfedfc1 | 2012-01-09 20:18:15 +0000 | [diff] [blame] | 276 | return true; |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 277 | if (l == getEmptyKey()) |
Nick Kledzik | bfedfc1 | 2012-01-09 20:18:15 +0000 | [diff] [blame] | 278 | return false; |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 279 | if (r == getEmptyKey()) |
Nick Kledzik | bfedfc1 | 2012-01-09 20:18:15 +0000 | [diff] [blame] | 280 | return false; |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 281 | if (l == getTombstoneKey()) |
Nick Kledzik | bfedfc1 | 2012-01-09 20:18:15 +0000 | [diff] [blame] | 282 | return false; |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 283 | if (r == getTombstoneKey()) |
Nick Kledzik | bfedfc1 | 2012-01-09 20:18:15 +0000 | [diff] [blame] | 284 | return false; |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 285 | if (l->contentType() != r->contentType()) |
Nick Kledzik | bfedfc1 | 2012-01-09 20:18:15 +0000 | [diff] [blame] | 286 | return false; |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 287 | if (l->size() != r->size()) |
Nick Kledzik | bfedfc1 | 2012-01-09 20:18:15 +0000 | [diff] [blame] | 288 | return false; |
Nick Kledzik | 32d0d09 | 2014-10-02 17:22:05 +0000 | [diff] [blame] | 289 | if (l->sectionChoice() != r->sectionChoice()) |
| 290 | return false; |
| 291 | if (l->sectionChoice() == DefinedAtom::sectionCustomRequired) { |
| 292 | if (!l->customSectionName().equals(r->customSectionName())) |
| 293 | return false; |
| 294 | } |
Michael J. Spencer | e6203a5 | 2012-04-03 18:39:40 +0000 | [diff] [blame] | 295 | ArrayRef<uint8_t> lc = l->rawContent(); |
| 296 | ArrayRef<uint8_t> rc = r->rawContent(); |
Michael J. Spencer | 67f2527 | 2013-03-20 22:18:22 +0000 | [diff] [blame] | 297 | return memcmp(lc.data(), rc.data(), lc.size()) == 0; |
Nick Kledzik | bfedfc1 | 2012-01-09 20:18:15 +0000 | [diff] [blame] | 298 | } |
| 299 | |
Rui Ueyama | 2a52251 | 2014-05-14 17:29:27 +0000 | [diff] [blame] | 300 | bool SymbolTable::addByContent(const DefinedAtom &newAtom) { |
Nick Kledzik | bfedfc1 | 2012-01-09 20:18:15 +0000 | [diff] [blame] | 301 | AtomContentSet::iterator pos = _contentTable.find(&newAtom); |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 302 | if (pos == _contentTable.end()) { |
Nick Kledzik | bfedfc1 | 2012-01-09 20:18:15 +0000 | [diff] [blame] | 303 | _contentTable.insert(&newAtom); |
Rui Ueyama | 2a52251 | 2014-05-14 17:29:27 +0000 | [diff] [blame] | 304 | return true; |
Nick Kledzik | bfedfc1 | 2012-01-09 20:18:15 +0000 | [diff] [blame] | 305 | } |
| 306 | const Atom* existing = *pos; |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 307 | // New atom is not being used. Add it to replacement table. |
| 308 | _replacedAtoms[&newAtom] = existing; |
Rui Ueyama | 2a52251 | 2014-05-14 17:29:27 +0000 | [diff] [blame] | 309 | return false; |
Nick Kledzik | bfedfc1 | 2012-01-09 20:18:15 +0000 | [diff] [blame] | 310 | } |
| 311 | |
Michael J. Spencer | e6203a5 | 2012-04-03 18:39:40 +0000 | [diff] [blame] | 312 | const Atom *SymbolTable::findByName(StringRef sym) { |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 313 | NameToAtom::iterator pos = _nameTable.find(sym); |
| 314 | if (pos == _nameTable.end()) |
Michael J. Spencer | c9d2506 | 2012-03-29 19:39:14 +0000 | [diff] [blame] | 315 | return nullptr; |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 316 | return pos->second; |
| 317 | } |
| 318 | |
Michael J. Spencer | e6203a5 | 2012-04-03 18:39:40 +0000 | [diff] [blame] | 319 | bool SymbolTable::isDefined(StringRef sym) { |
Rui Ueyama | 71c0202 | 2014-04-03 22:43:42 +0000 | [diff] [blame] | 320 | if (const Atom *atom = findByName(sym)) |
Rui Ueyama | 0abf613 | 2014-10-14 21:42:08 +0000 | [diff] [blame] | 321 | return !isa<UndefinedAtom>(atom); |
Rui Ueyama | 71c0202 | 2014-04-03 22:43:42 +0000 | [diff] [blame] | 322 | return false; |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 323 | } |
| 324 | |
Rui Ueyama | e5416ec | 2013-09-12 19:14:05 +0000 | [diff] [blame] | 325 | void SymbolTable::addReplacement(const Atom *replaced, |
| 326 | const Atom *replacement) { |
| 327 | _replacedAtoms[replaced] = replacement; |
| 328 | } |
| 329 | |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 330 | const Atom *SymbolTable::replacement(const Atom *atom) { |
Rui Ueyama | 1c3486a | 2014-04-03 22:58:41 +0000 | [diff] [blame] | 331 | // Find the replacement for a given atom. Atoms in _replacedAtoms |
| 332 | // may be chained, so find the last one. |
Rui Ueyama | 4f010d2 | 2014-04-03 22:36:55 +0000 | [diff] [blame] | 333 | for (;;) { |
| 334 | AtomToAtom::iterator pos = _replacedAtoms.find(atom); |
| 335 | if (pos == _replacedAtoms.end()) |
| 336 | return atom; |
Rui Ueyama | 4f010d2 | 2014-04-03 22:36:55 +0000 | [diff] [blame] | 337 | atom = pos->second; |
| 338 | } |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 339 | } |
| 340 | |
Rui Ueyama | 733b45f | 2014-06-05 07:37:29 +0000 | [diff] [blame] | 341 | bool SymbolTable::isCoalescedAway(const Atom *atom) { |
| 342 | return _replacedAtoms.count(atom) > 0; |
| 343 | } |
| 344 | |
Rui Ueyama | 8dc9f0a | 2014-04-04 00:15:52 +0000 | [diff] [blame] | 345 | std::vector<const UndefinedAtom *> SymbolTable::undefines() { |
| 346 | std::vector<const UndefinedAtom *> ret; |
Rui Ueyama | 17e899c | 2013-11-25 17:09:27 +0000 | [diff] [blame] | 347 | for (auto it : _nameTable) { |
| 348 | const Atom *atom = it.second; |
Michael J. Spencer | c9d2506 | 2012-03-29 19:39:14 +0000 | [diff] [blame] | 349 | assert(atom != nullptr); |
Rui Ueyama | 839fb2f | 2014-08-22 02:00:58 +0000 | [diff] [blame] | 350 | if (const auto *undef = dyn_cast<const UndefinedAtom>(atom)) |
| 351 | if (_replacedAtoms.count(undef) == 0) |
| 352 | ret.push_back(undef); |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 353 | } |
Rui Ueyama | 8dc9f0a | 2014-04-04 00:15:52 +0000 | [diff] [blame] | 354 | return ret; |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 355 | } |
| 356 | |
Rui Ueyama | 8dc9f0a | 2014-04-04 00:15:52 +0000 | [diff] [blame] | 357 | std::vector<StringRef> SymbolTable::tentativeDefinitions() { |
| 358 | std::vector<StringRef> ret; |
Nick Kledzik | 20e652d | 2012-04-20 01:24:37 +0000 | [diff] [blame] | 359 | for (auto entry : _nameTable) { |
| 360 | const Atom *atom = entry.second; |
| 361 | StringRef name = entry.first; |
| 362 | assert(atom != nullptr); |
Rui Ueyama | f347e75 | 2013-11-13 23:22:00 +0000 | [diff] [blame] | 363 | if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom)) |
| 364 | if (defAtom->merge() == DefinedAtom::mergeAsTentative) |
Rui Ueyama | 8dc9f0a | 2014-04-04 00:15:52 +0000 | [diff] [blame] | 365 | ret.push_back(name); |
Nick Kledzik | 20e652d | 2012-04-20 01:24:37 +0000 | [diff] [blame] | 366 | } |
Rui Ueyama | 8dc9f0a | 2014-04-04 00:15:52 +0000 | [diff] [blame] | 367 | return ret; |
Nick Kledzik | 20e652d | 2012-04-20 01:24:37 +0000 | [diff] [blame] | 368 | } |
Rui Ueyama | 8dc9f0a | 2014-04-04 00:15:52 +0000 | [diff] [blame] | 369 | |
Michael J. Spencer | 773a8fb | 2011-12-18 08:27:59 +0000 | [diff] [blame] | 370 | } // namespace lld |