1 //===- Core/Resolver.cpp - Resolves Atom References -----------------------===//
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "lld/Core/Resolver.h"
11 #include "lld/Common/LLVM.h"
12 #include "lld/Core/ArchiveLibraryFile.h"
13 #include "lld/Core/Atom.h"
14 #include "lld/Core/File.h"
15 #include "lld/Core/Instrumentation.h"
16 #include "lld/Core/LinkingContext.h"
17 #include "lld/Core/SharedLibraryFile.h"
18 #include "lld/Core/SymbolTable.h"
19 #include "lld/Core/UndefinedAtom.h"
20 #include "llvm/ADT/iterator_range.h"
21 #include "llvm/Support/Debug.h"
22 #include "llvm/Support/Error.h"
23 #include "llvm/Support/ErrorHandling.h"
24 #include "llvm/Support/Format.h"
25 #include "llvm/Support/raw_ostream.h"
33 llvm::Expected<bool> Resolver::handleFile(File &file) {
34 if (auto ec = _ctx.handleLoadedFile(file))
36 bool undefAdded = false;
37 for (auto &atom : file.defined().owning_ptrs())
38 doDefinedAtom(std::move(atom));
39 for (auto &atom : file.undefined().owning_ptrs()) {
40 if (doUndefinedAtom(std::move(atom)))
43 for (auto &atom : file.sharedLibrary().owning_ptrs())
44 doSharedLibraryAtom(std::move(atom));
45 for (auto &atom : file.absolute().owning_ptrs())
46 doAbsoluteAtom(std::move(atom));
50 llvm::Expected<bool> Resolver::forEachUndefines(File &file,
51 UndefCallback callback) {
52 size_t i = _undefineIndex[&file];
53 bool undefAdded = false;
55 for (; i < _undefines.size(); ++i) {
56 StringRef undefName = _undefines[i];
57 if (undefName.empty())
59 const Atom *atom = _symbolTable.findByName(undefName);
60 if (!isa<UndefinedAtom>(atom) || _symbolTable.isCoalescedAway(atom)) {
61 // The symbol was resolved by some other file. Cache the result.
65 auto undefAddedOrError = callback(undefName);
66 if (auto ec = undefAddedOrError.takeError())
68 undefAdded |= undefAddedOrError.get();
70 } while (i < _undefines.size());
71 _undefineIndex[&file] = i;
75 llvm::Expected<bool> Resolver::handleArchiveFile(File &file) {
76 ArchiveLibraryFile *archiveFile = cast<ArchiveLibraryFile>(&file);
77 return forEachUndefines(file,
78 [&](StringRef undefName) -> llvm::Expected<bool> {
79 if (File *member = archiveFile->find(undefName)) {
80 member->setOrdinal(_ctx.getNextOrdinalAndIncrement());
81 return handleFile(*member);
87 llvm::Error Resolver::handleSharedLibrary(File &file) {
88 // Add all the atoms from the shared library
89 SharedLibraryFile *sharedLibrary = cast<SharedLibraryFile>(&file);
90 auto undefAddedOrError = handleFile(*sharedLibrary);
91 if (auto ec = undefAddedOrError.takeError())
94 forEachUndefines(file, [&](StringRef undefName) -> llvm::Expected<bool> {
95 auto atom = sharedLibrary->exports(undefName);
97 doSharedLibraryAtom(std::move(atom));
101 if (auto ec = undefAddedOrError.takeError())
103 return llvm::Error::success();
106 bool Resolver::doUndefinedAtom(OwningAtomPtr<UndefinedAtom> atom) {
107 DEBUG_WITH_TYPE("resolver", llvm::dbgs()
108 << " UndefinedAtom: "
109 << llvm::format("0x%09lX", atom.get())
110 << ", name=" << atom.get()->name() << "\n");
113 bool newUndefAdded = _symbolTable.add(*atom.get());
115 _undefines.push_back(atom.get()->name());
117 // add to list of known atoms
118 _atoms.push_back(OwningAtomPtr<Atom>(atom.release()));
120 return newUndefAdded;
123 // Called on each atom when a file is added. Returns true if a given
124 // atom is added to the symbol table.
125 void Resolver::doDefinedAtom(OwningAtomPtr<DefinedAtom> atom) {
126 DEBUG_WITH_TYPE("resolver", llvm::dbgs()
128 << llvm::format("0x%09lX", atom.get())
130 << atom.get()->file().ordinal()
132 << atom.get()->ordinal()
134 << atom.get()->name()
136 << atom.get()->contentType()
139 // An atom that should never be dead-stripped is a dead-strip root.
140 if (_ctx.deadStrip() &&
141 atom.get()->deadStrip() == DefinedAtom::deadStripNever) {
142 _deadStripRoots.insert(atom.get());
145 // add to list of known atoms
146 _symbolTable.add(*atom.get());
147 _atoms.push_back(OwningAtomPtr<Atom>(atom.release()));
150 void Resolver::doSharedLibraryAtom(OwningAtomPtr<SharedLibraryAtom> atom) {
151 DEBUG_WITH_TYPE("resolver", llvm::dbgs()
152 << " SharedLibraryAtom: "
153 << llvm::format("0x%09lX", atom.get())
155 << atom.get()->name()
159 _symbolTable.add(*atom.get());
161 // add to list of known atoms
162 _atoms.push_back(OwningAtomPtr<Atom>(atom.release()));
165 void Resolver::doAbsoluteAtom(OwningAtomPtr<AbsoluteAtom> atom) {
166 DEBUG_WITH_TYPE("resolver", llvm::dbgs()
168 << llvm::format("0x%09lX", atom.get())
170 << atom.get()->name()
174 if (atom.get()->scope() != Atom::scopeTranslationUnit)
175 _symbolTable.add(*atom.get());
177 // add to list of known atoms
178 _atoms.push_back(OwningAtomPtr<Atom>(atom.release()));
181 // Returns true if at least one of N previous files has created an
183 bool Resolver::undefinesAdded(int begin, int end) {
184 std::vector<std::unique_ptr<Node>> &inputs = _ctx.getNodes();
185 for (int i = begin; i < end; ++i)
186 if (FileNode *node = dyn_cast<FileNode>(inputs[i].get()))
187 if (_newUndefinesAdded[node->getFile()])
192 File *Resolver::getFile(int &index) {
193 std::vector<std::unique_ptr<Node>> &inputs = _ctx.getNodes();
194 if ((size_t)index >= inputs.size())
196 if (GroupEnd *group = dyn_cast<GroupEnd>(inputs[index].get())) {
197 // We are at the end of the current group. If one or more new
198 // undefined atom has been added in the last groupSize files, we
199 // reiterate over the files.
200 int size = group->getSize();
201 if (undefinesAdded(index - size, index)) {
203 return getFile(index);
206 return getFile(index);
208 return cast<FileNode>(inputs[index++].get())->getFile();
211 // Keep adding atoms until _ctx.getNextFile() returns an error. This
212 // function is where undefined atoms are resolved.
213 bool Resolver::resolveUndefines() {
214 DEBUG_WITH_TYPE("resolver",
215 llvm::dbgs() << "******** Resolving undefines:\n");
216 ScopedTask task(getDefaultDomain(), "resolveUndefines");
218 std::set<File *> seen;
220 bool undefAdded = false;
221 DEBUG_WITH_TYPE("resolver",
222 llvm::dbgs() << "Loading file #" << index << "\n");
223 File *file = getFile(index);
226 if (std::error_code ec = file->parse()) {
227 llvm::errs() << "Cannot open " + file->path()
228 << ": " << ec.message() << "\n";
231 DEBUG_WITH_TYPE("resolver",
232 llvm::dbgs() << "Loaded file: " << file->path() << "\n");
233 switch (file->kind()) {
234 case File::kindErrorObject:
235 case File::kindNormalizedObject:
236 case File::kindMachObject:
237 case File::kindCEntryObject:
238 case File::kindHeaderObject:
239 case File::kindEntryObject:
240 case File::kindUndefinedSymsObject:
241 case File::kindStubHelperObject:
242 case File::kindResolverMergedObject:
243 case File::kindSectCreateObject: {
244 // The same file may be visited more than once if the file is
245 // in --start-group and --end-group. Only library files should
246 // be processed more than once.
247 if (seen.count(file))
250 assert(!file->hasOrdinal());
251 file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
252 auto undefAddedOrError = handleFile(*file);
253 if (auto EC = undefAddedOrError.takeError()) {
254 // FIXME: This should be passed to logAllUnhandledErrors but it needs
255 // to be passed a Twine instead of a string.
256 llvm::errs() << "Error in " + file->path() << ": ";
257 logAllUnhandledErrors(std::move(EC), llvm::errs(), std::string());
260 undefAdded = undefAddedOrError.get();
263 case File::kindArchiveLibrary: {
264 if (!file->hasOrdinal())
265 file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
266 auto undefAddedOrError = handleArchiveFile(*file);
267 if (auto EC = undefAddedOrError.takeError()) {
268 // FIXME: This should be passed to logAllUnhandledErrors but it needs
269 // to be passed a Twine instead of a string.
270 llvm::errs() << "Error in " + file->path() << ": ";
271 logAllUnhandledErrors(std::move(EC), llvm::errs(), std::string());
274 undefAdded = undefAddedOrError.get();
277 case File::kindSharedLibrary:
278 if (!file->hasOrdinal())
279 file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
280 if (auto EC = handleSharedLibrary(*file)) {
281 // FIXME: This should be passed to logAllUnhandledErrors but it needs
282 // to be passed a Twine instead of a string.
283 llvm::errs() << "Error in " + file->path() << ": ";
284 logAllUnhandledErrors(std::move(EC), llvm::errs(), std::string());
289 _newUndefinesAdded[file] = undefAdded;
293 // switch all references to undefined or coalesced away atoms
294 // to the new defined atom
295 void Resolver::updateReferences() {
296 DEBUG_WITH_TYPE("resolver",
297 llvm::dbgs() << "******** Updating references:\n");
298 ScopedTask task(getDefaultDomain(), "updateReferences");
299 for (const OwningAtomPtr<Atom> &atom : _atoms) {
300 if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom.get())) {
301 for (const Reference *ref : *defAtom) {
302 // A reference of type kindAssociate should't be updated.
303 // Instead, an atom having such reference will be removed
304 // if the target atom is coalesced away, so that they will
305 // go away as a group.
306 if (ref->kindNamespace() == lld::Reference::KindNamespace::all &&
307 ref->kindValue() == lld::Reference::kindAssociate) {
308 if (_symbolTable.isCoalescedAway(atom.get()))
309 _deadAtoms.insert(ref->target());
312 const Atom *newTarget = _symbolTable.replacement(ref->target());
313 const_cast<Reference *>(ref)->setTarget(newTarget);
319 // For dead code stripping, recursively mark atoms "live"
320 void Resolver::markLive(const Atom *atom) {
321 // Mark the atom is live. If it's already marked live, then stop recursion.
322 auto exists = _liveAtoms.insert(atom);
326 // Mark all atoms it references as live
327 if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom)) {
328 for (const Reference *ref : *defAtom)
329 markLive(ref->target());
330 for (auto &p : llvm::make_range(_reverseRef.equal_range(defAtom))) {
331 const Atom *target = p.second;
337 static bool isBackref(const Reference *ref) {
338 if (ref->kindNamespace() != lld::Reference::KindNamespace::all)
340 return (ref->kindValue() == lld::Reference::kindLayoutAfter);
343 // remove all atoms not actually used
344 void Resolver::deadStripOptimize() {
345 DEBUG_WITH_TYPE("resolver",
346 llvm::dbgs() << "******** Dead stripping unused atoms:\n");
347 ScopedTask task(getDefaultDomain(), "deadStripOptimize");
348 // only do this optimization with -dead_strip
349 if (!_ctx.deadStrip())
352 // Some type of references prevent referring atoms to be dead-striped.
353 // Make a reverse map of such references before traversing the graph.
354 // While traversing the list of atoms, mark AbsoluteAtoms as live
355 // in order to avoid reclaim.
356 for (const OwningAtomPtr<Atom> &atom : _atoms) {
357 if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom.get()))
358 for (const Reference *ref : *defAtom)
360 _reverseRef.insert(std::make_pair(ref->target(), atom.get()));
361 if (const AbsoluteAtom *absAtom = dyn_cast<AbsoluteAtom>(atom.get()))
365 // By default, shared libraries are built with all globals as dead strip roots
366 if (_ctx.globalsAreDeadStripRoots())
367 for (const OwningAtomPtr<Atom> &atom : _atoms)
368 if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom.get()))
369 if (defAtom->scope() == DefinedAtom::scopeGlobal)
370 _deadStripRoots.insert(defAtom);
372 // Or, use list of names that are dead strip roots.
373 for (const StringRef &name : _ctx.deadStripRoots()) {
374 const Atom *symAtom = _symbolTable.findByName(name);
376 _deadStripRoots.insert(symAtom);
379 // mark all roots as live, and recursively all atoms they reference
380 for (const Atom *dsrAtom : _deadStripRoots)
383 // now remove all non-live atoms from _atoms
384 _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(),
385 [&](OwningAtomPtr<Atom> &a) {
386 return _liveAtoms.count(a.get()) == 0;
391 // error out if some undefines remain
392 bool Resolver::checkUndefines() {
393 DEBUG_WITH_TYPE("resolver",
394 llvm::dbgs() << "******** Checking for undefines:\n");
396 // build vector of remaining undefined symbols
397 std::vector<const UndefinedAtom *> undefinedAtoms = _symbolTable.undefines();
398 if (_ctx.deadStrip()) {
399 // When dead code stripping, we don't care if dead atoms are undefined.
400 undefinedAtoms.erase(
401 std::remove_if(undefinedAtoms.begin(), undefinedAtoms.end(),
402 [&](const Atom *a) { return _liveAtoms.count(a) == 0; }),
403 undefinedAtoms.end());
406 if (undefinedAtoms.empty())
409 // Warn about unresolved symbols.
410 bool foundUndefines = false;
411 for (const UndefinedAtom *undef : undefinedAtoms) {
412 // Skip over a weak symbol.
413 if (undef->canBeNull() != UndefinedAtom::canBeNullNever)
416 // If this is a library and undefined symbols are allowed on the
417 // target platform, skip over it.
418 if (isa<SharedLibraryFile>(undef->file()) && _ctx.allowShlibUndefines())
421 // If the undefine is coalesced away, skip over it.
422 if (_symbolTable.isCoalescedAway(undef))
425 // Seems like this symbol is undefined. Warn that.
426 foundUndefines = true;
427 if (_ctx.printRemainingUndefines()) {
428 llvm::errs() << "Undefined symbol: " << undef->file().path()
429 << ": " << _ctx.demangle(undef->name())
435 if (_ctx.printRemainingUndefines())
436 llvm::errs() << "symbol(s) not found\n";
440 // remove from _atoms all coaleseced away atoms
441 void Resolver::removeCoalescedAwayAtoms() {
442 DEBUG_WITH_TYPE("resolver",
443 llvm::dbgs() << "******** Removing coalesced away atoms:\n");
444 ScopedTask task(getDefaultDomain(), "removeCoalescedAwayAtoms");
445 _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(),
446 [&](OwningAtomPtr<Atom> &a) {
447 return _symbolTable.isCoalescedAway(a.get()) ||
448 _deadAtoms.count(a.get());
453 bool Resolver::resolve() {
454 DEBUG_WITH_TYPE("resolver",
455 llvm::dbgs() << "******** Resolving atom references:\n");
456 if (!resolveUndefines())
460 if (checkUndefines()) {
461 DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "Found undefines... ");
462 if (!_ctx.allowRemainingUndefines()) {
463 DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "which we don't allow\n");
466 DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "which we are ok with\n");
468 removeCoalescedAwayAtoms();
469 _result->addAtoms(_atoms);
470 DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "******** Finished resolver\n");
474 void Resolver::MergedFile::addAtoms(
475 llvm::MutableArrayRef<OwningAtomPtr<Atom>> all) {
476 ScopedTask task(getDefaultDomain(), "addAtoms");
477 DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "Resolver final atom list:\n");
479 for (OwningAtomPtr<Atom> &atom : all) {
481 if (auto *definedAtom = dyn_cast<DefinedAtom>(atom.get())) {
482 DEBUG_WITH_TYPE("resolver", llvm::dbgs()
483 << llvm::format(" 0x%09lX", definedAtom)
485 << definedAtom->file().ordinal()
487 << definedAtom->ordinal()
489 << definedAtom->name()
491 << definedAtom->contentType()
494 DEBUG_WITH_TYPE("resolver", llvm::dbgs()
495 << llvm::format(" 0x%09lX", atom.get())
497 << atom.get()->name()
501 addAtom(*atom.release());