[lld-macho] Add very basic support for LTO

[int3]

Summary

Just enough to consume some bitcode files and link them. There's more
to be done around the symbol resolution API and the LTO config, but I don't yet
understand what all the various LTO settings do...

[tschuett]

Out of curiosity: are going to add distributed thinlto?
e.g. https://reviews.llvm.org/D46034

[compnerd]

lld/MachO/Driver.cpp

322–323

Why not write this as:

if (Optional<DylibFile *> dylib = makeDylibFromTAPI(mbref))
  newFile = *dylib;

332–333

LLVM style generally does not compare against nullptr or NULL.

lld/MachO/LTO.cpp

41

Could we not just do a .reserve on the std::vector on L37 and then do an emplace_back on the vector and use a range based for loop, and avoid the unnecessary construction and replacement of the resolutions?

[int3]

@tschuett we'll want to implement that eventually, but it's not a priority. Thanks for the pointer to that diff!

[int3]

address comments

[tschuett]

No worries and thank you!

[MaskRay]

lld/MachO/LTO.cpp

74

This needs a test file with more than one input file.

[int3]

lld/MachO/LTO.cpp

74

I actually did try doing that (with 2 files), but it appears that the ltoObj compiled both of them in the same thread. Any idea how to get it to deterministically use more than 1?

[MaskRay]

MachO/CMakeLists.txt needs 3 dependencies LTO/MC/Passes otherwise it will fail to build in -DBUILD_SHARED_LIBS=on mode due to -Wl,-z,defs

[MaskRay]

lld/MachO/LTO.cpp

74

Ah, partitions is a ThinLTO concept. You'll need opt -module-summary a.ll -o a.o instead of llvm-as

[smeenai]

LGTM, very nice :)

[int3]

address comments

lld/MachO/LTO.cpp

74

Thanks for the pointer! I've added the test, let me know if it looks right

[int3]

pack into one test file

[int3]

fix

lld/test/MachO/lto-save-temps.ll

11

it would be nice to check that the other temp files *don't* exist, but I'm not sure how to do that in a cross-platform way in llvm-lit

[int3]

fix use-after-free

lld/MachO/CMakeLists.txt

 set(LLVM_TARGET_DEFINITIONS Options.td)
 tablegen(LLVM Options.inc -gen-opt-parser-defs)
 add_public_tablegen_target(MachOOptionsTableGen)
 
 include_directories(${LLVM_MAIN_SRC_DIR}/../libunwind/include)
 
 add_lld_library(lldMachO2
   Arch/X86_64.cpp
   UnwindInfoSection.cpp
   Driver.cpp
   DriverUtils.cpp
   ExportTrie.cpp
   InputFiles.cpp
   InputSection.cpp
+  LTO.cpp
   MergedOutputSection.cpp
   ObjC.cpp
   OutputSection.cpp
   OutputSegment.cpp
   SymbolTable.cpp
   Symbols.cpp
   SyntheticSections.cpp
   Target.cpp
   Writer.cpp
 
   LINK_COMPONENTS
   ${LLVM_TARGETS_TO_BUILD}
   BinaryFormat
   Core
+  LTO
+  MC
   Object
   Option
+  Passes
   Support
   TextAPI
 
   LINK_LIBS
   lldCommon
   ${LLVM_PTHREAD_LIB}
 
   DEPENDS
   MachOOptionsTableGen
   ${tablegen_deps}
   )

lld/MachO/Config.h

struct Configuration {
   Symbol *entry;
   bool hasReexports = false;
   bool allLoad = false;
   bool forceLoadObjC = false;
   bool staticLink = false;
   bool isPic = false;
   bool headerPadMaxInstallNames = false;
   bool searchDylibsFirst = false;
+  bool saveTemps = false;
   uint32_t headerPad;
   llvm::StringRef installName;
   llvm::StringRef outputFile;
   llvm::MachO::Architecture arch;
   PlatformInfo platform;
   llvm::MachO::HeaderFileType outputType;
   std::vector<llvm::StringRef> systemLibraryRoots;
   std::vector<llvm::StringRef> librarySearchPaths;

lld/MachO/Driver.cpp

 //===- Driver.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
 //
 //===----------------------------------------------------------------------===//
 
 #include "Driver.h"
 #include "Config.h"
 #include "DriverUtils.h"
 #include "InputFiles.h"
+#include "LTO.h"
 #include "ObjC.h"
 #include "OutputSection.h"
 #include "OutputSegment.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "Writer.h"
 
 #include "lld/Common/Args.h"
 #include "lld/Common/Driver.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/LLVM.h"
 #include "lld/Common/Memory.h"
 #include "lld/Common/Version.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/BinaryFormat/MachO.h"
 #include "llvm/BinaryFormat/Magic.h"
+#include "llvm/LTO/LTO.h"
 #include "llvm/Object/Archive.h"
 #include "llvm/Option/ArgList.h"
 #include "llvm/Option/Option.h"
 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Host.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
+#include "llvm/Support/TargetSelect.h"
 
 #include <algorithm>
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace llvm::object;
 using namespace llvm::opt;
 using namespace llvm::sys;
static InputFile *addFile(StringRef path) {
   case file_magic::macho_object:
     newFile = make<ObjFile>(mbref);
     break;
   case file_magic::macho_dynamically_linked_shared_lib:
   case file_magic::macho_dynamically_linked_shared_lib_stub:
     newFile = make<DylibFile>(mbref);
     break;
   case file_magic::tapi_file: {
-    Optional<DylibFile *> dylibFile = makeDylibFromTAPI(mbref);
-    if (!dylibFile)
-      return nullptr;
+    if (Optional<DylibFile *> dylibFile = makeDylibFromTAPI(mbref))
       newFile = *dylibFile;
     break;
   }
+  case file_magic::bitcode:
+    newFile = make<BitcodeFile>(mbref);
+    break;
   default:
     error(path + ": unhandled file type");
   }
+  if (newFile)
     inputFiles.push_back(newFile);
   return newFile;
 }
 
 static void addFileList(StringRef path) {
   Optional<MemoryBufferRef> buffer = readFile(path);
   if (!buffer)
     return;
   MemoryBufferRef mbref = *buffer;
if (auto *dylibFile = dyn_cast<DylibFile>(file)) {
         dylibFile->reexport = true;
         return true;
       }
     }
   }
   return false;
 }
 
+// This function is called on startup. We need this for LTO since
+// LTO calls LLVM functions to compile bitcode files to native code.
+// Technically this can be delayed until we read bitcode files, but
+// we don't bother to do lazily because the initialization is fast.
+static void initLLVM() {
+  InitializeAllTargets();
+  InitializeAllTargetMCs();
+  InitializeAllAsmPrinters();
+  InitializeAllAsmParsers();
+}
+
+static void compileBitcodeFiles() {
+  auto lto = make<BitcodeCompiler>();
+  for (InputFile *file : inputFiles)
+    if (auto *bitcodeFile = dyn_cast<BitcodeFile>(file))
+      lto->add(*bitcodeFile);
+
+  for (ObjFile *file : lto->compile())
+    inputFiles.push_back(file);
+}
+
 // Replaces common symbols with defined symbols residing in __common sections.
 // This function must be called after all symbol names are resolved (i.e. after
 // all InputFiles have been loaded.) As a result, later operations won't see
 // any CommonSymbols.
 static void replaceCommonSymbols() {
   for (macho::Symbol *sym : symtab->getSymbols()) {
     auto *common = dyn_cast<CommonSymbol>(sym);
     if (common == nullptr)
config->librarySearchPaths =
       getLibrarySearchPaths(args, config->systemLibraryRoots);
   config->frameworkSearchPaths =
       getFrameworkSearchPaths(args, config->systemLibraryRoots);
   if (const opt::Arg *arg =
           args.getLastArg(OPT_search_paths_first, OPT_search_dylibs_first))
     config->searchDylibsFirst =
         (arg && arg->getOption().getID() == OPT_search_dylibs_first);
 
+  config->saveTemps = args.hasArg(OPT_save_temps);
+
   if (args.hasArg(OPT_v)) {
     message(getLLDVersion());
     message(StringRef("Library search paths:") +
             (config->librarySearchPaths.size()
                  ? "\n\t" + llvm::join(config->librarySearchPaths, "\n\t")
                  : ""));
     message(StringRef("Framework search paths:") +
             (config->frameworkSearchPaths.size()
bool macho::link(llvm::ArrayRef<const char *> argsArr, bool canExitEarly,
   // re-exported.
   for (opt::Arg *arg : args.filtered(OPT_sub_library)) {
     config->hasReexports = true;
     StringRef searchName = arg->getValue();
     if (!markSubLibrary(searchName))
       error("-sub_library " + searchName + " does not match a supplied dylib");
   }
 
+  initLLVM();
+  compileBitcodeFiles();
   replaceCommonSymbols();
 
   StringRef orderFile = args.getLastArgValue(OPT_order_file);
   if (!orderFile.empty())
     parseOrderFile(orderFile);
 
   if (config->outputType == MH_EXECUTE && isa<Undefined>(config->entry)) {
     error("undefined symbol: " + config->entry->getName());

lld/MachO/InputFiles.h

 #include "llvm/Object/Archive.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/TextAPI/MachO/InterfaceFile.h"
 #include "llvm/TextAPI/MachO/TextAPIReader.h"
 
 #include <map>
 #include <vector>
 
+namespace llvm {
+namespace lto {
+class InputFile;
+} // namespace lto
+} // namespace llvm
+
 namespace lld {
 namespace macho {
 
 class InputSection;
 class Symbol;
 struct Reloc;
 
 // If .subsections_via_symbols is set, each InputSection will be split along
 // symbol boundaries. The keys of a SubsectionMap represent the offsets of
 // each subsection from the start of the original pre-split InputSection.
 using SubsectionMap = std::map<uint32_t, InputSection *>;
 
 class InputFile {
 public:
   enum Kind {
     ObjKind,
+    OpaqueKind,
     DylibKind,
     ArchiveKind,
-    OpaqueKind,
+    BitcodeKind,
   };
 
   virtual ~InputFile() = default;
   Kind kind() const { return fileKind; }
   StringRef getName() const { return name; }
 
   MemoryBufferRef mb;
   std::vector<Symbol *> symbols;

 
 private:
   std::unique_ptr<llvm::object::Archive> file;
   // Keep track of children fetched from the archive by tracking
   // which address offsets have been fetched already.
   llvm::DenseSet<uint64_t> seen;
 };
 
+class BitcodeFile : public InputFile {
+public:
+  explicit BitcodeFile(MemoryBufferRef mb);
+  static bool classof(const InputFile *f) { return f->kind() == BitcodeKind; }
+
+  std::unique_ptr<llvm::lto::InputFile> obj;
+};
+
 extern std::vector<InputFile *> inputFiles;
 
 llvm::Optional<MemoryBufferRef> readFile(StringRef path);
 
 const llvm::MachO::load_command *
 findCommand(const llvm::MachO::mach_header_64 *, uint32_t type);
 
 } // namespace macho
 
 std::string toString(const macho::InputFile *file);
 } // namespace lld
 
 #endif

lld/MachO/InputFiles.cpp

 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "Target.h"
 
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/BinaryFormat/MachO.h"
+#include "llvm/LTO/LTO.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/Path.h"
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace llvm::support::endian;
 using namespace llvm::sys;
MemoryBufferRef mb =
                 ": could not get the buffer for the member defining symbol " +
                 sym.getName());
   auto file = make<ObjFile>(mb);
   symbols.insert(symbols.end(), file->symbols.begin(), file->symbols.end());
   subsections.insert(subsections.end(), file->subsections.begin(),
                      file->subsections.end());
 }
 
+BitcodeFile::BitcodeFile(MemoryBufferRef mbref)
+    : InputFile(BitcodeKind, mbref) {
+  obj = check(lto::InputFile::create(mbref));
+}
+
 // Returns "<internal>" or "baz.o".
 std::string lld::toString(const InputFile *file) {
   return file ? std::string(file->getName()) : "<internal>";
 }

lld/MachO/LTO.h

+//===- LTO.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_LTO_H
+#define LLD_MACHO_LTO_H
+
+#include "llvm/ADT/SmallString.h"
+#include <memory>
+#include <vector>
+
+namespace llvm {
+namespace lto {
+class LTO;
+} // namespace lto
+} // namespace llvm
+
+namespace lld {
+namespace macho {
+
+class BitcodeFile;
+class ObjFile;
+
+class BitcodeCompiler {
+public:
+  BitcodeCompiler();
+
+  void add(BitcodeFile &f);
+  std::vector<ObjFile *> compile();
+
+private:
+  std::unique_ptr<llvm::lto::LTO> ltoObj;
+  std::vector<llvm::SmallString<0>> buf;
+};
+
+} // namespace macho
+} // namespace lld
+
+#endif

lld/MachO/LTO.cpp

+//===- LTO.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
+//
+//===----------------------------------------------------------------------===//
+
+#include "LTO.h"
+#include "Config.h"
+#include "InputFiles.h"
+
+#include "lld/Common/ErrorHandler.h"
+#include "lld/Common/Strings.h"
+#include "lld/Common/TargetOptionsCommandFlags.h"
+#include "llvm/LTO/LTO.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace lld;
+using namespace lld::macho;
+using namespace llvm;
+
+static lto::Config createConfig() {
+  lto::Config c;
+  c.Options = initTargetOptionsFromCodeGenFlags();
+  return c;
+}
+
+BitcodeCompiler::BitcodeCompiler() {
+  auto backend =
+      lto::createInProcessThinBackend(llvm::heavyweight_hardware_concurrency());
+  ltoObj = std::make_unique<lto::LTO>(createConfig(), backend);
+}
+
+void BitcodeCompiler::add(BitcodeFile &f) {
+  ArrayRef<lto::InputFile::Symbol> objSyms = f.obj->symbols();
+  std::vector<lto::SymbolResolution> resols;
+  resols.reserve(objSyms.size());
+
+  // Provide a resolution to the LTO API for each symbol.
+  for (const lto::InputFile::Symbol &objSym : objSyms) {
+    resols.emplace_back();
+    lto::SymbolResolution &r = resols.back();
+
+    // Ideally we shouldn't check for SF_Undefined but currently IRObjectFile
+    // reports two symbols for module ASM defined. Without this check, lld
+    // flags an undefined in IR with a definition in ASM as prevailing.
+    // Once IRObjectFile is fixed to report only one symbol this hack can
+    // be removed.
+    r.Prevailing = !objSym.isUndefined();
+
+    // TODO: set the other resolution configs properly
+    r.VisibleToRegularObj = true;
+  }
+  checkError(ltoObj->add(std::move(f.obj), resols));
+}
+
+// Merge all the bitcode files we have seen, codegen the result
+// and return the resulting ObjectFile(s).
+std::vector<ObjFile *> BitcodeCompiler::compile() {
+  unsigned maxTasks = ltoObj->getMaxTasks();
+  buf.resize(maxTasks);
+
+  checkError(ltoObj->run([&](size_t task) {
+    return std::make_unique<lto::NativeObjectStream>(
+        std::make_unique<raw_svector_ostream>(buf[task]));
+  }));
+
+  if (config->saveTemps) {
+    if (!buf[0].empty())
+      saveBuffer(buf[0], config->outputFile + ".lto.o");
+    for (unsigned i = 1; i != maxTasks; ++i)
+      saveBuffer(buf[i], config->outputFile + Twine(i) + ".lto.o");
+  }
+
+  std::vector<ObjFile *> ret;
+  for (unsigned i = 0; i != maxTasks; ++i)
+    if (!buf[i].empty())
+      ret.push_back(make<ObjFile>(MemoryBufferRef(buf[i], "lto.tmp")));
+
+  return ret;
+}

lld/MachO/Options.td

def map : Separate<["-"], "map">,
      HelpText<"Writes all symbols and their addresses to <path>">,
      Flags<[HelpHidden]>,
      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 temporary files instead of deleting them">,
+     Group<grp_introspect>;
 
 def grp_symtab : OptionGroup<"symtab">, HelpText<"SYMBOL TABLE OPTIMIZATIONS">;
 
 def S : Flag<["-"], "S">,
      HelpText<"Strip debug information (STABS or DWARF) from the output">,
      Flags<[HelpHidden]>,
      Group<grp_symtab>;
 def x : Flag<["-"], "x">,

 def pause : Flag<["-"], "pause">,
      HelpText<"This option is undocumented in ld64">,
      Flags<[HelpHidden]>,
      Group<grp_undocumented>;
 def random_uuid : Flag<["-"], "random_uuid">,
      HelpText<"This option is undocumented in ld64">,
      Flags<[HelpHidden]>,
      Group<grp_undocumented>;
-def save_temps : Flag<["-"], "save-temps">,
-     HelpText<"This option is undocumented in ld64">,
-     Flags<[HelpHidden]>,
-     Group<grp_undocumented>;
 def simulator_support : Flag<["-"], "simulator_support">,
      HelpText<"This option is undocumented in ld64">,
      Flags<[HelpHidden]>,
      Group<grp_undocumented>;
 def snapshot_dir : Flag<["-"], "snapshot_dir">,
      HelpText<"This option is undocumented in ld64">,
      Flags<[HelpHidden]>,
      Group<grp_undocumented>;

lld/test/MachO/lto-save-temps.ll

+; REQUIRES: x86
+
+; Test that we compile regular LTO inputs in a single task but handle ThinLTO
+; modules in separate tasks.
+
+; RUN: rm -rf %t; split-file %s %t
+; RUN: llvm-as %t/foo.ll -o %t/foo.o
+; RUN: llvm-as %t/test.ll -o %t/test.o
+; RUN: %lld -save-temps %t/foo.o %t/test.o -o %t/test
+; RUN: llvm-objdump -d --no-show-raw-insn %t/test.lto.o | FileCheck %s --check-prefix=ALL
+; RUN: llvm-objdump -d --no-show-raw-insn %t/test | FileCheck %s --check-prefix=ALL
+
+; RUN: rm -rf %t; split-file %s %t
+; RUN: opt -module-summary %t/foo.ll -o %t/foo.o
+; RUN: opt -module-summary %t/test.ll -o %t/test.o
+; RUN: %lld -save-temps %t/foo.o %t/test.o -o %t/test
+; RUN: llvm-objdump -d --no-show-raw-insn %t/test1.lto.o | FileCheck %s --check-prefix=FOO
+; RUN: llvm-objdump -d --no-show-raw-insn %t/test2.lto.o | FileCheck %s --check-prefix=MAIN
+; RUN: llvm-objdump -d --no-show-raw-insn %t/test | FileCheck %s --check-prefix=ALL
+
+; FOO:      <_foo>:
+; FOO-NEXT: retq
+
+; MAIN:      <_main>:
+; MAIN-NEXT: retq
+
+; ALL:      <_foo>:
+; ALL-NEXT: retq
+; ALL:      <_main>:
+; ALL-NEXT: retq
+
+;--- foo.ll
+
+target triple = "x86_64-apple-macosx10.15.0"
+target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @foo() {
+  ret void
+}
+
+;--- test.ll
+
+target triple = "x86_64-apple-macosx10.15.0"
+target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @main() {
+  ret void
+}