[WebAssembly] Initial support for LTO

[sbc100]

• cleanup

[ruiu]

wasm/Driver.cpp

306

ELF lld supports --thinlto-jobs=, --lto-partitions=, etc as well as --plugin-opt=jobs=, --plugin-opt=partitions=, etc for compatibility with the LTO plugin for GNU gold. Since you are creating a new linker from scratch now, I don't think that makes sense to keep --plugin-opt options. I'd use only non-"--plugin-opt=" options.

wasm/InputFiles.cpp

378

No else after return

wasm/InputFiles.h

73

nit: add a blank line before a comment.

[sbc100]

• feedback

[ruiu]

wasm/InputFiles.cpp

374

What does Ref means? I'd name this just Name.

392

fatal is to report corrupted files. Since this case is to report a miseuse of the command, you should use error.

wasm/LTO.cpp

45

Move this to Common/Strings.cpp.

53

I'd think you should move this function to Common/ErrorHandler.cpp.

58

Move this to Common/ErrorHandler.cpp.

[pcc]

wasm/Driver.cpp

280

Should we implement -u in the same way as in the ELF linker? With this implementation it doesn't look like it will work correctly for undefined data and globals.

wasm/InputFiles.cpp

383

I think you also want to copy the symbol's binding here and below.

wasm/SymbolTable.cpp

200

This function seems to be unused.

[sbc100]

• feedback

[sbc100]

wasm/InputFiles.cpp

374

Looks like I cargo-culted that from ELF/InputFiles.cpp. Fixed there too.

wasm/LTO.cpp

58

Is it OK for ErrorHandler.h to include llvm/IR/DiagnosticInfo.h ? I was thinking of doing some followup changes to factor out some of the common LTO code.

[ruiu]

wasm/LTO.cpp

58

Can't you just declare the class without including that header?

[sbc100]

• feedback

[ruiu]

wasm/Driver.cpp

279

It feels like handle prefix implies that it's a side-effect-only function, though this function returns a new object. Perhaps addUndefined is a better name.

291

We do this not in Driver::main() but in elf::link() in the ELF linker.

wasm/InputFiles.cpp

392

Please fix.

wasm/LTO.h

52

Buff -> Buf for consistency with ELF.

wasm/SymbolTable.cpp

201

Why is this function empty?

[sbc100]

• feedback and rebase onto separate change

wasm/InputFiles.cpp

392

Both COFF and ELF use fatal() when when passed bitcode of the wrong arch, but I guess that just means that they need fixing.

[sbc100]

• revert

[sbc100]

• revert ProgName

[sbc100]

• addUndefined

[pcc]

test/wasm/lto/lto-start.ll

3

More tests please. I would expect to see a ThinLTO test as well as tests for the new flags.

wasm/Config.h

32–50

Out of these new options it looks like you are only initializing --lto-partitions and --save-temps during option parsing. You probably want to either initialize the remaining ones or remove them.

wasm/Driver.cpp

280

Please address.

wasm/InputFiles.cpp

383

Please address.

[sbc100]

• handle bitcode symbol flags

[sbc100]

• use flags

[sbc100]

test/wasm/lto/lto-start.ll

3

I agree. I was thinking of landing this initial version and iterating (see the change description), but perhaps its best not to land in a half baked state. I'm happy to add more tests and make this more complete.

wasm/Driver.cpp

280

You are correct. Right now with wasm-ld -u flag only works for function symbols. This is a current limitation of the wasm linker, not something that this change introduces. I agree we should address that, but that would be a separate change I think.

[pcc]

wasm/Driver.cpp

280

Yes it should be a separate change, just something I noticed while reviewing this code.

[sbc100]

• remove unused options
• add more tests

[sbc100]

• remove debugging

[ruiu]

Generally looking good, but I'd like to wait for pcc as he knows more than me about LTO.

wasm/InputFiles.cpp

406

I think you can use toString(this) instead of toString(MB...).

wasm/LTO.h

52

nit: Buff -> Buf for consistency.

[pcc]

I think this needs a couple more tests:

• Test that the binding is copied correctly to the LLD symbol. You can probably do this with a test that shows that strong/weak resolution produces the correct symbol.
• Test that VisibleToRegularObj is set correctly when building an executable. See test/ELF/lto/internalize-basic.ll for an example.

ELF/Options.td

200 ↗

(On Diff #148982)

You probably want to undo this part or do it separately.

test/wasm/lto/thinlto.ll

18 ↗

(On Diff #148982)

You should be able to do the same test here as in the other cases. I've updated this test in the ELF linker to do the same in r333480.

[sbc100]

• feedback
• more tests

[sbc100]

• fix failing test

[pcc]

LGTM

include/lld/Common/Strings.h

 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/GlobPattern.h"
 #include <string>
 #include <vector>
 
 namespace lld {
+
 // Returns a demangled C++ symbol name. If Name is not a mangled
 // name, it returns Optional::None.
 llvm::Optional<std::string> demangleItanium(llvm::StringRef Name);
 llvm::Optional<std::string> demangleMSVC(llvm::StringRef S);
 
 std::vector<uint8_t> parseHex(llvm::StringRef S);
 bool isValidCIdentifier(llvm::StringRef S);
 

test/wasm/lto/lto-start.ll

+; RUN: llvm-as %s -o %t.o
+; RUN: wasm-ld %t.o -o %t.wasm
+; RUN: obj2yaml %t.wasm | FileCheck %s
+
+; CHECK:        - Type:            CUSTOM
+; CHECK-NEXT:     Name:            name
+; CHECK-NEXT:     FunctionNames:   
+; CHECK-NEXT:       - Index:           0
+; CHECK-NEXT:         Name:            __wasm_call_ctors
+; CHECK-NEXT:       - Index:           1
+; CHECK-NEXT:         Name:            _start
+
+
+target triple = "wasm32-unknown-unknown-wasm"
+target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+
+define void @_start() {
+  ret void
+}

wasm/CMakeLists.txt

 set(LLVM_TARGET_DEFINITIONS Options.td)
 tablegen(LLVM Options.inc -gen-opt-parser-defs)
 add_public_tablegen_target(WasmOptionsTableGen)
 
 add_lld_library(lldWasm
   Driver.cpp
   InputChunks.cpp
   InputFiles.cpp
+  LTO.cpp
   MarkLive.cpp
   OutputSections.cpp
   SymbolTable.cpp
   Symbols.cpp
   Writer.cpp
   WriterUtils.cpp
 
   LINK_COMPONENTS
   ${LLVM_TARGETS_TO_BUILD}
   BinaryFormat
   Core
   Demangle
+  LTO
+  MC
   Object
   Option
   Support
 
   LINK_LIBS
   lldCommon
   )

wasm/Config.h

 //===- Config.h -------------------------------------------------*- C++ -*-===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_WASM_CONFIG_H
 #define LLD_WASM_CONFIG_H
 
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/BinaryFormat/Wasm.h"
+#include "llvm/Support/CachePruning.h"
 
 namespace lld {
 namespace wasm {
 
 struct Configuration {
   bool AllowUndefined;
   bool CompressRelocTargets;
   bool Demangle;
   bool ExportTable;
   bool GcSections;
   bool ImportMemory;
   bool ImportTable;
   bool MergeDataSegments;
   bool PrintGcSections;
   bool Relocatable;
+  bool SaveTemps;
   bool StripAll;
   bool StripDebug;
   bool StackFirst;
   uint32_t GlobalBase;
   uint32_t InitialMemory;
   uint32_t MaxMemory;
-  uint32_t Optimize;
   uint32_t ZStackSize;
+  unsigned LTOPartitions;
+  unsigned LTOO;
+  unsigned Optimize;
+  unsigned ThinLTOJobs;
   llvm::StringRef Entry;
+  llvm::StringRef ProgName;
   llvm::StringRef OutputFile;
+  llvm::StringRef ThinLTOCacheDir;
 
   llvm::StringSet<> AllowUndefinedSymbols;
   std::vector<llvm::StringRef> SearchPaths;
+  llvm::CachePruningPolicy ThinLTOCachePolicy;
 };
 
 // The only instance of Configuration struct.
 extern Configuration *Config;
 
 } // namespace wasm
 } // namespace lld
 
 #endif

wasm/Driver.cpp

 #include "lld/Common/Threads.h"
 #include "lld/Common/Version.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Object/Wasm.h"
 #include "llvm/Option/ArgList.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Process.h"
+#include "llvm/Support/TargetSelect.h"
 
 #define DEBUG_TYPE "lld"
 
 using namespace llvm;
 using namespace llvm::sys;
 using namespace llvm::wasm;
 
 using namespace lld;
 using namespace lld::wasm;
 
 Configuration *lld::wasm::Config;
 
 namespace {
 
 // Create enum with OPT_xxx values for each option in Options.td
 enum {
   OPT_INVALID = 0,
 #define OPTION(_1, _2, ID, _4, _5, _6, _7, _8, _9, _10, _11, _12) OPT_##ID,
 #include "Options.inc"
 #undef OPTION
 };
 
+// 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();
+}
+
 class LinkerDriver {
 public:
   void link(ArrayRef<const char *> ArgsArr);
 
 private:
   void createFiles(opt::InputArgList &Args);
   void addFile(StringRef Path);
   void addLibrary(StringRef Name);
   std::vector<InputFile *> Files;
 };
 } // anonymous namespace
 
 bool lld::wasm::link(ArrayRef<const char *> Args, bool CanExitEarly,
                      raw_ostream &Error) {
   errorHandler().LogName = Args[0];
   errorHandler().ErrorOS = &Error;
   errorHandler().ColorDiagnostics = Error.has_colors();
   errorHandler().ErrorLimitExceededMsg =
       "too many errors emitted, stopping now (use "
       "-error-limit=0 to see all errors)";
 
   Config = make<Configuration>();
   Symtab = make<SymbolTable>();
 
+  initLLVM();
   LinkerDriver().link(Args);
 
   // Exit immediately if we don't need to return to the caller.
   // This saves time because the overhead of calling destructors
   // for all globally-allocated objects is not negligible.
   if (CanExitEarly)
     exitLld(errorCount() ? 1 : 0);
 

 }
 
 void LinkerDriver::addFile(StringRef Path) {
   Optional<MemoryBufferRef> Buffer = readFile(Path);
   if (!Buffer.hasValue())
     return;
   MemoryBufferRef MBRef = *Buffer;
 
-  if (identify_magic(MBRef.getBuffer()) == file_magic::archive) {
+  switch (identify_magic(MBRef.getBuffer())) {
+  case file_magic::archive: {
     SmallString<128> ImportFile = Path;
     path::replace_extension(ImportFile, ".imports");
     if (fs::exists(ImportFile))
       readImportFile(ImportFile.str());
 
     Files.push_back(make<ArchiveFile>(MBRef));
     return;
   }
-
+  case file_magic::bitcode:
+    Files.push_back(make<BitcodeFile>(MBRef));
+    break;
+  default:
     Files.push_back(make<ObjFile>(MBRef));
   }
+}
 
 // Add a given library by searching it from input search paths.
 void LinkerDriver::addLibrary(StringRef Name) {
   for (StringRef Dir : Config->SearchPaths) {
     if (Optional<std::string> S = findFile(Dir, "lib" + Name + ".a")) {
       addFile(*S);
       return;
     }
for (Symbol *Sym : Symtab->getSymbols()) {
     Func->setTableIndex(0);
     Symtab->SyntheticFunctions.emplace_back(Func);
     // Hide our dummy to prevent export.
     uint32_t Flags = WASM_SYMBOL_VISIBILITY_HIDDEN;
     replaceSymbol<DefinedFunction>(Sym, Sym->getName(), Flags, nullptr, Func);
   }
 }
 
+// Force Sym to be entered in the output. Used for -u or equivalent.
+static Symbol *handleUndefined(StringRef Name) {
+  Symbol *S = Symtab->addUndefinedFunction(Name, 0, nullptr, nullptr);
+
+  // Since symbol S may not be used inside the program, LTO may
+  // eliminate it. Mark the symbol as "used" to prevent it.
+  S->IsUsedInRegularObj = true;
+
+  return S;
+}
+
 void LinkerDriver::link(ArrayRef<const char *> ArgsArr) {
   WasmOptTable Parser;
+  Config->ProgName = ArgsArr[0];
   opt::InputArgList Args = Parser.parse(ArgsArr.slice(1));
 
   // Handle --help
   if (Args.hasArg(OPT_help)) {
     Parser.PrintHelp(outs(), ArgsArr[0], "LLVM Linker", false);
     return;
   }
 
   // Handle --version
   if (Args.hasArg(OPT_version) || Args.hasArg(OPT_v)) {
     outs() << getLLDVersion() << "\n";
     return;
   }
 
   // Parse and evaluate -mllvm options.
   std::vector<const char *> V;
   V.push_back("wasm-ld (LLVM option parsing)");
   for (auto *Arg : Args.filtered(OPT_mllvm))
     V.push_back(Arg->getValue());
   cl::ParseCommandLineOptions(V.size(), V.data());
 
   errorHandler().ErrorLimit = args::getInteger(Args, OPT_error_limit, 20);
 
   Config->AllowUndefined = Args.hasArg(OPT_allow_undefined);
   Config->Demangle = Args.hasFlag(OPT_demangle, OPT_no_demangle, true);
   Config->Entry = getEntry(Args, Args.hasArg(OPT_relocatable) ? "" : "_start");
   Config->ExportTable = Args.hasArg(OPT_export_table);
   errorHandler().FatalWarnings =
       Args.hasFlag(OPT_fatal_warnings, OPT_no_fatal_warnings, false);
   Config->ImportMemory = Args.hasArg(OPT_import_memory);
   Config->ImportTable = Args.hasArg(OPT_import_table);
+  Config->LTOPartitions = args::getInteger(Args, OPT_lto_partitions, 1);
   Config->Optimize = args::getInteger(Args, OPT_O, 0);
   Config->OutputFile = Args.getLastArgValue(OPT_o);
   Config->Relocatable = Args.hasArg(OPT_relocatable);
   Config->GcSections =
       Args.hasFlag(OPT_gc_sections, OPT_no_gc_sections, !Config->Relocatable);
   Config->MergeDataSegments =
       Args.hasFlag(OPT_merge_data_segments, OPT_no_merge_data_segments,
                    !Config->Relocatable);
   Config->PrintGcSections =
       Args.hasFlag(OPT_print_gc_sections, OPT_no_print_gc_sections, false);
+  Config->SaveTemps = Args.hasArg(OPT_save_temps);
   Config->SearchPaths = args::getStrings(Args, OPT_L);
   Config->StripAll = Args.hasArg(OPT_strip_all);
   Config->StripDebug = Args.hasArg(OPT_strip_debug);
   Config->StackFirst = Args.hasArg(OPT_stack_first);
   errorHandler().Verbose = Args.hasArg(OPT_verbose);
   ThreadsEnabled = Args.hasFlag(OPT_threads, OPT_no_threads, true);
 
   Config->InitialMemory = args::getInteger(Args, OPT_initial_memory, 0);
if (!Config->Relocatable) {
     WasmSym::HeapBase = Symtab->addSyntheticDataSymbol("__heap_base", 0);
     WasmSym::DsoHandle = Symtab->addSyntheticDataSymbol(
         "__dso_handle", WASM_SYMBOL_VISIBILITY_HIDDEN);
     WasmSym::DataEnd = Symtab->addSyntheticDataSymbol("__data_end", 0);
 
     // For now, since we don't actually use the start function as the
     // wasm start symbol, we don't need to care about it signature.
     if (!Config->Entry.empty())
-      EntrySym =
-          Symtab->addUndefinedFunction(Config->Entry, 0, nullptr, nullptr);
+      EntrySym = handleUndefined(Config->Entry);
 
     // Handle the `--undefined <sym>` options.
     for (auto *Arg : Args.filtered(OPT_undefined))
-      Symtab->addUndefinedFunction(Arg->getValue(), 0, nullptr, nullptr);
+      handleUndefined(Arg->getValue());
   }
 
   createFiles(Args);
   if (errorCount())
     return;
 
   // Add all files to the symbol table. This will add almost all
   // symbols that we need to the symbol table.
   for (InputFile *F : Files)
     Symtab->addFile(F);
 
   // Add synthetic dummies for weak undefined functions.
   if (!Config->Relocatable)
     handleWeakUndefines();
 
+  // Do link-time optimization if given files are LLVM bitcode files.
+  // This compiles bitcode files into real object files.
+  Symtab->addCombinedLTOObject();
+  if (errorCount())
+    return;
+
   // Make sure we have resolved all symbols.
   if (!Config->Relocatable && !Config->AllowUndefined) {
     Symtab->reportRemainingUndefines();
   } else {
     // Even when using --allow-undefined we still want to report the absence of
     // our initial set of undefined symbols (i.e. the entry point and symbols
     // specified via --undefined).
     // Part of the reason for this is that these function don't have signatures

wasm/InputFiles.h

 //===- InputFiles.h ---------------------------------------------*- C++ -*-===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_WASM_INPUT_FILES_H
 #define LLD_WASM_INPUT_FILES_H
 
 #include "Symbols.h"
 #include "lld/Common/LLVM.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/LTO/LTO.h"
 #include "llvm/Object/Archive.h"
 #include "llvm/Object/Wasm.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include <vector>
 
 using llvm::object::Archive;
 using llvm::object::WasmObjectFile;
 using llvm::object::WasmSection;
 using llvm::object::WasmSymbol;
 using llvm::wasm::WasmGlobal;
 using llvm::wasm::WasmImport;
 using llvm::wasm::WasmRelocation;
 using llvm::wasm::WasmSignature;
 
+namespace llvm {
+namespace lto {
+class InputFile;
+}
+} // namespace llvm
+
 namespace lld {
 namespace wasm {
 
 class InputChunk;
 class InputFunction;
 class InputSegment;
 class InputGlobal;
 class InputSection;
 
 class InputFile {
 public:
   enum Kind {
     ObjectKind,
     ArchiveKind,
+    BitcodeKind,
   };
 
   virtual ~InputFile() {}
 
   // Returns the filename.
   StringRef getName() const { return MB.getBufferIdentifier(); }
 
   // Reads a file (the constructor doesn't do that).
   virtual void parse() = 0;
 
   Kind kind() const { return FileKind; }
 
   // An archive file name if this file is created from an archive.
   StringRef ParentName;
 
+  ArrayRef<Symbol *> getSymbols() const { return Symbols; }
+
 protected:
   InputFile(Kind K, MemoryBufferRef M) : MB(M), FileKind(K) {}
   MemoryBufferRef MB;
 
+  // List of all symbols referenced or defined by this file.
+  std::vector<Symbol *> Symbols;
+
 private:
   const Kind FileKind;
 };
 
 // .a file (ar archive)
 class ArchiveFile : public InputFile {
 public:
   explicit ArchiveFile(MemoryBufferRef M) : InputFile(ArchiveKind, M) {}
public:
   std::vector<uint32_t> TableEntries;
   std::vector<bool> UsedComdats;
   std::vector<InputSegment *> Segments;
   std::vector<InputFunction *> Functions;
   std::vector<InputGlobal *> Globals;
   std::vector<InputSection *> CustomSections;
   llvm::DenseMap<uint32_t, InputSection *> CustomSectionsByIndex;
 
-  ArrayRef<Symbol *> getSymbols() const { return Symbols; }
   Symbol *getSymbol(uint32_t Index) const { return Symbols[Index]; }
   FunctionSymbol *getFunctionSymbol(uint32_t Index) const;
   DataSymbol *getDataSymbol(uint32_t Index) const;
   GlobalSymbol *getGlobalSymbol(uint32_t Index) const;
   SectionSymbol *getSectionSymbol(uint32_t Index) const;
 
 private:
   Symbol *createDefined(const WasmSymbol &Sym);
   Symbol *createUndefined(const WasmSymbol &Sym);
 
   bool isExcludedByComdat(InputChunk *Chunk) const;
 
-  // List of all symbols referenced or defined by this file.
-  std::vector<Symbol *> Symbols;
-
   std::unique_ptr<WasmObjectFile> WasmObj;
 };
 
+class BitcodeFile : public InputFile {
+public:
+  explicit BitcodeFile(MemoryBufferRef M) : InputFile(BitcodeKind, M) {}
+  static bool classof(const InputFile *F) { return F->kind() == BitcodeKind; }
+
+  void parse() override;
+  std::unique_ptr<llvm::lto::InputFile> Obj;
+};
+
 // Opens a given file.
 llvm::Optional<MemoryBufferRef> readFile(StringRef Path);
 
 } // namespace wasm
 
 std::string toString(const wasm::InputFile *File);
 
 } // namespace lld
 
 #endif

wasm/InputFiles.cpp

if (identify_magic(MB.getBuffer()) != file_magic::wasm_object) {
     return;
   }
 
   InputFile *Obj = make<ObjFile>(MB);
   Obj->ParentName = ParentName;
   Symtab->addFile(Obj);
 }
 
+static Symbol *createBitcodeSymbol(const lto::InputFile::Symbol &ObjSym,
+                                   BitcodeFile &F) {
+  StringRef Name = Saver.save(ObjSym.getName());
+
+  if (ObjSym.isUndefined()) {
+    if (ObjSym.isExecutable())
+      return Symtab->addUndefinedFunction(Name, 0, &F, nullptr);
+    return Symtab->addUndefinedData(Name, 0, &F);
+  }
+
+  if (ObjSym.isExecutable())
+    return Symtab->addDefinedFunction(Name, 0, &F, nullptr);
+  return Symtab->addDefinedData(Name, 0, &F, nullptr, 0, 0);
+}
+
+void BitcodeFile::parse() {
+  Obj = check(lto::InputFile::create(MemoryBufferRef(
+      MB.getBuffer(), Saver.save(ParentName + MB.getBufferIdentifier()))));
+  Triple T(Obj->getTargetTriple());
+  if (T.getArch() != Triple::wasm32) {
+    error(toString(MB.getBufferIdentifier()) + ": machine type must be wasm32");
+    return;
+  }
+
+  for (const lto::InputFile::Symbol &ObjSym : Obj->symbols())
+    Symbols.push_back(createBitcodeSymbol(ObjSym, *this));
+}
+
 // Returns a string in the format of "foo.o" or "foo.a(bar.o)".
 std::string lld::toString(const wasm::InputFile *File) {
   if (!File)
     return "<internal>";
 
   if (File->ParentName.empty())
     return File->getName();
 
   return (File->ParentName + "(" + File->getName() + ")").str();
 }

wasm/LTO.h

+//===- LTO.h ----------------------------------------------------*- C++ -*-===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides a way to combine bitcode files into one wasm
+// file by compiling them using LLVM.
+//
+// If LTO is in use, your input files are not in regular wasm files
+// but instead LLVM bitcode files. In that case, the linker has to
+// convert bitcode files into the native format so that we can create
+// a wasm file that contains native code. This file provides that
+// functionality.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLD_WASM_LTO_H
+#define LLD_WASM_LTO_H
+
+#include "lld/Common/LLVM.h"
+#include "llvm/ADT/SmallString.h"
+#include <memory>
+#include <vector>
+
+namespace llvm {
+namespace lto {
+class LTO;
+}
+} // namespace llvm
+
+namespace lld {
+namespace wasm {
+
+class BitcodeFile;
+class InputFile;
+
+class BitcodeCompiler {
+public:
+  BitcodeCompiler();
+  ~BitcodeCompiler();
+
+  void add(BitcodeFile &F);
+  std::vector<StringRef> compile();
+
+private:
+  std::unique_ptr<llvm::lto::LTO> LTOObj;
+  std::vector<SmallString<0>> Buff;
+  std::vector<std::unique_ptr<MemoryBuffer>> Files;
+};
+} // namespace wasm
+} // namespace lld
+
+#endif

wasm/LTO.cpp

+//===- LTO.cpp ------------------------------------------------------------===//
+//
+//                             The LLVM Linker
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "LTO.h"
+#include "Config.h"
+#include "InputFiles.h"
+#include "Symbols.h"
+#include "lld/Common/ErrorHandler.h"
+#include "lld/Common/Strings.h"
+#include "lld/Common/TargetOptionsCommandFlags.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/IR/DiagnosticPrinter.h"
+#include "llvm/LTO/Caching.h"
+#include "llvm/LTO/Config.h"
+#include "llvm/LTO/LTO.h"
+#include "llvm/Object/SymbolicFile.h"
+#include "llvm/Support/CodeGen.h"
+#include "llvm/Support/Error.h"
+#include "llvm/Support/FileSystem.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/raw_ostream.h"
+#include <algorithm>
+#include <cstddef>
+#include <memory>
+#include <string>
+#include <system_error>
+#include <vector>
+
+using namespace llvm;
+using namespace llvm::object;
+
+using namespace lld;
+using namespace lld::wasm;
+
+static std::unique_ptr<lto::LTO> createLTO() {
+  lto::Config C;
+  C.Options = InitTargetOptionsFromCodeGenFlags();
+
+  // Always emit a section per function/datum with LTO.
+  C.Options.FunctionSections = true;
+  C.Options.DataSections = true;
+
+  C.DisableVerify = true;
+  C.DiagHandler = diagnosticHandler;
+  C.OptLevel = Config->LTOO;
+
+  if (Config->SaveTemps)
+    checkError(C.addSaveTemps(Config->OutputFile.str() + ".",
+                              /*UseInputModulePath*/ true));
+
+  lto::ThinBackend Backend;
+  if (Config->ThinLTOJobs != -1U)
+    Backend = lto::createInProcessThinBackend(Config->ThinLTOJobs);
+  return llvm::make_unique<lto::LTO>(std::move(C), Backend,
+                                     Config->LTOPartitions);
+}
+
+BitcodeCompiler::BitcodeCompiler() : LTOObj(createLTO()) {}
+
+BitcodeCompiler::~BitcodeCompiler() = default;
+
+static void undefine(Symbol *S) {
+  if (isa<DefinedFunction>(S))
+    replaceSymbol<UndefinedFunction>(S, S->getName(), 0);
+  else if (isa<DefinedData>(S))
+    replaceSymbol<UndefinedData>(S, S->getName(), 0);
+  else
+    llvm_unreachable("unexpected symbol kind");
+}
+
+void BitcodeCompiler::add(BitcodeFile &F) {
+  lto::InputFile &Obj = *F.Obj;
+  unsigned SymNum = 0;
+  ArrayRef<Symbol *> Syms = F.getSymbols();
+  std::vector<lto::SymbolResolution> Resols(Syms.size());
+
+  // Provide a resolution to the LTO API for each symbol.
+  for (const lto::InputFile::Symbol &ObjSym : Obj.symbols()) {
+    Symbol *Sym = Syms[SymNum];
+    lto::SymbolResolution &R = Resols[SymNum];
+    ++SymNum;
+
+    // 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() && Sym->getFile() == &F;
+    R.VisibleToRegularObj = Config->Relocatable || Sym->IsUsedInRegularObj;
+    if (R.Prevailing)
+      undefine(Sym);
+  }
+  checkError(LTOObj->add(std::move(F.Obj), Resols));
+}
+
+// Merge all the bitcode files we have seen, codegen the result
+// and return the resulting objects.
+std::vector<StringRef> BitcodeCompiler::compile() {
+  unsigned MaxTasks = LTOObj->getMaxTasks();
+  Buff.resize(MaxTasks);
+  Files.resize(MaxTasks);
+
+  // The --thinlto-cache-dir option specifies the path to a directory in which
+  // to cache native object files for ThinLTO incremental builds. If a path was
+  // specified, configure LTO to use it as the cache directory.
+  lto::NativeObjectCache Cache;
+  if (!Config->ThinLTOCacheDir.empty())
+    Cache = check(
+        lto::localCache(Config->ThinLTOCacheDir,
+                        [&](size_t Task, std::unique_ptr<MemoryBuffer> MB) {
+                          Files[Task] = std::move(MB);
+                        }));
+
+  checkError(LTOObj->run(
+      [&](size_t Task) {
+        return llvm::make_unique<lto::NativeObjectStream>(
+            llvm::make_unique<raw_svector_ostream>(Buff[Task]));
+      },
+      Cache));
+
+  if (!Config->ThinLTOCacheDir.empty())
+    pruneCache(Config->ThinLTOCacheDir, Config->ThinLTOCachePolicy);
+
+  std::vector<StringRef> Ret;
+  for (unsigned I = 0; I != MaxTasks; ++I) {
+    if (Buff[I].empty())
+      continue;
+    if (Config->SaveTemps) {
+      if (I == 0)
+        saveBuffer(Buff[I], Config->OutputFile + ".lto.o");
+      else
+        saveBuffer(Buff[I], Config->OutputFile + Twine(I) + ".lto.o");
+    }
+    Ret.emplace_back(Buff[I].data(), Buff[I].size());
+  }
+
+  return Ret;
+}

wasm/Options.td

 
 // Aliases
 def alias_entry_e: JoinedOrSeparate<["-"], "e">, Alias<entry>;
 def alias_entry_entry: J<"entry=">, Alias<entry>;
 def alias_initial_memory_i: Flag<["-"], "i">, Alias<initial_memory>;
 def alias_max_memory_m: Flag<["-"], "m">, Alias<max_memory>;
 def alias_relocatable_r: Flag<["-"], "r">, Alias<relocatable>;
 def alias_undefined_u: JoinedOrSeparate<["-"], "u">, Alias<undefined>;
+
+// LTO-related options.
+def lto_aa_pipeline: J<"lto-aa-pipeline=">,
+  HelpText<"AA pipeline to run during LTO. Used in conjunction with -lto-newpm-passes">;
+def lto_newpm_passes: J<"lto-newpm-passes=">,
+  HelpText<"Passes to run during LTO">;
+def lto_partitions: J<"lto-partitions=">,
+  HelpText<"Number of LTO codegen partitions">;
+def disable_verify: F<"disable-verify">;
+def opt_remarks_filename: Separate<["--"], "opt-remarks-filename">,
+  HelpText<"YAML output file for optimization remarks">;
+def opt_remarks_with_hotness: Flag<["--"], "opt-remarks-with-hotness">,
+  HelpText<"Include hotness information in the optimization remarks file">;
+def save_temps: F<"save-temps">;
+def thinlto_cache_dir: J<"thinlto-cache-dir=">,
+  HelpText<"Path to ThinLTO cached object file directory">;
+defm thinlto_cache_policy: Eq<"thinlto-cache-policy">,
+  HelpText<"Pruning policy for the ThinLTO cache">;
+def thinlto_jobs: J<"thinlto-jobs=">, HelpText<"Number of ThinLTO jobs">;

wasm/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_WASM_SYMBOL_TABLE_H
 #define LLD_WASM_SYMBOL_TABLE_H
 
 #include "InputFiles.h"
+#include "LTO.h"
 #include "Symbols.h"
 #include "llvm/ADT/CachedHashString.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/Support/raw_ostream.h"
 
 using llvm::wasm::WasmGlobalType;
 using llvm::wasm::WasmSignature;
 

 // 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 the
 // add*() functions, which are called by input files as they are parsed.
 // There is one add* function per symbol type.
 class SymbolTable {
 public:
   void addFile(InputFile *File);
+  void addCombinedLTOObject();
 
   std::vector<ObjFile *> ObjectFiles;
+  std::vector<BitcodeFile *> BitcodeFiles;
   std::vector<InputFunction *> SyntheticFunctions;
   std::vector<InputGlobal *> SyntheticGlobals;
 
   void reportRemainingUndefines();
 
   ArrayRef<Symbol *> getSymbols() const { return SymVector; }
   Symbol *find(StringRef Name);
 

 
 private:
   std::pair<Symbol *, bool> insert(StringRef Name);
 
   llvm::DenseMap<llvm::CachedHashStringRef, Symbol *> SymMap;
   std::vector<Symbol *> SymVector;
 
   llvm::DenseSet<llvm::CachedHashStringRef> Comdats;
+
+  // For LTO.
+  std::unique_ptr<BitcodeCompiler> LTO;
 };
 
 extern SymbolTable *Symtab;
 
 } // namespace wasm
 } // namespace lld
 
 #endif

wasm/SymbolTable.cpp

 using namespace lld::wasm;
 
 SymbolTable *lld::wasm::Symtab;
 
 void SymbolTable::addFile(InputFile *File) {
   log("Processing: " + toString(File));
   File->parse();
 
-  if (auto *F = dyn_cast<ObjFile>(File))
+  // LLVM bitcode file
+  if (auto *F = dyn_cast<BitcodeFile>(File))
+    BitcodeFiles.push_back(F);
+  else if (auto *F = dyn_cast<ObjFile>(File))
     ObjectFiles.push_back(F);
 }
 
+// This function is where all the optimizations of link-time
+// optimization happens. When LTO is in use, some input files are
+// not in native object file format but in the LLVM bitcode format.
+// This function compiles bitcode files into a few big native files
+// using LLVM functions and replaces bitcode symbols with the results.
+// Because all bitcode files that the program consists of are passed
+// to the compiler at once, it can do whole-program optimization.
+void SymbolTable::addCombinedLTOObject() {
+  if (BitcodeFiles.empty())
+    return;
+
+  // Compile bitcode files and replace bitcode symbols.
+  LTO.reset(new BitcodeCompiler);
+  for (BitcodeFile *F : BitcodeFiles)
+    LTO->add(*F);
+
+  for (StringRef Filename : LTO->compile()) {
+    auto *Obj = make<ObjFile>(MemoryBufferRef(Filename, "lto.tmp"));
+    Obj->parse();
+    ObjectFiles.push_back(Obj);
+  }
+}
+
 void SymbolTable::reportRemainingUndefines() {
   SetVector<Symbol *> Undefs;
   for (Symbol *Sym : SymVector) {
     if (Sym->isUndefined() && !Sym->isWeak() &&
         Config->AllowUndefinedSymbols.count(Sym->getName()) == 0) {
       Undefs.insert(Sym);
     }
   }
Symbol *SymbolTable::find(StringRef Name) {
   return SymMap.lookup(CachedHashStringRef(Name));
 }
 
 std::pair<Symbol *, bool> SymbolTable::insert(StringRef Name) {
   Symbol *&Sym = SymMap[CachedHashStringRef(Name)];
   if (Sym)
     return {Sym, false};
   Sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
+  Sym->IsUsedInRegularObj = false;
   SymVector.emplace_back(Sym);
   return {Sym, true};
 }
 
 static void reportTypeError(const Symbol *Existing, const InputFile *File,
                             llvm::wasm::WasmSymbolType Type) {
   error("symbol type mismatch: " + toString(*Existing) + "\n>>> defined as " +
         toString(Existing->getWasmType()) + " in " +
static bool shouldReplace(const Symbol *Existing, InputFile *NewFile,
 
   // Neither symbol is week. They conflict.
   error("duplicate symbol: " + toString(*Existing) + "\n>>> defined in " +
         toString(Existing->getFile()) + "\n>>> defined in " +
         toString(NewFile));
   return true;
 }
 
 Symbol *SymbolTable::addDefinedFunction(StringRef Name, uint32_t Flags,
                                         InputFile *File,
                                         InputFunction *Function) {
   LLVM_DEBUG(dbgs() << "addDefinedFunction: " << Name << "\n");
   Symbol *S;
   bool WasInserted;
   std::tie(S, WasInserted) = insert(Name);
 
+  if (!File || File->kind() == InputFile::ObjectKind)
+    S->IsUsedInRegularObj = true;
+
   if (WasInserted || S->isLazy()) {
     replaceSymbol<DefinedFunction>(S, Name, Flags, File, Function);
     return S;
   }
 
+  if (Function)
     checkFunctionType(S, File, &Function->Signature);
 
   if (shouldReplace(S, File, Flags))
     replaceSymbol<DefinedFunction>(S, Name, Flags, File, Function);
   return S;
 }
 
 Symbol *SymbolTable::addDefinedData(StringRef Name, uint32_t Flags,
                                     InputFile *File, InputSegment *Segment,
                                     uint32_t Address, uint32_t Size) {
   LLVM_DEBUG(dbgs() << "addDefinedData:" << Name << " addr:" << Address
                     << "\n");
   Symbol *S;
   bool WasInserted;
   std::tie(S, WasInserted) = insert(Name);
 
+  if (!File || File->kind() == InputFile::ObjectKind)
+    S->IsUsedInRegularObj = true;
+
   if (WasInserted || S->isLazy()) {
     replaceSymbol<DefinedData>(S, Name, Flags, File, Segment, Address, Size);
     return S;
   }
 
   checkDataType(S, File);
 
   if (shouldReplace(S, File, Flags))
     replaceSymbol<DefinedData>(S, Name, Flags, File, Segment, Address, Size);
   return S;
 }
 
 Symbol *SymbolTable::addDefinedGlobal(StringRef Name, uint32_t Flags,
                                       InputFile *File, InputGlobal *Global) {
   LLVM_DEBUG(dbgs() << "addDefinedGlobal:" << Name << "\n");
   Symbol *S;
   bool WasInserted;
   std::tie(S, WasInserted) = insert(Name);
 
+  if (!File || File->kind() == InputFile::ObjectKind)
+    S->IsUsedInRegularObj = true;
+
   if (WasInserted || S->isLazy()) {
     replaceSymbol<DefinedGlobal>(S, Name, Flags, File, Global);
     return S;
   }
 
   checkGlobalType(S, File, &Global->getType());
 
   if (shouldReplace(S, File, Flags))

wasm/Symbols.h

public:
 
   // Get/set the index in the output symbol table.  This is only used for
   // relocatable output.
   uint32_t getOutputSymbolIndex() const;
   void setOutputSymbolIndex(uint32_t Index);
 
   WasmSymbolType getWasmType() const;
 
+  // True if this symbol was referenced by a regular (non-bitcode) object.
+  unsigned IsUsedInRegularObj : 1;
+
 protected:
   Symbol(StringRef Name, Kind K, uint32_t Flags, InputFile *F)
-      : Name(Name), SymbolKind(K), Flags(Flags), File(F),
-        Referenced(!Config->GcSections) {}
+      : IsUsedInRegularObj(false), Name(Name), SymbolKind(K), Flags(Flags),
+        File(F), Referenced(!Config->GcSections) {}
 
   StringRef Name;
   Kind SymbolKind;
   uint32_t Flags;
   InputFile *File;
   uint32_t OutputSymbolIndex = INVALID_INDEX;
   bool Referenced = false;
 };

 T *replaceSymbol(Symbol *S, ArgT &&... Arg) {
   static_assert(std::is_trivially_destructible<T>(),
                 "Symbol types must be trivially destructible");
   static_assert(sizeof(T) <= sizeof(SymbolUnion), "Symbol too small");
   static_assert(alignof(T) <= alignof(SymbolUnion),
                 "SymbolUnion not aligned enough");
   assert(static_cast<Symbol *>(static_cast<T *>(nullptr)) == nullptr &&
          "Not a Symbol");
-  return new (S) T(std::forward<ArgT>(Arg)...);
+
+  Symbol SymCopy = *S;
+
+  T *S2 = new (S) T(std::forward<ArgT>(Arg)...);
+  S2->IsUsedInRegularObj = SymCopy.IsUsedInRegularObj;
+  return S2;
 }
 
 } // namespace wasm
 
 // Returns a symbol name for an error message.
 std::string toString(const wasm::Symbol &Sym);
 std::string toString(wasm::Symbol::Kind Kind);
 
 } // namespace lld
 
 #endif