blob: 1b40bd37dcc5afefedea7cd65283bd4801464471 [file] [log] [blame]
Michael J. Spencer773a8fb2011-12-18 08:27:59 +00001//===- Core/Resolver.cpp - Resolves Atom References -----------------------===//
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
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000010#include "lld/Core/Atom.h"
Shankar Easwarana96f3a32013-10-07 02:47:09 +000011#include "lld/Core/ArchiveLibraryFile.h"
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000012#include "lld/Core/File.h"
Shankar Easwarana96f3a32013-10-07 02:47:09 +000013#include "lld/Core/SharedLibraryFile.h"
Michael J. Spencerbd66d042013-05-28 18:55:39 +000014#include "lld/Core/Instrumentation.h"
Michael J. Spencere6203a52012-04-03 18:39:40 +000015#include "lld/Core/LLVM.h"
Nick Kledzikabb69812012-05-31 22:34:00 +000016#include "lld/Core/Resolver.h"
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000017#include "lld/Core/SymbolTable.h"
Rui Ueyama0ca149f2013-08-06 22:31:59 +000018#include "lld/Core/LinkingContext.h"
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000019#include "lld/Core/UndefinedAtom.h"
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000020
Nick Kledzikabb69812012-05-31 22:34:00 +000021#include "llvm/Support/Debug.h"
Michael J. Spencer4586fbc2013-01-22 20:49:42 +000022#include "llvm/Support/ErrorHandling.h"
Nick Kledzikabb69812012-05-31 22:34:00 +000023#include "llvm/Support/Format.h"
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000024#include "llvm/Support/raw_ostream.h"
25
26#include <algorithm>
27#include <cassert>
28#include <vector>
29
30namespace lld {
31
Nick Kledzik80d83082013-05-08 21:34:11 +000032namespace {
33
Michael J. Spencer765792d2012-04-03 18:40:27 +000034/// This is used as a filter function to std::remove_if to coalesced atoms.
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000035class AtomCoalescedAway {
36public:
Nick Kledzik80d83082013-05-08 21:34:11 +000037 explicit AtomCoalescedAway(SymbolTable &sym) : _symbolTable(sym) {}
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000038
39 bool operator()(const Atom *atom) const {
40 const Atom *rep = _symbolTable.replacement(atom);
41 return rep != atom;
42 }
43
44private:
45 SymbolTable &_symbolTable;
46};
47
Nick Kledzik80d83082013-05-08 21:34:11 +000048} // namespace
49
Shankar Easwarana96f3a32013-10-07 02:47:09 +000050void Resolver::handleFile(const File &file) {
Rui Ueyama70625fb2014-04-03 22:21:59 +000051 bool isEmpty = file.defined().empty() && file.undefined().empty() &&
52 file.sharedLibrary().empty() && file.absolute().empty();
Rui Ueyama6aa91cf2014-04-03 21:00:03 +000053 if (isEmpty)
54 return;
55
Rui Ueyamaedd5c0a2014-04-02 21:02:44 +000056 for (const DefinedAtom *atom : file.defined())
Shankar Easwarana96f3a32013-10-07 02:47:09 +000057 doDefinedAtom(*atom);
Rui Ueyama70625fb2014-04-03 22:21:59 +000058 for (const UndefinedAtom *atom : file.undefined())
59 doUndefinedAtom(*atom);
Rui Ueyama94575102014-04-03 20:54:47 +000060 for (const SharedLibraryAtom *atom : file.sharedLibrary())
61 doSharedLibraryAtom(*atom);
62 for (const AbsoluteAtom *atom : file.absolute())
63 doAbsoluteAtom(*atom);
Rui Ueyamaedd5c0a2014-04-02 21:02:44 +000064
Rui Ueyama6aa91cf2014-04-03 21:00:03 +000065 // Notify the input file manager of the fact that we have made some progress
66 // on linking using the current input file. It may want to know the fact for
67 // --start-group/--end-group.
Rui Ueyama8bd093b2014-04-04 00:14:04 +000068 _context.getInputGraph().notifyProgress();
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000069}
70
Rui Ueyamafd133b32013-11-21 23:41:53 +000071void Resolver::forEachUndefines(UndefCallback callback,
72 bool searchForOverrides) {
Shankar Easwarana96f3a32013-10-07 02:47:09 +000073 // Handle normal archives
74 int64_t undefineGenCount = 0;
75 do {
76 undefineGenCount = _symbolTable.size();
77 std::vector<const UndefinedAtom *> undefines;
78 _symbolTable.undefines(undefines);
79 for (const UndefinedAtom *undefAtom : undefines) {
80 StringRef undefName = undefAtom->name();
81 // load for previous undefine may also have loaded this undefine
Rui Ueyama3429d012013-11-15 04:58:54 +000082 if (!_symbolTable.isDefined(undefName))
83 callback(undefName, false);
Shankar Easwarana96f3a32013-10-07 02:47:09 +000084 }
85 // search libraries for overrides of common symbols
Rui Ueyama3429d012013-11-15 04:58:54 +000086 if (searchForOverrides) {
Shankar Easwarana96f3a32013-10-07 02:47:09 +000087 std::vector<StringRef> tentDefNames;
88 _symbolTable.tentativeDefinitions(tentDefNames);
89 for (StringRef tentDefName : tentDefNames) {
90 // Load for previous tentative may also have loaded
91 // something that overrode this tentative, so always check.
92 const Atom *curAtom = _symbolTable.findByName(tentDefName);
93 assert(curAtom != nullptr);
94 if (const DefinedAtom *curDefAtom = dyn_cast<DefinedAtom>(curAtom)) {
Rui Ueyama3429d012013-11-15 04:58:54 +000095 if (curDefAtom->merge() == DefinedAtom::mergeAsTentative)
96 callback(tentDefName, true);
Shankar Easwarana96f3a32013-10-07 02:47:09 +000097 }
98 }
99 }
100 } while (undefineGenCount != _symbolTable.size());
101}
102
Rui Ueyama3429d012013-11-15 04:58:54 +0000103void Resolver::handleArchiveFile(const File &file) {
Rui Ueyama0ca88e32014-04-02 06:54:43 +0000104 const ArchiveLibraryFile *archiveFile = cast<ArchiveLibraryFile>(&file);
Rui Ueyama3429d012013-11-15 04:58:54 +0000105 auto callback = [&](StringRef undefName, bool dataSymbolOnly) {
106 if (const File *member = archiveFile->find(undefName, dataSymbolOnly)) {
107 member->setOrdinal(_context.getNextOrdinalAndIncrement());
108 handleFile(*member);
109 }
110 };
Rui Ueyamafd133b32013-11-21 23:41:53 +0000111 bool searchForOverrides =
112 _context.searchArchivesToOverrideTentativeDefinitions();
Rui Ueyama3429d012013-11-15 04:58:54 +0000113 forEachUndefines(callback, searchForOverrides);
114}
Shankar Easwarana96f3a32013-10-07 02:47:09 +0000115
Rui Ueyama3429d012013-11-15 04:58:54 +0000116void Resolver::handleSharedLibrary(const File &file) {
Shankar Easwarana96f3a32013-10-07 02:47:09 +0000117 // Add all the atoms from the shared library
Rui Ueyama0ca88e32014-04-02 06:54:43 +0000118 const SharedLibraryFile *sharedLibrary = cast<SharedLibraryFile>(&file);
Shankar Easwarana96f3a32013-10-07 02:47:09 +0000119 handleFile(*sharedLibrary);
Rui Ueyama3429d012013-11-15 04:58:54 +0000120
121 auto callback = [&](StringRef undefName, bool dataSymbolOnly) {
Rui Ueyamafd133b32013-11-21 23:41:53 +0000122 if (const SharedLibraryAtom *shAtom =
123 sharedLibrary->exports(undefName, dataSymbolOnly))
Rui Ueyama3429d012013-11-15 04:58:54 +0000124 doSharedLibraryAtom(*shAtom);
125 };
126 bool searchForOverrides =
127 _context.searchSharedLibrariesToOverrideTentativeDefinitions();
128 forEachUndefines(callback, searchForOverrides);
Shankar Easwarana96f3a32013-10-07 02:47:09 +0000129}
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000130
Rui Ueyamafd133b32013-11-21 23:41:53 +0000131void Resolver::doUndefinedAtom(const UndefinedAtom &atom) {
Nick Kledzikabb69812012-05-31 22:34:00 +0000132 DEBUG_WITH_TYPE("resolver", llvm::dbgs()
133 << " UndefinedAtom: "
134 << llvm::format("0x%09lX", &atom)
Rui Ueyama70625fb2014-04-03 22:21:59 +0000135 << ", name=" << atom.name() << "\n");
Nick Kledzikabb69812012-05-31 22:34:00 +0000136
Rui Ueyamafd133b32013-11-21 23:41:53 +0000137 // add to list of known atoms
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000138 _atoms.push_back(&atom);
Michael J. Spencer765792d2012-04-03 18:40:27 +0000139
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000140 // tell symbol table
141 _symbolTable.add(atom);
Rui Ueyama70625fb2014-04-03 22:21:59 +0000142
143 // If the undefined symbol has an alternative name, try to resolve the
144 // symbol with the name to give it a second chance. This feature is used
145 // for COFF "weak external" symbol.
146 if (!_symbolTable.isDefined(atom.name())) {
147 if (const UndefinedAtom *fallbackAtom = atom.fallback()) {
148 doUndefinedAtom(*fallbackAtom);
149 _symbolTable.addReplacement(&atom, fallbackAtom);
150 }
151 }
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000152}
153
Shankar Easwaran7ac2a3d2014-03-26 16:37:13 +0000154/// \brief Add the section group and the group-child reference members.
Shankar Easwaran9316c402014-04-01 03:49:55 +0000155bool Resolver::maybeAddSectionGroupOrGnuLinkOnce(const DefinedAtom &atom) {
Rui Ueyamafb44f5e2014-04-03 21:06:23 +0000156 // First time adding a group?
Shankar Easwaran7ac2a3d2014-03-26 16:37:13 +0000157 bool isFirstTime = _symbolTable.addGroup(atom);
Shankar Easwaran9316c402014-04-01 03:49:55 +0000158
159 if (!isFirstTime) {
160 // If duplicate symbols are allowed, select the first group.
161 if (_context.getAllowDuplicates())
162 return true;
163 const DefinedAtom *prevGroup =
Rui Ueyamab461b1c2014-04-02 06:54:46 +0000164 dyn_cast<DefinedAtom>(_symbolTable.findGroup(atom.name()));
Shankar Easwaran9316c402014-04-01 03:49:55 +0000165 assert(prevGroup &&
166 "Internal Error: The group atom could only be a defined atom");
167 // The atoms should be of the same content type, reject invalid group
168 // resolution behaviors.
169 if (atom.contentType() != prevGroup->contentType())
170 return false;
171 return true;
172 }
Shankar Easwaran7ac2a3d2014-03-26 16:37:13 +0000173
174 for (const Reference *r : atom) {
175 if ((r->kindNamespace() == lld::Reference::KindNamespace::all) &&
176 (r->kindValue() == lld::Reference::kindGroupChild)) {
Rui Ueyamab461b1c2014-04-02 06:54:46 +0000177 const DefinedAtom *target = dyn_cast<DefinedAtom>(r->target());
Shankar Easwaran7ac2a3d2014-03-26 16:37:13 +0000178 assert(target && "Internal Error: kindGroupChild references need to "
179 "be associated with Defined Atoms only");
180 _atoms.push_back(target);
181 _symbolTable.add(*target);
182 }
183 }
Shankar Easwaran9316c402014-04-01 03:49:55 +0000184 return true;
Shankar Easwaran7ac2a3d2014-03-26 16:37:13 +0000185}
186
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000187// called on each atom when a file is added
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000188void Resolver::doDefinedAtom(const DefinedAtom &atom) {
Nick Kledzikabb69812012-05-31 22:34:00 +0000189 DEBUG_WITH_TYPE("resolver", llvm::dbgs()
190 << " DefinedAtom: "
191 << llvm::format("0x%09lX", &atom)
Nick Kledzik36293f62013-01-23 22:32:56 +0000192 << ", file=#"
193 << atom.file().ordinal()
194 << ", atom=#"
195 << atom.ordinal()
Nick Kledzikabb69812012-05-31 22:34:00 +0000196 << ", name="
197 << atom.name()
198 << "\n");
199
Nick Kledzik36293f62013-01-23 22:32:56 +0000200 // Verify on zero-size atoms are pinned to start or end of section.
Rui Ueyama71c02022014-04-03 22:43:42 +0000201 if (atom.sectionPosition() == DefinedAtom::sectionPositionStart ||
202 atom.sectionPosition() == DefinedAtom::sectionPositionEnd) {
Rui Ueyamae20474d2013-11-13 03:30:29 +0000203 assert(atom.size() == 0);
Nick Kledzik36293f62013-01-23 22:32:56 +0000204 }
205
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000206 // add to list of known atoms
207 _atoms.push_back(&atom);
Michael J. Spencer765792d2012-04-03 18:40:27 +0000208
Shankar Easwaran9316c402014-04-01 03:49:55 +0000209 if (atom.isGroupParent()) {
210 // Raise error if there exists a similar gnu linkonce section.
211 if (!maybeAddSectionGroupOrGnuLinkOnce(atom)) {
212 llvm::errs() << "SymbolTable: error while merging " << atom.name()
213 << "\n";
214 llvm::report_fatal_error("duplicate symbol error");
215 }
216 } else {
Shankar Easwaran7ac2a3d2014-03-26 16:37:13 +0000217 _symbolTable.add(atom);
Shankar Easwaran9316c402014-04-01 03:49:55 +0000218 }
Nick Kledzikabb69812012-05-31 22:34:00 +0000219
Rui Ueyama83e6acc2014-04-03 21:11:22 +0000220 // An atom that should never be dead-stripped is a dead-strip root.
221 if (_context.deadStrip() && atom.deadStrip() == DefinedAtom::deadStripNever) {
222 _deadStripRoots.insert(&atom);
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000223 }
224}
225
Rui Ueyamafd133b32013-11-21 23:41:53 +0000226void Resolver::doSharedLibraryAtom(const SharedLibraryAtom &atom) {
227 DEBUG_WITH_TYPE("resolver", llvm::dbgs()
Nick Kledzikabb69812012-05-31 22:34:00 +0000228 << " SharedLibraryAtom: "
229 << llvm::format("0x%09lX", &atom)
230 << ", name="
231 << atom.name()
232 << "\n");
233
Nick Kledzik6bc04c62012-02-22 21:56:59 +0000234 // add to list of known atoms
235 _atoms.push_back(&atom);
Michael J. Spencer765792d2012-04-03 18:40:27 +0000236
Nick Kledzik6bc04c62012-02-22 21:56:59 +0000237 // tell symbol table
238 _symbolTable.add(atom);
239}
Michael J. Spencer765792d2012-04-03 18:40:27 +0000240
Rui Ueyamafd133b32013-11-21 23:41:53 +0000241void Resolver::doAbsoluteAtom(const AbsoluteAtom &atom) {
242 DEBUG_WITH_TYPE("resolver", llvm::dbgs()
Nick Kledzikabb69812012-05-31 22:34:00 +0000243 << " AbsoluteAtom: "
244 << llvm::format("0x%09lX", &atom)
245 << ", name="
Rui Ueyamafd133b32013-11-21 23:41:53 +0000246 << atom.name()
Nick Kledzikabb69812012-05-31 22:34:00 +0000247 << "\n");
248
Nick Kledzik6bc04c62012-02-22 21:56:59 +0000249 // add to list of known atoms
250 _atoms.push_back(&atom);
Michael J. Spencer765792d2012-04-03 18:40:27 +0000251
Nick Kledzik6bc04c62012-02-22 21:56:59 +0000252 // tell symbol table
Rui Ueyamac53b3b02013-12-10 06:19:09 +0000253 if (atom.scope() != Atom::scopeTranslationUnit)
Hemant Kulkarnif8286132012-11-05 19:13:54 +0000254 _symbolTable.add(atom);
Nick Kledzik6bc04c62012-02-22 21:56:59 +0000255}
256
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000257// utility to add a vector of atoms
Rui Ueyamafd133b32013-11-21 23:41:53 +0000258void Resolver::addAtoms(const std::vector<const DefinedAtom *> &newAtoms) {
Rui Ueyamac53b3b02013-12-10 06:19:09 +0000259 for (const DefinedAtom *newAtom : newAtoms)
Rui Ueyama2b2ac912014-04-03 18:13:14 +0000260 doDefinedAtom(*newAtom);
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000261}
262
Rui Ueyama8bd093b2014-04-04 00:14:04 +0000263// Keep adding atoms until _context.getNextFile() returns an error. This
264// function is where undefined atoms are resolved.
Rui Ueyama2ad117d2013-10-11 06:26:16 +0000265bool Resolver::resolveUndefines() {
Michael J. Spencerbd66d042013-05-28 18:55:39 +0000266 ScopedTask task(getDefaultDomain(), "resolveUndefines");
Shankar Easwaraneeee23e2013-04-11 02:56:30 +0000267
Rui Ueyamad542b9e2013-10-11 03:48:06 +0000268 for (;;) {
Rui Ueyama8bd093b2014-04-04 00:14:04 +0000269 ErrorOr<File &> file = _context.getInputGraph().getNextFile();
Rafael Espindolad28918b2014-01-08 22:00:09 +0000270 error_code ec = file.getError();
271 if (ec == InputGraphError::no_more_files)
Rui Ueyama2ad117d2013-10-11 06:26:16 +0000272 return true;
Rui Ueyamad542b9e2013-10-11 03:48:06 +0000273 if (!file) {
Rui Ueyama8bd093b2014-04-04 00:14:04 +0000274 llvm::errs() << "Error occurred in getNextFile: " << ec.message() << "\n";
Rui Ueyama2ad117d2013-10-11 06:26:16 +0000275 return false;
Rui Ueyamad542b9e2013-10-11 03:48:06 +0000276 }
277
278 switch (file->kind()) {
279 case File::kindObject:
280 assert(!file->hasOrdinal());
281 file->setOrdinal(_context.getNextOrdinalAndIncrement());
282 handleFile(*file);
Shankar Easwarana96f3a32013-10-07 02:47:09 +0000283 break;
Rui Ueyamad542b9e2013-10-11 03:48:06 +0000284 case File::kindArchiveLibrary:
285 if (!file->hasOrdinal())
286 file->setOrdinal(_context.getNextOrdinalAndIncrement());
287 handleArchiveFile(*file);
288 break;
289 case File::kindSharedLibrary:
290 if (!file->hasOrdinal())
291 file->setOrdinal(_context.getNextOrdinalAndIncrement());
292 handleSharedLibrary(*file);
293 break;
Shankar Easwaran1d3c48f2013-10-09 05:23:23 +0000294 }
Shankar Easwarana96f3a32013-10-07 02:47:09 +0000295 }
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000296}
297
298// switch all references to undefined or coalesced away atoms
299// to the new defined atom
300void Resolver::updateReferences() {
Michael J. Spencerbd66d042013-05-28 18:55:39 +0000301 ScopedTask task(getDefaultDomain(), "updateReferences");
Rui Ueyamafd133b32013-11-21 23:41:53 +0000302 for (const Atom *atom : _atoms) {
303 if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom)) {
Nick Kledzik062a98c2012-04-08 23:52:13 +0000304 for (const Reference *ref : *defAtom) {
Rui Ueyamafd133b32013-11-21 23:41:53 +0000305 const Atom *newTarget = _symbolTable.replacement(ref->target());
306 const_cast<Reference *>(ref)->setTarget(newTarget);
Nick Kledzik1a6615d2012-03-08 00:18:30 +0000307 }
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000308 }
309 }
310}
311
Rui Ueyamae5531fa2013-12-26 07:13:28 +0000312// For dead code stripping, recursively mark atoms "live"
Nick Kledzikbb963df2012-04-18 21:55:06 +0000313void Resolver::markLive(const Atom &atom) {
Rui Ueyamae5531fa2013-12-26 07:13:28 +0000314 // Mark the atom is live. If it's already marked live, then stop recursion.
315 auto exists = _liveAtoms.insert(&atom);
316 if (!exists.second)
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000317 return;
318
Rui Ueyamae5531fa2013-12-26 07:13:28 +0000319 // Mark all atoms it references as live
Rui Ueyamac481b5b2013-12-26 07:02:33 +0000320 if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(&atom))
321 for (const Reference *ref : *defAtom)
322 if (const Atom *target = ref->target())
Rui Ueyama2b2ac912014-04-03 18:13:14 +0000323 markLive(*target);
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000324}
325
326// remove all atoms not actually used
Rui Ueyamaf3630fe2013-10-16 19:21:50 +0000327void Resolver::deadStripOptimize() {
Michael J. Spencerbd66d042013-05-28 18:55:39 +0000328 ScopedTask task(getDefaultDomain(), "deadStripOptimize");
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000329 // only do this optimization with -dead_strip
Rui Ueyama0ca149f2013-08-06 22:31:59 +0000330 if (!_context.deadStrip())
Rui Ueyamaf3630fe2013-10-16 19:21:50 +0000331 return;
Rui Ueyama841016a2013-12-26 08:11:06 +0000332 assert(_liveAtoms.empty());
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000333
Nick Kledzikbb963df2012-04-18 21:55:06 +0000334 // By default, shared libraries are built with all globals as dead strip roots
Rui Ueyama517f0d92014-04-03 21:16:37 +0000335 if (_context.globalsAreDeadStripRoots())
336 for (const Atom *atom : _atoms)
337 if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom))
338 if (defAtom->scope() == DefinedAtom::scopeGlobal)
339 _deadStripRoots.insert(defAtom);
Nick Kledzikabb69812012-05-31 22:34:00 +0000340
Joerg Sonnenberger03ed4cf2014-01-03 18:43:32 +0000341 // Or, use list of names that are dead strip roots.
Rui Ueyama0ca149f2013-08-06 22:31:59 +0000342 for (const StringRef &name : _context.deadStripRoots()) {
Nick Kledzikbb963df2012-04-18 21:55:06 +0000343 const Atom *symAtom = _symbolTable.findByName(name);
Rui Ueyamaf3630fe2013-10-16 19:21:50 +0000344 assert(symAtom);
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000345 _deadStripRoots.insert(symAtom);
346 }
347
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000348 // mark all roots as live, and recursively all atoms they reference
Rui Ueyamac53b3b02013-12-10 06:19:09 +0000349 for (const Atom *dsrAtom : _deadStripRoots)
Rui Ueyama2b2ac912014-04-03 18:13:14 +0000350 markLive(*dsrAtom);
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000351
352 // now remove all non-live atoms from _atoms
Rui Ueyama450d9872014-04-03 22:24:40 +0000353 _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(), [&](const Atom *a) {
354 return _liveAtoms.count(a) == 0;
355 }),
356 _atoms.end());
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000357}
358
359// error out if some undefines remain
Rui Ueyama43a589c2014-04-02 06:38:46 +0000360bool Resolver::checkUndefines() {
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000361 // build vector of remaining undefined symbols
Michael J. Spencer280dadb2013-01-31 22:56:13 +0000362 std::vector<const UndefinedAtom *> undefinedAtoms;
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000363 _symbolTable.undefines(undefinedAtoms);
Rui Ueyama0ca149f2013-08-06 22:31:59 +0000364 if (_context.deadStrip()) {
Nick Kledzikbb963df2012-04-18 21:55:06 +0000365 // When dead code stripping, we don't care if dead atoms are undefined.
Rui Ueyama450d9872014-04-03 22:24:40 +0000366 undefinedAtoms.erase(
367 std::remove_if(undefinedAtoms.begin(), undefinedAtoms.end(),
368 [&](const Atom *a) { return _liveAtoms.count(a) == 0; }),
369 undefinedAtoms.end());
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000370 }
371
Nick Kledzikbb963df2012-04-18 21:55:06 +0000372 // error message about missing symbols
Nick Kledzikc314b462013-04-04 18:59:24 +0000373 if (!undefinedAtoms.empty()) {
Shankar Easwaraneeee23e2013-04-11 02:56:30 +0000374 // FIXME: need diagnostics interface for writing error messages
Nick Kledzikc314b462013-04-04 18:59:24 +0000375 bool foundUndefines = false;
Michael J. Spencer280dadb2013-01-31 22:56:13 +0000376 for (const UndefinedAtom *undefAtom : undefinedAtoms) {
Shankar Easwaraneeee23e2013-04-11 02:56:30 +0000377 const File &f = undefAtom->file();
Michael J. Spencer9d70cef2013-04-24 19:00:26 +0000378
379 // Skip over a weak symbol.
380 if (undefAtom->canBeNull() != UndefinedAtom::canBeNullNever)
381 continue;
382
383 // If this is a library and undefined symbols are allowed on the
384 // target platform, skip over it.
Rui Ueyama0ca149f2013-08-06 22:31:59 +0000385 if (isa<SharedLibraryFile>(f) && _context.allowShlibUndefines())
Michael J. Spencer9d70cef2013-04-24 19:00:26 +0000386 continue;
387
Rui Ueyama6f3254962013-09-12 21:42:52 +0000388 // If the undefine is coalesced away, skip over it.
389 if (_symbolTable.replacement(undefAtom) != undefAtom)
390 continue;
391
Michael J. Spencer9d70cef2013-04-24 19:00:26 +0000392 // Seems like this symbol is undefined. Warn that.
393 foundUndefines = true;
Rui Ueyama0ca149f2013-08-06 22:31:59 +0000394 if (_context.printRemainingUndefines()) {
Rui Ueyama8d7a6f22014-01-18 00:57:40 +0000395 llvm::errs() << "Undefined symbol: " << undefAtom->file().path()
396 << ": " << undefAtom->name() << "\n";
Michael J. Spencer280dadb2013-01-31 22:56:13 +0000397 }
Nick Kledzikbb963df2012-04-18 21:55:06 +0000398 }
Nick Kledzikc314b462013-04-04 18:59:24 +0000399 if (foundUndefines) {
Rui Ueyama0ca149f2013-08-06 22:31:59 +0000400 if (_context.printRemainingUndefines())
Nick Kledzikc314b462013-04-04 18:59:24 +0000401 llvm::errs() << "symbol(s) not found\n";
402 return true;
403 }
Nick Kledzikbb963df2012-04-18 21:55:06 +0000404 }
Nick Kledzikc314b462013-04-04 18:59:24 +0000405 return false;
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000406}
407
408// remove from _atoms all coaleseced away atoms
409void Resolver::removeCoalescedAwayAtoms() {
Michael J. Spencerbd66d042013-05-28 18:55:39 +0000410 ScopedTask task(getDefaultDomain(), "removeCoalescedAwayAtoms");
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000411 _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(),
Rui Ueyamafd133b32013-11-21 23:41:53 +0000412 AtomCoalescedAway(_symbolTable)),
413 _atoms.end());
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000414}
415
Nick Kledzikc314b462013-04-04 18:59:24 +0000416bool Resolver::resolve() {
Rui Ueyama2b2ac912014-04-03 18:13:14 +0000417 if (!resolveUndefines())
Rui Ueyama2ad117d2013-10-11 06:26:16 +0000418 return false;
Rui Ueyama2b2ac912014-04-03 18:13:14 +0000419 updateReferences();
420 deadStripOptimize();
421 if (checkUndefines())
Rui Ueyama0ca149f2013-08-06 22:31:59 +0000422 if (!_context.allowRemainingUndefines())
Rui Ueyamaee366042013-10-11 06:16:33 +0000423 return false;
Rui Ueyama2b2ac912014-04-03 18:13:14 +0000424 removeCoalescedAwayAtoms();
425 _result->addAtoms(_atoms);
Rui Ueyamaee366042013-10-11 06:16:33 +0000426 return true;
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000427}
428
Rui Ueyamafd133b32013-11-21 23:41:53 +0000429void Resolver::MergedFile::addAtom(const Atom &atom) {
Rui Ueyama251e68b2014-01-18 00:38:44 +0000430 if (auto *def = dyn_cast<DefinedAtom>(&atom)) {
431 _definedAtoms._atoms.push_back(def);
432 } else if (auto *undef = dyn_cast<UndefinedAtom>(&atom)) {
433 _undefinedAtoms._atoms.push_back(undef);
434 } else if (auto *shared = dyn_cast<SharedLibraryAtom>(&atom)) {
435 _sharedLibraryAtoms._atoms.push_back(shared);
436 } else if (auto *abs = dyn_cast<AbsoluteAtom>(&atom)) {
437 _absoluteAtoms._atoms.push_back(abs);
Michael J. Spencerb4955622012-04-02 23:56:36 +0000438 } else {
Nick Kledzik751eb3d2012-06-15 20:37:24 +0000439 llvm_unreachable("atom has unknown definition kind");
Nick Kledzik1a6615d2012-03-08 00:18:30 +0000440 }
441}
442
Nick Kledzik36293f62013-01-23 22:32:56 +0000443MutableFile::DefinedAtomRange Resolver::MergedFile::definedAtoms() {
Rui Ueyamafd133b32013-11-21 23:41:53 +0000444 return range<std::vector<const DefinedAtom *>::iterator>(
445 _definedAtoms._atoms.begin(), _definedAtoms._atoms.end());
Nick Kledzik36293f62013-01-23 22:32:56 +0000446}
447
Rui Ueyamafd133b32013-11-21 23:41:53 +0000448void Resolver::MergedFile::addAtoms(std::vector<const Atom *> &all) {
Michael J. Spencerbd66d042013-05-28 18:55:39 +0000449 ScopedTask task(getDefaultDomain(), "addAtoms");
Nick Kledzikabb69812012-05-31 22:34:00 +0000450 DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "Resolver final atom list:\n");
Rui Ueyamafd133b32013-11-21 23:41:53 +0000451 for (const Atom *atom : all) {
Nick Kledzikabb69812012-05-31 22:34:00 +0000452 DEBUG_WITH_TYPE("resolver", llvm::dbgs()
453 << llvm::format(" 0x%09lX", atom)
454 << ", name="
455 << atom->name()
456 << "\n");
Rui Ueyama2b2ac912014-04-03 18:13:14 +0000457 addAtom(*atom);
Nick Kledzik1a6615d2012-03-08 00:18:30 +0000458 }
459}
460
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000461} // namespace lld