[lld-macho] Implement -dependency_info (partially - more opcodes needed)

[oontvoo]

Summary

Bug: https://bugs.llvm.org/show_bug.cgi?id=49278
The flag is not well documented, so this implementation is based on observed behaviour.

When specified, -dependency_info <path> produced a text file containing information pertaining to the current linkage, such as input files, output file, linker version, etc.

This file's layout is also not documented, but it seems to be a series of null ('\0') terminated strings in the form <op code><path>

<op code> could be:

`0x00` : linker version
`0x10` : input
`0x11` : files not found(??)
`0x40` : output

<path> : is the file path, except for the linker-version case.

(??) This part is a bit unclear. I think it means all the files the linker attempted to look at, but could not find.

[int3]

As discussed, let's verify that we are emulating ld64's behavior correctly. We should also support the other opcodes (but we can do that in a series of separate diffs)

lld/MachO/Config.h

101–109 ↗

(On Diff #330378)

Judging from the rest of LLD, enum naming convention is generally CamelCase (or FOO_BAR in the case of bitfields / flags).

160–170 ↗

(On Diff #330378)

I'd like the Config to stay as a plain "bag of values" kind of struct -- no methods other than trivial getters. dependencyTracker here can be a global. Also the class can be declared in Driver.cpp / DriverUtils.cpp.

[oontvoo]

updated diff:

• addressed review comments
• added tests

[oontvoo]

Updated test to exclude windows because the paths are in different orders

[int3]

lld/MachO/Driver.cpp

822

no need for llvm::

824

lld/MachO/Driver.h

71–72

This is a very Java-like way of creating singletons :) The rest of the LLD code just uses a global (config, target, inputFiles etc). I think DependencyTracker should follow suit

93

LLVM tries to avoid std::set (and std::map): https://llvm.org/docs/ProgrammersManual.html#set-like-containers-std-set-smallset-setvector-etc

In this case we could use a DenseSet

115–120

The number of files will be pretty small, there's no real need to optimize this. That said... could we take a Twine here instead of using templates?

Nit: Also, I'd prefer if this wasn't a global, at least not with such a generic name. Could we always initialize DependencyTracker. and have its methods be no-ops if -dependency_info wasn't passed? Alternatively, just having this named logDepNotFound would be an improvement, at least in that case we have a hint as to why we're logging it.

lld/MachO/DriverUtils.cpp

263

legit lint

272

no need for llvm::

295

fwiw, the other LLD ports don't use getSpecificAllocSingleton at all... I wonder if it's really that useful an optimization 🤔

299

this isn't necessary, the default DependencyTracker destructor will call the std::set destructor, which will free this memory

lld/test/MachO/Inputs/DependencyDump.py

5

the old LLD for Mach-O code should be going away soon, let's not reference it

lld/test/MachO/dependency-info.s

31

convention is to double-comment lines that aren't passed to FileCheck

[oontvoo]

updated diff

lld/MachO/Driver.h

93

I've thought about this, and IIRC DenseSet's doesn't offer the ordering we need.
And I'd rather not have to dump it to a vector and re-sort at the end.
Is there other ds we could use?

[int3]

lld/MachO/Driver.cpp

57–59

I think we could drop lld:: from both of these

821–831

I don't see why this needs to be in a lambda vs just putting it in the constructor of DependencyTracker (and moving the definition of the ctor into DriverUtils.cpp).

Also, args.getLastArgValue(OPT_dependency_info) will return an empty string if the option is not available, so you can skip the null check

lld/MachO/Driver.h

91–93

re the "weird" comment: I think the purpose of this is so that the build system can re-invoke the linker when any of its input files change (including input files that did not previously exist)

93

ah I see. yeah I guess std::set is good then

106–108

rm?

lld/MachO/DriverUtils.cpp

253

I think we're suppose to pass Twines as const references rather than by value, so that the temporary values they reference don't get freed

[int3]

Also maybe title the diff something like "partially implement" since we have more opcodes to add

[int3]

lld/MachO/Driver.cpp

825

extra parens

826

our other option-related messages include the dash, so it would be nice to use that here too :)

[oontvoo]

updated diff

lld/MachO/Driver.h

91–93

Thanks! removed the comment.

[oontvoo]

rebase

[oontvoo]

updated diff

[thakis]

This breaks tests everywhere, eg http://45.33.8.238/linux/42252/step_11.txt

Please take a look, and revert for now if it takes a while to fix.

[thakis]

Also doesn't build on win and mac:
http://45.33.8.238/win/35446/step_4.txt
http://45.33.8.238/macm1/5982/step_3.txt

(due to the inline on a fun def in a .cpp file)

[thakis]

lld/test/MachO/dependency-info.s

27

I guess the problem is that these lines are sorted by name and libSystem is in the src tree and the rest are generated files, and the order of the names of build dir and src dir isn't predictable.

[thakis]

Reverted in 2554b95db57cfcc13864d9bbb9f4e75892067c14 for now.

[oontvoo]

In D98559#2640336, @thakis wrote:

Reverted in 2554b95db57cfcc13864d9bbb9f4e75892067c14 for now.

Thanks!

[oontvoo]

moved inline functions to header

[oontvoo]

lld/test/MachO/dependency-info.s

27

Ah, good catch! Hmm, maybe I'll just grep -v libSystem.tbd from the output before we FileCheck?
(Does anyone have a better solution?)

[oontvoo]

updated diff

[oontvoo]

bot still unhappy ... reverting again: https://reviews.llvm.org/rG9670d2e4af4c996098089e31b03ca138bc8d27e9

[int3]

lld/test/MachO/dependency-info.s

27

I guess you could just turn all the CHECK-NEXT lines into CHECK-DAG, and leave a comment saying that this is sorted but gives different orders due to the build/src dirs.

(As an aside, I'm not sure having these entries in sorted order is super important... I imagine anything that cares about monitoring dependencies just cares about the unordered set of input files)

[oontvoo]

• fixed test
• fixed build failure at https://lab.llvm.org/buildbot/#/builders/68/builds/9121/steps/4/logs/stdio

[mehdi_amini]

Reverted in 4876ba5b2d6a : the build is broken:

lld/MachO/DriverUtils.cpp:271:8: error: use of overloaded operator '<<' is ambiguous (with operand types 'llvm::raw_fd_ostream' and 'lld::macho::DependencyTracker::DepOpCode')
    os << opcode;
    ~~ ^  ~~~~~~

https://buildkite.com/mlir/mlir-core/builds/12456#920bd17a-4c37-435c-b91d-aca1cc15400b

[oontvoo]

Thanks for the revert! May be this patch is cursed 😕

[oontvoo]

Updated diff: explicitly specified "signed char" to avoid ambiguity

[oontvoo]

Updated diff. rebase.

So it's turned out that this was likely a clang bug (or unimplemented feature).
In clang older than 10.x, it didn't know to cast the enum (DepOpCode) to its underlying type. Hence, << DepOpCode was ambiguous to it because the enum could be converted to any of the integer types.

Simple repro: https://gcc.godbolt.org/z/bT6zE7x77

[int3]

lld/MachO/DriverUtils.cpp

287–288

I think this does the same thing?

lld/test/MachO/dependency-info.s

3–5

can this be removed now that we have CHECK-DAG?

[oontvoo]

I've sent D99210

lld/MachO/Driver.h

 //===- Driver.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_MACHO_DRIVER_H
 #define LLD_MACHO_DRIVER_H
 
 #include "lld/Common/LLVM.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Option/OptTable.h"
 #include "llvm/Support/MemoryBuffer.h"
 
+#include <set>
+#include <type_traits>
+
 namespace llvm {
 namespace MachO {
 class InterfaceFile;
 } // namespace MachO
 } // namespace llvm
 
 namespace lld {
 namespace macho {

 llvm::Optional<InputFile *> loadArchiveMember(MemoryBufferRef, uint32_t modTime,
                                               StringRef archiveName,
                                               bool objCOnly);
 
 uint32_t getModTime(llvm::StringRef path);
 
 void printArchiveMemberLoad(StringRef reason, const InputFile *);
 
+// Helper class to export dependency info.
+class DependencyTracker {
+public:
+  explicit DependencyTracker(llvm::StringRef path);
+
+  // Adds the given path to the set of not-found files.
+  void logFileNotFound(std::string);
+  void logFileNotFound(const llvm::Twine &path);
+
+  // Writes the dependencies to specified path.
+  // The content is sorted by its Op Code, then within each section,
+  // alphabetical order.
+  void write(llvm::StringRef version,
+             const llvm::SetVector<InputFile *> &inputs,
+             llvm::StringRef output);
+
+private:
+  enum DepOpCode : char {
+    // Denotes the linker version.
+    Version = 0x00,
+    // Denotes the input files.
+    Input = 0x10,
+    // Denotes the files that do not exist(?)
+    NotFound = 0x11,
+    // Denotes the output files.
+    Output = 0x40,
+  };
+
+  const llvm::StringRef path;
+  bool active;
+
+  // The paths need to be alphabetically ordered.
+  // We need to own the paths because some of them are temporarily
+  // constructed.
+  std::set<std::string> notFounds;
+};
+
+extern DependencyTracker *depTracker;
+
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/Driver.cpp

 using namespace llvm;
 using namespace llvm::MachO;
 using namespace llvm::object;
 using namespace llvm::opt;
 using namespace llvm::sys;
 using namespace lld;
 using namespace lld::macho;
 
-Configuration *lld::macho::config;
+Configuration *macho::config;
+DependencyTracker *macho::depTracker;
 
 static HeaderFileType getOutputType(const InputArgList &args) {
   // TODO: -r, -dylinker, -preload...
   Arg *outputArg = args.getLastArg(OPT_bundle, OPT_dylib, OPT_execute);
   if (outputArg == nullptr)
     return MH_EXECUTE;
 
   switch (outputArg->getOption().getID()) {
   case OPT_bundle:
findAlongPathsWithExtensions(StringRef name, ArrayRef<StringRef> extensions) {
   SmallString<261> base;
   for (StringRef dir : config->librarySearchPaths) {
     base = dir;
     path::append(base, Twine("lib") + name);
     for (StringRef ext : extensions) {
       Twine location = base + ext;
       if (fs::exists(location))
         return location.str();
+      else
+        depTracker->logFileNotFound(location);
     }
   }
   return {};
 }
 
 static Optional<std::string> findLibrary(StringRef name) {
   if (config->searchDylibsFirst) {
     if (Optional<std::string> path =
if (errOrWriter) {
       error("--reproduce: " + toString(errOrWriter.takeError()));
     }
   }
 
   config = make<Configuration>();
   symtab = make<SymbolTable>();
   target = createTargetInfo(args);
 
+  depTracker =
+      make<DependencyTracker>(args.getLastArgValue(OPT_dependency_info, ""));
+
   config->entry = symtab->addUndefined(args.getLastArgValue(OPT_e, "_main"),
                                        /*file=*/nullptr,
                                        /*isWeakRef=*/false);
   for (const Arg *arg : args.filtered(OPT_u)) {
     config->explicitUndefineds.push_back(symtab->addUndefined(
         arg->getValue(), /*file=*/nullptr, /*isWeakRef=*/false));
   }
 
   for (const Arg *arg : args.filtered(OPT_U))
     symtab->addDynamicLookup(arg->getValue());
 
   config->mapFile = args.getLastArgValue(OPT_map);
   config->outputFile = args.getLastArgValue(OPT_o, "a.out");
   config->headerPad = args::getHex(args, OPT_headerpad, /*Default=*/32);
   config->headerPadMaxInstallNames =
       args.hasArg(OPT_headerpad_max_install_names);
for (const InputFile *file : inputFiles) {
           InputSection *isec = p.second;
           inputSections.push_back(isec);
         }
       }
     }
 
     // Write to an output file.
     writeResult();
+
+    depTracker->write(getLLDVersion(), inputFiles, config->outputFile);
   }
 
   if (config->timeTraceEnabled) {
     if (auto E = timeTraceProfilerWrite(
             args.getLastArgValue(OPT_time_trace_file_eq).str(),
             config->outputFile)) {
       handleAllErrors(std::move(E),
                       [&](const StringError &SE) { error(SE.getMessage()); });

lld/MachO/DriverUtils.cpp

 #include "llvm/ADT/CachedHashString.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Bitcode/BitcodeReader.h"
 #include "llvm/LTO/LTO.h"
 #include "llvm/Option/Arg.h"
 #include "llvm/Option/ArgList.h"
 #include "llvm/Option/Option.h"
 #include "llvm/Support/CommandLine.h"
+#include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Path.h"
 #include "llvm/TextAPI/MachO/InterfaceFile.h"
 #include "llvm/TextAPI/MachO/TextAPIReader.h"
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace llvm::opt;
 using namespace llvm::sys;
std::string macho::createResponseFile(const InputArgList &args) {
   return std::string(data.str());
 }
 
 Optional<std::string> macho::resolveDylibPath(StringRef path) {
   // TODO: if a tbd and dylib are both present, we should check to make sure
   // they are consistent.
   if (fs::exists(path))
     return std::string(path);
+  else
+    depTracker->logFileNotFound(path);
 
   SmallString<261> location = path;
   path::replace_extension(location, ".tbd");
   if (fs::exists(location))
     return std::string(location);
-
+  else
+    depTracker->logFileNotFound(location);
   return {};
 }
 
 // It's not uncommon to have multiple attempts to load a single dylib,
 // especially if it's a commonly re-exported core library.
 static DenseMap<CachedHashStringRef, DylibFile *> loadedDylibs;
 
 Optional<DylibFile *> macho::loadDylib(MemoryBufferRef mbref,

 }
 
 void macho::printArchiveMemberLoad(StringRef reason, const InputFile *f) {
   if (config->printEachFile)
     message(toString(f));
   if (config->printWhyLoad)
     message(reason + " forced load of " + toString(f));
 }
+
+macho::DependencyTracker::DependencyTracker(StringRef path)
+    : path(path), active(!path.empty()) {
+  if (active && fs::exists(path) && !fs::can_write(path)) {
+    warn("Ignoring dependency_info option since specified path is not "
+         "writeable.");
+    active = false;
+  }
+}
+
+inline void macho::DependencyTracker::logFileNotFound(std::string path) {
+  if (active)
+    notFounds.insert(std::move(path));
+}
+
+inline void macho::DependencyTracker::logFileNotFound(const Twine &path) {
+  if (active)
+    notFounds.insert(path.str());
+}
+
+void macho::DependencyTracker::write(llvm::StringRef version,
+                                     const llvm::SetVector<InputFile *> &inputs,
+                                     llvm::StringRef output) {
+  if (!active)
+    return;
+
+  std::error_code ec;
+  llvm::raw_fd_ostream os(path, ec, llvm::sys::fs::OF_None);
+  if (ec) {
+    warn("Error writing dependency info to file");
+    return;
+  }
+
+  auto addDep = [&os](DepOpCode opcode, const StringRef &path) {
+    os << opcode;
+    os << path;
+    os << '\0';
+  };
+
+  addDep(DepOpCode::Version, version);
+
+  // Sort the input by its names.
+  std::vector<StringRef> inputNames;
+  inputNames.reserve(inputs.size());
+  for (InputFile *f : inputs)
+    inputNames.push_back(f->getName());
+  llvm::sort(inputNames,
+             [](const StringRef &a, const StringRef &b) { return a < b; });
+  for (const StringRef &in : inputNames)
+    addDep(DepOpCode::Input, in);
+
+  for (const std::string &f : notFounds)
+    addDep(DepOpCode::NotFound, f);
+
+  addDep(DepOpCode::Output, output);
+}

lld/MachO/Options.td

def order_file_statistics : Flag<["-"], "order_file_statistics">,
     Group<grp_introspect>;
 def map : Separate<["-"], "map">,
     MetaVarName<"<path>">,
     HelpText<"Writes all symbols and their addresses to <path>">,
     Group<grp_introspect>;
 def dependency_info : Separate<["-"], "dependency_info">,
     MetaVarName<"<path>">,
     HelpText<"Dump dependency info">,
-    Flags<[HelpHidden]>,
     Group<grp_introspect>;
 def save_temps : Flag<["-"], "save-temps">,
     HelpText<"Save intermediate LTO compilation results">,
     Group<grp_introspect>;
 
 def grp_symtab : OptionGroup<"symtab">, HelpText<"SYMBOL TABLE OPTIMIZATIONS">;
 
 def S : Flag<["-"], "S">,

lld/test/MachO/Inputs/DependencyDump.py

+#
+# Dump the dependency file (produced with -dependency_info) to text
+# format for testing purposes.
+#
+
+import sys
+
+f = open(sys.argv[1], "rb")
+byte = f.read(1)
+while byte != b'':
+    if byte == b'\x00':
+        sys.stdout.write("lld-version: ")
+    elif byte == b'\x10':
+        sys.stdout.write("input-file: ")
+    elif byte == b'\x11':
+        sys.stdout.write("not-found: ")
+    elif byte == b'\x40':
+        sys.stdout.write("output-file: ")
+    byte = f.read(1)
+    while byte != b'\x00':
+        sys.stdout.write(byte.decode("ascii"))
+        byte = f.read(1)
+    sys.stdout.write("\n")
+    byte = f.read(1)
+
+f.close()

lld/test/MachO/dependency-info.s

+# REQUIRES: x86
+## FIXME: Paths on windows have both `\` and '/', as a result, they are in a different
+## order when sorted. Maybe create a separate test for that?
+# UNSUPPORTED: system-windows
+#
+# RUN: rm -rf %t
+# RUN: split-file %s %t
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos -o %t/foo.o %t/foo.s
+# RUN: %lld -dylib -o %t/libfoo.dylib %t/foo.o
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos -o %t/bar.o %t/bar.s
+# RUN: llvm-ar csr  %t/bar.a %t/bar.o
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos -o %t/main.o %t/main.s
+
+# RUN: %lld %t/main.o %t/bar.a %t/libfoo.dylib -lSystem -dependency_info %t/deps_info.out
+
+# RUN: %python %S/Inputs/DependencyDump.py %t/deps_info.out | FileCheck %s
+
+# CHECK: lld-version: LLD {{.*}}
+
+# CHECK-NEXT: input-file: {{.*}}/bar.a
+# CHECK-NEXT: input-file: {{.*}}/libfoo.dylib
+# CHECK-NEXT: input-file: {{.*}}/main.o
+# CHECK-NEXT: input-file: {{.*}}/libSystem.tbd
+# CHECK-NEXT: bar.o
+
+# CHECK-NEXT: not-found: {{.*}}/libdyld.dylib
+## There could be more not-found here but we are not checking those because it's brittle.
+
+# CHECK: output-file: a.out
+
+
+#--- foo.s
+.globl __Z3foo
+__Z3foo:
+  ret
+
+#--- bar.s
+.globl _bar
+_bar:
+  callq __Z3foo
+  ret
+
+#--- main.s
+.globl _main
+_main:
+  callq _bar
+  callq __Z3foo
+  ret