diff --git a/lld/ELF/CMakeLists.txt b/lld/ELF/CMakeLists.txt --- a/lld/ELF/CMakeLists.txt +++ b/lld/ELF/CMakeLists.txt @@ -28,6 +28,7 @@ Driver.cpp DriverUtils.cpp EhFrame.cpp + Explain.cpp ICF.cpp InputFiles.cpp InputSection.cpp diff --git a/lld/ELF/Driver.cpp b/lld/ELF/Driver.cpp --- a/lld/ELF/Driver.cpp +++ b/lld/ELF/Driver.cpp @@ -24,6 +24,7 @@ #include "Driver.h" #include "Config.h" +#include "Explain.h" #include "ICF.h" #include "InputFiles.h" #include "InputSection.h" @@ -58,6 +59,7 @@ #include "llvm/Support/TargetSelect.h" #include "llvm/Support/raw_ostream.h" #include +#include #include using namespace llvm; @@ -1986,6 +1988,10 @@ readCallGraphsFromObjectFiles(); } + // Handle --explain + for (auto *arg : args.filtered(OPT_explain)) + explain(arg->getValue()); + // Write the result to the file. writeResult(); } diff --git a/lld/ELF/Explain.h b/lld/ELF/Explain.h new file mode 100644 --- /dev/null +++ b/lld/ELF/Explain.h @@ -0,0 +1,20 @@ +//===- Explain.h ----------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLD_ELF_EXPLAIN_H +#define LLD_ELF_EXPLAIN_H + +namespace lld { +namespace elf { + +template void explain(StringRef filename); + +} // namespace elf +} // namespace lld + +#endif diff --git a/lld/ELF/Explain.cpp b/lld/ELF/Explain.cpp new file mode 100644 --- /dev/null +++ b/lld/ELF/Explain.cpp @@ -0,0 +1,227 @@ +//===- Explain.cpp --------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file implements an optional analysis pass that doesn't change the +// linker's internal state. If you are reading this file to understand how the +// linker works, you can skip this file now. +// +// So, if you are doing a release work, it is a common situation that you find a +// binary bloat between releases, nail down the file that wasn't linked in a +// previous release, and try to figure out why the file gets linked to the +// current release. There was no elegant solution for the last step; you would +// make a guess and remove some function calls, hoping that that eliminates a +// dependency to the file. +// +// --explain option is intended to be the solution for the above situation. You +// can specify a filename as an argument for the option, and lld prints out the +// shortest path from a root to a given file. This is an example output of lld +// when `--explain=lib/libLLVMipo.a(Inliner.cpp.o)` is given (shortened to fit +// to the screen). +// +// This is why 'lib/libLLVMipo.a(Inliner.cpp.o)' gets linked: +// +// '(--entry option)' uses '_start' +// '/usr/lib/x86_64-linux-gnu/crt1.o' uses 'main' +// 'lld.cpp.o' uses 'lld::elf::link(llvm::ArrayRef)' +// 'lib/liblldELF.a(Driver.cpp.o)' uses 'llvm::object::Archive::create()' +// 'lib/libLLVMObject.a(Archive.cpp.o)' uses 'llvm::Expected::operator bool()' +// 'lib/libLLVMPasses.a(PassBuilder.cpp.o)' uses 'llvm::InlinerPass::~InlinerPass()' +// 'lib/libLLVMipo.a(Inliner.cpp.o)' +// +// What we are doing in this file is the basic breadth-first search in the +// dependency graph. +// +//===----------------------------------------------------------------------===// + +#include "InputFiles.h" +#include "InputSection.h" +#include "LinkerScript.h" +#include "SymbolTable.h" +#include "Symbols.h" +#include "lld/Common/ErrorHandler.h" +#include + +using namespace llvm; +using namespace llvm::ELF; +using namespace llvm::object; + +namespace lld { +namespace elf { + +namespace { +template class Explain { +public: + void run(StringRef filename); + +private: + InputFile *findFile(StringRef filename); + template void enqueue(const InputSectionBase *sec, RelTy &rel); + void enqueueSpecial(StringRef cause, StringRef symName); + void printPath(); + + // A file object to which we are searching for a path. + InputFile *target = nullptr; + + // This map represents how we reach a file from root. + DenseMap> edges; + + // Some root objects are not really object files but command line arguments + // (e.g. --entry) or linker scripts. This map manages edges to such vertices. + DenseMap> specialEdges; + + // We want to visit each object file at most once. + DenseSet seen; + + // A queue for breadth-first search. + std::deque queue; +}; +} // namespace + +// This is the main function of the --explain feature. +template void Explain::run(StringRef filename) { + // Find a file object for a given filename. + target = findFile(filename); + + if (!target) { + error("--explain: file not found: " + filename); + return; + } + + // Collect root objects. + for (InputFile *f : objectFiles) + if (f->archiveName.empty()) + queue.push_back(f); + + enqueueSpecial("(--entry option)", config->entry); + enqueueSpecial("(--init option)", config->init); + enqueueSpecial("(--fini option)", config->fini); + for (StringRef s : config->undefined) + enqueueSpecial("(--undefined option)", s); + for (StringRef s : script->referencedSymbols) + enqueueSpecial("(linker script)", s); + + // Run BFS. + while (!queue.empty()) { + InputFile *file = queue.front(); + queue.pop_front(); + + if (file == target) { + printPath(); + return; + } + + if (!isa>(file) && !isa(file)) + continue; + + for (const InputSectionBase *sec : file->getSections()) { + if (!sec || !sec->isLive()) + continue; + + if (sec->areRelocsRela) { + for (const typename ELFT::Rela &rel : sec->template relas()) + enqueue(sec, rel); + } else { + for (const typename ELFT::Rel &rel : sec->template rels()) + enqueue(sec, rel); + } + } + } + + error("--explain: file unreachable: " + filename); +} + +template InputFile *Explain::findFile(StringRef filename) { + for (InputFile *f : objectFiles) + if (toString(f) == filename) + return f; + + for (SharedFile *f : sharedFiles) + if (toString(f) == filename) + return f; + + return nullptr; +} + +template +template +void Explain::enqueue(const InputSectionBase *sec, RelTy &rel) { + Symbol &sym = sec->getFile()->getRelocTargetSym(rel); + if (!sym.file) + return; + + if (!seen.insert(sym.file).second) + return; + + queue.push_back(sym.file); + edges[sym.file] = {sec->file, &sym}; +} + +template +void Explain::enqueueSpecial(StringRef cause, StringRef symName) { + auto *sym = dyn_cast_or_null(symtab->find(symName)); + if (!sym || sym->isWeak()) + return; + + auto *sec = dyn_cast_or_null(sym->section); + if (!sec) + return; + + if (!seen.insert(sec->file).second) + return; + + queue.push_back(sec->file); + specialEdges[sec->file] = {cause, symName}; +} + +template void Explain::printPath() { + InputFile *cur = target; + std::vector files; + std::vector symbols; + + for (;;) { + files.push_back(toString(cur)); + + if (specialEdges.count(cur)) { + StringRef cause; + StringRef sym; + std::tie(cause, sym) = specialEdges[cur]; + files.push_back(cause); + symbols.push_back(sym); + break; + } + + if (!edges.count(cur)) + break; + + Symbol *sym; + std::tie(cur, sym) = edges[cur]; + symbols.push_back(toString(*sym)); + } + + outs() << "Explain: This is why '" << files[0] << "' gets linked:\n" + << "Explain:\n" + << "Explain: '" << files.back() << "' uses '" << symbols.back() + << "'\n"; + + for (int i = symbols.size() - 2; i >= 0; --i) + outs() << "Explain: '" << files[i + 1] << "' uses '" << symbols[i] + << "'\n"; + outs() << "Explain: '" << files[0] << "'\n"; +} + +template void explain(StringRef filename) { + Explain().run(filename); +} + +template void explain(StringRef); +template void explain(StringRef); +template void explain(StringRef); +template void explain(StringRef); + +} // namespace elf +} // namespace lld diff --git a/lld/ELF/Options.td b/lld/ELF/Options.td --- a/lld/ELF/Options.td +++ b/lld/ELF/Options.td @@ -42,6 +42,10 @@ defm defsym: Eq<"defsym", "Define a symbol alias">, MetaVarName<"=">; +defm explain: + Eq<"explain", "Explain why a given file gets linked to the final binary">, + MetaVarName<"">; + defm split_stack_adjust_size : Eq<"split-stack-adjust-size", "Specify adjustment to stack size when a split-stack function calls a "