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

300–303

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

82

// 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 ↗

(On Diff #47736)

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.cpp

 #include "Error.h"
 #include "InputFiles.h"
 #include "LinkerScript.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;
   std::unique_ptr<TargetInfo> TI(createTarget());
   Target = TI.get();
   Script->finalize();
 
   if (!Config->Shared) {
     // Add entry 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

 //===- SymbolTable.h --------------------------------------------*- C++ -*-===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_SYMBOL_TABLE_H
 #define LLD_ELF_SYMBOL_TABLE_H
 
 #include "InputFiles.h"
 #include "llvm/ADT/MapVector.h"
 
+namespace llvm {
+class Module;
+}
+
 namespace lld {
 namespace elf2 {
 class Lazy;
 template <class ELFT> class OutputSectionBase;
 struct Symbol;
 class Undefined;
 
 // SymbolTable is a bucket of all known symbols, including defined,
 // undefined, or lazy symbols (the last one is symbols in archive
 // files whose archive members are not yet loaded).
 //
 // We put all symbols of all files to a SymbolTable, and the
 // SymbolTable selects the "best" symbols if there are name
 // conflicts. For example, obviously, a defined symbol is better than
 // an undefined symbol. Or, if there's a conflict between a lazy and a
 // 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:
   void wrap(StringRef Name);
   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::unique_ptr<InputFile> codegen(llvm::Module &M);
   std::string conflictMsg(SymbolBody *Old, SymbolBody *New);
 
+  SmallString<0> OwningLTOData;
+  std::unique_ptr<MemoryBuffer> LtoBuffer;
+  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

 // the symbol types.
 //
 //===----------------------------------------------------------------------===//
 
 #include "SymbolTable.h"
 #include "Config.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;
   }
 
+  // LLVM bitcode file.
+  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);
 }
 
+// Codegen the module M and returns the resulting InputFile.
+template <class ELFT>
+std::unique_ptr<InputFile> SymbolTable<ELFT>::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(OwningLTOData);
+  legacy::PassManager CodeGenPasses;
+  if (TM->addPassesToEmitFile(CodeGenPasses, OS,
+                              TargetMachine::CGFT_ObjectFile))
+    fatal("Failed to setup codegen");
+  CodeGenPasses.run(M);
+  LtoBuffer = MemoryBuffer::getMemBuffer(OwningLTOData, "", false);
+  return createObjectFile(*LtoBuffer);
+}
+
+// Merge all the bitcode files we have seen, codegen the result and return
+// the resulting ObjectFile.
+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/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
+}