Add a feature to dump dependency graph.

[MaskRay]

Summary

This patch is not intended to be submitted as-is.

This patch implements an experimental feature that can be enabled
by --print-dependency-graph flag. When you give that option to lld,
lld prints out dependencies between files in the following format:

<file1> <file2> <symbol>

The above line means <file1> uses <symbol> defined by <file2>.

This is a simple feature but seems pretty useful when debugging
why some file gets loaded. To find out why some file gets linked,
you can start from a special file <commandline> to follow the
triplets until you reach the file.

I uploaded an example output of --print-dependency-graph to
https://gist.github.com/rui314/f2f6b1bf5a30a12630183d5a0e5ad100

I don't think this feature is complete. At least I think I need
to do something for garbage-collected sections and ICF-merged
sections.

Rationale for the file format: I considered several different file
format for representing the dependency graph. I chose the above
format because a line-oriented text file format is easy to handle
by a scripting language. Since the same name is repeated many times
in an output, an output tend to be extremely large, but I think that
the advantage of simplicity outweighs the disadvantage, especially
for those who uses the option for the first time to debug some random
problem.

[grimar]

I looked at the sample provided and I think that if I was a new user, I'd find not clear what is "<internal>" probably.
What about including something like "<internal> is usually a symbol defined by linker" line to the header?

Also I am not sure what is situation now, but before we used to report "<internal>" for linker script defined symbols
in our messages sometimes. Would be nice to have a test for that case.

About printing "-": I am not sure how much it is usefull? Actually it was a bit confusing to see it for me at first. I think if file
is provided by command line it is enough to print "<commandline> <filename>" probably.

[MaskRay]

I think this feature will be very useful. If section-level dependency information (--gc-sections, --icf=) is required, we may need some variations of the triple representation ((<from input section>, <symbol>, <to input section>)) proposed in https://lists.llvm.org/pipermail/llvm-dev/2019-February/130565.html

lld/ELF/Driver.cpp

266

Should onCommandLine be set for a LazyObjFile?

[ruiu]

• remove "-" from "<commandline>" lines

[ruiu]

In D67388#1664387, @grimar wrote:

I looked at the sample provided and I think that if I was a new user, I'd find not clear what is "<internal>" probably.
What about including something like "<internal> is usually a symbol defined by linker" line to the header?

Also I am not sure what is situation now, but before we used to report "<internal>" for linker script defined symbols
in our messages sometimes. Would be nice to have a test for that case.

"<internal>" does not represent a symbol but a file. Ideally we should give more meaningful name for each virtual file, but I think that's beyond the scope of this patch.

About printing "-": I am not sure how much it is usefull? Actually it was a bit confusing to see it for me at first. I think if file
is provided by command line it is enough to print "<commandline> <filename>" probably.

I can remove "-" from the "<commandline>" lines.

[ruiu]

lld/ELF/Driver.cpp

266

I can but we don't have to because we are not going to use the bit for LazyObjFile.

[grimar]

In D67388#1664414, @ruiu wrote:

In D67388#1664387, @grimar wrote:

I looked at the sample provided and I think that if I was a new user, I'd find not clear what is "<internal>" probably.
What about including something like "<internal> is usually a symbol defined by linker" line to the header?

Also I am not sure what is situation now, but before we used to report "<internal>" for linker script defined symbols
in our messages sometimes. Would be nice to have a test for that case.

"<internal>" does not represent a symbol but a file. Ideally we should give more meaningful name for each virtual file, but I think that's beyond the scope of this patch.

If it reports "<internal>" for a symbol from a linker script still - it should be mentioned in the header. Otherwise it might be not clear where a sybmol is coming from.

[ruiu]

Here is an example of a simple post-link analysis using good old awk command. Assume file graph contains an output of --print-dependency-graph generated when linking bin/llvm-strings.

You noticed that Path.cpp.o in libLLVMSupport.a gets linked and were wondering why. You can get a list of files that depend on Path.cpp.o with the following command:

$ awk '$2 == "lib/libLLVMSupport.a(Path.cpp.o)" { print $1 }' graph | sort -u
lib/libLLVMSupport.a(CommandLine.cpp.o)
lib/libLLVMSupport.a(MD5.cpp.o)
lib/libLLVMSupport.a(MemoryBuffer.cpp.o)
lib/libLLVMSupport.a(Process.cpp.o)
lib/libLLVMSupport.a(Program.cpp.o)
lib/libLLVMSupport.a(raw_ostream.cpp.o)
lib/libLLVMSupport.a(Signals.cpp.o)

Now you are wondering what symbols are shared between them, so you type in the following command.

$ awk -F'\t' '$2 == "lib/libLLVMSupport.a(Path.cpp.o)" { print $1 " " $3 }' graph | sort -u
lib/libLLVMSupport.a(CommandLine.cpp.o) llvm::sys::fs::current_path(llvm::SmallVectorImpl<char>&)
lib/libLLVMSupport.a(CommandLine.cpp.o) llvm::sys::fs::equivalent(llvm::Twine const&, llvm::Twine const&, bool&)
lib/libLLVMSupport.a(CommandLine.cpp.o) llvm::sys::path::append(llvm::SmallVectorImpl<char>&, llvm::Twine const&, llvm::Twine const&, llvm::Twine const&, llvm::Twine const&)
lib/libLLVMSupport.a(CommandLine.cpp.o) llvm::sys::path::filename(llvm::StringRef, llvm::sys::path::Style)
lib/libLLVMSupport.a(CommandLine.cpp.o) llvm::sys::path::is_relative(llvm::Twine const&, llvm::sys::path::Style)
lib/libLLVMSupport.a(CommandLine.cpp.o) llvm::sys::path::parent_path(llvm::StringRef, llvm::sys::path::Style)
lib/libLLVMSupport.a(MD5.cpp.o) llvm::ArrayRef<unsigned char> llvm::makeArrayRef<unsigned char>(unsigned char const*, unsigned long)
lib/libLLVMSupport.a(MD5.cpp.o) void llvm::SmallVectorTemplateBase<char, true>::uninitialized_move<char*, char*>(char*, char*, char*)
lib/libLLVMSupport.a(MemoryBuffer.cpp.o) llvm::sys::fs::closeFile(int&)
lib/libLLVMSupport.a(MemoryBuffer.cpp.o) llvm::sys::fs::getStdinHandle()
lib/libLLVMSupport.a(MemoryBuffer.cpp.o) llvm::sys::fs::mapped_file_region::alignment()
lib/libLLVMSupport.a(MemoryBuffer.cpp.o) llvm::sys::fs::mapped_file_region::const_data() const
lib/libLLVMSupport.a(MemoryBuffer.cpp.o) llvm::sys::fs::mapped_file_region::~mapped_file_region()
lib/libLLVMSupport.a(MemoryBuffer.cpp.o) llvm::sys::fs::mapped_file_region::mapped_file_region(int, llvm::sys::fs::mapped_file_region::mapmode, unsigned long, unsigned long, std::error_code&)
lib/libLLVMSupport.a(MemoryBuffer.cpp.o) llvm::sys::fs::openNativeFileForRead(llvm::Twine const&, llvm::sys::fs::OpenFlags, llvm::SmallVectorImpl<char>*)
lib/libLLVMSupport.a(MemoryBuffer.cpp.o) llvm::sys::fs::openNativeFile(llvm::Twine const&, llvm::sys::fs::CreationDisposition, llvm::sys::fs::FileAccess, llvm::sys::fs::OpenFlags, unsigned int)
lib/libLLVMSupport.a(MemoryBuffer.cpp.o) llvm::sys::fs::readNativeFile(int, llvm::MutableArrayRef<char>)
lib/libLLVMSupport.a(MemoryBuffer.cpp.o) llvm::sys::fs::readNativeFileSlice(int, llvm::MutableArrayRef<char>, unsigned long)
lib/libLLVMSupport.a(MemoryBuffer.cpp.o) llvm::sys::fs::status(int, llvm::sys::fs::file_status&)
lib/libLLVMSupport.a(Process.cpp.o) llvm::SmallString<128u>::SmallString(llvm::StringRef)
lib/libLLVMSupport.a(Process.cpp.o) llvm::SmallVector<char, 128u>::SmallVector<char const*, void>(char const*, char const*)
lib/libLLVMSupport.a(Process.cpp.o) llvm::sys::fs::access(llvm::Twine const&, llvm::sys::fs::AccessMode)
lib/libLLVMSupport.a(Process.cpp.o) llvm::sys::fs::equivalent(llvm::Twine const&, llvm::Twine const&, bool&)
lib/libLLVMSupport.a(Process.cpp.o) llvm::sys::fs::exists(llvm::Twine const&)
lib/libLLVMSupport.a(Process.cpp.o) llvm::sys::path::append(llvm::SmallVectorImpl<char>&, llvm::Twine const&, llvm::Twine const&, llvm::Twine const&, llvm::Twine const&)
lib/libLLVMSupport.a(Process.cpp.o) llvm::sys::path::is_absolute(llvm::Twine const&, llvm::sys::path::Style)
lib/libLLVMSupport.a(Process.cpp.o) std::chrono::duration<long, std::ratio<1l, 1000000000l> >::count() const
lib/libLLVMSupport.a(Process.cpp.o) std::chrono::duration<long, std::ratio<1l, 1000000000l> >::duration<long, void>(long const&)
lib/libLLVMSupport.a(Process.cpp.o) std::chrono::duration<long, std::ratio<1l, 1l> >::count() const
lib/libLLVMSupport.a(Process.cpp.o) std::chrono::duration<long, std::ratio<1l, 1l> >::duration<long, void>(long const&)
lib/libLLVMSupport.a(Process.cpp.o) std::chrono::time_point<std::chrono::_V2::system_clock, std::chrono::duration<long, std::ratio<1l, 1000000000l> > >::time_since_epoch() const
lib/libLLVMSupport.a(Program.cpp.o) llvm::SmallString<128u>::SmallString(llvm::StringRef)
lib/libLLVMSupport.a(Program.cpp.o) llvm::SmallVector<char, 128u>::SmallVector<char const*, void>(char const*, char const*)
lib/libLLVMSupport.a(Program.cpp.o) llvm::SmallVectorTemplateCommon<llvm::StringRef, void>::back()
lib/libLLVMSupport.a(Program.cpp.o) llvm::sys::fs::access(llvm::Twine const&, llvm::sys::fs::AccessMode)
lib/libLLVMSupport.a(Program.cpp.o) llvm::sys::fs::can_execute(llvm::Twine const&)
lib/libLLVMSupport.a(Program.cpp.o) llvm::sys::fs::exists(llvm::Twine const&)
lib/libLLVMSupport.a(Program.cpp.o) llvm::sys::path::append(llvm::SmallVectorImpl<char>&, llvm::Twine const&, llvm::Twine const&, llvm::Twine const&, llvm::Twine const&)
lib/libLLVMSupport.a(raw_ostream.cpp.o) llvm::sys::fs::openFile(llvm::Twine const&, int&, llvm::sys::fs::CreationDisposition, llvm::sys::fs::FileAccess, llvm::sys::fs::OpenFlags, unsigned int)
lib/libLLVMSupport.a(Signals.cpp.o) llvm::sys::fs::access(llvm::Twine const&, llvm::sys::fs::AccessMode)
lib/libLLVMSupport.a(Signals.cpp.o) llvm::sys::fs::createTemporaryFile(llvm::Twine const&, llvm::StringRef, int&, llvm::SmallVectorImpl<char>&)
lib/libLLVMSupport.a(Signals.cpp.o) llvm::sys::fs::createTemporaryFile(llvm::Twine const&, llvm::StringRef, llvm::SmallVectorImpl<char>&)
lib/libLLVMSupport.a(Signals.cpp.o) llvm::sys::fs::exists(llvm::Twine const&)
lib/libLLVMSupport.a(Signals.cpp.o) llvm::sys::fs::getMainExecutable[abi:cxx11](char const*, void*)
lib/libLLVMSupport.a(Signals.cpp.o) llvm::sys::fs::remove(llvm::Twine const&, bool)
lib/libLLVMSupport.a(Signals.cpp.o) llvm::sys::path::parent_path(llvm::StringRef, llvm::sys::path::Style)

You can repeat this process until you reach "<commandline>" file.

[MaskRay]

In D67388#1664420, @grimar wrote:

In D67388#1664414, @ruiu wrote:

In D67388#1664387, @grimar wrote:

I looked at the sample provided and I think that if I was a new user, I'd find not clear what is "<internal>" probably.
What about including something like "<internal> is usually a symbol defined by linker" line to the header?

Also I am not sure what is situation now, but before we used to report "<internal>" for linker script defined symbols
in our messages sometimes. Would be nice to have a test for that case.

"<internal>" does not represent a symbol but a file. Ideally we should give more meaningful name for each virtual file, but I think that's beyond the scope of this patch.

If it reports "<internal>" for a symbol from a linker script still - it should be mentioned in the header. Otherwise it might be not clear where a sybmol is coming from.

If we want to have a meaningful file name for synthesized sections, linker synthesized symbols, and SymbolAssignment symbols, we have to create a new InputFile::Kind

std::string lld::toString(const InputFile *f) {
  if (!f)  // this can be null for various reasons above
    return "<internal>";

[grimar]

In D67388#1664463, @MaskRay wrote:

In D67388#1664420, @grimar wrote:

In D67388#1664414, @ruiu wrote:

In D67388#1664387, @grimar wrote:

I looked at the sample provided and I think that if I was a new user, I'd find not clear what is "<internal>" probably.
What about including something like "<internal> is usually a symbol defined by linker" line to the header?

Also I am not sure what is situation now, but before we used to report "<internal>" for linker script defined symbols
in our messages sometimes. Would be nice to have a test for that case.

"<internal>" does not represent a symbol but a file. Ideally we should give more meaningful name for each virtual file, but I think that's beyond the scope of this patch.

If it reports "<internal>" for a symbol from a linker script still - it should be mentioned in the header. Otherwise it might be not clear where a sybmol is coming from.

If we want to have a meaningful file name for synthesized sections, linker synthesized symbols, and SymbolAssignment symbols, we have to create a new InputFile::Kind

std::string lld::toString(const InputFile *f) {
  if (!f)  // this can be null for various reasons above
    return "<internal>";

I suggested the same previously: D45375

[MaskRay]

In D67388#1664465, @grimar wrote:

In D67388#1664463, @MaskRay wrote:

In D67388#1664420, @grimar wrote:

In D67388#1664414, @ruiu wrote:

In D67388#1664387, @grimar wrote:

I looked at the sample provided and I think that if I was a new user, I'd find not clear what is "<internal>" probably.
What about including something like "<internal> is usually a symbol defined by linker" line to the header?

Also I am not sure what is situation now, but before we used to report "<internal>" for linker script defined symbols
in our messages sometimes. Would be nice to have a test for that case.

"<internal>" does not represent a symbol but a file. Ideally we should give more meaningful name for each virtual file, but I think that's beyond the scope of this patch.

If it reports "<internal>" for a symbol from a linker script still - it should be mentioned in the header. Otherwise it might be not clear where a sybmol is coming from.

If we want to have a meaningful file name for synthesized sections, linker synthesized symbols, and SymbolAssignment symbols, we have to create a new InputFile::Kind

std::string lld::toString(const InputFile *f) {
  if (!f)  // this can be null for various reasons above
    return "<internal>";

I suggested the same previously: D45375

Interesting. So this current form of the patch is actually an alternative representation of the existing feature --cref. I wonder if we can change the output format of --cref and reuse the option name, or name it --cref=format.

[peter.smith]

I think that this will definitely be useful, especially to work out all the files that are involved in referencing a symbol. Looking to the future I'd recommend keeping the symbol dependency information, which is mostly useful for objects and libraries, from relocation dependencies as used in GC as the output is likely to be different and will answer different questions. How do you want the final interface to look when there are many diagnostic analyses?

As I think I mentioned in the discussion on the mailing lists, the output of the final state of a data structure can lose information that is useful in tracking problems. A complementary technique is to optionally print information as we process, this can help to fix problems caused by ordering of libraries.

lld/ELF/Driver.cpp

876

There are many types of dependency graph, for example the undefined symbol dependencies are not the same as GC/ICF dependencies. I think it would be worth being more specific, with the option name. There are also some options on future expansion:

• One flag for each dependency like option each with a different file name
• One flag for each dependency, but outputting to a single "map like" file
• An aggregated option like --dependency=<comma separated list> of topics.

1680

This is more a slice of the internal symbol table. In particular it is the set of symbols defined by other objects. We may want to be precise about what we are printing, an object could define a weak symbol, but not refer to it, only to have it defined non-weakly in another file. This would show up as uses.

For each object file participating in the linking of <object file>, print the Symbols that were defined by other object files.
The format of the file is:
# <file1> <file2> <symbol>
# meaning <file1> has <symbol> in its symbol table which was defined in <file2>.

1686

Personally I'd prefer not to include the files on the command line in this particular diagnostic. Although that information is useful I'd prefer to see it in a different diagnostic option to keep this one focused on symbol dependencies.

I can see myself writing a python/perl script to process this for large programs and whereas I could simply cut a static number of lines for the header, I'd have to account for the <commandline> in the parser.

[MaskRay]

Closed by D82437

[pcc]

I think this is actually a different feature to D82437?

[MaskRay]

In D67388#2192129, @pcc wrote:

I think this is actually a different feature to D82437?

My bad... I intended to close D65430

[mehdi_amini]

This can be useful!

For me right now: building a shared library from objects built with -ffunction-sections, I'm mostly interested in a finer grain information than "which object file gets loaded": I'd like to be able to track down why a particular symbols end up in the final binary / isn't stripped.

lld/ELF/Config.h

struct Configuration {
   bool noinhibitExec;
   bool nostdlib;
   bool oFormatBinary;
   bool omagic;
   bool optRemarksWithHotness;
   bool pacPlt;
   bool picThunk;
   bool pie;
+  bool printDependencyGraph;
   bool printGcSections;
   bool printIcfSections;
   bool relocatable;
   bool relrPackDynRelocs;
   bool saveTemps;
   bool singleRoRx;
   bool shared;
   bool isStatic = false;

lld/ELF/Driver.cpp

files.push_back(
         make<SharedFile>(mbref, withLOption ? path::filename(path) : path));
     return;
   case file_magic::bitcode:
   case file_magic::elf_relocatable:
     if (inLib)
       files.push_back(make<LazyObjFile>(mbref, "", 0));
     else
       files.push_back(createObjectFile(mbref));
+    files.back()->onCommandLine = true;
     break;
   default:
     error(path + ": unknown file type");
   }
 }
 
 // Add a given library by searching it from input search paths.
 void LinkerDriver::addLibrary(StringRef name) {
static void readConfigs(opt::InputArgList &args) {
   config->optRemarksPasses = args.getLastArgValue(OPT_opt_remarks_passes);
   config->optRemarksWithHotness = args.hasArg(OPT_opt_remarks_with_hotness);
   config->optRemarksFormat = args.getLastArgValue(OPT_opt_remarks_format);
   config->optimize = args::getInteger(args, OPT_O, 1);
   config->orphanHandling = getOrphanHandling(args);
   config->outputFile = args.getLastArgValue(OPT_o);
   config->pacPlt = args.hasArg(OPT_pac_plt);
   config->pie = args.hasFlag(OPT_pie, OPT_no_pie, false);
+  config->printDependencyGraph =
+      args.hasFlag(OPT_print_dependency_graph, OPT_no_print_dependency_graph, false);
   config->printIcfSections =
       args.hasFlag(OPT_print_icf_sections, OPT_no_print_icf_sections, false);
   config->printGcSections =
       args.hasFlag(OPT_print_gc_sections, OPT_no_print_gc_sections, false);
   config->printSymbolOrder =
       args.getLastArgValue(OPT_print_symbol_order);
   config->rpath = getRpath(args);
   config->relocatable = args.hasArg(OPT_relocatable);

 }
 
 static const char *libcallRoutineNames[] = {
 #define HANDLE_LIBCALL(code, name) name,
 #include "llvm/IR/RuntimeLibcalls.def"
 #undef HANDLE_LIBCALL
 };
 
+// Print out dependencies between files for off-line analysis.
+static void dumpSymbols() {
+  outs() << "# This is a dump of the internal symbol table of the lld linker\n"
+         << "# when linking '" << config->outputFile << "'.\n#\n"
+         << "# The format of this file is as follows:\n#\n"
+         << "#  <file1> <file2> <symbol>\n#\n"
+         << "# meaning <file1> uses <symbol> defined by <file2>.\n\n";
+
+  for (InputFile *file : objectFiles)
+    if (file->onCommandLine)
+      outs() << "<commandline>\t" << toString(file) << "\t-\n";
+
+  for (InputFile *file : objectFiles) {
+    for (Symbol *sym : file->getSymbols()) {
+      if (sym->isLocal() || sym->file == file)
+        continue;
+
+      outs() << toString(file) << "\t" << toString(sym->file) << "\t"
+             << toString(*sym) << "\n";
+    }
+  }
+}
+
 // Do actual linking. Note that when this function is called,
 // all linker scripts have already been parsed.
 template <class ELFT> void LinkerDriver::link(opt::InputArgList &args) {
   // If a -hash-style option was not given, set to a default value,
   // which varies depending on the target.
   if (!args.hasArg(OPT_hash_style)) {
     if (config->emachine == EM_MIPS)
       config->sysvHash = true;
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>();
   }
 
+  if (config->printDependencyGraph)
+    dumpSymbols();
+
   // Write the result to the file.
   writeResult<ELFT>();
 }

lld/ELF/InputFiles.h

public:
 
   // If this is an architecture-specific file, the following members
   // have ELF type (i.e. ELF{32,64}{LE,BE}) and target machine type.
   ELFKind ekind = ELFNoneKind;
   uint16_t emachine = llvm::ELF::EM_NONE;
   uint8_t osabi = 0;
   uint8_t abiVersion = 0;
 
+  // True if this is an object file and is given directly on the command
+  // line. False if this file is read from an archive file.
+  bool onCommandLine;
+
   // Cache for toString(). Only toString() should use this member.
   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;

lld/ELF/Options.td

 
 def pic_veneer: F<"pic-veneer">,
   HelpText<"Always generate position independent thunks (veneers)">;
 
 defm pie: B<"pie",
     "Create a position independent executable",
     "Do not create a position independent executable (default)">;
 
+defm print_dependency_graph: B<"print-dependency-graph",
+    "Print out the contents of the linker's internal symbol table",
+    "Do not print out the dependency graph (default)">;
+
 defm print_gc_sections: B<"print-gc-sections",
     "List removed unused sections",
     "Do not list removed unused sections (default)">;
 
 defm print_icf_sections: B<"print-icf-sections",
     "List identical folded sections",
     "Do not list identical folded sections (default)">;