Minimum LTO implementation

[• rafael]

Summary

This adds a truly minimum LTO implementation. It doesn't even handle undefined symbols.

The idea is to grow it with the test that were written for the gold plugin. One test at time so that each step is a simple patch.

[ruiu]

ELF/Driver.cpp

297–300

Do you know the cost of this initialization? (I mean if it is not cheap, say if it takes more than 10 milliseconds, then we want to do that lazily.)

ELF/InputFiles.cpp

443–446

According to the documentation of raw_svector_ostream, it is guranteed that the output is not buffered, so you don't need to enclose it in a narrower scope.

ELF/InputFiles.h

192

Ah, this is a nice way of initializing a StringSaver.

ELF/SymbolTable.cpp

83

// LLVM bitcode file

99

This function needs a comment.

116

You can remove this scope.

126

So you included Driver.h just for this line? If so, we want to move this buffer somewhere else so that we don't need to include that header.

130

This function needs a comment.

[silvas]

test/ELF/lto-start.ll

6

Does it make sense to put all LTO tests in a subdirectory? I expect we'll have quite a few.

[• rafael]

Address review comments.

[ruiu]

LGTM

[Eugene.Zelenko]

Committed in r260726.

ELF/Driver.h

 // Entry point of the ELF linker. Returns true on success.
 bool link(ArrayRef<const char *> Args, llvm::raw_ostream &Error = llvm::errs());
 
 class LinkerDriver {
 public:
   void main(ArrayRef<const char *> Args);
   void addFile(StringRef Path);
   void addLibrary(StringRef Name);
+  std::vector<std::unique_ptr<MemoryBuffer>> OwningMBs;
+  SmallString<0> OwningLTOData;
 
 private:
   void readConfigs(llvm::opt::InputArgList &Args);
   void createFiles(llvm::opt::InputArgList &Args);
   template <class ELFT> void link(llvm::opt::InputArgList &Args);
 
   llvm::BumpPtrAllocator Alloc;
   bool WholeArchive = false;
   std::vector<std::unique_ptr<InputFile>> Files;
-  std::vector<std::unique_ptr<MemoryBuffer>> OwningMBs;
 };
 
 // Parses command line options.
 llvm::opt::InputArgList parseArgs(llvm::BumpPtrAllocator *A,
                                   ArrayRef<const char *> Args);
 
 // Create enum with OPT_xxx values for each option in Options.td
 enum {

ELF/Driver.cpp

 #include "Config.h"
 #include "Error.h"
 #include "InputFiles.h"
 #include "SymbolTable.h"
 #include "Target.h"
 #include "Writer.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
+#include "llvm/Support/TargetSelect.h"
 #include "llvm/Support/raw_ostream.h"
 #include <utility>
 
 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
 
 using namespace lld;
if (WholeArchive) {
         Files.push_back(createObjectFile(MB, S));
       return;
     }
     Files.push_back(make_unique<ArchiveFile>(MBRef));
     return;
   case file_magic::elf_shared_object:
     Files.push_back(createSharedFile(MBRef));
     return;
+  case sys::fs::file_magic::bitcode:
+    Files.push_back(make_unique<BitcodeFile>(MBRef));
+    return;
   default:
     Files.push_back(createObjectFile(MBRef));
   }
 }
 
 // Add a given library by searching it from input search paths.
 void LinkerDriver::addLibrary(StringRef Name) {
   std::string Path = searchLibrary(Name);
for (auto *Arg : Args) {
     }
   }
 
   if (Files.empty() && !HasError)
     error("no input files.");
 }
 
 template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
+  // For LTO
+  InitializeAllTargets();
+  InitializeAllTargetMCs();
+  InitializeAllAsmPrinters();
+
   SymbolTable<ELFT> Symtab;
   Target.reset(createTarget());
 
   if (!Config->Shared) {
     // Add entry symbol.
     //
     // There is no entry symbol for AMDGPU binaries, so skip adding one to avoid
     // having and undefined symbol.
template <class ELFT> void LinkerDriver::link(opt::InputArgList &Args) {
   for (std::unique_ptr<InputFile> &F : Files)
     Symtab.addFile(std::move(F));
   if (HasError)
     return; // There were duplicate symbols or incompatible files
 
   for (StringRef S : Config->Undefined)
     Symtab.addUndefinedOpt(S);
 
+  Symtab.addCombinedLtoObject();
+
   for (auto *Arg : Args.filtered(OPT_wrap))
     Symtab.wrap(Arg->getValue());
 
   if (Config->OutputFile.empty())
     Config->OutputFile = "a.out";
 
   // Write the result to the file.
   Symtab.scanShlibUndefined();
   if (Config->GcSections)
     markLive<ELFT>(&Symtab);
   writeResult<ELFT>(&Symtab);
 }

ELF/InputFiles.h

 #include "Error.h"
 #include "Symbols.h"
 
 #include "lld/Core/LLVM.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Object/Archive.h"
 #include "llvm/Object/ELF.h"
+#include "llvm/Support/StringSaver.h"
 
 namespace lld {
 namespace elf2 {
 
 using llvm::object::Archive;
 
 class InputFile;
 class Lazy;
 class SymbolBody;
 
 // The root class of input files.
 class InputFile {
 public:
-  enum Kind { ObjectKind, SharedKind, ArchiveKind };
+  enum Kind { ObjectKind, SharedKind, ArchiveKind, BitcodeKind };
   Kind kind() const { return FileKind; }
 
   StringRef getName() const { return MB.getBufferIdentifier(); }
+  MemoryBufferRef MB;
 
   // Filename of .a which contained this file. If this file was
   // not in an archive file, it is the empty string. We use this
   // string for creating error messages.
   StringRef ArchiveName;
 
 protected:
   InputFile(Kind K, MemoryBufferRef M) : MB(M), FileKind(K) {}
-  MemoryBufferRef MB;
 
 private:
   const Kind FileKind;
 };
 
 template <typename ELFT> class ELFFileBase : public InputFile {
 public:
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Shdr Elf_Shdr;
public:
   llvm::MutableArrayRef<Lazy> getLazySymbols() { return LazySymbols; }
 
 private:
   std::unique_ptr<Archive> File;
   std::vector<Lazy> LazySymbols;
   llvm::DenseSet<uint64_t> Seen;
 };
 
+class BitcodeFile : public InputFile {
+public:
+  explicit BitcodeFile(MemoryBufferRef M);
+  static bool classof(const InputFile *F);
+  void parse();
+
+  std::vector<SymbolBody *> SymbolBodies;
+
+private:
+  llvm::BumpPtrAllocator Alloc;
+  llvm::StringSaver Saver{Alloc};
+};
+
 // .so file.
 template <class ELFT> class SharedFile : public ELFFileBase<ELFT> {
   typedef ELFFileBase<ELFT> Base;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Shdr Elf_Shdr;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym Elf_Sym;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Word Elf_Word;
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym_Range Elf_Sym_Range;
 

ELF/InputFiles.cpp

 //===- InputFiles.cpp -----------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InputFiles.h"
 #include "Error.h"
 #include "InputSection.h"
 #include "Symbols.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/Object/IRObjectFile.h"
+#include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace llvm::sys::fs;
 
 using namespace lld;
 using namespace lld::elf2;
for (const Elf_Sym &Sym : Syms) {
 
     if (Sym.isUndefined())
       Undefs.push_back(Name);
     else
       SymbolBodies.emplace_back(this, Name, Sym);
   }
 }
 
+BitcodeFile::BitcodeFile(MemoryBufferRef M) : InputFile(BitcodeKind, M) {}
+
+bool BitcodeFile::classof(const InputFile *F) {
+  return F->kind() == BitcodeKind;
+}
+
+void BitcodeFile::parse() {
+  LLVMContext Context;
+  ErrorOr<std::unique_ptr<IRObjectFile>> ObjOrErr =
+      IRObjectFile::create(MB, Context);
+  fatal(ObjOrErr);
+  IRObjectFile &Obj = **ObjOrErr;
+  for (const BasicSymbolRef &Sym : Obj.symbols()) {
+    SmallString<64> Name;
+    {
+      raw_svector_ostream OS(Name);
+      Sym.printName(OS);
+    }
+    StringRef NameRef = Saver.save(StringRef(Name));
+    SymbolBody *Body = new (Alloc) DefinedBitcode(NameRef);
+    SymbolBodies.push_back(Body);
+  }
+}
+
 template <typename T>
 static std::unique_ptr<InputFile> createELFFileAux(MemoryBufferRef MB) {
   std::unique_ptr<T> Ret = llvm::make_unique<T>(MB);
 
   if (!Config->FirstElf)
     Config->FirstElf = Ret.get();
 
   if (Config->EKind == ELFNoneKind) {

ELF/OutputSections.cpp

case SymbolBody::SharedKind: {
       if (cast<SharedSymbol<ELFT>>(Body)->needsCopy())
         OutSec = Out<ELFT>::Bss;
       break;
     }
     case SymbolBody::UndefinedElfKind:
     case SymbolBody::UndefinedKind:
     case SymbolBody::LazyKind:
       break;
+    case SymbolBody::DefinedBitcodeKind:
+      llvm_unreachable("Should have been replaced");
     }
 
     ESym->st_name = P.second;
 
     unsigned char Type = STT_NOTYPE;
     uintX_t Size = 0;
     if (const Elf_Sym *InputSym = getElfSym<ELFT>(*Body)) {
       Type = InputSym->getType();

ELF/SymbolTable.h

 // undefined, it'll read an archive member to read a real definition
 // to replace the lazy symbol. The logic is implemented in resolve().
 template <class ELFT> class SymbolTable {
   typedef typename llvm::object::ELFFile<ELFT>::Elf_Sym Elf_Sym;
   typedef typename llvm::object::ELFFile<ELFT>::uintX_t uintX_t;
 
 public:
   void addFile(std::unique_ptr<InputFile> File);
+  void addCombinedLtoObject();
 
   const llvm::MapVector<StringRef, Symbol *> &getSymbols() const {
     return Symtab;
   }
 
   const std::vector<std::unique_ptr<ObjectFile<ELFT>>> &getObjectFiles() const {
     return ObjectFiles;
   }
public:
   ELFFileBase<ELFT> *findFile(SymbolBody *B);
 
 private:
   Symbol *insert(SymbolBody *New);
   void addLazy(Lazy *New);
   void addMemberFile(Undefined *Undef, Lazy *L);
   void resolve(SymbolBody *Body);
   std::string conflictMsg(SymbolBody *Old, SymbolBody *New);
+  ObjectFile<ELFT> *createCombinedLtoObject();
 
   // The order the global symbols are in is not defined. We can use an arbitrary
   // order, but it has to be reproducible. That is true even when cross linking.
   // The default hashing of StringRef produces different results on 32 and 64
   // bit systems so we use a MapVector. That is arbitrary, deterministic but
   // a bit inefficient.
   // FIXME: Experiment with passing in a custom hashing or sorting the symbols
   // once symbol resolution is finished.
   llvm::MapVector<StringRef, Symbol *> Symtab;
   llvm::BumpPtrAllocator Alloc;
 
   // Comdat groups define "link once" sections. If two comdat groups have the
   // same name, only one of them is linked, and the other is ignored. This set
   // is used to uniquify them.
   llvm::DenseSet<StringRef> ComdatGroups;
 
   // The symbol table owns all file objects.
   std::vector<std::unique_ptr<ArchiveFile>> ArchiveFiles;
   std::vector<std::unique_ptr<ObjectFile<ELFT>>> ObjectFiles;
   std::vector<std::unique_ptr<SharedFile<ELFT>>> SharedFiles;
+  std::vector<std::unique_ptr<BitcodeFile>> BitcodeFiles;
 
   // Set of .so files to not link the same shared object file more than once.
   llvm::DenseSet<StringRef> SoNames;
 };
 
 } // namespace elf2
 } // namespace lld
 
 #endif

ELF/SymbolTable.cpp

 // all input files to the symbol table. The symbol table is basically
 // a hash table with the logic to resolve symbol name conflicts using
 // the symbol types.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SymbolTable.h"
 #include "Config.h"
+#include "Driver.h"
 #include "Error.h"
 #include "Symbols.h"
+#include "llvm/Bitcode/ReaderWriter.h"
+#include "llvm/IR/LegacyPassManager.h"
+#include "llvm/Linker/Linker.h"
 #include "llvm/Support/StringSaver.h"
+#include "llvm/Support/TargetRegistry.h"
+#include "llvm/Target/TargetMachine.h"
 
 using namespace llvm;
 using namespace llvm::object;
 using namespace llvm::ELF;
 
 using namespace lld;
 using namespace lld::elf2;
 
if (auto *F = dyn_cast<SharedFile<ELFT>>(FileP)) {
 
     SharedFiles.emplace_back(cast<SharedFile<ELFT>>(File.release()));
     F->parseRest();
     for (SharedSymbol<ELFT> &B : F->getSharedSymbols())
       resolve(&B);
     return;
   }
 
+  if (auto *F = dyn_cast<BitcodeFile>(FileP)) {
+    BitcodeFiles.emplace_back(cast<BitcodeFile>(File.release()));
+    F->parse();
+    for (SymbolBody *B : F->SymbolBodies)
+      resolve(B);
+    return;
+  }
+
   // .o file
   auto *F = cast<ObjectFile<ELFT>>(FileP);
   ObjectFiles.emplace_back(cast<ObjectFile<ELFT>>(File.release()));
   F->parse(ComdatGroups);
   for (SymbolBody *B : F->getSymbols())
     resolve(B);
 }
 
+static std::unique_ptr<InputFile> codegen(Module &M) {
+  StringRef TripleStr = M.getTargetTriple();
+  Triple TheTriple(TripleStr);
+
+  // FIXME: Should we have a default triple? The gold plugin uses
+  // sys::getDefaultTargetTriple(), but that is probably wrong given that this
+  // might be a cross linker.
+
+  std::string ErrMsg;
+  const Target *TheTarget = TargetRegistry::lookupTarget(TripleStr, ErrMsg);
+  if (!TheTarget)
+    fatal("Target not found: " + ErrMsg);
+
+  TargetOptions Options;
+  std::unique_ptr<TargetMachine> TM(
+      TheTarget->createTargetMachine(TripleStr, "", "", Options));
+
+  {
+    raw_svector_ostream OS(Driver->OwningLTOData);
+    legacy::PassManager CodeGenPasses;
+    if (TM->addPassesToEmitFile(CodeGenPasses, OS,
+                                TargetMachine::CGFT_ObjectFile))
+      fatal("Failed to setup codegen");
+    CodeGenPasses.run(M);
+  }
+  std::unique_ptr<MemoryBuffer> Buffer =
+      MemoryBuffer::getMemBuffer(Driver->OwningLTOData, "", false);
+  Driver->OwningMBs.push_back(std::move(Buffer));
+  return createObjectFile(*Driver->OwningMBs.back());
+}
+
+template <class ELFT>
+ObjectFile<ELFT> *SymbolTable<ELFT>::createCombinedLtoObject() {
+  LLVMContext Context;
+  Module Combined("ld-temp.o", Context);
+  Linker L(Combined);
+  for (const std::unique_ptr<BitcodeFile> &F : BitcodeFiles) {
+    std::unique_ptr<MemoryBuffer> Buffer =
+        MemoryBuffer::getMemBuffer(F->MB, false);
+    ErrorOr<std::unique_ptr<Module>> MOrErr =
+        getLazyBitcodeModule(std::move(Buffer), Context,
+                             /*ShouldLazyLoadMetadata*/ true);
+    fatal(MOrErr);
+    std::unique_ptr<Module> &M = *MOrErr;
+    L.linkInModule(std::move(M));
+  }
+  std::unique_ptr<InputFile> F = codegen(Combined);
+  ObjectFiles.emplace_back(cast<ObjectFile<ELFT>>(F.release()));
+  return &*ObjectFiles.back();
+}
+
+template <class ELFT> void SymbolTable<ELFT>::addCombinedLtoObject() {
+  if (BitcodeFiles.empty())
+    return;
+  ObjectFile<ELFT> *Obj = createCombinedLtoObject();
+  // FIXME: We probably have to ignore comdats here.
+  Obj->parse(ComdatGroups);
+  for (SymbolBody *Body : Obj->getSymbols()) {
+    Symbol *Sym = insert(Body);
+    assert(isa<DefinedBitcode>(Sym->Body));
+    Sym->Body = Body;
+  }
+}
+
 // Add an undefined symbol.
 template <class ELFT>
 SymbolBody *SymbolTable<ELFT>::addUndefined(StringRef Name) {
   auto *Sym = new (Alloc) Undefined(Name, false, STV_DEFAULT, false);
   resolve(Sym);
   return Sym;
 }
 

ELF/Symbols.h

 class SymbolBody {
 public:
   enum Kind {
     DefinedFirst,
     DefinedRegularKind = DefinedFirst,
     SharedKind,
     DefinedElfLast = SharedKind,
     DefinedCommonKind,
+    DefinedBitcodeKind,
     DefinedSyntheticKind,
     DefinedLast = DefinedSyntheticKind,
     UndefinedElfKind,
     UndefinedKind,
     LazyKind
   };
 
   Kind kind() const { return static_cast<Kind>(SymbolKind); }
DefinedElf(Kind K, StringRef N, const Elf_Sym &Sym)
         Sym(Sym) {}
 
   const Elf_Sym &Sym;
   static bool classof(const SymbolBody *S) {
     return S->kind() <= DefinedElfLast;
   }
 };
 
+class DefinedBitcode : public Defined {
+public:
+  DefinedBitcode(StringRef Name);
+  static bool classof(const SymbolBody *S);
+};
+
 class DefinedCommon : public Defined {
 public:
   DefinedCommon(StringRef N, uint64_t Size, uint64_t Alignment, bool IsWeak,
                 uint8_t Visibility);
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == SymbolBody::DefinedCommonKind;
   }

ELF/Symbols.cpp

else
       return Out<ELFT>::Bss->getVA() + SS->OffsetInBss;
   }
   case UndefinedElfKind:
   case UndefinedKind:
     return 0;
   case LazyKind:
     assert(isUsedInRegularObj() && "Lazy symbol reached writer");
     return 0;
+  case DefinedBitcodeKind:
+    llvm_unreachable("Should have been replaced");
   }
   llvm_unreachable("Invalid symbol kind");
 }
 
 template <class ELFT>
 typename ELFFile<ELFT>::uintX_t SymbolBody::getGotVA() const {
   return Out<ELFT>::Got->getVA() +
          (Out<ELFT>::Got->getMipsLocalEntriesNum() + GotIndex) *
if (Other->isCommon())
     return 1;
   return 0;
 }
 
 Defined::Defined(Kind K, StringRef Name, bool IsWeak, uint8_t Visibility,
                  bool IsTls, bool IsFunction)
     : SymbolBody(K, Name, IsWeak, Visibility, IsTls, IsFunction) {}
 
+DefinedBitcode::DefinedBitcode(StringRef Name)
+    : Defined(DefinedBitcodeKind, Name, false, STV_DEFAULT, false, false) {}
+
+bool DefinedBitcode::classof(const SymbolBody *S) {
+  return S->kind() == DefinedBitcodeKind;
+}
+
 Undefined::Undefined(SymbolBody::Kind K, StringRef N, bool IsWeak,
                      uint8_t Visibility, bool IsTls)
     : SymbolBody(K, N, IsWeak, Visibility, IsTls, /*IsFunction*/ false),
       CanKeepUndefined(false) {}
 
 Undefined::Undefined(StringRef N, bool IsWeak, uint8_t Visibility,
                      bool CanKeepUndefined)
     : Undefined(SymbolBody::UndefinedKind, N, IsWeak, Visibility,

test/ELF/lit.local.cfg

-config.suffixes = ['.test', '.s']
+config.suffixes = ['.test', '.s', '.ll']
 

test/ELF/lto-start.ll

+; REQUIRES: x86
+; RUN: llvm-as %s -o %t.o
+; RUN: ld.lld -m elf_x86_64 %t.o -o %t2
+; RUN: llvm-readobj -t %t2 | FileCheck %s
+
+; CHECK:      Format: ELF64-x86-64
+; CHECK-NEXT: Arch: x86_64
+; CHECK-NEXT: AddressSize: 64bit
+
+; CHECK:      Name: _start
+; CHECK-NEXT: Value:
+; CHECK-NEXT: Size: 1
+; CHECK-NEXT: Binding: Global
+; CHECK-NEXT: Type: Function
+; CHECK-NEXT: Other:
+; CHECK-NEXT: Section: .text
+
+target triple = "x86_64-unknown-linux-gnu"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @_start() {
+  ret void
+}