blob: 7d2aada6c696615b5a439e1f6164d697f8aa1328 [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"
Michael J. Spencerbd66d042013-05-28 18:55:39 +000013#include "lld/Core/Instrumentation.h"
Michael J. Spencere6203a52012-04-03 18:39:40 +000014#include "lld/Core/LLVM.h"
Rui Ueyama0ca149f2013-08-06 22:31:59 +000015#include "lld/Core/LinkingContext.h"
Shankar Easwaran2b67fca2014-10-18 05:33:55 +000016#include "lld/Core/Resolver.h"
17#include "lld/Core/SharedLibraryFile.h"
18#include "lld/Core/SymbolTable.h"
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000019#include "lld/Core/UndefinedAtom.h"
Rui Ueyama25d5abd2015-03-06 00:22:48 +000020#include "llvm/ADT/iterator_range.h"
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"
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000025#include <algorithm>
26#include <cassert>
Rui Ueyama25d5abd2015-03-06 00:22:48 +000027#include <utility>
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000028#include <vector>
29
30namespace lld {
31
Pete Cooper80c09742016-01-14 21:53:13 +000032ErrorOr<bool> Resolver::handleFile(File &file) {
33 if (auto ec = _ctx.handleLoadedFile(file))
34 return ec;
Rui Ueyama2a522512014-05-14 17:29:27 +000035 bool undefAdded = false;
Pete Cooper8ad55fb2016-03-22 17:15:50 +000036 for (auto &atom : file.defined().owning_ptrs())
37 doDefinedAtom(std::move(atom));
38 for (auto &atom : file.undefined().owning_ptrs()) {
39 if (doUndefinedAtom(std::move(atom)))
Rui Ueyama2a522512014-05-14 17:29:27 +000040 undefAdded = true;
Rui Ueyama791db5f2015-03-03 22:19:46 +000041 }
Pete Cooper8ad55fb2016-03-22 17:15:50 +000042 for (auto &atom : file.sharedLibrary().owning_ptrs())
43 doSharedLibraryAtom(std::move(atom));
44 for (auto &atom : file.absolute().owning_ptrs())
45 doAbsoluteAtom(std::move(atom));
Rui Ueyama00eb2572014-12-10 00:33:00 +000046 return undefAdded;
Michael J. Spencer773a8fb2011-12-18 08:27:59 +000047}
48
Rui Ueyama46a8e292016-03-28 20:59:47 +000049ErrorOr<bool> Resolver::forEachUndefines(File &file, UndefCallback callback) {
Rui Ueyama13003d72015-03-06 00:28:41 +000050 size_t i = _undefineIndex[&file];
Pete Cooper80c09742016-01-14 21:53:13 +000051 bool undefAdded = false;
Shankar Easwarana96f3a32013-10-07 02:47:09 +000052 do {
Rui Ueyama13003d72015-03-06 00:28:41 +000053 for (; i < _undefines.size(); ++i) {
54 StringRef undefName = _undefines[i];
55 if (undefName.empty())
56 continue;
Rui Ueyama803150c2015-03-08 21:31:38 +000057 const Atom *atom = _symbolTable.findByName(undefName);
58 if (!isa<UndefinedAtom>(atom) || _symbolTable.isCoalescedAway(atom)) {
Rui Ueyama13003d72015-03-06 00:28:41 +000059 // The symbol was resolved by some other file. Cache the result.
60 _undefines[i] = "";
61 continue;
Shankar Easwarana96f3a32013-10-07 02:47:09 +000062 }
Rui Ueyama46a8e292016-03-28 20:59:47 +000063 auto undefAddedOrError = callback(undefName);
Pete Cooper80c09742016-01-14 21:53:13 +000064 if (undefAddedOrError.getError())
65 return undefAddedOrError;
66 undefAdded |= undefAddedOrError.get();
Shankar Easwarana96f3a32013-10-07 02:47:09 +000067 }
Rui Ueyama13003d72015-03-06 00:28:41 +000068 } while (i < _undefines.size());
69 _undefineIndex[&file] = i;
Pete Cooper80c09742016-01-14 21:53:13 +000070 return undefAdded;
Shankar Easwarana96f3a32013-10-07 02:47:09 +000071}
72
Pete Cooper80c09742016-01-14 21:53:13 +000073ErrorOr<bool> Resolver::handleArchiveFile(File &file) {
Rui Ueyama394d10e2015-03-04 04:36:46 +000074 ArchiveLibraryFile *archiveFile = cast<ArchiveLibraryFile>(&file);
Rui Ueyama46a8e292016-03-28 20:59:47 +000075 return forEachUndefines(file, [&](StringRef undefName) -> ErrorOr<bool> {
76 if (File *member = archiveFile->find(undefName)) {
Rui Ueyamab2e16972015-02-27 23:40:00 +000077 member->setOrdinal(_ctx.getNextOrdinalAndIncrement());
Pete Cooper80c09742016-01-14 21:53:13 +000078 return handleFile(*member);
Rui Ueyama3429d012013-11-15 04:58:54 +000079 }
Pete Cooper80c09742016-01-14 21:53:13 +000080 return false;
Rui Ueyama0b8e0532014-04-04 00:39:37 +000081 });
Rui Ueyama3429d012013-11-15 04:58:54 +000082}
Shankar Easwarana96f3a32013-10-07 02:47:09 +000083
Pete Cooper80c09742016-01-14 21:53:13 +000084std::error_code Resolver::handleSharedLibrary(File &file) {
Shankar Easwarana96f3a32013-10-07 02:47:09 +000085 // Add all the atoms from the shared library
Rui Ueyama394d10e2015-03-04 04:36:46 +000086 SharedLibraryFile *sharedLibrary = cast<SharedLibraryFile>(&file);
Pete Cooper80c09742016-01-14 21:53:13 +000087 auto undefAddedOrError = handleFile(*sharedLibrary);
88 if (undefAddedOrError.getError())
89 return undefAddedOrError.getError();
Rui Ueyama46a8e292016-03-28 20:59:47 +000090 undefAddedOrError =
91 forEachUndefines(file, [&](StringRef undefName) -> ErrorOr<bool> {
92 auto atom = sharedLibrary->exports(undefName);
93 if (atom.get())
94 doSharedLibraryAtom(std::move(atom));
95 return false;
96 });
Pete Cooper80c09742016-01-14 21:53:13 +000097
98 if (undefAddedOrError.getError())
99 return undefAddedOrError.getError();
100 return std::error_code();
Shankar Easwarana96f3a32013-10-07 02:47:09 +0000101}
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000102
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000103bool Resolver::doUndefinedAtom(OwningAtomPtr<UndefinedAtom> atom) {
Nick Kledzikabb69812012-05-31 22:34:00 +0000104 DEBUG_WITH_TYPE("resolver", llvm::dbgs()
105 << " UndefinedAtom: "
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000106 << llvm::format("0x%09lX", atom.get())
107 << ", name=" << atom.get()->name() << "\n");
Pete Cooper3e4d7322016-03-22 04:00:41 +0000108
109 // tell symbol table
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000110 bool newUndefAdded = _symbolTable.add(*atom.get());
Pete Cooper3e4d7322016-03-22 04:00:41 +0000111 if (newUndefAdded)
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000112 _undefines.push_back(atom.get()->name());
113
114 // add to list of known atoms
115 _atoms.push_back(OwningAtomPtr<Atom>(atom.release()));
Rui Ueyama70625fb2014-04-03 22:21:59 +0000116
Rui Ueyama2a522512014-05-14 17:29:27 +0000117 return newUndefAdded;
Nick Kledzikf4fb2c52012-01-11 01:06:19 +0000118}
119
Rui Ueyama2a522512014-05-14 17:29:27 +0000120// Called on each atom when a file is added. Returns true if a given
121// atom is added to the symbol table.
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000122void Resolver::doDefinedAtom(OwningAtomPtr<DefinedAtom> atom) {
Nick Kledzikabb69812012-05-31 22:34:00 +0000123 DEBUG_WITH_TYPE("resolver", llvm::dbgs()
124 << " DefinedAtom: "
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000125 << llvm::format("0x%09lX", atom.get())
Nick Kledzik36293f62013-01-23 22:32:56 +0000126 << ", file=#"
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000127 << atom.get()->file().ordinal()
Nick Kledzik36293f62013-01-23 22:32:56 +0000128 << ", atom=#"
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000129 << atom.get()->ordinal()
Nick Kledzikabb69812012-05-31 22:34:00 +0000130 << ", name="
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000131 << atom.get()->name()
Pete Coopere5fa5a32015-12-16 22:03:21 +0000132 << ", type="
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000133 << atom.get()->contentType()
Nick Kledzikabb69812012-05-31 22:34:00 +0000134 << "\n");
135
Rui Ueyama83e6acc2014-04-03 21:11:22 +0000136 // An atom that should never be dead-stripped is a dead-strip root.
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000137 if (_ctx.deadStrip() &&
138 atom.get()->deadStrip() == DefinedAtom::deadStripNever) {
139 _deadStripRoots.insert(atom.get());
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000140 }
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000141
142 // add to list of known atoms
143 _symbolTable.add(*atom.get());
144 _atoms.push_back(OwningAtomPtr<Atom>(atom.release()));
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000145}
146
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000147void Resolver::doSharedLibraryAtom(OwningAtomPtr<SharedLibraryAtom> atom) {
Rui Ueyamafd133b32013-11-21 23:41:53 +0000148 DEBUG_WITH_TYPE("resolver", llvm::dbgs()
Nick Kledzikabb69812012-05-31 22:34:00 +0000149 << " SharedLibraryAtom: "
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000150 << llvm::format("0x%09lX", atom.get())
Nick Kledzikabb69812012-05-31 22:34:00 +0000151 << ", name="
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000152 << atom.get()->name()
Nick Kledzikabb69812012-05-31 22:34:00 +0000153 << "\n");
154
Pete Cooper3e4d7322016-03-22 04:00:41 +0000155 // tell symbol table
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000156 _symbolTable.add(*atom.get());
157
158 // add to list of known atoms
159 _atoms.push_back(OwningAtomPtr<Atom>(atom.release()));
Nick Kledzik6bc04c62012-02-22 21:56:59 +0000160}
Michael J. Spencer765792d2012-04-03 18:40:27 +0000161
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000162void Resolver::doAbsoluteAtom(OwningAtomPtr<AbsoluteAtom> atom) {
Rui Ueyamafd133b32013-11-21 23:41:53 +0000163 DEBUG_WITH_TYPE("resolver", llvm::dbgs()
Nick Kledzikabb69812012-05-31 22:34:00 +0000164 << " AbsoluteAtom: "
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000165 << llvm::format("0x%09lX", atom.get())
Nick Kledzikabb69812012-05-31 22:34:00 +0000166 << ", name="
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000167 << atom.get()->name()
Nick Kledzikabb69812012-05-31 22:34:00 +0000168 << "\n");
169
Pete Cooper3e4d7322016-03-22 04:00:41 +0000170 // tell symbol table
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000171 if (atom.get()->scope() != Atom::scopeTranslationUnit)
172 _symbolTable.add(*atom.get());
Pete Cooper3e4d7322016-03-22 04:00:41 +0000173
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000174 // add to list of known atoms
175 _atoms.push_back(OwningAtomPtr<Atom>(atom.release()));
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000176}
177
Rui Ueyama00eb2572014-12-10 00:33:00 +0000178// Returns true if at least one of N previous files has created an
179// undefined symbol.
Rui Ueyama80c04432015-01-15 06:49:21 +0000180bool Resolver::undefinesAdded(int begin, int end) {
Rui Ueyamab2e16972015-02-27 23:40:00 +0000181 std::vector<std::unique_ptr<Node>> &inputs = _ctx.getNodes();
Rui Ueyama80c04432015-01-15 06:49:21 +0000182 for (int i = begin; i < end; ++i)
183 if (FileNode *node = dyn_cast<FileNode>(inputs[i].get()))
184 if (_newUndefinesAdded[node->getFile()])
Rui Ueyamad4730ea2015-01-16 15:54:13 +0000185 return true;
Rui Ueyama00eb2572014-12-10 00:33:00 +0000186 return false;
187}
188
Rui Ueyamabcf89182015-01-21 18:54:26 +0000189File *Resolver::getFile(int &index) {
Rui Ueyamab2e16972015-02-27 23:40:00 +0000190 std::vector<std::unique_ptr<Node>> &inputs = _ctx.getNodes();
Rui Ueyama80c04432015-01-15 06:49:21 +0000191 if ((size_t)index >= inputs.size())
192 return nullptr;
193 if (GroupEnd *group = dyn_cast<GroupEnd>(inputs[index].get())) {
Rui Ueyama00eb2572014-12-10 00:33:00 +0000194 // We are at the end of the current group. If one or more new
195 // undefined atom has been added in the last groupSize files, we
196 // reiterate over the files.
Rui Ueyama80c04432015-01-15 06:49:21 +0000197 int size = group->getSize();
198 if (undefinesAdded(index - size, index)) {
199 index -= size;
Rui Ueyamabcf89182015-01-21 18:54:26 +0000200 return getFile(index);
Rui Ueyama80c04432015-01-15 06:49:21 +0000201 }
202 ++index;
Rui Ueyamabcf89182015-01-21 18:54:26 +0000203 return getFile(index);
Rui Ueyama00eb2572014-12-10 00:33:00 +0000204 }
Rui Ueyama80c04432015-01-15 06:49:21 +0000205 return cast<FileNode>(inputs[index++].get())->getFile();
Rui Ueyama00eb2572014-12-10 00:33:00 +0000206}
207
Rui Ueyamab2e16972015-02-27 23:40:00 +0000208// Keep adding atoms until _ctx.getNextFile() returns an error. This
Rui Ueyama8bd093b2014-04-04 00:14:04 +0000209// function is where undefined atoms are resolved.
Rui Ueyamad4730ea2015-01-16 15:54:13 +0000210bool Resolver::resolveUndefines() {
Pete Cooper3e8f5652015-12-16 19:12:49 +0000211 DEBUG_WITH_TYPE("resolver",
212 llvm::dbgs() << "******** Resolving undefines:\n");
Michael J. Spencerbd66d042013-05-28 18:55:39 +0000213 ScopedTask task(getDefaultDomain(), "resolveUndefines");
Rui Ueyama80c04432015-01-15 06:49:21 +0000214 int index = 0;
Rui Ueyamabcf89182015-01-21 18:54:26 +0000215 std::set<File *> seen;
Rui Ueyamad542b9e2013-10-11 03:48:06 +0000216 for (;;) {
Rui Ueyama00eb2572014-12-10 00:33:00 +0000217 bool undefAdded = false;
Pete Cooper3e8f5652015-12-16 19:12:49 +0000218 DEBUG_WITH_TYPE("resolver",
219 llvm::dbgs() << "Loading file #" << index << "\n");
Rui Ueyamabcf89182015-01-21 18:54:26 +0000220 File *file = getFile(index);
Rui Ueyamae9b45512014-12-14 02:04:01 +0000221 if (!file)
Rui Ueyamad4730ea2015-01-16 15:54:13 +0000222 return true;
223 if (std::error_code ec = file->parse()) {
224 llvm::errs() << "Cannot open " + file->path()
225 << ": " << ec.message() << "\n";
226 return false;
227 }
Pete Cooper3e8f5652015-12-16 19:12:49 +0000228 DEBUG_WITH_TYPE("resolver",
229 llvm::dbgs() << "Loaded file: " << file->path() << "\n");
Rui Ueyamad542b9e2013-10-11 03:48:06 +0000230 switch (file->kind()) {
Pete Cooperf0c0f3c2016-01-14 22:55:38 +0000231 case File::kindErrorObject:
232 case File::kindNormalizedObject:
233 case File::kindMachObject:
Pete Cooperf0c0f3c2016-01-14 22:55:38 +0000234 case File::kindCEntryObject:
Pete Cooperd4f41452016-02-02 21:37:15 +0000235 case File::kindHeaderObject:
Pete Cooperf0c0f3c2016-01-14 22:55:38 +0000236 case File::kindEntryObject:
237 case File::kindUndefinedSymsObject:
Pete Cooperf0c0f3c2016-01-14 22:55:38 +0000238 case File::kindStubHelperObject:
239 case File::kindResolverMergedObject:
240 case File::kindSectCreateObject: {
Rui Ueyamabcf89182015-01-21 18:54:26 +0000241 // The same file may be visited more than once if the file is
242 // in --start-group and --end-group. Only library files should
243 // be processed more than once.
244 if (seen.count(file))
Rui Ueyama00eb2572014-12-10 00:33:00 +0000245 break;
Rui Ueyamabcf89182015-01-21 18:54:26 +0000246 seen.insert(file);
Rui Ueyamad542b9e2013-10-11 03:48:06 +0000247 assert(!file->hasOrdinal());
Rui Ueyamab2e16972015-02-27 23:40:00 +0000248 file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
Pete Cooper80c09742016-01-14 21:53:13 +0000249 auto undefAddedOrError = handleFile(*file);
250 if (undefAddedOrError.getError()) {
251 llvm::errs() << "Error in " + file->path()
252 << ": " << undefAddedOrError.getError().message() << "\n";
253 return false;
254 }
255 undefAdded = undefAddedOrError.get();
Shankar Easwarana96f3a32013-10-07 02:47:09 +0000256 break;
Pete Cooper80c09742016-01-14 21:53:13 +0000257 }
258 case File::kindArchiveLibrary: {
Rui Ueyamad542b9e2013-10-11 03:48:06 +0000259 if (!file->hasOrdinal())
Rui Ueyamab2e16972015-02-27 23:40:00 +0000260 file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
Pete Cooper80c09742016-01-14 21:53:13 +0000261 auto undefAddedOrError = handleArchiveFile(*file);
262 if (undefAddedOrError.getError()) {
263 llvm::errs() << "Error in " + file->path()
264 << ": " << undefAddedOrError.getError().message() << "\n";
265 return false;
266 }
267 undefAdded = undefAddedOrError.get();
Rui Ueyamad542b9e2013-10-11 03:48:06 +0000268 break;
Pete Cooper80c09742016-01-14 21:53:13 +0000269 }
Rui Ueyamad542b9e2013-10-11 03:48:06 +0000270 case File::kindSharedLibrary:
271 if (!file->hasOrdinal())
Rui Ueyamab2e16972015-02-27 23:40:00 +0000272 file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
Pete Cooper80c09742016-01-14 21:53:13 +0000273 if (auto EC = handleSharedLibrary(*file)) {
274 llvm::errs() << "Error in " + file->path()
275 << ": " << EC.message() << "\n";
276 return false;
277 }
Rui Ueyamad542b9e2013-10-11 03:48:06 +0000278 break;
Shankar Easwaran1d3c48f2013-10-09 05:23:23 +0000279 }
Rui Ueyama80c04432015-01-15 06:49:21 +0000280 _newUndefinesAdded[file] = undefAdded;
Shankar Easwarana96f3a32013-10-07 02:47:09 +0000281 }
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000282}
283
284// switch all references to undefined or coalesced away atoms
285// to the new defined atom
286void Resolver::updateReferences() {
Pete Cooper3e8f5652015-12-16 19:12:49 +0000287 DEBUG_WITH_TYPE("resolver",
288 llvm::dbgs() << "******** Updating references:\n");
Michael J. Spencerbd66d042013-05-28 18:55:39 +0000289 ScopedTask task(getDefaultDomain(), "updateReferences");
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000290 for (const OwningAtomPtr<Atom> &atom : _atoms) {
291 if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom.get())) {
Nick Kledzik062a98c2012-04-08 23:52:13 +0000292 for (const Reference *ref : *defAtom) {
Rui Ueyama61d7f972014-06-17 16:19:33 +0000293 // A reference of type kindAssociate should't be updated.
294 // Instead, an atom having such reference will be removed
295 // if the target atom is coalesced away, so that they will
296 // go away as a group.
297 if (ref->kindNamespace() == lld::Reference::KindNamespace::all &&
298 ref->kindValue() == lld::Reference::kindAssociate) {
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000299 if (_symbolTable.isCoalescedAway(atom.get()))
Rui Ueyama61d7f972014-06-17 16:19:33 +0000300 _deadAtoms.insert(ref->target());
301 continue;
302 }
Rui Ueyamafd133b32013-11-21 23:41:53 +0000303 const Atom *newTarget = _symbolTable.replacement(ref->target());
304 const_cast<Reference *>(ref)->setTarget(newTarget);
Nick Kledzik1a6615d2012-03-08 00:18:30 +0000305 }
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000306 }
307 }
308}
309
Rui Ueyamae5531fa2013-12-26 07:13:28 +0000310// For dead code stripping, recursively mark atoms "live"
Rui Ueyama6ffe42e2014-06-02 08:06:57 +0000311void Resolver::markLive(const Atom *atom) {
Rui Ueyamae5531fa2013-12-26 07:13:28 +0000312 // Mark the atom is live. If it's already marked live, then stop recursion.
Rui Ueyama6ffe42e2014-06-02 08:06:57 +0000313 auto exists = _liveAtoms.insert(atom);
Rui Ueyamae5531fa2013-12-26 07:13:28 +0000314 if (!exists.second)
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000315 return;
316
Rui Ueyamae5531fa2013-12-26 07:13:28 +0000317 // Mark all atoms it references as live
Rui Ueyama23487e82014-06-03 01:59:02 +0000318 if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom)) {
Rui Ueyamac481b5b2013-12-26 07:02:33 +0000319 for (const Reference *ref : *defAtom)
Rui Ueyama6ffe42e2014-06-02 08:06:57 +0000320 markLive(ref->target());
Rui Ueyama25d5abd2015-03-06 00:22:48 +0000321 for (auto &p : llvm::make_range(_reverseRef.equal_range(defAtom))) {
322 const Atom *target = p.second;
Rui Ueyamad20d44f2014-09-26 23:21:10 +0000323 markLive(target);
Rui Ueyama25d5abd2015-03-06 00:22:48 +0000324 }
Rui Ueyama23487e82014-06-03 01:59:02 +0000325 }
326}
327
328static bool isBackref(const Reference *ref) {
Rui Ueyama9aee0502014-06-03 03:07:49 +0000329 if (ref->kindNamespace() != lld::Reference::KindNamespace::all)
330 return false;
Rafael Espindolafd149792016-02-28 16:03:37 +0000331 return (ref->kindValue() == lld::Reference::kindLayoutAfter);
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000332}
333
334// remove all atoms not actually used
Rui Ueyamaf3630fe2013-10-16 19:21:50 +0000335void Resolver::deadStripOptimize() {
Pete Cooper3e8f5652015-12-16 19:12:49 +0000336 DEBUG_WITH_TYPE("resolver",
337 llvm::dbgs() << "******** Dead stripping unused atoms:\n");
Michael J. Spencerbd66d042013-05-28 18:55:39 +0000338 ScopedTask task(getDefaultDomain(), "deadStripOptimize");
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000339 // only do this optimization with -dead_strip
Rui Ueyamab2e16972015-02-27 23:40:00 +0000340 if (!_ctx.deadStrip())
Rui Ueyamaf3630fe2013-10-16 19:21:50 +0000341 return;
Rui Ueyama23487e82014-06-03 01:59:02 +0000342
343 // Some type of references prevent referring atoms to be dead-striped.
344 // Make a reverse map of such references before traversing the graph.
Davide Italianoa82ae912015-02-26 05:39:57 +0000345 // While traversing the list of atoms, mark AbsoluteAtoms as live
346 // in order to avoid reclaim.
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000347 for (const OwningAtomPtr<Atom> &atom : _atoms) {
348 if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom.get()))
Rui Ueyama23487e82014-06-03 01:59:02 +0000349 for (const Reference *ref : *defAtom)
350 if (isBackref(ref))
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000351 _reverseRef.insert(std::make_pair(ref->target(), atom.get()));
352 if (const AbsoluteAtom *absAtom = dyn_cast<AbsoluteAtom>(atom.get()))
Davide Italianoa82ae912015-02-26 05:39:57 +0000353 markLive(absAtom);
354 }
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000355
Nick Kledzikbb963df2012-04-18 21:55:06 +0000356 // By default, shared libraries are built with all globals as dead strip roots
Rui Ueyamab2e16972015-02-27 23:40:00 +0000357 if (_ctx.globalsAreDeadStripRoots())
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000358 for (const OwningAtomPtr<Atom> &atom : _atoms)
359 if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom.get()))
Rui Ueyama517f0d92014-04-03 21:16:37 +0000360 if (defAtom->scope() == DefinedAtom::scopeGlobal)
361 _deadStripRoots.insert(defAtom);
Nick Kledzikabb69812012-05-31 22:34:00 +0000362
Joerg Sonnenberger03ed4cf2014-01-03 18:43:32 +0000363 // Or, use list of names that are dead strip roots.
Rui Ueyamab2e16972015-02-27 23:40:00 +0000364 for (const StringRef &name : _ctx.deadStripRoots()) {
Nick Kledzikbb963df2012-04-18 21:55:06 +0000365 const Atom *symAtom = _symbolTable.findByName(name);
Rui Ueyamaf3630fe2013-10-16 19:21:50 +0000366 assert(symAtom);
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000367 _deadStripRoots.insert(symAtom);
368 }
369
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000370 // mark all roots as live, and recursively all atoms they reference
Rui Ueyamac53b3b02013-12-10 06:19:09 +0000371 for (const Atom *dsrAtom : _deadStripRoots)
Rui Ueyama6ffe42e2014-06-02 08:06:57 +0000372 markLive(dsrAtom);
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000373
374 // now remove all non-live atoms from _atoms
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000375 _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(),
376 [&](OwningAtomPtr<Atom> &a) {
377 return _liveAtoms.count(a.get()) == 0;
Rui Ueyama450d9872014-04-03 22:24:40 +0000378 }),
379 _atoms.end());
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000380}
381
382// error out if some undefines remain
Rui Ueyama43a589c2014-04-02 06:38:46 +0000383bool Resolver::checkUndefines() {
Pete Cooper3e8f5652015-12-16 19:12:49 +0000384 DEBUG_WITH_TYPE("resolver",
385 llvm::dbgs() << "******** Checking for undefines:\n");
386
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000387 // build vector of remaining undefined symbols
Rui Ueyama8dc9f0a2014-04-04 00:15:52 +0000388 std::vector<const UndefinedAtom *> undefinedAtoms = _symbolTable.undefines();
Rui Ueyamab2e16972015-02-27 23:40:00 +0000389 if (_ctx.deadStrip()) {
Nick Kledzikbb963df2012-04-18 21:55:06 +0000390 // When dead code stripping, we don't care if dead atoms are undefined.
Rui Ueyama450d9872014-04-03 22:24:40 +0000391 undefinedAtoms.erase(
392 std::remove_if(undefinedAtoms.begin(), undefinedAtoms.end(),
393 [&](const Atom *a) { return _liveAtoms.count(a) == 0; }),
394 undefinedAtoms.end());
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000395 }
396
Rui Ueyama6780cea2015-03-05 20:22:14 +0000397 if (undefinedAtoms.empty())
398 return false;
Michael J. Spencer9d70cef2013-04-24 19:00:26 +0000399
Rui Ueyama6780cea2015-03-05 20:22:14 +0000400 // Warn about unresolved symbols.
401 bool foundUndefines = false;
402 for (const UndefinedAtom *undef : undefinedAtoms) {
403 // Skip over a weak symbol.
404 if (undef->canBeNull() != UndefinedAtom::canBeNullNever)
405 continue;
Michael J. Spencer9d70cef2013-04-24 19:00:26 +0000406
Rui Ueyama6780cea2015-03-05 20:22:14 +0000407 // If this is a library and undefined symbols are allowed on the
408 // target platform, skip over it.
409 if (isa<SharedLibraryFile>(undef->file()) && _ctx.allowShlibUndefines())
410 continue;
Rui Ueyama6f3254962013-09-12 21:42:52 +0000411
Rui Ueyama6780cea2015-03-05 20:22:14 +0000412 // If the undefine is coalesced away, skip over it.
413 if (_symbolTable.isCoalescedAway(undef))
414 continue;
415
416 // Seems like this symbol is undefined. Warn that.
417 foundUndefines = true;
418 if (_ctx.printRemainingUndefines()) {
419 llvm::errs() << "Undefined symbol: " << undef->file().path()
420 << ": " << _ctx.demangle(undef->name())
421 << "\n";
Nick Kledzikc314b462013-04-04 18:59:24 +0000422 }
Nick Kledzikbb963df2012-04-18 21:55:06 +0000423 }
Rui Ueyama6780cea2015-03-05 20:22:14 +0000424 if (!foundUndefines)
425 return false;
426 if (_ctx.printRemainingUndefines())
427 llvm::errs() << "symbol(s) not found\n";
428 return true;
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000429}
430
431// remove from _atoms all coaleseced away atoms
432void Resolver::removeCoalescedAwayAtoms() {
Pete Cooper3e8f5652015-12-16 19:12:49 +0000433 DEBUG_WITH_TYPE("resolver",
434 llvm::dbgs() << "******** Removing coalesced away atoms:\n");
Michael J. Spencerbd66d042013-05-28 18:55:39 +0000435 ScopedTask task(getDefaultDomain(), "removeCoalescedAwayAtoms");
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000436 _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(),
437 [&](OwningAtomPtr<Atom> &a) {
438 return _symbolTable.isCoalescedAway(a.get()) ||
439 _deadAtoms.count(a.get());
Rui Ueyama733b45f2014-06-05 07:37:29 +0000440 }),
Rui Ueyamafd133b32013-11-21 23:41:53 +0000441 _atoms.end());
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000442}
443
Nick Kledzikc314b462013-04-04 18:59:24 +0000444bool Resolver::resolve() {
Pete Cooper3e8f5652015-12-16 19:12:49 +0000445 DEBUG_WITH_TYPE("resolver",
446 llvm::dbgs() << "******** Resolving atom references:\n");
Rui Ueyamad4730ea2015-01-16 15:54:13 +0000447 if (!resolveUndefines())
448 return false;
Rui Ueyama2b2ac912014-04-03 18:13:14 +0000449 updateReferences();
450 deadStripOptimize();
Pete Cooper3e8f5652015-12-16 19:12:49 +0000451 if (checkUndefines()) {
452 DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "Found undefines... ");
453 if (!_ctx.allowRemainingUndefines()) {
454 DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "which we don't allow\n");
Rui Ueyamaee366042013-10-11 06:16:33 +0000455 return false;
Pete Cooper3e8f5652015-12-16 19:12:49 +0000456 }
457 DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "which we are ok with\n");
458 }
Rui Ueyama2b2ac912014-04-03 18:13:14 +0000459 removeCoalescedAwayAtoms();
460 _result->addAtoms(_atoms);
Pete Cooper3e8f5652015-12-16 19:12:49 +0000461 DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "******** Finished resolver\n");
Rui Ueyamaee366042013-10-11 06:16:33 +0000462 return true;
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000463}
464
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000465void Resolver::MergedFile::addAtoms(
466 llvm::MutableArrayRef<OwningAtomPtr<Atom>> all) {
Michael J. Spencerbd66d042013-05-28 18:55:39 +0000467 ScopedTask task(getDefaultDomain(), "addAtoms");
Nick Kledzikabb69812012-05-31 22:34:00 +0000468 DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "Resolver final atom list:\n");
Pete Coopere5fa5a32015-12-16 22:03:21 +0000469
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000470 for (OwningAtomPtr<Atom> &atom : all) {
Pete Coopere5fa5a32015-12-16 22:03:21 +0000471#ifndef NDEBUG
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000472 if (auto *definedAtom = dyn_cast<DefinedAtom>(atom.get())) {
Pete Coopere5fa5a32015-12-16 22:03:21 +0000473 DEBUG_WITH_TYPE("resolver", llvm::dbgs()
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000474 << llvm::format(" 0x%09lX", definedAtom)
Pete Coopere5fa5a32015-12-16 22:03:21 +0000475 << ", file=#"
476 << definedAtom->file().ordinal()
477 << ", atom=#"
478 << definedAtom->ordinal()
479 << ", name="
480 << definedAtom->name()
481 << ", type="
482 << definedAtom->contentType()
483 << "\n");
484 } else {
485 DEBUG_WITH_TYPE("resolver", llvm::dbgs()
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000486 << llvm::format(" 0x%09lX", atom.get())
Pete Coopere5fa5a32015-12-16 22:03:21 +0000487 << ", name="
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000488 << atom.get()->name()
Pete Coopere5fa5a32015-12-16 22:03:21 +0000489 << "\n");
490 }
491#endif
Pete Cooper8ad55fb2016-03-22 17:15:50 +0000492 addAtom(*atom.release());
Nick Kledzik1a6615d2012-03-08 00:18:30 +0000493 }
494}
495
Michael J. Spencer773a8fb2011-12-18 08:27:59 +0000496} // namespace lld