Add a feature to explain why some file gets included to the linker's output

[ruiu]

Summary

This patch proposes a new option --explain. This patch is not intended to be
committed as-is but is for discussion.

So, I sent https://reviews.llvm.org/D67388 to dump the internal dependency graph
from the linker so that users can run arbitrary graph algorithms to analyze
linker outputs. But I believe in most cases what users want to know is simple:
why some file, that wasn't previously linked, is now included to the final
binary? I think this situation occurs so frequently that we probably should add
a new feature that answers to that particular question, so that users don't have
to write a graph analysis program.

This is an example output of lld when --explain=lib/libLLVMSupport.a(APInt.cpp.o)
is given (shortened to fit to the screen).

This is why 'lib/libLLVMSupport.a(APInt.cpp.o)' is linked:

'(--entry option)' uses '_start' defined in '/usr/lib/x86_64-linux-gnu/crt1.o'
which uses 'main' defined in 'tools/lld/tools/lld/CMakeFiles/lld.dir/lld.cpp.o'
which uses 'StringRef::endswith_lower()' defined in 'lib/libLLVMSupport.a(StringRef.cpp.o)'
which uses 'APInt::zext()' defined in 'lib/libLLVMSupport.a(APInt.cpp.o)'

What we are doing in this patch is the basic breadth-first search in the
dependency graph.

The feature implemented in this patch is somewhat redundant once we land
https://reviews.llvm.org/D67388, but this option seems pretty practical and easy
to use. So, I guess that adding something like this would make users life a bit
easier.

[grimar]

Looks useful.

lld/ELF/Explain.cpp

92

Perhaps worth to show a list of files available for --explain to user on this step?
Or have another way to get a list of files that can be passed here. May be explain without arguments could show something.

[peter.smith]

I agree that having the most common case built in is valuable. Unless there is an analysis program that is shipped with the linker I suspect that the majority of users won't want to write their own algorithm.
Looking at the example output:

'(--entry option)' uses '_start'
'/usr/lib/x86_64-linux-gnu/crt1.o' uses 'main'
'lld.cpp.o' uses 'lld::elf::link(llvm::ArrayRef<char const*>)'
'lib/liblldELF.a(Driver.cpp.o)' uses 'llvm::object::Archive::create()'
'lib/libLLVMObject.a(Archive.cpp.o)' uses 'llvm::Expected<bool>::operator bool()'
'lib/libLLVMPasses.a(PassBuilder.cpp.o)' uses 'llvm::InlinerPass::~InlinerPass()'
'lib/libLLVMipo.a(Inliner.cpp.o)'

I'd be tempted to start with the last object in the chain that is unconditionally present on the command line. For example _start, crt1.o, etc. will always be present and most likely not visible to the user as they have been added by the compiler driver. In this case I'd expect lld.cpp.o to be the first entry in the diagnostic.

Although it is implicit, it may be worth stating the dependency as:

'lld.cpp.o' uses 'lld::elf::link(llvm::ArrayRef<char const*>)' defined in 'lib/liblldELF.a(Driver.cpp.o)'

It would make it a bit more verbose, but everything is on one line.

[thakis]

I think this is a cool feature. Could it accept symbol names in addition to files as well? ld64 has a "-why_live" for symbols, and a "-why_load" for object files (https://www.manpagez.com/man/1/ld64/). I've used why_live a lot more than why_load.

[joerg]

Just for the sake of correctness, this is provided by GNU ld as part of the map file (-Wl,-Map=foo.map). It lists all archive members and which object file and symbol triggered the inclusion.

[pcc]

I agree with Nico that it would be nice if this could take symbol names as well. Maybe the --explain output could be added to the output of --trace`?

lld/ELF/Explain.cpp

96

Hmm, object files aren't really gc roots, so this could give misleading output (e.g. ld a.o b.o --explain a with a.o containing a: ret and b.o containing b: call a with only b in dynsym won't report b.o). Also, it misses archives included with --whole-archive.

Shouldn't this be more similar to MarkLive.cpp? In other words, include dynsym and don't treat object files as roots.

126

Shouldn't it also look at dependentSections?

168

I don't think the isWeak part here is correct.

[MaskRay]

lld/ELF/Explain.cpp

102

--init and --fini are used in --gc-sections but they do not fetch lazy definitions. I do not know why GNU ld behaves this way.

158

We can make edges a superset of specialEdges, then we can just delete seen and use edges.try_emplace(...) here.

168

-u/-e can fetch a weak lazy definition. This may cause a bogus file unreachable error.

[MaskRay]

lld/ELF/Driver.cpp

1990

Missing full stop.

lld/ELF/Explain.h

12

Missing #include "lld/Common/LLVM.h"

[MaskRay]

lld/ELF/Options.td

46

It is not obvious that the user is supposed to specify b.a(b.o) for an object file in an archive or b.o for an object between --start-lib and --end-lib.

[ruiu]

In D69607#1726792, @peter.smith wrote:

I agree that having the most common case built in is valuable. Unless there is an analysis program that is shipped with the linker I suspect that the majority of users won't want to write their own algorithm.
Looking at the example output:

'(--entry option)' uses '_start'
'/usr/lib/x86_64-linux-gnu/crt1.o' uses 'main'
'lld.cpp.o' uses 'lld::elf::link(llvm::ArrayRef<char const*>)'
'lib/liblldELF.a(Driver.cpp.o)' uses 'llvm::object::Archive::create()'
'lib/libLLVMObject.a(Archive.cpp.o)' uses 'llvm::Expected<bool>::operator bool()'
'lib/libLLVMPasses.a(PassBuilder.cpp.o)' uses 'llvm::InlinerPass::~InlinerPass()'
'lib/libLLVMipo.a(Inliner.cpp.o)'

I'd be tempted to start with the last object in the chain that is unconditionally present on the command line. For example _start, crt1.o, etc. will always be present and most likely not visible to the user as they have been added by the compiler driver. In this case I'd expect lld.cpp.o to be the first entry in the diagnostic.

Although it is implicit, it may be worth stating the dependency as:

'lld.cpp.o' uses 'lld::elf::link(llvm::ArrayRef<char const*>)' defined in 'lib/liblldELF.a(Driver.cpp.o)'

It would make it a bit more verbose, but everything is on one line.

How about the new one? I think I can reverse the order by making the message in a passive tense, but it seems that this order is a bit easier to read.

lld/ELF/Explain.cpp

92

Added a hint as to how to get a list of input files.

96

I think object files are actually roots in this features sense if you do not pass -gc-sections, so we need to handle two different cases, -no-gc-sections and -gc-sections. How is this new code?

126

Done.

168

Yeah, this was in a wrong place. I moved this to enqueue.

[ruiu]

• address review comments

[ruiu]

lld/ELF/Explain.cpp

158

We probably could but looks like it also makes sense to keep them distinctive sets, so I'm leaning towards not doing that.

[ruiu]

• address vreview comments

[MaskRay]

lld/ELF/Explain.cpp

157

We may consider turning the error into a regular print. A similar functionality -y not_exist does not error.

[ruiu]

lld/ELF/Explain.cpp

158

It's not a strong preference, but error is perhaps better than printing it out as a non-error message? When the control reaches here, something is wrong from the user's perspective.

[grimar]

lld/ELF/Explain.cpp

176

But it doesn't seem helps for the case mentioned in the description?

If we have a main.o compiled from

.global _start;
_start:
callq foo

And a foo.a which contains a foo.o compiled from

.globl foo;
foo:

Then when I invoke -flavor gnu main.o foo.a "-o" out --verbose I see:

lld: main.o
lld: foo.a

Then, like a possible normal user :) I do:
-flavor gnu --explain=foo.a main.o foo.a "-o" out --verbose

and I see:

lld: main.o
lld: foo.a
lld: error: --explain: no such file or symbol: 'foo.a'. Use --verbose option to
see a list of input files.

How I am supposed to realise that I should invoke -flavor gnu --explain=foo.a(foo.o) main.o foo.a "-o" out --verbose
to see the following?

lld: main.o
lld: foo.a
Explain: This is why 'foo.a(foo.o)' is linked:
Explain:
Explain: '(--entry option)' uses '_start' defined in 'main.o'
Explain: which uses 'foo' defined in 'foo.a(foo.o)'

[grimar]

lld/ELF/Explain.cpp

176

btw, note that it says '(--entry option)' uses '_start', but in fact I am not using any command line option like -e

[ruiu]

lld/ELF/Explain.cpp

176

That's I think fine. It's an implicit option but still there.

176

Well, I don't think we should print out all section names because it's just too long, and I believe showing a hint is better. The problem is that --verbose option doesn't show archive members, but that can be fixed simply by adding a log() call to fetch().

[ruiu]

• address review comments

[peter.smith]

Thanks for the update, I'm happy with the explain output format.

One anomaly that I'm not sure is worth dealing with is the linkerscript GROUP command as used in libc.so

GROUP ( /lib/libc.so.6 /usr/lib/libc_nonshared.a  AS_NEEDED ( /lib/ld-linux-armhf.so.3 ) )

I think that these will just end up as input files on the command line. Although they are non-obvious and implicitly included due to the linker script.

lld/ELF/Explain.cpp

169

Global symbols defined by a comdat group may cause some confusion as there will be multiple object files that define the symbol, but only one group that is selected that will match here. Not a lot that we can do here. Perhaps if we knew that a symbol was defined in a group then we could print that out. "Explain: Symbol foo is defined in COMDAT group g, selected from from file foo.o". Perhaps wait and see if anyone does get confused.

lld/ELF/Options.td

47

A suggestion:

Explain why a given object file gets linked in to the final binary. Objects can be specified by full path, or by a global symbol that they define. Objects defined in archives are specified by full/path/to/library(object) such as library.a(object.o).

[MaskRay]

lld/ELF/Explain.cpp

158

error inhibits producing an output. I have a feeling that retaining the output may be slightly more useful.

Sometimes the user can specify multiple --explain. The user may still need the output though some of the --explain values are not existent.

169

Explaining more about COMDAT groups looks good to me. We essentially discarded all but one definitions, lost some information in the transformation, and the best we can do here is to select the prevailing definition. The user is hinted from the message that the archive order may matter.

A COMDAT group is a SHT_GROUP section with the ELF group section flag GRP_COMDAT. Its name is almost always ".group". Shall we say the COMDAT group with signature "g"?

176

Is --trace better? --verbose suggests the raw archive names while --trace does not, and the --trace output does not include unused files.

# --verbose
ld.lld: a.a
ld.lld: b.o
ld.lld: a.a(a.o)

# --trace
b.o
a.a(a.o)

lld/ELF/Options.td

47

Unfortunately this (lld::elf::InputFile::archiveName) is not the full path. Here are some examples:

ld.lld a.a => a.a
ld.lld -L. -la => ./liba.a
ld.lld /tmp/c/a.a => /tmp/c/a.a

So we may need path normalization here. Some users may resolve the path and feed that to lld.

[ruiu]

• added tests
• added a man page entry
• removed dependent section tracking because dependencies are within the same object file, while this explain feature works in the file granularity

[ruiu]

In D69607#1728450, @peter.smith wrote:

Thanks for the update, I'm happy with the explain output format.

One anomaly that I'm not sure is worth dealing with is the linkerscript GROUP command as used in libc.so

GROUP ( /lib/libc.so.6 /usr/lib/libc_nonshared.a  AS_NEEDED ( /lib/ld-linux-armhf.so.3 ) )

I think that these will just end up as input files on the command line. Although they are non-obvious and implicitly included due to the linker script.

In most cases I believe linker scripts are explicitly added to the command line by users, and that wouldn't cause too much confusion as they should know what they are doing. One exception is Linux's libc.so which is not a DSO but actually a linker script, but maybe that's the only implicit use case?

lld/ELF/Explain.cpp

158

I guess that's actually a good thing, no? I want users to use this option only interactively just by appending an --explain to an otherwise complete command line, and if a command line option passed by a user is not correct, that is, well, I think an error.

169

Currently it is not easy to know whether a section was in a comdat group or not. Fortunately, I don't think that's too confusing, at least we don't tell a lie to users. If we report that there's some dependency from one file to another, that dependency does exist in the source code, though other files may have similar dependencies to the same file. So I don't think we need to do something special for comdats.

176

Thank you for the suggestion. I replaced --verbose with --trace.

lld/ELF/Options.td

47

Added that text to the man page, thanks!

47

OK, I made a change to code so that we normalize pathnames before comparison.

[ruiu]

• address review comments

[grimar]

This needs a test case.

[ruiu]

• add a test file which I forgot to add in a previous patch

[pcc]

removed dependent section tracking because dependencies are within the same object file, while this explain feature works in the file granularity

Is it a good idea to make the feature use file granularity in the --gc-sections case? I would imagine that this feature would be used in tricky situations where the explanation for a section being included is not entirely obvious, so doing things at a file granularity may end up hiding critical information. That's just my opinion though.

lld/ELF/Explain.cpp

96

Maybe I'm missing something, but I don't see where dynsyms are being added in the new code in the --gc-sections case,

[MaskRay]

lld/ELF/Explain.cpp

96

We don't need to handle --init, --fini or .dynsym as opposed to MarkLive.cpp.

# c.s -> c.o
.globl _start
_start:
  ret

.section .text.foo,"ax"
call bar

# b.s -> b.o -> b.a
% cat b.s
.globl bar
bar:
  call foo

# a.s -> a.o -> a.a
.globl foo
foo:
  ret

For example, in ld.lld c.o b.a a.a --gc-sections -o a, neither b.a nor a.a is necessary (none of their sections is retained) but we still need to link in b.a and a.a before discarding their sections. The archive handling logic happens before garbage collection.

[MaskRay]

In D69607#1726863, @thakis wrote:

I think this is a cool feature. Could it accept symbol names in addition to files as well? ld64 has a "-why_live" for symbols, and a "-why_load" for object files (https://www.manpagez.com/man/1/ld64/). I've used why_live a lot more than why_load.

@thakis The current implementation uses the option name --explain and allows either a symbol name and a filename pattern. Do you have a preference of using an alternative name, or using different option names?

[thakis]

In D69607#1734134, @MaskRay wrote:

In D69607#1726863, @thakis wrote:

I think this is a cool feature. Could it accept symbol names in addition to files as well? ld64 has a "-why_live" for symbols, and a "-why_load" for object files (https://www.manpagez.com/man/1/ld64/). I've used why_live a lot more than why_load.

@thakis The current implementation uses the option name --explain and allows either a symbol name and a filename pattern. Do you have a preference of using an alternative name, or using different option names?

I don't have an opinion on the flag name. --explain sounds fine, and it working with both file and symbol names seems fine too.

[MaskRay]

I created D109572 (--why-extract) as an alternative.

lld/ELF/CMakeLists.txt

add_lld_library(lldELF
   Arch/X86.cpp
   Arch/X86_64.cpp
   ARMErrataFix.cpp
   CallGraphSort.cpp
   DWARF.cpp
   Driver.cpp
   DriverUtils.cpp
   EhFrame.cpp
+  Explain.cpp
   ICF.cpp
   InputFiles.cpp
   InputSection.cpp
   LTO.cpp
   LinkerScript.cpp
   MapFile.cpp
   MarkLive.cpp
   OutputSections.cpp

lld/ELF/Driver.cpp

 // be harmful when you are doing cross-linking. Therefore, in LLD, we
 // simply trust the compiler driver to pass all required options and
 // don't try to make effort on our side.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Driver.h"
 #include "Config.h"
+#include "Explain.h"
 #include "ICF.h"
 #include "InputFiles.h"
 #include "InputSection.h"
 #include "LinkerScript.h"
 #include "MarkLive.h"
 #include "OutputSections.h"
 #include "ScriptParser.h"
 #include "SymbolTable.h"
template <class ELFT> void LinkerDriver::link(opt::InputArgList &args) {
   // Read the callgraph now that we know what was gced or icfed
   if (config->callGraphProfileSort) {
     if (auto *arg = args.getLastArg(OPT_call_graph_ordering_file))
       if (Optional<MemoryBufferRef> buffer = readFile(arg->getValue()))
         readCallGraph(*buffer);
     readCallGraphsFromObjectFiles<ELFT>();
   }
 
+  // Handle --explain.
+  for (auto *arg : args.filtered(OPT_explain))
+    explain<ELFT>(arg->getValue());
+
   // Write the result to the file.
   writeResult<ELFT>();
 }
 
 } // namespace elf
 } // namespace lld

lld/ELF/Explain.h

+//===- 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
+
+#include "lld/Common/LLVM.h"
+
+namespace lld {
+namespace elf {
+
+template <class ELFT> void explain(StringRef fileOrSym);
+
+} // namespace elf
+} // namespace lld
+
+#endif

lld/ELF/Explain.cpp

+//===- 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 a file that wasn't linked in a
+// previous release, and try to figure out why the file gets linked to the
+// current one. 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. Below is an example output of lld
+// when `--explain=lib/libLLVMSupport.a(APInt.cpp.o)` is given (shortened to fit
+// to the screen):
+//
+//   This is why 'lib/libLLVMSupport.a(APInt.cpp.o)' is linked:
+//
+//   '(--entry option)' uses '_start' defined in '/usr/lib/x86_64-linux-gnu/crt1.o'
+//   which uses 'main' defined in 'tools/lld/tools/lld/CMakeFiles/lld.dir/lld.cpp.o'
+//   which uses 'StringRef::endswith_lower()' defined in 'lib/libLLVMSupport.a(StringRef.cpp.o)'
+//   which uses 'APInt::zext()' defined in 'lib/libLLVMSupport.a(APInt.cpp.o)'
+//
+// You can also pass a symbol name instead of a filename to the option, and lld
+// will try to figure out why a file that defines a symbol is linked.
+//
+// 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 <deque>
+
+using namespace llvm;
+using namespace llvm::ELF;
+using namespace llvm::object;
+
+namespace lld {
+namespace elf {
+
+namespace {
+template <class ELFT> class Explain {
+public:
+  void run(StringRef fileOrSym);
+
+private:
+  InputFile *findFile(StringRef fileOrSym);
+  template <class RelTy> void enqueue(const InputSectionBase *sec, RelTy &rel);
+  void enqueueSpecial(StringRef cause, StringRef symName);
+  void printPath(StringRef fileOrSym);
+
+  // 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<InputFile *, std::pair<InputFile *, Symbol *>> 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<InputFile *, std::pair<StringRef, StringRef>> specialEdges;
+
+  // We want to visit each object file at most once.
+  DenseSet<InputFile *> seen;
+
+  // A queue for breadth-first search.
+  std::deque<InputFile *> queue;
+};
+} // namespace
+
+// This is the main function of the --explain feature.
+template <class ELFT> void Explain<ELFT>::run(StringRef fileOrSym) {
+  // Find a file object for a given filename or a symbol.
+  target = findFile(fileOrSym);
+  if (!target)
+    return;
+
+  // Collect root objects. Object files are usually root objects (i.e. always
+  // included to the result), but if -gc-sections is passed, they need to be
+  // (directly or indirectly) referenced by a root symbol.
+  if (!config->gcSections) {
+    for (InputFile *file : objectFiles)
+      if (!file->loadedLazily)
+        queue.push_back(file);
+
+    for (InputFile *file : bitcodeFiles)
+      if (!file->loadedLazily)
+        queue.push_back(file);
+
+    // If the target file is a root object, we don't need to run BFS.
+    for (InputFile *file : queue) {
+      if (file != target)
+        continue;
+      outs() << "Explain: File '" << toString(target) << "' is linked because "
+             << "it is passed as a command line argument.\n";
+      return;
+    }
+  }
+
+  // Object files referenced by the following symbols are also root objects.
+  enqueueSpecial("(--entry option)", config->entry);
+  for (StringRef s : config->undefined)
+    enqueueSpecial("(--undefined option)", s);
+  for (StringRef s : script->referencedSymbols)
+    enqueueSpecial("(linker script)", s);
+
+  // Now that we have a complete set of root objects, run BFS.
+  while (!queue.empty()) {
+    InputFile *file = queue.front();
+    queue.pop_front();
+
+    if (file == target) {
+      printPath(fileOrSym);
+      return;
+    }
+
+    if (!isa<ObjFile<ELFT>>(file) && !isa<BitcodeFile>(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<ELFT>())
+          enqueue(sec, rel);
+      } else {
+        for (const typename ELFT::Rel &rel : sec->template rels<ELFT>())
+          enqueue(sec, rel);
+      }
+    }
+  }
+
+  error("--explain: unreachable file: " + toString(target));
+}
+
+// Returns the shortest absolute path for a given path, so that
+// it is easy to compare two paths.
+static std::string canonicalize(StringRef path) {
+  SmallVector<char, 256> buf(path.begin(), path.end());
+  sys::fs::make_absolute(buf);
+  sys::path::remove_dots(buf, /*remove_dot_dot=*/true);
+  return {buf.begin(), buf.end()};
+}
+
+// Returns true if a given file has a given path. You can specify
+// "foo.a(bar.o)"-style string as a path.
+static bool hasPath(InputFile *file, StringRef path) {
+  // If a given path doesn't seem to represent an object in an archive,
+  // we can just compare the two paths.
+  size_t pos = path.find('(');
+  if (pos == StringRef::npos || !path.endswith(")"))
+    return canonicalize(file->mb.getBufferIdentifier()) == canonicalize(path);
+
+  if (file->archiveName.empty())
+    return false;
+
+  // Split "foo.a(bar.o)" into "foo.a" and "bar.o".
+  StringRef archivePath = path.substr(0, pos);
+  StringRef subPath = path.substr(pos + 1, path.size() - pos - 2);
+
+  return canonicalize(file->archiveName) == canonicalize(archivePath) &&
+         file->mb.getBufferIdentifier() == subPath;
+}
+
+template <class ELFT> InputFile *Explain<ELFT>::findFile(StringRef fileOrSym) {
+  for (InputFile *file : objectFiles)
+    if (hasPath(file, fileOrSym))
+      return file;
+
+  for (SharedFile *file : sharedFiles)
+    if (hasPath(file, fileOrSym))
+      return file;
+
+  if (auto *sym = dyn_cast_or_null<Defined>(symtab->find(fileOrSym))) {
+    outs() << "Explain: Symbol '" << fileOrSym << "' is defined in file '"
+           << toString(sym->file) << "'.\n";
+    return sym->file;
+  }
+
+  error("--explain: no such file or symbol: '" + fileOrSym +
+        "'. Use --trace option to see a list of input files.");
+  return nullptr;
+}
+
+// Add a new vertex for BFS.
+template <class ELFT>
+template <class RelTy>
+void Explain<ELFT>::enqueue(const InputSectionBase *sec, RelTy &rel) {
+  Symbol &sym = sec->getFile<ELFT>()->getRelocTargetSym(rel);
+  if (!sym.file || sym.isWeak() || !seen.insert(sym.file).second)
+    return;
+  queue.push_back(sym.file);
+  edges[sym.file] = {sec->file, &sym};
+}
+
+// Add a new vertex for BFS.
+template <class ELFT>
+void Explain<ELFT>::enqueueSpecial(StringRef cause, StringRef symName) {
+  auto *sym = dyn_cast_or_null<Defined>(symtab->find(symName));
+  if (!sym)
+    return;
+
+  auto *sec = dyn_cast_or_null<InputSection>(sym->section);
+  if (!sec || !seen.insert(sec->file).second)
+    return;
+
+  queue.push_back(sec->file);
+  specialEdges[sec->file] = {cause, symName};
+}
+
+// Print out a path from a root to the target file.
+template <class ELFT> void Explain<ELFT>::printPath(StringRef fileOrSym) {
+  std::vector<std::string> files;
+  std::vector<std::string> syms;
+  InputFile *cur = target;
+
+  for (;;) {
+    files.push_back(toString(cur));
+
+    if (specialEdges.count(cur)) {
+      StringRef cause;
+      StringRef sym;
+      std::tie(cause, sym) = specialEdges[cur];
+      files.push_back(cause);
+      syms.push_back(sym);
+      break;
+    }
+
+    if (!edges.count(cur))
+      break;
+
+    Symbol *sym;
+    std::tie(cur, sym) = edges[cur];
+    syms.push_back(toString(*sym));
+  }
+
+  outs() << "Explain: This is why '" << files[0] << "' is linked:\n"
+         << "Explain:\n"
+         << "Explain: '" << files.back() << "' uses '" << syms.back()
+         << "' defined in '" << files[files.size() - 2] << "'\n";
+
+  for (int i = files.size() - 3; i >= 0; --i)
+    outs() << "Explain: which uses '" << syms[i] << "' defined in '" << files[i]
+           << "'\n";
+}
+
+template <class ELFT> void explain(StringRef fileOrSym) {
+  Explain<ELFT>().run(fileOrSym);
+}
+
+template void explain<ELF32LE>(StringRef);
+template void explain<ELF32BE>(StringRef);
+template void explain<ELF64LE>(StringRef);
+template void explain<ELF64BE>(StringRef);
+
+} // namespace elf
+} // namespace lld

lld/ELF/InputFiles.h

public:
   mutable std::string toStringCache;
 
   std::string getSrcMsg(const Symbol &sym, InputSectionBase &sec,
                         uint64_t offset);
 
   // True if this is an argument for --just-symbols. Usually false.
   bool justSymbols = false;
 
+  // True if this file loaded lazily from an archive or --start-lib/--end-lib.
+  // False if this file is directly specified on the command line.
+  bool loadedLazily = false;
+
   // outSecOff of .got2 in the current file. This is used by PPC32 -fPIC/-fPIE
   // to compute offsets in PLT call stubs.
   uint32_t ppc32Got2OutSecOff = 0;
 
   // On PPC64 we need to keep track of which files contain small code model
   // relocations that access the .toc section. To minimize the chance of a
   // relocation overflow, files that do contain said relocations should have
   // their .toc sections sorted closer to the .got section than files that do

lld/ELF/InputFiles.cpp

MemoryBufferRef mb =
                 toELFString(sym));
 
   if (tar && c.getParent()->isThin())
     tar->append(relativeToRoot(CHECK(c.getFullName(), this)), mb.getBuffer());
 
   InputFile *file = createObjectFile(
       mb, getName(), c.getParent()->isThin() ? 0 : c.getChildOffset());
   file->groupId = groupId;
+  file->loadedLazily = true;
   parseFile(file);
 }
 
 unsigned SharedFile::vernauxNum;
 
 // Parse the version definitions in the object file if present, and return a
 // vector whose nth element contains a pointer to the Elf_Verdef for version
 // identifier n. Version identifiers that are not definitions map to nullptr.
void LazyObjFile::fetch() {
   file->groupId = groupId;
 
   mb = {};
 
   // Copy symbol vector so that the new InputFile doesn't have to
   // insert the same defined symbols to the symbol table again.
   file->symbols = std::move(symbols);
 
+  file->loadedLazily = true;
   parseFile(file);
 }
 
 template <class ELFT> void LazyObjFile::parse() {
   using Elf_Sym = typename ELFT::Sym;
 
   // A lazy object file wraps either a bitcode file or an ELF file.
   if (isBitcode(this->mb)) {

lld/ELF/Options.td

defm check_sections: B<"check-sections",
     "Do not check section addresses for overlaps">;
 
 defm compress_debug_sections:
   Eq<"compress-debug-sections", "Compress DWARF debug sections">,
   MetaVarName<"[none,zlib]">;
 
 defm defsym: Eq<"defsym", "Define a symbol alias">, MetaVarName<"<symbol>=<value>">;
 
+defm explain:
+    Eq<"explain", "Explain why a given file or a symbol gets linked to the final binary">,
+    MetaVarName<"<path|symbol>">;
+
 defm split_stack_adjust_size
     : Eq<"split-stack-adjust-size",
          "Specify adjustment to stack size when a split-stack function calls a "
          "non-split-stack function">,
       MetaVarName<"<value>">;
 
 defm library_path:
   Eq<"library-path", "Add a directory to the library search path">, MetaVarName<"<dir>">;

lld/docs/ld.lld.1

 A value of zero indicates that there is no limit.
 .It Fl -error-unresolved-symbols
 Report unresolved symbols as errors.
 .It Fl -execute-only
 Mark executable sections unreadable.
 This option is currently only supported on AArch64.
 .It Fl -exclude-libs Ns = Ns Ar value
 Exclude static libraries from automatic export.
+.It Fl -explain Ns = Ns Ar value
+Explain why an object file gets linked in to the final binary.
+.Ar value
+may be either an object file pathname or a symbol. If a symbol is
+specified, the reason why an object file defining a given symbol will
+be explained. Objects defined in archives are specified by
+.Ql full/path/to/library(object)
+such as
+.Ql /usr/lib/libc.a(printf.o)
+.
 .It Fl -export-dynamic , Fl E
 Put symbols in the dynamic symbol table.
 .It Fl -export-dynamic-symbol Ns = Ns Ar symbol
 Include
 .Ar symbol
 in the dynamic symbol table.
 .It Fl -fatal-warnings
 Treat warnings as errors.

lld/test/ELF/explain.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux -o %t-main.o %s
+# RUN: echo '.globl foo; foo:' | llvm-mc -filetype=obj -triple=x86_64-unknown-linux -o %t-foo.o -
+# RUN: echo '.globl bar; bar:' | llvm-mc -filetype=obj -triple=x86_64-unknown-linux -o %t-bar.o -
+
+# RUN: mkdir -p %t.dir/dir
+# RUN: rm -f %t.dir/foo.a %t.dir/bar.a
+# RUN: cp %t-foo.o %t.dir/foo.o
+# RUN: cp %t-bar.o %t.dir/bar.o
+# RUN: cd %t.dir
+# RUN: llvm-ar rcs foo.a foo.o
+# RUN: llvm-ar rcs bar.a bar.o
+
+# RUN: ld.lld -o /dev/null %t-main.o %t-foo.o --explain=%t-main.o \
+# RUN:   | FileCheck -check-prefix=TEST1 %s
+
+# TEST1: main.o' is linked because it is passed as a command line argument.
+
+# RUN: ld.lld -o /dev/null %t-main.o %t-foo.o --explain=%t-foo.o \
+# RUN:   | FileCheck -check-prefix=TEST2 %s
+
+# TEST2: foo.o' is linked because it is passed as a command line argument.
+
+# RUN: ld.lld -o /dev/null %t-main.o %t-foo.o --explain=%t-foo.o -gc-sections \
+# RUN:   | FileCheck -check-prefix=TEST3 %s
+
+# TEST3: This is why '{{.*}}tmp-foo.o' is linked:
+# TEST3: '(--entry option)' uses '_start' defined in '{{.*}}main.o'
+# TEST3: Explain: which uses 'foo' defined in '{{.*}}foo.o'
+
+# RUN: ld.lld -o /dev/null %t-main.o %t-foo.o --explain=_start \
+# RUN:   | FileCheck -check-prefix=TEST4 %s
+
+# TEST4: Symbol '_start' is defined in file '{{.*}}main.o'.
+# TEST4: File '{{.*}}main.o' is linked because it is passed as a command line argument.
+
+# RUN: ld.lld -o /dev/null %t-main.o foo.a --explain="foo.a(foo.o)" \
+# RUN:   | FileCheck -check-prefix=TEST5 %s
+
+# RUN: cd %t.dir/
+# TEST5: This is why 'foo.a(foo.o)' is linked:
+# TEST5: '(--entry option)' uses '_start' defined in '{{.*}}-main.o'
+# TEST5: which uses 'foo' defined in 'foo.a(foo.o)'
+
+# RUN: ld.lld -o /dev/null %t-main.o %t.dir/foo.a --explain="%t.dir/dir/../foo.a(foo.o)" \
+# RUN:   | FileCheck -check-prefix=TEST6 %s
+
+# TEST6: This is why '{{.*}}.dir/foo.a(foo.o)' is linked:
+# TEST6: '(--entry option)' uses '_start' defined in '{{.*}}-main.o'
+# TEST6: which uses 'foo' defined in '{{.*}}.dir/foo.a(foo.o)'
+
+# RUN: ld.lld -o /dev/null %t-main.o %t-foo.o %t.dir/bar.a -u bar --explain=bar \
+# RUN:   | FileCheck -check-prefix=TEST7 %s
+
+# TEST7: Symbol 'bar' is defined in file '{{.*}}bar.a(bar.o)'.
+# TEST7: This is why '{{.*}}bar.a(bar.o)' is linked:
+# TEST7: '(--undefined option)' uses 'bar' defined in '{{.*}}bar.a(bar.o)'
+
+.globl _start
+_start:
+  call foo
+  ret