diff options
Diffstat (limited to 'lib/Core/Resolver.cpp')
| -rw-r--r-- | lib/Core/Resolver.cpp | 516 |
1 files changed, 516 insertions, 0 deletions
diff --git a/lib/Core/Resolver.cpp b/lib/Core/Resolver.cpp new file mode 100644 index 000000000000..393a7ef2bfc8 --- /dev/null +++ b/lib/Core/Resolver.cpp @@ -0,0 +1,516 @@ +//===- Core/Resolver.cpp - Resolves Atom References -----------------------===// +// +// The LLVM Linker +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "lld/Core/Atom.h" +#include "lld/Core/ArchiveLibraryFile.h" +#include "lld/Core/File.h" +#include "lld/Core/Instrumentation.h" +#include "lld/Core/LLVM.h" +#include "lld/Core/LinkingContext.h" +#include "lld/Core/Resolver.h" +#include "lld/Core/SharedLibraryFile.h" +#include "lld/Core/SymbolTable.h" +#include "lld/Core/UndefinedAtom.h" +#include "llvm/ADT/iterator_range.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/Format.h" +#include "llvm/Support/raw_ostream.h" +#include <algorithm> +#include <cassert> +#include <utility> +#include <vector> + +namespace lld { + +bool Resolver::handleFile(File &file) { + bool undefAdded = false; + for (const DefinedAtom *atom : file.defined()) + doDefinedAtom(*atom); + for (const UndefinedAtom *atom : file.undefined()) { + if (doUndefinedAtom(*atom)) { + undefAdded = true; + maybePreloadArchiveMember(atom->name()); + } + } + for (const SharedLibraryAtom *atom : file.sharedLibrary()) + doSharedLibraryAtom(*atom); + for (const AbsoluteAtom *atom : file.absolute()) + doAbsoluteAtom(*atom); + return undefAdded; +} + +void Resolver::forEachUndefines(File &file, bool searchForOverrides, + UndefCallback callback) { + size_t i = _undefineIndex[&file]; + do { + for (; i < _undefines.size(); ++i) { + StringRef undefName = _undefines[i]; + if (undefName.empty()) + continue; + const Atom *atom = _symbolTable.findByName(undefName); + if (!isa<UndefinedAtom>(atom) || _symbolTable.isCoalescedAway(atom)) { + // The symbol was resolved by some other file. Cache the result. + _undefines[i] = ""; + continue; + } + callback(undefName, false); + } + if (!searchForOverrides) + continue; + for (StringRef tentDefName : _symbolTable.tentativeDefinitions()) { + // Load for previous tentative may also have loaded + // something that overrode this tentative, so always check. + const Atom *curAtom = _symbolTable.findByName(tentDefName); + assert(curAtom != nullptr); + if (const DefinedAtom *curDefAtom = dyn_cast<DefinedAtom>(curAtom)) + if (curDefAtom->merge() == DefinedAtom::mergeAsTentative) + callback(tentDefName, true); + } + } while (i < _undefines.size()); + _undefineIndex[&file] = i; +} + +bool Resolver::handleArchiveFile(File &file) { + ArchiveLibraryFile *archiveFile = cast<ArchiveLibraryFile>(&file); + bool searchForOverrides = + _ctx.searchArchivesToOverrideTentativeDefinitions(); + bool undefAdded = false; + forEachUndefines(file, searchForOverrides, + [&](StringRef undefName, bool dataSymbolOnly) { + if (File *member = archiveFile->find(undefName, dataSymbolOnly)) { + member->setOrdinal(_ctx.getNextOrdinalAndIncrement()); + member->beforeLink(); + updatePreloadArchiveMap(); + undefAdded = handleFile(*member) || undefAdded; + } + }); + return undefAdded; +} + +void Resolver::handleSharedLibrary(File &file) { + // Add all the atoms from the shared library + SharedLibraryFile *sharedLibrary = cast<SharedLibraryFile>(&file); + handleFile(*sharedLibrary); + bool searchForOverrides = + _ctx.searchSharedLibrariesToOverrideTentativeDefinitions(); + forEachUndefines(file, searchForOverrides, + [&](StringRef undefName, bool dataSymbolOnly) { + if (const SharedLibraryAtom *atom = + sharedLibrary->exports(undefName, dataSymbolOnly)) + doSharedLibraryAtom(*atom); + }); +} + +bool Resolver::doUndefinedAtom(const UndefinedAtom &atom) { + DEBUG_WITH_TYPE("resolver", llvm::dbgs() + << " UndefinedAtom: " + << llvm::format("0x%09lX", &atom) + << ", name=" << atom.name() << "\n"); + + // add to list of known atoms + _atoms.push_back(&atom); + + // tell symbol table + bool newUndefAdded = _symbolTable.add(atom); + if (newUndefAdded) + _undefines.push_back(atom.name()); + + // If the undefined symbol has an alternative name, try to resolve the + // symbol with the name to give it a second chance. This feature is used + // for COFF "weak external" symbol. + if (newUndefAdded || !_symbolTable.isDefined(atom.name())) { + if (const UndefinedAtom *fallbackAtom = atom.fallback()) { + doUndefinedAtom(*fallbackAtom); + _symbolTable.addReplacement(&atom, fallbackAtom); + } + } + return newUndefAdded; +} + +/// \brief Add the section group and the group-child reference members. +void Resolver::maybeAddSectionGroupOrGnuLinkOnce(const DefinedAtom &atom) { + // First time adding a group? + bool isFirstTime = _symbolTable.addGroup(atom); + + if (!isFirstTime) { + // If duplicate symbols are allowed, select the first group. + if (_ctx.getAllowDuplicates()) + return; + auto *prevGroup = dyn_cast<DefinedAtom>(_symbolTable.findGroup(atom.name())); + assert(prevGroup && + "Internal Error: The group atom could only be a defined atom"); + // The atoms should be of the same content type, reject invalid group + // resolution behaviors. + if (atom.contentType() == prevGroup->contentType()) + return; + llvm::errs() << "SymbolTable: error while merging " << atom.name() + << "\n"; + llvm::report_fatal_error("duplicate symbol error"); + return; + } + + for (const Reference *r : atom) { + if (r->kindNamespace() == lld::Reference::KindNamespace::all && + r->kindValue() == lld::Reference::kindGroupChild) { + const DefinedAtom *target = dyn_cast<DefinedAtom>(r->target()); + assert(target && "Internal Error: kindGroupChild references need to " + "be associated with Defined Atoms only"); + _atoms.push_back(target); + _symbolTable.add(*target); + } + } +} + +// Called on each atom when a file is added. Returns true if a given +// atom is added to the symbol table. +void Resolver::doDefinedAtom(const DefinedAtom &atom) { + DEBUG_WITH_TYPE("resolver", llvm::dbgs() + << " DefinedAtom: " + << llvm::format("0x%09lX", &atom) + << ", file=#" + << atom.file().ordinal() + << ", atom=#" + << atom.ordinal() + << ", name=" + << atom.name() + << "\n"); + + // add to list of known atoms + _atoms.push_back(&atom); + + if (atom.isGroupParent()) { + maybeAddSectionGroupOrGnuLinkOnce(atom); + } else { + _symbolTable.add(atom); + } + + // An atom that should never be dead-stripped is a dead-strip root. + if (_ctx.deadStrip() && atom.deadStrip() == DefinedAtom::deadStripNever) { + _deadStripRoots.insert(&atom); + } +} + +void Resolver::doSharedLibraryAtom(const SharedLibraryAtom &atom) { + DEBUG_WITH_TYPE("resolver", llvm::dbgs() + << " SharedLibraryAtom: " + << llvm::format("0x%09lX", &atom) + << ", name=" + << atom.name() + << "\n"); + + // add to list of known atoms + _atoms.push_back(&atom); + + // tell symbol table + _symbolTable.add(atom); +} + +void Resolver::doAbsoluteAtom(const AbsoluteAtom &atom) { + DEBUG_WITH_TYPE("resolver", llvm::dbgs() + << " AbsoluteAtom: " + << llvm::format("0x%09lX", &atom) + << ", name=" + << atom.name() + << "\n"); + + // add to list of known atoms + _atoms.push_back(&atom); + + // tell symbol table + if (atom.scope() != Atom::scopeTranslationUnit) + _symbolTable.add(atom); +} + +// utility to add a vector of atoms +void Resolver::addAtoms(const std::vector<const DefinedAtom *> &newAtoms) { + for (const DefinedAtom *newAtom : newAtoms) + doDefinedAtom(*newAtom); +} + +// Instantiate an archive file member if there's a file containing a +// defined symbol for a given symbol name. Instantiation is done in a +// different worker thread and has no visible side effect. +void Resolver::maybePreloadArchiveMember(StringRef sym) { + auto it = _archiveMap.find(sym); + if (it == _archiveMap.end()) + return; + ArchiveLibraryFile *archive = it->second; + archive->preload(_ctx.getTaskGroup(), sym); +} + +// Returns true if at least one of N previous files has created an +// undefined symbol. +bool Resolver::undefinesAdded(int begin, int end) { + std::vector<std::unique_ptr<Node>> &inputs = _ctx.getNodes(); + for (int i = begin; i < end; ++i) + if (FileNode *node = dyn_cast<FileNode>(inputs[i].get())) + if (_newUndefinesAdded[node->getFile()]) + return true; + return false; +} + +File *Resolver::getFile(int &index) { + std::vector<std::unique_ptr<Node>> &inputs = _ctx.getNodes(); + if ((size_t)index >= inputs.size()) + return nullptr; + if (GroupEnd *group = dyn_cast<GroupEnd>(inputs[index].get())) { + // We are at the end of the current group. If one or more new + // undefined atom has been added in the last groupSize files, we + // reiterate over the files. + int size = group->getSize(); + if (undefinesAdded(index - size, index)) { + index -= size; + return getFile(index); + } + ++index; + return getFile(index); + } + return cast<FileNode>(inputs[index++].get())->getFile(); +} + +// Update a map of Symbol -> ArchiveFile. The map is used for speculative +// file loading. +void Resolver::updatePreloadArchiveMap() { + std::vector<std::unique_ptr<Node>> &nodes = _ctx.getNodes(); + for (int i = nodes.size() - 1; i >= 0; --i) { + auto *fnode = dyn_cast<FileNode>(nodes[i].get()); + if (!fnode) + continue; + auto *archive = dyn_cast<ArchiveLibraryFile>(fnode->getFile()); + if (!archive || _archiveSeen.count(archive)) + continue; + _archiveSeen.insert(archive); + for (StringRef sym : archive->getDefinedSymbols()) + _archiveMap[sym] = archive; + } +} + +// Keep adding atoms until _ctx.getNextFile() returns an error. This +// function is where undefined atoms are resolved. +bool Resolver::resolveUndefines() { + ScopedTask task(getDefaultDomain(), "resolveUndefines"); + int index = 0; + std::set<File *> seen; + for (;;) { + bool undefAdded = false; + File *file = getFile(index); + if (!file) + return true; + if (std::error_code ec = file->parse()) { + llvm::errs() << "Cannot open " + file->path() + << ": " << ec.message() << "\n"; + return false; + } + file->beforeLink(); + updatePreloadArchiveMap(); + switch (file->kind()) { + case File::kindObject: + // The same file may be visited more than once if the file is + // in --start-group and --end-group. Only library files should + // be processed more than once. + if (seen.count(file)) + break; + seen.insert(file); + assert(!file->hasOrdinal()); + file->setOrdinal(_ctx.getNextOrdinalAndIncrement()); + undefAdded = handleFile(*file); + break; + case File::kindArchiveLibrary: + if (!file->hasOrdinal()) + file->setOrdinal(_ctx.getNextOrdinalAndIncrement()); + undefAdded = handleArchiveFile(*file); + break; + case File::kindSharedLibrary: + if (!file->hasOrdinal()) + file->setOrdinal(_ctx.getNextOrdinalAndIncrement()); + handleSharedLibrary(*file); + break; + } + _newUndefinesAdded[file] = undefAdded; + } +} + +// switch all references to undefined or coalesced away atoms +// to the new defined atom +void Resolver::updateReferences() { + ScopedTask task(getDefaultDomain(), "updateReferences"); + for (const Atom *atom : _atoms) { + if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom)) { + for (const Reference *ref : *defAtom) { + // A reference of type kindAssociate should't be updated. + // Instead, an atom having such reference will be removed + // if the target atom is coalesced away, so that they will + // go away as a group. + if (ref->kindNamespace() == lld::Reference::KindNamespace::all && + ref->kindValue() == lld::Reference::kindAssociate) { + if (_symbolTable.isCoalescedAway(atom)) + _deadAtoms.insert(ref->target()); + continue; + } + const Atom *newTarget = _symbolTable.replacement(ref->target()); + const_cast<Reference *>(ref)->setTarget(newTarget); + } + } + } +} + +// For dead code stripping, recursively mark atoms "live" +void Resolver::markLive(const Atom *atom) { + // Mark the atom is live. If it's already marked live, then stop recursion. + auto exists = _liveAtoms.insert(atom); + if (!exists.second) + return; + + // Mark all atoms it references as live + if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom)) { + for (const Reference *ref : *defAtom) + markLive(ref->target()); + for (auto &p : llvm::make_range(_reverseRef.equal_range(defAtom))) { + const Atom *target = p.second; + markLive(target); + } + } +} + +static bool isBackref(const Reference *ref) { + if (ref->kindNamespace() != lld::Reference::KindNamespace::all) + return false; + return (ref->kindValue() == lld::Reference::kindLayoutAfter || + ref->kindValue() == lld::Reference::kindGroupChild); +} + +// remove all atoms not actually used +void Resolver::deadStripOptimize() { + ScopedTask task(getDefaultDomain(), "deadStripOptimize"); + // only do this optimization with -dead_strip + if (!_ctx.deadStrip()) + return; + + // Some type of references prevent referring atoms to be dead-striped. + // Make a reverse map of such references before traversing the graph. + // While traversing the list of atoms, mark AbsoluteAtoms as live + // in order to avoid reclaim. + for (const Atom *atom : _atoms) { + if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom)) + for (const Reference *ref : *defAtom) + if (isBackref(ref)) + _reverseRef.insert(std::make_pair(ref->target(), atom)); + if (const AbsoluteAtom *absAtom = dyn_cast<AbsoluteAtom>(atom)) + markLive(absAtom); + } + + // By default, shared libraries are built with all globals as dead strip roots + if (_ctx.globalsAreDeadStripRoots()) + for (const Atom *atom : _atoms) + if (const DefinedAtom *defAtom = dyn_cast<DefinedAtom>(atom)) + if (defAtom->scope() == DefinedAtom::scopeGlobal) + _deadStripRoots.insert(defAtom); + + // Or, use list of names that are dead strip roots. + for (const StringRef &name : _ctx.deadStripRoots()) { + const Atom *symAtom = _symbolTable.findByName(name); + assert(symAtom); + _deadStripRoots.insert(symAtom); + } + + // mark all roots as live, and recursively all atoms they reference + for (const Atom *dsrAtom : _deadStripRoots) + markLive(dsrAtom); + + // now remove all non-live atoms from _atoms + _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(), [&](const Atom *a) { + return _liveAtoms.count(a) == 0; + }), + _atoms.end()); +} + +// error out if some undefines remain +bool Resolver::checkUndefines() { + // build vector of remaining undefined symbols + std::vector<const UndefinedAtom *> undefinedAtoms = _symbolTable.undefines(); + if (_ctx.deadStrip()) { + // When dead code stripping, we don't care if dead atoms are undefined. + undefinedAtoms.erase( + std::remove_if(undefinedAtoms.begin(), undefinedAtoms.end(), + [&](const Atom *a) { return _liveAtoms.count(a) == 0; }), + undefinedAtoms.end()); + } + + if (undefinedAtoms.empty()) + return false; + + // Warn about unresolved symbols. + bool foundUndefines = false; + for (const UndefinedAtom *undef : undefinedAtoms) { + // Skip over a weak symbol. + if (undef->canBeNull() != UndefinedAtom::canBeNullNever) + continue; + + // If this is a library and undefined symbols are allowed on the + // target platform, skip over it. + if (isa<SharedLibraryFile>(undef->file()) && _ctx.allowShlibUndefines()) + continue; + + // If the undefine is coalesced away, skip over it. + if (_symbolTable.isCoalescedAway(undef)) + continue; + + // Seems like this symbol is undefined. Warn that. + foundUndefines = true; + if (_ctx.printRemainingUndefines()) { + llvm::errs() << "Undefined symbol: " << undef->file().path() + << ": " << _ctx.demangle(undef->name()) + << "\n"; + } + } + if (!foundUndefines) + return false; + if (_ctx.printRemainingUndefines()) + llvm::errs() << "symbol(s) not found\n"; + return true; +} + +// remove from _atoms all coaleseced away atoms +void Resolver::removeCoalescedAwayAtoms() { + ScopedTask task(getDefaultDomain(), "removeCoalescedAwayAtoms"); + _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(), [&](const Atom *a) { + return _symbolTable.isCoalescedAway(a) || _deadAtoms.count(a); + }), + _atoms.end()); +} + +bool Resolver::resolve() { + updatePreloadArchiveMap(); + if (!resolveUndefines()) + return false; + updateReferences(); + deadStripOptimize(); + if (checkUndefines()) + if (!_ctx.allowRemainingUndefines()) + return false; + removeCoalescedAwayAtoms(); + _result->addAtoms(_atoms); + return true; +} + +void Resolver::MergedFile::addAtoms(std::vector<const Atom *> &all) { + ScopedTask task(getDefaultDomain(), "addAtoms"); + DEBUG_WITH_TYPE("resolver", llvm::dbgs() << "Resolver final atom list:\n"); + for (const Atom *atom : all) { + DEBUG_WITH_TYPE("resolver", llvm::dbgs() + << llvm::format(" 0x%09lX", atom) + << ", name=" + << atom->name() + << "\n"); + addAtom(*atom); + } +} + +} // namespace lld |