[ELF] Add --dependency-file option

[phosek]

Summary

Clang and GCC have a feature (-MD flag) to create a dependency file
in a format that build systems such as Make or Ninja can read, which
specifies all the additional inputs such .h files.

This change introduces the same functionality to lld bringing it to
feature parity with ld and gold which gained this feature recently.
See https://sourceware.org/bugzilla/show_bug.cgi?id=22843 for more
details and discussion.

The implementation corresponds to -MD -MP compiler flag where the
generated dependency file also includes phony targets which works
around the errors where the dependency is removed. This matches the
format used by ld and gold.

Fixes PR42806

[phosek]

This is an updated version of D65430 which matches the feature implemented by ld and gold in https://sourceware.org/git/?p=binutils-gdb.git;a=commitdiff;h=f37b21b481a7804a13c5806098c19b6119288ba4. I'm happy to abandon this change in favor of D65430 if @ruiu wants to go ahead with his change.

[MaskRay]

In D82437#2110769, @phosek wrote:

This is an updated version of D65430 which matches the feature implemented by ld and gold in https://sourceware.org/git/?p=binutils-gdb.git;a=commitdiff;h=f37b21b481a7804a13c5806098c19b6119288ba4. I'm happy to abandon this change in favor of D65430 if @ruiu wants to go ahead with his change.

You can just paste https://sourceware.org/bugzilla/show_bug.cgi?id=22843 beside "ld and gold which gained this feature recently" in the description.

For the tests, you can read reproduce* and make a summary.

lld/ELF/Options.td

135

EEq

We don't want to support -dependency-file

[MaskRay]

lld/ELF/Driver.cpp

1614

The backslash escaping rule is complex. Do you have a description how it works? We should have a test as well. If it can cause problems on Windows, add UNSUPPORTED: system-windows

[MaskRay]

lld/ELF/Driver.cpp

1614

@mcgrathr https://sourceware.org/git/?p=binutils-gdb.git;a=commit;h=f37b21b481a7804a13c5806098c19b6119288ba4 does not escape $ or \

[phosek]

lld/ELF/Driver.cpp

1614

See the comment above this lambda:

We use the same escape rules as Clang/GCC which are accepted by Make/Ninja:
* A space is escaped by a backslash which itself must be escaped.
* A hash sign is escaped by a single backslash.
* $ is escapes as $$.

I can drop this if we decide that we don't want to support escaping, but I wanted to match what the existing consumers expect.

[phosek]

Do you have any other comments? I'd like to see this landed.

[MaskRay]

lld/test/ELF/dependency-file.s

8

Backslashes and # are not tested. If they can be problems on Windows, just add UNSUPPORTED: system-windows

9

Can you use FileCheck -DFILE=%t so that the CHECK lines can test the full paths?

[MaskRay]

Ping

[phosek]

In D82437#2178812, @MaskRay wrote:

Ping

Updated, can you take a look again?

[MaskRay]

Thanks!

lld/ELF/Driver.cpp

1584

I hope @mcgrathr can spend a bit more time inspecting the wording here as he is the author of the GNU ld and gold patch.

lld/test/ELF/dependency-file.s

4

x86_64-unknown-linux -> x86_64

[phosek]

lld/ELF/Driver.cpp

1584

I talked to @mcgrathr offline and he said it looks fine.

[phosek]

I'm still debugging the failure which has showed up on some bots:

/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/install/stage1/bin/clang++  -fPIC -fvisibility-inlines-hidden -Werror -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -pedantic -Wno-long-long -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wstring-conversion -fdiagnostics-color -ffunction-sections -fdata-sections -O3  -fuse-ld=lld -Wl,--color-diagnostics -Wl,-allow-shlib-undefined    -Wl,-O3 -Wl,--gc-sections unittests/Target/X86/CMakeFiles/X86Tests.dir/MachineSizeOptsTest.cpp.o  -o unittests/Target/X86/X86Tests  lib/libLLVMAnalysis.a  lib/libLLVMCodeGen.a  lib/libLLVMCore.a  lib/libLLVMMC.a  lib/libLLVMMIRParser.a  lib/libLLVMSupport.a  lib/libLLVMTarget.a  lib/libLLVMX86CodeGen.a  lib/libLLVMX86Desc.a  lib/libLLVMX86Info.a  lib/libLLVMSupport.a  -lpthread  lib/libgtest_main.a  lib/libgtest.a  -lpthread  lib/libLLVMAsmParser.a  lib/libLLVMMCDisassembler.a  lib/libLLVMAsmPrinter.a  lib/libLLVMDebugInfoDWARF.a  lib/libLLVMCFGuard.a  lib/libLLVMGlobalISel.a  lib/libLLVMSelectionDAG.a  lib/libLLVMCodeGen.a  lib/libLLVMBitWriter.a  lib/libLLVMScalarOpts.a  lib/libLLVMAggressiveInstCombine.a  lib/libLLVMInstCombine.a  lib/libLLVMTarget.a  lib/libLLVMTransformUtils.a  lib/libLLVMAnalysis.a  lib/libLLVMObject.a  lib/libLLVMBitReader.a  lib/libLLVMMCParser.a  lib/libLLVMMC.a  lib/libLLVMDebugInfoCodeView.a  lib/libLLVMDebugInfoMSF.a  lib/libLLVMTextAPI.a  lib/libLLVMProfileData.a  lib/libLLVMCore.a  lib/libLLVMBinaryFormat.a  lib/libLLVMRemarks.a  lib/libLLVMBitstreamReader.a  lib/libLLVMSupport.a  -lrt  -ldl  -lpthread  -lm  /usr/lib64/libz.so  lib/libLLVMDemangle.a  -lpthread && :
ld.lld: /home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/llvm-project/llvm/include/llvm/ADT/DenseMap.h:408: void llvm::DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT>::moveFromOldBuckets(BucketT*, BucketT*) [with DerivedT = llvm::DenseMap<llvm::StringRef, llvm::detail::DenseSetEmpty, llvm::DenseMapInfo<llvm::StringRef>, llvm::detail::DenseSetPair<llvm::StringRef> >; KeyT = llvm::StringRef; ValueT = llvm::detail::DenseSetEmpty; KeyInfoT = llvm::DenseMapInfo<llvm::StringRef>; BucketT = llvm::detail::DenseSetPair<llvm::StringRef>]: Assertion `!FoundVal && "Key already in new map?"' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace.
Stack dump:
0.	Program arguments: /home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/install/stage1/bin/ld.lld --eh-frame-hdr -m elf64lppc -dynamic-linker /lib64/ld64.so.2 -o unittests/Target/X86/X86Tests /usr/lib/gcc/ppc64le-redhat-linux/8/../../../../lib64/crt1.o /usr/lib/gcc/ppc64le-redhat-linux/8/../../../../lib64/crti.o /usr/lib/gcc/ppc64le-redhat-linux/8/crtbegin.o -L/usr/lib/gcc/ppc64le-redhat-linux/8 -L/usr/lib/gcc/ppc64le-redhat-linux/8/../../../../lib64 -L/lib/../lib64 -L/usr/lib/../lib64 -L/usr/lib/gcc/ppc64le-redhat-linux/8/../../.. -L/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/install/stage1/bin/../lib -L/lib -L/usr/lib --color-diagnostics -allow-shlib-undefined -O3 --gc-sections unittests/Target/X86/CMakeFiles/X86Tests.dir/MachineSizeOptsTest.cpp.o lib/libLLVMAnalysis.a lib/libLLVMCodeGen.a lib/libLLVMCore.a lib/libLLVMMC.a lib/libLLVMMIRParser.a lib/libLLVMSupport.a lib/libLLVMTarget.a lib/libLLVMX86CodeGen.a lib/libLLVMX86Desc.a lib/libLLVMX86Info.a lib/libLLVMSupport.a -lpthread lib/libgtest_main.a lib/libgtest.a -lpthread lib/libLLVMAsmParser.a lib/libLLVMMCDisassembler.a lib/libLLVMAsmPrinter.a lib/libLLVMDebugInfoDWARF.a lib/libLLVMCFGuard.a lib/libLLVMGlobalISel.a lib/libLLVMSelectionDAG.a lib/libLLVMCodeGen.a lib/libLLVMBitWriter.a lib/libLLVMScalarOpts.a lib/libLLVMAggressiveInstCombine.a lib/libLLVMInstCombine.a lib/libLLVMTarget.a lib/libLLVMTransformUtils.a lib/libLLVMAnalysis.a lib/libLLVMObject.a lib/libLLVMBitReader.a lib/libLLVMMCParser.a lib/libLLVMMC.a lib/libLLVMDebugInfoCodeView.a lib/libLLVMDebugInfoMSF.a lib/libLLVMTextAPI.a lib/libLLVMProfileData.a lib/libLLVMCore.a lib/libLLVMBinaryFormat.a lib/libLLVMRemarks.a lib/libLLVMBitstreamReader.a lib/libLLVMSupport.a -lrt -ldl -lpthread -lm /usr/lib64/libz.so lib/libLLVMDemangle.a -lpthread -lstdc++ -lm -lgcc_s -lgcc -lc -lgcc_s -lgcc /usr/lib/gcc/ppc64le-redhat-linux/8/crtend.o /usr/lib/gcc/ppc64le-redhat-linux/8/../../../../lib64/crtn.o 
 #0 0x000000001042e3b8 llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/install/stage1/bin/ld.lld+0x1042e3b8)
 #1 0x000000001042e4e0 PrintStackTraceSignalHandler(void*) (/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/install/stage1/bin/ld.lld+0x1042e4e0)
 #2 0x000000001042bbd4 llvm::sys::RunSignalHandlers() (/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/install/stage1/bin/ld.lld+0x1042bbd4)
 #3 0x000000001042bdac SignalHandler(int) (/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/install/stage1/bin/ld.lld+0x1042bdac)
 #4 0x00007fff9ff004d8 (linux-vdso64.so.1+0x4d8)
 #5 0x00007fff9f874308 raise (/lib64/libc.so.6+0x44308)
 #6 0x00007fff9f85438c abort (/lib64/libc.so.6+0x2438c)
 #7 0x00007fff9f8678d0 __assert_fail_base (/lib64/libc.so.6+0x378d0)
 #8 0x00007fff9f867974 __assert_fail (/lib64/libc.so.6+0x37974)
 #9 0x000000001048dc8c llvm::DenseMap<llvm::StringRef, llvm::detail::DenseSetEmpty, llvm::DenseMapInfo<llvm::StringRef>, llvm::detail::DenseSetPair<llvm::StringRef> >::grow(unsigned int) (/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/install/stage1/bin/ld.lld+0x1048dc8c)
#10 0x00000000105c360c lld::elf::readFile(llvm::StringRef) (/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/install/stage1/bin/ld.lld+0x105c360c)
#11 0x000000001054526c lld::elf::LinkerDriver::addFile(llvm::StringRef, bool) (/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/install/stage1/bin/ld.lld+0x1054526c)
#12 0x0000000010545858 lld::elf::LinkerDriver::addLibrary(llvm::StringRef) (/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/install/stage1/bin/ld.lld+0x10545858)
#13 0x0000000010545dfc lld::elf::LinkerDriver::createFiles(llvm::opt::InputArgList&) (/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/install/stage1/bin/ld.lld+0x10545dfc)
#14 0x0000000010309bc0 lld::elf::LinkerDriver::main(llvm::ArrayRef<char const*>) (/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/install/stage1/bin/ld.lld+0x10309bc0)
#15 0x00000000105666a4 lld::elf::link(llvm::ArrayRef<char const*>, bool, llvm::raw_ostream&, llvm::raw_ostream&) (/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/install/stage1/bin/ld.lld+0x105666a4)
#16 0x0000000010306d0c main (/home/buildbots/ppc64le-lld-multistage-test/ppc64le-lld-multistage-test/install/stage1/bin/ld.lld+0x10306d0c)
#17 0x00007fff9f8549f8 generic_start_main.isra.0 (/lib64/libc.so.6+0x249f8)
#18 0x00007fff9f854be4 __libc_start_main (/lib64/libc.so.6+0x24be4)
clang-12: error: unable to execute command: Aborted (core dumped)

[MaskRay]

CC @nemanjai who can test this patch on ppc64be.

[phosek]

In D82437#2189738, @MaskRay wrote:

CC @nemanjai who can test this patch on ppc64be.

I have also managed to reproduce the failure locally on x86_64 with assertions enabled. I don't understand the failure though. It seems like the insertion into the SetVector is failing because the element is already present (which shouldn't cause a failure), and if I insert a presence check before calling insert, it returns false.

[phosek]

Switching from llvm::SetVector<StringRef> to llvm::SetVector<llvm::CachedHashString> addresses the issue.

[MaskRay]

LGTM.

lld/ELF/Options.td

136

I wonder whether <file> will work better than <path> because file conveys more information: a path can be either a file or a directory (if we exclude other possibilities).

lld/ELF/Config.h

 //===- Config.h -------------------------------------------------*- C++ -*-===//
 //
 // 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_CONFIG_H
 #define LLD_ELF_CONFIG_H
 
 #include "lld/Common/ErrorHandler.h"
+#include "llvm/ADT/CachedHashString.h"
 #include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/BinaryFormat/ELF.h"
 #include "llvm/Support/CachePruning.h"
 #include "llvm/Support/CodeGen.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/GlobPattern.h"
 #include <atomic>

 // This struct contains the global configuration for the linker.
 // Most fields are direct mapping from the command line options
 // and such fields have the same name as the corresponding options.
 // Most fields are initialized by the driver.
 struct Configuration {
   uint8_t osabi = 0;
   uint32_t andFeatures = 0;
   llvm::CachePruningPolicy thinLTOCachePolicy;
+  llvm::SetVector<llvm::CachedHashString> dependencyFiles; // for --dependency-file
   llvm::StringMap<uint64_t> sectionStartMap;
   llvm::StringRef bfdname;
   llvm::StringRef chroot;
-  llvm::StringRef dynamicLinker;
+  llvm::StringRef dependencyFile;
   llvm::StringRef dwoDir;
+  llvm::StringRef dynamicLinker;
   llvm::StringRef entry;
   llvm::StringRef emulation;
   llvm::StringRef fini;
   llvm::StringRef init;
   llvm::StringRef ltoAAPipeline;
   llvm::StringRef ltoCSProfileFile;
   llvm::StringRef ltoNewPmPasses;
   llvm::StringRef ltoObjPath;

lld/ELF/Driver.cpp

static void readConfigs(opt::InputArgList &args) {
   config->chroot = args.getLastArgValue(OPT_chroot);
   config->compressDebugSections = getCompressDebugSections(args);
   config->cref = args.hasFlag(OPT_cref, OPT_no_cref, false);
   config->defineCommon = args.hasFlag(OPT_define_common, OPT_no_define_common,
                                       !args.hasArg(OPT_relocatable));
   config->optimizeBBJumps =
       args.hasFlag(OPT_optimize_bb_jumps, OPT_no_optimize_bb_jumps, false);
   config->demangle = args.hasFlag(OPT_demangle, OPT_no_demangle, true);
+  config->dependencyFile = args.getLastArgValue(OPT_dependency_file);
   config->dependentLibraries = args.hasFlag(OPT_dependent_libraries, OPT_no_dependent_libraries, true);
   config->disableVerify = args.hasArg(OPT_disable_verify);
   config->discard = getDiscard(args);
   config->dwoDir = args.getLastArgValue(OPT_plugin_opt_dwo_dir_eq);
   config->dynamicLinker = getDynamicLinker(args);
   config->ehFrameHdr =
       args.hasFlag(OPT_eh_frame_hdr, OPT_no_eh_frame_hdr, false);
   config->emitLLVM = args.hasArg(OPT_plugin_opt_emit_llvm, false);
if (auto *lo = dyn_cast<LazyObject>(sym))
     mb = lo->file->mb;
   else
     mb = cast<LazyArchive>(sym)->getMemberBuffer();
 
   if (isBitcode(mb))
     sym->fetch();
 }
 
+// Handle --dependency-file=<path>. If that option is given, lld creates a
+// file at a given path with the following contents:
+//
+//   <output-file>: <input-file> ...
+//
+//   <input-file>:
+//
+// where <output-file> is a pathname of an output file and <input-file>
+// ... is a list of pathnames of all input files. `make` command can read a
+// file in the above format and interpret it as a dependency info. We write
+// phony targets for every <input-file> to avoid an error when that file is
+// removed.
+//
+// This option is useful if you want to make your final executable to depend
+// on all input files including system libraries. Here is why.
+//
+// When you write a Makefile, you usually write it so that the final
+// executable depends on all user-generated object files. Normally, you
+// don't make your executable to depend on system libraries (such as libc)
+// because you don't know the exact paths of libraries, even though system
+// libraries that are linked to your executable statically are technically a
+// part of your program. By using --dependency-file option, you can make
+// lld to dump dependency info so that you can maintain exact dependencies
+// easily.
+static void writeDependencyFile() {
+  std::error_code ec;
+  raw_fd_ostream os(config->dependencyFile, ec, sys::fs::F_None);
+  if (ec) {
+    error("cannot open " + config->dependencyFile + ": " + ec.message());
+    return;
+  }
+
+  // We use the same escape rules as Clang/GCC which are accepted by Make/Ninja:
+  // * A space is escaped by a backslash which itself must be escaped.
+  // * A hash sign is escaped by a single backslash.
+  // * $ is escapes as $$.
+  auto printFilename = [](raw_fd_ostream &os, StringRef filename) {
+    llvm::SmallString<256> nativePath;
+    llvm::sys::path::native(filename.str(), nativePath);
+    llvm::sys::path::remove_dots(nativePath, /*remove_dot_dot=*/true);
+    for (unsigned i = 0, e = nativePath.size(); i != e; ++i) {
+      if (nativePath[i] == '#') {
+        os << '\\';
+      } else if (nativePath[i] == ' ') {
+        os << '\\';
+        unsigned j = i;
+        while (j > 0 && nativePath[--j] == '\\')
+          os << '\\';
+      } else if (nativePath[i] == '$') {
+        os << '$';
+      }
+      os << nativePath[i];
+    }
+  };
+
+  os << config->outputFile << ":";
+  for (StringRef path : config->dependencyFiles) {
+    os << " \\\n ";
+    printFilename(os, path);
+  }
+  os << "\n";
+
+  for (StringRef path : config->dependencyFiles) {
+    os << "\n";
+    printFilename(os, path);
+    os << ":\n";
+  }
+}
+
 // Replaces common symbols with defined symbols reside in .bss sections.
 // This function is called after all symbol names are resolved. As a
 // result, the passes after the symbol resolution won't see any
 // symbols of type CommonSymbol.
 static void replaceCommonSymbols() {
   for (Symbol *sym : symtab->symbols()) {
     auto *s = dyn_cast<CommonSymbol>(sym);
     if (!s)
llvm::erase_if(inputSections, [](InputSectionBase *s) {
     if (auto *isec = dyn_cast<InputSection>(s))
       if (InputSectionBase *rel = isec->getRelocatedSection())
         if (isDebugSection(*rel))
           return true;
 
     return false;
   });
 
+  // Since we now have a complete set of input files, we can create
+  // a .d file to record build dependencies.
+  if (!config->dependencyFile.empty())
+    writeDependencyFile();
+
   // Now that the number of partitions is fixed, save a pointer to the main
   // partition.
   mainPart = &partitions[0];
 
   // Read .note.gnu.property sections from input object files which
   // contain a hint to tweak linker's and loader's behaviors.
   config->andFeatures = getAndFeatures<ELFT>();
 

lld/ELF/InputFiles.cpp

 
 Optional<MemoryBufferRef> elf::readFile(StringRef path) {
   // The --chroot option changes our virtual root directory.
   // This is useful when you are dealing with files created by --reproduce.
   if (!config->chroot.empty() && path.startswith("/"))
     path = saver.save(config->chroot + path);
 
   log(path);
+  config->dependencyFiles.insert(llvm::CachedHashString(path));
 
   auto mbOrErr = MemoryBuffer::getFile(path, -1, false);
   if (auto ec = mbOrErr.getError()) {
     error("cannot open " + path + ": " + ec.message());
     return None;
   }
 
   std::unique_ptr<MemoryBuffer> &mb = *mbOrErr;

lld/ELF/Options.td

 defm define_common: B<"define-common",
     "Assign space to common symbols",
     "Do not assign space to common symbols">;
 
 defm demangle: B<"demangle",
     "Demangle symbol names (default)",
     "Do not demangle symbol names">;
 
+defm dependency_file: EEq<"dependency-file", "Write a dependency file">,
+  MetaVarName<"<file>">;
+
 def disable_new_dtags: F<"disable-new-dtags">,
   HelpText<"Disable new dynamic tags">;
 
 def discard_all: F<"discard-all">, HelpText<"Delete all local symbols">;
 
 def discard_locals: F<"discard-locals">,
   HelpText<"Delete temporary local symbols">;
 

lld/test/ELF/dependency-file.s

+# REQUIRES: x86
+# RUN: mkdir -p %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t/foo.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64 /dev/null -o "%t/bar baz.o"
+# RUN: llvm-mc -filetype=obj -triple=x86_64 /dev/null -o "%t/#quux$.o"
+# RUN: ld.lld -o %t/foo.exe %t/foo.o %t/"bar baz.o" "%t/#quux$.o" --dependency-file=%t/foo.d
+# RUN: FileCheck --match-full-lines -DFILE=%t %s < %t/foo.d
+
+# CHECK:      [[FILE]]{{/|(\\)+}}foo.exe: \
+# CHECK-NEXT:   [[FILE]]{{/|(\\)+}}foo.o \
+# CHECK-NEXT:   [[FILE]]{{/|(\\)+}}bar\ baz.o \
+# CHECK-NEXT:   [[FILE]]{{/|(\\)+}}\#quux$$.o
+# CHECK-EMPTY:
+# CHECK-NEXT: [[FILE]]{{/|(\\)+}}foo.o:
+# CHECK-EMPTY:
+# CHECK-NEXT: [[FILE]]{{/|(\\)+}}bar\ baz.o:
+# CHECK-EMPTY:
+# CHECK-NEXT: [[FILE]]{{/|(\\)+}}\#quux$$.o:
+
+.global _start
+_start: